基于二阶k 近邻的密度峰值聚类算法研究

2021-08-07王大刚丁世飞

计算机与生活 2021年8期

王大刚，丁世飞，钟锦

1.中国矿业大学计算机科学与技术学院，江苏徐州 221116

2.合肥师范学院计算机学院，合肥 230601

聚类分析是用于模式识别和数据挖掘领域研究中的一个重要方法。20 世纪60 年代，最早的层次聚类算法[1]诞生，随后一大批聚类算法被相继提出，Kmeans[2]、谱聚类[3]、DBSCAN（density-based spatial clustering of applications with noise）[4]等常用经典算法一直沿用至今。根据文献[5]中的研究观点，现有的聚类算法大致可以分为[6-9]层次聚类、网格聚类、密度聚类、图模型聚类、划分聚类、代表点聚类、模型聚类共七大类方法。聚类算法在社交网络、舆情研究、图像识别、深度学习等领域有着广泛应用。

2014 年Rodriguez 等人[10]提出的密度峰值算法引起了学术界研究的一次新的研究热潮，算法通过定义局部密度和相对距离快速定位聚类中心，能够比较快速和高效地得到满意的聚类结果。尽管如此，算法仍然存在比较明显的缺点。DPC（clustering by fast search and find of density peaks）算法在计算局部密度时采用固定的截断距离，对节点周围的节点数据简单计数，针对密度有很大差异的数据集很难做出准确识别，不具备很好的鲁棒性。另外算法得到聚类中心后，通过单一的分配步骤，把非中心节点分配给相应的聚类中心点，分配过程一旦出错，会导致后续错误的层层传递。针对这些固有问题，学者们提出了一大批改进算法。

传统DPC 算法利用欧几里德距离计算节点之间相似度，对于非均匀和高维数据，无法得到满意结果。丁世飞等人[11]提出基于不相似性度量优化的密度峰值聚类，考虑节点周围的分布情况，用概率块重新度量节点的相似性，在不均匀数据和高维数据上有较好的识别精度。Du 等人[12]从提升算法鲁棒性角度，将k近邻（k-nearest neighbor，KNN）思想引入DPC，结合主成分分析，提出DPC-KNN 算法。该算法基于k近邻的概念取代原始算法中固定的截断距离，从对固定距离的计算转化为节点周围节点数的计算，对不同密度的数据集具有很好的鲁棒性和精度提升。同样基于近邻思想，Liu 等人[13]结合增强版的SNN（shared-nearest-neighbor-based clustering）近邻原理，结合两步骤的分配方案，提出SNNDPC 算法。算法提出共享距离概念，把节点共享邻居情况作为节点间相似性的度量方式，进而改进局部密度的计算方式。在此基础上，又定义了两种策略的非中心分配方案，算法对变化密度和分布不规则数据集有一定的优越性。Xie 等人[14]提出FDPC（fuzzy weightedk-nearest neighbors density peak clustering）算法，算法用节点间的距离衡量节点间的相似性，然后利用相似性定义节点属于某个簇的概率大小。利用这个概率，同样结合多步骤的分配策略对节点进行聚类，算法取得了比较满意的效果。文献[15-16]结合近邻和密度的概念，提出结合重力度量的密度聚类（clustering approach based on density peaks clustering and a modified gravitational search algorithm，GSA-DPC）算法。算法充分利用近邻思想的优点，结合密度指标，重新确定集群中心的候选者，取得比较好的准确性和计算效率。此外研究者还借鉴其他领域中的思想，比如生物进化、物理学优化等概念结合密度峰值聚类，提出改进算法[17-18]。Yang等人[19]提出LDPC（Laplacian centrality peaks clustering algorithm）算法，把数据集用带权重的有向图进行刻画，利用类似谱聚类中拉普拉斯矩阵的概念来度量原来的局部密度，算法消除了原始DPC 算法对固定参数的依赖，取得了比较高的鲁棒性和正确率。上述算法在对原有算法改进的过程中，基本出发点就是对局部密度的度量引入其他更多的信息，试图更加准确地表达节点的局部密度。从现有文献来看，相当数量的文献都是把k近邻思想引入原算法，从对原来固定距离的度量上升到对周围节点个数多少的度量，一定程度上提高了算法的鲁棒性，但都忽视了节点周围的具体局部网络分布结构对节点密度的实际影响，导致仍然无法度量节点的实际密度。

