Must Know！數據科學家們必須知道的 5 種聚類演算法

知識 03-13

本文為雷鋒字幕組編譯的技術博客，原標題 The 5 Clustering Algorithms Data Scientists Need to Know，作者為 George Seif。

翻譯 | 姜波整理 | 凡江吳璇

聚類是一種關於數據點分組的機器學習技術。給出一組數據點，我們可以使用聚類演算法將每個數據點分類到特定的組中。理論上，同一組中的數據點應具有相似的屬性或特徵，而不同組中的數據點應具有相當不同的屬性或特徵（即類內差異小，類間差異大）。聚類是一種無監督學習方法，也是一種統計數據分析的常用技術，被廣泛應用於眾多領域。

在數據科學中，我們可以通過聚類演算法，查看數據點屬於哪些組，並且從這些數據中獲得一些有價值的信息。今天，我們一起來看看數據科學家需要了解的 5 種流行聚類演算法以及它們的優缺點。

一、K 均值聚類

K-Means 可能是最知名的聚類演算法了。在數據科學或機器學習課程中都有過它的介紹。K-Means 的代碼也非常容易理解和實現。請查看下面的圖片：

開始，我們先選取一些類型或者組類，分別隨機初始化它們的中心點。要計算出使用的類的數量，最好快速查看數據並嘗試識別不同的分組。中心點是與每個數據點向量長度相同的向量，並且是上圖中的『X』s』。

每一個數據點，是通過計算該點與每一組中的點之間的距離，來進行分類的，然後將該點歸類到距離中心最近的組。

基於這些分類的點，我們通過求取每一組中所有向量的均值，重複計算每一組的中心點。

重複上述步驟，直到每一組的中心點不再發生變化或者變化不大為止。你也可以選擇對組中心點進行多次隨機初始化，選擇運行效果最好的即可。

