這是近期science上的一篇關于無監督聚類的文章。本文的作者為Alex Rodriguez 和 Alessandro Laio。以下簡要介紹下算法的主要思想以及算法分析。
算法思想
該算法的兩個重要假設：類簇的中心由一些局部密度比較低的點圍繞, 并且這些點距離其他有高局部密度的點的距離都比較大.
首先定義兩個值: 局部密度
文獻閱讀筆記——Clustering by fast search and find of density peak 以及到高局部密度點的距離
文獻閱讀筆記——Clustering by fast search and find of density peak 。
樣本點
文獻閱讀筆記——Clustering by fast search and find of density peak 局部密度
文獻閱讀筆記——Clustering by fast search and find of density peak ：
文獻閱讀筆記——Clustering by fast search and find of density peak 其中
文獻閱讀筆記——Clustering by fast search and find of density peak ,如果
文獻閱讀筆記——Clustering by fast search and find of density peak ；否則，
文獻閱讀筆記——Clustering by fast search and find of density peak 。
文獻閱讀筆記——Clustering by fast search and find of density peak 是一個截斷距離, 是一個參數. 是以
文獻閱讀筆記——Clustering by fast search and find of density peak 相當于距離點 i 的距離小于
文獻閱讀筆記——Clustering by fast search and find of density peak 的點的個數。文章的實驗表明，
文獻閱讀筆記——Clustering by fast search and find of density peak 的選擇比較魯棒, 文中
文獻閱讀筆記——Clustering by fast search and find of density peak 的推薦值是使得平均每個點的鄰居數為樣本總數的1%-2%。如果樣本點的數量過小即分布過散，可參照mean-shift，采用核密度估計的方法計算每點的局部密度。
樣本點
文獻閱讀筆記——Clustering by fast search and find of density peak 到高局部密度點的距離：
文獻閱讀筆記——Clustering by fast search and find of density peak 由公式可知，
文獻閱讀筆記——Clustering by fast search and find of density peak 為密度高于樣本點
文獻閱讀筆記——Clustering by fast search and find of density peak 的樣本點到樣本點
文獻閱讀筆記——Clustering by fast search and find of density peak 的最近距離。對于密度最大的點,
文獻閱讀筆記——Clustering by fast search and find of density peak 。由定義可知，局部密度最大的點肯定是一個中心點。
聚類過程
計算出所有樣本點的局部密度值和到高局部密度點的距離後，可以得到一張決策圖。在決策圖上挑選出具有較大
文獻閱讀筆記——Clustering by fast search and find of density peak 以及較大
文獻閱讀筆記——Clustering by fast search and find of density peak 的樣本點作為類簇中心。在确定了類簇中心之後, 其它樣本點依據局部密度從高到低依先後順序确定所屬的類别，每個人非中心的樣本點的類别為鄰域内最近的高于該點樣本點的點的樣本點所屬的類别（重要，如此可滿足流形）。圖例如下:
文獻閱讀筆記——Clustering by fast search and find of density peak 圖 1 聚類過程說明
如圖1所示，總共有28個樣本點，樣本點按密度高低從小到大給以标号，即1～28号點局部密度遞減。通過圖1右側的決策圖，我們篩選出具有較大
文獻閱讀筆記——Clustering by fast search and find of density peak 以及較大
文獻閱讀筆記——Clustering by fast search and find of density peak 的1号和10号點作為類簇中心，其餘點按密度從高到低依次賦予所屬類簇标号。如首先為2号點指派，離2号最近的密度高于2号點的為1，是以将1号點所屬标号賦予2号；對于3号點，離3号最近的密度高于3号點的為1，是以将1号點所屬标号賦予3号；對于4号點，離4号最近的密度高于4号點的為1，是以将1号點所屬标号賦予4号；對于5号點，離5号最近的密度高于4号點的為4，是以将4号點所屬标号賦予5号……，如此直至标完所有樣本點标号。此外，26, 27, 28三個點的
文獻閱讀筆記——Clustering by fast search and find of density peak 也比較大, 但是
文獻閱讀筆記——Clustering by fast search and find of density peak 較小, 是以是異常點.
聚類分析
聚類分析主要是評估本文算法對參數以及樣本分布的魯棒性。
首先評估樣本分布對聚類結果的影響。在聚類分析中, 通常需要确定每個點劃分給某個類簇的可靠性. 在該算法中, 可以首先為每個類簇定義一個邊界區域(border region), 亦即劃分給該類簇但是距離其他類簇的點的距離小于
文獻閱讀筆記——Clustering by fast search and find of density peak 的點. 然後為每個類簇找到其邊界區域的局部密度最大的點, 令其局部密度為
文獻閱讀筆記——Clustering by fast search and find of density peak . 該類簇中所有局部密度大于
文獻閱讀筆記——Clustering by fast search and find of density peak 的點被認為是類簇核心的一部分(亦即将該點劃分給該類簇的可靠性很大), 其餘的點被認為是該類簇的光暈(halo), 亦即可以認為是噪音. 圖例如下
文獻閱讀筆記——Clustering by fast search and find of density peak 圖2 樣本疏密對聚類結果的影響
A圖為生成資料的機率分布, B, C二圖為分别從該分布中生成了4000, 1000個點. D, E分别是B, C兩組資料的決策圖, 可以看到兩組資料都隻有五個點有具有較大
文獻閱讀筆記——Clustering by fast search and find of density peak 以及較大
文獻閱讀筆記——Clustering by fast search and find of density peak 這些點作為類簇的中心, 在确定了類簇的中心之後, 每個點被劃分到各個類簇(彩色點), 或者是劃分到類簇光暈(黑色點)。F圖展示的是随着抽樣點數量的增多, 聚類的錯誤率在逐漸下降。由圖可知當樣本數處于1000～10000時，聚類錯誤率均為1%以下， 說明該算法對資料疏密具有一定的魯棒性。
文獻閱讀筆記——Clustering by fast search and find of density peak 圖3 門檻值
文獻閱讀筆記——Clustering by fast search and find of density peak 對算法的影響
其次評估參數
文獻閱讀筆記——Clustering by fast search and find of density peak 對聚類結果的影響。如圖3所示，分别設定
文獻閱讀筆記——Clustering by fast search and find of density peak 的值為0.005、0.001，0.005和0.1。由以上4個不同的
文獻閱讀筆記——Clustering by fast search and find of density peak 值，得到4種聚類結果。觀察圖3可發現，當
文獻閱讀筆記——Clustering by fast search and find of density peak 的值從0.005變化值0.1時，雖然
文獻閱讀筆記——Clustering by fast search and find of density peak 的值變化了20倍，但是聚類結果在感官上并無大的差異。以上說明，本文算法對門檻值
文獻閱讀筆記——Clustering by fast search and find of density peak 具有良好的魯棒性。
接着評估不同的資料分布對聚類結果的影響。 圖4中的4幅子圖中的資料都具有較大的聚類難度。其中，圖A的難點在于，類的大小不均衡；圖B的難度在于類的數量繁多，且高度重合；圖C和圖D的難度在于各類在特征空間上分布為非球形。一般來講，在涉及到利用流形分類的算法中，圖C和圖D都會作為經典的測試資料。由4幅子圖的聚類結果容易看出本文算法對資料分布的魯棒性。
文獻閱讀筆記——Clustering by fast search and find of density peak 圖4 不同的資料分布下的聚類效果展示
最後評估不同度量對聚類結果的影響。如圖5所示，對圖A中的資料做3種非線性映射分别得到B、C和D三種新的資料分布。由A、B、C和D的聚類結果可以看出，本文算法對度量具有好的魯棒性。
文獻閱讀筆記——Clustering by fast search and find of density peak 圖5 不同的度量對聚類結果的影響
算法總結
本文提出的算法在本質上是基于流形的做法。本文的算法的過程可以總結為：首先搜尋合适的局部密度最大點作為類簇中心，然後再将類簇标簽從高密度點向低密度點依次傳播。
代碼
https://gist.github.com/jdeng/d2c538e4cab6dd75bf34
http://www.52ml.net/16351.html#title-1
參考：
[1]. Clustering by fast search and find of density peak. Alex Rodriguez, Alessandro Laio
網址：http://www.52ml.net/16296.html
