Spatial Clustering with Obstacles Constraints Using Ant Colony and Particle Swarm Optimization

摘要

Spatial clustering is an important research topic in Spatial Data Mining (SDM). This paper proposes an Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO) method for solving Spatial Clustering with Obstacles Constraints (SCOC). In the process of doing so, we first use improved ACO to obtain the shortest obstructed distance, which is an effective method for arbitrary shape obstacles, and then we develop a novel PKSCOC based on PSO and K-Medoids to cluster spatial data with obstacles. The PKSCOC algorithm can not only give attention to higher local constringency speed and stronger global optimum search, but also get down to the obstacles constraints and practicalities of spatial clustering. The experimental results demonstrate the effectiveness and efficiency of the proposed method, which performs better than Improved K-Medoids SCOC (IKSCOC) in terms of quantization error and has higher constringency speed than Genetic K-Medoids SCOC (GKSCOC).