一、簡要介紹

1、聚類概念
聚類就是按照某個特定標準(如距離準則)把一個數(shù)據(jù)集分割成不同的類或簇，使得同一個簇內(nèi)的數(shù)據(jù)對象的相似性盡可能大，同時不在同一個簇中的數(shù)據(jù)對象的差異性也盡可能地大。即聚類后同一類的數(shù)據(jù)盡可能聚集到一起，不同數(shù)據(jù)盡量分離。

2、聚類和分類的區(qū)別
聚類技術通常又被稱為無監(jiān)督學習，因為與監(jiān)督學習不同，在聚類中那些表示數(shù)據(jù)類別的分類或者分組信息是沒有的。
Clustering (聚類)，簡單地說就是把相似的東西分到一組，聚類的時候，我們并不關心某一類是什么，我們需要實現(xiàn)的目標只是把相似的東西聚到一起。因此，一個聚類算法通常只需要知道如何計算相似度就可以開始工作了，因此 clustering 通常并不需要使用訓練數(shù)據(jù)進行學習，這在Machine Learning中被稱作unsupervised learning (無監(jiān)督學習)。
Classification (分類)，對于一個classifier，通常需要你告訴它“這個東西被分為某某類”這樣一些例子，理想情況下，一個 classifier 會從它得到的訓練集中進行“學習”，從而具備對未知數(shù)據(jù)進行分類的能力，這種提供訓練數(shù)據(jù)的過程通常叫做supervised learning (監(jiān)督學習)。

3、衡量聚類算法優(yōu)劣的標準
不同聚類算法有不同的優(yōu)劣和不同的適用條件。大致上從跟數(shù)據(jù)的屬性（是否序列輸入、維度），算法模型的預設，模型的處理能力上看。具體如下：
1、算法的處理能力：處理大的數(shù)據(jù)集的能力（即算法復雜度）；處理數(shù)據(jù)噪聲的能力；處理任意形狀，包括有間隙的嵌套的數(shù)據(jù)的能力；
2、算法是否需要預設條件：是否需要預先知道聚類個數(shù)，是否需要用戶給出領域知識；
3、算法的數(shù)據(jù)輸入屬性：算法處理的結果與數(shù)據(jù)輸入的順序是否相關，也就是說算法是否獨立于數(shù)據(jù)輸入順序；算法處理有很多屬性數(shù)據(jù)的能力，也就是對數(shù)據(jù)維數(shù)是否敏感，對數(shù)據(jù)的類型有無要求。

1. K-Means(K均值)聚類

算法步驟：
(1) 首先我們選擇一些類/組，并隨機初始化它們各自的中心點。中心點是與每個數(shù)據(jù)點向量長度相同的位置。這需要我們提前預知類的數(shù)量(即中心點的數(shù)量)。
(2) 計算每個數(shù)據(jù)點到中心點的距離，數(shù)據(jù)點距離哪個中心點最近就劃分到哪一類中。
(3) 計算每一類中中心點作為新的中心點。
(4) 重復以上步驟，直到每一類中心在每次迭代后變化不大為止。也可以多次隨機初始化中心點，然后選擇運行結果最好的一個。
下圖演示了K-Means進行分類的過程：

優(yōu)點：
速度快，計算簡便
缺點：
我們必須提前知道數(shù)據(jù)有多少類/組。
K-Medians是K-Means的一種變體，是用數(shù)據(jù)集的中位數(shù)而不是均值來計算數(shù)據(jù)的中心點。
K-Medians的優(yōu)勢是使用中位數(shù)來計算中心點不受異常值的影響；缺點是計算中位數(shù)時需要對數(shù)據(jù)集中的數(shù)據(jù)進行排序，速度相對于K-Means較慢。

2. 均值漂移聚類

均值漂移聚類是基于滑動窗口的算法，來找到數(shù)據(jù)點的密集區(qū)域。這是一個基于質(zhì)心的算法，通過將中心點的候選點更新為滑動窗口內(nèi)點的均值來完成，來定位每個組/類的中心點。然后對這些候選窗口進行相似窗口進行去除，最終形成中心點集及相應的分組。
具體步驟：

確定滑動窗口半徑r，以隨機選取的中心點C半徑為r的圓形滑動窗口開始滑動。均值漂移類似一種爬山算法，在每一次迭代中向密度更高的區(qū)域移動，直到收斂。

