伴随着时代的发展与进步，大数据技术已深入到人们的生活中，比如在视频广告、交易平台和视频终端，每天产生海量的数据，如果将这些数据加以利用，就可以化“数字”为“神奇”，创造无穷价值，因此“数据挖掘”技术被广泛运用。而聚类^[1-5]分析是数据挖掘的一项重要技术，是探索数据之间隐藏联系的重要一环。聚类分析源自分类学，但是聚类和分类并不一样。分类是已经知晓物品的标签，将其分到对应的标签下；而聚类是未知的，是一种无监督的分类方法。

密度峰值(DP)算法^[6]是一种近几年流行的聚类算法。该算法的优势在于不受数据集形状的限制，可以识别出任意形状的数据，如流形、线形、环形和簇形等数据集；也很容易发现数据集中的噪声点。而且其参数唯一、易于使用，并具有很好的鲁棒性，广受学者们的欢迎。尽管如此，DP算法还是有一些不足：1)DP算法的局部密度计算方式是通过截断距离（ ${d}_{\rm{c}}$ ）来计算的，这个值往往是通过经验设置，无法适应不同密度的数据集。2)DP算法是根据排序好的候选中心来聚类的，若开始选择了较差的候选者则会导致难以估量的后果。近年来，针对DP算法提出很多的改进算法，如引入信息熵概念来改进 ${d}_{\rm{c}}$ 的计算^[7]，这样会使DP算法聚类中心的选择过程更直观；还有利用基尼不纯度发现最佳 ${d}_{\rm{c}}$ ^[8]；Liu等^[9]提出基于KNN的新密度度量方式的ADPC-KNN算法；Mehmood等^[10]结合了截断距离选择和核密度估计的边界矫正的CFSFDP-HD，以实现更精确的聚类效果，不受噪声点的干扰。

经过上述分析发现，实现自适应DP聚类算法关键是聚类中心的选取、 ${d}_{\rm{c}}$ 的计算和类数目的确定。目前针对前2个因素的改进已经进行了大量的相关研究^[11]，但是对于类数目的确定仍然停留在人工干预选择的阶段，缺少自动选择类数目的相关工作。

本文针对上述分析，提出以下内容：1)提出基于自然邻居的新内核；2)改进自然邻居的搜索算法；3)联合肘方法以自适应确定类数目。

1 相关工作 1.1 DP算法

密度峰值算法的本质在于聚类中心，该算法在于提出一种方式高效地选取数据集中的聚类中心。Rodriguez等^[6]提出2个关于聚类中心的假设：

假设1　聚类中心的密度应比其邻居密度都要大，即它任意邻居的密度均小于它。

假设2　聚类中心应与其他密度大于它的聚类中心的“距离”相对更大，即2个聚类中心应有一段距离。

设数据集 $ D=\{{x}_{1},{x}_{2},\cdots ,{x}_{N}\} $ ，标签集 $ F=\{{f}_{1},{f}_{2},\cdots , $ $ {f}_{N}\} $ ，候选聚类中心 $ C=\{{c}_{1},c,\cdots ,{c}_{K}\} $ ， $ {d}_{ij}={\rm{dist}}({x}_{i},{x}_{j}) $ 表示数据点 $ {x}_{i} $ 和 $ {x}_{j} $ 之间的欧几里得(或者其他度量方法)距离。

对于局部密度 $ {\rho }_{i} $ 的计算方式大体有2种，分别是截断内核(Cut-off kernel)和高斯内核(Gaussian kernel)。

1.1.1 截断内核

${\rho _i} = \sum\limits_{j \in {F_D}\left\{ i \right\}} {X({d_{ij}} - {d_c})} $

式中

