基于密度峰值剪枝后的最短路径聚类算法

doi:10.3969/j.issn.0255-8297.2020.05.010

Abstract

Abstract: Clustering is to classify multiple empirical data according to their similarity or proximity based on data labels and properties. For the clustering algorithm based on the density peaks, it mainly focuses on the determination of the clustering center and how to allocate the remaining points. In this paper, according to a trainable clustering algorithm based on shortest paths to density peaks, the clustering center is determined by the density peaks. We propose that using a cutoff threshold and pruning the path graph to improve the algorithm. The remaining points are allocated globally based on the shortest path method. It is proved that the algorithm can significantly improve the efficiency while maintaining the clustering accuracy.

Key words: clustering, density peak, shortest path method, pruning path

CLC Number:

TP301.6

HU Enxiang, WANG Chunyu, PAN Meiqin. Clustering by Pruning Paths Based on Shortest Paths from Density Peaks[J]. Journal of Applied Sciences, 2020, 38(5): 792-802.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jas.shu.edu.cn/EN/10.3969/j.issn.0255-8297.2020.05.010

https://www.jas.shu.edu.cn/EN/Y2020/V38/I5/792

References

[1] Ester M, Kriegel H P. A density-based algorithm for discovering clusters in large spatial databases with noise[J]. Knowledge Discovery & Data Mining, 1996, 96(34):226-231.
[2] 夏鲁宁, 荆继武. SA-DBSCAN:一种自适应基于密度聚类算法[J]. 中国科学院研究生院学报, 2009, 26(4):530-538. Xia L N, Jing J W. SA-DBSCAN:an adaptive clustering algorithm based on density[J]. Journal of University of Chinese Academy of Science, 2009, 26(4):530-538. (in Chinese)
[3] 周水庚, 周傲英, 曹晶. 基于数据分区的DBSCAN算法[J]. 计算机研究与发展, 2000, 37(10):1153-1159. Zhou S G, Zhou A Y, Cao J. DBSCAN algorithm based on data partition[J]. Journal of Computer Research and Development, 2000, 37(10):1153-1159. (in Chinese)
[4] 周水庚, 周傲英, 曹晶, 等. 一种基于密度的快速聚类算法[J]. 计算机研究与发展, 2000, 37(11):8-13. Zhou S G, Zhou A Y, Cao J, et al. A fast clustering algorithm based on density[J]. Journal of Computer Research and Development, 2000, 37(11):8-13. (in Chinese)
[5] Rodriguez A, Laio A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191):1492-1496.
[6] Pizzagalli D U, Gonzalez S F, Krause R. A trainable clustering algorithm based on shortest paths from density peaks[J]. Science Advances, 2019, 5(10):eaax3770.
[7] Wang X F, Xu Y F. Fast clustering using adaptive density peak detection[J]. Statistical Methods in Medical Research, 2017, 26(6):2800-2811.
[8] 谢娟英, 高红超, 谢维信. K近邻优化的密度峰值快速搜索聚类算法[J]. 中国科学:信息科学, 2016, 46(2):258-280. Xie J Y, Gao H C, Xie W X. A fast clustering algorithm based on K-nearest neighbor optimized density[J]. Science China:Information Science, 2016, 46(2):258-280. (in Chinese)
[9] Wang S L, Wang D K, Li C Y, et al. Clustering by fast search and find of density peaks with data field[J]. Chinese Journal of Electronics, 2016, 25(3):397-402.
[10] 高诗莹, 周晓锋, 李帅. 基于密度比例的密度峰值聚类算法[J]. 计算机工程与应用, 2017, 53(16):10-17. Gao S Y, Zhou X F, Li S. A fast clustering algorithm based on density ratio[J]. Computer Engineering and Applications, 2017, 53(16):10-17. (in Chinese)
[11] Zhang W, Li J. Extended fast search clustering algorithm:widely density clusters, no density peaks[J]. Computer Science, 2015, 5(7):415-423.
[12] 蒋礼青, 张明新, 郑金龙, 等. 快速搜索与发现密度峰值聚类算法的优化研究[J]. 计算机应用研究, 2016, 33(11):3251-3254. Jiang L Q, Zhang M X, Zheng J L, et al. Optimization research of the fast clustering algorithm based on density peaks[J]. Application Research of Computers, 2016, 33(11):3251-3254. (in Chinese)
[13] Tang G, Jia S, Li J. An enhanced density peak-based clustering approach for hyperspectral band selection[C]//2015 IEEE International Geoscience and Remote Sensing Symposium (IGARSS). IEEE, 2015:1116-1119.
[14] Tenenbaum J B, Silva V D, Langford J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000, 290(5500):2319-2323.
[15] Xu X H, Ju Y S, Liang Y L, et al. Manifold density peaks clustering algorithm[C]//Third International Conference on Advanced Cloud & Big Data. IEEE, 2016:311-318.
[16] Du M, Ding S, Xu X, et al. Density peaks clustering using geodesic distances[J]. International Journal of Machine Learning & Cybernetics, 2017, 9(8):1335-1349.
[17] Cheng Y. Mean shift, mode seeking, and clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1995, 17(8):790-799.
[18] Satopaa V, Albrecht J, Irwin D, et al. Finding a kneedle in a haystack:detecting knee points in system behavior[C]//International Conference on Distributed Computing Systems Workshops. IEEE Computer Society, 2011:166-171.
[19] Wiwie C, Baumbach J, RÖTtger R. Comparing the performance of biomedical clustering methods[J]. Nature Methods, 2015, 12(11):1033.
[20] 周志华. 机器学习[J]. 中国民商, 2016(3):198-199. Zhou Z H. Machine learning[J]. China Non-Governmental, 2016(3):198-199. (in Chinese)

