基于密度峰值和近邻优化的聚类算法*

何云斌，董 恒，万 静，李 松

哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080

1 引言

在数据挖掘领域，聚类分析是一个十分活跃的研究方向。聚类分析无需具有先验知识，根据数据之间内在的关系，就可以进行分类或者划分，因此得到了广大科研工作者的青睐。其中基于密度的聚类方法具有可以识别出任意类型的簇，对噪声不敏感等优点。

文献[1]提出了基于密度的典型代表算法DBSCAN（density-based spatial clustering of applications with noise），可以识别出任意形状的数据，并对噪声不敏感，但时间复杂度略高，并且对邻域参数(ε,MinPts)比较敏感，不同的参数可能会得到不同结果。因此文献[2]对DBSCAN 算法改进，提出了OPTICS（ordering points to identify the clustering structure）算法，使得基于密度的算法得到了更广泛的适用。文献[3]提出“分而治之”和并行方法对DBSCAN 算法改进，通过对数据进行划分，利用“分而治之”思想减少全局变量Eps值的影响，以及采用并行处理方法和降维技术提高聚类效率，降低了DBSCAN 算法对内存的较高要求。Huang等提出了一种基于网格和密度的混合聚类算法GRPDBSCAN（grid-based DBSCAN algorithm with referential parameters），该算法可以有效处理噪声点，且运算效率较高，自动生成邻域参数(ε,MinPts)[4]。这些对聚类算法的讨论，使聚类研究得到了更深入和广泛的应用。

Rodriguez 等[5]在2014 年提出了DPC（clustering by fast search and find of density peaks）算法。该算法简单高效，不需要迭代运算，性能不受数据空间维度的影响，对于聚类过程采取的是基于密度的方法，核心思想是对聚类中心的描述：

（1）聚类中心被不高于它的密度点所包围；

（2）与其他聚类中心的相对距离更大。

根据上述对聚类中心的描述筛选聚类中心，然后将非聚类中心点进行分配到距离其最近的聚类中心，算法结束。

密度峰值算法有一些局限性，比如截断距离由用户根据经验选取，若选取的不合适，则聚类结果较差。此外，在度量数据点的密度时，只有一个恒定不变的截断距离参数，这在同一簇内同时拥有多个高密度点的情况下，无法取得良好的聚类效果。针对这些问题，文献[6]提出信息熵来计算截断距离的方法。文献[7-8]都提出使用网格的方法进行改进。其中文献[7]的主要思想是通过自适应多分辨率的网格划分思想把数据划分到多个网格空间中，然后在每个网格空间中进行密度峰值聚类，进而利用网格边界合并聚类结果。文献[8]则是引入稀疏网格筛选的方法，去除一部分不可能成为聚类中心的点，只保留稠密网格单元中的点进行聚类中心的选择，其余步骤则与原DPC 算法相同。文献[9]提出利用Voronoi图对数据进行处理，并结合MapReduce 模型实现了DPC算法在大规模数据下的应用。文献[10]则指出算法EDDPC[9]（efficient distributed density peaks clustering algorithm）存在大量的冗余数据复制和计算开销，进而提出基于z值的分布式DPC 算法，该算法的设计也是结合了MapReduce模型。

文献[11]提出了基于共享最近邻的密度峰值算法，该算法有效改善了DPC 算法对于一些类簇不能有效识别的缺点。文献[12]结合半监督约束、密度聚类和层次聚类等思想，提出了一种基于约束的DPC算法。文献[13]从两方面来对DPC 算法进行改进：一是从聚类中心开始对数据点的K-最近邻居进行广度优先搜索来指定非异常值；二是使用模糊加权K最近邻居技术分配异常值和第一次分配过程未分配的数据点。文献[14]提出基于自然最近邻优化的方法优化密度峰聚类。文献[15]针对DPC 算法的dc值不能自适应，导致不能够有效应对复杂数据集的问题，提出利用基尼不纯度找到最优的dc值。文献[16]则在局部密度的计算上使用KNN（K-nearest neighbor）的方法改进，在后续数据点的分配时，提出了两种分配策略。文献[17]在利用高斯函数计算局部密度时，将考虑范围限制在dc范围内并在判断相似类簇合并时提出了相应的标准。这些算法从不同角度对DPC算法进行改进，并经过实验验证取得了良好的聚类效果和准确性，但时间复杂度却居高不下。

