Comparative density peaks clustering algorithm with automatic determination of clustering center

doi:10.11772/j.issn.1001-9081.2020071071

Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (3): 738-744.DOI: 10.11772/j.issn.1001-9081.2020071071

Special Issue: 数据科学与技术

• Data science and technology • Previous Articles Next Articles

Comparative density peaks clustering algorithm with automatic determination of clustering center

GUO Jia¹, HAN Litao^1,2, SUN Xianlong¹, ZHOU Lijuan¹

1. College of Geodesy and Geomatics, Shandong University of Science and Technology, Qingdao Shandong 266590, China;
2. Key Laboratory of Geomatics and Digital Technology of Shandong Province(Shandong University of Science and Technology), Qingdao Shandong 266590, China

Received:2020-07-23 Revised:2020-10-10 Online:2021-03-10 Published:2020-11-12
Supported by:
This work is partially supported by the Natural Science Foundation of Shandong Province (ZR2017MD003).

自动确定聚类中心的比较密度峰值聚类算法

郭佳¹, 韩李涛^1,2, 孙宪龙¹, 周丽娟¹

1. 山东科技大学测绘科学与工程学院, 山东青岛 266590;
2. 山东省基础地理信息与数字化技术重点实验室(山东科技大学), 山东青岛 266590

通讯作者: 韩李涛
作者简介:郭佳(1995-),女,山西阳泉人,硕士研究生,主要研究方向:GIS;韩李涛(1978-),男,山东菏泽人,副教授,博士,主要研究方向:空间信息可视化、三维GIS、室内GIS;孙宪龙(1995-),男,山东菏泽人,硕士研究生,主要研究方向:GIS;周丽娟(1994-),女,山西太原人,硕士研究生,主要研究方向:GIS。
基金资助:
山东省自然科学基金资助项目（ZR2017MD003）。

Abstract

Abstract: In order to solve the problem that the clustering centers cannot be determined automatically by Density Peaks Clustering (DPC) algorithm, and the clustering center points and the non-clustering center points are not obvious enough in the decision graph, Comparative density Peaks Clustering algorithm with Automatic determination of clustering center (ACPC) was designed. Firstly, the distance parameter was replaced by the distance comparison quantity, so that the potential clustering centers were more obvious in the decision graph. Then, the 2D interval estimation method was used to perform the automatic selection of clustering centers, so as to realize the automation of clustering process. Experimental results show that the ACPC algorithm has better clustering effect on four synthetic datasets; and the comparison of the Accuracy indicator on real datasets shows that on the dataset Iris, the clustering accuracy of ACPC can reach 94%, which is 27.3% higher than that of the traditional DPC algorithm, and the problem of selecting clustering centers interactively is solved by ACPC.

Key words: clustering analysis, density clustering, density peak, clustering center, statistical analysis

摘要： 针对密度峰值聚类算法（DPC）不能自动确定聚类中心，并且聚类中心点与非聚类中心点在决策图上的显示不够明显的问题，设计了一种自动确定聚类中心的比较密度峰值聚类算法（ACPC）。该算法首先利用距离的比较量来代替原距离参数，使潜在的聚类中心在决策图中更加突出；然后通过二维区间估计方法进行对聚类中心的自动选取，从而实现聚类过程的自动化。仿真实验结果表明，在4个合成数据集上ACPC取得了更好的聚类效果；而在真实数据集上的Accuracy指标对比表明，在Iris数据集上，ACPC聚类结果可达到94%，与传统的DPC算法相比提高了27.3%，ACPC解决了交互式选取聚类中心的问题。

关键词: 聚类分析, 密度聚类, 密度峰值, 聚类中心, 统计分析

CLC Number:

TP181

GUO Jia, HAN Litao, SUN Xianlong, ZHOU Lijuan. Comparative density peaks clustering algorithm with automatic determination of clustering center[J]. Journal of Computer Applications, 2021, 41(3): 738-744.

郭佳, 韩李涛, 孙宪龙, 周丽娟. 自动确定聚类中心的比较密度峰值聚类算法[J]. 计算机应用, 2021, 41(3): 738-744.

References

