Spatial Clustering Based On Delaunay Triangulation With The Obstacles

With the development of satellite communication and remote sensing technology, a large number of the spatial data can be obtained easily. In present, spatial data mining have to meet the challenge in data mining methods how to extract useful information from these spatial data high-efficiently. Spatial clustering is an important method of the spatial data mining which has been widely used in spatial discovery. The traditional spatial clustering algorithms usually neglect the influence of constraint, such as obstacles etc. However, in the real world, because of the complexity of the terrain and the difference of the natural conditions, it has made the spatial clustering more difficultly. Nowdays, the spatial clustering based on obstacles has been one of the hotspot of the spatial data mining.In this paper, spatial clustering and spatial clustering with obstacles that had been raised at home and abroad, has been researched and analyzed. At present, many algorithms of spatial clustering with obstacles had been obtained by improving their original algorithms respectively that had been not considered constraint. To deal with these obstacles, some algorithms had been lower precision of clustering because of considering the factors of obstacles, such as their larger by the size, shape and quantity. And some algorithms made the calculation increasing sharply. The algorithms of clustering based on Delaunay triangulation have some advantages, such as high precision of clustering, less supplying parameters, recognizing the clusters that have various kinds of shape, and so on. AUTOCLUST+ is a fairly representative algorithm of clustering with obstacles. However, the algorithm has some faults, such as flexibility in dealing with obstacles, much more quantity of calculation, etc. In this paper, a new algorithm that is CBDTO (clustering based on Delaunay triangulation with obstacles), has been proposed that have adopted the advanced ideas of Delaunay triangulation and AUTOCLUST+. In this algorithm, the obstacles had been expressed by triangles that have obstacle flags. So, this method not only can maintain the structure of original Delaunay triangulation, but also makes more flexibility in dealing with obstacles, while obstacles had been appended, deleted and modified. Meanwhile, the algorithm has adopted the model of clustering by dividing triangles into smaller-triangles, long and narrow-triangles and bigger-triangles in the Delaunay triangulation, and expanded these triangles to carry out clustering that made less calculation. This algorithm is feasible by experiments. In conclusion, the algorithm of CBDTO not only can recognize these clusters that AUTOCLUST+ can do, but also can recognize the kind of clusters that their density is gradually changing that AUTOCLUST+ can not do. And the algorithm has overcome some faults, such as non-flexibility in dealing with obstacles and more calculation. Finally, the study to the algorithm of CBDTO will contribute to the system of route selection about highway that based on spatial terrain analysis.