5種演算法玩轉聚類分析

5種演算法玩轉聚類分析

22 人贊了文章

聚類是一種涉及數據點分組的機器學習技術。給定一組數據點，我們可以使用聚類演算法將每個數據點分類到特定的組中。理論上，同一組中的數據點應具有相似的屬性或特徵，而不同組中的數據點應具有較大差異的屬性或特徵。聚類是無監督學習的一種方法，也是用於許多領域中統計數據分析的常用技術。

在數據科學中，通過使用聚類分析，查看數據點在應用聚類分析演算法時所對應的分類，從而挖掘出數據隱藏的信息。今天，我們將討論數據科學家需要了解的5種流行聚類演算法以及它們的優缺點！

1.K-Means聚類

K-Means可能是我們最熟知的聚類演算法之一。它在很多介紹性的數據科學和機器學習課程中出現過。因為很容易理解並且容易用代碼實現，如下所示。

1、我們首先選擇若干簇，並隨機初始化他們各自的中心點。為了計算出需要使用的簇的數量，最好是快速地瀏覽數據並嘗試識別所有獨特的分組。中心點是與數據點矢量有相同維數的向量，如上圖中的「X」。

2、對於每個數據點，通過計算該點與每個簇中心點之間的距離，按照距離最小的原則進行分類，將該點歸類到距離最近的簇中。

3、基於這些分類點，重新計算簇中的所有向量的平均值，確定新的中心點。

4、重複迭代這些步驟若干次，或者直到各組的中心點在兩次迭代之間變化不大時停止迭代。也可以選擇隨機初始化簇中心若干次，然後選擇效果最好的分類結果。

K-Means的優點是運算速度非常快，因為我們所做的只是計算點和簇中心之間的距離（這是非常少的計算！），因此它有線性複雜度O（n）。

另一方面，K-Means有兩個缺點。首先，必須設置簇的數量，這對聚類演算法來說並不簡單。我們希望它自己找出這些答案，因為聚類演算法目的就是從數據中獲得隱藏信息。此外，K-Means演算法從隨機選擇的聚類中心開始執行，它可能在演算法的不同運行過程中產生不同的聚類結果。這可能會導致結果無法復現且缺乏一致性。而其他聚類方法則相對具有較高的一致性。

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

2.均值漂移聚類

Mean-Shift聚類是基於滑動窗口的演算法，試圖找到數據點的密集區域。這是一種基於質心的演算法，意味著其目標是定位每個簇的中心點，通過將滑動窗口的均值點作為候選點來迭代更新中心點。在後處理階段將消除近似重複的窗口，最終形成一組中心點及其相應的簇。如下所示。

1、為了解釋Mean-Shift，我們將考慮如上圖所示的二維空間中的一組點。我們從圓形滑動窗口為核心開始，其以C點（隨機選擇）為中心並以r半徑。Mean-Shift是一種爬山演算法（局部擇優的方法），它在每個步驟中將核迭代地轉移到更高密度的區域，直到收斂。

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

3、我們繼續根據平均值移動滑動窗口，直到無法通過移動使內核中容納更多的點。如上圖所示; 我們不斷移動這一圓形，直到密度（即窗口中的點數）不再增加。

4、步驟1至3的這個過程用許多滑動窗口完成，直到所有點均落到某一個窗口內。當多個滑動窗口重疊時，保留包含最多點的窗口。然後根據數據點所在的滑動窗口將其聚為一類。

下圖顯示了包含所有滑動窗口的整個過程。每個黑點代表滑動窗口的質心，每個灰點代表一個數據點。

與K-means聚類相比，Mean-Shift的最大優勢就是可以自動發現簇的數量而不需要人工選擇。簇的中心向最大密度點聚合的事實也是非常令人滿意的，因為它可被非常直觀地理解並很自然地契合數據驅動。當然不足就是窗口大小/半徑「r」的選擇可能是非平凡的。

3.具雜訊基於密度的空間聚類演算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一種基於密度的聚類演算法，類似於Mean-Shift，但具有一些顯著的優點。如下圖所示。

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

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

3、對於新簇中的第一個點，ε鄰域內的點也成為同一個簇的一部分。之後對已經添加到簇中的所有新點重複執行這一過程，即將ε鄰域中的所有點歸到同一個簇內。

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

5、當我們完成了對當前簇的操作，則會檢索和處理一個新的未訪問點，這樣可發現更多的集群或雜訊。重複此過程，直到所有點都被標記為「已訪問」。由於所有點已經被訪問完畢，每個點都被標記為歸屬於一個簇或是雜訊。