考察到节点的邻居和邻居周围节点间连接的综合影响，本文提出一种折中的局部密度度量方法，称为二阶k近邻密度峰值聚类。算法认为节点的综合密度应该由两部分构成，直观上来看，一方面k近邻提供直接密度，直接密度由节点周围直接相连的节点数来直接反映，另一方面由次k近邻与周围的节点提供间接密度，间接密度衡量节点邻居周围的网络拓扑分布，反映了邻居间的相互影响和相互关系。二阶k近邻思想可以总结为从最近邻居节点的范围扩大到了最近邻和次近邻节点构成的集合，其本质是对节点中心性度量的进阶，将节点的影响力在扩散中所发挥的作用进一步凝聚，对节点的影响力衡量更为准确，核心假设则是认为当一个节点u所连接的邻居与该邻居节点所处的局部网络中的其他节点连接更为紧密时，邻居节点扩散信息的能力更强，将邻居节点的扩散能力相叠加累计作为衡量节点u密度大小的重要因素。在此基础上重新定义密度聚类算法。实验验证本文算法有效性，且在精度和正确性方面具有一定的优势。

1 密度峰值聚类算法的基本原理

密度峰值聚类基本思想基于两个基本假设：聚类中心之间的相对距离较远，聚类中心的局部密度大于其周围非中心点的局部密度。算法定义数据集X={x1,x2,…,xn}，首先利用欧几里德距离dij定义节点之间的相似度，然后构造相似度矩阵D=[d1,d2,…,dn]T∈Rn×n，在此基础上，利用式（1）、式（2）度量节点的局部密度。其中dc称为截断距离，该公式用于统计节点i周围不超过截断距离的节点个数。

当数据集为小规模数据集时，可用高斯函数来计算：

与此同时，式（3）定义相对距离δi表示局部密度大于xi节点且距离最近点的距离，如果xi节点本身为密度最大节点，则定义为式（4）：

DPC 算法根据计算出的局部密度ρi和相对距离δi，绘制决策图，如图1 所示。根据二维决策图标识具有较高ρi和δi的点作为簇中心，然后利用单步骤的分配策略对非中心点进行分配，最后筛选出离群点，得到划分结果。

Fig.1 Decision diagram of density peak clustering algorithm图1 密度峰值聚类算法决策图

密度峰值聚类能够对各种形状的数据样本进行聚类，得到满意的效果，但是仍存在以下一些不足：

（1）截断距离dc考虑的是数据的全局分布信息，忽略节点周围的局部分布情况，针对密度变化较大的数据集有非常大的敏感性和较差的计算精度。如图2 是采用不同截断距离在完全相同数据集flame 上的表现，可以看到原始算法不具有较好的鲁棒性。

（2）算法在得到簇中心节点后，非中心点分配采用标准统一的、单次的策略，对个别发生错误的节点很难有机会进行纠正，容错性较差。

2 基于二阶k 近邻的密度峰值聚类算法

2.1 局部密度的定义

Fig.2 Performance of different dc on same data set图2 不同的截断距离dc 在相同数据集上的表现

通过上文分析知道局部密度的计算对确定聚类中心非常重要，为了提高局部密度的计算精度，本文考虑节点的二阶k近邻，从现有文献中普遍采用的k近邻度量扩大和扩展到由k近邻和次k近邻节点所构成的节点集合，新的集合可以看作一个局部的网络结构，其本质是节点中心性度量的进阶，用周围的节点和周围节点所构成的局部结构关系来描述中心节点，从而使得节点的密度度量更为准确和接近实际。为了便于后面算法的展开说明，给出如下定义和描述：

定义1（二阶k近邻）用Γ1(u)表示节点u的k-近邻，用Γ2(u)表示节点u的二阶k近邻，Γ2(u)={u′∈Γ1(v)|v∈Γ1(u)}，在此基础上有式（5）、式（6）成立：

其中，Q(u)表示节点u的二阶近邻的数量；C(v)表示节点v的k近邻数量；N(w)表示节点w集合的大小。

