引用本文

纪霞, 姚晟, 赵鹏. 相对邻域与剪枝策略优化的密度峰值聚类算法. 自动化学报, 2020, 46(3): 562−575 doi: 10.16383/j.aas.c170612

Ji Xia, Yao Sheng, Zhao Peng. Relative neighborhood and pruning strategy optimized density peaks clustering algorithm. Acta Automatica Sinica, 2020, 46(3): 562−575 doi: 10.16383/j.aas.c170612

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c170612

关键词

聚类算法，密度峰值，相对邻域，剪枝策略 

摘要

针对Science发表的密度峰值聚类(Density peaks clustering, DPC)算法及其改进算法效率不高的缺陷, 提出一种相对邻域和剪枝策略优化的密度峰值聚类(Relative neighborhood and pruning strategy optimized DPC, RP-DPC)算法. DPC聚类算法主要有两个阶段: 聚类中心点的确定和非聚类中心点样本的类簇分配, 并且时间复杂度集中在第1个阶段, 因此RP-DPC算法针对该阶段做出改进研究. RP-DPC算法去掉了DPC算法预先计算距离矩阵的步骤, 首先利用相对距离将样本映射到相对邻域中, 再从相对邻域来计算各样本的密度, 从而缩小各样本距离计算及密度统计的范围; 然后在计算各样本的δ值时加入剪枝策略, 将大量被剪枝样本δ值的计算范围从样本集缩小至邻域以内, 极大地提高了算法的效率. 理论分析和在人工数据集及UCI数据集的对比实验均表明, 与DPC算法及其改进算法相比, RP-DPC算法在保证聚类质量的同时可以实现有效的时间性能提升.

文章导读

聚类分析简称聚类, 是根据样本间的相似性将样本集划分成合理类簇的过程, 聚类结果使得同一类簇中的样本具有较高的相似性, 而不同类簇之间的样本相似性较低[1-3]. 聚类是数据挖掘中的基本技术, 能够从数据中发现潜藏的知识和模式, 已广泛应用于社会网络分析、图像模式识别、智能商务等众多领域.大数据背景下, 数据的海量、多样和复杂使得具有自动理解、处理和概括数据的高效聚类算法研究迫在眉睫[4].

聚类算法大致可以分为划分式聚类方法[5-6]、层次聚类方法[7]、基于网格的聚类方法[8]和基于密度的聚类方法[9]等. 其中, 基于密度的聚类方法可以发现任意形状的类簇, 对噪音数据不敏感, 且聚类时不需要事先知道类簇的个数, 是数据挖掘技术中广泛使用的一类方法.

快速搜索和发现样本密度峰值聚类(Density peaks clustering, DPC)算法是Rodriguez等[10]近年在Science发表的一种新型聚类算法. 与其他聚类算法不同, DPC算法能自动确定类簇数和类簇中心点, 并进行高效的非中心点样本分配和离群点剔除, 因而吸引了众多学者对它进行深入研究. Wang等[11]针对DPC算法对输入参数dc (密度计算的截断距离)敏感, 并且没有有效的设定准则的问题, 在采用核函数计算密度的情况下, 结合数据域的概念提出了一种自动计算dc的方法. 同时, 强调在大数据量情况下算法效率是DPC算法亟待研究的关键问题. Zhang等[12]针对DPC算法不能解决一个类簇中多密度峰值或者无密度峰值的情况, 提出一种扩展的E_CFSFDP (Extended clustering by fast search and find of density peaks)算法, 在DPC算法聚类完成之后, 多执行一个子类的合并步骤. 该扩展方法在无密度峰值的数据集上取得了更好的实验效果, 但是时间开销巨大, 作者也将降低时间消耗作为下一步研究的重点. 谢娟英等[13]针对DPC算法中截断距离dc对聚类结果影响较大和样本分配策略可能会导致的“多米诺骨牌”效应的问题, 分别提出了K近邻优化和模糊加权K近邻优化的密度聚类方法KNN-DPC (K-nearest neighbors optimized density peaks clustering)和FKNN-DPC (Fussy weighted KNN-DPC)[14], 并通过实验证明了改进方法的有效性. 但是并未给出关于引入参数K的有效设定方法, 同时由于额外K近邻的查找和复杂的类簇分配策略的引入, 使得KNN-DPC和FKNN-DPC算法的时间复杂性都要远高于DPC, 极大地影响了算法的实用性. 因为DPC算法首先需要计算数据集中任意两个样本间的欧氏距离, 其时间复杂度为${\rm O}(m\times n^2)$(m为样本特征个数, n为数据集样本个数), 当处理海量高维数据时,大量的高维欧氏距离计算会带来高额的时间开销, 严重影响了算法的实用性, 所以对DPC算法的效率改进展开研究具有重要的应用价值. 巩树凤等[15]考虑了DPC算法效率不高的问题, 给出了分布式环境下的密度中心聚类算法SDDPC (Simple distributed density peaks clustering), 并且结合Voronoi图提出了优化的EDDPC (Efficient distributed density peaks clustering)算法, 提高了分布式环境下DPC算法的效率, 但并没有涉及DPC算法本身的研究与改进.

针对DPC算法和现有改进算法在效率方面的不足, 本文提出一种基于相对邻域和剪枝策略的密度峰值快速搜索聚类(Relative neighborhood and pruning strategy optimized density peaks clustering, RP-DPC)算法. RP-DPC的主要贡献包括: 1)改变原DPC算法的流程, 不再预先计算样本两两之间的距离, 改为在聚类过程中计算必要的样本间距离, 从而避免了大量冗余距离的计算; 2)借助双基准点映射的相对邻域来大致衡量样本之间的亲疏关系, 从而只需要对相对“亲密”的样本进行距离计算和密度统计; 3)在计算样本的斥群值(与更高密度样本之间距离的最小值[15])时加入剪枝策略, 极大地缩小被剪枝样本的斥群值查找范围, 从而加快了算法的效率; 4) 理论分析和在多个数据集上的对比实验均表明, RP-DPC算法具有和DPC算法同样的聚类效果, 时间性能却大大优于已有的DPC算法及其改进算法.

图 1  算法流程图

图 2  相对邻域映射模型

图 3  6种算法在flame数据集的聚类结果

本文针对密度中心聚类算法DPC及其改进算法效率不高的问题, 基于相对邻域映射与剪枝策略提出了一种高效的密度中心聚类RP-DPC算法. 与DPC算法及其改进算法相比, RP-DPC通过双基准点的距离映射给出了样本间的相对位置, 缩小了样本密度统计的范围, 从而避免了很多冗余的距离计算. 在样本$ \delta $值计算中引入剪枝策略, 缩小样本的$ \delta $值计算范围, 有效地提高了算法的效率. 如何将邻域信息引入到非类簇中心点样本的类簇分配, 实现高效且高质量的聚类是下一步将研究的问题.

作者简介

纪霞

博士, 安徽大学计算机科学与技术学院讲师. 主要研究方向为数据挖掘与机器学习, 粒计算与粗糙集理论. 本文通信作者. E-mail: jixia1983@163.com

姚晟

博士, 安徽大学计算机科学与技术学院讲师. 主要研究方向为粗糙集理论与粒计算.E-mail: fishenyao@126.com

赵鹏

博士, 安徽大学计算机科学与技术学院副教授. 主要研究方向为机器学习, 智能信息处理.E-mail: zhaopeng_ad@163.com