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

空间聚类是点状空间目标群在地图综合中必须解决的问题。分析点群的几种常用邻近图的特征及其层次关系，并基于原始的点集合生成的DT构建相应的GG，UG，MST和NNG，然后在所选择的密度适应性约束、距离适应性约束和偏差适应性约束这三种条件下，利用所生成的邻近图进行了点群的层次聚类。研究并改进现有的点状空间目标群的无监督层次聚类方法，并通过实例验证该算法的可行性。

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

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.