The paper describes method for situations assessment based on retrieving information about similar earlier observed conditions. Situation is a set of qualitative and quantitative characteristics that describe states of interrelated objects. Object states are defined by measurement parameters. A method for situation assessment is based on calculation of aggregated indices and their comparison was developed. For calculating aggregated indices it is proposed to use an algorithm for alphabetic description of time series that provide convenient means for their comparison. For situations retrieval it is suggested to use FCA methods. As a case study the results of ocean data analyses for calculating temperature and salinity parameters of water area are presented.
Nowadays Intelligent Geographic Information Systems (IGIS) are widely used for solving different functional tasks. IGIS incorporates GIS interface as well as various methods of artificial intelligence intended for solving certain intricate problems including problem of decision making support. Decision support systems in IGIS are aimed to provide end users with complex information about the solved problem as well as with reasonable alternative decisions in real time with a pictorial rendition of this information to let it be easily perceived and used.
One of the important tasks, that is solved in decision making support systems, is
situation assessment and awareness. Situation assesment is aimed to make situations
understandable by users. Situation awareness is the perception of the elements in the
environment within a volume of time and space, the comprehension of their meaning,
and the projection of their status in the near future [
Problem of situation assessment can be decomposed into two subtasks. The first task is situation recognition and the second is making decision about system state. For situation recognition an approach based on comparing situations to ones that were earlier observed is widely used. To provide this knowledge base of situations a description is formed. Decision about system state is based on knowledge about recognized situations. Various directions of situation development can be considered using modeling tools or expert systems.
By now one of the key means for storing information about systems actual states are measurements instruments that provide information about system parameters in real time. Using these measurements ability to analyze the dynamic of a state evaluation and control a system state is provided. There are several problems related with measurements processing. First problem is great volume of data that has to be processed in limited time. Second problem is that measurements have rather bad quality; they are not coordinated in time and space and are implemented as non-stationary time series. Consequently, highly specialized methods have to be used for measurements processing. Third problem is a necessity to represent measurements as a set of complex characteristics, so that they can be used in methods of situation assessment.
In the paper an approach to situation assessment based on comparison of situations is extended for using measurements of system parameters as one of important information sources and approach to retrieval situations using formal concept analyses (FCA) methods is proposed. In the second section general description of the method for situation assessment based on measures analyses in presented. Following sections provide detailed description of algorithms used in the general method. An algorithm of alphabetic representation of time series given in section 3 is aimed to represent time series in a form that provides easy mechanism for comparing parameters. In section 4 the algorithm of identification of information valuable parameters that allow ranging parameters according to information values is considered. In section 5 algorithm for objects aggregated indicators calculating that takes into account values of parameters measurements is presented. Algorithms for building and comparing graphs that describe situations in terms of objects and their relations are discussed in section 6. In section 7 application of Formal Concept Analysis methods for revealing earlier observed distinguishable situations are considered. As a case study task of ocean parameters estimation using measurements provided by floating hydrographic buoys is described. 2
FCA is a well-established technique in mathematics that is widely used for
solving various tasks of intelligent data analyses. Standard FCA definitions are introduced
in [
AI {m M | g A : g Im};
BI {m M | m B : g Im} .
AI is the set of attributes common to all objects of A and BI is the set of objects that share attributes of B . For simplicity operator ()' is used instead of ()I . The double application of ()' is a closure operator; it is extensive, idempotent, and monotonous. Therefore, sets A'' and B'' are closed sets.
A formal concept of the context (G, M , I ) is a pair ( A, B) , where ( A G) , (B M ) , A B' , and B A' . In this case A A'' and B B'' . The set A is called the extent and B is called the intent of the concept ( A, B) . In categorical terms a formal concept is defined by its objects A or its attributes B .
A concept ( A, B) is a subconcept of (C, D) and (C, D) is a superconcept of ( A, B) if ( A C) (equivalently, (D B) ). For ( A, B) and (C, D) relations , , , and are defined and written as usual. ( A, B) is a lower neighbor of (C, D) (notation is (A, B) (C, D) ) and (C, D) is an upper neighbor of (A, B) (notation is (C, D) ( A, B) ) if ( A, B) (C, D) and there is no (E, F) : ( A, B) (E, F) (C, D) . The set of all concepts ordered by forms a concept lattice of the context K, that is denoted by B(K ) . The relation defines edges in the covering graph of B(K ) .
For building lattices while solving task of situations analyses formal context as a set of objects G situations are considered, M is a set of situations characteristics, I is an incidence relation between these sets. Each situation s is characterized by a set of relevant objects E {Oi}iN1 and relations between objects R {ri, j}i, j1 , where N N
M is a total number of objects. For each object a set of parameters e {Pi}i1 that describes objects state is defined. 3
Situation assessment is based on comparing current conditions with the previously observed ones. Situation involves objects that can be technical or natural and relation between them. Relations are described for pairs of objects, for each relation its type is defined. All types are to be described a priori in a vocabulary of subject domain. An object state is characterized with a set of parameters; values of parameters are measured using various measurement instruments and are represented as time series.
When solving problem of situation assessment it is necessary to provide an effective and efficient mechanism for situation comparing to retrieve similar ones. For comparing two situations it is necessary to compare list of objects and their states and relations between objects. Objects and relations between objects are reasonable to represent as a graph, where vertexes of the graph are objects and edges of the graph are relations.
For comparing two graphs a wide range of methods is developed. The most
convenient algorithm for similar situations retrieval is based on graph edit distance. The
main idea of this algorithm is to define difference between graphs using a set of
editing operations that are necessary for transforming one graph to the other. This method
is tolerant to errors and provides inexact graph matching. Algorithms for graph edit
distance calculation are described in [
For describing parameters measurements it is proposed to use alphabetic
representation of time series. To build alphabetic representation method based on Symbolic
Aggregate Approximation (SAX) [
For solving the second task Aggregated Indices Randomization Method (AIRM)
[
General description of proposed method for situation assessment is given in Fig.1 ____________________________________________________________________ Input data. Data base of graphs describing earlier observed situations, description of estimated situa
N N tion, that includes E {Oi}i1 is a set of objects, R {ri, j }i, j 1 is a set of objects relations,
M O {Pi}i1 is set of objects parameters, P {(ti , xi )}iH1 is a time series of parameters measurements, where H is a total number of measurements.
Output data. S {(si , qi )}Ti1 is a set of situations s that are similar to a defined situation s d with similarity degree q .
Algorithm description A. Building description of estimated situation Step A1 build symbolic representation of objects parameters measurements Cˆ fsymb(P) Step A2 Building descriptions of objects
calculate weights of parameters W {wi}iM according to information value calculate estimations of aggregated indices for objects Q {Q~i}iN1 ~ B. Building graph for situation description Step B1 Defining graph vertexes GV using formalized descriptions of objects Step B2 Defining graph edges GD using formalized descriptions of objects relations C. Situation estimation Step C1. Reveling similar graphs of situation description in data base Step C2. Ranging graphs according to degree of similarity S {(si , qi )}Ti1 ____________________________________________________________________
Fig.1 General description of method for situation assessment 4
Proposed algorithm of alphabetic representation is based on algorithm of
Symbolic Aggregate Approximation (SAX) described in [
Algorithm description Step 1. calculate length of one segment l H
z Step 2 for ( i 1... z )
ci f ({c j}ljil( j1)1) , where f is a function of calculating segment statistical characteristics ____________________________________________________________________ Fig.2 Algorithm for building PAA representation of time series ____________________________________________________________________
Input data. P p1, ..., pH is an initial time series, where H is a number of segments, A a1, ..., ak is an alphabet for time series symbolic representation, B 1, ..., k 1 are levels of time series representation.
Output data. Cˆ cˆ1, ..., cˆz is asymbolic representation of time series.
Algorithm description Step 1. calculate C using algorithm for PAA representation of time series Step 2. calculate range of time series characteristic values [ Vl , Vh ], where Vl - low border, Vh - high border Step 3. calculate range of characteristics values for each level Step 4. for ( i 1... w ) define alphabet symbol cˆi a j j1 c j j
z Step 5. concatenate symbols Cˆ {cˆi}i1 ____________________________________________________________________
Fig.3 Algorithm for building time series symbolic representation
By now many algorithms that allow to deal with strings, in particular, algorithms of inexact string comparison, based on calculation of Edit Distance are developed. Algorithms of string comparison are applied for qualitative evaluation of time series similarity. 5
Each object is described by a set of various parameters. Degree of information value of each parameter differs and it is necessary to take it into account when two objects are compared. The degree of parameter information value is used to range parameters in algorithm of calculating objects aggregated indices.
The proposed algorithm of calculating degree of parameter information value is
based on using a set of statistical characteristics. Depending on objects characteristics
different measures for time series described in [
M
Output data. P is a sorted set of parameters, W {wi}i 1 is a list of preliminary weight coefficients for parameters.
Algorithm description A. Calculating measures for parameters time series
Step A1. for each parameter (i 1... M ) for each object ( j 1... N)
calculate measures sij (s1ij , ..., siUj ) calculate mean distance si 1
N
M M (sik sil )2 k 1 l 1 B. Ranging parameters
Step B1 for (i 1... M )
define preliminary weights wi si
Step B2 sort parameters according to preliminary weights P sort({Pi}iM1) ____________________________________________________________________
Fig.4 Algorithm for ranging parameters 6
To calculate objects aggregated indicators based on set of parameters it is proposed to use indices randomization method. ARIM is used to solve tasks of multiple criteria decision making on the base of poor-quality input information. The main advantage of AIRM is its ability to cope with non-numeric (ordinal), non-exact (interval) and non-complete information. When solving user’s tasks information about objects parameters is often incomplete as parameters due to different reasons can’t be gathered. Calculated in section 5 preliminary weights of parameters provide approximate estimation of parameters information value and therefor can’t be used directly for calculating objects aggregated indicators. Preliminary parameters weights are used to range parameters and thus provide ordinal information about parameters. This information can be effectively used in AIRM.
In ARIM three key steps are executed: i) building vector of single indicators; ii) defining aggregative function; iii) defining weighs coefficients.
Main features of ARIM application for calculating objects indicators using measurements are the following:
1. Results of symbolic representation of time series of parameters measurements build according to algorithm described in section 3 are considered as list of objects characteristics.
2. Single indicators for objects are functions of objects characteristics. They are defined as normalizing power functions of degree one. When characteristic values increase functions also increase.
3. An aggregative indicator is a synthesized function that characterizes each object in general. It depends on weight coefficients and is represented in a form of linear convolution of single indicators functions and weight coefficients.
4. As information I about objects parameters weights is incomplete, weightvector w (w1, ...,wm ) is ambiguously determined. In ARIM this vector is determined with accuracy to within a set w(I ) of all admissible weight-vectors. An uncertain choice of a weight-vector from set w(I ) is modeled by a random choice of an element of the set according to the concept of Bayesian randomization. Such randomization produces a random weight-vector w(I ) (w1(I ), ...,wm (I )) , which is uniformly distributed on the set w(I ) . Set w(I ) is reduced using ordinal and interval information. Mathematical expectation of random weight coefficient wi (I ) may be used as a numerical estimation of particular indicator qi significance. Then randomized weight-vector can be defined as w~(I ) (w~1(I ),...,w~M (I )) . The precision of this estimation is measured by standard deviation of the corresponding random variable.
The algorithm for objects summary indicators calculating is given in Fig.5. ____________________________________________________________________ Input data. E {Oi}i1 is a set of objects, O {Cˆi}i1 is a set of symbolic representation of N M z measured objects parameters, where M is a total number of objects parameters, Cˆ {cˆi}i1 is a symbolic representation of parameter, where z is a length of symbolic representation.
~ ~ N Output data. Q {Qi}i1 are estimations of objects aggregated indicators.
Algorithm description Step 1. for each object ( 1, ..., N )
define Cˆ (cˆ1, ..., cM ) as set of initial characteristics calculate vector of single indicators q (q1, ..., qM ) , 0, cˆ j MIN j q j q j (cˆ j ) MAX j MIN j 1, ,
cˆ j MIN j , MIN j cˆ j MAX j ,
cˆ j MAX j ; MIN j and MAX j - minimum and maximum values of characteristic calculate randomized weight-vector for characteristics w~i (w~1,...,w~M ) calculate aggregated indicator A situation graph contains information about objects, a set of characteristic that are sufficient for objects description, and relations between objects. Building a situation graph assumes following main steps: i) making a list of objects that are significant for situation description; ii) defining set of objects characteristics; iii) defining set of admissible relations between objects; iv) building structure of the graph. All tasks are enumerated but the last one is solved by experts manually. A set of objects characteristics contains aggregated characteristics of measured parameters that are defined in section 5 and it may also contain one or several additional characteristics. Usually, as additional characteristics, time and earth coordinates of parameters measurements are considered. The algorithm for building situation graph is given in Fig. 6. ____________________________________________________________________
N N Input data. E {Oi}i1 is a set of objects, R {ri, j }i, j 1 is a set of objects relations,
Y F { fi}i1 is a set of object characteristics, where Y is a total number of object characteristics.
Output data. G GV , GD is a situation graph, GV are graph vertexes and GD aregraph edges.
Algorithm description Step 1. define empty graph GV [] , GD [] Step 2. create vertexes from objects GV E Step 3. create edges for related objects GD R Step 4 for each vertex vi GV (i 1, ..., N)
define attributes Avi av (Oi ) according to characteristics of object Oi Step 5. for each edge di, j d (Oi , Oj ) , i 1, ..., N , j 1, ..., N if ( di exists)
define attributes Adi ad (ri, j ) according to defined relation between objects Oi , O j ____________________________________________________________________
Fig.6 Algorithm for building situation graphs
Widely used methods for comparing graphs are based on calculation of graph edit
distance [
k min c(ei ) , where are all possible edit paths, e is a (e1, ...,ek )(G1, G2 ) i1 graph editing operation, c(e) is the cost of operation e . The key advantage of these methods is their flexibility as methods are able to deal with any graphs and any types of vertex and edge attributes. The standard set of graphs operations include following operations: adding, removing and modifying elements.
The described group of methods allows finding optimal solution, but is
complicated from computational point of view. Due to this fact if situation description
contains considerable number of object and relations, it is proposed to use suboptimal
methods for graph comparison [
The alternative approach for suboptimal graph comparing is based on using
Hungarian method [
In case if a priori knowledge about objects and their relations for different types of situations is available, complexity of comparing graphs methods can be significantly reduced. 8
The approach for situations assessment based on building and comparing graphs
supposes that a data base of situations is created a priori. The task of creation of a
universal mechanism for distinguishable situations retrieval is highly complicated as
situations are often rather similar; they have a number of equal characteristics,
relations and involved objects. Since there are many situations and each situation is
described by huge volume of heterogeneous data it is proposed to use Formal Concept
Analysis methods [
To build lattices formal context K is defined using a set of defined situations and
their characteristics. Characteristics can be binary, quantitative or qualitative. Binary
characteristics can be used directly for building a context. Qualitative characteristics
can be considered as a set of adjusted characteristics, where each of characteristics
values correspond to one adjusted characteristic. For representation of quantitative
characteristics in binary form nominal scales can be used. This approach is rather
flexible as it allows user to modify scales manually. It is also possible to build lattices
using multivalued contexts that are defined as K (G, M , W, I ) , where W is a set
of situations characteristics values, I is a ternary relation, I G M W I ,
where process of scaling is automated. Approaches for building lattices using
multivalued contexts are described in [
The algorithm for revealing situations using FCA supposes executing of three
main stages. The first stage assumes building formal context for representation
situations and their characteristics. As objects of formal context a preliminary list of
situations defined by experts is used. A list of context features contains set of three
characteristics for each involved subject domain object. A set of used characteristics is equal
to the set that is used for building graphs. Each object is characterized by i) its name
or id, ii) its location in space and, if necessary, in time and iii) aggregated indicators.
All characteristics are represented in binary form. For building nominal scale for
aggregated indicators, ranges for values are defined using entropy based methods, in
particular, Gini [
N Y
Input data. E {Oi}i1 isa set of objects, F { fi}i1 is a set of object characteristics, where Y is a total number of object characteristics.
K Output data. S {si}i1 is a set of situations, where K is a number of revealed situations. Algorithm description
K Step 1 define preliminary list of situations S {si}i1 Step 2 calculate characteristics of situation for each situation si S for each object e j E involved in si calculate object characteristics Fij convert characteristics to binary form Fij FijB Step 3 build formal context K define formal objects G S define formal objects features M {E, F B} define relations I Step 4 build lattice Step 5 improve set of situations S ____________________________________________________________________
Fig.7 Algorithm for revealing situations using FCA 9
The proposed approach for situation assessment was used for solving task of
providing operational information about ocean temperature and salinity parameters
for hydroacoustics calculations that use sound speed of water area as one of
parameters. Regular grids of parameters values are usually used as a source for information
about water area state. Performing processing and analysis of available oceanographic
data in order to build regular data grids includes two main steps: data verification and
data regularization. The main purpose of data verification step is systematic storage,
analysis and processing of data in order to prepare it for solving problem of building
data grids [
The experiments on operational estimation of water area parameters were made
using measurements received from Argo float drifts [
An example of Argo float trajectory, temperature and salinity profiles are given in Fig.8.
Fig.8 An example of an Argo float trajectory and profiles with measurements For operational estimation of ocean parameters each Argo buoy was considered as a system that was characterized by trajectory and a set of profiles with measurements. Each point where data transmission was fulfilled was defined as objects. For neighboring objects according to the trajectory relations were set. List of possible relations contained two types of relations: ‘measured before’, ‘measured after’. Each object was characterized by a vector of characteristics listed in table 1 and by a vector of measured parameters. The parameters were described in the form presented in table 2.
Name PLATFORM_ NUMBER JULD LATITUDE LONGITUDE Name <PARAM>
LATITUDE:valid_max = 90.; double LONGITUDE(N_PROF); LONGITUDE:long_name = "Longitude of the station, best estimate"; LONGITUDE:units = "degree_east"; LONGITUDE:_FillValue = 99999.; LONGITUDE:valid_min = -180.; LONGITUDE:valid_max = 180.;
Longitude of the profile. Unit : degree east.
Example : 16.7222 : 16° 43’ 19.92’’ E Definition float <PARAM>(N_PROF, N_LEVELS); <PARAM>:long_name = "<X>"; <PARAM>:_FillValue = <X>; <PARAM>:units = "<X>"; <PARAM>:valid_min = <X>; <PARAM>:valid_max = <X>; <PARAM>:comment = "<X>"; <PARAM>:resolution = <X>;
To provide end-users with actual information based on results of new measurements, regular grids were rebuilt for the region where new data was received. Identification of ocean regions borders can be made manually by experts of subject domain or using algorithms of cluster analyzes. Algorithms for building gridded data were extended by a preliminary step that assumed assessment of observable situation. Buoys with similar or partly similar trajectories that have close measurements values were found using algorithms for building and comparing situation graphs. Depending on distances between the analyzed and similar situations weight coefficients were assigned to measurements. The highest values were assigned to newly received measurements. When rebuilding grid weight of measurements are considered. It allows calculating ocean parameters estimations based on new data and take into account tendencies that were observed in similar situations. As not all grid is rebuild, but only region of interest, processing is executed enough fast to meet users requirements.
Examples of results of ocean data processing using proposed approach are given in Figure 9.
ured by instruments and calculated values for the same parameters at the points with the same coordinates. The result of the comparison showed that the accuracy of calculated parameters values has increased up to 5% in some regions and in average in about 2-3%. 10
The application of the proposed method for situation assessment allows to take into account results of objects parameters measurements received from different sources. Recognition of situations and revealing similar situations provides possibility to obtain additional information about observed situation including tendencies and dynamics of its development. The approach to describe and compare situations using graphs provides high speed of calculations. Thus, we can say that the presented method can solve all problems considered in the paper.
Our future research is connected with developing algorithms that will allow using information about dependencies between parameters and their mutual influence.