$X\left( x \right) = \left\{ {\begin{array}{*{20}{c}} {1,}&{x < 0} \\ {0,}&{x \geqslant 0} \end{array}} \right.$

其中，参数 ${d}_{\rm{c}}$ 一般通过经验设置或是实验验证最优 $ {d}_{c} $ 来选取。

1.1.2 距离 $ {\delta }_{i} $

${\delta _i} = \left\{ {\begin{array}{*{20}{c}} {\max \left\{ {{d_{ij}}} \right\},}&{F_D^i = \phi } \\ {\min \left\{ {{d_{ij}}} \right\},}&{F_D^i \ne \phi } \end{array}} \right.$

(1)

式中

$F_D^i = \left\{ {k \in {F_D}:{\rho _k} > {\rho _i}} \right\},$

通过式(1)可知：若 $ {x}_{i} $ 的局部密度为全局最大时， $ {\delta }_{i} $ 为 $ {x}_{i} $ 与数据集中所有数据点的聚类降序排序中的最大值；否则 $ {\delta }_{i} $ 为所有局部密度大于 $ {x}_{i} $ 的数据点中的距离降序排序中的最小值。

文中提出一种新的参数 $ \gamma $ ，用来表示聚类中心的评估值，参数 $ \gamma $ 是局部密度 $ {\rho }_{i} $ 和距离 $ {\delta }_{i} $ 的乘积：

$\gamma {\rm{ = }}{\rho _i}{\delta _i},i \in {I_S},$

显然，一个数据点的 $ \gamma $ 值越大，它是聚类中心的可能性越高。

1.2 自然邻居

自然邻居是一个新的邻居概念^[12-14]。与k个最近邻居相比，此方法不需要设置任何参数，并且是自适应搜索邻居的方法。自然邻居主要受到人类社会关系的启发：假设2个人A和B，2个人之间的友谊应该是相互的，即A认识了解B，而B也认识了解A，此时才认为2个人是熟悉的；而当A认识B，但B不认识A时，可以说两者并没有任何关系。这说明一个数据点的自然邻居个数越多，其越紧密；反之，说明其越稀疏。

自然邻居的生成过程是这样实现的：首先初始化当前邻居个数r，通过不断增加r以扩大搜索范围，且每次计算每个点的逆最近邻居数量。当满足以下2个条件之一时，即：1)所有点具逆最近邻居；2)没有逆最近邻居的个数不变，可以认为达到了自然稳定状态。此时的搜索范围r是自然特征值 $ \lambda $ 。

如图1所示，当r=2时，红色圆圈的K近邻为蓝、绿圆圈，其中，蓝色圆圈的K近邻为红、黑圆圈，绿色圆圈的K近邻为白色圆圈。此时，红、蓝互为自然邻居；反之红、绿不是自然邻居。

1.3 肘方法

肘方法顾名思义，就是类似人的手肘，有一个拐点存在^[15]。肘方法就是通过这个拐点来得到最终的K值。它是基于2条曲线得到：一条是由误差平方和(sum of the squared errors，SSE)计算得到，另一条是搜索范围的起点和终点的SSE连线( $ y=ax+b $ )；然后将两者的差值中的最大值所在的K值作为最终结果。其中K的搜索范围影响着2条曲线差值的精度。若范围太大，则当误差平方和趋于平缓时，搜索还未结束；反之范围太小，搜索就会在误差平方和还在下降时结束。无论哪一个都会导致最终的K值无效。如何解决这一问题是使用肘方法的关键。传统的肘方法是通过经验设置搜索范围，本文将其与密度峰值联合以自适应计算肘方法的搜索范围。

2 基于自然邻居的密度峰值算法

传统的密度峰值算法无法实现真正的自适应，其中的参数 ${d}_{{c}}$ 往往根据经验设置，若设置合适，能取得不错的结果，但是这也将导致其局限性。若数据集差别较大，则要么需要通过大量实验重新设置参数，要么会导致得到较差的聚类结果。为了改进这一缺陷，本文通过引入自然邻居的思想，重新定义每个数据点的邻居关系，来重新计算每个数据点的局部密度 $ {\rho }_{i} $ 和距离 $ {\delta }_{i} $ ，根据得到的候选集合联合肘方法得到全局最优类数目。本文还引入了减而治之的思想，改进计算自然邻居的搜索算法，大大减少运行时间。

对于传统的KNN算法，每个数据点要根据 $ {\rm{dist}} $ $ \left(x,y\right) $ (其中y是任意非x数据点)排序，根据距离的大小来判断谁是它的邻居；这就需要事先知道K的大小，否则无法实现真正的自适应。而自然邻居(nature neighbor)的思想是，2个数据点互相认为对方此时是自己的K最近邻居，才认为彼此是自然邻居关系。此时，可以说2个数据点是可靠稳定的邻居关系。通过自然邻居的思想，不仅可以得到理论上更为可靠的邻居关系，并且基于此可以得到更可靠的局部密度，以实现真正意义上的自适应，不再受数据集的规模和固有参数的限制。