针对密度峰值算法，本文从以下几个方面进行改进：首先，提出基于K最近邻方法计算局部密度，以改进密度峰值算法不能准确衡量数据点的真实局部密度的不足，根据聚类中心的特点，对聚类中心进行两步筛选，从而准确筛选出聚类中心。然后，依据离群点的特征，结合Voronoi 图，去除离群点的影响。最后，结合层次聚类的思想解决簇之间的合并分裂问题，以改进密度峰值聚类算法不能适应复杂环境数据如流形数据的不足。

2 IDPC（improved density peak cluster）算法

2.1 聚类中心的筛选

在密度峰值聚类算法中，选择聚类中心，需要计算所有数据点之间的距离，并作出决策图。这种方法虽然简单明了，但是时间复杂度达到O(n2)，并且dc值选取不恰当的话，将无法选择出正确的聚类中心，造成多米诺骨牌效应，使聚类结果较差。

如图1 所示，实线圆的半径都为dc，直虚线的长度相同。根据文献[5]的计算局部密度的方法，A中②的局部密度为7，而B中⑥的局部密度为5。但是如果通过选取第k个近邻内的数据点的个数，来算②和⑥的密度，则结果就不一样。假设k为7，则A中②的密度为7，B中⑥的密度为10，⑥的密度大于②的密度。直观上来看，使用K近邻的方法，更符合各数据点的真实局部密度。

Fig.1 Schematic diagram of cluster center图1 聚类中心示意图

为更好地衡量数据点局部密度，将目标数据点与K近邻内的数据点之间的距离也作为一个考虑因素。如图1 所示，若选择前5 个数据点，A中的②相对于B中的⑥，处于更为紧凑的地方，②的局部密度理应大于⑥。因此可以得出，目标数据点周围数据点距离与目标数据点的局部密度成反相关关系。

综合以上分析，给定数据点o，参数k，数据点o的局部密度ρ的计算公式如式（1）所示。

其中，numk是指数据点o和第k近的数据点ok之间的距离内包含的数据点个数。dist(o,oi)是指数据点oi与数据点o之间的欧式距离。

在上述计算局部密度时，采用了KNN 方法，该方法的局限性是需要事先指定k值，但是相对于原DPC算法事先指定dc值，指定k值要相对容易一些。虽然在指定k值之后，k值也像原DPC 算法指定dc值之后一样不再发生变化，但是每个数据点的k个近邻点的分布却是不一样的，结合式（1）的具体计算局部密度方法可知，本文所采用的KNN 方法计算局部密度更为符合数据点的真实情况。KNN 算法另一个局限性是无法考虑样本之间的相关性，由于本文探讨和处理的数据，不涉及高维数据，因此不构成影响。本文选择采用KNN 方法计算局部密度。

成正态分布的数据集的聚类中心的另一个特征是，大于整个数据集的平均密度。利用这个特征，可以对聚类中心进行过滤筛选。

本文通过两步筛选的策略来选择聚类中心。第一步：基于K最近邻的思想，进行初步筛选聚类中心，首先寻找数据点o的K最近邻，根据式（1）计算数据集O中所有的数据点的局部密度，然后计算数据集O的平均密度，将平均密度作为一条分界线，高于平均密度的数据点作为候选聚类中心，并将这些候选聚类中心从高到低进行排序，存入到集合preC中。第二步：根据密度峰值算法对聚类中心的描述，提出规则1 对候选聚类中心进行筛选。

规则1 在候选聚类中心集合preC中，首先选择拥有局部密度最大的数据点oi，将数据点oi加入到候选聚类中心集合realC中，然后从集合preC中判断所有低于其局部密度的数据点是否在oi的dok内，dok是指数据点oi与距离其第k近的数据点之间的距离。将所有局部密度低于oi并且在oi的dok内的数据点及数据点oi，从候选聚类中心集合preC中删除。循环上述过程，直至候选聚类中心集合preC为空。

