共享K近邻和多分配策略的密度峰值聚类算法

张新元，贠卫国

(西安建筑科技大学 信息与控制工程学院，西安 710055)

1 引 言

数据挖掘领域中，聚类分析[1]是非常重要的一个手段.它利用一定规则将数据划分成不同簇，同一簇下的对象具有一定的相似性，而不同簇下的对象差异性较大[2].现如今聚类已经在商业、计算机应用、生物技术、图像分割等领域被应用.

经典的聚类算法主要有k均值聚类算法(K-means)[3]，该算法简单有效，尤其在凸类数据上有非常不错的表现，FCM(Fuzzy C-means)[4]通过引入模糊性建立了样本的隶属不确定性，该算法在多种数据上仍有不错的表现.另还有AP(Affinity Propagation)算法[5]，DBSCAN(Density-Based Algorithm For Discovering Clusters in Large Spatial Databases With Noise)算法[6]，均简单有效且被广泛使用，但仍有较大改进空间.

Alex等[7]提出一种快速搜索和寻找密度峰值的聚类算法，简称DPC(Density Peaks Clustering).DPC能够快速找到聚类中心点，对非聚类中心点按照密度与距离的思想完成分配，能够取得不错的效果.但仍存在不足，主要体现在：1)局部密度定义仅考虑距离属性且对于低维数据和高维数据采取的密度定义不同，算法的通用性不强；2)对非聚类中心点的一次分配策略易导致一步错、步步错的现象，降低算法的效果.近年来，多位学者都对DPC算法的不足提出了不同的解决方法.纪霞[8]等通过距离矩阵将样本点映射到相对邻域来获取局部密度，对相对距离执行剪枝策略，仅需考虑近邻之间的距离，提出的RN-DPC(Relative Neighborhood And Pruning Strategy Optimized Density Peaks Clustering Algorithm)算法增强了聚类的效率.Du[9]等通过考虑样本的K近邻提出了能够反映样本点空间结构特点的局部密度计算方法，所提出的DPC-KNN(Density Peaks Clustering Based On K-Nearest Neighbors)算法考虑到样本点空间结构，避免了簇丢失的问题，Rui[10]等人通过共享近邻个数，重新定义了局部密度以及相对距离的计算，并对分配策略采用共享近邻数的二次分配方法，提出的SNN-DPC(Shared-nearest-neighbor-based clustering by fast search and find of density peaks)算法有效提升了聚类性能.赵嘉[11]等引入样本的邻域思想计算局部密度，并定义了邻近度的度量规则，提出一种考虑近邻度的分配策略.所提出的DPC-MND(Density Peaks Clustering Based on Mutual Neighbor Degree)算法综合了数据全局与局部特征，聚类性能优越.吴辰文[12]等提出IA-DPC(Density Peak Clustering Algorithm for Improved Node Aggregation)算法，采用节点凝聚度思想，引入加权完成图和建立新的评价函数来选择聚类中心，IA-DPC可有效选择正确聚类中心.

本文提出一种共享K近邻和多分配策略的密度峰值聚类算法(SKM-DPC).其主要思想是将共享近邻距离引入数据点的相似性度量中，基于放大因子定义了局部密度计算方式，并对分配策略进行优化.在12个数据集上的测试验证了该算法能够较好的捕捉聚类准确性.本文的贡献包括：

1)用既能描述数据间距离特性和空间特性的共享邻域定义了数据间的相似性，解决了传统欧式距离度量相似性的不足.

2)定义了基于放大因子的数据点局部密度计算方法，扩大了聚类中心与非聚类中心在决策值图中的差异性，减少不必要的错误.

3)优化SNN-DPC算法的分配策略，对可能从属点的分配进行了限制，降低分配错误的风险.

2 相关工作

2.1 基础知识

定义1.(K近邻集合)计算数据集X中数据点xi与其他数据点距离并按照升序排列，第K个距离为distki，记录前K个距离的索引值，对应的数据点即为数据点xi的K近邻集合，数学定义如式(1)所示：

KNN(xi)={xj∈X|dij≤distki}

(1)

定义2.(共享近邻集合)数据点xi的K近邻集合为KNN(xi)，数据点xj的K近邻集合为KNN(xj)，则样本xi和xj的共享近邻集合的数学定义如式(2)所示：