由于肘方法的搜索范围往往是根据经验确定，设置数据集大小为N，搜索范围一般为 $\sqrt{N}$ 。对于一些规模较大的数据集，根据经验选择搜索范围在一些情况下可能会耗费更高的时间成本，甚至还会降低聚类的精度。本文通过基于自然邻居的密度峰值算法来确定肘方法的搜索范围，经实验验证，该方法可以大大缩小肘方法的搜索范围，绘制的曲线也更能准确地获得数据集的真实类数目。

为了进一步减小时间成本，本文基于减而治之的思想改进了求自然邻居的算法，将原始时间复杂度从 $ {O\left(n\right)}^{2} $ 缩小到 ${O\left(n{\rm{log}}_{n}\right)}^{2}$ 。在保证准确的同时，大大缩短了运行时间。

2.1 基于自然邻居思想的密度峰值算法

密度峰值算法思想的核心是密集区域的局部密度要大于稀疏地区的局部密度，即密集区域的邻居之间的距离要更小，反之邻居之间的距离要更大。本文结合自然邻居思想给出局部密度 $ {\rho }_{i} $ 的定义为

${\rho _i} = \frac{\omega }{{\displaystyle\sum\nolimits_{j \in N{N_\omega }\left( i \right)} {{\rm{dist}}\left( {i,j} \right)} }}$

(2)

式中： $ \omega $ 为在自然邻居寻找过程中迭代结束后r的值，即某个数据点拥有的最高自然邻居的个数； $ {NN}_{\omega }\left(i\right) $ 表示距i数据点的 $ \omega $ 最近邻居，而 $ {\rm{dist}}(i,j) $ 是数据点i和数据点j的欧几里得距离。

由式(2)易知，基于自然邻居的思想，可以真正自适应地计算合适的邻居个数，为更准确地得到聚类结果提供保证。

2.2 肘方法的搜索范围

假设肘方法的搜索范围 $ {k}_{\rm{max}} $ ，传统方法中 $ {k}_{\rm{max}}=\sqrt{N} $ ，其中N为数据集大小。为了设置更为合适的搜索范围，提高搜索精度，本文提出了候选因子 ${\theta }_{i}$ 。在自然邻居的思想中，聚类中心具有这一特征，即任意候选聚类中心的自然邻居个数应该大于其任意自然邻居的自然邻居个数。因此，候选因子定义为

$ {\theta _i} = \frac{{{n_{{b_i}}}}}{{F\left( {\displaystyle\sum\nolimits_{j \in {n_{{b_i}}}} {{{l}}\left( {{n_{{b_j}}}} \right)} } \right)}} $

式中： ${n_{{b_i}}}$ 为数据点i的自然邻居个数； $ F\left(x\right) $ 为 $ x $ 的算术平均值。

候选因子 $ {\theta }_{i} $ 的大小取决于两点，一是数据点 $ x $ 的自然邻居个数，二是其所有自然邻居的自然邻居个数的平均值。可以发现，一个点的自然邻居个数比其所有自然邻居的自然邻居个数都多，则它很可能是聚类中心。

在选择候选聚类中心时，首先，计算每个数据点的候选因子 $ {\theta }_{i} $ ，只有当 $ {\theta }_{i}>1 $ 时，说明其有资格作为候选聚类中心，即它的自然邻居个数要大于它的邻居；反之，排除它成为候选聚类中心的可能。然后，再根据候选聚类中心的特征值 $ {\gamma }_{i} $ 排序，将结果降序排列。最后，肘方法的搜索范围即经过候选因子 $ {\theta }_{i} $ 过滤出来的数据点，再根据特征值 $ {\gamma }_{i} $ 降序排列，采用肘方法得到最优的类数目。

2.3 NDP指标

