【论文学习笔记】Clustering by fast search and find of density peak

这是近期science上的一篇关于无监督聚类的文章。本文的作者为Alex Rodriguez 和 Alessandro Laio。以下简要介绍下算法的主要思想以及算法分析。

算法主要思想：

该算法的两个重要假设：类簇的中心由一些局部密度比较低的点围绕, 并且这些点距离其他有高局部密度的点的距离都比较大.

算法的C++实现可以参考这里：https://github.com/Tonyfy/fastclust

下面是对聚类过程的形象描述

任务：把所有江湖人士放在一起，要找出这里有几个帮派，每个人属于哪个帮派。

假设：真正的帮主被一些“小喽啰”（局部密度低）包围，知名度高；真正的帮主离其他帮派距离较远，很独立——一山无二虎。

按知名度倒序排列，（知道某人的人数越多，他的局部密度越大，知道乔峰的人最多，乔峰密度最大）。越靠前的人，成为帮主的可能性越大。

假设知名度如下：丐帮乔峰>虚竹>慕容复>丐帮二把手>少林方丈...>小喽啰...

在从前往后，考察每个“帮主”与比他知名度高（局部密度更大）的"帮主"的距离。取其中最小的距离作为这个“帮主”的距离值，距离值表示了该人是否远离其他帮派，称为独立指数。

比如丐帮二把手的知名度也高，但度量距离时，二把手的距离值很显然会等于他与乔峰的距离（乔峰成为他的邻居），这个值很小。那么二把手紧紧与乔峰联系在一起。

按知名度继续判别，对慕容复，可以看出他的局部密度大，距离值也较大（并没有和乔峰等人走得近）。但是他还是会有一个邻居，假设d(虚竹，慕容复)<d（乔峰，慕容复），那么慕容复的距离值是d（虚竹，慕容复），邻居是虚竹。

...依此方案可以知道每个人的知名度和独立指数，对于知名度和独立指数都大的人，我们判断其为帮主。同时，我们也知道了每个人的邻居（乔峰除外，他没有邻居）。

我们判断到有以下帮主：乔峰 虚竹 慕容复 少林方丈...

那么上述帮主自称一类，再次按照知名度由高到低，对每个非帮主进行归类（属于他邻居所在的类别），先是丐帮二把手，他的邻居是乔峰，他属于乔峰一类。

对于其后的小喽啰，如逍遥派的领地内的一个山大王，他的知名度一般，独立指数也不高（邻居是虚竹）。若他没有能够被分为帮主，则他属于虚竹一类。

对于一个更小的帮派，住在遥远的东瀛，他们离其他帮派很远，独立指数很高，但是知名度可以很低（只被东瀛人所知晓）。但他们也会有个邻居，假设是少林方丈，若东瀛帮没被认可，他们会归入少林寺。数据集变化时，如江湖中混入了峨嵋派，碰巧d(周芷若，东瀛武士A)<d（少林方丈，东瀛武士A）。邻居改变，则东瀛帮隶属峨嵋派。