SNN(xi，xj)=KNN(xi)∩KNN(xj)

(2)

2.2 DPC算法

DPC算法是一种基于密度与距离的聚类算法，基于两种假设：1)聚类中心周围的密度低；2)聚类中心间距离远.DPC通过局部密度ρi为横坐标，相对距离δi为纵坐标来得到决策图，并选取出聚类中心，最后基于ρi与δi对未分配点进行归类.

对于给定一个数据集Xi×j={x1；x2;x3;…;xi}，其中xi={xi1；xi2;xi3;…;xij}，共有i个数据点，j个数据点属性.DPC算法在计算局部密度时采用2种度量方式：截断核与高斯核.

截断核的局部密度计算见式(3)：

ρi=∑i≠jχ(dij-dc)

(3)

高斯核的局部密度计算见式(4)：

(4)

其中，若x<0，则χ(x)=1，反之x≥0，则χ(x)=0.其中，dij为数据点xi和xj的距离，dc为人为指定的截断距离.

当数据点xi局部密度最大时，相对距离见式(5)：

δi=maxi≠j(dij)

(5)

其余数据点的相对距离见式(6)：

δj=minj:ρj>ρi(dij)

(6)

截断核度量的局部密度指以截断距离为半径构成的圆中包含数据点的个数，高斯核度量的局部密度指全部数据点到该数据点的距离之和.

这是由于DPC认为密度最高的数据点之外的数据点不可能比其密度高，认定密度最高的点为聚类中心点.其余聚类中心点需满足局部密度ρi较高且相对距离δi较大.

DPC通过局部密度ρi与相对距离δi画出决策图来选取聚类中心.找到聚类中心后，将剩余未分配数据点分配给密度比其大且距离最近的簇.

2.3 DPC算法不足分析

DPC与其他密度聚类算法均有不足，表现为两方面：

1)局部密度的度量上未考虑数据点之间的空间特性，仅考虑数据点间距离特性，当多个簇之间的密度存在较大差异时，DPC不能很好的将同一簇数据点归类.实际上，对于小规模数据集采用的是高斯核度量局部密度，对于大规模数据集采用截断核度量局部密度.对于同一个数据集而言，分别采用两种度量方式的聚类结果是有较大差别的.

图1和图2展示的是DPC算法在Aggregation数据集上分别采用高斯核和截断核得到的聚类结果，清楚的看到在dc取值相同，即dc=2时，分别采用高斯核与截断核度量局部密度时，聚类效果是存在较大差别的.

图1 DPC算法采用高斯核在Aggregation上的聚类结果Fig.1 Gaussian kernel results of clustering using DPC on Aggregation

图2 DPC算法采用截断核在Aggregation上的聚类结果Fig.2 Cutoff kernel results of clustering using DPC on Aggregation

2)分配策略采用一站式策略，易发生连带错误，导致聚类结果不理想.DPC对于非聚类中心点的分配上，采用寻找密度比其高且距离最近的原则，这非常容易导致一个点分配错误，后续大多数点也分配错误.在环形数据集的表现更为明显.如图3所示，A、B、C 3个数据点为聚类中心点且为3个密度峰值点，Z为已分配给C点所属簇的数据点，在分配X点时，由于Z点和Y点都比X点的密度值大，X点到Z点的距离为b，X点到Y点的距离为a，由图很明显得出a>b，则X点按照DPC算法的分配策略会分配给Z所在簇，而实际上X点应当分配给A簇.由此引发X点至M点间的多个数据点错误的被归为C簇，这种原因不仅与DPC的分配策略有关，与其密度定义方法也有一定关系[13].

图3 DPC算法在Spiral的聚类结果Fig.3 Results of clustering using DPC on Spiral

2.4 SNN-DPC算法

SNN-DPC算法采用共享近邻的概念描述数据点的局部密度和相对距离，并定义了可能从属点与不可避免从属点，最后利用邻域信息完成聚类.

对于数据点xi和xj，xi的K近邻集合和xj的K近邻集合为这两个数据点的共享近邻集合，表示为SNN(xi,xj).相似度的计算见式(7)：

(7)

xi的局部密度定义为与xi相似度最高的K个相似度之和，计算公式见式(8)：