[1] ROSENBERGER C,CHEHDI K. Unsupervised clustering method with optimal estimation of the number of clusters:application to image segmentation[C]//Proceedings of the 15th International Conference on Pattern Recognition. Piscataway:IEEE, 2000:656-659.
[2] 李晓光, 邵超. 基于网格数据中心的密度峰值聚类算法[J]. 计算机科学,2019,46(S1):457-460,487.(LI X G,SHAO C. Density peak clustering algorithm based on grid data center[J]. Computer Science,2019,46(S1):457-460,487.)
[3] 周世波, 徐维祥. 密度峰值快速搜索与聚类算法及其在船舶位置数据分析中的应用[J]. 仪器仪表学报,2018,39(7):152-163.(ZHOU S B,XU W X. Clustering by fast search and find of density peaks and its application in ship location data analysis[J]. Chinese Journal of Scientific Instrument,2018,39(7):152-163.)
[4] QI J, YU Y, WANG L, et al. An effective and efficient hierarchical K-means clustering algorithm[J]. International Journal of Distributed Sensor Networks,2017,13(8):1-17.
[5] MA L,FAN S. CURE-SMOTE algorithm and hybrid algorithm for feature selection and parameter optimization based on random forests[J]. BMC Bioinformatics,2017,18:No. 169.
[6] XU X,DING S,SHI Z. An improved density peaks clustering algorithm with fast finding cluster centers[J]. Knowledge-Based Systems,2018,158:65-74.
[7] DENG C,SONG J,SUN R,et al. GRIDEN:an effective gridbased and density-based spatial clustering algorithm to support parallel computing[J]. Pattern Recognition Letters,2018,109:81-88.
[8] 朱杰, 陈黎飞. 核密度估计的聚类算法[J]. 模式识别与人工智能,2017,30(5):439-447. (ZHU J,CHEN L F. Clustering algorithm with kernel density estimation[J]. Pattern Recognition and Artificial Intelligence,2017,30(5):439-447.)
[9] MACQUEEN J B. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley, CA:University of California Press,1967:281-297.
[10] ESTER M,KRIEGE H P,SANDER J,et al. A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Palo Alto,CA:AAAI Press,1996:226-231.
[11] ANKERST M,BREUNIG M M,KRIEGE H P,et al. OPTICS:ordering points to identify the clustering structure[C]//Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data. New York:ACM,1999:49-60.
[12] FREY B J,DUECK D. Clustering by passing messages between data points[J]. Science,2007,315(5814):972-976.
[13] RODRIGUEZ A,LAIO A. Clustering by fast search and find of density peaks[J]. Science,2014,344(6191):1492-1496.
[14] CHEN Z, QI Z, MENG F, et al. Image segmentation via improving clustering algorithms with density and distance[J]. Procedia Computer Science,2015,55:1015-1022.
[15] CHEN Y,LAI D H,QI H,et al. A new method to estimate ages of facial image for large database[J]. Multimedia Tools and Applications,2016,75(5):2877-2895.
[16] 黄岚, 李玉, 王贵参, 等. 基于点距离和密度峰值聚类的社区发现方法[J]. 吉林大学学报(工学版),2016,46(6):2042-2051. (HUANG L,LI Y,WANG G S,et al. Community detection method based on vertex distance and clustering of density peaks[J]. Journal of Jilin University (Engineering and Technology Edition),2016,46(6):2042-2051.)
[17] 杜航原, 裴希亚, 王文剑. 面向属性网络的重叠社区发现算法[J]. 计算机应用,2019,39(11):3151-3157.(DU H Y,PEI X Y,WANG W J. Overlapping community detection algorithm for attributed networks[J]. Journal of Computer Applications,2019, 39(11):3151-3157.)
[18] DU M,DING S,XU X,et al. Density peaks clustering using geodesic distances[J]. International Journal of Machine Learning and Cybernetics,2017,9(8):1335-1349.
[19] MEHMOOD R,ZHANG G,BIE R,et al. Clustering by fast search and find of density peaks via heat diffusion[J]. Neurocomputing,2016,208:210-217.
[20] 吴斌, 卢红丽, 江惠君. 自适应密度峰值聚类算法[J]. 计算机应用,2020,40(6):1654-1661.(WU B,LU H L,JIANG H J. Adaptive density peaks clustering algorithm[J]. Journal of Computer Applications,2020,40(6):1654-1661.)
[21] 马春来, 单洪, 马涛. 一种基于簇中心点自动选择策略的密度峰值聚类算法[J]. 计算机科学,2016,43(7):255-258,280. (MA C L,SHAN H,MA T. Improved density peaks based clustering algorithm with strategy choosing cluster center automatically[J]. Computer Science, 2016, 43(7):255-258,280.)
[22] 丁志成, 葛洪伟, 周竞. 基于KL散度的密度峰值聚类算法[J]. 重庆邮电大学学报(自然科学版),2019,31(3):367-374. (DING Z C,GE H W,ZHOU J. Density peaks clustering based on Kullback Leibler divergence[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition),2019,31(3):367-374.)
[23] LI Z,TANG Y. Comparative density peaks clustering[J]. Expert Systems with Application,2018,95:236-247.
[24] 晏焕钱. 基于密度峰值聚类的两种改进算法的研究[D]. 兰州:兰州大学,2018:26-28. (YAN H Q. Research on two improved density peaks clustering algorithms[D]. Lanzhou:Lanzhou University, 2018:26-28.)
[25] 刘奕志, 程汝峰, 梁永全. 一种基于共享近邻的密度峰值聚类算法[J]. 计算机科学,2018,45(2):125-129,146.(LIU Y Z, CHENG R F,LIANG Y Q. Clustering algorithm based on shared nearest neighbors and density peaks[J]. Computer Science, 2018,45(2):125-129,146.)
[26] DUA D,GRAFF C. UCI machine learning repository[EB/OL].[2019-11-05]. http://archive.ics.uci.edu/ml.
[27] 王万良, 吴菲, 吕闯. 自动确定聚类中心的快速搜索和发现密度峰值的聚类算法[J]. 模式识别与人工智能,2019,32(11):1032-1041. (WANG W L, WU F, LYU C. Automatic determination of clustering center for clustering by fast search and find of density peaks[J]. Pattern Recognition and Artificial Intelligence,2019,32(11):1032-1041.)
[28] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E:Statistical, Nonlinear, and Soft Matter Physics,2008,78(4 Pt 2):No. 046110.

