DensityPeaks算法：基于AA的聚类算法优化

在4.2.2小节提到的k-means和k-中心点算法中，簇被定义为距离簇质心（中心）最近距离的数据对象形成的集合，但是，这种方法不能发现非球面的簇。在4.2.3小节中，指出基于密度的聚类方法能够检测含有任意形状的簇，然而，这样的方法通常需要用户选择一个密度阈值，而这个阈值的选择是不容易的。本节介绍一种类似于k-中心的方法，能够发现非球状簇，并能自动发现簇的数量^[2]。该算法的核心思想在于对簇中心的描述，认为簇中心同时具有下述特点：

（1）簇中心本身密度大，即它被密度均不超过它的邻居包围。

（2）与其他密度更大的数据点之间的距离相对更大。

该算法假设簇中心被局部低密度的相邻数据对象（数据点）所围绕，并且距离局部高密度的数据点相对较远。

设需要聚类的数据集X=｛xi｝（i=1， 2，…， N）， dij = dist（xi，xj）表示数据点xi和xj之间的（某种）距离。

对于数据集x中的任何一个数据对象xi，可以定义两个量（这两个量分别用于对前面提及的簇中心的两个特点进行刻画）：该数据点的局部密度ρi和该数据点距离高密度点的距离δi。这两个值仅仅取决于数据对象间的距离dij，并且假设这些数据对象满足三角不等式。

（1）数据点的局部密度ρi：包括Cut-off Kernel和Gaussian Kernel两种计算方式。

① Cut-off Kernel:

其中函数：

参数dc是截断距离（cut-off distance），需事先指定（后面会对参数dc进行说明）。

由上述定义可知，ρi表示的是x中与xi之间的距离小于dc的数据点的个数（注意，这里不考虑xi本身）。

② Gaussian Kernel:

对比Gaussian Kernel定义和Cut-off Kernel定义，Cut-off Kernel为离散值，Gaussian Kernel为连续值，因此，相对来说，后者产生冲突（即不同的数据点具有相同的局部密度值）的概率更小。此外，对于Gaussian Kernel仍有“与xi的距离小于dc的数据点越多，ρi的值越大”成立。

（2）距离δi：通过计算点xi和任意其他高密度点的最短距离：(www.xing528.com)

注意，δi是比那些一般的最近相邻点的距离更大一些，这些相邻点要满足为局部或是全体最大密度值的点。因此，簇中心被视为值不同寻常的大的数据点。

下面以图4-23为例说明该算法（找到簇中心点）^[3]的主要思想。

图4-23a显示二维空间中的28个数据点。可以看到数据点1和数据点10是密度最大的点，因为它们同时具有较大的ρ值和δ值，它们被作为数据集的两个簇的中心。

图4-23b显示δi和ρi关系的函数，对确定簇中心具有决定性作用。因此，将这种由（pi ，δi）对应的图称为决策图（decision graph）。数据点9和数据点10虽然具有相似的ρ值，但是其对应的δ值却不同：数据点9隶属于数据点1的簇，其他有着更高ρ值的数据点和它十分接近，然而，离数据点10最近的并且有着更高密度邻近点在另一个簇中。因此，正如所预期的一样，只有同时具有相对较高的ρ值和高的δ是簇的中心。此外，数据点26、数据点27和数据点28这三个数据点在数据集中被看作是“离群点”。他们在图4-23b中也很有特点：其δ值很大，但ρ值很小。

簇中心被发现后，每个剩余的点被分配到有着更高密度最近邻近点所在的簇。簇分配只需要一个步骤就可以完成，不像其他聚类算法需要目标函数不断的优化。对于非簇中心的数据点聚类时，是按照ρ值从大到小的顺序进行遍历的，即先处理ρ值大的数据点，然后再考虑其他数据点。

图4-23　算法示例图

（a）数据点的分布，数据点以密度递减的次序排列； （h） （a）图中数据点所构成的决策图，不同的颜色对应不同的簇

算法首先找到每个簇的边界区域（border region），这个边界区域是由这样的数据点构成的：它们本身属于这个簇，但在与其距离不超过dc的范围内，存在属于其他簇的数据点。利用边界区域，为簇计算出平均局部密度ρb，该局部密度用来作为区分cluster core和cluster halo（簇的边际）的分割。簇中密度高于该ρb的点作为簇内的一部分。其他点被作为簇的边际。

关于参数dc的选取，算法使用了一个可选参数t用于确定dc。即，使得每个数据点的平均邻居个数约为数据点总数的1%～2%^[4]。

图4-24是该算法的一个实验。这些数据点是由非球面概率分布和强重叠峰值所绘制成的（图4-24a）。在图4-24b和图4-24c，分别含有4000和1000数据点，其分布在图4-24a中。在对应的决策图（图4-24d和图4-24e），可以看到只有5个点拥有大的δ值和一定规模的密度。这些点在图中用大的实心圆代表，它们对应簇中心。中心被选择出来后，每一个点被分配到簇或边界。

另外，该算法还在一个衡量机器学习算法常用的脸部图像数据集上进行了验证，有兴趣的读者可以查看原文。

图4-24　合成点的分布结果

（a）数据点的概率分布，最低强度的区域对应20%的背景均匀概率；（b）含有4000个点的数据点样本的数据分布。（c）含有1000个点的数据样本的数据分布；（d）对应图4-24b的决策图；（e）对应图4-24c的决策图