【IT168 資訊】聚類是一種涉及數據點分組的機器學習技術。給定一組數據點，我們可以使用聚類算法將每個數據點分類到一個特定的組中。理論上，屬於同一組的數據點應具有相似的屬性和特徵，而不同組中的數據點應具有高度不同的屬性和特徵。聚類是無監督學習的一種方法，是在許多領域使用統計數據分析的常用技術。
在數據科學中，我們可以使用聚類分析，通過在應用聚類算法時查看數據點落入哪些組，從數據中獲得一些有價值的見解。今天，我們將看看數據科學家需要知道的5種流行的聚類算法以及它們的優缺點!
K均值(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-means 聚類相比，不需要選擇聚類數量，因為均值偏移能自動發現這一點。這是一個巨大的優勢。聚類中心向最大密度點聚合的事實也是非常理想的，因為它理解和符合自然數據驅動的意義是非常直觀的。缺點是窗口大小/半徑「r」的選擇可能是不重要的。
基於密度的噪聲應用空間聚類(DBSCAN)
DBSCAN是一種基於密度的聚類算法，類似於均值偏移，但具有一些顯著的優點。看看下面的另一個圖表，讓我們開始吧!
▲DBSCAN笑臉集群
1.DBSCAN從一個沒有被訪問的任意開始數據點開始。這個點的鄰域是利用距離epsilon提取的(ε距離內的所有點都是鄰域點)。
2.如果在該鄰域內有足夠數量的點(根據minPoints)，則聚類過程開始，並且當前數據點成為新聚類中的第一個點。否則，該點將被標記為噪聲(稍後會介紹，這個噪聲點可能成為群集的一部分)。在這兩種情況下，該點被標記為「已訪問」。
3.在這個新集群中第一個點，它的ε距離鄰域內的點也成為同一個集群的一部分。這個過程使ε鄰域內的所有點屬於同一個集群，然後對剛剛添加到組中的所有新點重複該過程。
4.重複步驟2和3的這個過程直到聚類中的所有點都被確定，即聚類的ε鄰域內的所有點都被訪問和標記。
5.一旦我們完成了當前的集群，一個新的未訪問的點被檢索和處理，導致發現進一步的集群或噪聲。這個過程重複，直到所有點被標記為已訪問。由於所有點已經被訪問完畢，每個點都被標記為屬於一個集群或是噪聲。
與其他聚類算法相比，DBSCAN具有很多優點。首先，它根本不需要固定數量的族群。它還將異常值識別為噪聲，不同於均值偏移，即使數據點非常不同，也會將它們簡單地引入群集中。另外，它能夠很好地找到任意大小和任意形狀的族群。
DBSCAN的主要缺點是，當密度不同時，性能不如其他。這是因為當密度變化時，用於識別鄰近點的距離閾值ε和minPoints的設置將隨著族群而變化。對於非常高維數據也會出現這種缺點，因為距離閾值ε會變得再次難以估計。
使用高斯混合模型(GMM)的期望最大化(EM)聚類
K-Means的主要缺點之一就是它對於聚類中心的平均值進行簡單de使用。通過查看下面的圖片，我們可以明白為什麼這不是最好的方法。在左側，人眼看起來非常明顯，有兩個不同半徑的圓形星團，以相同的平均值為中心。 K-Means不能處理這個，因為這些集群的平均值是非常接近的。 K-Means在集群不是圓形的情況下也失敗了，這是使用均值作為集群中心的結果。
▲K-Means的兩個失敗案例
高斯混合模型(GMMs)比K-Means更靈活。對於GMM，我們假設數據點是高斯分布的，這是一個限制較少的假設，而不是用均值來表示它們是循環的。這樣，我們有兩個參數來描述群集的形狀：均值和標準差!以二維為例，這意味著這些集群可以採取任何類型的橢圓形(因為我們在x和y方向都有標準偏差)。因此，每個高斯分布被分配給單個集群。
為了找到每個群集的高斯參數(例如均值和標準差)，我們將使用稱為期望最大化(EM)的優化算法。請看下面的圖表，作為適合群集的高斯圖的例證。然後我們可以繼續進行使用GMM的期望最大化聚類過程。
1.我們首先選擇的數量(如K-Means)，然後隨機初始化每個集群的高斯分布參數。可以通過快速查看數據來嘗試為初始參數提供一個很好的猜測。但需要注意，從上圖可以看出，這並不是100%必要的。
2.給定每個群集的這些高斯分布，計算每個數據點屬於特定群集的概率。一個點越靠近高斯的中心，它越可能屬於該群。這應該是直觀的，因為使用高斯分布，我們假設的是大部分數據更靠近集群的中心。
3.基於這些概率，我們為高斯分布計算一組新的參數，使得我們最大化群內數據點的概率。我們使用數據點位置的加權來計算這些新參數，其中權重是屬於該特定群集的數據點的概率。為了用視覺的方式解釋這個，我們可以看看上面的圖片，特別是黃色的群集。分布從第一次迭代隨機開始，但是我們可以看到大部分黃點都在分布的右側。當我們計算一個按概率加權的和時，即使中心附近有一些點，它們大部分都在右邊。因此，分配的均值自然就會接近這些點。我們也可以看到，大部分要點都是「從右上到左下」。因此，標準偏差改變，以創建一個更適合這些點的橢圓，以最大化概率加權的總和。
4.步驟2和3重複迭代，直到收斂，分布從迭代到迭代的變化不大。
使用GMM確實有兩個關鍵的優勢。首先，GMM在聚類協方差上比K-Means靈活得多。由於標準偏差參數，集群可以呈現任何橢圓形狀，而不是被限制為圓形。K-Means實際上是GMM的一個特殊情況，其中每個群集的協方差在所有維度都接近0。其次，由於GMM使用概率，每個數據點可以有多個群集。因此，如果一個數據點位於兩個重疊的集群的中間，我們可以簡單地定義它的類，將其歸類為1類，Y類歸屬於2類。例如，GMM支持混合成員。
凝聚層次聚類
分層聚類算法實際上分為兩類：自上而下或自下而上。自下而上的算法首先將每個數據點視為一個單一的聚類，然後連續地合併(或聚合)成對的聚類，直到所有的聚類都合併成一個包含所有數據點的聚類。因此，自下而上的分層聚類被稱為分層凝聚聚類或HAC。這個集群的層次表示為樹(或樹狀圖)。樹的根是收集所有樣本的唯一聚類，葉是僅具有一個樣本的聚類。在進入算法步驟之前，請查看下面的圖解。
我們首先將每個數據點視為一個單一的聚類，即如果我們的數據集中有X個數據點，那麼我們有X個聚類。然後，我們選擇一個度量兩個集群之間距離的距離度量。作為一個例子，我們將使用平均關聯，它將兩個集群之間的距離定義為第一個集群中的數據點與第二個集群中的數據點之間的平均距離。
▲凝聚層次聚類
1.在每次迭代中，我們將兩個集群合併成一個集群。這兩個要組合的組被選為那些平均聯繫最小的組。根據我們選擇的距離度量，這兩個群集之間的距離最小，因此是最相似的，應該結合起來。
2.重複步驟2直到我們到達樹的根，即我們只有一個包含所有數據點的聚類。通過這種方式，我們可以選擇最終需要多少個集群，只需選擇何時停止組合集群，即停止構建樹時。
3.分層聚類不需要我們指定聚類的數量，我們甚至可以選擇哪個數量的聚類看起來最好，因為我們正在構建一棵「樹」。另外，該算法對距離度量的選擇不敏感，所有算法都能很好的工作，而與其他聚類算法，距離度量的選擇是至關重要的。分層聚類方法的一個特別好的用例是基礎數據具有層次結構，並且想要恢復層次結構; 其他聚類算法不能做到這一點。與K-Means和GMM的線性複雜性不同，層次聚類的這些優點是以較低的效率為代價的，因為它具有O(n 3)的時間複雜度。