A Study Of Spatial Clustering With Constraints Based Swarm Intelligence

Spatial clustering is not only an important effective method but also a prelude of other task for Spatial Data Mining (SDM). Spatial clustering has been an active research area in the SDM community. Many methods have been proposed in the literature, but few of them have taken into account constraints that may be present in the data or constraints on the clustering. These constraints have significant influence on the clustering results. Therefore, to improve clustering practicalities, researching on spatial clustering with constraints is important, and it is a challenge that finds the better clustering results which not only make special constraints satisfied but also have fine clustering characteristic.Recently, swarm intelligence has been popular in the field of artificial intelligence (AI) and successfully applied to solve a wide range of optimization problems. To solve the issue above, the researches on spatial clustering with constraints based swarm intelligence are done in this thesis, which include the theory and improving of Genetic Algorithm (GA), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO), and their applications in solving spatial clustering with constraints. The main contributions of this thesis are as the following:A novel spatial clustering with constraints based swarm intelligence is presented in this thesis. Researching on spatial clustering with constraints based swarm intelligence opens up the new approach for spatial clustering with constraints and extends the new applies field of swarm intelligence.The thought of integration in various algorithms is adopted for spatial clustering with constraints. The improved swarm intelligence optimization algorithms are done, which have better convergence speed and search accuracy.Obstacle distance is the key to Spatial Clustering with Obstacles Constraints (SCOC). Based on the analyzing of the drawback of calculating obstacle distance through Visibility GRAPH (VGRAPH), a new method for computing obstacle distance based grid using improved GA is presented, which is on the basis of robot route planning. The experimental results show that the proposed method not only has higher search speed but also is effective for arbitrary shape obstacles.In addition, to overcome the disadvantage of GA method, a novel obstacle distance based grid using improved ACO is presented. The experiments show that the approach of obstacle distance based grid using improved ACO is not only an effective method for arbitrary shape obstacles but also much better than GA and is fit for the situation that needs to be parted by much more grid. Besides that, the presented method of obstacle distance based grid provides a new approach for spatial analysis in GIS (Geographical Information System).The approach of spatial clustering with obstacle constraints based partitioning algorithm is is discussed in sufficient detail and a novel Genetic K-Medoids Spatial Clustering with Obstacles Constraints (GKSCOC) based on GA and K-Medoids is proposed. The GKSCOC algorithm can not only give attention to higher local convergence speed and stronger global optimum search, but also get down to the obstacles constraints and practicalities of spatial clustering. But the drawback of GKSCOC is a comparatively slower speed in clustering.To overcome the disadvantage of GKSCOC approach which has slower convergence speed, a novel SCOC based on PSO and K-Medoids (PKSCOC) is presented. The experimental results demonstrate the effectiveness and efficiency of the proposed method, which performs better than Improved K-Medoids SCOC in terms of quantization error and has higher convergence speed than GKSCOC obviously. So, PKSCOC has better scalability than GKSCOC, and it is fit for dealing with dynamic constraints.Finally, the experiments on city parks in Zhengzhou for the example of facility location are done and the results show that spatial clustering with constraints based swarm intelligence is an effective method and have more practical value. It indicates that the presented method is much better than usual spatial clustering in revealing space correlativity, and then the results of facility location analysis have a more rational explanation.Spatial clustering with obstacles constraints based swarm intelligence not only can provide more rational decision for establishment layout but also can increase intellectualized analysis in GIS, and it is a forceful guarantee for SDM.