依据以上分析和规则，给出算法FliterC的主要思想：首先计算数据点oi的局部密度，求出所有数据点的平均密度，然后进行第一步过滤筛选操作，即将那些局部密度低于平均密度的数据点过滤掉，只留下高于平均密度的数据点，并采用快速排序的方法将这些高密度点进行递减排序。接下来，根据规则1，进行第二步精炼筛选操作，直至得到聚类中心。基于以上分析，下面给出筛选聚类中心具体算法FilterC，如算法1 所示。

算法1FliterC(O,k)

算法时间复杂度分析：假设数据集中数据点的个数为n，筛选过后的preC集合大小为m。步骤1～步骤3，只有一个for 循环，可得时间复杂度为O(n)，同样步骤5～步骤9，时间复杂度也是O(n)，步骤10 采用快速排序，时间复杂度为O(nlbn)，在步骤11～步骤19 中有一层for 循环，因为这个for 循环遍历的是preC集合，因此最坏情况下的时间复杂度为O(m)。综上所述，时间复杂度为O(nlbn)。

2.2 离群点的筛选和剪枝

本节讨论数据集中的离群点处理。在密度峰值聚类算法中，对于离群点采用了如下方法处理：首先定义边界区域，边界区域的数据点特征是，它们属于某一个类簇，即在截断距离dc内，但在这些数据点中存在属于其他类簇的数据点。将这些数据点的局部密度计算出一个平均密度，这个平均密度用于区分这些数据点是离群点还是类簇内的点。

上述筛选离群点的方法，依赖于截断距离dc，而截断距离dc的计算代价较高，因此本文采用其他的方法进行处理。本文在计算局部密度时，考虑到目标数据点与周围数据点之间的距离对局部密度的影响。本文基于这样一个直观认知，如果周围数据点距离目标数据点紧凑，那么目标数据点则处于一个相对密集区域，如果周围数据点距离目标数据点松散，那么目标数据点处于相对稀疏的区域。因此本文选择局部密度衡量一个数据点所处于稀疏区域还是密集区域。

在2.1 节中讨论了聚类中心在一个成正态分布的数据集中应该处于平均密度之上，而对于离群点的局部密度应该是处于平均密度之下，因此从这个角度出发，如果一个数据点低于整个数据集的平均密度，那么它就可能成为离群点。因此本文从那些处于平均密度以下的数据点中，进行离群点的筛选和剪枝操作。为了便于查找离群点，本文提出基于Voronoi 图的方法进行查找，首先给出Voronoi 的相关定义：

定义1（Voronoi 图[18]）给定一组生成点O={o1,o2,…,on}⊂R2，其中2 ＜n＜∞，且当(i≠j)时，oi≠oj。其中i,j∈{1,2,…,n}。由oi所决定的区域称为Voronoi单元VO，Voronoi 图构成为VD(O)={VO(o1),VO(o2),…,VO(on)}，其中VO(oi)表示的是oi所在的Voronoi单元。

定义2（邻接多边形[19]）共享相同边的Voronoi多边形称为邻接多边形，它们的生成点被称为邻接生成点。Voronoi 单元存在几条边，就会有几个邻接多边形。

定义3（Voronoi 图的t级邻接生成点[18]）给定一组生成点O={o1,o2,…,on}⊂R2。oi的t级邻接生成点定义如下：

（1）一级邻接生成点AG1(oi)={oj|VO(oi) 和VO(oj)有公共边}；

（2）t(t≥2)级邻接生成点AGt(oi)={oj|VO(o)和VO(oj)有公共边，o∈AGt-1(oi)}。

定理1 如果一个数据点有反向最近邻，那么其反向最近邻一定在其一级邻接生成点中。证明见文献[20]。

下面给出离群点的判断规则：

规则2 如果一个低于平均密度的数据点的反向最近邻是0，那么该数据点是一个离群点。

规则3 如果一个数据点的一级邻接生成点均为离群点，那么这个数据点是一个离群点。

根据规则2、规则3 和定理1，本文提出判断一个数据点是否为离群点的规则4。

规则4 对于一个低于平均密度的数据点o，首先找其一级邻接生成点，依次判断其一级邻接生成点的最近邻是否为数据点o，如果都不是，则数据点o为离群点；如果是，则判断其一级邻接生成点是否均为离群点，如果均为离群点，那么数据点o也为离群点，进行剪枝处理。

定理2 给定两个低于平均密度的数据点a、b，假设数据点a的局部密度大于数据点b的局部密度。如果数据点a是离群点的话，数据点b也一定是离群点。

证明 假设数据点a的局部密度高于数据点b的局部密度，根据对局部密度的定义可知，数据点的局部密度与其周围的数据点分布有关，如果一个数据点是离群点，那么该数据点则处于一个稀疏区域。由此可知，如果数据点a是离群点，那么数据点a处于稀疏区域，既然数据点b的局部密度小于数据点a，那么数据点b也必然处于更为稀疏的区域，那么b肯定是离群点。 □

Fig.2 Schematic diagram of outliers图2 离群点示意图

如图2 所示，根据定理1 得到，如果一个数据点具有反向最近邻，则必然在其一级邻接点内。假设数据点v17没有反向最近邻，也就意味着，数据点v17不是任何数据点的近邻点，处于密度稀疏区，那么就将数据点v17视为离群点，即规则2。

假设数据点{v16,v17,v18,v19,v20}为离群点，那么这些点必然处于密度稀疏点，而v21在这些点中间，也处在密度稀疏区域，也将v21视为离群点，即规则3。

通过以上论述和分析以及提出的定理1、定理2，规则2、规则3、规则4，下面给出关于离群点筛选剪枝算法outlierO的主要思想：给定数据集O，首先计算数据集O中数据点的局部密度，进而算出平均密度并筛选出所有低于平均密度的数据点，按递减顺序进行排序，并存入集合outO中。然后，将所有数据点作为生成点，生成Voronoi 图，将集合outO中的数据点根据局部密度大小，从大到小进行逐个判断是否为离群点，如果是离群点，则从数据集O中删除该点及后续所有数据点，并停止判断，离群点筛选剪枝算法过程结束。下面给出具体的离群点筛选剪枝算法outlierO，如算法2 所示。

算法2outlierO(O,k)

算法时间复杂度分析：假设数据集的大小为n，筛选过后的数据集outO的大小为m。算法有三个循环：步骤1～步骤3 为第一个循环，时间复杂度为O(n)；步骤5～步骤9 为第二个循环，由于遍历的数据是整个数据集O，因此时间复杂度为O(n)；步骤12～步骤17 为第三个循环，当遇到数据点是离群点时，停止遍历，由于遍历的数据集为筛选过后outO，因此时间复杂度肯定是不大于O(n)。步骤10 使用快速排序的方法对数据集outO进行递减排序，时间复杂度为O(mlbm)，步骤11 生成Voronoi 图的时间复杂度为O(nlbn)。综上所述，该算法的时间复杂度为O(nlbn)。

2.3 数据点的分配

本节讨论非聚类中心点、非离群点，即普通数据点如何进行聚类划分的问题。在密度峰值聚类算法中，针对数据点分配问题的算法是在选择聚类中心时，计算了所有数据点到其最近密度更高的数据点的距离，因此在筛选出聚类中心后，将剩余的数据点根据先前计算出的信息，直接进行分配即可，该算法分配数据点步骤的高效是建立在前期计算出的信息上面。由于本文提出的聚类中心筛选算法，没有获取数据集中数据点两两之间的距离信息以及数据点距离密度比其高的最近数据点的距离，因此无法利用密度峰值聚类算法对数据点分配的方法，如果继续采用原方法的话，则需重新进行计算，这将造成巨大的计算代价，会导致整个聚类算法时间复杂度提高。

本文借鉴密度峰值算法对于数据点的分配思想，通过对以上问题的分析，利用Voronoi 图的性质，提出基于Voronoi图的分配策略。该策略无需利用两两数据点之间的距离信息，就可以完成数据点的分配操作。

Voronoi图的相关定义在2.2 节已经介绍过，下面给出Voronoi图的性质[18]。

性质1 任意两个多边形不存在公共区域。Voronoi图将数据集中数据按照其最近属性将空间进行划分，生成互不重叠的区域。

性质2 在Voronoi 图区域内的数据点，距离其Voronoi图区域内的生成点的距离最近。

性质3 处于两个邻接生成点的生成区域的Voronoi 图公共边上的数据点，与两个邻接生成点之间的距离相等。

性质4 处于m个邻接生成点的生成区域的在Voronoi 图公共边交点处的数据点，与这m个邻接生成点的距离相等。

