數據科學家需要了解的5大聚類演算法

知識 02-15

聚類是一種涉及數據點分組的機器學習技術。給定一個數據點集，則可利用聚類演算法將每個數據點分類到一個特定的組中。理論上，同一組數據點具有相似的性質或（和）特徵，不同組數據點具有高度不同的性質或（和）特徵。聚類屬於無監督學習，也是在很多領域中使用的統計數據分析的一種常用技術。本文將介紹常見的5大聚類演算法。

K-Means演算法

K-Means演算法可能是最知名的聚類演算法，該演算法在代碼中很容易理解和實現。

K-Means聚類

1.首先我們選擇一些類或組，並隨機初始化它們各自的中心點。為了計算所使用類的數量，最好快速查看數據並嘗試識別任何一個不同的分組。中心點是和每個數據點矢量長度相同的矢量，上圖標記為「X」。

2.每個數據點是通過計算該點與每個組中心的距離進行分類的，然後再將該點分類到和中心最接近的分組中。

3.根據這些分類點，通過計算群組中所有向量的均值重新計算分組中心。

4.重複以上步驟進行數次迭代，或者直到迭代之間的組中心變化不大。選擇結果最好的迭代方式。

因為我們只是計算點和組中心之間的距離，計算量很少，所以K-Means演算法的速度非常快，具有線性複雜度O(n)。

K-Means演算法的缺點是必須選擇有多少個組或類，因為該演算法的目的是從不同的數據中獲得信息。另外，K-means演算法從隨機的選擇聚類中心開始，因此不同的演算法運行可能產生不同的聚類結果。其結果缺乏一致性，而其他聚類方法結果更一致。

K-Medians演算法是和K-Means演算法相關的另一個聚類演算法，該演算法不用均值重新計算組中心點，而是使用組的中值矢量，因此對異常值不太敏感，但對於數據量較大的數據集運行速度慢很多。

Mean-Shift聚類演算法

Mean-Shift聚類演算法基於滑動窗口，並嘗試找到密集的數據點區域。該演算法是一個基於質心的演算法，這就意味著該演算法的目標是定位每個組（類）的中心點，通過更新候選中心店作為滑動窗口的平均值，然後在後續處理階段對這些候選串口進行過濾，消除臨近重複點，形成最終的中心點集及其對應的組。

Mean-Shift聚類演算法的單個滑動窗口

1.如上圖所示的二維空間中的點集合，我們從一個隨機選擇的C點為中心，以r為半徑的圓形華東窗口開始。Mean-Shift演算法是一種爬山演算法，將內核一步步迭代移動到一個較高密度的區域，直到收斂為止。

2.每次進行迭代的時候，通過移動中心點到窗口內點的平均值，將滑動窗口移動到更高密度的區域。滑動窗口的密度和窗口內部點的數量成正比。

3.我們繼續根據平均值移動滑動窗口，直到直到沒有方向可以移動使其容納更多的點。如上圖所示，繼續移動這個圓，直到窗口內的數量（密度）不再增加為止。

4.我們在步驟1-3中會使用很多個滑動窗口，直到所有的點都位於一個窗口內為止。當多個滑動窗口重疊時，保留包含最多點的窗口，然後根據其所在的窗口，將數據點進行聚類。

下圖展示了所有的滑動窗口從頭至尾的運動過程，其中，每個黑點表示滑動窗口的質心，每個灰點表示一個數據點。

Mean-Shift演算法過程

這和K-Mean聚類演算法相比，由於Mean-Shift可以自動選擇聚類的數量，因此不需要手動選擇。這是一個很大的優勢，事實上，聚類中心向最大密度點聚合也很理想。該演算法的缺點是窗口半徑的選擇相對來說不重要。

具有雜訊的基於密度的聚類方法（DBSCAN）

DBSCAN是一種基於密度的聚類演算法，它類似於Mean-Shift演算法，但是具有顯著的優點。

1.DBSCAN從一個未被訪問的任意一個數據點開始。該點的領域用距離ε劃分（ε距離內所有的點都是領域點）。

2.如果領域內有足夠多的點（最大值為minPoints），則聚類過程開始，並且當前的數據點成為新的聚類過程中的第一個點。否則，標記該點味雜訊（稍後，這個雜訊點可能成為聚類的一部分）。在這兩種情況下，該點被標記為「已訪問」。

3.對於新的聚類過程中的第一個點來說，其ε距離領域內頁成為同一個聚類中的一部分。這個過程使ε領域內所有的點都屬於同一個聚類，然後對剛添加到聚類中的所有的新點重複該過程。

4.重複步驟2和3，直到可以確定聚類中所有的點為止，即我們訪問並標記了聚類的ε鄰域內所有的點。

