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

來自專欄論智

作者：George Seif

編譯：Bot

編者按：聚類是一種涉及數據點分組的機器學習技術。給定一組數據點，我們可以使用聚類演算法將每個數據點到分類到圖像中的特定組中。理論上，同一組中的數據點應具有相似的屬性和特徵，而不同組中的數據點的屬性和特徵則應高度不同。聚類是無監督學習的一種方法，是用於多領域統計數據分析的常用技術。

在數據科學中，我們可以通過聚類分析觀察使用聚類演算法後這些數據點分別落入了哪個組，並從中獲得一些有價值的信息。那麼今天，我們就跟著機器學習工程師George Seif來看看數據科學家需要掌握的5種實用聚類演算法以及它們的優缺點。

K-Means聚類

K-Means（k-平均或k-均值）可以稱的上是知名度最高的一種聚類演算法，它常出現在許多有關數據科學和機器學習的課程中。在代碼中非常容易理解和實現！讓我們來看下面這幅動圖。

1. 首先，我們確定要幾個的聚類（cluster，也稱簇），並為它們隨機初始化一個各自的聚類質心點（cluster centroids），它在上圖中被表示為「X」。要確定聚類的數量，我們可以先快速看一看已有的數據點，並從中分辨出一些獨特的數據。
2. 其次，我們計算每個數據點到質心的距離來進行分類，它跟哪個聚類的質心更近，它就被分類到該聚類。
3. 需要注意的是，初始質心並不是真正的質心，質心應滿足聚類里每個點到它的歐式距離平方和最小這個條件。因此根據這些被初步分類完畢的數據點，我們再重新計算每一聚類中所有向量的平均值，並確定出新的質心。
4. 最後，重複上述步驟，進行一定次數的迭代，直到質心的位置不再發生太大變化。當然你也可以在第一步時多初始化幾次，然後選取一個看起來更合理的點節約時間。

K-Means的優點是速度非常快，因為我們所做的只是計算數據點和質心點之間的距離，涉及到的計算量非常少！因此它的演算法時間複雜度只有O(n)。

另一方面，K-Means有兩個缺點。一是你必須一開始就決定數據集中包含多少個聚類。這個缺點並不總是微不足道的，理想情況下，我們的目標其實是用一種演算法來分類這些數據，並從結果中觀察出一些規律，而不是限制幾個條件強行聚類。二是一開始質心點的選取是隨機的，演算法可能會初始化出差異巨大的點。這個缺點導致的結果是質心點的位置不可重複且缺乏一致性。

K-Medians是與K-Means相關的另一種聚類演算法，不同之處在於它使用簇的中值向量來重新計算質心點。該方法對異常值不敏感（因為使用中值），但在較大數據集上運行時速度會慢很多，因為每次計算中值向量，我們都要重新排序。

Mean-Shift聚類

Mean shift演算法，又稱均值漂移演算法，這是一種基於核密度估計的爬山演算法，可用於聚類、圖像分割、跟蹤等。它的工作原理基於質心，這意味著它的目標是定位每個簇/類的質心，即先算出當前點的偏移均值，將該點移動到此偏移均值，然後以此為新的起始點，繼續移動，直到滿足最終的條件（找出最密集的區域）。如果沒理解，請看下圖。

1. 為了理解均值漂移，我們可以像上圖一樣想像二維空間中的一組數據點，然後先隨機選擇一個點C，以它為圓心畫一個半徑為r的圓開始移動。之前提到了，這是個爬山演算法，它的核函數會隨著迭代次數增加逐漸向高密度區域靠近。
2. 在每輪迭代中，演算法會不斷計算圓心到質心的偏移均值，然後整體向質心靠近。漂移圓圈內的密度與數據點數成正比。到達質心後，演算法會更新質心位置，並繼續讓圓圈向更高密度的區域靠近。
3. 當圓圈到達目標質心後，它發現自己無論朝哪個方向漂移都找不到更多的數據點，這時我們就認為它已經處於最密集的區域。
4. 這時，演算法滿足了最終的條件，即退出。

這裡我們主要介紹了一個漂移圓圈的思路，如下圖所示，其實Mean shift演算法事實上存在多個圓形區域，圖中黑點代表質心，而灰點則是數據點。

