密度峰值聚类算法研究进展-徐晓，丁世飞，丁玲.pdf

上善若水

499

17页

1次

2022-05-19

免费下载



密度峰值聚类算法研究进展

徐晓

,丁世飞

1,2

,丁玲

(中国矿业大学计算机科学与技术学院,江苏徐州221116)

(矿山数字化教育部工程研究中心,江苏徐州221116)

通信作者:丁世飞,E-mail:dingsf@cumt.edu.cn

摘　要:密度峰值聚类(densitypeaksclustering,DPC)算法是聚类分析中基于密度的一种新兴算法,该算法考虑局

部密度和相对距离绘制决策图,快速识别簇中心,完成聚类.DPC具有唯一的输入参数,且无需先验知识,也无需迭

代.自2014年提出以来,DPC引起了学者们的极大兴趣,并得到了快速发展.首先阐述DPC的基本理论,并通过与

经典聚类算法比较,分析了DPC的特点;其次,分别从聚类精度和计算复杂度两个角度分析了DPC的弊端及其优

化方法,包括局部密度优化、分配策略优化、多密度峰优化以及计算复杂度优化,并介绍了每个类别的主要代表

算法;最后介绍了DPC在不同领域中的相关应用研究.对DPC的优缺点提供了全面的理论分析,并对DPC的优

化以及应用进行了全面阐述.还试图找出进一步的挑战来促进DPC研究发展.

关键词:密度峰值聚类;聚类精度;计算复杂度;应用

中图法分类号:TP311

中文引用格式:徐晓,丁世飞,丁玲.密度峰值聚类算法研究进展.软件学报,2022,33(5):1800–1816.http://www.jos.org.cn/1000-

9825/6122.htm

英文引用格式:XuX,DingSF,DingL.SurveyonDensityPeaksClusteringAlgorithm.RuanJianXueBao/JournalofSoftware,

2022,33(5):1800–1816(inChinese).http://www.jos.org.cn/1000-9825/6122.htm

Survey on Density Peaks Clustering Algorithm

XUXiao

,DINGShi-Fei

1,2

,DINGLing

(SchoolofComputerScienceandTechnology,ChinaUniversityofMiningandTechnology,Xuzhou221116,China)

(MineDigitizationEngineeringResearchCenteroftheMinistryofEducation,Xuzhou221116,China)

Abstract:Density peaks clustering (DPC) algorithm is an emerging algorithm in density-based clustering analysis which draws a decision-

graph based on the calculation of local-density and relative-distance to obtain the cluster centers fast. DPC is known as only one input

parameter without prior knowledge and no iteration. Since DPC was introduced in 2014, it has attracted great interests and developments

in recent years. This survey first analyzes the theory of DPC and the satisfactory behaviors of DPC by comparing it with classical

clustering algorithms. Secondly, DPC survey is described in terms of clustering accuracy and computational complexity, including local-

density optimization, allocation-strategy optimization, multi-density peaks optimization, and computational complexity optimization, to

provide a clear organization. The main representative algorithms of each category are presented simultaneously. Finally, it introduces the

related application research of DPC in different fields. This overview offers a comprehensive analysis for the advantages and disadvantages

of DPC, and gives a comprehensive description for the improvements and applications of DPC. It is also attempted to find out some

furtherchallengestopromoteDPCresearch.

Key words:densitypeaksclustering(DPC);clusteringaccuracy;computationalcomplexity;application



随着互联网的高速发展,生成数据的方式越来越多.面对各种各样的数据,有效且高效地挖掘大规模复杂数据

成为技术改革的标志,对于促进社会发展和创造产业价值变得越来越重要

[1,2]

.聚类是一种重要的数据挖掘技术,



*

基金项目:国家自然科学基金(61976216,61672522)

收稿时间:2019-11-17;修改时间:2019-04-19,2020-06-17;采用时间:2020-07-23;jos在线出版时间:2020-09-10



软件学报ISSN1000-9825,CODENRUXUEW E-mail:jos@iscas.ac.cn

Journal of Software,2022,33(5):1800−1816[doi:10.13328/j.cnki.jos.006122] http://www.jos.org.cn

旨在识别隐藏在数据中的潜在模式

[3]

.聚类主要应用于模式识别中的语音识别和字符识别、机器学习中的图像分

割和机器视觉

[4,5]

.另外,聚类在统计学、生物学、心理学、考古学、地质学和地理学中也起着重要作用

[6−9]

聚类是一种典型的无监督学习,不需要任何的先验知识

[10]

.簇是通过某种相似性度量得到的数据对象的集

合

[11]

