基于密度峰值的快速聚类算法（CFSFDP）

这是Science上一篇聚类的文章：Clustering by fast search and find of density peaks（CFSFDP）。算法的思想很简单，但之前却没有人想到过。所以，仅仅是做聚类的人，也是有希望登大顶的。

为了简化描述，我们称应该归为一类的数据为簇。作者首选讨论了k-means的不足，因为k-means方法将点聚类到临近的簇中去，导致无法处理非球面形状的簇。DBSCAN方法需要设置一个密度的阈值，然后通过这个阈值确定cluster，设置阈值的过程很麻烦，是这个方法的一个缺点。k-means也有类似的缺点，就是需要预先设置k。作者设计了一种方法，既可以处理非球面的簇，又可以自动地检测簇数量的多少。因为该方法不需要反复的迭代运算，所以效率非常高。

算法假设聚类的簇的中心符合以下规则：1. 簇的中心被拥有更低密度的邻居包围着; 2. 并且这些邻居和更高密度的其他点都距离比较远。

N个数据对象 每个数据对象假设有D个维度，本文默认维度为2

定义：U为数据对象集合，xi为数据对象，两个对象的距离用欧氏距离度量：

欧式距离

局部密度

xi的局部密度pi，其中dist_cutoff为截断距离 符合条件的对象个数统计函数

针对数据集中的每个点，我们通过公式计算其密度pi和deltai。pi代表点的密度，deltai代表点i和其他拥有更高密度点的距离的最小值。聚类效果的好坏，dist_cutoff的取值也很关键。

点密度计算的示意图，该图上j的范围是1-5

与高密度点之间的距离

deltai的直观理解是：与隔壁峰值点的距离越大越好。

在比pi大的pj里取离xi最短的那个距离值，作为deltai的值，示意图如下图所示 deltai的计算公式的示意图，假定p1和p2的密度比pi大，则deltai等于点i到点2的距离

聚类过程

计算完每个点的pi和deltai后，画出决策图，决策图右上方的点就是簇的中心点，右上方有几个点，就分几个簇。具体的筛选过程如下：（1）密度非常低的点通常是噪音点，独自成簇，可做好标记，不参与后面的分配；（2）可选择两个指标都在前50%的成立簇中心，剩余的点将归到离它最近的簇中心所在的簇里去。这样，整个聚类操作就结束了。和其它聚类算法相比，该方法不需要反复的迭代操作。作者主要的创新在提炼了两个衡量指标，并提出用决策图进行簇的分类，非常直观。

决策图

本文公式部分来自：https://blog.csdn.net/qq_17073497/article/details/81320837