由於我們所做的只是計算點和組中心之間的距離，計算量較小，因此 K-Means 的一大優點就是運行速度非常快。所以它具有線性複雜度 O(n）。

當然，K-Means 也有兩個缺點。首先，你必須選擇有分類組的數目（如聚為 3 類，則 K=3）。這並不能忽略，理想情況下，我們希望它使用聚類演算法來幫助我們理解這些數據，因為它的重點在於從數據中獲得一些有價值的發現。由於 K-means 演算法選擇的聚類中心是隨機的（即初始化是隨機的），因此它可能會因為類數不同而運行演算法中產生不同的聚類結果。因此，結果可能不可重複且缺乏一致性。相反，其他集群方法更一致。

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

二、Mean-Shift 聚類

平均移位聚類是基於滑動窗口的演算法，試圖找到密集的數據點區域。這是一種基於質心的演算法，意味著目標是定位每個組 / 類的中心點，通過更新中心點的候選點作為滑動窗口內點的平均值來工作。然後在後處理（相對『預處理』來說的）階段對這些候選窗口進行濾波以消除近似重複，形成最終的中心點集及其相應的組。請查看下面的圖片：

Mean-Shift 聚類用於單個滑動窗口

為了解釋平均偏移，我們將考慮像上圖那樣的二維空間中的一組點。我們從以 C 點（隨機選擇）為中心並以半徑 r 為核心的圓滑動窗口開始。平均偏移是一種爬山演算法，它涉及將這個核迭代地轉移到每個步驟中更高密度的區域，直到收斂。

在每次迭代中，通過將中心點移動到窗口內的點的平均值（因此得名），將滑動窗口移向較高密度的區域。滑動窗口內的密度與其內部的點數成正比。當然，通過轉換到窗口中的點的平均值，它將逐漸走向更高點密度的區域。

我們繼續根據平均值移動滑動窗口，直到沒有方向移位可以在內核中容納更多點。看看上面的圖片; 我們繼續移動該圓，直到我們不再增加密度（即窗口中的點數）。

步驟 1 至 3 的這個過程用許多滑動窗口完成，直到所有點位於一個窗口內。當多個滑動窗口重疊時，保留包含最多點的窗口。數據點然後根據它們所在的滑動窗口聚類。

下面顯示了所有滑動窗口從頭到尾的整個過程的說明。每個黑點代表滑動窗口的質心，每個灰點代表一個數據點。

Mean-Shift 聚類的整個過程

與 K 均值聚類相比，不需要選擇聚類數量，因為均值偏移可以自動發現。這是一個巨大的優勢。聚類中心向最大密度點聚合的結果也是非常令人滿意的，因為它的理解比較符合數據驅動的規律，且十分直觀。缺點是窗口大小 / 半徑 r 的選擇是非常重要的，換句話說半徑的選擇決定了運行結果。

三、基於密度的雜訊應用空間聚類（DBSCAN）

http://suo.im/3r9b56

http://suo.im/1JQmbi

http://suo.im/12XwkZ

DBSCAN 以任何尚未訪問過的任意起始數據點開始。這個點的鄰域用距離 epsilon 提取（ε距離內的所有點都是鄰域點）。

如果在該鄰域內有足夠數量的點（根據 minPoints），則聚類過程將開始並且當前數據點將成為新聚類中的第一個點。否則，該點將被標記為雜訊（稍後，這個雜訊點可能會成為群集的一部分）。在這兩種情況下，該點都被標記為「已訪問」。

對於新簇中的第一個點，ε距離鄰域內的點也成為同一個簇的一部分。然後對已經添加到群集組中的所有新點重複使ε鄰域中的所有點屬於同一個群集的過程。

重複步驟 2 和 3 的這個過程直到聚類中的所有點都被確定，即聚類的ε鄰域內的所有點都被訪問和標記。

一旦我們完成了當前的集群，一個新的未訪問點被檢索和處理，導致發現更多的集群或雜訊。重複此過程，直到所有點都被標記為已訪問。由於所有點已經被訪問完畢，每個點都被標記為屬於一個簇或是雜訊。

與其他聚類演算法相比，DBSCAN 具有一些很大的優勢。首先，它根本不需要 pe-set 數量的簇。它還將異常值識別為雜訊，而不像 mean-shift，即使數據點非常不同，它們也會將它們引入群集中。另外，它能夠很好地找到任意大小和任意形狀的簇。

DBSCAN 的主要缺點是，當簇的密度不同時，DBSCAN 的性能不如其他組織。這是因為當密度變化時，用於識別鄰近點的距離閾值ε和 minPoints 的設置將隨著群集而變化。對於非常高維的數據也會出現這種缺點，因為距離閾值ε再次難以估計。

四、使用高斯混合模型（GMM）的期望最大化（EM）聚類

K-Means 的主要缺點之一是其使用了集群中心的平均值。通過查看下面的圖片，我們可以明白為什麼這不是選取聚類中心的最佳方式。在左側，人眼看起來非常明顯的是，有兩個半徑不同的圓形星團以相同的平均值為中心。K-Means 無法處理這個問題，因為這些集群的平均值非常接近。K-Means 在集群不是圓形的情況下也會出錯，這也是因為使用均值作為集群中心的原因。

K-Means 的兩個失敗案例

高斯混合模型（GMMs）比 K-Means 更具靈活性。對於 GMM，我們假設數據點是高斯分布的。這是一個限制較少的假設，而不是用均值來表示它們是循環的。這樣，我們有兩個參數來描述群集的形狀，均值和標準差。以二維數據為例，這意味著群集可以採取任何類型的橢圓形（因為我們在 x 和 y 方向都有標準偏差）。因此，每個高斯分布被分配給單個集群。

為了找到每個群集的高斯參數（例如平均值和標準偏差），我們將使用期望最大化（EM）的優化演算法。看看下面的圖表，作為適合群集的高斯圖的例證。然後我們可以繼續進行使用 GMM 的期望最大化聚類過程

使用 GMM 的 EM 聚類

我們首先選擇簇的數量（如 K-Means）並隨機初始化每個簇的高斯分布參數。人們可以嘗試通過快速查看數據來為初始參數提供良好的假設。請注意，這不是 100％必要的，因為開始時高斯分布化非常弱，雖然從上圖可以看出，但隨著演算法的運行很快就能得到優化。

給定每個群集的這些高斯分布，計算每個數據點屬於特定群集的概率。一個點越接近高斯中心，它越可能屬於該群。這應該是直觀的，因為對於高斯分布，我們假設大部分數據更靠近集群的中心。

基於這些概率，我們為高斯分布計算一組新的參數，以便使集群內數據點的概率最大化。我們使用數據點位置的加權和來計算這些新參數，其中權重是屬於該特定群集中的數據點的概率。為了以可視化的方式解釋這一點，我們可以看看上面的圖片，特別是黃色的群集。分布從第一次迭代開始隨機開始，但我們可以看到大部分黃點都在該分布的右側。當我們計算一個按概率加權的和時，即使中心附近有一些點，它們中的大部分都在右邊。因此，分配的均值自然會更接近這些點的集合。我們也可以看到，大部分要點都是「從右上到左下」。因此，標準偏差改變以創建更適合這些點的橢圓，以便最大化由概率加權的總和。

步驟 2 和 3 迭代地重複直到收斂，其中分布從迭代到迭代的變化不大。

使用 GMM 有兩個關鍵優勢。首先 GMM 比 K-Means 在群協方面更靈活。由於標準偏差參數，集群可以採取任何橢圓形狀，而不是限於圓形。K 均值實際上是 GMM 的一個特例，其中每個群的協方差在所有維上都接近 0。其次，由於 GMM 使用概率，每個數據點可以有多個群。因此，如果一個數據點位於兩個重疊的簇的中間，我們可以簡單地定義它的類，將其歸類為類 1 的概率為百分之 x，類 2 的概率為百分之 y。

五、凝聚層次聚類

分層聚類演算法實際上分為兩類：自上而下或自下而上。自下而上演算法首先將每個數據點視為單個群集，然後連續合併（或聚合）成對的群集，直到所有群集合併成包含所有數據點的單個群集。自下而上的層次聚類因此被稱為分層凝聚聚類或 HAC。該簇的層次結構被表示為樹（或樹狀圖）。樹的根是收集所有樣本的唯一聚類，葉是僅有一個樣本的聚類。在進入演算法步驟之前，請查看下面的圖解。

凝聚層次聚類

我們首先將每個數據點視為一個單一的聚類，即如果我們的數據集中有 X 個數據點，則我們有 X 個聚類。然後我們選擇一個度量兩個集群之間距離的距離度量。作為一個例子，我們將使用平均關聯，它將兩個集群之間的距離定義為第一個集群中的數據點與第二個集群中的數據點之間的平均距離。

在每次迭代中，我們將兩個群集合併成一個群集。將要組合的兩個群被選為平均聯繫最小的群。即根據我們選擇的距離度量，這兩個群集之間的距離最小，因此是最相似的，應該結合起來。

重複步驟 2 直到我們到達樹的根部，即我們只有一個包含所有數據點的聚類。通過這種方式，我們可以最終選擇我們想要的簇數量，只需選擇何時停止組合簇，即停止構建樹。

分層聚類不需要我們指定聚類的數量，我們甚至可以選擇哪個數量的聚類看起來最好，因為我們正在構建一棵樹。另外，該演算法對距離度量的選擇不敏感; 他們都傾向於工作同樣好，而與其他聚類演算法，距離度量的選擇是至關重要的。分層聚類方法的一個特別好的用例是基礎數據具有層次結構並且您想要恢復層次結構; 其他聚類演算法無法做到這一點。與 K-Means 和 GMM 的線性複雜性不同，這種層次聚類的優點是以較低的效率為代價，因為它具有 O（n3）的時間複雜度。

結論

數據科學家應該知道的這 5 個聚類演算法！我們將期待一些其他的演算法的執行情況以及可視化，敬請期待 Scikit Learn！