基于高斯核优化的密度峰值聚类算法

王舰

摘要：DPC算法在处理紧密相邻的团形簇时，对于簇间样本点分配效果不佳，同时DPC算法对于团形簇由密集到稀疏的渐变区域，即边界点和噪音点的划分也存在着缺陷。针对这两个问题，本文提出基于高斯核优化的密度峰值聚类算法（Gauss-DPC）。Gauss-DPC算法在DPC聚类算法快速发现簇中心的基础之上，通过计算簇内样本点到簇中心距离的统计量，利用统计量构建高斯判别式，使用高斯判别式进行簇间样本点的分配，最后引入高斯约束来区分簇边界点和噪声点。通过实验证明了Gauss-DPC算法具有更好的聚类效果，而且Gauss-DPC可以动态的控制簇的边界范围。

关键词：密度峰值聚类;簇内统计量;高斯核;边界约束

中图分类号：TP391文献标识码：A

文章编号：1009-3044（2020）28-0192-03

1引言

聚类算法作为无监督学习的分支，是数据挖掘领域的一个重要研究方向。聚类算法在无任何先验知识的情况下，对数据集进行特征提取[1]，发现数据中隐藏的内在模式与规律。目前聚类算法的主要分类有基于划分的聚类、基于层次的聚类、基于密度的聚类，基于图论的聚类等[2，3]。K-means[4]算法是经典的基于划分的聚类算法，但是需要人工输入聚类的簇个数，并且对非球形的数据聚类效果不好。基于密度的聚类算法例如DBSCAN[5]，该算法需要人工输入两个参数，半径和半径内样本点数量阈值，DBSCAN算法遇到数据集样本点分布密度差距较大的情况时聚类效果较差，DBSCAN算法的时间复杂度为O（n2），当数据集规模较大时所消耗的计算资源非常大。2014年6月，Rodriguez等人在Science上发表的DPC[6]算法（《Clustering by fast search and find of density peaks》）为聚类算法的设计提供了一种新的思路。DPC算法基于两个假设，第一簇中心拥有最大局部密度，第二两个簇中心距离较远。DPC算法能够适应任意形状的类簇，自动获取数据集中密度峰值样本点。

近几年，随着DPC算法研究的深入，有大量针对该算法的优化和改进。谢娟英等人[7]提出了基于K近邻优化的KNN-DPC算法，该算法基于样本点的K个最近邻样本点信息，计算样本点的密度，然后在分配非簇中心时，按照K近邻关系逐个分配。纪霞等人[8]通过相似度函数，找出每个点的K近邻，然后根据K近邻信息判断样本点的指向是否正确，从而可以有效减少错误分配。

DPC算法也存在着不足，对于紧密聚集的团形簇，DPC算法对于簇间共享的样本点分配存在误判，针对这一问题提出高斯判别优化的密度峰值聚类算法（Density Peak  Clustering algorithm based on Gaussian kernel optimization， Gauss-DPC）。Gauss-DPC算法从样本分布频率的角度对光晕点进行分配。

2密度峰值聚类算法

DPC算法有一个需要人工设置的参数截断距离[dc]，数据集中的样本点以[dc]为半径计算局部密度。DPC算法使用[dc]来计算两个关键参数，局部密度[ρ]和高局部密度最小距离[δ]。DPC算法将簇间共享的样本点命名为光晕点，光晕点的具体定义为：如果样本点[i]的截断距离半径之内存在一个样本[j]与[i]属于不同簇，则称点[i]为光晕点。

密度峰值聚类算法的聚类过程的创新之处在于簇中心的获取，在得到每个样本点的局部密度[ρi]和高局部密度最小距离[δi]后，以[ρ]为x轴，[δ]为y轴构造决策图，使用决策图辅助选取密度峰值点，也即簇的中心。在获取簇中心之后，将每个样本点指向比自身密度更高且最近的样本点，通过这种逐层迭代的方法分配非簇中心点。

3高斯核优化的密度峰值聚类算法

DPC算法的优势在于通过构建决策图可以快速确定簇中心，但是DPC算法单一的样本点分配策略对于簇间光晕点分配和噪音点识别存在不足。本文提出的Gauss-DPC算法将簇内样本点分布转化为点到簇中心的距离，通过计算距离的统计信息构建高斯判别式，利用高斯判别式改善了原DPC算法的不足。

3.1高斯判别式相关定义

本节将介绍高斯判别式的相关定义。

定义7  高斯约束系数（Gausslimit）

Gausslimit為人工输入可调参数，作用是用来判别低局部密度点的属性。将低密度点的样本簇内距离[dcen]和对应的簇内统计量代入高斯判别式，求出对应的值与Gausslimit进行对比来判断是簇边界还是噪音点。

3.2高斯判别式处理光晕点归属

结合3.1小节定义的簇内统计量的相关定义，本节将基于高斯核判别式应用到簇间光晕样本点归属的判断。

高斯判别式进行簇间光晕点归属判断的过程如下：取出光晕点距离两个簇中心的距离，分别代入两个局部核心簇的高斯判别式（公式4）;对比两个高斯判别式值的大小，将光晕点归入高斯判别式值大的那个簇。高斯判别过程模型如图1所示。

3.3簇边界点和噪音点判断