密度峰值聚类其中的一个基本假设就是用节点周围一定范围内的节点数量来定义其密度，但这不足以表征足够的信息。本文同时考察节点一定范围内节点数量和节点的分布质量来综合度量密度。为此将节点密度的度量分为两部分：一部分由节点周围的相似度较大的节点近邻提供直接密度；另一部分由二阶k近邻节点集中不包含直接近邻的部分来提供间接密度。

Fig.3 Data distribution diagram图3 数据分布示意图

如图3 所示，在k近邻取值为5 的情况下，节点1的Γ1(1)={2,3,4,5,6}共5 个节点，而Γ2(1)={1,4,12,13,3,2,6,7,16,14,15,5,7,17,}共14 个节点，在考虑衡量节点1 的密度时，可以看到节点5 周围的密度比其他节点的密度要高，但是距离节点1 较远，节点1 和节点5在k=5 的情况下并不互为k近邻，其周围的密度无法为节点1 提供直接的聚类密度，在考虑近邻用直接距离度量的算法中可能会被忽略。但同时可以关注到节点1 和节点5 在k=5 的情况下互为二阶k近邻。通过二阶k近邻和计算出来的节点一部分是包含在k近邻节点当中，这部分节点反映了邻居的邻居节点也是邻居的现象，说明这部分节点紧密围绕在节点周围，为节点贡献了直接的密度度量，而其余节点则提供某种程度的间接度量，相当于动态引入了一个截断距离，根据实际的数据点的分布情况来衡量。社交网络中使用节点的度[20-21]作为衡量节点之间相互影响力大小的指标，借鉴相关的概念，本文中节点对其他节点的密度的影响认为可以通过距离来产生，因此为了衡量节点对其他节点密度的影响力大小，本文给出如下定义：

定义2（直接密度）提供直接密度的节点属于中心节点的k近邻节点，且连接较为紧密的节点，定义集合C1(u)，有C1(u)=Γ1(u)⋂Γ2(u)，直观上理解，提供直接密度的是这样一些节点：是自己的邻居，同时邻居的邻居也是自己的邻居。在此基础上定义直接密度计算公式（7），表示为d(u)，该公式用节点的C1集合中节点集的距离和的倒数来表达节点的直接密度。

定义3（间接密度）对于某数据集的节点，属于某个节点的k近邻节点和二阶k近邻节点集合，但是计算节点连接不够紧密的集合定义为C2(u)，对那些节点邻居的邻居并不是自己的邻居的节点，有定义C2(u)=Γ1(u)⋃Γ2(u)-C1(u)，用C2集合来计算间接密度，在此基础上定义间接密度公式（8），公式用C2集合中距离的平方和的倒数与C2集合数量的乘积表达，计为i(u)。

在上述定义的基础上，本文为直接密度节点和间接密度节点分配一个比例系数α，根据文献[20]中实验的建议，实验中α取0.7 是一个适中的取值，那么可以定义节点的混合密度度量公式用于取代原始的密度公式ρ(u)。

从直观上解释，综合考虑直接密度和间接密度关系的局部密度公式在近邻数k确定的情况下，不增加其他多余的参数，既考虑到了近邻的数量，又考虑到了近邻周围的分布情况对密度的影响，使得算法适应数据集不同密度和形状的变化，具备很好的鲁棒性，后面通过实验验证算法的有效性。

2.2 粗调与细调结合的分配策略

工程上最常用的复杂系统的调优策略就是一种粗调到细调的过程性多步骤思路，即先大再小，先粗再细。传统的密度峰值聚类算法在计算相对距离的同时，根据局部密度大小从高到低排序，一边计算相对距离，一边在密度已排序的基础上根据相对距离更新簇标记。本质上是一种单步的分配策略，最大的问题就是如果有个别节点分配出错，导致错误会一步一步传递下去，从而影响相关节点分配的正确性。本文在二阶k近邻概念的基础上提出多步骤且逐步细化的分配策略。其特点是原算法的连续分配过程分解成在迭代过程中多阶段完成，一个节点的分配结果对另外节点归属关系造成的影响的可能性被降低。一个距离中心点较远或者密度较弱的节点会经历粗调、细调和最后判断三个阶段才会最终确定，最大程度上调高算法的容错性和准确性。主要步骤包括首先确定中心节点周围的连接比较紧密的非中心点，然后分配次要的非中心点，在前面两个步骤的基础上不断递归迭代，最后利用传统的密度峰值聚类分配策略确定剩下的所有节点的归属关系。

