Clustering by fast search and find of density peaks based on spectrum analysis

doi:10.11772/j.issn.1001-9081.2018061381

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (2): 409-413.DOI: 10.11772/j.issn.1001-9081.2018061381

Previous Articles Next Articles

Clustering by fast search and find of density peaks based on spectrum analysis

HAN Zhonghua^1,2, BI Kaiyuan¹, SI Wen¹, LYU Zhe¹

1. Faculty of Information and Control Engineering, Shenyang Jianzhu Universty, Shenyang Liaoning 110168, China;
2. Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang Liaoning 110016, China

Received:2018-07-03 Revised:2018-08-29 Online:2019-02-10 Published:2019-02-15
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61503259), the Liaoning Provincial Science and Technology Department Project (201602608), the Basic Research Project of Liaoning Higher Education Institutions (LJZ2017015), the Liaoning Provincial Archives Science and Technology Project (L-2018-X-10).

基于谱分析的密度峰值快速聚类算法

韩忠华^1,2, 毕开元¹, 司雯¹, 吕哲¹

1. 沈阳建筑大学信息与控制工程学院, 沈阳 110168;
2. 中国科学院沈阳自动化研究所, 沈阳 110016

通讯作者: 毕开元
作者简介:韩忠华(1977-),男,辽宁沈阳人,教授,博士,主要研究方向:生产经营管理、企业自动化系统集成、生产调度方法;毕开元(1994-),男,辽宁丹东人,硕士研究生,主要研究方向:机器学习、数据挖掘;司雯(1995-),女,河北唐山人,硕士研究生,主要研究方向:机器学习、数据挖掘;吕哲(1993-),男,甘肃兰州人,硕士,主要研究方向:机器学习、数据挖掘。
基金资助:
国家自然科学基金资助项目（61503259）；辽宁省科技厅面上项目（201602608）；辽宁省高等学校基本科研项目（LJZ2017015）；辽宁省档案科技项目（L-2018-X-10）。

Abstract

Abstract: For different clustering effects of Clustering by Fast Search and Find of Density Peaks (CFSFDP) on different datasets, an improved CFSFDP algorithm based on spectral clustering was proposed, namely CFSFDP-SA (CFSFDP based on Spectrum Analysis). Firstly, a high-dimensional non-linear dataset was mapped into a low-dimensional subspace to realize dimension reduction, then the clustering problem was transformed into the optimal partitioning problem of the graph to enhance the algorithm adaptability to the global structure of the data. Secondly, the CFSFDP algorithm was used to cluster the processed dataset. Combining the advantages of these two clustering algorithms, the clustering performance was further improved. The clustering results of two artificial linear datasets, three artificial nonlinear datasets and four real datasets in UCI show that compared with CFSFDP, the CFSFDP-SA algorithm has higher clustering precision, achieving up to 14% improvement in accuracy for high-dimensional dataset, which means CFSFDP-SA is more adaptable to the original datasets.

Key words: data clustering, adaptability, dimension reduction, Clustering by Fast Search and Find of Density Peaks (CFSFDP), spectrum analysis

摘要： 针对密度峰值快速聚类（CFSFDP）算法对不同数据集聚类效果的差异，利用谱聚类对密度峰值快速聚类算法加以改进，提出了一种基于谱分析的密度峰值快速聚类算法CFSFDP-SA。首先，将高维非线性的数据集映射到低维子空间上实现降维处理，将聚类问题转化为图的最优划分问题以增强算法对数据全局结构的适应性；然后，利用CFSFDP算法对处理后的数据集进行聚类。结合这两种聚类算法各自的优势，能进一步提升聚类算法的性能。在5个人工合成数据集（2个线性数据集和3个非线性数据集）与4个UCI数据库中真实数据集上的聚类结果显示，相比CFSFDP算法，CFSFDP-SA算法的聚类精度有一定提升，在高维数据集的聚类精度上最多提高了14%，对原始数据集的适应性更强。