首先根据算法FliterC对数据点的预处理操作后生成的聚类中心，作为Voronoi 图的生成点，生成Voronoi 图，根据Voronoi 图的性质，可以得到在某一个Voronoi区域内的数据点距离其所在区域的生成点最近，那么可以将其划分到对应的生成点所代表的类簇中。这时会出现对于分布在邻接多边形的共享边，共享交点处的数据点怎样进行划分的问题，如图3 所示。针对这个问题，本文根据性质2、性质3、性质4，对于分布在共享边、共享交点处的数据点，提出规则5 进行解决。

规则5 当数据点分布在m个邻接多边形的共享边或者共享交点时，采取随机分配的方法将数据点分配到m个邻接生成点中的一个代表的类簇上。

如图3 所示，数据点o1、o2在被映射到Voronoi图中时，分布到了{v17,v18,v7,v8}的共享交点和{v7,v8}的共享边处，因此这时可根据规则5 进行判断o1、o2的归属。

Fig.3 Schematic diagram of partial data points distribution图3 部分数据点分布示意图

基于以上论述和分析，结合Voronoi图的性质，本文提出基于Voronoi 图的分配方法，首先将一些初始聚类中心作为Voronoi图生成点生成Voronoi图，这些点将整个区域划分成一个个邻接多边形，将那些不是离群点的数据点映射到整个区域中，根据这些数据点在Voronoi 图哪个邻接多边形区域中，就将其划分归属于哪个类簇，对于在共享边、共享交点处的数据点则按照规则5 进行判断归于哪个类簇，进而可以得到初始的类簇划分。在2.1 节筛选出的聚类中心，只是一个初始聚类中心，因此基于这个聚类中心划分的数据点形成的类簇，也只是一个初始的类簇，并非最终的类簇划分结果。

此外基于Voronoi图的划分方法的不足是无法正确识别出流形数据。比如：图4 所示是一个流形数据的部分，其中三角形数据点为聚类中心点，取k=2时，根据基于Voronoi图的划分方法，则会将其分裂成3 个簇o1、o2、o3，这显然是不对的。

Fig.4 Schematic diagram of core point data图4 核心点数据示意图

针对上述问题，采用层次聚类的思想，使用式（2）计算这些候选聚类中心集合C中的两两之间的jaccard 相似系数，若其jaaccrd 系数≥距离阈值α，则视为同一组元素，进行合并，直至得出最后的聚类结果，其中距离阈值α由人工设定。

其中，|ci∩cj|是指以ci或cj为中心，第k近邻的数据点距离两个聚类中心的距离为半径的范围内相交的数据点个数。|ci∪cj|为两个集合并集的数据点的个数。虽然以半径为范围，但是实际以两个Voronoi 区域内的数据点个数计算jaccard 系数。

如图3 所示，在Voronoi 区域{v19,v18,v21}3 个区域中，虽然由Voronoi 图的性质2 可知在各自的Voronoi区域内的数据点距离其生成点最近，将这些数据点都划分到生成点所代表的类簇中。但经过观察可以发现，各自数据点互相之间的分布极为接近，如果此时将其分成3 个类簇，则是一种错误的分类，根据实际情况理应划分为一类，这时可以通过给定的k值和阈值α，找到k距离内数据点，然后利用式（2）判断是否超过阈值α，比较各个初始类簇的相似程度，进而判断是否可以进行类簇的合并。

基于以上分析以及2.1 节、2.2 节的讨论，下面给出算法IDPC 的主要思想：首先将数据集O中的数据点作为邻接生成点，生成Voronoi 图。其次利用outlierO算法筛选和剪枝离群点，得到新的数据集O，然后利用FliterC算法进行聚类中心的筛选，将筛选出的聚类中心作为生成点生成新的Voronoi 图，并将其余的数据点映射进Voronoi图中。最后随机选择一个生成点采用广度优先遍历的方法，逐级扫描其邻接区域，使用式（2）判断两者jaccard 系数是否超过阈值α，进而判断是否进行合并，直至得到最后的结果簇。下面给出聚类算法IDPC，如算法3 所示。

算法3 IDPC

