基于邻近图的点群层次聚类方法的研究  

Hierarchical Clustering Method of Group of Points Based on the Neighborhood Graph

作　　者：郭庆胜[1] 郑春燕[1] 胡华科[2] 

机构地区：[1]武汉大学资源与环境科学学院 [2]嘉应学院地理系,广东梅州514015

出　　处：《测绘学报》2008年第2期256-261,共6页Acta Geodaetica et Cartographica Sinica

基　　金：国家自然科学基金项目(40571133);地理空间信息工程国家测绘局重点实验室基金项目(200625);测绘遥感信息工程国家重点实验室项目((04)0301);嘉应学院资助项目(06KJZ01)

摘　　要：空间聚类是点状空间目标群在地图综合中必须解决的问题。分析点群的几种常用邻近图的特征及其层次关系,并基于原始的点集合生成的DT构建相应的GG,UG,MST和NNG,然后在所选择的密度适应性约束、距离适应性约束和偏差适应性约束这三种条件下,利用所生成的邻近图进行了点群的层次聚类。研究并改进现有的点状空间目标群的无监督层次聚类方法,并通过实例验证该算法的可行性。Spatial clustering is an important task in cartographic generalization. It is necessary to cluster a group of points. For example, in the typification operator and selection operator of a group of points, the spatial characteristics of clusters of points have to be considered. Clustering algorithms have become increasingly more important in handling and analyzing spatial data. These clustering methods can be classified into two kinds： supervised and unsupervised approaches, or hierarchical and non-hierarchical approaches. Based on neighborhood graphs of a set of point features, the existing unsupervised hierarchical methods of clustering points have been discussed and improved in this paper. Firstly, several common neighborhood graphs＇ features and their hierarchical relationships are analyzed, and GG（ Gabriel Graph）, UG（Urquhart Graph）, MST（ Minimum Spanning Tree） and NNG（ Nearest Neighborhood Graph） are created from the same initial set of points based on DT（ Delaunay Triangulation）. In this paper, UG is selected to be used for spatial clustering instead of RNG（ Relative Neighborhood Graph）, because UG approximates to RNG well, and there are typically only about 2% more edges in UG than in RNG ,this can be found through statistical tests of random samples, furthermore, UG is much easier to compute from the DT. Secondly, the constraints which include density compatibility, distance compatibility and variance compatibility are given with the help of statistics and Anders＇ research results. According to these constraints, the hierarchical clustering approaches are realized by means of these neighborhood graphs of points. At last, the algorithm of clustering points is improved and researched, the procedure about the clustering algorithm is elaborated, and the feasibility of the unsupervised hierarchical approach is validated through a detailed example.

关 键 词：空间聚类 邻近图 点群 适应性约束 

分 类 号：P28[天文地球—地图制图学与地理信息工程]