开放科学（资源服务）标志码（OSID）：

0 概述

聚类作为一种无监督学习方法，是数据挖掘领域^[1]的重要技术之一。聚类的主要目的是依照所定义的聚类准则，将一组杂乱的数据中具有相似特征的数据点划归为一个类簇，同时使得不同类簇之间具有显著差异^[2]。在如今万物互联、大数据蓬勃发展的当下，所产生的数据量也正在爆炸式增长，因此，寻求一种高效的数据聚类方法显得尤为重要。近年来，许多学者相继提出了多种不同的聚类算法，按照不同的算法原理可将其分为基于划分的聚类、基于层次的聚类、基于网格的聚类、基于密度的聚类、基于模型的聚类这五大类，这几类不同的聚类算法各自都具有独特的优势并得到了广泛研究与应用。

DBSCAN^[3]作为一种典型的基于密度的聚类算法，能够有效识别任意形状的数据，且具有较好的聚类效果，但该算法在聚类过程中易受邻域参数的影响，其结果往往需要反复调参才能确保精确。RODRIGUEZ等^[4]于2014年提出一种新的基于密度的聚类（DPC）算法，该算法因具有原理简单、高效等优点，自提出以来便引起许多学者的关注，且被广泛应用于图像处理^[5]、生物医学^[6]、文档处理^[7]等领域，但是，DPC算法也存在一些缺陷，如聚类结果受局部密度及其相对距离的影响、截断距离需要人为设定且参数的选取较为敏感、聚类中心的选取需人为参与决策、算法难以处理密度分布差异较大和复杂的流形结构数据，这些问题提高了算法在聚类过程中的主观性与不稳定性。

为提高DPC算法的适用性，很多学者都对其做了相应的改进。DU等^[8]提出一种基于KNN的改进密度峰值聚类（DPC-KNN）算法，将KNN与主成分分析法引入局部密度的计算过程，充分考虑数据的邻域分布特征，从而更好地识别边界点的类别。PARMAR等^[9]采用残差来测量邻域内的局部密度，提出一种基于残差的密度峰值聚类（REDPC）算法，其能够更好地处理包含各种数据分布模式的数据集。LIU等^[10]指出DPC算法中如局部密度及最短距离度量方法、剩余点分配策略等所存在的一些问题，提出一种基于共享近邻的聚类方法，该方法通过共享近邻重新定义密度及其距离的计算方式，最后设计两步分配方式对剩余点进行分配，其有效提高了算法的聚类性能。XIE等^[11]提出一种基于模糊加权K近邻的改进DPC（FKNN-DPC）算法，利用K个最近邻个体之间的距离之和来衡量密度，并用一种新的分配方式对剩余点进行分配。CHENG等^[12]提出一种新的基于自然邻居优化的DPC算法，该改进算法可以很好地反映数据的分布，且无需任何参数。HOU等^[13]提出仅基于相对密度关系的聚类中心识别准则，以增强密度峰值聚类算法的聚类效果。FLORES等^[14]通过检测一维决策图中数据点之间的间隙来自动确定聚类中心。LIANG等^[15]提出一种基于分治法的改进DPC算法，该算法在不需要任何先验条件的情况下能够自动寻得聚类中心。QIAO等^[16]引入一种新的不对称度量指标，增强了算法查找边界点的能力，解决了DPC算法在分布不均的数据上聚类效率不高的问题。XU等^[17]提出一种具有密度敏感相似性的密度峰值聚类（RDPC-DSS）算法，其有效提高了流形数据的聚类精度。

本文提出一种基于加权共享近邻与累加序列的密度峰值（DPC-WSNN）算法。定义一种新的基于加权共享近邻的局部密度度量公式，替代DPC中根据截断距离$ {d}_{c} $所定义的密度公式，避免因$ {d}_{c} $选取不当而影响聚类效果，同时，利用加权共享近邻并进一步考虑全局一致性，以有效处理不同类簇数据集分布不均的情况。在选取聚类中心的过程中，在原有决策值$ {\gamma }_{i}={\rho }_{i}{\delta }_{i} $的基础上，重新定义$ \gamma $的计算方式，借鉴ZHOU等^[18]在灰色预测模型中所定义的一阶累加序列生成方式，产生一组$ \gamma $的累加序列，根据所产生的累加序列数值变化情况来实现类簇中心的自动选取，从而避免手动选取聚类中心所带来的误差。