肘方法的核心思想是：随着聚类的类别数目K增加，数据集的误差平方和的下降幅度会骤减；然后随着K值的继续增大而趋于平缓，那么曲线图的拐点就是聚类中心。本文提出NDP指标，该指标由2条直线的差值计算得到，一条是由数据集的误差平方和计算得到( $ Z=\left\{{z}_{1},{z}_{2},\cdots ,{z}_{M}\right\} $ )，另一条是肘方法搜索范围的起点和终点的SSE值两点确定的一条直线 $ y=ax+b $ ( $Y=\{{y}_{1},{y}_{2},\cdots ,{y}_{M}\}$ )；然后将2条曲线的差值作为每个K值的NDP指标值，即集合 $ H=\left\{{h}_{1},{h}_{2},\cdots ,{h}_{M}\right\} $ ，最优的类数目是该集合中的最大值所对应的指标K值。

$I_{\rm{NDP}} = \left\{ {{y_i} - {z_i}|i \in C} \right\}$

式中C为候选聚类中心集合， $ C=\left\{{c}_{1},{c}_{2},\cdots ,{c}_{k}\right\}, $ $ \forall {\theta }_{{c}_{i}}>1 $ 。

2.4 减而治之的自然邻居搜索算法

自然邻居的计算过程为，设置n初始值为1(n为自然邻居个数)，遍历n直到满足以下任意条件其中一个：1)所有数据点的自然邻居集合不为空，即每个数据点都至少有1个自然邻居， $l\left({n_{{b_i}}}\right)\geqslant 1$ ；2)2次迭代中没有自然邻居的数据点的个数相等，即新一轮迭代没有减少还未有自然邻居的数据点的个数，时间复杂度是 $ {O\left(n\right)}^{2} $ 。本文对此作出了改进，提出了基于二分的自然邻居搜索算法(binary natuer-neighbor，BNaN)。该算法采用减而治之的思想，每一轮迭代都在缩短搜索区间，以进一步减少时间复杂度并提升运行效率。

首先，算法的目标是找到一个n值使得每个数据点都至少有一个自然邻居。而对于数据来说，有这样一个趋势：随着n的递增，数据集中至少有1个自然邻居的数据点的个数是递增的，且当达到最大值时停止增加。即可以将求n值的问题转换为在一个递增序列中求这个最大值出现的位置。

二分查找的基本用法是在一个有序数组里查找目标元素，具体是检查区间中间元素的值与目标值的大小关系。如果等于，就可以直接返回；如果严格大于，就往右边查找；如果严格小于，就往左边查找。这也符合人类的逻辑思维。

由于一个元素出现多次，即当所有数据点都有自然邻居时，再增加n的值，得到的计算结果相同，此时的n值就是该序列中的最大值。算法具体可以分为3种情况：

1)如果当前看到的元素恰好等于目标值，那么当前元素有可能是目标值出现的第一个位置，因为要找第1个位置，此时应该向左边继续查找。

2)如果当前看到的元素严格大于目标值，那么当前元素一定不是要找的目标值出现的第一个位置(理论上不存在大于目标的值)，此时应该向左边继续查找。

3)小于的情况与第2种情况类似。

Algorithm1总结了所提出的BNaN算法。

Algorithm1BNaN-Searching

Input $ X $ (the data set)

Ouput $ \lambda $

Initializing: $nb\left(i\right),\;{\rm{count}}\left(1\right),\;i,\;j=0,\;N,\;0,\;{l}\left(X\right)$

While $ i<j $ do:

　　 $ {\rm{mid}}=\left(i+j\right)\gg 1 $

　　 ${\rm{count}}\left({\rm{mid}}\right)={{l}}\left({\rm{find}}\left({nb}_{{\rm{mid}}}==0\right)\right)$

　　 $ {\rm{if}}\;{\rm{count}}\left({\rm{mid}}\right)\leqslant 0: $

　　　　 $ j={\rm{mid}} $

　　 $ {\rm{else}}: $

　　　　 $ i={\rm{mid}}+1 $

$ {\rm{if}}\;{\rm{count}}\left({\rm{mid}}\right)==0: $

　　 $ {\rm{return}}\;{\rm{mid}} $

$ {\rm{return}}\;{\rm{mid}}+1 $

end

3 实验结果