每一次滑動到新的區(qū)域，計算滑動窗口內(nèi)的均值來作為中心點，滑動窗口內(nèi)的點的數(shù)量為窗口內(nèi)的密度。在每一次移動中，窗口會想密度更高的區(qū)域移動。

移動窗口，計算窗口內(nèi)的中心點以及窗口內(nèi)的密度，知道沒有方向在窗口內(nèi)可以容納更多的點，即一直移動到圓內(nèi)密度不再增加為止。

步驟一到三會產(chǎn)生很多個滑動窗口，當多個滑動窗口重疊時，保留包含最多點的窗口，然后根據(jù)數(shù)據(jù)點所在的滑動窗口進行聚類。
下圖演示了均值漂移聚類的計算步驟：

下面顯示了所有滑動窗口從頭到尾的整個過程。每個黑點代表滑動窗口的質(zhì)心，每個灰點代表一個數(shù)據(jù)點。

優(yōu)點：（1）不同于K-Means算法，均值漂移聚類算法不需要我們知道有多少類/組。
（2）基于密度的算法相比于K-Means受均值影響較小。
缺點：（1）窗口半徑r的選擇可能是不重要的。

3. 基于密度的聚類方法(DBSCAN)

與均值漂移聚類類似，DBSCAN也是基于密度的聚類算法。
具體步驟：

首先確定半徑r和minPoints. 從一個沒有被訪問過的任意數(shù)據(jù)點開始，以這個點為中心，r為半徑的圓內(nèi)包含的點的數(shù)量是否大于或等于minPoints，如果大于或等于minPoints則改點被標記為central point,反之則會被標記為noise point。

重復1的步驟，如果一個noise point存在于某個central point為半徑的圓內(nèi)，則這個點被標記為邊緣點，反之仍為noise point。重復步驟1，知道所有的點都被訪問過。
優(yōu)點：不需要知道簇的數(shù)量
缺點：需要確定距離r和minPoints

4. 用高斯混合模型（GMM）的最大期望（EM）聚類

K-Means的缺點在于對聚類中心均值的簡單使用。下面的圖中的兩個圓如果使用K-Means則不能作出正確的類的判斷。同樣的，如果數(shù)據(jù)集中的點類似下圖中曲線的情況也是不能正確分類的。

使用高斯混合模型（GMM）做聚類首先假設數(shù)據(jù)點是呈高斯分布的，相對應K-Means假設數(shù)據(jù)點是圓形的，高斯分布（橢圓形）給出了更多的可能性。我們有兩個參數(shù)來描述簇的形狀：均值和標準差。所以這些簇可以采取任何形狀的橢圓形，因為在x，y方向上都有標準差。因此，每個高斯分布被分配給單個簇。
所以要做聚類首先應該找到數(shù)據(jù)集的均值和標準差，我們將采用一個叫做最大期望(EM)的優(yōu)化算法。下圖演示了使用GMMs進行最大期望的聚類過程。

具體步驟：

選擇簇的數(shù)量（與K-Means類似）并隨機初始化每個簇的高斯分布參數(shù)（均值和方差）。也可以先觀察數(shù)據(jù)給出一個相對精確的均值和方差。

給定每個簇的高斯分布，計算每個數(shù)據(jù)點屬于每個簇的概率。一個點越靠近高斯分布的中心就越可能屬于該簇。

基于這些概率我們計算高斯分布參數(shù)使得數(shù)據(jù)點的概率最大化，可以使用數(shù)據(jù)點概率的加權來計算這些新的參數(shù)，權重就是數(shù)據(jù)點屬于該簇的概率。

重復迭代2和3直到在迭代中的變化不大。
GMMs的優(yōu)點：（1）GMMs使用均值和標準差，簇可以呈現(xiàn)出橢圓形而不是僅僅限制于圓形。K-Means是GMMs的一個特殊情況，是方差在所有維度上都接近于0時簇就會呈現(xiàn)出圓形。
（2）GMMs是使用概率，所有一個數(shù)據(jù)點可以屬于多個簇。例如數(shù)據(jù)點X可以有百分之20的概率屬于A簇，百分之80的概率屬于B簇。也就是說GMMs可以支持混合資格。

5. 凝聚層次聚類

