【Science】颠覆三观的超强聚类算法

这篇文章是自己在上大数据分析课程时老师推荐的一篇文章，当时自己听着也是对原作者当年的的思路新奇非常敬佩，相信很多伙伴也会非常感兴趣，就来做个分享吧。原论文于2014年发表于Science期刊杂志上。

Science官网截图

论文题目：Clustering by fast search and find of density peaks

所解决的问题？

作者提出了一种更加强大的聚类算法，其对参数的依赖更少，泛化能力更强。集成了k-means和DBSCAN算法的思想。

背景

在研究问题前，我们先做综述算法分析，看看研究进展，还有未研究问题，需要归纳总结，从实际问题，不同门类的研究问题，发现共性问题。这是科研的基本素养。作者正是基于规划总结各类聚类算法得出一种更强的聚类算法。

如今已有很多聚类的方法，但是这些聚类方法针对很多衡量方式都没有达成一致，也就是缺少一种通用的方式，或者说generalization不够。k-means是完全聚类，无法分辨噪声。K参数选择也比较困难，对于非凸形状也无法处理。DBSCAN可以聚类任意形状，但是找一个恰当的minpoint也比较玄学，并且对$\varepsilon$参数敏感。

所采用的方法？

聚类的中心点会有什么特征呢？作者提出了两点直观的理解，之后对其量化建模：

Cluster centers are surrounded by neighbors with lower local density。(聚类的中心周围都是比它密度低的点)。也就是说聚类中心周围密度较低，中心密度较高。
They are a relatively large distance from any points with a higher local density。(聚类中心点与其它密度更高的点之间通常都距离较远)。

也就是满足这两个点才能成为聚类中心点

因此，对于每个样本点 $i$ 计算两个值：

局部密度值(local density)：$\rho_{i}$

$$\rho_{i}=\sum_{j} \chi\left(d_{i j}-d_{\mathrm{c}}\right)$$

其中函数：

$$\chi(x)=\left{\begin{array}{ll}
1, & x<0 \
0, & x \geq 0
\end{array}\right.$$

参数 $d_{c} > 0$ 为截断距离(cutoff distance)，需要事先指定。

距离的定义如下：

$$\delta_{i}=\left{\begin{array}{ll}
\min _{j \in I_{S}^{i}}\left{d_{i j}\right}, & I_{S}^{i} \neq \emptyset \
\max _{j \in I_{S}}\left{d_{i j}\right}, & I_{S}^{i}=\emptyset
\end{array}\right.$$

对于非局部密度最大点，计算距离$\delta_{i}$实际上分两步 :