自然最近邻优化的密度峰值聚类算法*

金 辉，钱雪忠

江南大学 物联网工程学院 物联网技术应用教育部工程研究中心，江苏 无锡 214122

1 引言

聚类分析是对一组数据对象或者物理对象进行处理，最终将对象分成几类，使得同一类对象之间的相似度更大，不同类对象之间的相似度更小。聚类分析已经应用在了数据挖掘、图像压缩、图像边缘检测、基因识别、面部识别和文档检索等领域。

在聚类分析的发展过程中，相继提出了K-means、DBSCAN（density-based spatial clustering of applications with noise）[1]、FCM（fuzzy C-means clustering algorithm）、AP（affinity propagation）等一系列的聚类算法文献。2014年Science[2]上发表了一篇“Clustering by fast search and find of fast search”，论文提出一种快速搜索和发现密度峰值的聚类算法。该算法能自动给出数据集样本的类簇中心，而且对数据集样本的形状没有严苛的要求，对任意形状的数据集样本都能实现高效的聚类。该算法的核心思想是认定聚类中心同时满足两点基本要求：（1）本身的密度很大，即它的周围邻居点的密度均没有它大；（2）与比它密度更大的数据点之间的“距离”更大。然而DPC（clustering by fast search and find of density peaks）算法的劣势和难点不容小觑：（1）各个领域在使用DPC算法的时候，截断距离是该算法必须设定的参数，人们一直是手工设定该参数，手工设定存在一定的随机性和人为因素，影响聚类质量。（2）对较高维度数据的分析处理一直是DPC算法的短板，较高维度数据自身结构拥有稀疏性和空间复杂性，使得传统的欧式距离在反映数据对象之间的相似性时无法达到准确、合理的目的，因此导致该算法失效。（3）虽然DPC算法声称能自动确定聚类结果，但在实际聚类操作中却需要手动进行聚类结果的选定，聚类结果不能自动给出。

针对DPC聚类算法存在的不足，Zhang等[3]结合该算法和 Chameleon（hierarchical clustering using dynamic modeling）算法，提出了E_CFSFDP（extended fast search clustering algorithm：widely density clusters,no density peaks），解决了CFSFDP（clustering by fast search and find of density peaks）算法中无法处理一个类簇中有一个以上密度峰值点的问题，但是该算法的性能有待进一步提高并且在处理高维数据上的能力有待加强。Liu等[4]提出一种基于K近邻（Knearest neighbor，KNN）的快速密度峰值搜索并高效分配样本的算法KNN-DPC，解决了CFSFDP算法聚类结果对截断距离dc比较敏感和因为一步分配所带来的连带分配错误的问题，但是该算法的聚类结果对近邻数K的选取比较敏感。Bie等[5]提出了Fuzzy-CFSFDP算法，将模糊规则用于CFSFDP算法的类簇的中心点确定中，提高了类簇中心点选取和聚类结果的准确率，但在处理复杂数据[6-9]时稍显不足。

本文针对上述遇到的问题，提出了自然最近邻[10-11]优化的密度峰值聚类算法（optimized density peak clustering algorithm by natural nearest neighbor,TNDP）。TNDP算法自适应地、不需要参数地、根据每个点的特征来获得不同的邻居数，以此来计算每个数据点的局部密度，根据类簇中心局部密度大和被稀疏区域划分[12]的特点来确定聚类中心，最后引入类间相似度的概念来合并相似度高的类簇。实验证明，TNDP算法具有更加优秀的聚类效果。

2 自然最近邻居

最近邻居概念在早先就已经被提出，且被广泛应用于模式识别、机器学习等领域。最著名的就是Stevens所提出的两个邻居概念，K-最近邻[13-15]和ε-最近邻。K-最近邻的思想是给定一个数据集，设置一个参数K，然后每个数据对象在数据集中找到K个与自身相似度最大或者距离最小的数据对象。ε-最近邻的基本思想是给定一个数据集，设置一个参数扫描半径ε，然后求出每个数据对象在其扫描半径ε内的近邻数，这样使得每个数据对象在扫描半径ε内的近邻数有可能不同。无论是K-最近邻还是ε-最近邻，其近邻的搜索都是靠人为地设置参数得到的，而不是根据所给数据集自身的特性搜索。

自然最近邻居（natural nearest neighbor，TN）是一种新的最近邻居概念[16]，它是一种无尺度的最近邻居，这也是它与K-最近邻和ε-最近邻最大的不同之处。自然最近邻居的基本思想就是数据集中密集区域的数据点拥有较多的邻居，稀疏区域的数据点拥有较少的邻居，而数据集中最离群的数据点只有几个或没有最近邻居，自然最近邻居的特点是计算过程不需要任何的参数，数据点根据数据集自身的属性特点获得准确邻居，邻居数由于数据的密集程度存在差异，由于噪声点和异常点没有邻居，因此正常点也不会把噪声点和异常点当作邻居。