1 密度峰值聚类算法

DPC算法在实现过程中主要基于以下2个假设：

1）聚类中心被一群密度较低的点包围。

2）聚类中心与其他高密度点之间的最短距离足够远。

基于上述2个假设，选取一个合适的截断距离参数$ {d}_{c} $，用来求解数据点的局部密度$ \rho $及其相对距离$ \delta $值，最后根据决策图找出聚类中心并分配剩余点。对于数据集$ X=\{{x}_{1}, {x}_{2}, \cdots , {x}_{n}\} $，$ {d}_{ij} $表示数据点$ i $与点$ j $间的欧氏距离。数据点的局部密度有2种不同的定义方式：

1）在截断核的定义下，点$ i $的局部密度$ {\rho }_{i} $定义为：

$ {\rho }_{i}=\sum\limits _{j=1}^{n}\chi ({d}_{ij}-{d}_{c}) $

(1)

当$ {d}_{ij} < {d}_{c} $时，$ \chi ({d}_{ij}-{d}_{c})=1 $；否则，$ \chi ({d}_{ij}-{d}_{c}) $=0。

2）在高斯核的定义下，$ {\rho }_{i} $如式（2）所示：

$ {\rho }_{i}=\sum\limits _{j\ne i}^{}\mathrm{e}\mathrm{x}\mathrm{p}\left(-\frac{{d}_{ij}^{2}}{{d}_{c}^{2}}\right) $

(2)

点$ i $到其他高密度点间的最短距离$ {\delta }_{i} $定义为：

