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

doi:10.3969/j.issn.0255-8297.2020.05.010

应用科学学报 ›› 2020, Vol. 38 ›› Issue (5): 792-802.doi: 10.3969/j.issn.0255-8297.2020.05.010

• 智能计算新技术 • 上一篇

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

胡恩祥¹, 汪春雨², 潘美芹¹

1. 上海外国语大学国际工商管理学院, 上海 201600;
2. 华东师范大学计算机科学与技术学院, 上海 200062

收稿日期:2020-05-25 发布日期:2020-10-14
通信作者: 潘美芹,副教授,研究方向为个人信用评估与决策分析.E-mail:panmqin@sina.com E-mail:panmqin@sina.com
基金资助:
上海外国语大学规划项目基金（No.2019114009）资助

Clustering by Pruning Paths Based on Shortest Paths from Density Peaks

HU Enxiang¹, WANG Chunyu², PAN Meiqin¹

1. School of Business and Management, Shanghai International Studies University, Shanghai 201600, China;
2. School of Computer Science and Technology, East China Normal University, Shanghai 200062, China

Received:2020-05-25 Published:2020-10-14

摘要/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

中图分类号:

TP301.6

胡恩祥, 汪春雨, 潘美芹. 基于密度峰值剪枝后的最短路径聚类算法[J]. 应用科学学报, 2020, 38(5): 792-802.

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.

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	魏子洋, 赵志宏, 赵敬娇. 改进Faster R-CNN算法及其在车辆检测中的应用[J]. 应用科学学报, 2020, 38(3): 377-387.
[2]	胡本固, 戴牡红. 多中心点增量式模糊聚类算法[J]. 应用科学学报, 2019, 37(6): 806-814.
[3]	余玥, 邓丽, 庞洪霖, 费敏锐. 基于分布式聚类的作物生长环境异常检测方法[J]. 应用科学学报, 2018, 36(6): 1010-1021.
[4]	韦秋含, 梁海华, 张新鹏. 基于动态BoW模型的密文JPEG图像检索[J]. 应用科学学报, 2018, 36(4): 628-634.
[5]	巫兆聪, 项伟, 李俊, 杨志. 基于满足度评估的遥感应用需求聚类算法[J]. 应用科学学报, 2018, 36(4): 635-643.
[6]	陈江平, 谭波, 连世忠. 湖北省雷击关联规则挖掘发现[J]. 应用科学学报, 2017, 35(1): 42-50.
[7]	胡昭华, 王冠南, 王珏, 邵晓雯, 卞飞飞. 模板在线聚类的目标跟踪[J]. 应用科学学报, 2016, 34(4): 430-440.
[8]	姚利涛，董育宁. 无监督的视频业务特征分析与分类[J]. 应用科学学报, 2015, 33(2): 117-128.
[9]	吴诗婳1，吴一全1,2,3,4,5，周建江1，孟天亮1，戴一冕1. 基于Shearlet 变换和Krawtchouk 矩不变量的河流SAR 图像分割[J]. 应用科学学报, 2015, 33(1): 21-31.
[10]	喻钧1, 刘飞鸿1, 王占峰2, 杨俊娜1. 基于色度直方图的颜色聚类算法[J]. 应用科学学报, 2015, 33(1): 95-104.
[11]	谢凯，张涛，奚玲，李文祥，平西建. k均值聚类的混合异构图像隐写分析[J]. 应用科学学报, 2014, 32(5): 543-550.
[12]	董天宝. 采用孤立点检测的欠定混合矩阵盲辨识[J]. 应用科学学报, 2013, 31(5): 481-487.
[13]	喻钧，双晓. 仿造数码迷彩的设计方法[J]. 应用科学学报, 2012, 30(4): 331-334.
[14]	吴昊，苏卫民，顾红. 干扰环境下数目可变的多目标跟踪[J]. 应用科学学报, 2012, 30(3): 263-269.
[15]	潘斌，舒宁. 聚类分析用于序列SAR干涉像对选取[J]. 应用科学学报, 2010, 28(5): 501-506.