A Revised Ant Clustering Algorithm with Obstacle Constraints

Clustering of spatial data in the presence of obstacles has a wide application. It is an important research topic in the spatial data mining. This paper discusses the problem of spatial clustering with obstacles constraints and presents a revised method named ant clustering algorithm with obstacle constraints(ACAOC) based on the basic ant model. This algorithm avoids some defects of other spatial clustering algorithms. These defects make algorithm not iterate when it has arrived at the stagnating state of the iteration or local optimum solution. ACAOC algorithm proposed in this paper cannot only give attention to local converging and the whole converging, but also consider the obstacles that exit in the real world and make the clustering result more practical. Because of the use of approximate nearest neighbor (ANN), the computing speed is increased greatly. The last experimental results conducted on synthetic data sets demonstrate that this method could extract the correct number of clusters with good clustering quality and high whole converging speed compared to the results obtained from clustering algorithm ignoring considering obstacles constraints.