Clustering by Pruning Paths Based on Shortest Paths from Density Peaks

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	JIN Zhengyang, YAN Shaohong, ZHANG Yanbo, YAO Xulong, TAO Zhigang, CHEN Zhiyuan. Three-Dimensional Fuzzy Clustering Algorithm Integrating Spatial Texture Features [J]. Journal of Applied Sciences, 2026, 44(1): 134-148.
[2]	YI Huawei, SONG Shixi, WANG Yanfei, BAI Siyi. Federated Recommendation Algorithm Integrating Graph Neural Networks and Depth Graph Clustering [J]. Journal of Applied Sciences, 2026, 44(1): 83-96.
[3]	LI Yongzhen, MA Fuyuan, MA Shixuan, WANG Yuhan, WANG Ying. Network Community Detection Based on Structure-Enhanced Deep Clustering [J]. Journal of Applied Sciences, 2026, 44(1): 1-20.
[4]	LUO Hongmei, WANG Changjiang, YANG Peijie, GUAN Xiaoyan, ZHOU Xiaojie, YU Hang. Seismic Phase Clustering Analysis Technology Based on Multi-granularity Ensemble Learning [J]. Journal of Applied Sciences, 2025, 43(4): 643-655.
[5]	SUN Lijun, XU Xingjian, MENG Fanjun. Joint Extraction of Curriculum Entity Relationships Based on Parallel Decoding and Clustering [J]. Journal of Applied Sciences, 2025, 43(2): 334-347.
[6]	YUAN Ziye, QIU Baolin, YE Yu, WEN Wenying, HUA Dingli, ZHANG Yushu. A Robust Coverless Image Steganography Method for Coding Camouflage [J]. Journal of Applied Sciences, 2024, 42(3): 469-485.
[7]	LIU Yuxin, YE Xijuan, BAO Junwei, MA Jian, CHEN Xiaomin, LI Mingsheng, ZHU Qiuming. 5G Channel Propagation Model and Signal Coverage Inside Aircraft Cabin Scenarios [J]. Journal of Applied Sciences, 2024, 42(3): 425-436.
[8]	GUAN Zheng, YIN Yongqiang, ZHANG Xiaoxiang, CHEN Yuehong. Estimating Flash Flood Disaster Susceptibility Based on K-means Clustering and Ensemble Learning Approaches [J]. Journal of Applied Sciences, 2024, 42(3): 388-404.
[9]	ZHANG Faying, LYU Li, HAN Longzhe, LIU Dongxiao, FAN Tanghuai. Intuition Fuzzy and Structural Least Squares Twin Support Vector Machine [J]. Journal of Applied Sciences, 2024, 42(2): 350-363.
[10]	ZHANG Ziyang, ZHAO Junhui, MA Xiaoting. Large-Scale Device Access Algorithm for 5G Cellular Internet of Things [J]. Journal of Applied Sciences, 2023, 41(4): 626-635.
[11]	CHEN Xijiang, AN Qing, BAN Ya, WANG Dexin, LI Kun, LIU Haipeng. Point Cloud Object Extraction Based on Gaussian Kernel Function and Exponential Function Clustering [J]. Journal of Applied Sciences, 2022, 40(3): 411-422.
[12]	LIU Yawen, ZHANG Ying. Vehicle Point Cloud Clustering Based on Contextual Feature and Graph Cut [J]. Journal of Applied Sciences, 2020, 38(6): 924-935.
[13]	ZHANG Xiaoning, KONG Xiangzhen, LUO Chuanwen, LIU Jinxing. Integrated Robust Structured NMF Model for Sample Clustering and Network Analysis [J]. Journal of Applied Sciences, 2020, 38(5): 825-842.
[14]	WEI Ziyang, ZHAO Zhihong, ZHAO Jingjiao. Improved Faster R-CNN Algorithm and Its Application on Vehicle Detection [J]. Journal of Applied Sciences, 2020, 38(3): 377-387.
[15]	HU Bengu, DAI Muhong. Multiple-center Points Incremental Fuzzy Clustering Algorithm [J]. Journal of Applied Sciences, 2019, 37(6): 806-814.