A Methodology Of Adaptive Spatial Clustering Analysis

Spatial clustering has played an important role in spatial data mining and knowledge discovery. It aims to classify a spatial database into several clusters without any prior knowledge (e.g., probability distribution and the number of clusters). Spatial clustering has a wide range of applications, such as astronomy, geography, geology, meteorology, cartography and public health. Currently, the applications on complicated spatial database bring new demand for spatial clustering algorithms-adaptiveness. First, spatial clustering algorithms should be adaptive to complicated spatial database, such as clusters adjacent to each other, with arbitrary geometrical shapes and/or different densities and a large amount of noise possibly exists. Second, spatial clustering algorithms should be adaptive to the requirements of users, such as different kinds of applications, minimal requirements of prior knowledge to determine the input parameters. On that account, a methodology of adaptive spatial clustering analysis is developed in this thesis. The primary contents of the thesis can be summarized as follows:(1) The special characteristics of spatial clustering are firstly analyzed based on the feathers and characteristics of spatial data. Then, a detailed definition of spatial clustering is given, and a framework for spatial clustering including spatial data cleaning, spatial clustering trend analysis, spatial clustering feature extraction, spatial clustering algorithm and spatial clustering validity assessment is also proposed. Finally, an overview and comparison of current spatial clustering algorithms are made.(2) A field theory based adaptive spatial clustering algorithm-FTASC is proposed. A novel data field for spatial clustering, called aggregation field, is first of all developed. Then a novel concept of aggregation force is utilized to measure the degree of aggregation among the entities. The FTASC algorithm does not involve the setting of input parameters, and a series of iterative strategies are implemented to obtain different clusters according to various spatial distributions. Two experiments are designed to illustrate the advantages of the FTASC algorithm. The practical experiment indicates that FTASC algorithm can effectively discover local aggregation patterns. The comparative experiment is made to further demonstrate the FTASC algorithm superior than classic DBSCAN algorithm.(3) An adaptive spatial clustering algorithm based on Delaunay triangulation-ASCDT is proposed. The ASCDT algorithm employs both statistical features of the edges of Delaunay triangulation and a novel spatial proximity definition based upon Delaunay triangulation to detect spatial clusters. Normally, this algorithm can automatically discover clusters of complicated shapes, and non-homogeneous densities in a spatial database, without the need to set parameters or prior knowledge. The user can also modify the parameter to fit with special applications. In addition, the algorithm is robust to noise. Experiments on both simulated and real-world spatial databases are utilized to demonstrate the effectiveness and advantages of the ASCDT algorithm. Based on the ASCDT algorithm, a novel adaptive spatial clustering algorithm considering spatial obstacles-ASCDT+is further developed.(4) A graph and density based hybrid spatial clustering algorithm-HGDSC is proposed. First, Delaunay triangulation with edge length constraints is used for the modeling of the spatial proximity relationships among spatial entities. Then, a modified density-based clustering strategy is used to identify the spatial clusters. The algorithm mainly has two desirable properties. First, both spatial and non-spatial attributes are taken into account. Entities in same cluster are similar in both spatial and non-spatial domain. Second, the algorithm can adapt to a complex spatial database which may contain the clusters of arbitrary shapes and/or non-homogeneous densities and/or large amount of noise. Experiments on both synthetic and real-world spatial datasets are utilized to demonstrate the effectiveness and practicability of the HGDSC algorithm.(5) A spatial clustering validity index based on gravitational theory-SCV is proposed. The construction principle of the spatial clustering validity function is first investigated. Then, the aggregation force is utilized to describe the issue of spatial clustering similar to the FTASC algorithm and a novel spatial clustering validity index for two dimension spatial hard clustering is developed. Through the experiments on both simulated data set and real-world data set, it can be found that the index developed in this thesis can well evaluate the spatial hard clustering scheme including both arbitrary shape clusters and outliers.(6) A spatial clustering software named as EasyCluster is developed. There are mainly four aspects of functions, including spatial data cleaning, spatial clustering information extraction,21 spatial clustering algorithms and 3 spatial clustering validity index (35 spatial clustering validity functions).