ρi=∑xj∈L(xi)Sim(xi，xj)

(8)

其中，L(xi)表示xi中相似度比较大的K个数据点的集合.其中K的取值同选择的近邻数K的取值.

在相对距离δ的计算中，SNN-DPC引入了距离最近的较大密度点的欧氏距离，并利用邻近距离增加了补偿机制，基于此原理低密度所在簇的数据点也可能具有比较大的相对距离δ.

当样本点xi局部密度最大，相对距离见式(9)：

δi=maxi≠j(dij)

(9)

其余样本点的相对距离见式(10)：

δi=minj:ρj>ρi[dij(∑p∈KNN(xi)dip+∑q∈KNN(xj)djp)]

(10)

通过构建局部密度为横轴，相对距离为距离的纵轴，便可获得聚类中心.

在SNN-DPC算法中，除聚类中心外的点被分成两部分，一部分被定义为不可避免的从属点，另一部分被定义为可能的从属点.

对于数据点xi和xj，当xi和xj的共享近邻点的个数为近邻数的一半时，SNN-DPC认为xi和xj是归属于同一簇的.数学定义见式(11)：

|{p|p∈KNN(xi)∩p∈KNN(xj)}|≥K/2

(11)

剩余未分配的数据点属于可能的从属点，数学定义表达见式(12)：

|{p|p∈KNN(xi)∩p∈KNN(xj)}|

(12)

根据式(11)来分配不可避免的从属点，对于分配剩下的可能的从属点，SNN-DPC利用邻域特点进一步确定可能的从属点的簇.

3 SKM-DPC算法

本文提出了一种共享K近邻和多分配策略的密度峰值聚类算法(SKM-DPC).SKM-DPC利用共享近邻距离度量数据点间的相似性，重新定义了局部密度的计算，优化了样本的二次分配策略，有效避免DPC算法未考虑数据间空间特性以及一步式分配问题.

3.1 局部密度

对于数据点xi和xj，其相似度计算由式(13)给出：

(13)

其中∑p∈SNN(xi,xj)(dip+djp)代表数据点xi和xj之间的共享近邻距离，反应数据的局部稀疏性.取值越大，分布越稀疏.取值越小，分布越密集.|SNN(xi,xj)|代表数据点xi和xj之间的共享近邻个数，共享近邻个数越多，数据点越相似.指数函数ex的作用为归一化相似度，避免取值过大造成量纲层面对后续密度计算的影响.

表1和表2分别给出SNN-DPC和SKM-DPC在Flame数据集上的相似度矩阵，聚类分析的目的是使同一簇的相似性更大，不同簇的差异性更大.表格的横纵坐标分别为Flame数据集的1～9号数据，其中1号和2号数据属于同一簇.3号～9号数据属于另一簇.由于本文算法SKM-DPC对相似度进行了归一化，故不做数量级上的对比.

SNN-DPC算法和SKM-DPC算法均能有效识别出同一簇的数据点，并没有产生两个不同簇的数据点存在相似度的异常现象.SNN-DPC算法计算1号与2号数据的相似度为16.9，计算3号与8号数据的相似度为59.7，计算3号与9号数据的相似度为46.1.而SKM-DPC算法计算1号与2号数据的相似度为0.71，3号与8号数据的相似度为0.89，3号与9号属于的相似度为0.89.1号和2号数据属于同一簇，3号和8号数据属于另一簇，则1号和2号的相似度与3号和8号的相似度应当尽可能高且接近，SNN-DPC中，1号与2号对比3号与8号，所计算出的相似度分别为16.9和59.7，同一簇的相似度差异性过大.而SKM-DPC计算出的相似度分别为0.71和0.88，同一簇的相似性更接近.SKM-DPC很好的度量出相似度.表2中，3号～9号数据间的相似度基本都稳定在0.88～0.91的区间内，满足同一簇的相似度相对较高且接近的特点.

表1 SNN-DPC计算的相似度Table 1 Similarity of SNN-DPC

表2 SKM-DPC计算的相似度Table 2 Similarity of SKM-DPC

数据点xi的局部密度为与xi相似度最高的K个相似度之和的r次方，其中r为放大因子.局部密度的计算由式(14)给出：

