基于密度的聚类算法(Clustering by fast search and find of density peaksd)

r囧r小猫 2022-06-12 00:58 113阅读 0赞

## 一、概述 ##

“Clustering by fast search and find of density peaks”（下面简称CFDP）是在《Science》期刊上发表的的一篇论文，论文中提出了一种非常巧妙的聚类算法-基于密度的聚类算法。虽然文章出来后遭到了许多人的质疑，但是作为一个小白，该算法的思想是非常值得学习的。新聚类算法的基本思想很新颖，且简单明快，值得学习。下面将对该算法的基本原理进行介绍，并对其中的若干实现细节进行分析。

## 二、算法的基本假设 ##

经典的聚类算法K-means是通过指定聚类中心，再通过迭代的方式更新聚类中心的方式，由于每个点都被指派到距离最近的聚类中心，所以导致其不能检测非球面类别的数据分布。虽然有DBSCAN（density-based spatial clustering of applications with noise）对于任意形状分布的进行聚类，但是必须指定一个密度阈值，从而去除低于此密度阈值的噪音点。  
基于以上分析，在CFDP算法是基于这样的假设：**聚类中心周围都是密度比其低的点，同时这些点距离该聚类中心的距离相比于其他聚类中心来说是最近的。**新算法就是基于这两个假设来识别和查找聚类中心。下面来看该算法的详细计算流程。

## 三、聚类算法流程 ##

对于每一个数据点，要计算两个量：点的局部密度和该点到具有更高局部密度的点的距离，而这两个值都取决于数据点间的距离。

### 1、计算局部密度 ###

数据点的局部密度计算有两种方法：Cut-off kernal和Gaussian kernel

*  Cut-off kernal

Cut-off kernal的计算公式如下：  
![这里写图片描述][20170711154926128]

关于dc的确定，文章指出，dc可以选择为平均每个点的邻居局部密度为数据总数的1-2%（具体做实验时还得调整，但是结果可能不是特别让人满意）。

*  注意

在该算法中Dc需要人工设定，是一个可变参数。从某种程度上来讲，Dc的选取决定着这个聚类算法的成败，取得太大和太小都不行。如果Dc去的太大，将使得每个数据点的局部密度值都很大，导致区分度不高。极端情况是Dc的值大于所有点的最大距离值，这样算法的最终结果就是所有点都属于同一个聚类中心。如果Dc取值太小，那么同一个分组有可能被拆分为多个。极端情况是Dc比所有点的距离值都要小，这样将导致每一个点都是一个聚类中心。在文中作者给出的参考方法是选取一个Dc，使得每个数据点的平均邻居个数约为数据点总数的1%-2%，这里的邻居是指与之距离不超过Dc的数据点。

*  Gaussian kernel

Gaussian kernel的计算公示如下：  
![这里写图片描述][20170711155106592]

### 2、计算距离 ###

距离定义如下：  
![这里写图片描述][20170711155135869]

对于非局部密度最大点，计算距离δi实际上分两步  
\- 找到所有局部密度比i点高的点；  
\- 在这些点中找到距离i点最近的那个点j，i和j的距离就是δi的值。

对于局部密度最大点，δi实际上是该点和其他所有点距离值的最大值。

### 3、找出聚类中心 ###

图1.中的简单示例展示了算法的核心思想。图1.A展示了二维空间中的28个点。可以发现点1和点10的局部密度最大，故将其作为类簇中心。图1.B展示了对于每一个点函数的图示（局部密度为横轴，距离为纵轴），称其为决策图。点9和点10的局部密度值相似，但距离值却有很大差别：点9属于点1的类簇，其它几个有更高的局部密度的点距离其很近，然而点10的有更高密度的最近邻属于其它的类簇。所以，正如预期的那样，只有具有高局部密度和相对较高的距离的点才是类簇中心。因为点26、27、28是孤立的，所以有相对较高的距离值和低局部密度值，它们可以被看作是由单个点做成的类簇，也就是异常点。  
![图1.算法在二维空间的展示][1.]  
图1.算法在二维空间的展示

(A)中点的分布 数据点按照密度降序排列。不同的颜色代表不同的类簇。

类簇中心找到后，剩余的每个点被归属到它的有更高密度的最近邻所属类簇。类簇分配只需一步即可完成，不像其它算法要对目标函数进行迭代优化。

### 4、剩余点的类别指派 ###

当聚类中心确定之后，剩下的点的类别标签指定按照以下原则：

*  首先规定：当前点的类别标签（也就是属于哪个聚类中心）和高于当前点密度的最近的点的标签一致。
 *  根据上面的规定对所有点的类别进行了指定。如下图所示，编号表示密度高低，“1”表示密度最高，以此类推。“1”和“2”均为聚类中心,”3”号点的类别标签应该为与距离其最近的密度高于其的点一致，因此“3”号点属于聚类中心1，由于距离“4”号点最近的密度比其高的点为“3”号点，因此其类别标签与”3“号相同，也为聚类中心1，以此类推。  
    ![20141029105710716][]

在对每一个点指派所属类别之后，该算法并没有人为的直接用噪音信号截断的方法去除噪音点，而是先算出类别之间的边界，然后找出边界中密度值最高的点的密度作为阈值，只保留前类别中大于或等于此密度值的点。

### 5、类别间边界确定 ###

首先为每个类簇定义一个边界区域，即分配到该类簇但于其它类簇的点的距离小于dc（截断距离）的点的集合。然后为每个类簇找到其边界区域中密度最高的点，并以该点的密度作为阀值来筛选类簇。

以下图为例，对于类别1中的所有点（1，3，6，7），计算与其他类别中所有点距离小于等于截断距离DC的最大密度值，例如“1”号点由于其距离其他类别的点的距离均大于DC，因此不予考虑。由下图可以看出密度第6的值距离其他类别最近所以选定密度=(6)，由于“7”号点的密度(7)<（6）， 因此将其作为噪音点去除，最后得到的类别1的点为绿色圈所示“1”、“3”和“6”。  
![20141029110439640][]

## 四、总结 ##

*  算法优点  
    该聚类算法可以得到非球形的聚类结果，可以很好地描述数据分布，同时在算法复杂度上也比一般的K-means算法的复杂度低。同时此算法的只考虑点与点之间的距离，因此不需要将点映射到一个向量空间中。
 *  算法缺点  
    需要事先计算好所有点与点之间的距离。如果样本太大则整个距离矩阵的内存开销特别大，因此如果只需要得到最终聚类中心，则可以考虑牺牲速度的方式计算每一个样本点的和，避免直接加载距离矩阵。

[20170711154926128]: /images/20220612/cd1407d0cb9546ba9de10d3fed5bd54f.png
[20170711155106592]: /images/20220612/fc1d55b8d6764d769922a43341c92a73.png
[20170711155135869]: /images/20220612/7210f0f0ac3e4fd7af011dc9e13436ef.png
[1.]: /images/20220612/21cf6103fba74b4599826ade11b3a78f.png
[20141029105710716]: /images/20220612/b432ce92585c4eb3a5a93005ec015873.png
[20141029110439640]: /images/20220612/c3959132cb834c35b27cc70a4207ec2e.png