Comparative density peaks clustering algorithm with automatic determination of clustering center

自动确定聚类中心的比较密度峰值聚类算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	DAI Yanran, DAI Guoqing, YUAN Yubo. Multi-face foreground extraction method based on skin color learning [J]. Journal of Computer Applications, 2021, 41(6): 1659-1666.
[2]	LYU Jia, XIAN Yan. Co-training algorithm combining improved density peak clustering and shared subspace [J]. Journal of Computer Applications, 2021, 41(3): 686-693.
[3]	WU Bin, LU Hongli, JIANG Huijun. Adaptive density peaks clustering algorithm [J]. Journal of Computer Applications, 2020, 40(6): 1654-1661.
[4]	WANG Min, WU Yubo, MIN Fan. Multi-category active learning algorithm based on multiple clustering algorithms and multivariate linear regression [J]. Journal of Computer Applications, 2020, 40(12): 3437-3444.
[5]	SU Junning, YE Dongyi. Under-sampling method based on sample density peaks for imbalanced data [J]. Journal of Computer Applications, 2020, 40(1): 83-89.
[6]	GONG Yanlu, LYU Jia. Co-training algorithm with combination of active learning and density peak clustering [J]. Journal of Computer Applications, 2019, 39(8): 2297-2301.
[7]	REN Shuai, XU Zhenchao, WANG Zhen, HE Yuan, ZHANG Tao, SU Dongxu, MU Dejun. Low-density 3D model information hiding algorithm based on multple fusion states [J]. Journal of Computer Applications, 2019, 39(4): 1100-1105.
[8]	WANG Zhihe, HUANG Mengying, DU Hui, QIN Hongwu. Integrated algorithm based on density peaks and density-based clustering [J]. Journal of Computer Applications, 2019, 39(2): 398-402.
[9]	WANG Jun, ZHOU Kai, CHENG Yong. Mixed density peaks clustering algorithm [J]. Journal of Computer Applications, 2019, 39(2): 403-408.
[10]	HAN Zhonghua, BI Kaiyuan, SI Wen, LYU Zhe. Clustering by fast search and find of density peaks based on spectrum analysis [J]. Journal of Computer Applications, 2019, 39(2): 409-413.
[11]	DU Hangyuan, PEI Xiya, WANG Wenjian. Overlapping community detection algorithm for attributed networks [J]. Journal of Computer Applications, 2019, 39(11): 3151-3157.
[12]	SUN Shilei, WANG Chao, ZHAO Yuandi. Parameter independent clustering of air traffic trajectory based on silhouette coefficient [J]. Journal of Computer Applications, 2019, 39(11): 3293-3297.
[13]	QIU Baozhi, CHENG Luan. Parameter-free clustering algorithm based on Laplace centrality and density peaks [J]. Journal of Computer Applications, 2018, 38(9): 2511-2514.
[14]	BAO Shuting, SUN Liping, ZHENG Xiaoyao, GUO Liangmin. Density peaks clustering algorithm based on shared near neighbors similarity [J]. Journal of Computer Applications, 2018, 38(6): 1601-1607.
[15]	REN Shuai, ZHANG Tao, XU Zhenchao, WANG Zhen, HE Yuan, LIU Yunong. Information hiding algorithm for 3D models based on feature point labeling and clustering [J]. Journal of Computer Applications, 2018, 38(4): 1017-1022.