顾及密度对比的多层次聚类点群选取方法
|
摘要
在语义信息缺乏的情况下进行点群选取是制图综合的难点之一。提出了一种新的通过多层次聚类进行点群选取的方法。首先,针对k-means聚类算法的不足,利用改进的密度峰值聚类算法实现点群自动聚类,主要表现为用基尼系数确定最优截断距离及用局部密度和相对距离的关系自动确定聚类中心。其次,提出一种顾及密度对比的选取策略,通过点群多层次聚类,将点群划分成不同等级的簇,确定不同等级的聚类中心,建立点群的层次树结构;依据方根定律计算的选取数量,按照各级别簇的点数比例,自上而下逐层分配待选取点数,确定选取对象,实现点群的自动选取和多尺度表达。对不同分布模式的点群进行实验,验证了该方法的普适性和有效性。
In the absence of semantic information, the selection of point group is one of the difficulties in cartographic generalization. This paper proposes a new multi-level clustering point group generalization method which takes into account density contrast. Firstly, in view of the shortcoming of k-means clustering algorithm, this paper uses an improved density peak clustering method to realize automatic clustering of point group, mainly reflects on determining the optimal cut-off distance by the Gini coefficient and uses the relation of local density and relative distance to detect the clustering centers. Secondly, we propose a point group selection strategy which takes into account density contrast, the point group is divided into clusters of different grade by multi-level clustering. The clustering centers of different grades are determined, and the hierarchical tree structure of point group data is established. The number of points to be selected is calculated according to the square root law, then allocated from top to bottom according to the number of clusters at each level, and the selected objects are determined, and automatic selection of points and multi-scale expression of point group are realized. Point groups experimental results with different distribution patterns show that the method described in this paper can get reasonable selection results, which verifies the universality and effectiveness of the method.
In the absence of semantic information, the selection of point group is one of the difficulties in cartographic generalization. This paper proposes a new multi-level clustering point group generalization method which takes into account density contrast. Firstly, in view of the shortcoming of k-means clustering algorithm, this paper uses an improved density peak clustering method to realize automatic clustering of point group, mainly reflects on determining the optimal cut-off distance by the Gini coefficient and uses the relation of local density and relative distance to detect the clustering centers. Secondly, we propose a point group selection strategy which takes into account density contrast, the point group is divided into clusters of different grade by multi-level clustering. The clustering centers of different grades are determined, and the hierarchical tree structure of point group data is established. The number of points to be selected is calculated according to the square root law, then allocated from top to bottom according to the number of clusters at each level, and the selected objects are determined, and automatic selection of points and multi-scale expression of point group are realized. Point groups experimental results with different distribution patterns show that the method described in this paper can get reasonable selection results, which verifies the universality and effectiveness of the method.
引文
[1]Yan Haowen,Wang Jiayao.A Generic Algorithm for Point Cluster Generalization Based on Voronoi Diagrams[J].Journal of Image and Graphics,2005,10(5):633-636(闫浩文,王家耀.基于Voronoi图的点群目标普适综合算法[J].中国图象图形学报,2005,10(5):633-636)
[2]Guo Qingsheng,Zheng Chunyan,Hu Huake.Hierarchical Clustering Method of Group of Points Based on the Neighborhood Graph[J].Acta Geodaetica et Cartographica Sinica,2008,37(2):256-261(郭庆胜,郑春燕,胡华科.基于邻近图的点群层次聚类方法的研究[J].测绘学报,2008,37(2):256-261)
[3]Yan Haowen,Wang Bangsong.A MWVD-Based Algorithm for Point Cluster Generalization[J].Geomatics and Information Science of Wuhan University,2013,38(9):1 088-1 091(闫浩文,王邦松.地图点群综合的加权Voronoi算法[J].武汉大学学报·信息科学版,2013,38(9):1 088-1 091)
[4]Li Jiatian,Kang Shun,Luo Fuli.Point Group Generalization Method Based on Hierarchical Voronoi Diagram[J].Acta Geodaetica et Cartographic Sinica,2014,43(12):1 300-1 306(李佳田,康顺,罗富丽.利用层次Voronoi图进行点群综合[J].测绘学报,2014,43(12):1 300-1 306)
[5]Li Wenjing,Li Shaoning,Long Yi,et al.Point Cluster Selection in GIS Using Gravity Model[J].Geomatics and Information Science of Wuhan University,2013,38(8):945-949(李雯静,李少宁,龙毅,等.利用重力模型进行GIS点群选取[J].武汉大学学报·信息科学版,2013,38(8):945-949)
[6]Yan H,Weibel R,Yang B.A Multi-parameter Approach to Automated Building Grouping and Generalization[J].GeoInformatica,2008,12(1):73-89
[7]Steinhauer J H,Wiese T,Freksa C,et al.Recognition of Abstract Regions in Cartographic Maps[J].Lecture Notes in Computer Science,2001,2 205:306-321
[8]Jain A K.Data Clustering:50 Years Beyond k-means[C].European Conference on Machine Learning and Knowledge Discovery in Databases,Antwerp,Belgium,2008
[9]Sander J.Density-Based Clustering[M].US:Springer,2011
[10]Achtert E,Goldhofer S,Kriegel H P,et al.Evaluation of Clusterings-Metrics and Visual Support[C].IEEE 28th International Conference on Data Engineering(ICDE),Washington D C,USA,2012
[11]Xu R,Wunsch D.Survey of Clustering Algorithms[J].IEEE Transactions on Neural Networks,2005,16(3):645-678
[12]Guha S,Rastogi R,Shim K.CURE:An Efficient Clustering Algorithm for Large Databases[J].ACMSIGMOD Record,1998,27(1):73-84
[13]Kalita H K,Bhattacharya D K,Kar A.A New Algorithm for Ordering of Points to Identify Clustering Structure Based on Perimeter of Triangle:Optics(bopt)[C].The 15th International Conference on Advanced Computing and Communications,Guwahati,India,2007
[14]Sheikholeslami G,Chatterjee S,Zhang A.WaveCluster:A Multi-resolution Clustering Approach for Very Large Spatial Databases[C].The 24th International Conference on Very Large Data Bases,New York,USA,1998
[15]Rhouma M B H,Frigui H.Self-Organization of PulseCoupled Oscillators with Application to Clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(2):180-195
[16]Rodriguez A,Laio A.Clustering by Fast Search and Find of Density Peaks[J].Science,2014,344(6 191):1 492-1 496
[17]Xie J,Gao H,Xie W,et al.Robust Clustering by Detecting Density Peaks and Assigning Points Based on Fuzzy Weighted k-nearest Neighbors[J].Information Sciences,2016,354:19-40
[18]Li D,Wang S,Gan W,et al.Data Field for Hierarchical Clustering[J].International Journal of Data Warehousing and Mining,2011,7(4):43-63
[19]Yan H,Weibel R.An Algorithm for Point Cluster Generalization Based on the Voronoi Diagram[J].Computers and Geosciences,2008,34(8):939-954
[2]Guo Qingsheng,Zheng Chunyan,Hu Huake.Hierarchical Clustering Method of Group of Points Based on the Neighborhood Graph[J].Acta Geodaetica et Cartographica Sinica,2008,37(2):256-261(郭庆胜,郑春燕,胡华科.基于邻近图的点群层次聚类方法的研究[J].测绘学报,2008,37(2):256-261)
[3]Yan Haowen,Wang Bangsong.A MWVD-Based Algorithm for Point Cluster Generalization[J].Geomatics and Information Science of Wuhan University,2013,38(9):1 088-1 091(闫浩文,王邦松.地图点群综合的加权Voronoi算法[J].武汉大学学报·信息科学版,2013,38(9):1 088-1 091)
[4]Li Jiatian,Kang Shun,Luo Fuli.Point Group Generalization Method Based on Hierarchical Voronoi Diagram[J].Acta Geodaetica et Cartographic Sinica,2014,43(12):1 300-1 306(李佳田,康顺,罗富丽.利用层次Voronoi图进行点群综合[J].测绘学报,2014,43(12):1 300-1 306)
[5]Li Wenjing,Li Shaoning,Long Yi,et al.Point Cluster Selection in GIS Using Gravity Model[J].Geomatics and Information Science of Wuhan University,2013,38(8):945-949(李雯静,李少宁,龙毅,等.利用重力模型进行GIS点群选取[J].武汉大学学报·信息科学版,2013,38(8):945-949)
[6]Yan H,Weibel R,Yang B.A Multi-parameter Approach to Automated Building Grouping and Generalization[J].GeoInformatica,2008,12(1):73-89
[7]Steinhauer J H,Wiese T,Freksa C,et al.Recognition of Abstract Regions in Cartographic Maps[J].Lecture Notes in Computer Science,2001,2 205:306-321
[8]Jain A K.Data Clustering:50 Years Beyond k-means[C].European Conference on Machine Learning and Knowledge Discovery in Databases,Antwerp,Belgium,2008
[9]Sander J.Density-Based Clustering[M].US:Springer,2011
[10]Achtert E,Goldhofer S,Kriegel H P,et al.Evaluation of Clusterings-Metrics and Visual Support[C].IEEE 28th International Conference on Data Engineering(ICDE),Washington D C,USA,2012
[11]Xu R,Wunsch D.Survey of Clustering Algorithms[J].IEEE Transactions on Neural Networks,2005,16(3):645-678
[12]Guha S,Rastogi R,Shim K.CURE:An Efficient Clustering Algorithm for Large Databases[J].ACMSIGMOD Record,1998,27(1):73-84
[13]Kalita H K,Bhattacharya D K,Kar A.A New Algorithm for Ordering of Points to Identify Clustering Structure Based on Perimeter of Triangle:Optics(bopt)[C].The 15th International Conference on Advanced Computing and Communications,Guwahati,India,2007
[14]Sheikholeslami G,Chatterjee S,Zhang A.WaveCluster:A Multi-resolution Clustering Approach for Very Large Spatial Databases[C].The 24th International Conference on Very Large Data Bases,New York,USA,1998
[15]Rhouma M B H,Frigui H.Self-Organization of PulseCoupled Oscillators with Application to Clustering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(2):180-195
[16]Rodriguez A,Laio A.Clustering by Fast Search and Find of Density Peaks[J].Science,2014,344(6 191):1 492-1 496
[17]Xie J,Gao H,Xie W,et al.Robust Clustering by Detecting Density Peaks and Assigning Points Based on Fuzzy Weighted k-nearest Neighbors[J].Information Sciences,2016,354:19-40
[18]Li D,Wang S,Gan W,et al.Data Field for Hierarchical Clustering[J].International Journal of Data Warehousing and Mining,2011,7(4):43-63
[19]Yan H,Weibel R.An Algorithm for Point Cluster Generalization Based on the Voronoi Diagram[J].Computers and Geosciences,2008,34(8):939-954
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |