【論文學習筆記】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）。鄰居改變，則東瀛幫隸屬峨嵋派。