和K-Means演算法相比，Mean-Shift不需要實現定義聚類數量，因為這些都可以在計算偏移均值時得出。這是一個巨大的優勢。同時，演算法推動聚類中心在向密度最大區域靠近的效果也非常令人滿意，這一過程符合數據驅動型任務的需要，而且十分自然直觀。如果要說Mean-Shift有什麼缺點，那就是對高維球區域的半徑r的定義，不同選擇可能會產生高度不同的影響。

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

DBSCAN是一種基於密度的聚類演算法，它與mean-shift類似，但又有一些顯著優勢。我們先來看看下面這幅花哨的圖。

1. 首先，DBSCAN演算法會以任何尚未訪問過的任意起始數據點為核心點，並對該核心點進行擴充。這時我們給定一個半徑/距離ε，任何和核心點的距離小於ε的點都是它的相鄰點。
2. 如果核心點附近有足夠數量的點，則開始聚類，且選中的核心點會成為該聚類的第一個點。如果附近的點不夠，那演算法會把它標記為雜訊（之後這個雜訊可能會成為簇中的一部分）。在這兩種情形下，選中的點都會被標記為「已訪問」。
3. 一旦聚類開始，核心點的相鄰點，或者說以該點出發的所有密度相連的數據點（注意是密度相連）會被劃分進同一聚類。然後我們再把這些新點作為核心點，向周圍拓展ε，並把符合條件的點繼續納入這個聚類中。
4. 重複步驟2和3，直到附近沒有可以擴充的數據點為止，即簇的ε鄰域內所有點都已被標記為「已訪問」。
5. 一旦我們完成了這個集群，演算法又會開始檢索未訪問過的點，並發現更多的聚類和雜訊。一旦數據檢索完畢，每個點都被標記為屬於一個聚類或是雜訊。

與其他聚類演算法相比，DBSCAN有一些很大的優勢。首先，它不需要輸入要劃分的聚類個數。其次，不像mean-shift，即使數據點非常不同，它也會將它們納入聚類中，DBSCAN能將異常值識別為雜訊，這就意味著它可以在需要時輸入過濾雜訊的參數。第三，它對聚類的形狀沒有偏倚，可以找到任意大小和形狀的簇。

DBSCAN的主要缺點是，當聚類的密度不同時，DBSCAN的性能會不如其他演算法。這是因為當密度變化時，用於識別鄰近點的距離閾值ε和核心點的設置會隨著聚類發生變化。而這在高維數據中會特別明顯，因為屆時我們會很難估計ε。

EM聚類

均值→質心，方差→橢圓聚類，權重→聚類大小。

K-Means演算法的主要缺點之一是它直接用了距離質心的平均值。我們可以從下圖中看出這樣做為什麼不好——圖的左側是兩個半徑不同的同心圓，K-Means沒法處理這個問題，因為這些聚類的平均值非常接近；圖的右側是一個中心對稱的非圓形分布，K-Means同樣解決不了它，因為如果單純依靠均值判斷，演算法無法捕捉更多特徵。

高斯混合模型（GMM）比K-Means演算法具有更好的靈活性。它是多個高斯分布函數的線性組合，理論上可以擬合出任意類型的分布，通常用於解決同一集合下的數據包含多個不同的分布的情況。對於GMM，我們假設數據點滿足不同參數下的高斯分布——比起均值，這是一個限制較少的假設。我們用兩個參數來描述聚類的形狀：均值和標準差！以二維分布為例，標準差的存在允許聚類的形狀可以是任何種類的橢圓形。因此這個演算法的思想是：如果數據點符合某個高斯分布，那它就會被歸類為那個聚類。

為了找到每個聚類的高斯參數，我們要用到一種名為期望最大化（EM）的優化演算法。下圖是高斯混合模型的聚類過程，那麼，你知道怎麼在其中運用EM演算法嗎？