與其他聚類演算法相比，DBSCAN有很多優點。 首先，它根本不需要預先設定簇的數量。它還能將異常值識別為雜訊，而不是像Mean-Shift那樣將數據點簡單地扔進一個簇中，不管數據之間是否有很大的差異。另外，它能夠很好地找到任意大小和任意形狀的簇。

DBSCAN的主要缺點是當簇的密度不同時，DBSCAN的性能不如其他的聚類演算法。因為當密度變化時，用於識別鄰近點的距離閾值ε和minPoints也將隨著簇的變化而變化。同樣對較高維數據的處理時也會存在距離閾值ε難以估計的缺陷。

4.高斯混合模型的期望最大化聚類

K-Means的主要缺點之一是其簡單地使用了平均值作為簇的中心。

通過下圖，我們可以看出為什麼這不是最佳方式。在左側，人的眼睛可以明顯地看到有兩個半徑不同的圓形簇以相同的平均值為中心。

由於這些簇的均值非常接近，導致K-Means無法處理這個問題。 K-Means在簇不是圓形的情況下也會失效，這也是因為它使用均值作為簇的中心。

高斯混合模型（GMMs）相比於K-Means來說有更多的靈活性。

對於GMMs，我們假設數據點是服從高斯分布的（對於用均值進行聚類，這一假設是個相對較弱的限制）。

這樣，我們有兩個參數來描述簇的形狀：均值和標準差！ 以二維為例，這意味著簇可以採用任何類型的橢圓形（因為我們在x和y方向都有標準偏差）。

因此，每個簇都有一個高斯分布。

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

1、我們首先選擇簇的數量（如K-Means）並隨機初始化每個簇的高斯分布參數。人們也可以嘗試通過快速瀏覽數據來猜測一個較好的初始參數。但從上圖可以看出這不是必要的，因為雖然高斯擬合雖然開始時效果很差，但很快就得到了優化。

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

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

4、迭代地重複步驟2和3直到收斂，當分布在兩次迭代中變化不大時停止。

使用GMMs有兩個關鍵優勢。首先GMMs在簇的協方差方面比K-Means更靈活，由於含有標準差參數，簇可以採取任何橢圓形狀，而不僅限於圓形。K-Means實際上是GMMs的一個特例，其中每個簇的協方差在所有維度上都接近0。其次，由於GMMs使用了概率，每個數據點可以有多個簇。因此，如果一個數據點位於兩個重疊的簇的中間，我們可以簡單地定義它的簇，X%屬於簇1且Y%屬於簇2。即GMMs支持混合的成員資格。

5.凝聚層次聚類

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

1、我們首先將每個數據點視為一個單一的簇，即如果我們的數據集中有X個數據點，則有X個簇。然後選擇一個度量來確定兩個簇之間的距離。使用平均連接（average linkage）作為例子來定義兩個簇之間的距離，即第一個簇內的點與第二個簇內的點的平均距離。

2、在每次迭代中，我們將兩個簇合併成一個簇。選出的兩個簇為平均連接最小的簇。即根據我們選擇的距離度量，這兩個簇之間的距離最小，因此是最相似的，應該被合併起來。

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

分層聚類不要求我們指定聚類的數量，因為我們在構建一棵樹，我們甚至可以選擇哪個數量的簇看起來最好。另外，該演算法對距離度量的選擇不敏感，它們的效果都趨於相同，而對其他聚類演算法而言，距離度量的選擇則是至關重要的。

分層聚類方法的一個特別好的應用是源數據具有層次結構並且用戶想要恢復其層次結構，其他聚類演算法則無法做到這一點。這種層次聚類是以較低的效率為代價實現的，與K-Means和GMM的線性複雜性不同，它具有O（n3）的時間複雜度。

總結

這是數據科學家應該知道的top5的聚類演算法！我們將用一個展現這些演算法性能的圖來結束本文。向Scikit學習！

翻譯：非線性

審校：wanting

原文地址：

https://www.kdnuggets.com/2018/06/5-clustering-algorithms-data-scientists-need-know.html

---

關注集智AI學園公眾號

獲取更多更有趣的AI教程吧！

搜索微信公眾號：swarmAI

集智AI學園QQ群：426390994

學園網站：http://campus.swarma.org

商務合作和投稿轉載｜swarma@swarma.org

推薦閱讀：