基于空间邻近的点目标聚类方法

Clustering for point objects based on spatial proximity

空间聚类是空间数据挖掘和知识发现领域的主要研究方向之一,但点目标空间分布密度的不均匀、分布形状的多样化,以及"多桥"链接问题的存在,使得基于距离和密度的聚类算法不能高效且有效地识别聚集性高的点目标。提出了基于空间邻近的点目标聚类方法,通过Voronoi建模识别点目标间的空间邻近关系,并以Voronoi势力范围来定义相似度准则,最终构建树结构以实现点目标的聚集模式识别。实验将所提算法与K-means、具有噪声的基于密度的聚类(DBSCAN)算法进行比较分析,结果表明算法能够发现密度不均且任意形状分布的点目标集群,同时准确划分"桥"链接的簇,适用于空间点目标异质分布下的聚集模式识别。

Spatial clustering is one of the vital research directions in spatial data mining and knowledge discovery.However,constrained by the complex distribution of uneven density,various shapes and multi-bridge connection of points,most clustering algorithms based on distance or density cannot identify high aggregative point sets efficiently and effectively. A point clustering method based on spatial proximity was proposed. According to the structure of point Voronoi diagram,adjacent relationships among points were recognized. The similarity criteria was defined by region of Voronoi,a tree structure was built to recognize point-target clusters. The comparison experiments were conducted on the proposed algorithm,K-means algorithm and Density-Based Spatial Clustering of Applications with Noise（ DBSCAN） algorithm. Results show that the proposed algorithm is capable for identifying clusters in arbitrary shapes,with different densities and connected only at bridges or chains,meanwhile also suitable for aggregative pattern recognition in heterogeneous space.