算法时间复杂度分析：假设数据集O的大小为n，筛选过后的preC集合大小为m。步骤1 的时间复杂度为O(nlbn)，步骤2 的时间复杂度已经在2.1 节分析得到的是O(nlbn)。步骤3～步骤5 主要是生成Voronoi 图需要耗费时间，生成Voronoi 图的时间复杂度为O(mlbm)。步骤6～步骤18 时间主要消耗在候选区域的两两比较上面，但并不是一个数据点需要与所有的数据点进行比较，而只是与其一级邻接点比较。根据文献[18]可知，平均情况下，每个数据点的一级邻接点的个数为[1,6]个，因此时间复杂度不会达到O(m2)，在最坏情况下的时间复杂度为O(6m) 。综上所述，总时间复杂度为O(nlbn)。

3 实验结果与分析

实验设备系统环境采用Windows 7 的64 位操作系统，计算机的硬件配置16 GB RAM，256 GB ROM，处理器Intel®CoreTMi7 处理器（主频为2.60 GHz）。所有程序使用Java语言进行实现。

本文所提算法IDPC 将在人工数据集与真实数据集上验证可行性，与DPC[5]算法、DBSCAN[1]算法、对DPC 算法进行改进的FKNN-DPC[13]（fuzzy weightedK-nearest neighbors density peak clustering）算法、基于反向最近邻的RNN-DBSCAN[21]（reverse nearest neighbor density-based spatial clustering of applications with noise）算法进行比较与分析。

UCI 数据集是公认、公开的机器学习/数据挖掘数据集，许多聚类算法都会使用其验证聚类算法准确率和有效性。因此本文选择UCI 中的数据作为本文实验的真实数据集，本文所采用的数据信息如表1所示。

Table 1 Data information of UCI data set表1 UCI数据集的数据信息

在对一个聚类算法进行评价时，一般用F-measure熵作为评价聚类外部的标准，简写为F值。用轮廓系数（silhouette coefficient），简写为S值，作为评价聚类内部有效性的指标。另一个聚类评价指标是聚类精度Accuracy，简写为Acc值。

在F值、S值和Acc值中，值的取值范围为[0,1]，并且越接近1，说明效果越好。对上述算法进行100次聚类，取各算法的各指标值的平均值作为其最终的结果值，如表2 所示。从表2 中可以得到，在这些密度聚类算法中，IDPC 算法不论是在F值还是在S值的表现上，都比DPC 和DBSCAN 算法要好一些，而与FKNN-DPC 与RNN-DBSCAN 等算法表现出相近的效果。

Table 2 Comparison of evaluation criteria of each algorithm表2 各算法评价标准对比

在表3 的算法运行时间对比中，因为Iris、Heart、Wine 数据集的样本量较少，因此各个算法运行时间较少，而Waveform 的样本数量较多，因此运行时间较慢。从单独的各个样本的运行时间来看，DBSCAN算法相对较慢。在上述分析中，IDPC算法聚类评价指标，与改进DPC 的算法FKNN-DPC、RNN-DBSCAN性能相近，但在时间对比上，本文算法处理相对较快，表现出更高的效率。

上述是在真实数据集上的实验结果与分析，下面进行人工数据集的实验。第一组人工数据集称为Zigzag，由1 002 个数据点生成，包含3 个类簇，1 个如锯齿形状的流形簇，2 个球状簇，如图5 所示。第二组人工数据集称为Parabolic，由1 000 个数据点生成两条对绕抛物线形状的类簇，如图6 所示。

Table 3 Comparison of running time of each algorithm表3 各算法的运行时间对比图

Fig.5 Zigzag data set图5 Zigzag 数据集

对于这两组人工数据集，同样使用F值和S值进行比较，实验进行500 次，取最好结果作为结果值，如表4 所示。从表4 可以得到DPC 算法处理流形数据Parabolic 和Zigzag 的聚类效果和准确率，不如其他几个算法，这正是DPC 的一个缺点，就是对于流形数据，会产生一些误差。纵观整个算法指标信息对比，本文所提IDPC 算法的F值和轮廓系数S值都表现出比其他算法较好的效果。

Fig.6 Parabolic data set图6 Parabolic 数据集

Table 4 Comparison of experimental results of artificial data表4 人工数据实验结果对比

Fig.7 Histogram of artificial data experiment running time图7 人工数据实验运行时间直方图