关键词: 数据聚类, 适应性, 降维, 密度峰值快速聚类, 谱分析

CLC Number:

TP301.6

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.

韩忠华, 毕开元, 司雯, 吕哲. 基于谱分析的密度峰值快速聚类算法[J]. 计算机应用, 2019, 39(2): 409-413.

References

[1] 蔡晓妍,戴冠中,杨黎斌.谱聚类算法综述[J]. 计算机科学,2008,35(7):14-18. (CAI X Y, DAI G Z, YANG L B. Survey on spectral clustering algorithms[J]. Computer Science, 2008, 35(7):14-18.)
[2] 申彦.大规模数据集高效数据挖掘算法研究[D].镇江:江苏大学, 2013:1-8. (SHEN Y. The research of high efficient data mining algorithms for massive data sets[D]. Zhenjiang:Jiangsu University, 2013:1-8.)
[3] 唐东明. 聚类分析及其应用研究[D].成都:电子科技大学, 2010:13-27. (TANG D M. Study on clustering analysis and its applications[D]. Chengdu:University of Electronic Science and Technology of China, 2010:13-27.)
[4] 贺玲,蔡益朝,杨征.高维数据聚类方法综述[J]. 计算机应用研究,2010,27(1):23-27. (HE L, CAI Y C, YANG Z. Survey of clustering algorithms for high-dimensional data[J]. Application Research of Computers, 2010, 27(1):23-27.)
[5] 张文开.基于密度的层次聚类算法研究[D]. 合肥:中国科学技术大学, 2015:15-26. (ZHANG W K. Research on density-based hierarchical clustering algorithm[D]. Hefei:University of Science and Technology of China, 2015:15-26.)
[6] 张蓉,彭宏.一种基于超图模式的高维空间数据聚类方法[J]. 计算机工程,2002,28(7):54-55. (ZHANG R, PENG H. Method for data clustering in a high dimensional space based on a hypergraph model[J]. Computer Engineering, 2002, 28(7):54-55.)
[7] 冯少荣,肖文俊. DBSCAN聚类算法的研究与改进[J].中国矿业大学学报,2008,37(1):105-106. (FENG S R, XIAO W J. An improved DBSCAN clustering algorithm[J]. Journal of China University of Mining & Technology, 2008,37(1):105-106.)
[8] 马春来,单洪,马涛,等.一种基于CFSFDP改进算法的重要地点识别方法研究[J].计算机应用研究,2017,34(1):136-140. (MA C L, SHAN H, MA T, et al. Research on important places identification method based on improved CFSFDP algorithm[J]. Application Research of Computers, 2017, 34(1):136-140.)
[9] 马春来,单洪,马涛.一种基于簇中心点自动选择策略的密度峰值聚类算法[J].计算机科学,2016,43(7):255-258. (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.)
[10] 蒋礼青,张明新,郑金龙.快速搜索与发现密度峰值聚类算法的优化研究[J].计算机应用研究,2016,33(11):3251-3254. (JIANG L Q, ZHANG M X, ZHENG J L. Optimization of clustering by fast search and find of density peaks[J]. Application Research of Computers, 2016, 33(11):3251-3254.)
[11] 李金泽,徐喜荣,潘子琦,等.改进的自适应谱聚类NJW算法[J].计算机科学,2017,44(6):424-427. (LI J Z, XU X R, PAN Z Q, et al. Improved adaptive spectral clustering NJW algorithm[J]. Computer Science, 2017, 44(6):424-427.)
[12] 李届家,郭鹏程,韩忠华.在高维数据上的近邻传播聚类降维研究[J]. 控制工程,2016,23(9):1419-1422. (LI J J, GUO P C, HAN Z H. Research of affinity propagation clustering dimension reduction on high-dimensional data[J]. Control Engineering of China, 2016,23(9):1419-1422.)
[13] 周世兵,徐振源,唐旭清.基于近邻传播算法的最佳聚类数确定方法比较研究[J].计算机科学,2011,38(2):225-228. (ZHOU S B, XU Z Y, TANG X Q. Comparative study on method for determining optimal number of clusters based on affinity propagation clustering[J]. Computer Science, 2011, 38(2):225-228.)
[14] 吕宗磊.对聚类及聚类评价若干问题的研究[D].南京:南京航空航天大学,2009:10-24. (LYU Z L. The research on several issues of clustering and clustering validity indexes[D]. Nanjing:Nanjing University of Aeronautics and Astronautics, 2009:10-24.)

