原文：Clustering by fast search and find of density peaks
作者：Alex Rodriguez and Alessandro Laio
來源：Science 344.6191(2014), 1492-1496.
轉(zhuǎn)載：簡書不支持公式渲染，便于閱讀可參考 原博文。
摘要
聚類分析的目的在于根據(jù)元素的相似性將元素分類。而該論文基于這樣一種觀點的提出新的方法，即聚類中心的密度高于其鄰居，而密度高的點相對較遠。這個想法構(gòu)成了聚類過程的基礎(chǔ)，其中簇的數(shù)量直觀地產(chǎn)生，異常值被自動地發(fā)現(xiàn)并從分析中排除，并且聚類被識別，而不管它們的形狀和嵌入它們的空間的維度如何。
正文
不同的聚類策略
基于距離的方法
在 K-means 和 K-medoids，聚類是以距離聚類中心很小的距離為特征的數(shù)據(jù)集合。
然而，因為數(shù)據(jù)點總是被分配到最近的中心，所以該類算法只能發(fā)現(xiàn)球形的簇，而在發(fā)現(xiàn)任意形狀的簇時會遇到困難。
提示：
K-均值 (K-Means)的方法僅當簇中均值有定義時才有意義，而當涉及具有標稱屬性的數(shù)據(jù)時，K-均值的方法失效。而這里可采用K-眾數(shù) (K-Modes)的變體，即采用基于頻率的方法來更新簇的眾數(shù)，對具有標稱屬性的數(shù)據(jù)進行聚類。當然，還有K-Prototype、
K-Means++等優(yōu)化版本的算法。
基于密度的方法
通過基于數(shù)據(jù)點局部密度的方法很容易檢測具有任意形狀的簇。其主要思想是：在某領(lǐng)域 (對象或數(shù)據(jù)點的數(shù)目) 內(nèi)，給定密度閾值，將密度低于該閾值的數(shù)據(jù)點視為噪聲丟棄，并將其分配給不連續(xù)的高密度領(lǐng)域的其他簇。這樣的方法可用來過濾噪聲或離群點，發(fā)現(xiàn)任意形狀的簇。
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 是一個基于密度的聚類算法，它將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的領(lǐng)域劃分為簇。在噪聲的空間數(shù)據(jù)庫中可發(fā)現(xiàn)任意形狀的聚類。
然而，從上述當中可知，除了要選擇合適的閾值，且它缺少均值漂移的聚類方法。雖然這種方法允許發(fā)現(xiàn)非球形簇，但僅適用于由一組坐標定義的數(shù)據(jù)。
本文改進的方法
首先，該算法提出假設(shè)：類簇中心被具有較低局部密度的 鄰居點 包圍，且與具有較高密度的 任何點 有相對較大的距離。對于每一個數(shù)據(jù)點 i，要計算 兩個量：點的局部密度 和該點到具有更高局部密度的點的距離
。而這兩個值都取決于數(shù)據(jù)點間的距離
(歐幾里得距離，也稱
歐式距離)。數(shù)據(jù)點的局部密度定義為：
其中 為 0-1 函數(shù)，如果 x < 0，那么
；否則
，
是一個
截斷距離。基本上， 等于與點 i 的距離小于
的點的個數(shù)。算法只對不同點
的相對大小敏感，這意味著對于大數(shù)據(jù)集，分析結(jié)果在
的選擇方面具有很好
魯棒性。
-
是通過計算點之間的
最小距離來測量的，即數(shù)據(jù)點 i 與距離它最近的、密度更高的點 j 的距離最小值式：提示：在圖 1-1.(A) 中可知，數(shù)據(jù)點是按照密度降序排列。
- 若數(shù)據(jù)點 i 是密度最大的點，
如圖 1-1 所示，其展示了算法的核心思想。圖 1-1.(A) 展示了二維空間中的 28 個點，且 A 中數(shù)據(jù)點是按照密度降序排列。圖 1-1.(B) 中以 作為橫坐標，
作為縱坐標，畫二維圖，并稱其為決策圖?？梢园l(fā)現(xiàn)點 1 和點 10 的
和
最大，故將其作為類簇中心。
點 9 和點 10 的
相似，但
所以，正如預(yù)期的那樣，只有具有高
類簇中心。因為點 26、27、28 是孤立的，所以有相對較高的異常點。
類簇中心找到后，剩余的每個點被歸屬到它的有更高密度的最近鄰所屬類簇。類簇分配只需 一步即可完成，不像其它算法要對目標函數(shù)進行 迭代優(yōu)化。
在聚類分析中，定量的衡量分配的可信度是很重要的。在該算法中，首先為每個類簇定義一個 邊界區(qū)域 (即分配到該類簇的點集合，且與其它類簇的點的距離小于 )，然后為每個類簇的找到其邊界區(qū)域中密度最高的點
，并以來表示該點的密度。若類簇中局部密度值比
大的點被看作是類簇的核心部分 (即分配到該類簇的可靠性較高)，其他點 (類簇中局部密度值比
小的點) 被看作是類簇的
光暈部分 (亦可被看作是噪聲)。
(A) 為繪制點分布的概率分布。(B和C) 分分別為4000和1000樣本點的點分布。且每個點以其顏色表示所屬類簇，黑色點屬于光暈類簇 (噪聲點)。(D和E) 為 (B和C) 相應(yīng)的決策圖，其中心由相應(yīng)簇來著色。(F) 作為樣本維度的函數(shù)，分配給不正確聚類的點的分數(shù)。誤差線表示平均值的標準誤差。
從圖 1-2.(F) 中可以看到，錯分點的比例即使在只有 1000 個點的小樣本中仍保持在 1% 以下，說明算法有很好的魯棒性。
從圖 1-3 中可以看到，該算法對于各種數(shù)據(jù)級都能達到很好的聚類效果 (圖中為引用文獻中的測試用例結(jié)果)。
思考
- 摘要部分提到的，異常點能
自動地被分析出來，但從它的 Matlab 源碼可知，還是需要人為判斷異常點 (與問題三結(jié)合思考)？ - 文中提到的截斷距離
，該設(shè)定多少才算較合理？
- 文中判斷簇中心的兩個參數(shù)量
參考資料
[1] Huang Z. Clustering large data sets with mixed numeric and categorical values [C]. 1997: 21-34.
[2] Huang Z. Extensions to the k-means algorithm for clustering large data sets with categorical values [J]. Data mining and knowledge discovery, 1998, 2(3): 283-304.
[3] San O M, Huynh V N, Nakamori Y. A clustering algorithm for mixed numeric and categorical data [J]. Journal of Systems Science and Complexity, 2003, 16(4): 562-571.