$ {\delta }_{i}=\left\{\begin{array}{l}\underset{j}{\mathrm{m}\mathrm{a}\mathrm{x}}\left({d}_{ij}\right), {\rho }_{i}\mathrm{最}\mathrm{大}\\ \underset{j:{\rho }_{j} > {\rho }_{i}}{\mathrm{m}\mathrm{i}\mathrm{n}}\left({d}_{ij}\right), \mathrm{其}\mathrm{他}\end{array}\right. $

(3)

当计算出所有点的局部密度$ {\rho }_{i} $以及相对距离$ {\delta }_{i} $后，选择$ {\rho }_{i} $与$ {\delta }_{i} $均较大的点作为聚类中心，将剩余点分配给与之较近的高密度点所在的类簇中从而完成聚类。

2 DPC算法改进 2.1 基于加权共享近邻的局部密度改进

DPC算法定义了2种密度计算方式，2种方式都是以欧几里得距离来衡量数据点的密度，但是欧几里得距离只考虑数据点之间的局部一致性特征，忽略了全局一致性特征，因此，当数据样本点分布不均时，基于欧几里得距离得到的密度通常不能准确地捕捉到固有的数据结构，最终导致聚类性能下降。为了适应更多复杂且分布不均的数据集，本文将共享近邻引入密度计算中，充分考虑样本的整体分布，以更好地平衡样本点的全局一致性与局部一致性。共享近邻^[10]与样本间的相似度定义如下：

定义1（共享近邻）  对于数据集$ X $中的样本点$ {x}_{i} $与$ {x}_{j} $，点$ {x}_{i} $的K近邻记为$ {\mathit{\Gamma}} \left({x}_{i}\right) $，点$ {x}_{j} $的K近邻记为$ {\mathit{\Gamma}} \left({x}_{j}\right) $，则点$ {x}_{i} $与$ {x}_{j} $的共享近邻$ \mathrm{S}\mathrm{N}\mathrm{N}({x}_{i}, {x}_{j}) $定义为：

$ \mathrm{S}\mathrm{N}\mathrm{N}({x}_{i}, {x}_{j})=\left|{\mathit{\Gamma}} \right({x}_{i})\bigcap {\mathit{\Gamma}} ({x}_{j}\left)\mathrm{ }\right| $

(4)

定义2（样本间的相似度） 根据共享近邻的定义，样本点$ {x}_{i} $与$ {x}_{j} $间的相似度$ {s}_{ij} $定义为：

$ {s}_{ij}=\mathrm{e}\mathrm{x}\mathrm{p}\left(-\frac{\sum \limits_{o\in \mathrm{S}\mathrm{N}\mathrm{N}({x}_{i}, {x}_{j})}({d}_{io}+{d}_{jo}{)}^{2}}{1+\left|\mathrm{S}\mathrm{N}\mathrm{N}\right({x}_{i}, {x}_{j}){|}^{2}}\right) $

(5)

其中：$ o $为共享近邻中所取的样本点；$ \left|\mathrm{S}\mathrm{N}\mathrm{N}\right({x}_{i}, {x}_{j}\left)\mathrm{ }\right| $表示属于共享近邻的样本数目，其值越大，表明点$ i\mathrm{、}j $的相似度越大，$ ({d}_{io}+{d}_{jo}) $越小，点$ i\mathrm{、}j $之间的相似度也越大。当2组样本的共享近邻数目相等时，如图 1所示，点$ i $和$ j $、点$ i $和$ k $的共享近邻个数都为1，且此时$ {d}_{ij}={d}_{ik} $，根据三角形的三边关系可知，有$ ({d}_{i{o}_{2}}+{d}_{j{o}_{2}}) > ({d}_{i{o}_{1}}+{d}_{k{o}_{1}}) $，根据式（5）所定义的相似度，则认为点$ i $与点$ k $间的相似度大于点$ i $与点$ j $间的相似度，这样更能反映空间中样本点的分布特征。

此外，在面对不同密度和大小的类簇时，位于数据密集区域的样本点和位于数据稀疏区域的样本点对聚类中心选取的贡献度不一样，因此，在解决数据分布不均的问题上，除对数据进行过采样和欠采样调节外，对样本点的贡献度进行加权处理也可以起到很好的平衡作用。本文以样本点间的共享近邻数作为密度的重要衡量指标，以对每个样本点所在的区域相似度进行权重调整，为此，引入图 2所示的sigmoid函数，其定义如下：

$ \theta \left(x\right)=\frac{1}{1+\mathrm{e}\mathrm{x}\mathrm{p}(-x)} $

(6)

相比于一元一次函数，sigmoid函数在一定程度上可以对数据相似度进行权重调整，减少了因数据分布不均而带来的误差。本文将sigmoid函数引入密度计算中，以互近邻点的数目作为变量$ x $值，分析可知，在式（6）中，当共享近邻数目较多时，表明2个样本点间的相似度较高，有较大的可能性会被聚为一类，通过图 2函数变化图像可知，当互近邻点的数目足够多时，其函数值为1，这表明在处理高密度区域的点时，所加权重接近1，对于高密度样本点而言，其本身就有较大概率被选作聚类中心，此时可令其相似度的权重为1，当互近邻点的数目不断减少或为0时，其权重则由1非线性递减到0.5，这时非聚类中心点与聚类中心有了更加明显的区分，能够使得式（5）所定义的相似度更具合理性和准确性。经过加权后，局部密度$ {\rho }_{i} $如定义3所示。

定义3（局部密度）  对于样本点$ i $，根据其相似度定义密度$ {\rho }_{i} $为：

$ {\rho }_{i}=\sum\limits _{j\in {\mathit{\Gamma}} \left(i\right)}\theta \left( \right|{\rm{SNN}}({x}_{i}, {x}_{j}) \left| \right)\cdot {s}_{ij} $

(7)

通过定义3所给出的密度度量公式，可计算出数据集中所有点的局部密度及相对距离。

为了进一步说明所改进的密度在处理分布不均数据集时的有效性，以Pathbased数据集为例，DPC算法与加权共享近邻的改进DPC算法的决策图如图 3所示。从图 3（a）可以看出，DPC的决策图在确定聚类中心时很容易将第3个聚类点处理为噪声点，从而导致最终聚类结果出现偏差；从图 3（b）可以看出，对密度进行改进后，决策图中聚类中心分布在右上角，均位于高密度区域，通过该决策图可以准确选出目标聚类中心。实验结果表明，改进DPC可以对数据进行全局考虑，解决数据集中的分布不均问题，从而确定正确的聚类中心。

2.2 聚类中心选取方法改进

DPC算法在选取聚类中心时，需要人为参与决策，通过决策图来选取$ \rho $与$ \delta $均较大的点，但对于聚类中心较多的数据集，这种方法显得复杂低效，而且出现错选的概率较大。本文提出一种新的聚类中心选取方法，首先定义决策值$ {\gamma }_{i} $如下：

$ {\gamma }_{i}=\frac{{\rho }_{i}}{{\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}}}\cdot \frac{{\delta }_{i}}{{\delta }_{\mathrm{m}\mathrm{a}\mathrm{x}}} $

(8)

为消除$ {\rho }_{i} $与$ {\delta }_{i} $量纲不同而造成的误差，对$ {\rho }_{i} $与$ {\delta }_{i} $进行归一化处理，将归一化后结果的乘积作为决策值$ {\gamma }_{i} $。本文将$ {\gamma }_{i} $进行降序排列得到一组降序值，将其记为$ {\gamma }^{\text{'}} $，根据聚类中心的性质可知，在$ {\gamma }^{\text{'}}=[{\gamma }_{1}, {\gamma }_{2}, \cdots , {\gamma }_{n}] $中，只有前面几个较大值所对应的点应被选作聚类中心。对此，本文参考文献[18]所定义的一种新的非负序列累加生成方法，对于非负序列$ {S}^{\left(0\right)}=\{{s}_{1}^{\left(0\right)}, $ $ {s}_{2}^{\left(0\right)}, \cdots , {s}_{n}^{\left(0\right)}\} $，定义其累加序列为$ {S}^{\left(1\right)}=\{{s}_{1}^{\left(1\right)}, {s}_{2}^{\left(1\right)}, \cdots , $ $ {s}_{n}^{\left(1\right)}\} $，其中：

$ {s}_{j}^{\left(1\right)}=\sum\limits _{v=1}^{j}{\lambda }^{j-v}\cdot {s}_{v}^{\left(0\right)}, \lambda \in \left(\mathrm{0, 1}\right), j=\mathrm{1, 2}, \cdots , n $

(9)

观察式（9）可知，由于$ \lambda \in \left(\mathrm{0, 1}\right) $，因此该序列在累加过程中，靠前位置信息的影响权重在不断降低，而信息越靠后，权值越大。