第一步粗调，从筛选密度较大节点开始，首先在k近邻内考虑为节点提供直接密度的集合C1(u)，算法迭代首次从中心节点开始对每个中心节点的所有直接密度节点集合直接标记所属簇中心的簇标记，同时将所有的中心点的周围直接密度节点放入队列p中，分配策略接着进行细调，通过计算平均距离du，考虑每个中心点的二阶k近邻集合，定义式（10）：

对二阶k近邻集合中所有距离不超过平均距离du的节点标注簇标记，同时将集合C2(u)中的相应节点也放入p队列的末尾，广度优先搜索遍历队列p，对p中元素完成从粗调到细调的步骤，直到数据集中所有数据遍历结束。最后把所有未标注节点归于密度高于当前点的最近一类，完成所有节点标注。非中心点的分配的算法的伪代码描述如下。

算法1非中心点分配伪代码

输入：数据中心点集合C{c1,c2,…,cm},k，距离矩阵D。

2.3 SODPC算法整体描述和时间复杂度分析

原始DPC 算法在计算相对距离时，同时判断节点的归属关系，本文算法把归属关系步骤放到算法的后期进行，在算法1 的基础上，结合原始的密度峰值聚类算法，通过多步骤的分配方案对非中心节点聚类。SODPC（optimized density peaks clustering algorithm based on second-orderkneighbors）算法的伪代码如算法2 描述。

算法2SODPC 聚类算法

输入：数据集X,近邻数k，比例系数α。

输出：聚类结果C′{C1,C2,…,Cm}。

1.初始化数据集X={x1,x2,…,xn}。

2.对X中每个节点分别利用式（7）和式（8）计算直接密度和间接密度，在此基础上利用式（9）计算局部密度ρi，利用式（3）计算相对距离δi。

3.根据γi=ρi×δi计算决策图，定义γi大值作为聚类中心，所选中心集合构成C{c1,c2,…,cm}。

4.调用算法1 完成非中心分配。

5.把所有未标注节点归于密度高于当前点的最近一类，完成所有节点标注。

6.输出数据划分结果。

SODPC 算法几个主要部分的时间复杂度如下：（1）算法2 计算每个数据点之间的距离矩阵需要O(n2)，排序需要O(n2)时间复杂度。这部分开销与原始DPC 是相同的。（2）算法1 中局部密度的计算，需要搜索k近邻和二阶k近邻,需要遍历节点队列p的时间为O(n)，每个节点需要在二阶k近邻内比较距离和分配，总时间复杂度为O(2kn2)。原始DPC 是在密度排序的基础上，边计算距离，边分配节点，总复杂度是O(n2)。（3）剩下节点的归属操作总时间复杂度为O(n) 。由上述分析看出SODPC 总时间复杂度为O(2kn2)，而原始DPC 算法的时间复杂度为O(n2)。由于实验中采用的节点的近邻数k都在个位，而n是数据集节点个数，k≪n,在实际的数据集上运行并没有非常明显的时间差距。

3 实验结果与实验分析

3.1 实验数据集与评价指标

实验选择6 个人工合成数据集和6 个来自UCI上的真实数据集进行实验，数据集的具体属性分别如表1 和表2 所示。

Table 1 Artificial data sets表1 人工数据集

Table 2 UCI data sets表2 UCI数据集

在所有基准数据集上比较聚类算法的ACC（accuracy）、NMI（normalized mutual information）和F-M（F-measure）的相应参数和实验结果。评价指标值越大，聚类结果的质量越好。聚类精度ACC 代表正确的聚类样本数与总样本数之比，表示聚类结果的质量。F-M 度量是精度和召回率的加权谐波均值，它表示聚类解决方案与数据集的真实分类标签之间的匹配程度。NMI 量化了聚类结果和已知类别标签之间的匹配程度，从而衡量了聚类算法的鲁棒性。

3.2 算法实验结果分析

分别在上述数据集上选择DPC、SNNDPC、LDPC和本文的SODPC 进行比较。SNNDPC 基于k近邻思想，同时考虑更新局部密度和分配策略，LDPC 把数据集转化为有向图，利用图论知识，对局部密度重新定义。根据相应原文中对算法的描述信息，相关参数分别设置为：原始DPC 参数设置为2.0 到3.8 取值；SNNDPC算法的k值从3到10手动取值，重复实验。