ρi=[∑xj∈L(xi)Sim(xi,xj)]r

(14)

其中，放大因子的讨论见3.2.1节.

3.2 聚类中心选择与分配策略

3.2.1 聚类中心选择

定义3.(决策值)局部密度ρi与相对距离δi的乘积定义为决策值，数学表达见式(15)：

γi=ρi·δi

(15)

聚类中心点与非聚类中心点的决策值γi在决策值图的分布是不同的，因此正确选择出聚类中心的前提是聚类中心点与非聚类中心点的决策值γi存在较大差异.大多改进措施按照决策图来选择聚类中心，本文依照局部密度和相对距离的乘积，即决策值图来选择聚类中心.这样做的好处在于避免了由于密度或者距离差异性不大时，无法准确选取出聚类中心的这一问题.决策值权衡了密度和距离分别的贡献，本文中放大了局部密度的值，对于相同的距离的两个数据点，局部密度的扩大势必导致决策值的差异性更大，有助于准确识别聚类中心.

Spiral数据集是3类数据集，需要在决策值图中选取3个点作为聚类中心点.如图4所示，图4(a)为SNN-DPC算法在Spiral数据集的决策值图，图4(b)为SKM-DPC算法在Spiral数据集的决策值图.区别在于2、3点的识别上，图4(a)中2、3点与后续点存在重叠现象，而图4(b)中的2、3点与后续点并无规律分布特点.

图4 SNN-DPC和SKM-DPC在Spiral和Jain上的决策值riFig.4 riof SNN-DPC and SKM-DPC on Spiral and Jain

Jain数据集是2类数据集，需要在决策值图中选取2个点作为聚类中心点.图4(c)为SNN-DPC算法在Jain数据集的决策值图，图4(d)为SKM-DPC算法在Jain数据集的决策值图.区别在于第3个点的识别上，图4(c)中第3个点既和1、2点呈规律分布，又和第4个点及之后的点呈近似规律分布.图4(d)中第3个点与第4个点及之后的点呈高度规律分布，而与第1、2点(聚类中心)并无规律性.这表明SKM-DPC算法在聚类中心点识别上更具优势.

无论是SNN-DPC算法还是SKM-DPC算法，都可以在Spiral和Jain数据集上正确选择出聚类中心，SKM-DPC算法在聚类中心与非聚类中心之间显示出更大的差异性，表明我们选择SKM-DPC算法可降低错误率.

放大因子r调整规则：

在实际应用里，放大因子r的取值应当控制在合理范围，r过大则会导致一些较大的非聚类中心决策值急剧增大，逼近聚类中心点的决策值.r过小又会导致聚类中心点和非聚类中心点的决策值差异性降低，无法达到理想聚类效果.根据实验，建议放大因子r的取值范围为r∈[2,5]，默认值取r=3，本文实验结果均是在r=3下得出.

3.2.2 分配策略

定义4.(近邻数可达)当数据点xi已分配给对应簇，数据点xj还未分配，当且仅当满足式(16)：

|{p|p∈KNN(xi)∩p∈KNN(xj)}|≥3K/4

(16)

认为数据点xj应当与数据点xi属同一簇.对于大多数数据集，各个簇之间交叉重叠部分为划分的难点，为了降低分配错误的风险，本文相比SNN-DPC算法提高了近邻数可达的条件，当且仅当两个数据点xi、xj间共享邻近个数大于等于3K/4时，才将其划分为同一簇.剩余未分配的数据点，考虑其近邻特性，按照SNN-DPC算法中不可避免从属点分配方法进行分配.本文算法SKM-DPC可以很好的刻画聚类分析中的不确定性，减小误差，从而提高聚类精度.

3.3 SKM-DPC算法步骤

算法1.SKM-DPC

输入：数据集X，近邻数K

输出：聚类结果C

1.归一化数据集

2.计算数据点间欧氏距离，根据式(1)计算样本点的K近邻集合.

3.根据式(13)计算样本点的相似度.

4.根据式(14)计算样本点的局部密度.

5.根据式(9)、式(10)计算样本点的相对距离.

6.根据式(15)计算样本点的决策值，根据决策值画出决策值图.

7.由决策值图选择出聚类中心点.

8.满足式(16)的数据点划分为同一簇.

9.不满足式(16)的数据点输入到SNN-DPC算法中，按照对不可避免从属点的分配方法进行划分.

10.输出聚类结果.

3.4 复杂度分析

本节分析中，认为数据点总数为n，簇数为m，近邻数为k.

3.4.1 时间复杂度

DPC算法的时间复杂度主要由计算距离、密度、相对距离组成，复杂度均为O(n2)，则DPC算法的总的时间复杂度为O(n2).

SNN-DPC算法的时间复杂度主要由距离、近邻、密度、相对距离、分配，总体复杂度为O((k+m)n2).

SKM-DPC算法的时间复杂度主要由以下5点构成：

1)计算数据点的欧氏距离矩阵O(n2).

2)由于SKM-DPC算法需要计算k个近邻，则计算局部密度为O(kn).

3)计算数据点的相对距离O(n2)

4)分配近邻可达点的复杂度为O(mn2)

5)分配剩余点的复杂度为O(kn2+mn2)

本文总的时间复杂度为O((k+m)n2)和SNN-DPC的复杂度O((k+m)n2)相同，但高于DPC算法的O(n2).由于近邻个数k和类簇个数m的取值偏小，相比于n来说可以忽略不计，不会对运行时长产生大的影响.

3.4.2 空间复杂度

DPC算法和SNN-DPC算法的空间复杂度均为O(n2).

SKM-DPC算法的空间复杂度主要由以下3点构成：

1)计算距离矩阵和相似度矩阵的空间复杂度为O(n2).

2)计算局部密度和相对距离的空间复杂度为O(n).

3)分配非聚类中心点的空间复杂度为O(mn).

本文总的空间复杂度为O(n2)，与DPC算法、SNN-DPC算法相同.

4 实验结果与分析

本文选取合成数据集与UCI真实数据集与对SKM-DPC性能进行评估，将实验结果与SNN-DPC、DPC-KNN、DPC，进行对比.对比算法均使用的是作者公开的源代码，其中DPC算法采用的是高斯核聚类.各算法的的参数均选择的最优值.

本文选用3个聚类评价指标：AMI(Adjusted Mutual Information)[14]、ARI(Adjusted Rand Index)[14]、FMI(Fowlkes Mallows Index)[15]，其中ARI的取值为[-1，1]，AMI和FMI的取值为[0，1]，取值越大，聚类性能越优.

实验环境：Intel(R)core(TM)i5-8300H CPU@2.3GHZ 2.30GHz处理器，机带RAM为8.00GB，操作系统为Windows10 64位.

4.1 人工合成数据集实验

本节选取8个合成数据集对SKM-DPC性能进行评估，数据集的信息见表3.

表3 合成数据集信息Table 3 Information of synthetic dataset

表4给出4种算法在8个合成数据集上的聚类评价指标值，分别为AMI、ARI、FMI.表中PAR为每个算法的最优参数值，黑体的结果表示同一个数据集下某项指标的最优值.

表4 各算法在合成数据集上的性能值Table 4 Performance indicators values of various algorithms on synthetic dataset

AlgorithmPathbasedSpiralAggregationR15AMIARIFMIPARAMIARIFMIPARAMIARIFMIPARAMIARIFMIPARSKM-DPC0.94820.96950.9797201.00001.00001.000050.99220.99560.9966270.99380.99280.993315SNN-DPC0.90010.92940.952991.00001.00001.000050.95000.95940.9681150.99380.99280.993310DPC-KNN0.52710.51720.7424100.49600.39770.615250.97400.98260.9864150.99070.98920.989917DPC0.49980.45300.658521.00001.00001.000020.99220.99560.99663.90.99380.99280.99330.6

PAR参数在不同算法中的具体值说明：在SKM-DPC算法、SNN-DPC算法、DPC-KNN算法中，PAR代表实验选取近邻的个数K值.DPC中，PAR代表截断距离dc值.

