高级检索
    陈叶旺, 申莲莲, 钟才明, 王田, 陈谊, 杜吉祥. 密度峰值聚类算法综述[J]. 计算机研究与发展, 2020, 57(2): 378-394. DOI: 10.7544/issn1000-1239.2020.20190104
    引用本文: 陈叶旺, 申莲莲, 钟才明, 王田, 陈谊, 杜吉祥. 密度峰值聚类算法综述[J]. 计算机研究与发展, 2020, 57(2): 378-394. DOI: 10.7544/issn1000-1239.2020.20190104
    Chen Yewang, Shen Lianlian, Zhong Caiming, Wang Tian, Chen Yi, Du Jixiang. Survey on Density Peak Clustering Algorithm[J]. Journal of Computer Research and Development, 2020, 57(2): 378-394. DOI: 10.7544/issn1000-1239.2020.20190104
    Citation: Chen Yewang, Shen Lianlian, Zhong Caiming, Wang Tian, Chen Yi, Du Jixiang. Survey on Density Peak Clustering Algorithm[J]. Journal of Computer Research and Development, 2020, 57(2): 378-394. DOI: 10.7544/issn1000-1239.2020.20190104

    密度峰值聚类算法综述

    Survey on Density Peak Clustering Algorithm

    • 摘要: 密度峰值聚类(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.

       

    /

    返回文章
    返回