An approach to identifying information objects (IOs), data about which is received by the monitoring system from independently operating sources, is presented. It considers a situation where data about the same physical object can be entered multiple times into an information resource, as about different objects. At the same time, the values of such IOs features do not completely coincide, since the data sources introduce some operation errors. The proposed approach for object identification is based on a new proximity (similarity) measure of information objects, which takes into account the existing probabilistic uncertainty regarding the values of quantitative features and the uncertainty of the possibility type for qualitative features.
The majority of information systems have a functionally, and sometimes organizationally dedicated monitoring subsystem, the aim of which is to extract (obtain) data about the external environment and the state of the system as a whole. This work focuses on one of the problematic tasks of forming an information resource that is populated with data from monitoring the external environment, shaped by the actions of dynamic objects in the surrounding space. As the number of monitored objects increases, along with expanding the means of monitoring, or when multiple monitoring systems are integrated into a higher-level system, there is an increased probability that data about the same object can independently be entered into the common information resource of the monitoring system. This situation is typical for cases when the monitoring system (or subsystem, if the monitoring system is hierarchical) simultaneously analyzes objects in the surrounding space in overlapping spatial areas. Figure 1 schematically shows several overlapping areas monitored by different data sources (DS), and, accordingly, a few sources can observe the same physical (real) objects. The set of features of such objects, determined by the data source, will be called an information object (IO). Essentially, the IO, formed by a suitable data source, is an information representation of a real object in the system’s information resource in the form of a finite set of features and their values.
In the case described above, there is a need to solve the problem of identifying IOs, that is, attributing them to a single physical object, with the subsequent unification (aggregation) of the characteristics of such (identified) IOs. In the simplest case, the values of IO features that refer to the same real object should completely coincide, even if they are determined by different data sources. Such a coincidence would make it quite easy to classify a certain number of IOs as those describing the same physical object, provided that in the area of the monitoring system operation, there are no different objects with completely identical observational characteristics. Regarding the latter condition, we would additionally note that if the monitoring system allows the formation of completely identical IOs without additional (marking) data that refer to different physical objects, this indicates its insensitivity to certain differences in the external environment, which can be seen as a flaw.
In our case, given that among the key object features in the surrounding space are the static or
time-varying coordinates of their location, we can reasonably assume that the condition above is
satisfied. However, even if the feature values for different IOs referring to the same real object are
equal, there would be a need to identify such IOs due to the fact that not all sources are able to
determine the full list of features. Therefore, even in such a simple case, to solve the problem of
identifying the IO, it would be necessary to introduce and analyze a certain IO proximity measure,
such as Rao coefficients [
The problem of determining which observations or descriptions correspond to the same object
(object instance) exists in various fields. These can be image recognition and analysis, natural
language generation and processing, text processing, integration of information resources, etc. For
example, to track a moving object in computer vision systems, it is necessary to identify whether
two shapes in different frames of a video stream are actually the same object. Creating a distributed
information system with a common information space involves merging separate databases. As a
result, it is necessary to determine which records belong to the same entity and solve the
integration task when incomplete matching of their attributes. When preparing reference lists in
articles, it is necessary to find which citations refer to the same papers to avoid duplication. In
natural language processing, a key task is to determine which phrases (word combinations) refer to
the same entity. An object identification for databases data merging/cleansing, record linking and
duplicate removal was first formulated as a separate problem by Newcombe et al. [
There are currently numerous developments in this area, including Wang and Ji [
The set of information objects that will be used by an information system is first defined during its design phase. Later, over the life of the system, this set is supplemented and edited in accordance with users’ information needs. IOs can describe: for the set of features of information objects set , = 1 …
– association relationship (semantic relations).
= 〈 , , , 〉, = 〈 , , 〉, = = 1 … . – a set of IO features (attributes) = { | = 1 … }. – a set of constraints on the object attribute values : → . – a mapping to set constraints for each attribute.
In general, information objects are interconnected and interdependent. Let us define the set of relations between IOs as follows: where – inheritance relationship ("class-subclass") ( , ), where is an upper class – aggregation relationship ("included in") , , where features are included in (1) (2)
The total set of possible IO features can be divided into features of a quantitative and qualitative
nature. The values of quantitative features are determined using certain measuring instruments
and, accordingly, are characterized by uncertainty of the type "probability", since any means of
measurement has limited, albeit defined, accuracy. The values of qualitative features are
determined by the active participation of a person, and therefore contain a subjective component,
which today is usually described by uncertainty of the type "possibility" [
, where – an index of an object feature ( = 1, ), L – total number of features; = = 1, 0, − ℎ 1,
ℎ 0, ℎ ≤ , ; (for quantitative features)
(for qualitative features ) - quantitative proximity threshold for the -th feature.
As can be seen from expression (3), Zhuravlev's measure for quantitative features allows the possibility of some slight difference in their values, within which it is assumed that the features still coincide. That is, a threshold analysis of the proximity of such feature values is used. It should be noted that determining the threshold value when solving a specific problem is up to the researcher. Such a possibility is not provided for qualitative features, and only complete coincidence/difference of their values is allowed.
Let us consider the acceptability of the approach to accounting for the possible difference in the quantitative feature values − =
through defining some admissible value of it - . It is known that measurement errors of various quantities are distributed according to a certain law of probability distribution. This distribution is characterized by the mathematical expectation of the error (the average error value, which is equal to zero in the absence of a systematic component), the standard deviation from its mathematical expectation (mean square error - MSE), and other higher-order moments.
It is generally accepted that measurement errors are most often distributed according to a normal law. Let us assume this statement is true for all our cases. Then the measurement error distribution for quantitative features is completely determined by the first order moment (mathematical expectation) and the second order moment - the dispersion, or the standard deviation of the random variable. It is quite obvious that when the linear distance between the measured feature values decreases, the probability that the obtained measured values actually refer to the same true value will increase nonlinearly, in accordance with the distribution laws of their measurement errors with two different means (which are generally characterized by different MSE). In addition, if the measured feature values coincide, but the values were obtained with an error, then such a coincidence cannot be guaranteed to mean a coincidence of the true values.
This paper proposes an alternative method for calculating the degree of proximity between the quantitative feature values, which takes into account the probabilistic nature of the process of their definition by different sources. The currently known proximity measures between two measured (quantitative) feature values require calculating the probability that the true value of the feature for both measurements is actually the same value. Calculating such a probability requires full knowledge of the probability distribution laws for measured values (not just the measurement errors) and, therefore, the true value of the measured quantity. In our problem, this value is unknown. Taking into account the above, it is proposed to formalize the quantitative feature values by the normal distribution law of their determination errors, where the feature value obtained from the source is considered as the mathematical expectation. Data on the standard measurement error is expected to be obtained from the data source or determined based on its characteristics as a measurement means. Then the coincidence of the feature values obtained from two sources can be considered dependent on the probability of finding the true value in the intersection area of the two distribution laws, which can be calculated based on the Laplace function, the probability multiplication theorem for independent events and the well-known "three sigmas" rule. The expression for calculating the probability of finding a random variable x in the interval (с, d) with its normal distribution has the following form (4) − − Ф − , where Ф() – Laplace function m – mathematical expectation of a random variable.
actually within the range of values ( ≤ ≤ ): = ( , ) ∙ ( , ), where ( , ) and ( , ) - the probabilities that the feature values for each measurement are within the interval (с, d).
Consider the example shown in Figure 2. Let the value of the attribute x be measured by two different sources. The obtained measurement results are: = 12 and = 18 units. In this case, the MSE for measurement errors for each source are: = 3, = 2, and = 18 − 12 = 6.
specified probability) for two variables - (taking into account the "three sigmas" rule) are determined as the difference between the smaller value from the pair + 3 and the larger value from the pair For the case shown in Figure 2: − 3 + 3 and = 21; − 3 , where + 3
Next, we calculate the probability that the true value of each measurement is in the range from two data sources.
= 14 and = 17 units (other parameters are the same as in the previous case), = 17 − 14 = 3.
For this case: + 3 = 23; + 3 = 23; − 3 = 5; − 3 = 11 and, respectively,
= (11,23). Next we calculate
(11 ≤ ≤ 23) = Ф (11 ≤ ≤ 23) = Ф 2
3 23 − 14
11 − 14 23 − 17
11 − 17 − Ф − Ф 2 3
= 0,84, = 0,9973.
= 0,8377.
Let's perform another calculation to analyze the change nature in the proposed proximity measure and set = 15 and = 17 units ( = 2). Then: + 3
probability calculated by the expression (1):
≈ 1. If they do not intersect within 3, the value will be equal to zero.
Comparing the calculation results, it can be stated that as the difference between the two feature value measurements
obtained from different data sources decreases, the value of the proximity measure increases. Additionally, the measure value changes nonlinearly in relation to the linear change of
in accordance with the distribution laws of measurement errors of the
feature value. Testing the proposed measure for compliance with known conditions for its
acceptability and validity (non-negativity, symmetry, maximum similarity of an object to itself, and
the “triangle inequality” [
features is that the probability (and therefore the measure) changes from 0 to 1, i.e., it is immediately normalized. That is, calculating proximity values for different features does not require their transformation when determining the common proximity for all features.
especially since it is based on a probability analysis that has a specific physical meaning. Also, this proximity measure is simply transformed into a distance measure by its inversion
Let us consider the problem of calculating the possibility that two specified values of a certain qualitative feature are actually the same value. At the same time, it is important to remember that a qualitative characteristic can be expressed in numbers and still retain its qualitative character, since this feature character is determined not by the form of its expression (reflection), but by the method of its acquisition.
To determine the proximity measure between the values of qualitative features, it is proposed to use their formalization in the form of fuzzy sets by constructing a triangular membership function for each obtained feature value on a clear set of its possible values (an example is shown in Figure 3). The number of feature values in the support sets is determined by the possibility of other feature values in reality (which can be considered a certain analogue of measurement error for quantitative attributes). Then the distance between the qualitative feature values can be defined as the maximum value of the set, which is the intersection of two fuzzy sets (formalized feature values). So the expression for the proximity measure is (5) (6) the form of fuzzy sets where and
– clear values of the feature x () ,
() – membership functions of fuzzy sets constructed for both values of the qualitative feature.
= 18. The region of clear feature values, which are covered by non-zero values of the membership function, is specified by the maximum possible errors in the feature determination. As a result, the proximity measure is between the obtained values = 0,67. It is obvious that if the clear feature values approach each other, the value of the proximity measure approaches 1. Otherwise, it approaches zero.
= 1 −
and some constant value for all other members of the set, which will characterize the possibility of false determination of the feature. Therefore, if the IO feature values obtained from two sources do not coincide, their proximity will be determined by this value , regardless of the feature values
Note, if, instead of the error distribution laws, we use their triangular approximation for quantitative characteristics, the triangle inequality condition will also be met. 6. Determining the proximity measure (metric) for IOs on the set of themselves. for the measures’ validity.
their features (7) (8) To determine the metric (function) of IOs similarity by all features, we can use one of the known additive functions with normalization by the number of values of quantitative and qualitative features and, if necessary, different weight values for each feature, or subsets of quantitative and qualitative features as a whole. It is desirable that the sum of the weight coefficients be equal to 1. Considering the different natures of uncertainty for quantitative and qualitative features, the most acceptable expression for determining the distance measure between IOs on the set of their features is = – the weight coefficients for quantitative features.
The final stage of solving the identification problem may be the analysis of the IOs’ behavior (actions) over time from the point of view of possible changes in their feature values. This analysis requires setting a criterion by which IOs are considered to be identified as a single object, given the variable distance (proximity) between them over time. Such a criterion will be determined by the characteristics of the chosen distance metric and the specific application problem. For example, if the same physical object is observed by two data sources over several cycles of information update, increasing the probability of correct object identification can be achieved by analyzing the linear trend ( ) of the change in the distance metric (proximity). For this purpose, the well-known least squares method (LSM) can be applied. Let us denote the distance metric value between two IOs at numbers natural numbers we get and the expression for the sum of the squares of the first N terms of the arithmetic progression of = =
( + 1) ( + 1)(2 + 1)
, 2 6 (9) (10) (11) (12) (13) time i as . Then, using the expression obtained based on LSM to calculate the trend line slope and substituting successive time stamps from the interval = 1, into it, we obtain = − −
Using expressions for the sum of the first N terms of the arithmetic progression of natural = − ( + 1) 2 ( + 1)(2 + 1) 6 − ( + 1) 2
We can finally write after simplifications to define = − ( + 1) 2 ( 12 − 1)
This suggests that if these IOs were the candidates to be identified as one object by separate values , then most likely these IOs really belong to the same physical object. If the value is negative, then the distance between the IOs decreases over time, and therefore, the possibility that the identification problem is solved correctly increases. If the value is significantly greater than zero, most likely the IOs under consideration should not be identified as a single object, and the low value
at a particular point in time from the interval was random. Moreover, a larger value gives greater confidence that the IO data refers to different physical objects.
The paper proposes a method for solving the problem of identifying IOs that enter the monitoring system’s common information resource from several data sources. For this purpose, it is proposed to use a new proximity measure (similarity) of IO, which takes into account the nature of uncertainty of the type "probability" for quantitative features and the type "possibility" for qualitative features. At the same time, it does not require the transformation of feature values, which significantly simplifies the formation of a metric – a proximity (or distance) function between IOs as a whole according to all available features. The proposed measure was checked for compliance with the mandatory conditions for the validity of measures.
between the IOs to be identified, which can be calculated using the least squares method, which improves the quality of solving the identification problem.