ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2020, Vol. 57 ›› Issue (2): 378-394.doi: 10.7544/issn1000-1239.2020.20190104

• 人工智能 • 上一篇    下一篇

密度峰值聚类算法综述

陈叶旺1,2,3,4, 申莲莲1, 钟才明5, 王 田1, 陈 谊2, 杜吉祥1   

  1. 1(华侨大学计算机科学与技术学院 福建厦门 361021);2(食品安全大数据技术北京市重点实验室(北京工商大学) 北京 100048);3(江苏省计算机信息处理技术重点实验室(苏州大学) 江苏苏州 215006);4(福建省大数据智能与安全重点实验室(华侨大学) 福建厦门 361021);5(宁波大学信息学院 浙江宁波 315211) (ywchen@hqu.edu.cn)
  • 出版日期: 2020-02-01
  • 基金资助: 
    国家自然科学基金项目(61673186,71771094,61876068,61972010);泉州市高层次人才创新创业项目(2018C114R,2018C110R);福建省科技计划项目(2017H01010065,2019H01010129)

Survey on Density Peak Clustering Algorithm

Chen Yewang1,2,3,4, Shen Lianlian1, Zhong Caiming5, Wang Tian1, Chen Yi2, and Du Jixiang1   

  1. 1(College of Computer Science and Technology, Huaqiao University, Xiamen, Fujian 361021);2(Beijing Key Laboratory of Big Data Technology for Food Safety (Beijing Technology and Business University), Beijing 100048);3(Provincial Key Laboratory for Computer Information Processing Technology (Soochow University), Suzhou, Jiangsu 215006);4(Fujian Key Laboratory of Big Data Intelligence and Security (Huaqiao University), Xiamen, Fujian 361021);5(College of Information, Ningbo University, Ningbo, Zhejiang 315211)
  • Online: 2020-02-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61673186, 71771094, 61876068, 61972010), the Quanzhou City Science & Technology Program of China (2018C114R, 2018C110R), and the Project of Science and Technology Plan of Fujian Province of China (2017H01010065, 2019H01010129).

摘要: 密度峰值聚类(density peak, DPeak)算法是一种简单有效的聚类算法,它可将任意维度数据映射成2维,在降维后的空间中建构出数据之间的层次关系,可以非常容易地从中挑选出密度高、且与其他密度更高区域相隔较远的数据点.这些点被称为密度峰值点,可以用来作为聚类中心.根据建构好的层次关系,该算法提供了2种不同的方式完成最后聚类:一种是与用户交互的决策图,另一种是自动化方式.跟踪了DPeak近年来的发展与应用动态,对该算法的各种改进或变种从以下3方面进行了总结和梳理:首先,介绍了DPeak算法原理,对其在聚类算法分类体系中的位置进行了讨论.将其与5个主要的聚类算法做了比较之后,发现DPeak与均值漂移聚类算法(mean shift)有诸多相似之处,因而认为其可能为mean shift的一个特殊变种.其次,讨论了DPeak的几个不足之处,如复杂度较高、自适应性不足、精度低和高维数据适用性差等,将针对这些缺点进行改进的相关算法做了分类讨论.此外,梳理了DPeak算法在不同领域中的应用,如自然语言处理、生物医学应用、光学应用等.最后,探讨了密度峰值聚类算法所存在的问题及挑战,同时对进一步的工作进行展望.

关键词: 聚类算法, 密度峰值, 大数据, 数据挖掘, 密度聚类

Abstract: DPeak(density peak) is a simple but effective clustering method. It is able to map data with arbitrary dimension onto a 2-dimensional space, and construct hierarchical relationship for all data points on the new reduction space. This makes it is easy to pick up some distinguished points (density peaks), each of which has high density and large distance from other regions of higher density. In addition, based on regarding theses density peaks as cluster centers and the hierarchical relationship, the algorithm provides two different ways to perform the final task of clustering, i.e., one is decision diagram that can interact with users, and the other is an automatic method. In this paper, we trace the development and application trends of DPeak in recent years, summarize and comb various improvements or variations of DPeak algorithm from the following aspects. Firstly, the principle of DPeak algorithm is introduced, and its position in the classification system of clustering algorithm is discussed as well. After comparing DPeak with several other main clustering algorithms, it is found that DPeak is highly similar to mean shift, and hence, we think that DPeak may be a special variant of mean shift. Secondly, some shortcomings of DPeak are discussed, such as high time complexity, lack of adaptability, low precision and inefficiency in high dimensional space etc., and then various improved algorithms are demonstrated in different categories. In addition, some applications of DPeak in different fields, such as natural language processing, biomedical analysis and optical applications etc., are presented and combed. Last but not least, we look forward to its future work based on the problems and challenges of the DPeak.

Key words: clustering algorithm, density peak, big data, data mining, density clustering

中图分类号: