一种聚类算法

最近在Science上发表的一篇文章提出如下聚类算法,在网络上引起不少关注。

算法

该算法的假设是类簇的中心由一些局部密度比较低的点围绕, 并且这些点距离其他有高局部密度的点的距离都比较大. 首先定义两个值: 局部密度 $\rho_i$ 以及到高局部密度点的距离 $\delta_i$。

$$\rho_i = N(d_{ij}<d_c) $$

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

对密度最大的点,令
$$\delta_i = \max(d_{ij})$$

一种推荐做法是选择$d_c$使得平均每个点的邻居数为所有点的1%-2%.

那些有着比较大的局部密度 $\rho_i$ 和很大的 $\delta_i$ 的点被认为是类簇的中心,局部密度较小但是 $\delta_i$ 较大的点是异常点。在确定了类簇中心之后, 其他点(按密度从大到小顺序处理)属于比它的密度更大的最近邻的类别。(注意:上述定义比“属于距离其最近的类簇中心所代表的类簇”可能要好,得到的数据类簇更有连续性)

本文提出的算法在本质上是基于流形的做法。本文的算法的过程可以总结为:首先搜索合适的局部密度最大点作为类簇中心,然后再将类簇标签从高密度点向低密度点依次传播。

扩展

以下是个人的一些想法。要应用于社交网络的话,需要修改 $\delta_i$ 的定义。两个团体的中心人物(设为A、B,A为较大团体的成员)也可能相互认识,如果定义他们的距离为1的话,较小团体的中心人物的独立地位就无法体现了。所以我们需要增长他们之间的距离。一种可能的方案是,计算B的友邻与A的平均距离。

确定了类簇中心后,如何确定其他点的归属也比较麻烦,因为社交网络中距离是离散的,最近的距离就是1,往往不只一个最近点。一种方法是视共同友邻最多的友邻为最近友邻,或者更复杂一点,考虑 Merit Function $$f( N_A, N_B, N_{A \cap B})$$。

参考

Clustering by fast search and find of density peak. Alex Rodriguez, Alessandro Laio. 2014

http://www.cnblogs.com/kemaswill/p/3813854.html. kemaswill

http://blog.csdn.net/breeze5428/article/details/36625591. 刘伟

标签: clustering, mechine learning

赞 (4)

添加新评论