Скачати 31.1 Kb.
ЗмістIt is supposed to carry out realization and preliminary debugging of the intelligent block of system on the basis of methods of
8. Acceptance of the final decision on results of voting on a set of ways of recognition (tests) and approaches.
INTELLIGENT EXPANSION OF THE GEOINFORMATION SYSTEM
A. Ryumkin1, A. Yankovskaya2
1 Tomsk State University of Architecture and Building,
2, Solyanaya Square, 634003, Tomsk, Russia, firstname.lastname@example.org, email@example.com
2 Tomsk State University, 36, Lenin pr., 634050, Tomsk, Russia, firstname.lastname@example.org
The intelligent expansion tradition vector GIS with the use of intelligent recognizing system is proposed. Integration of two systems is put in a basis of intelligent expansion GIS – typical vector GIS and the intelligent recognizing system based on software tool IMSLOG with the purpose of union of functionalities of both. Original test methods of pattern recognition are used.
There is a fairly wide list of commercial software products in the field of geoinformation system (GIS) in the world scale as well as markets. The basic world leaders in the given sphere of the software are products of the American firms: ESRI, MapInfo, ERDAS, Autodesk, Intergraph . Prominent features of this software are: 1) presence of the advanced means of representation of the graphic information both vector formats and raster; 2) opportunity of use of databases such widespread DBMS as Oracle, MS SQL Server, dBase, FoxPro and a number of others. The majority of systems of the given class give users support of a big number of the various geographical projections, advanced means of the analysis of the graphic information represented in various formats, advanced means of graphic search.
However the enumerated software products do not contain components using knowledge bases for the solution of wide a number of problems, and are not equipped with intelligent means, which does not allow to solve practically important problems for which heterogeneity of the processable information, an fuzzybility and great volume of the data and knowledge are essential. The problems of decision-making at planning, development of territories of cities or regions, estimations of the real estate, an ecological condition, expediency of investments  are typical applications. Research on application of methods of an artificial intellect in GIS are at the initial stage. In widespread raster GIS ERDAS IMAGINE, intended for processing images (including for GIS), subsystem IMAGINE Expert Classifier using production rules of knowledge representation at the solution of problems of classification has appeared recently. In some vector GIS there are also elements of AI, but all this has trial character.
Problem of investigation developed by us is construction of the geoinformation system possessing possibilities of representation, processing and application of knowledge on the basis of original methods of an artificial intellect.
Bases of intelligent expansion of geoinformation system
Integration of two systems is put in a basis of intelligent expansion GIS – typical vector GIS such as ArcVier  or the GrafIn  and the intelligent recognizing system based on software tool IMSLOG  with the purpose of union of functionalities of both: effective means of extraction, systematization, representation and data processing about the territories realized in GIS, and intelligent means of the data and knowledge analysis ; revealings of a various regularities in the data and knowledge; decision-making on the basis of a combination of various schemes (mechanisms) of a inference logic-combinatory (l-c) , logic-probabilistic (l-p) [5,6], logic-combinatorial-probabilistic (l-c-p)  and voting procedures on a set of solving rules constructed on a set of logic tests (unconditional and mixed, ones which are a compromise between unconditional and conditional components) at each scheme of a inference as well as various, oriented on users of different qualification, graphic (including cognitive) means of visualization of information structures, regularities, decision-making and substantiation of the decision-making results  realized in intelligent system.
The structure traditional GIS usually includes the advanced graphic editor and the block of management of the attribute data, allowing for the description of a subject area to use a composition of graphic and attribute components. In vector GIS for this purpose a set of graphic primitives (a point, a line, polygon) is used. Each them is characterized by a set of the attribute data. In aggregate they form the digital terrain models (DTM) equivalent to usual not spatial databases. In GIS the modules of the spatial analysis using geometrical operations above graphic objects, as well as usual for DBMS operations above tables of the data are realized. Compositions of these operations, mutual transitions between them give the user convenient means of work with (DTM) in the dialogue. It is easy to see that similar models of the data are also convenient for the application to this problem area of methods of AI. One of the major in construction GIS is the stage of formation DTM on materials of aerial photograph, space shooting, or on available cartographical materials. Here, and also in many other problems GIS methods of pattern recognition and images analysis  are used. Formalizing typical for GIS spatial relations and conditions it is possible to receive typical statement of a problem.
The test approach to pattern recognition assumes performance of the following stages.
1. Adaptive code conversion of characteristic features of a different type (quantitative, nominal, serial) with the purpose of the maximal partition of classes (patterns) and reduction a kind used in a matrix methods of data and knowledge representation [5,6].
2. The analysis of a database and knowledge on consistency (check of paired crossing of descriptions of objects from different patterns (classes on each mechanism of classification)).
3. Revealing of knowledge representativenes in two ways: logic-combinatory with deep optimizing transformations and statistical methods on the basis of so-called divergence of Koulbac information; an estimation (on a basis of Koulbac divergence) of additional volume of training knowledge with a purpose of obtaining reliable conclusions.
4. Construction of irredundant implication matrix U' (with simultaneous revealing constant, steady, noninformative, obligatory, alternative and dependent features and calculation of weight coefficients of all features), assigning either necessary and sufficient conditions or sufficient conditions of distingrushability of any pair the objects belonging to different patterns (to classes at each mechanism of classification) .
5. The finding of all shortest (all or a part irredundant) columns coverings of matrix U', to each of which corresponds minimal (irredundant) distinguishing subset of features (minimal (irredundant) test), assigning necessary and sufficient (sufficient) conditions of distingrushability of any pair of objects from different patterns. Revealing of nonexistent and pseudo-obligatory (at construction only of a part irredundant column coverings of matrix U') features. Construction of all minimal (all or a part irredundant) the unconditional and mixed tests .
6. Construction of a set of the solving rules taking into account all found regularities and realizing a set of independent ways of recognition (schemes of a logic inference) of the same object under investigation (OUI). The number of recognition ways is equal to the number of tests used for recognition .
7. Recognition of the OUI by one of approaches (at the l-c approach – on the basis of similarity coefficients and taking into account of an admissible error of decision-making assigned by the user ; at l-p approach - on the basis of a partial implication at a partial ortogonalization of some DNF of Boolean functions describing a pattern in space of features included in the minimal (irredundant) test ; at l-c-p approach – on the basis of similarity coefficients taking into account of values probability of some features of the OUI) .
9. Application of various cognitive means of acceptance and a substantiation of decisions and graphic means of visualization of information structures and the revealed regularities .
We list the basic approaches to construction of tests for 2-, 3-and k-values features: 1) with construction irredundant implication matrix U'; 2) with partial construction of the matrix U'; 3) without construction of the matrix U'.
A particular approach is applied. This depends on the dimension of knowledge (the number of characteristic, classification features, the number of rows of matrix Q), of knowledge, and its representativeness. In the first approach, one of the following algorithms can be executed: a) the search for all shortest column coverings with simultaneous detection of the regularities; b) the search of irredundant tests with simultaneous detection of obligatory features, with calculation of the weight coefficients feature and with the use of a step-cyclic algorithm; c) the search of the minimum and irredundant unconditional tests with the use of genetic algorithms.
At the second and third approaches the algorithms similar to algorithms b,c from the first approach are used. Addition of columns at construction of minimal and irredundant descriptions matrices is carried out to nonexcluded subset of columns, corresponded to the core of diagnostic tests, and at removal columns the ones corresponded to the core are not removed.
Algorithms of construction unconditional and mixed minimal and irredundant tests at the first approach in case of realization of algorithm a) include the following steps: 1) calculation of a distinguishing vector-function for the next pair a class-class (an object-class, object-object) from different classes at the fixed classification mechanism (a pattern-pattern, an object-pattern, object-object from different patterns for nonpartitioned matrix U'); 2) calculation of weight features coefficients; 3) revealing of obligatory features and, at presence of which, their inclusion in a core; 4) addition of the next value of a distinguishing vector function to the current matrix U; consecutive formation of the vector used for revealing of constant features and vectors for each patterns (a class on each classification mechanism) for revealing steady features and removing in the current matrix U of covering rows; 5) construction of matrix U' with simultaneous revealing a part of regularities; 6) Construction of a set of all possible shortest (optimum) column coverings of a matrix U' with the use of features weight coefficients; 7) construction of the minimal (optimum) unconditional diagnostic test on each from the shortest (optimum) column coverings; 8) construction of the mixed test on the base of unconditional test with inclusion of obligatory features in a unconditional component of the test; 9) calculation of weights of diagnostic tests.
Let's note that features are considered obligatory if in matrix U there are rows containing only one unit in columns corresponding to these features. Features are considered to be alternative if corresponding to them columns matrix U are equal. Features to which zero columns of matrix U correspond are not informative as far as they do not distinguish any pair of objects from different patterns. If the i-th the column of matrix U is covered by j-th (not equal to the i-th) column corresponding i-th column the feature distinguishes only some pairs objects from a set of pairs, distinguished by j-th feature, and it is considered a dependent one.
The features, which have not been included in all shortest (irredundant) coverings of the matrix U', are considered nonessential at decision-making on the basis of minimal (irredundant) tests and are not used for the description of OUI and decision-making.
Search of all shortest column coverings of matrix U' is based on construction on matrix U' the hierarchical system of submatrices being a tree of search, and are reduced to selection of all nonrecurrent shortest ways in a tree of search.
In a basis of algorithms of construction of a tree of the mixed test  at the first approach (of a partial tree of the mixed test on presentation of the object description at the second approach) on the unconditional test procedure of partition of rows of a descriptions matrix on a set of reactions on values of obligatory and pseudo-obligatory features lies.
Partition coefficient C is used for forming of a conditional component of the mixed test. The partition coefficient reflect a degree of nonintersection of patterns subsets corresponding to different feature values. The feature with maximum coefficient C is chosen on every step of construction of a tree of the mixed test. The calculation procedure of a number of voices given for the test is used for a final solution.
Intelligent expansion of a geoinformation system will allow to develop the existing traditional possibilities of geoinformation system directed at visualization of territory data, the spatial analysis with the use of solving rules allowing to carry out classification of spatial situations and to take administrative solution for the specialized applications.
This work was supported by the Russian Foundation for Basic Research, project nos. 01-01-00772 and 01-01-01050).