对于$ {\gamma }^{\text{'}} $而言，需要保留前面一部分较大的值，因此，本文对式（9）进行调整，使其在累加过程中不断降低序列靠后位置信息的权值，而增大靠前位置信息的权重，使其更好地满足本文的需求。修改后的累加定义如下：

$ {s}_{j}^{\left(1\right)}=\sum\limits _{\nu =1}^{j}{\lambda }^{\nu -1}\cdot {s}_{\nu }^{\left(0\right)}, \lambda \in (0, \mathrm{ }1)\mathrm{ }, j=\mathrm{1, 2}, \cdots , n $

(10)

利用式（10）对$ {\gamma }^{\text{'}} $进行累加，得到一组累加序列$ {\gamma }^{\left(t\right)}=\{{\gamma }_{1}^{\left(t\right)}, {\gamma }_{2}^{\left(t\right)}, \cdots , {\gamma }_{n}^{\left(t\right)}\} $，其中：

$ \left\{\begin{array}{l}{\gamma }_{1}^{\left(t\right)}={\gamma }_{1}\\ {\gamma }_{2}^{\left(t\right)}={\lambda }^{1}{\gamma }_{2}+{\gamma }_{1}\\ {\gamma }_{3}^{\left(t\right)}={\lambda }^{2}{\gamma }_{3}+{\lambda }^{1}{\gamma }_{2}+{\gamma }_{1}\\ ⋮\\ {\gamma }_{n}^{\left(t\right)}={\lambda }^{n-1}{\gamma }_{n}+{\lambda }^{n-2}{\gamma }_{n-1}+\cdots +{\lambda }^{1}{\gamma }_{2}+{\gamma }_{1}\end{array}\right. $

(11)

由于$ {\gamma }^{\text{'}} $为降序排列的序列，因此在逐步累加的过程中，累加序列的值也越来越接近，最终大量的点会不断地集中在一起。在累加序列$ {\gamma }^{\left(t\right)} $中，定义均值$ \mu $为：

$ \mu =\frac{1}{n}\sum\limits_{i=1}^{n}{\gamma }_{i}^{\left(t\right)} $

(12)

在选取聚类中心时，只需在$ {\gamma }^{\left(t\right)} $序列中挑选比均值$ \mu $小的点，将其作为聚类中心。以类别数为7的Aggregation数据集为例，图 4展示了其$ {\gamma }^{\text{'}} $的累加序列分布情况（彩色效果见《计算机工程》官网HTML版），图 4（b）是图 4（a）中方框线内的局部放大图，以便更好地观察均值$ \mu $的位置分布。从图 4（b）可以看出，在累加过程中，大量的点不断地集中在一起，红色点$ u $表示这组序列的均值$ \mu $，其也位于堆积点附近，而聚类中心点对应的累加值则位于均值的前方，此时只需选取那些累加值小于均值的点作为中心进行聚类即可，即将前7个$ {\gamma }^{\text{'}} $所对应的点选取为聚类中心。因此，将累加序列$ {\gamma }^{\left(t\right)} $的均值作为聚类中心和非聚类中心的临界点，可以准确选取聚类中心，从而实现聚类中心的自适应。

综上，聚类中心选取策略步骤为：

1）根据式（8）和式（11）得到累加序列$ {\gamma }^{\left(t\right)} $，并求得其均值$ \mu $，将小于均值$ \mu $的$ {\gamma }^{\text{'}} $个数作为聚类中心数目$ m $。

2）将前$ m $个$ {\gamma }^{\text{'}} $值所对应的点选取为聚类中心。

2.3 算法描述

改进DPC算法描述如算法1所示：首先，计算样本点间的距离矩阵；然后，根据式（3）、式（7）分别计算相对距离与局部密度，在求得每个点的距离与密度后，根据式（11）、式（12）自动选择聚类中心；最后，按照DPC的分配策略对剩余点进行分配聚类。

算法1  DPC-WSNN算法

输入   数据集$ X $

输出   聚类结果$ C $

1.计算样本点的距离矩阵$ \mathrm{D} $

2.根据式（7）计算各点的局部密度$ \mathrm{\rho } $

3.根据式（3）计算各点的相对距离$ \mathrm{\delta } $

4.利用式（8）计算$ \mathrm{\gamma } $序列值，再得到排序后的$ {\mathrm{\gamma }}^{\text{'}} $序列

5.根据式（11）对$ {\mathrm{\gamma }}^{\text{'}} $进行累加得到$ {\mathrm{\gamma }}^{\left(\mathrm{t}\right)} $，再求出$ {\mathrm{\gamma }}^{\left(\mathrm{t}\right)} $序列的均值，将其中小于均值的元素数目$ \mathrm{m} $作为聚类中心数，其$ {\mathrm{\gamma }}^{\mathrm{\text{'}}} $所对应的前$ \mathrm{m} $个点作为聚类中心点

6.对剩余点按照DPC算法的分配准则进行聚类分配，绘制聚类结果图

7.完成聚类

2.4 算法复杂度分析

对于含有$ N $个样本点的数据集，DPC算法的时间复杂度为$ O\left({N}^{2}\right) $。对于本文所提的DPC-WSNN算法，设近邻数为$ K $，其计算局部密度$ {\rho }_{i} $是基于共享近邻的，时间复杂度为$ O\left(KN\right) $；在选取聚类中心时，需多计算一个决策值$ {\gamma }_{i} $，其时间复杂度为$ O\left(N\right) $。综上，本文所提DPC-WSNN算法的时间复杂度为（$ O\left({N}^{2}\right)+O\left(KN\right)+O\left(N\right))\sim O({N}^{2}) $。因此，相较于DPC算法，DPC-WSNN算法的时间复杂度并未增加。此外，在相关算法中，FKNN-DPC算法的时间复杂度为$ O\left({N}^{2}\right) $，DBSCAN算法的时间复杂度为$ O\left({N}^{2}\right) $，AP算法与K-Means算法的时间复杂度分别为$ O\left({N}^{2}\mathrm{l}\mathrm{b}N\right) $与$ O\left(N\right) $。

3 实验结果及分析 3.1 实验数据集

为了评估本文所提算法的有效性，采用如表 1、表 2所示的8个合成数据集和8个UCI数据集对其进行验证。

3.2 评价指标

在实验中，本文将DPC-WSNN算法的聚类结果与FKNN-DPC、DPC、DBSCAN、AP、K-Means的聚类结果进行比较，评价指标选取FM指数（FMI）^[19]、调整兰德指数（Adjusted Rand Index，ARI）^[20]和调整互信息（Adjusted Mutual Information，AMI）^[21]。各指标具体如下：

1）FMI指标。FMI是成对精度与召回率的几何均值，定义如下：

$ {F}_{\mathrm{F}\mathrm{M}\mathrm{I}}=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}} $

(13)

其中：$ a $表示在$ C $和$ {C}^{\mathrm{*}} $中都属于同一类的数据点对数；$ b $表示在$ C $中属于同一类但在$ {C}^{\mathrm{*}} $中不属于同一类的数据点对数；$ c $表示在$ {C}^{\mathrm{*}} $中属于不同类但在$ C $中属于同一类的数据点对数。FMI指标的取值范围是$ \left[\mathrm{0, 1}\right] $，数值越大表示聚类效果越好。

2）ARI指标。兰德指数（RI）的定义式为：

$ {R}_{\mathrm{R}\mathrm{I}}=\frac{a+b}{{C}_{2}^{{n}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{s}}}} $

(14)

其中：$ a $代表在$ C $和$ {C}^{\mathrm{*}} $中都属于同一类的数据点对数；$ b $代表在$ {C}^{\mathrm{*}} $中属于不同类但在$ C $中属于同一类的数据点对数；$ {C}_{2}^{{n}_{\mathrm{s}\mathrm{a}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{s}}} $代表数据集中可组成总元素的对数。在使用RI指标时，不能保证类别标签在随机分配的情况下其值接近0。因此，本文引入ARI^[20]来解决这一问题，ARI指标的定义式为：

$ {A}_{\mathrm{A}\mathrm{R}\mathrm{I}}=\frac{{R}_{\mathrm{R}\mathrm{I}}-E\left({R}_{\mathrm{R}\mathrm{I}}\right)}{\mathrm{m}\mathrm{a}\mathrm{x}\left({R}_{\mathrm{R}\mathrm{I}}\right)-E\left({R}_{\mathrm{R}\mathrm{I}}\right)} $

(15)

其中：$ E\left({R}_{\mathrm{R}\mathrm{I}}\right) $表示RI的数学期望。ARI的取值范围为$ [-\mathrm{1, 1}] $，值越大表示聚类结果越精确。

3）AMI指标。与ARI相似，AMI也是一种常见的聚类评价指标，其定义式为：

$ {A}_{\mathrm{A}\mathrm{M}\mathrm{I}}=\frac{{M}_{\mathrm{M}\mathrm{I}}-E\left({M}_{\mathrm{M}\mathrm{I}}\right)}{\mathrm{m}\mathrm{a}\mathrm{x}\left(H\left(A\right), H\left(B\right)\right)-E\left({M}_{\mathrm{M}\mathrm{I}}\right)} $

(16)

其中：$ H\left(A\right)\mathrm{、}H\left(B\right) $表示2个类别标签的熵。AMI是基于互信息（MI）来衡量聚类效果的类别信息，$ E\left({M}_{\mathrm{M}\mathrm{I}}\right) $表示MI的数学期望。AMI的取值范围是$ [-\mathrm{1, 1}] $，值越接近1表示聚类结果越好，即与真实结果越吻合。

3.3 算法参数设置

为了更好地测试算法的聚类效果，对各对比算法进行参数调优。DPC-WSNN算法和FKNN-DPC算法需要设定样本近邻数$ K $，该参数可根据不同数据集在5~30之间择优选取。DBSCAN算法需要设定邻域半径$ \epsilon $和邻域内包含的最少样本数Minpts，其中，邻域半径$ \epsilon $以0.01为步长，在0.01~1之间选取，邻域内包含的最少样本数Minpts在5~30之间选取。AP算法没有通用的规则来选取参数，本文考虑将参数搜索上限设置为最大相似度的几倍，逐渐缩小搜索范围^[10]。由于K-Means算法中类簇中心的选取对聚类结果有较大影响，因此对每个数据集进行30次重复实验，取最优结果。

3.4 结果分析

选取8种合成数据集和8种UCI数据集，对本文所提算法进行测试和评价，并将其实验结果与FKNN-DPC、DPC、DBSCAN、AP、K-Means进行对比，各算法的3种评价指标值如表 3~表 6所示，其中，加粗值表示最好的聚类结果。从表 3、表 4可以看出，本文所提DPC-WSNN算法相比其他对比算法具有更好的聚类表现，尤其对于Jain数据集，本文算法的聚类准确率较对比算法具有大幅提升。从表 5、表 6可以看出：对于维度高且样本点密度变化大的数据集，DPC、DBSCAN、AP、K-Means的聚类效果都不理想，无法得到较高的聚类指标值；FKNN-DPC算法在Wine数据集上达到最优，而在其他数据集上的聚类效果略差于DPC-WSNN算法，由于DPC-WSNN算法在DPC的基础上引入SNN来对密度公式进行改进，充分考虑了数据分布稀疏的情况，进而可以得到更准确的密度。DPC-WSNN在UCI数据集上的聚类指标值整体更高，在所有对比算法中，其聚类表现最优，在其他数据集上也能达到较好的聚类效果。相比DPC算法和其他几种对比算法，DPC-WSNN算法在处理大部分问题上均能达到较好的效果。

图 5~图 7分别为DPC-WSNN、FKNN-DPC、DPC、DBSCAN、AP、K-Means这6种对比算法在Jain数据集、Flame数据集、Pathbased数据集上的聚类效果（彩色效果见《计算机工程》官网HTML版），图中不同颜色的点被分配到不同的类簇中，其中，蓝色星形代表聚类中心点，叉形代表噪声点。

从图 5可以看出：本文DPC-WSNN算法不仅可以找到正确的聚类中心，而且聚类结果也完全正确；DPC-KNN算法、DPC算法、AP算法、K-Means算法都将本该属于下半部分的类簇错误地分配到了上半部分，从而出现了错误的聚类结果；DBSCAN算法下半部分类簇的聚类结果正确，但上半部分左端几个数据点被错误分配。

从图 6可以看出：DPC-WSNN算法、DPC-KNN算法、DPC算法、DBSCAN算法均得到了正确的类簇数目，其中，DBSCAN算法将左上角的2个点识别为噪声点，导致聚类准确率有所降低，AP算法错误地识别类簇数目，导致将聚类结果分为了3类，而K-Means算法将本该属于红色类簇的点错误地分配给了蓝色类簇。

从图 7可以看出：本文DPC-WSNN算法聚类准确度较高；AP算法不能准确识别出类簇中心，导致聚类结果出现明显偏差；DPC-KNN算法、DPC算法和K-Means算法虽能正确识别类簇中心，但将半环部分的类簇点进行了错误分配；在DBSCAN算法中，虽然2个类簇被正确分配，但半环部分被识别为噪声点，导致聚类准确率大幅降低。

3.5 参数敏感性分析

DPC-WSNN算法在运行过程中，需要人为设置参数$ K $值，为了验证该参数对算法聚类结果的影响，通过改变参数$ K $值大小来探索DPC-WSNN算法在不同数据集上的聚类结果变化。实验选取3个合成数据集和3个UCI数据集，以AMI值作为稳定性衡量指标，$ K $在5~30之间取值，所得的AMI指标值结果如图 8所示。从图 8可以看出：对于合成数据集而言，不同的$ K $值所得到的结果较为稳定，波动较小，具有很好的鲁棒性；对于UCI数据集，前期当$ K $取值较小时，聚类值有一定的波动，但随着$ K $的不断增大，其波动逐渐减小，结果趋于稳定，这意味着当$ K $近邻个数增大时，所设计的加权共享近邻的密度度量具有更好的优势，因此，聚类实验验证了DPC-WSNN算法对参数$ K $的敏感性较低，算法具有较强的鲁棒性。

4 结束语

本文对DPC算法进行改进，提出一种基于加权共享近邻与累加序列的密度峰值算法DPC-WSNN。该算法考虑各数据点的邻域分布情况，利用加权共享近邻重新定义局部密度的度量方式，同时使用$ \gamma $的累加序列来实现聚类中心的自动选取。实验结果表明，相比DPC、AP等算法，DPC-WSNN算法具有较高的聚类准确度。本文算法执行过程中涉及参数$ K $，虽然参数$ K $相较截断距离$ {d}_{c} $更容易确定，但其仍然需要人为决策。此外，DPC算法对剩余点的分配方法也可能会影响DPC-WSNN的聚类效果。因此，实现参数$ K $的自适应以及对DPC算法中剩余点分配策略进行改进，将是下一步的研究方向。