定义1（自然最近邻居） 基于自然邻居搜索算法，如果点X属于点Y的邻居，而点Y属于点X的邻居，那么点X和Y属于彼此的自然邻居。

定义2（自然特征值supk） 根据TN-Searching算法，每个点有不同数量的邻居，对于任何点i，邻居数量是nb（i）。但是TN-Searching有一个平均数量的邻居，称为supk，它是自然特征值。计算supk的公式如下：

定义3（R-邻域（R-neighbor））findKNN(xi,r)表示KNN搜索函数，它返回xi的第r个邻居，KNNr(xi)是X的子集，定义如下：

算法1TN-Searching

3 TNDP算法

定义4（数据点的密度Den(Pi)） 基于自然邻居定义的密度如下：

这里nb(i)是根据TN-Searching算法得到的每个点的自然邻居数，N(i,nb(i))是点i的nb(i)个自然邻居，dist(i,j)是数据点i和j之间的距离。

定义5（代表点（exemplar）） 数据点q的代表点定义为：

定义6（密度峰（density peak）） 如果数据点p满足如下条件，就称数据点p为一个密度峰：

二是建立完善管理责任制度。在天津日报公布了133条（段）纳入河长制管理的河道和57名“河长”名单，由“河长”对河道水生态环境管理负总责。各区县出台了具体的实施方案，细化分解落实责任至街镇、单位，有的区县还明确了街镇级河长。各区县制定了保洁养管及巡查制度，组建或利用已有保洁队伍，对河道进行日常保洁，全市水生态环境管理责任制初步建立。

定义7（类间相似度（similarity between clusters））

|Ci⋂Cj|指的是类Ci和类Cj的公共部分，supk是自然邻居特征值，Sim(Ci,Cj)的值不小于0，如果这两个相邻的初始簇被稀疏区域划分，则这两个簇之间的相似性将很小，是两个单独的集群。相反，如果这两个相邻的初始簇通过密度区域连接，则这两个相邻簇之间的相似性会很大，然后这两个集群将被合并为一个集群。

定义8（稀疏邻居和密集邻居（sparse and dense neighbor）） 如果数据点q的密度小于数据点p的密度且q是p的自然邻居，则称q是p的稀疏邻居，相反如果数据点q的密度大于等于数据点p的密度且q是p的自然邻居，则称q是p的密集邻居，定义如下：

算法2TNDP

根据以上理论，提出TNDP算法，TNDP算法的主要优点：（1）用自然最近邻居来计算数据点的局部密度，不需要参数，避免了参数敏感问题；（2）用自然最近邻居计算局部密度，由于自然最近邻居准确反映数据点的属性特点，因此这样计算出来的局部密度能准确表示每个数据点的密度大小，提高聚类效果；（3）由于自然最近邻居不包含噪声点和异常点，因此TNDP算法减少了噪声点和异常点对聚类结果的影响。

TNDP算法的主要流程：

步骤2使用定义5和定义8找到每个数据点的代表点和稀疏邻居；

步骤3找到所有的密度峰并任意访问一个密度峰，将它和它的稀疏邻居分到同一个聚类；

步骤4任意在这个簇中找到一个点，并将这个点的稀疏邻居和这个点分类为同一个簇，直到这个簇的所有点都被访问过；

步骤5找到一个未访问的密度峰并重复上述步骤，直到所有的密度峰都被访问过；

步骤6划分好初始类簇，根据初始类簇之间的相似度关系，合并相似度高的初始类簇；

步骤7将类簇中数据个数小于最小自然邻居数的类簇从聚类结果中除去，并将这些类簇中的数据标记为噪声点，获得最终的聚类结果。

如图1所示，绿色点同时被分类为C1和C2，相似度大于α，C1和C2合并成一类，如果相似度小于α，那么绿色点将被分类到其代表点所属的集群中。α值越大，聚类越多。实际上，TNDP算法在参数α的选择上是鲁棒的。

因为TNDP算法使用k-d树来求自然邻居，所以TNDP的算法复杂度为O(n×lgn)。

Fig.1 Intersection ofC1andC2图1 C1和C2的交集

4 实验结果与分析

为了证明TNDP算法的有效性，将TNDP算法与DPC、DBSCAN、K-means算法在合成数据集和真实数据集上进行实验，图2显示了4个合成数据集。Data1是由两个流形类组成，共1 500个点。Data2是由3个复杂流形类组成，共3 603个点。Data3由3个球形类、2个复杂流形类和1个稀疏密度类组成。Data4由6个高密度复杂流形类和一些噪声点组成。对于DPC和DBSCAN算法，进行多次实验取效果最好的结果进行对比，对于K-means假设事先知道所要划分的类数进行实验。

图3显示了Data1在DPC、DBSCAN、K-means和TNDP算法上的聚类效果。DPC算法虽然能聚类正确的类簇数，但无法将所有点准确聚类，聚类效果不好，流形簇相互靠近的地方无法正确聚类。K-means算法同样无法准确聚类两个流形簇相互靠近的地方，聚类效果不好。DBSCAN算法和TNDP算法都能准确聚类，聚类效果都不错，明显比DPC和K-means算法聚类效果要好，但DBSCAN算法需要更多的参数设置。