为了证实新NDP指标和BNaN算法的性能，本文使用了12个人工数据集和3个真实数据集来测试NDP索引。此外，我们使用调整兰德指标来评估12个合成数据集和3个实际数据集的聚类结果。

通常，聚类K值的范围是 $ [2,{k}_{\rm{max}}] $ ，我们选择 $ {k}_{\rm{max}}=\sqrt{n} $ 。 $\rm{NDP}$ 算法则是自适应地选择K值。在下面的实验结果中都设置以下规则：所有适用NDP索引的算法如果没有特殊表明，都是使用BNaN算法。

3.1 使用人工数据集进行实验

实验包括12个合成数据集，其中包括通过计算机模拟生成的二维随机数。这些数据集是Semicircle2、Semicircle3、Semicircle4、Mix3、Norm2、Norm3，Norm4，Ring2，Parallel2，Parallel3，Segenment4和Circle2。在这些数据集中，Parallel2、Parallel3、Segenment4数据集的结构是线性的，Semicircle2、Semicircle3、Semicircle4数据集的结构是多方面的，Ring2和Circle2数据集是环形的，Norm2、Norm3、Norm4数据集的结构是凸的，而Mix3数据集是混合的。12个数据集的聚类效果如图2所示。

对于Parallel2数据集，其正确的类数目为2。所得到的聚类结果也为2。通过实验发现，在给定最优类簇数目时，其余11个人工数据集的实验结果与Parallel2数据集的实验结果相似。因此，可以得出的结论，在给定最佳聚类数的情况下，可以正确划分12个人工数据集。

3.2 使用真实数据集进行实验

实验包括3个真实数据集：Seeds、Iris和Titanic，这些数据集分别来自UCI机器学习存储库( http://archive.ics.uci.edu/ml/)和KEEL存储库( https://sci2s.ugr.es/keel/datasets.php)。表1为本文算法对3个真实数据集的最佳类数的实验结果。

表1中加粗部分表示在当前数据集中得到的最大值。表1显示了通过候选因子限定了簇数的搜索范围，其中，Seeds簇数的搜索范围是2~14，Iris簇数的搜索范围是2~12，而Titanic簇数的搜索范围是2~6。可以看出通过候选因子，能减少搜索范围，提升计算效率。比如Titanic的样本数目是2201，若按照经验，K值的搜索范围应该是 $ \sqrt{2\;201}=46 $ ，而通过候选因子计算得到的聚类中心候选人的数目是6，远远小于46，可以得出候选因子的提出可以大大提高肘方法的计算效率。最后通过实验可以发现，本文提出的NDP算法可以为3个真实数据集获得正确的最优簇数。当肘方法形成的拐点图肉眼难以区分其拐点时，通过所提出的方法，可以有效地识别拐点，得到最优类簇数目。

表2列出了使用3个真实数据集确定最佳簇数的算法的运行时间，通过观察该表可以发现，通过改进自然邻居的搜索算法(BNaN-Searching)，可以大幅减少算法的时间成本。

为了验证本文提出算法的有效性，将本文算法与自适应密度峰值算法(adaptive peak cluster，APC)、密度峰值算法(density peak cluster, DPC)、基于密度的聚类算法((density-based cluster，DBSCAN)和K-means算法进行比较。真实数据集的聚类结果采用综合评价指标(F值)、归一化互信息(NMI)、准确率(ACC)这3个聚类指标进行评价。通过表3数据可以看出NDP算法的各评价指标均高于其他算法。

4 结论

密度峰值算法已经成为近几年流行的聚类算法，本文针对其依赖固有参数，对于不同数据集的聚类具有很大局限性这一缺点，引入自然邻居思想，实现真正的自适应密度峰值算法，并通过结合肘方法和候选因子，可以快速有效地得到类簇数目。最后对自然邻居的选取算法进一步改良，以实现更高效率的聚类。通过理论研究和实验结果证明，本文提出的新内核和方法可以准确地得到数据集的最优类簇数目，并适用于多种类型的数据集，如线形、流形、环形和凸形数据集。

本文还存在一些不足，所求的局部密度对于噪声点敏感，当噪声较多时，聚类效果和类簇数目的准确度会降低。后续会引入归一化来更好地求得数据点的密度。