图7 是各算法的运行时间对比的直方图，从图中可以看出，DBSCAN 算法相对DPC 算法来说较为耗费时间，但是各项聚类指标要优于DPC 算法。这与真实数据集上得到的结果、表现出的特征略有不同，从这里可以看出在处理流形数据时，DBSCAN 算法要略优于DPC 算法。结合表4 来看，FKNN-DPC 算法比其他算法时间消耗要多，主要是在考虑共享近邻时花费的时间代价较大，但是带来好处是F值和S值要好一些。本文所提的IDPC 算法，在时间代价上面要优于其他算法，但是在聚类指标F值和S值上和FKNN-DPC 算法相近，比RNN-DBSCAN 算法要好一些。

表5 展示了各个算法在不同数据集上的聚类精度，其中加粗部分为多次实验取得的最优值，“—”表示没有对应值。在UCI 的4 个数据集上，本文所提算法要优于其他算法的聚类精度。此外，在人工数据集Zigzag 和Parabolic 方面，从图5 和图6 可知这两 个数据集是较为复杂的数据集，既包含流形数据，也包含了流形数据与普通形状数据混合的数据，但从表5 展示的聚类精度可得，相比于其他算法，本文所提算法在处理这类复杂数据时可以取得更高的聚类精度。

Table 5 Comparison of clustering accuracy of different algorithms in different data sets表5 各算法在不同数据集聚类精度对比

Fig.8 Clustering accuracy of different distance thresholds α图8 不同距离阈值α的聚类精度

IDPC 算法中包含一个距离阈值α，下面讨论分析距离阈值α对IDPC 算法的影响。本文选择通过在复杂数据集Zigzag 和Parabolic 下，不同距离阈值α对IDPC 算法产生的聚类精度影响进行实验，并给出距离阈值α的选取原则。从图5 和图6 可知，Zigzag数据集是一个锯齿形数据加两个圆形数据的数据集，Parabolic 数据集是两个对绕的条形数据。图8 展示了不同距离阈值α，IDPC 算法处理Zigzag 数据集和Parabolic 数据集获得的聚类精度。对于Zigzag 数据集，距离阈值α从1 增长到5，获得的聚类精度也跟着从62.1%增长到93.3%，继续增加距离阈值α到16，可以发现，聚类精度从距离阈值α为5 时的93.3%开始一直呈现下降趋势。观察整个变化情况，在距离阈值α为5 时，IDPC 算法处理Zigzag 数据集可以获得最高的聚类精度。对于Parabolic 数据集，距离阈值α从1 增长到4，聚类精度从60.2%增长到95.1%，然后聚类精度开始随着距离阈值α的增长呈现下降趋势。通过观察图8 可知，IDPC 算法在距离阈值α为4 时取得最高的聚类精度95.1%。

通过上述实验过程和结果的分析，可以得出距离阈值α在不断增长的情况下，IDPC 算法处理数据集得到的聚类效果（本文选择聚类精度指标进行衡量）是呈现先升后降的趋势，并且只需在选取一定范围的距离阈值α进行少量数次实验，进行统计，当出现明显的下降趋势时，即可停止实验，就可以确定出最佳的距离阈值α参数。结合表5 可知，只要距离阈值α选取适当，IDPC 算法相比其他实验算法处理复杂数据集可以取得更高的聚类精度，而距离阈值α的选取也相对原DPC 算法的dc值要相对容易一些，对人的经验依赖性也较小。

综上所述，在聚类效果相近的情况下，本文所提算法更加节约时间，具有更高的效率。在处理复杂数据时，本文所提算法相比其他算法，具有更为良好的聚类效果。

4 结束语

在聚类算法中，基于密度的聚类算法，具有一个显著的优势，就是可以识别出任意形状的类簇，密度峰值算法是近年来基于密度的聚类算法新星，其对聚类中心的描述，是其聚类算法的核心所在，但其缺陷是时间复杂度较高，本文提出基于K近邻的方法遴选初始聚类中心并结合Voronoi图进行了聚类的优化处理，提出了基于密度峰值和近邻优化的IDPC 聚类算法。通过实验证明，本文所提聚类算法具有较好的聚类效果和准确率。

下一步将探讨在障碍环境和移动环境下的聚类算法。