这是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
网友评论