[1]	TIAN Zhihong, ZHAO Jindong. Overview of blockchain consensus mechanism for internet of things [J]. Journal of Computer Applications, 2021, 41(4): 917-929.
[2]	HU Min, BAI Xue, XU Wei, WU Bingjian. Review of anomaly detection algorithms for multidimensional time series [J]. Journal of Computer Applications, 2020, 40(6): 1553-1564.
[3]	WANG Jinkai, JIA Xu. Vehicle face recognition algorithm based on NMF with weighted and orthogonal constraints [J]. Journal of Computer Applications, 2020, 40(4): 1050-1055.
[4]	WANG Qiaoling, QIAO Fei, JIANG Youhao. Improved K-means algorithm with aggregation distance coefficient [J]. Journal of Computer Applications, 2019, 39(9): 2586-2590.
[5]	ZHANG Yonglai, ZHOU Yaojian. Review of clustering algorithms [J]. Journal of Computer Applications, 2019, 39(7): 1869-1882.
[6]	DING Cheng, WANG Qiuping, WANG Xiaofeng. Krill herd algorithm based on generalized opposition-based learning and its application in data clustering [J]. Journal of Computer Applications, 2019, 39(2): 336-342.
[7]	CHEN Jingren, WU Yefu, WU Bing. Driver behavior spectrum analysis method based on vehicle driving data [J]. Journal of Computer Applications, 2018, 38(7): 1916-1922.
[8]	WANG Aizhen, HU Jiao, HAN Hangcheng. Capture method of direct sequence spread spectrum signal based on cascade stochastic resonance [J]. Journal of Computer Applications, 2018, 38(7): 2020-2023.
[9]	YANG Hongyu, NING Yuguang. Adaptive weight allocation method of risk assessment index for access control of cloud platform [J]. Journal of Computer Applications, 2018, 38(6): 1614-1619.
[10]	SUN Shengzi, WAN Yuan, ZENG Cheng. Semi-supervised adaptive multi-view embedding method for feature dimension reduction [J]. Journal of Computer Applications, 2018, 38(12): 3391-3398.
[11]	JIA Xu, SUN Fuming, LI Haojie, CAO Yudong. Image feature extraction method based on improved nonnegative matrix factorization with universality [J]. Journal of Computer Applications, 2018, 38(1): 233-237.
[12]	ZHU Jie, CHEN Lifei. Bayesian clustering algorithm for categorical data [J]. Journal of Computer Applications, 2017, 37(4): 1026-1031.
[13]	FANG Jianchao, MAO Xuesong. Fourier spectrum analysis for non-uniform sampled signals [J]. Journal of Computer Applications, 2016, 36(2): 492-494.
[14]	XU Chun, GUO Wenqiang, GUNIMIRE Awudan. Adaptability of light source array simplification in wireless optical access network [J]. Journal of Computer Applications, 2016, 36(10): 2675-2679.
[15]	JIN Liyan, CHEN Li, FAN Taiting, GAO Jing. Speech denoising algorithm based on singular spectrum analysis and Wiener filtering [J]. Journal of Computer Applications, 2015, 35(8): 2336-2340.

Clustering by fast search and find of density peaks based on spectrum analysis

基于谱分析的密度峰值快速聚类算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics