基于KL散度的密度峰值聚类算法

丁志成，葛洪伟，周 竞

(1.江南大学 轻工过程先进控制教育部重点实验室，江苏 无锡 214122；2. 江南大学 物联网工程学院，江苏 无锡 214122)

0 引 言

聚类是根据某些特定的准则，通过在数据中发现的对象及其关系将未划分类的数据分割为不同的簇，令同一簇内数据点相似性尽可能大，同时不同簇间的数据点相似性尽可能小[1]的分析方法。聚类作为一种无先验知识的统计方法，能够分析数据的聚类属性、潜在结构以及数据存储容量[2-3]，是数据挖掘的重要分支[4]，如今其在模式识别、web搜索、人工智能、生物及航天等领域[5-6]已得到普遍推广和应用。

如今有许多优秀的算法被相继提出，其中最为典型的算法有基于划分的K-means[7]，K-medoids[8]聚类；基于网格的STING[9]聚类；基于层次的CURE[10]聚类以及基于密度的DBSCAN[11]，OPTICS[12]聚类算法。其中，密度聚类DBSCAN算法相较于基于划分和基于层次的聚类而言，具有无需事先确定生成簇的数量、可以探测拥有任何形状簇类的优点。算法对整个数据空间进行邻域搜索，能够有效识别正确的簇并且可以准确发现离群点。但DBSCAN也具有明显的缺陷：算法调用的是全局邻域值，对局部密度的变化趋势不能有效反映，无法有效处理密度不均匀的数据集且算法对输入参数十分敏感。尽管之后也提出过一些针对以上缺点的改进算法但许多缺陷仍无法避免。

2014年，Alex，Alessandro等提出了一种新的基于密度的聚类算法：快速搜索与发现密度峰值聚类(clustering by fast search and find of density peaks, DPC)[13]算法。DPC算法无需额外参数，通过决策图人工选取聚类中心后将其余数据点自动分配到相应聚类中心从而完成聚类。尽管DPC算法简单高效，却无法自动确定聚类中心，特别是选取一些特殊的密度峰值点时人工操作容易出现错误。针对这一缺点，本文拟通过引入新的聚类中心选择策略，提出一种基于KL散度的密度峰值聚类算法(density peaks clustering based on Kullback-Leibler divergence，KLDPC)。KLDPC算法可以根据KL散度的差异性度量准则赋予数据点一个新的Dkl值，并在Dkl排序图上通过拐点分辨出聚类中心点，从而自动确定聚类中心。实验证明， KLDPC提高了算法的准确率，摆脱了经验值影响及复杂的人工干预，可以获得更优的聚类效果。

1 DPC算法及其缺陷

DPC算法只需要一个输入参数，无需预先指定簇类数量，能够自动生成相应簇类并一步完成簇的分配。算法将满足下列条件的数据点定义为聚类中心点：被局部密度相对较低的数据点包围并且这些点距离其他拥有更高局部密度的点有相对较大的距离。

对于数据点Xi，计算局部密度ρi为以dc为半径的圆内其他数据点的数目

(1)

dc=dround(P·M)

(2)

(2)式中：di为任意点间的欧式距离升序排列的结果；P取值为(0,1)；M=N(N-1)/2，N为数据总数；round(·)函数表示对P·M四舍五入取整数值；dc为可调参数，在实验中调试P的值选取最佳聚类。

距离具有更大密度的点的最短距离δi定义为

δi=min(dij),j:ρj>ρi

(3)

具有全局最高密度的数据点，默认为聚类中心点，并令其δi=max(dij)。以下是DPC算法的具体步骤描述。

步骤1根据(1)式和(2)式，由对象数据集确定dc和所有数据点的局部密度ρi。

步骤2根据(3)式计算出所有点的δi并和ρi一起存储在相对应的记号中。

步骤3生成有关ρi和δi的关系决策图(decision graph)并手动选取聚类中心点。

步骤4将非聚类中心点分配到距离最近的聚类中心所属类簇中并计算边界区域密度。边界区域密度定义为归属某簇但与其余簇所属点间的间隔小于dc的点的数目。

步骤5对聚类结果进行除噪：将局部密度ρi高于边界区域密度的数据点视为所属簇的核心点，否则视为噪声点，完成聚类。

通过实验，我们发现DPC算法在面对以下情况时会产生较大误差。

1)由于原DPC算法同时考察ρ和δ值，只有2个参数值同时满足大于选取点时才会被选为聚类中心点。而事实上除了同时具有较大ρ和δ值的明显的密度峰值点，有一些具有较大ρ和较小δ值或是较小ρ和较大δ值的点也可能作为聚类中心，如图1所示，而这类数据点却被忽略，导致聚类中心点出现少选、漏选。

图1 DPC算法由决策图1a少选聚类中心Fig.1 DPC gets less clusters by decision graph 1a

2)因为仅关注ρ和δ值整体的大小，并没有研究参数值变化的趋势，也会在人工选取具有较多簇类中心的数据集时造成多选聚类中心的结果，导致同一个簇的点被错误地划分为多个簇，如图2所示。

图2 DPC算法由决策图2a多选聚类中心Fig.2 DPC gets more clusters by decision graph 2a

观察图2a可以发现，同时具有较大ρ和δ值的点有10个，而正确的簇类中心为7个，因此，通过人工选取并不能准确选取聚类真正的中心。而如果在选择聚类中心出现了错误，那么在接下来的数据点分配簇类上会产生连锁反应，最终使得聚类效果不理想。即便利用密度峰值算法的决策图选取到了正确的聚类中心，也是通过了大量的手动选取、反复对比所得到的理想状态下的最优效果，在工程应用中并无实际意义。

3)处理高维数据或数据量大的数据集时，更难以选择聚类中心，需要大量的尝试，并且因为DPC的选取原则，部分点会由于数据过密导致无法准确选取。

2 基于KL散度的密度峰值聚类算法

2.1 聚类中心选择策略

定义1γi为衡量点i是否为聚类中心点的参数，称之为中心指标，定义为

γi=ρi·δi

(4)

对于具有较大ρ或δ的聚类中心来说，γ值也具有较大值，因此，γ可作为判断数据点能否作为聚类中心的标准。记数据集为U(x)，数据点总数为N，排序图选取样本比例为Pγ，对γi进行降序排列，做前NP=[N·Pγ] 个数据点的γ排序图。对γ排序图进行实验可避免由于单独考察ρ或δ所带来的误差。

本文通过大量实验选用γ排序图的比例Pγ=4%作为经验值进行相关数据实验，不同聚类中心指标在数据集aggregation上的表现效果如图3所示。从图3a可看出，由于存在多个拐点，所以仅凭γ排序图很难区分出数据集的聚类中心点。通过观察可知，疑似聚类中心的数据点都有较高的相似度,而非聚类中心点的γ值数值较低且趋于一致。因此，本文拟用KL散度的概念对γ进行再处理以得到KL中心指标来确定正确的聚类中心。

图3 不同聚类中心指标在数据集aggregation上的 表现效果Fig.3 Effects of different central indexes for dataset aggregation

定义2KL中心指标为基于KL散度的参数指标，用于描述数据集点与其他点γ值的差异度之和，差异度越大，值越趋近于0。公式表示为

(5)

KL散度即相对熵[14]，原定义为在相同的事件空间中，2个概率分布P(x)，Q(x)的差异程度，得到的KL散度为概率分布中每个点的差异度累加值，值越大，差异越大。

(6)

由于同样是描述点集的数据相似度并且拥有一致的参数取值区间，本文在考察数据点是否为聚类中心时，选择运用此差异性度量准则加以判别。已知在概率分布间，通过KL散度能够对离散概率进行定量的计算。而将相对熵的差异性度量准则应用到点的分布上虽然无法定量计算，但通过实验证明，其依然可以满足对数据点是否为聚类中心的定性的划分。

(7)

在数据集中，仅有少数点是聚类中心点。所以对于聚类中心而言，多数与之差异度很大，因此，Dkl值较小；相反，非聚类中心点的Dkl值则很大。所以利用KL中心指标可以将两者清楚地划分，以便选取到正确的聚类中心。对于更多的数据集，γ排序图与Dkl排序图的对比效果如图4—图7所示。

图4 数据集spiral的γ排序图和Dkl排序图的对比 (维数为2，类别为3)Fig.4 Comparison of γ sorting graph and Dkl sorting graph on spiral with 2 dimensions and 3 clusters

图5 数据集wine的γ排序图和Dkl排序图的对比 (维数为15，类别为3)Fig.5 Comparison of γ sorting graph and Dkl sorting graph on wine with 15 dimensions and 3 clusters

图6 数据集seeds的γ排序图和Dkl排序图的对比 (维数为7，类别为3)Fig.6 Comparison of γ sorting graph and Dkl sorting graph on seeds with 7 dimensions and 3 clusters

由实验效果图可知，无论是在高维(数据集seeds，wine)还是在低维(数据集spiral，test)的处理上，使用KL中心指标的Dkl排序图总比γ排序图能获得更优的聚类效果，并且Dkl排序图上的聚类中心与其他点间存在一个Dkl值增长幅度最大的拐点cn，在此，可以引入该点作为KL中心指标的分界点。

定义3将Dkl排序图中位于拐点cn前的i个点称作候选聚类中心cci，满足条件

cci={i|i<=cn,i=1,2,…,NP}

cn={j|max(sj),j=2,3,…,NP-1}

(8)

图7 数据集test的γ排序图和Dkl排序图的对比 (维数为2，类别为3)Fig.7 Comparison of γ sorting graph and Dkl sorting graph on test with 2 dimensions and 3 clusters

2.2 KLDPC算法步骤

综上所述，KLDPC算法的具体步骤描述如下。

输入：实验数据集U(x)={x1,x2, …,xn}，数据点的近邻点数目占数据总数的比例P。

输出：聚类结果。

步骤1通过P值计算截断距离dc。

步骤2计算数据集中所有点的局部密度ρi以及最短距离δi。

步骤3计算Dkl并升序排列，以Dkl排序图的拐点作为分界点筛选出聚类中心cci。

步骤4根据DPC原文定义，将γ值最大点定义为实际聚类中心，在候选聚类中心cci中计算距离dist(i,j)，其中，idc，点j被确定为聚类中心，否则，被归并到i点所属的簇类中。

步骤5重复步骤4，直到j=cci，自动选取所有的聚类中心点。

步骤6将其余点分配到最近的聚类中心点，通过计算边界地区密度进行去噪处理，完成聚类。

2.3 算法复杂度分析

假定聚类实验的数据集共有n个数据，根据第1节的描述，DPC算法的时间复杂度主要由计算欧式距离(O(n2))、对欧式距离进行快速排序降序排列(O(n2lbn))和计算ρ和δ(O(n2))组成，因此，DPC的时间复杂度为O(n2lbn)。而根据2.2节的描述，KLDPC在对欧式距离的计算、降序排列和参数ρ和δ的处理上与DPC算法一致，而计算γ，KL中心指标Dkl的时间复杂度为O(n2lbn)，自动选取聚类中心的复杂度为O(n2)，去噪处理的时间复杂度为O(n2)。综上所述，KLDPC的算法时间复杂度也为O(n2lbn)。

3 仿真实验与性能分析

为验证KLDPC算法的效果与性能，本文将KLDPC算法与DPC算法、同样自动确定密度峰值聚类中心的，基于全局簇中心权值的CFSFDP算法[15]和基于γ线性拟合的DenPEHC[16]算法分别在人工数据集和UCI数据集上进行对比实验。

3.1 人工数据集的实验结果分析

在仿真实验中，使用如表1所示的相关信息的3个人工数据集，依次运行CFSFDP，DenPEHC，DPC和KLDPC算法，实验效果如图8—图11所示。

表1 3个人工数据集信息Tab.1 Three synthetic data sets

图8 CFSFDP算法在人工数据集上的聚类结果Fig.8 Clustering results on synthetic datasets by CFSFDP

图8为CFSFDP算法得到的聚类效果图，算法利用全局簇中心权值只能在数据集aggregation上得到正确的聚类结果，无法准确处理环形簇和密集的团状簇。图9为DenPEHC算法在人工数据集上的聚类结果，图9中的DenPEHC算法虽然在数据集spiral和DS31上可以得到正确的聚类结果，但是将数据集aggregation错误地分成了10个簇类，算法无法处理分布不均匀的球形簇。图10为DPC算法在人工数据集上的聚类结果，图10中的DPC算法能够在大量尝试后通过人工挑选比对，得到理想状态下的聚类效果，但却有很大的不确定性，算法不够稳定。图11为KLDPC算法在人工数据集上的聚类结果，图11中的KLDPC算法在DPC的基础上，通过引入参数γ扩大了聚类中心的选取范围、应用KL散度的差异性度量准则从而科学有效地区分出聚类中心点、使用Dkl排序图自动确定聚类中心以跳过手工选取阶段，这3个方法分别解决了原DPC算法存在的少选、多选以及无法准确选取聚类中心点的问题。最终算法可以对环形、团状、球状这3类数据集都自动选取到正确的类簇。上述实验证明，KLDPC算法避免了DPC算法需要手动经验选取合适的聚类中心的不足，并且较之部分自动确定聚类中心的密度峰值算法，KLDPC能够更准确地选取数据集的聚类中心。

图9 DenPEHC算法在人工数据集上的聚类结果Fig.9 Clustering results on synthetic datasets by DenPEHC

图10 DPC算法在人工数据集上的聚类结果Fig.10 Clustering results on Synthetic datasets by DPC

图11 KLDPC算法在人工数据集上的聚类结果Fig.11 Clustering results on Synthetic datasets by KLDPC

3.2 UCI数据集的实验结果分析

为了进一步验证KLDPC算法的性能，采用F-measure[17]与ARI[18]两类聚类评价指标并利用4个真实数据集的信息对4种算法进行对比实验，如表2所示。

两类聚类评价指标的取值为[0,1]，数值越大代表聚类效果越好。实验结果如表3、表4所示(正确的聚类中心数和最优的聚类效果数值都已加下划线表示)

表2 4个真实数据集信息Tab.2 Four real data sets

由表3、表4的实验结果可知， KLDPC和DPC算法都可以得到4个真实数据集的聚类中心点的准确个数，而CFSFDP和DenPEHC算法则都只能得到其中2个正确的聚类中心点。由聚类评价指标值可见，KLDPC算法在使用F-measure和ARI两类评价指标时除了在数据集seeds上结果相同，在其他数据集上均对DPC进行了一定的提升，并且皆是4种算法中最优的聚类效果。综上，KLDPC算法对DPC算法进行了成功改进并且相对其他的改进算法，能够得到更好的聚类效果和更高的聚类中心准确率。

表3 4种算法在真实数据集上的F-measure值和中心数Tab.3 F-measure index value and centers of four methods on real data sets

表4 4种算法在真实数据集上的ARI值和中心数Tab.4 ARI index value and centers of three methods on real data sets

4 结束语

针对DPC需要人工选取聚类中心的问题，本文提出了一种KLDPC算法。该算法在继承了原算法迅捷高效优势的同时，去除了复杂的人工，实现了聚类中心的自动确定，并使选取聚类中心的准确度得到了一定的提升。通过人工以及真实数据集的实验皆可证明，和原DPC算法以及部分密度峰值优化算法相比，KLDPC算法具有更好的准确率以及更优的聚类效果。

但KLDPC算法主要是对选取聚类中心进行优化改进，对于具有复杂数据集结构的对象来说，算法仍有可能无法获得理想的聚类效果。针对这一问题，需要考虑使用合适的距离度量来更好地反映数据间的相对关系并且需要进一步改进算法的分配机制。因此，如何使KLDPC算法能够更有效地处理具有复杂数据结构的数据集，将会是下一步的研究目标。