在高斯判别式的基础之上引入高斯约束来区分簇边界点和噪声点。首先通过稀疏局部密度阈值[ρlimit]筛选出可能为噪音的样本点，然而低密度点可能是簇边界点或者少量聚集的噪音点，虽然为密度相近的密度低点，但是边界点的簇内距离[dcen]显然比少量聚集的噪音点的簇内距离[dcen]要小;然后利用高斯判别式，将低密度点的簇内距离[dcen]代入到高斯判别式，边界点对应的高斯判别式值要大于噪音点对应的高斯判别式值。再将计算出来的高斯判别式的值和高斯约束的值进行对比，小于高斯约束值的样本点判定为噪音点。

3.4Gauss-DPC算法

Gauss-DPC算法首先通过引入簇内统计量的概念，对DPC算法输出的每一个簇独立构建高斯判别式，以此来处理簇间归属有争议的光晕点。然后引入稀疏局部密度阈值率，将可能是噪音点的低密度样本点筛选出来;最后通过高斯约束系数，再次利用高斯判别式将低密度样本点分为边界点和噪音点。Gauss-DPC算法流程如表1所示。

Gauss-DPC算法流程图如图2所示。

4实验分析

为验证Gauss-DPC算法的效果，实验用到3个数据集进行对比实验，数据集相关信息见表2。

R15数据集是有15個团形簇的数据集，由图3（a）可得Gauss-DPC算法可以精准地识别出离群点。图3（b）为 DPC算法的聚类结果，可以看出DPC算法虽然正确的聚类，但是对噪音点的识别不可控。图3（c） DBSCAN算法聚类结果，DBSCAN可以正确聚类，但是为了得到正确聚类结果需要经过多次反复调参。由图3（d）可知K-means算法对于稀疏的团形簇聚类效果较好。

D31数据集为31个复杂团形簇聚集的数据集。由图3（a）可以看出Gauss-DPC算法对比复杂地聚集在一起的团形数据集可以准确地聚类，同时还可以精准地对噪音进行识别。图3（b）为DPC算法聚类结果，DPC算法对于紧密聚在一起的簇存在严重的簇边界误判情况。图3（d）为DBSCAN算法的聚类结果，DBSCAN算法无法区分紧密聚集在一起的簇。由图3（d）可以看出，对于复杂的团形簇K-means算法对于簇边界点有明显的错误分类。

Aggregation数据集是典型的不规则的团形簇，一共有由7个簇，Gauss-DPC，DPC，DNSCAN算法均能正确的得到7个簇的聚类结果，但是由图5（b）和5（c）可知DPC算法和DBSCAN算法将部分粗边界点判断为噪音点。由图5（a）可知Gauss-DPC算法对于簇边界可以正确的判断，对于簇边界点误判的噪音点，可以通过高斯约束参数作为修正，将误判为噪音的样本点修正为相应的簇内样本点。由图5（d）可知K-means算法将一个大型簇一分为二，可见周围小型簇对于整体的聚类效果会发生影响。

综上Gauss-DPC算法可对簇间光晕点根据簇内密度进行自适应划分，通过调节低密度阈值和高斯约束两个参数，实现对簇边界的约束，经过对DPC算法聚类结果的两次修正，提升聚类结果的准确率。尽管Gauss-DPC算法对于部分数据集上聚类效果不佳，但是得益于Gauss-DPC算法样本自身分布统计信息对交叉样本进行分类，在大部分数据集上表现较优，体现了较强的适应性。

5结束语

本文提出了基于高斯核优化的密度峰值聚类算法，从频率分布的思想进行判别簇间样本点归属，以及判断簇边界和噪音点的判断。通过实验，将Gauss-DPC与DPC，DBSCAN，K-means进行对比，证明了Gauss-DPC算法有更好的聚类结果。Gauss-DPC算法引入了低密度阈值和高斯约束两个可调参数，实现了根据数据特征和实际应用的需求对簇的边界范围进行控制。

参考文献：

[1] 乔少杰，韩楠，张凯峰.复杂网络大数据中重叠社区检测算法[J].软件学报，2017，28（3）：631-647.

[2] 谢娟英，丁丽娟. 基于谱聚类的无监督特征选择算法[J]. 软件学报，2020，31（4）：1009-1024

[3] 陈叶旺，申莲莲，钟才明，等.密度峰值聚类算法综述[J].计算机研究与发展，2020，57（2）：378-394.

[4] MacQueenJ. Some Methods for Classification and Analysis of MultiVariate Observations[C].Proc of Berkeley Symposium on Mathematical Statistics & Probability， 1965.

[5] Ester M， Kriegel H P. A density-based algorithm for discovering clusters in large spatial databases with noise[C]. Proceedings of the second International Conference on Knowledge Discovery and Data Mining， 1996， 96（34）： 226-231.

[6] Rodriguez A，Laio A.Clustering by fast search and find of density peaks[J].Science，2014，344（6191）：1492-1496.

[7] 谢娟英，高红超，谢维信.K近邻优化的密度峰值快速搜索聚类算法[J].中国科学：信息科学，2016，46（2）：258-280.

[8] 纪霞，张涛，朱建磊，等.近邻密度分布优化样本分配的改进DPC聚类算法[J].华南理工大学学报（自然科学版），2019，47（2）：98-105.

【通联编辑：唐一东】