图4显示了Data2在DPC、DBSCAN、K-means和TNDP算法上的聚类效果。DPC和K-means算法虽然选择了正确的类簇数，但无法将所有点准确聚类，聚类效果不好，只是将复杂流形簇距离近的点聚为一类，DBSCAN聚类算法和TNDP算法都能准确聚类，聚类效果都很好。

Fig.2 Original datasets图2 原始数据集

Fig.3 Clustering results of DPC、DBSCAN、K-means and TNDP on Data1图3 Data1在DPC、DBSCAN、K-means、TNDP上的聚类结果

Fig.4 Clustering results of DPC、DBSCAN、K-means and TNDP on Data2图4 Data2在DPC、DBSCAN、K-means、TNDP上的聚类结果

Fig.5 Clustering results of DPC、DBSCAN、K-means and TNDP on Data3图5 Data3在DPC、DBSCAN、K-means、TNDP上的聚类结果

图5显示了Data3在DPC、DBSCAN、K-means和TNDP算法上的聚类效果。DPC算法对球形簇的聚类效果很好，对复杂流形簇也有一定的聚类效果，但是对Data3显然没有取得很好的聚类效果，K-means可以聚类球形簇，但是对复杂流形簇聚类效果不好，显然DBSCAN聚类效果优于DPC和K-means算法，对球形簇和复杂流形簇都有很好的聚类效果，但是对于密度差异较大的类簇聚类效果一般，将一些正常点当作噪声点，也错误地将不同类簇的点聚为一类，TNDP算法聚类效果比DBSCAN更加优秀，不仅准确聚类球形簇和复杂流形簇，对密度差异较大的类簇也准确聚类。

图6显示了Data4在DPC、DBSCAN、K-means和TNDP算法上的聚类效果。DPC和K-means算法虽然选择了正确的类簇数，但对复杂流形簇的聚类效果不好，只是将复杂流形簇相对距离近的点聚为一类，DBSCAN获得了正确的类簇数，也检测出了噪声点，但是正常类簇中的一些点也被DBSCAN视为噪声点，尽管TNDP未能检测到Data4中的噪声，但TNDP获得了正确的聚类数并正确聚类了所有正常点。

因此，TNDP算法在Data1、Data2、Data3、Data4上的聚类效果明显优于DPC和K-means算法，在Data3、Data4上的聚类效果明显优于DBSCAN，且比DBSCAN需要更少的参数，并且对参数的设置具有一定的鲁棒性。

接着，将TNDP算法在真实数据集上进行实验，数据集信息如表1。

Table 1 Information of datasets表1 数据集信息

在实验中，采用Acc（准确率）、F-Measure（加权F值）这两个聚类指标来评价TNDP算法，并将TNDP算法与DPC、DBSCAN、K-means算法对比。

Fig.6 Clustering results of DPC、DBSCAN、K-means and TNDP on Data4图6 Data4在DPC、DBSCAN、K-means、TNDP上的聚类结果

由表2可知，在准确率上，TNDP算法要明显优于DPC、DBSCAN、K-means算法，在F值的计算上，除了在Wpbc数据集上DBSCAN要优于TNDP算法，其他数据集上都是TNDP算法要明显优于DPC、DBSCAN、K-means算法，且对这几个数据集TNDP算法都能聚类出正确的类数。综合这三方面，显然TNDP算法是最优秀的。

Table 2 Information of clustering index表2 聚类指标信息

TNDP除了在聚类效果上的优越性，在对参数的选择上也具有一定的鲁棒性。如图7所示，在不同的参数α的选择下，聚类效果依旧没有发生变化，只有当α从0.01提高到2.00时，聚类结果才出现了一点点偏差。

因为受到自然最近邻居的影响，一个类簇中相似初始簇的类簇间相似度会在一个小的范围内波动，不同类簇之间的相似度一定很小，甚至为0，所以对参数α的取值不是那么敏感。做实验时一般取所有数据个数的1/100与自然特征值的比值作为初始α。如果α取值过高，原本属于一个类簇的数据会被分成多个类簇；如果α取值过低，可能原本两个相似度很小的类簇会被分成一个类簇。

Fig.7 Clustering results of TNDP with different parameter α图7 不同参数α下TNDP的聚类结果

5 结束语

本文提出了一种新的基于自然最近邻居的密度峰值聚类算法TNDP。首先，该算法通过引入自然最近邻居的概念来计算数据点的局部密度，然后通过类簇间被稀疏区域划分来找到密度峰值，最后通过类簇间相似度的概念来把相似的类簇合并产生最后的聚类结果。通过实验，TNDP算法在对复杂流形数据和密度变化大的数据的处理上具有相当大的优越性，比DPC、DBSCAN、K-means算法更有效，拥有更少的参数，只有一个类簇间相似度，且对类簇间相似度的选择具有一定的鲁棒性。