Study And Application On Visual Multi-scale Spatial Clustering Based On Graph Theory

With the development of worldwide automatic data collecting network, the ability to collecte data is getting greater, and large amount of data are stored in spatial databases, relational databases and data warehouses. In some sense, we are submerged in data rather than lack of data. This situation creates the necessity of an automated knowledge/information discovery from data, which leads to a promising emerging field, spatial data mining or spatial knowledge discovery in databases (SKDD). Spatial knowledge discovery in databases can be defined as the nontrivial extraction of implicit, previously unknown, and potentially useful information from spatial data. Spatial clustering is one of data mining methods. Extracting interesting and useful patterns from spatial datasets is more difficult than extracting patterns from traditional numeric and categorical data due to the characteristic of spatial data (e.g. high-dimension, multi-scale, large amount etc.) and the complexity of spatial relationships(e.g. spatial topological relation, spatial orientation relation, spatial measurement relation etc.). In general the algorithms of clustering in RDBMS are inapplicable in GIS. In this paper, spatial clustering is studied from the perspective of GIS. We combines two major characteristic of spatial data(spatial topological relation and multi-scale property) and visualization techniques with clustering processing.We first study an efficient method for spatial clustering that takes into account the effect of spatial relationship, then extend it to mutli-scale spatial datasets. The major research results and conclusions of this paper are as follows: (1) We describe spatial data structure, related concepts and theory of spatial data mining and spatial clustering. Especially we divide spatial clustering algorithm into five classes, and make further research on them respectively. (2) We discusse spatial preprocessing techniques and related visualization techniques. We show a method to contruct spatial data cube and perform on-line analysis process (OLAP) with sample data. (3) We develop a novel visual spatial clustering method named VSG-CLUST, which is able to recognize spatial patterns that involve neighbors. Its principle is to maintain the spatial structure with the help of graph theory tool includes Delaunay Triangulation (DT) and Minimum Spanning Tree (MST). VSG_CLUST groups and visualizes cluster hierarchies consisting of both non-spatial and spatial attributes. The usability and effectiveness of VSG-CLUST is presented. (4) We propose a new multi-scale spatial clustering method based on spatial concept tree. We believe that spatial hierarchical characteristic represents spatial multi-scale characteristic. Hence, we regard multi-scale factor as a kind of constraint, and apply it to control the strategy of partitioning a MST, namely a spatial hierarchical clustering based on multi-scale constrain. (5) Employing the theoretical research mentioned above, a data mining system called Hsminer was implemented using the web services technology as the platform. An application instance of Hsminer is attached to the end of this paper. In this instance, we use VSG-CLUST algorithm to mine the rules in Fujian province environmental monitoring data.