5.一旦我們完成了當前的聚類，我們對新的未訪問到的點進行檢索和處理，發現一個更進一步的聚類或雜訊。重複這個過程，直到我們標記完成所有的點，每個點都被標記為一個聚類或雜訊。

與其它聚類演算法相比，DBSCAN演算法具有很多優點：首先，該演算法不需要固定數量的聚類。其次，它將異常值識別為雜訊，而不像Mean-Shift演算法，即便是數據點非常不同，也會將其放入聚類中。另外，該演算法可以找到任意大小和任意形狀的聚類。

DBSCAN演算法的主要缺點是，當密度不同時，該演算法的性能相對較差。這是因為當密度發生變化時，不同的聚類，用於識別鄰近點的距離閾值ε和minPoints的值將會不同。對於高維數據也會有這種缺點，因為距離閾值ε難以估計。

基於高斯混合模型（GMM）的期望最大化（EM）聚類演算法

K-Means聚類演算法的主要缺點之一就是它使用了聚類中心平均值。通過下圖我們可以明白為什麼這不是一個最佳方式。左側的人眼看的非常明顯，有兩個半徑不同的圓形，二者中心相同。由於這些聚類的平均值非常接近，K-Means並不能處理這種情況。同樣是使用均值作為聚類中心，右側的圖像也不能使用K-Means聚類算處理。

K-Means聚類演算法不能處理的兩種情況

高斯混合模型（GMM）演算法的靈活性比K-Means演算法的靈活性要高。假設GMM演算法中的數據呈高斯分布，這樣我們就有兩個可以描述聚類形狀的參數：均值和標準差。以二維分布為例，這就意味著聚類可以有各種類型的橢圓形（因為在x和y方向都有標準差）。因此，每個單獨的聚類都分配了一個高斯分布。

為了找到每個聚類的高斯參數（均值和標準差），我們使用稱作期望最大化（EM）的一種優化演算法。

1.首先選擇聚類的數量（和K-Means演算法一樣），然後對每個聚類的高斯分布參數進行隨機初始化。我們也可以通過快速查看數據來為初始化參數提供一個較好的預測。

2.為每個聚類分配這些高斯分布，計算每個數據點屬於一個特定聚類的概率。這個點越靠近高斯中心，就越有可能屬於該聚類。因為使用高斯分布，我們假設大部分數據更加靠近聚類中心，因此可以比較直觀的看出來。

3.基於這些概率，我們計算一組新的高斯分布參數，這樣就可以最大化聚類內部數據點的概率。然後我們使用數據點所在位置的加權來計算新的高斯分布參數，其中，權重是數據點屬於特定聚類的概率。

4.重複步驟2和3進行迭代，直到收斂位置。重複迭代，其分布並沒有太大變化。

GMM演算法有兩大優勢。首先，GMM演算法比K-Means演算法在聚類協方差上具有更高的靈活性。根據標準差的參數不同，集群是任何形狀的橢圓，而不限於圓形。K-Means實際上是GMM演算法的一個特例，其中每個聚類的協方差在所有維度上都近似。其次，由於GMM演算法使用概率，每個數據點都可以有多個聚類。因此，如果一個數據點位於兩個重疊的聚類中間，我們可以簡單地將其定義為類，即有X%的概率屬於1類和Y%的概率屬於2類。

合成聚類演算法-AHC

合成聚類演算法分為兩大類：自上而下或自下而上。自下而上演算法首先將每個數據點視為單個聚類，然後連續的合併（聚合）成對的聚類，直到所有的聚類合併成包含所有數據點的一個單個聚類。因此，自下而上的分層聚類被稱為合成聚類演算法或AHC。聚類的層用樹（樹狀圖）表示，樹的根是收集所有樣本的唯一聚類，葉子是只有一個樣本的聚類。圖解如下：

1.首先將每個數據點視為一個單一聚類，即如果數據集中有X個聚類。然後，我們選擇一個度量測量兩個聚類之間的距離。在本例中，我們使用平均連接，它將兩個聚類間的距離定義為第一個數據集中的數據點和第二個聚類中數據點之間的平均距離。

2.每迭代一次，將兩個聚類合併成為一個，作為平均連接最小的聚類。根據我們選擇的聚類度量，這兩個聚類間的距離最小，因此最相似，則應該合併起來。

3.重複步驟2直到遍歷到樹的根，即包含所有數據點的唯一一個聚類。通過這種方式，我們可以根據最後需要多少聚類，只需選擇何時停止組合聚類，即何時停止構建樹。

合成聚類演算法不需要指定聚類的數量，甚至可以選擇哪個數量的聚類最好。另外，該演算法對距離度量的選擇並不敏感，而對於其他演算法來說，距離度量的選擇至關重要。