.同一簇中的数据对象尽可能相似,但要不同于其他簇中的对象

[12]

.目前,典型的聚类算法包括基于划分的K-

means

[13]

、基于层次的CHAMELEON

[14]

、基于网格的CLIQUE

[15]

、基于密度的DBSCAN

[16]

以及基于图论的

SpectralClustering(SC)

[17]

等.K-means使用迭代方式将数据对象划分为簇,最大程度地减少每个数据对象及其对应

簇中心之间的差异之和.然而,它需要先验知识来预设不同的适当数量的簇,并且不能获得非凸簇

[18]

.CHAMELEON

试图在不同级别划分数据对象以形成树状图聚类结构,它不需要预先确定簇数,并且可以找到非球形簇,但是受参

数设置的影响,时间复杂度很高

[19]

.CLIQUE从组织分布信息在块上的矩形块划分模式中获取围绕空间的网格结

构的值以实现聚类,算法对于大型高维空间数据的聚类是高效的,但是聚类准确性不高

[20]

.SC将数据集转换为图

结构,然后通过图划分的方式找到最佳子图以完成聚类.然而,传统的SC算法构造相似度矩阵和特征分解需要消

耗大量资源,并且它需要先验知识来预设不同的适当数量的簇

[21]

.事实上,大多数传统聚类算法,在面对任意形状

和密度的簇时都无法获得令人满意的聚类结果

[22,23]

.然而,DBSCAN作为一种基于密度的聚类算法,它引入了密

度可达的概念来定义核心对象,当正确选择了半径参数Eps和最小样本数参数Minpts时,DBSCAN可以在嘈杂的

空间中找到形状各异的簇

[24]

.但是,DBSCAN在重叠密度方面表现不佳,并且缺乏参数选择的理论基础

[25]

Rodrigues等人

[26]

提出了一种新颖的基于密度的聚类算法,称为密度峰值聚类(densitypeaksclustering,DPC)

算法,该算法已证明其在解决非球形聚类问题上的能力,并且较DBSCAN更易确定唯一输入参数.自2014年发布

以来,DPC备受关注,聚类准确性和计算效率均得到了提高,优化的DPC算法可以刺激理论研究和实际应用

[27,28]

因此,分析DPC的最新发展并研究其特性非常有意义.首先,我们对DPC进行了理论上的综合分析;其次,本研究

以一种新的方式进行阐述,根据DPC的缺点,将DPC的优化算法分为面向聚类精度和面向计算效率的两大类,面

向聚类精度的优化又分为局部密度优化的DPC算法、分配策略优化的DPC算法、多密度峰优化的DPC算法.

具体来说:首先,局部密度计算是DPC的关键步骤,需要根据数据的分布结构设计新的度量方式,从而消除参数的

敏感性并统一在不同规模数据集上的计算方法;其次,需要为非中心点分配更鲁棒的标记提高DPC的聚类精度;

第三,当数据集中一个簇涉及多个密度峰时,需要通过优化DPC识别准确的簇中心;第四,由于存储设备的限制,

需要降低DPC的计算复杂度以适应大规模数据集;此外,我们列举了相关算法的实验结果以进一步解释说明;最

后,我们总结了DPC算法在实际推广中的应用以及未来的挑战.本研究整体架构如图1所示.



1 DPC聚类算法

密度峰值聚类是2014年在《Science》上发表的一种新颖的基于密度的聚类算法

[29]

.为了找出DPC与传统

聚类算法的区别,本节介绍了DPC的理论基础和算法细节,并对其性能和特点进行了综合分析.



1.1 DPC算法原理

DPC算法的关键是根据簇中心的特征绘制决策图,以快速识别准确的簇中心

[30]

.簇中心具有两大特征:一,簇

中心被密度不超过它的邻居点包围,因此簇中心的局部密度相对较大;二,簇中心的位置相对远离具有较高局部密

度的任何其他对象,即两个簇中心之间的距离相对较远

[31]

.在DPC中,搜索簇中心需要做两个准备工作.

1)构造相似度矩阵

[32]

探索合适的相似性度量方法是聚类执行的重要过程.假设一个数据集X={x

,x

,…,x

},n是数据集的规模.

在DPC中,欧几里得距离用于计算数据对象之间的相似度:

i j

= ||x

− x

(1)

DPC的相似度矩阵是通过计算所有数据对象之间的距离构建的:

D = [d

, d

, . . . , d

]

∈ R

n×n

(2)

其中,d

=[d

,d

,…,d

].D是一个对称矩阵.



徐晓等:密度峰值聚类算法研究进展 1801

of 17

免费下载

软件学报计算机技术

关注

评论