1. 首先，我們確定聚類的數量（如K-Means），並隨機初始化每個聚類的高斯分布參數。你也可以嘗試通過快速查看數據來為初始參數提供更好的猜測，但從上圖可以看出，這其實不是很必要，因為演算法會很快進行優化。
2. 其次，根據每個聚類的高斯分布，計算數據點屬於特定聚類的概率。如果數據點越接近高斯質心，那它屬於該聚類的概率就越高。這很直觀，因為對於高斯分布，我們一般假設大部分數據更靠近聚類質心。
3. 在這些概率的基礎上，我們為高斯分布計算一組新的參數，使聚類內數據點的概率最大化。我們用數據點位置的加權和來計算這些新參數，其中權重就是數據點屬於聚類的概率。為了可視化這個過程，我們可以看看上面的圖片，特別是黃色的聚類。第一次迭代中，它是隨機的，大多數黃點都集中在該聚類的右側。當我們按概率計算加權和後，雖然聚類的中部出現一些點，但右側的比重依然很高。隨著迭代次數增加，黃點在聚類中的位置也完成了「右下→左下」的移動。因此，標準差的變化調整著聚類的形狀，以使它能更適合數據點的分布。
4. 迭代步驟2和步驟3，直至收斂。

論智註：對於上述第3步，請結合混合高斯模型定義公式理解。如果我們設K為模型的個數，πk為第k個高斯的權重，即第k個高斯的概率密度函數，其均值為μk，方差為σk。我們對此概率密度的估計就是要求πk、μk和σk各個變數。當求出的表達式後，求和式的各項的結果就分別代表樣本x屬於各個類的概率。在做參數估計的時候，常採用的方法是最大似然。——引自 姜文暉《聚類(1)——混合高斯模型》

GMM有兩個關鍵優勢。首先它比K-Means更靈活，由於標準差的引入，最後聚類的形狀不再局限於圓形，它還可以是大小形狀不一的橢圓形——K均值實際上是GMM的一個特例，其中每個聚類的協方差在所有維上都接近0。其次，權重的引入為同一點屬於多個聚類找到了解決方案。如果一個數據點位於兩個聚類的重疊區域，那我們就可以簡單為它定義一個聚類，或者計算它屬於X聚類的百分比是多少，屬於Y聚類的百分比是多少。簡而言之，GMM支持混合「成員」。

談及缺點，和K-Means相比，GMM每一步迭代的計算量比較大。另外，它的求解辦法基於EM演算法，因此有可能陷入局部極值，需要經過多次迭代。

層次聚類

層次聚類實際上可以被分為兩類：自上而下和自下而上。其中自下而上演算法（Bottom-up algorithms）首先會將每個數據點視為單個聚類，然後連續合併（或聚合）成對的聚類，直到所有聚類合併成包含所有數據點的單個聚類。它也因此會被稱為hierarchical agglomerative clustering 或HAC。該演算法的聚類可以被表示為一幅樹狀圖，樹根是最後收納所有數據點的單個聚類，而樹葉則是只包含一個樣本的聚類。在講解具體步驟前，我們先看看整個過程的圖解。

1. 首先，我們把每個數據點看作是一個聚類，即如果數據集中有X個數據點，它就有X個聚類。然後我們設置一個閾值作為衡量兩個聚類間距離的指標：如果距離小於閾值，則合併；如果距離大於閾值，迭代終止。
2. 在每輪迭代中，我們會把兩個聚類合併成一個聚類。這裡我們可以用到average linkage，它的思路是計算所有分屬於兩個目標聚類的數據點之間距離，然後求一個平均值。每次我們會根據設定的閾值選取平均距離最小的兩個聚類，然後把它們合併起來，因為按照我們的標準，它們是最相似的。
3. 重複步驟2，直到我們到達樹根，即最後只有一個包含所有數據點的聚類。通過這種方式，我們可以選擇要幾個聚類，以及什麼時候停止聚類。

層次聚類不要求我們指定聚類的數量，由於這是一個構建樹的過程，我們甚至可以選擇那種聚類看起來更合適。另外，該演算法對距離閾值的選擇不敏感，無論怎麼定，演算法始終會傾向於給出更好地聚類結果，而不像其他演算法很依賴參數。根據層次聚類的特點，我們可以看出它非常適合具有層次結構的數據，尤其是當你的目標是為數據恢復層次時。這一點是其他演算法無法做到的。與K-Means和GMM的線性複雜性不同，層次聚類的優勢是以較低的效率為代價，因為它具有O(n3)的時間複雜度。

結論

以上就是數據科學家需要知道的5個聚類方法。在文章的最後，就讓我們以一幅聚類圖做結，直觀展示這些演算法和其他演算法的表現！