層次聚類算法分為兩類：自上而下和自下而上。凝聚層級聚類(HAC)是自下而上的一種聚類算法。HAC首先將每個數(shù)據(jù)點視為一個單一的簇，然后計算所有簇之間的距離來合并簇，知道所有的簇聚合成為一個簇為止。
下圖為凝聚層級聚類的一個實例：

具體步驟：

首先我們將每個數(shù)據(jù)點視為一個單一的簇，然后選擇一個測量兩個簇之間距離的度量標準。例如我們使用average linkage作為標準，它將兩個簇之間的距離定義為第一個簇中的數(shù)據(jù)點與第二個簇中的數(shù)據(jù)點之間的平均距離。

在每次迭代中，我們將兩個具有最小average linkage的簇合并成為一個簇。

重復步驟2知道所有的數(shù)據(jù)點合并成一個簇，然后選擇我們需要多少個簇。
層次聚類優(yōu)點：（1）不需要知道有多少個簇
（2）對于距離度量標準的選擇并不敏感
缺點：效率低

6. 圖團體檢測(Graph Community Detection)

當我們的數(shù)據(jù)可以被表示為網(wǎng)絡或圖是，可以使用圖團體檢測方法完成聚類。在這個算法中圖團體（graph community）通常被定義為一種頂點(vertice)的子集，其中的頂點相對于網(wǎng)絡的其他部分要連接的更加緊密。下圖展示了一個簡單的圖，展示了最近瀏覽過的8個網(wǎng)站，根據(jù)他們的維基百科頁面中的鏈接進行了連接。

模塊性可以使用以下公式進行計算：
M=12L∑Ni,j=1(Aij?kiKj2L)δCi,CjM=12L∑i,j=1N(Aij?kiKj2L)δCi,Cj
其中L代表網(wǎng)絡中邊的數(shù)量，AijAij代表真實的頂點i和j之間的邊數(shù), ki,kjki,kj代表每個頂點的degree，可以通過將每一行每一列的項相加起來而得到。兩者相乘再除以2L表示該網(wǎng)絡是隨機分配的時候頂點i和j之間的預期邊數(shù)。所以Aij?kikj2LAij?kikj2L代表了該網(wǎng)絡的真實結構和隨機組合時的預期結構之間的差。當AijAij為1時，且kikj2Lkikj2L很小的時候，其返回值最高。也就是說，當在定點i和j之間存在一個非預期邊是得到的值更高。
δCi,CjδCi,Cj是克羅內(nèi)克δδ函數(shù)(Kronecker-delta function). 下面是其Python解釋：

def Kronecker_Delta(ci,cj):if ci==cj:return 1else:return 0

通過上述公式可以計算圖的模塊性，且模塊性越高，該網(wǎng)絡聚類成不同團體的程度越好，因此通過最優(yōu)化方法尋找最大模塊性就能發(fā)現(xiàn)聚類該網(wǎng)絡的最佳方法。
組合學告訴我們對于一個僅有8個頂點的網(wǎng)絡，就存在4140種不同的聚類方式，16個頂點的網(wǎng)絡的聚類方式將超過100億種。32個頂點的網(wǎng)絡的可能聚類方式更是將超過10^21種。因此，我們必須尋找一種啟發(fā)式的方法使其不需要嘗試每一種可能性。這種方法叫做Fast-Greedy Modularity-Maximization(快速貪婪模塊性最大化)的算法，這種算法在一定程度上類似于上面描述的集聚層次聚類算法。只是這種算法不根據(jù)距離來融合團體，而是根據(jù)模塊性的改變來對團體進行融合。
具體步驟：

首先初始分配每個頂點到其自己的團體，然后計算整個網(wǎng)絡的模塊性 M。

第 1 步要求每個團體對（community pair）至少被一條單邊鏈接，如果有兩個團體融合到了一起，該算法就計算由此造成的模塊性改變 ΔM。

第 2 步是取 ΔM 出現(xiàn)了最大增長的團體對，然后融合。然后為這個聚類計算新的模塊性 M，并記錄下來。

重復第 1 步和 第 2 步——每一次都融合團體對，這樣最后得到 ΔM 的最大增益，然后記錄新的聚類模式及其相應的模塊性分數(shù) M。

重復第 1 步和 第 2 步——每一次都融合團體對，這樣最后得到 ΔM 的最大增益，然后記錄新的聚類模式及其相應的模塊性分數(shù) M。

總結

以上是生活随笔為你收集整理的聚类方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。