在Flame数据集上，我们发现SKM-DPC算法的各项指标值均略低于DPC.这现象的原因为： Flame数据集有2个类簇，整体呈现平衡性的分布特征.根据实验观察得出：SKM-DPC与DPC的聚类结果仅在一个数据点的划分上出现了区别，该数据点处于两个类簇的重叠区域，SKM-DPC未能将该数据点正确划分，而DPC正确划分了该数据点.SKM-DPC和DPC算法均能找到正确的聚类中心，对于未分配的数据点，DPC采用的是将其划分到密度比起高且距离最近的已分配数据点所在的类簇，这种分配策略简单高效，但易受数据点结构的影响，鲁棒性不强.SKM-DPC采用的是将其首先划分到与其共享近邻个数达到3K/4的已分配点所在类簇，如未满足条件将会根据该点的近邻分配情况来综合考量该数据点所属类簇.在本文实验中，SKM-DPC在绝大多数数据集的聚类鲁棒性均强于DPC.

图5和图6分别为SKM-DPC和SNN-DPC在6个数据集上的聚类结果，由于篇幅受限，故仅给出SKM-DPC和SNN-DPC的聚类结果.图5(a)和图6(a)是Jain的聚类结果，Jain数据集的特点是月牙状且密度不均.SKM-DPC的效果均优于其他算法，正确的找到密度峰值点且对剩余点正确划分，SNN-DPC算法导致下方月牙状数据中的一小部分被错误划分.图5(b)和图6(b)是Flame的聚类结果，SKM-DPC仅有1个数据点被划分错误，而SNN-DPC有多个数据点被划分错误.图5(c)和图6(c)是Spiral的聚类结果，SKM-DPC和SNN-DPC均能正确聚类该数据集.图5(d)和图6(d)是Aggregation的聚类结果，Aggregation数据集的特点是呈现7个堆状分布，有2堆存在交叉分布.SKM-DPC的聚类错误率最低，SNN-DPC聚类错误率稍大.图5(e)和图6(e)是S2的聚类结果，S2数据集的特点是15个类簇中每一簇都与其他至少一个类簇存在交叉分布.SKM-DPC的聚类效果最好，SNN-DPC次之.图5(f)和图6(f)是D31的聚类结果，D31具有较多的类簇个数，同时每个类簇都与其他至少一个类簇(大多数情况是3个)都有交叉重叠部分，交叉重叠部分的划分效果是展示算法优越性的体现.划分精度最高的是SKM-DPC算法，SNN-DPC算法略低.

4.2 真实数据集实验

本节在4个真实数据集上验证SKM-DPC算法和另3种算法的表现.真实数据集的信息见表5.

表6展示的是4种算法在4个真实数据集上的表现.从表6中可以看出，SKM-DPC算法的AMI、ARI、FMI指标均高于SNN-DPC、DPC-KNN、DPC算法.特别的，在ionnsphere数据集上，本文算法的AMI指标较DPC算法提高了22.12%.在waveform数据集上，本文算法的ARI指标较DPC算法提高了34.5%，较DPC-KNN算法ARI指标提高了40.24%.在wine数据集上，本文算法的FMI指标较DPC算法提高了16%.在seeds数据集上，本文算法的各项指标均比其他3个方法提高了至少2%.

图5 SKM-DPC在不同数据集的聚类结果Fig.5 Clustering results of SKM-DPC in different data sets

图6 SNN-DPC在不同数据集的聚类结果Fig.6 Clustering results of SNN-DPC in different data set

表5 真实数据集信息Table 5 Information of real dataset

表6 各算法在真实数据集上的性能值Table 6 Performance indicators values of various algorithms on real dataset

5 结 论

针对DPC算法的局部密度定义简单且无统一的度量方式以及单一分配策略易导致连错问题，本文提出一种共享K近邻和多分配策略的密度峰值聚类算法(SKM-DPC).SKM-DPC算法引入共享近邻距离来度量数据点间的相似性，增强了样本点与其近邻间的联系，解决了DPC算法的局部密度定义简单且无统一度量方式的问题.提出了基于放大因子优化的局部密度计算方式，扩大了聚类中心在决策值图中与非聚类中心点的差异性.优化了样本点的二次分配策略，相比DPC算法的单一分配策略，有效提升了聚类精度.在真实数据集以及人工数据集上的测试表明，SKM-DPC算法能够有效提高聚类精度，并能够很好的捕捉聚类的准确性.本文的实验结果虽较其他方法存在优势，但如何更准确的划分数据集中交叉重叠部分的所属簇是今后研究的难点.