基于密度峰值的聚类算法

1.引言

    2014年6⽉，Alex Rodriguez和Alessandro Laio在Science上发表了⼀篇名《Clustering by fast search and find of density peaks》的文章，提供了⼀种简洁而优美的聚类算法，是⼀种基于密度的聚类方法，可以识别各种形状的类簇，并且参数很容易确定。它克服了DBSCAN中不同类的密度差别大、邻域范围难以设定的问题，鲁棒性强。

    在文章中提出的聚类方法DPCA算法（Desity Peaks Clustering Algorithm）基于这样⼀种假设：对于⼀个数据集，聚类中心被⼀些低局部密度的数据点包围，而且这些低局部密度点距离其他有高局部密度的点的距离都比较大。

2.几个概念

局部密度 ρ i ho_i ρi的定义如下：

    其中     其中 d c d_c dc是⼀个截断距离， 即到对象 i i i的距离小于 d c d_c dc的对象的个数。由于该算法只对 ρ i ho_i ρi的相对值敏感，所以对 d c d_c dc的选择是比较稳健的。

高局部密度点距离 δ i delta_i δi，其定义为： 即在局部密度高于对象 i i i的所有对象中，到对象 i i i最近的距离。 而极端地，对于密度最大的那个对象，我们设置 δ = m a x ( d i j ) delta=max(d_{ij}) δ=max(dij) ； 只有那些密度是局部或者全局最大的点才会有远大于正常值的高局部密度点距离。

3.聚类中心的选取

那些有着比较⼤的局部密度 ρ i ho_i ρi和很大的高局部密度 δ i delta_i δi的点被认为是簇的中心，而高局部密度距离 δ i delta_i δi较大但局部密度 ρ i ho_i ρi较小的点是异常点；确定簇中心之后，其他点按照距离已知簇的中心最近进行分类，也可以按照密度可达的方法进行分类。

4.DPCA算法聚类过程

1.首先计算每个点的局部密度 ρ i ho_i ρi，如图， ρ 1 = 7 ho_1=7 ρ1=7, ρ 8 = 5 ho_8=5 ρ8=5, ρ 1 0 = 4 ho_10=4 ρ10=4 2.然后对于每个点 i i i计算在局部密度高于对象 i i i的所有对象中，到对象 i i i最近的距离 δ i delta_i δi 3.对每⼀个点，绘制出局部密度 ρ i ho_i ρi与高局部密度点距离 δ i delta_i δi的关系散点图 4.图上的异常点即为簇中心。如图所示，1和10两点的局部密度和高局部密度距离都很大，将其作为簇中心。 5.将其他的点分配给距离其最近的有着更⾼的局部密度的簇。（Assign each point to the same cluster of its nearest neighbor of higher density） 左图是所有点在⼆维空间的分布，右图是以 ρ ho ρ为横坐标，以 δ delta δ为纵坐标绘制的决策图。容易发现，1和10两个点的 ρ i ho_i ρi和 δ i delta_i δi都⽐较大，作为簇的中⼼点。26、27、28三个点的 δ i delta_i δi也比较大，但是 ρ i ho_i ρi比较小，所以是异常点。

5.几个注意点

选定簇中心之后 在聚类分析中, 通常需要确定每个点划分给某个类簇的可靠性. 在该算法中, 可以首先为每个类簇定义⼀个边界区域(border region), 亦即划分给该类簇但是距离其他类簇的点的距离小于 d c d_c dc的点(这个区域由这样的数据点构成：它们本身属于该Cluster，但在与其距离不超过 d c d_c dc的范围内，存在属于其他Cluster的数据点). 然后为每个类簇找到其边界区域的局部密度最大的点, 令其局部密度为 ρ h ho_h ρh. 该类簇中所有局部密度大于 ρ h ho_h ρh的点被认为是类簇核心的⼀部分(亦即将该点划分给该类簇的可靠性很大), 其余的点被认为是该类簇的光晕(halo), 亦即可以认为是噪音. 图例如下 A图为生成数据的概率分布，B、C⼆图为分别从该分布中生成了4000，1000个点。D,E分别是B,C两组数据的决策图（decision tree），可以看到两组数据都只有五个点有比较大 ρ i ho_i ρi的 和很大的 δ i delta_i δi，这些点作为类簇的中心，在确定了类簇的中心之后，每个点被划分到各个类簇（彩色点），或者划分到类簇光晕（黑色点），F图展示的是随着抽样点数量的增多，聚类的错误率在逐渐下降，说明该算法是鲁棒的。