根据实验结果有如下结论:针对fourlines 和Gauss_data 数据集，数据的分布密度均匀，数据分布规则且简单，从图4 和图5 可以看出除了DPC 算法，本文算法和其他两种算法都有比较好的识别结果。针对multiscale 数据集，从图6 上可以看出，本文算法、LDPC 有正确的结果，但是原始的DPC 利用统一的截断距离，且采用单一的分配原则，不能对密度不均匀和不规则数据集识别。另外，虽然LDPC 能够给出正确的识别，但是从算法的执行效率上来看，在本文的人工小数据规模上，平均执行时间都在1 s 以上，算法复杂度高于其他所有对比算法，因此并不适合大规模聚类识别。从图6 上看出，DPC 算法未能给出multiscale 数据集较好的识别结果。图7 和图8 分别给出了算法针对数据集twocircles 和twomoons 的识别情况，可以看出本文算法和SNNDPC（twocircles 和twomoons 数据集上k值分别为3 和7 时为最佳结果）能够做出正确识别，而LDPC 以及DCP 算法未能给出较好的聚类，针对twocircles 和twomoons 这种不规则的数据，识别情况不尽如人意。最后从图9 上看出，本文和LDPC 能够对twospirals 数据做出正确识别，而其他两种算法未能给出正确结果。从上述分析看出，本文算法考虑到从密度和分配策略两个角度同时改进，能够在各种形状不规则、不均匀的数据集上有比较好的识别结果，而且本文算法相比原始的DPC 算法有更好的鲁棒性。进一步通过具体指标做分析，需要手动调试，多次运行，计算并统计ACC、NMI 和F-M 指标和平均执行时间，利用所有结果的平均值表示最终结果，如表3 和表4 所示。

Fig.4 Renderings of fourlines data set图4 fourlines数据集的效果图

Fig.5 Renderings of Gauss_data data set图5 Gauss_data 数据集的效果图

Fig.6 Renderings of multiscale data set图6 multiscale数据集的效果图

Fig.7 Renderings of twomoons data set图7 twomoons数据集的效果图

Fig.8 Renderings of twocircles data set图8 twocircles数据集的效果图

Fig.9 Renderings of twospirals data set图9 twospirals数据集的效果图

Table 3 Performance on synthetic data set表3 人工数据集上的性能表现

Table 4 Performance on UCI data set表4 UCI数据集上的性能表现

从表3 和表4 的结果可以看出，算法在人工数据和实际数据上的运行结果和执行时间大体是吻合的，LDPC 在人工和实际数据上运行时间最慢。在Sonar和Segmentation 数据集上，在整体表现都欠佳情况下，SODPC 算法仍然能够给出比较理想的结果。在人工数据集twospirals 和实际数据集Pen-Based 上，在各个性能上的表现都是最好的，可以看出算法能够适应复杂的数据分布和多属性大数据量情况下的聚类任务。整体来看，SODPC 在不同数据集上的运行能够保持在一个比较理想的性能表现。为了测试本文算法对于k值的敏感性，本文算法k值分别从3 取到7，DPC 的截断参数从2.0%到4.0%，测试并对比两算法在相同数据集Iris上的聚类准确度。

从表5 可以看出，本文算法在Iris 上的平均准确率达到0.94 左右，而且不同的k值对算法的影响较小，算法结果的波动不大，具备较好的鲁棒性。

4 结束语

本文提出了一种基于节点二阶k近邻的密度峰值聚类算法，引入节点的二阶k近邻，计算直接密度和间接密度，并重新定义局部密度的计算方式。在此基础上，定义非中心节点的分配策略。算法利用统一的度量值，避免了参数的选择问题，提高了算法的鲁棒性，二阶k近邻的计算同时考虑了节点近邻的数量和近邻之间的关系，提高了算法的精度，从理论和实验上证明了本文算法在同类算法中有较好的表现。下一步工作需要研究针对各种空间下复杂形状数据集聚类，以及探索如何保证算法有效性的情况下让算法的复杂度进一步降低，以便用于在大数据环境下的实际应用场合。