Clustering by fast search and find of density peaks是我看过的公式最少的一篇方法类文章。

全篇就两个公式,介绍了一类新的(2013年的)聚类方法。 我们一般聚类都会用k-means或者层次聚类,但是这些方法都是在空间中找个中心点。 但要在非球型(空间)的数据中找中心,估计就不太好做了(虽然肯定也是能找出来的,重心,几何中心之类)。

本文用的方法是定义一个局部密度\(\rho_i\)和距离\(\delta\)。

\[\rho_i=\sum_{j}\chi(d_{ij}-d_c)\]

其中当\(x<0\)时有\(\chi(x)=1\),其他情况下\(\chi(x)=0\)

\(d_c\)是距离的cutoff。

本质上,\(\rho_i\)计算的是与点\(i\)的距离小于\(d_c\)的点的数量。

\(\delta_i\)是计算点\(i\)与其他有更高密度的点之间的最小距离。

\[\delta_i=\min_{j:\rho_j>\rho_i}(d_{ij})\]

假设某个点的密度最高,那么\(\delta_i=\max_j(d_{ij})\)

聚类的中心就是有最大\(\delta_i\)的那个点。

该方法的优势是计算比较简单,不需要考虑密度函数,也不需要考虑最优化问题的求解。但是也肯定有不足的地方,这个方法对离群点的处理是认为这些点在一些聚类集合的边缘光晕中。3个实际例子的分析请看文章,不在赘述。