在機器學習中，無監(jiān)督學習一直是我們追求的方向，而其中的聚類算法更是發(fā)現(xiàn)隱藏數(shù)據(jù)結(jié)構(gòu)與知識的有效手段。目前如谷歌新聞等很多應(yīng)用都將聚類算法作為主要的實現(xiàn)手段，它們能利用大量的未標注數(shù)據(jù)構(gòu)建強大的主題聚類。本文從最基礎(chǔ)的 K 均值聚類到基于密度的強大方法介紹了 6 類主流方法，它們各有擅長領(lǐng)域與情景，且基本思想并不一定限于聚類方法。

本文將從簡單高效的 K 均值聚類開始，依次介紹均值漂移聚類、基于密度的聚類、利用高斯混合和最大期望方法聚類、層次聚類和適用于結(jié)構(gòu)化數(shù)據(jù)的圖團體檢測。我們不僅會分析基本的實現(xiàn)概念，同時還會給出每種算法的優(yōu)缺點以明確實際的應(yīng)用場景。

聚類是一種包括數(shù)據(jù)點分組的機器學習技術(shù)。給定一組數(shù)據(jù)點，我們可以用聚類算法將每個數(shù)據(jù)點分到特定的組中。理論上，屬于同一組的數(shù)據(jù)點應(yīng)該有相似的屬性和/或特征，而屬于不同組的數(shù)據(jù)點應(yīng)該有非常不同的屬性和/或特征。聚類是一種無監(jiān)督學習的方法，是一種在許多領(lǐng)域常用的統(tǒng)計數(shù)據(jù)分析技術(shù)。

K-Means（K 均值）聚類

K-Means 可能是最知名的聚類算法。它是很多入門級數(shù)據(jù)科學和機器學習課程的內(nèi)容。在代碼中很容易理解和實現(xiàn)！請看下面的圖。

K-Means 聚類

首先，我們選擇一些類/組，并隨機初始化它們各自的中心點。為了算出要使用的類的數(shù)量，最好快速查看一下數(shù)據(jù)，并嘗試識別不同的組。中心點是與每個數(shù)據(jù)點向量長度相同的位置，在上圖中是「X」。

通過計算數(shù)據(jù)點與每個組中心之間的距離來對每個點進行分類，然后將該點歸類于組中心與其最接近的組中。

根據(jù)這些分類點，我們利用組中所有向量的均值來重新計算組中心。

重復(fù)這些步驟來進行一定數(shù)量的迭代，或者直到組中心在每次迭代后的變化不大。你也可以選擇隨機初始化組中心幾次，然后選擇看起來提供了最佳結(jié)果的運行。

K-Means 的優(yōu)勢在于速度快，因為我們真正在做的是計算點和組中心之間的距離：非常少的計算！因此它具有線性復(fù)雜度 O(n)。

另一方面，K-Means 有一些缺點。首先，你必須選擇有多少組/類。這并不總是仔細的，并且理想情況下，我們希望聚類算法能夠幫我們解決分多少類的問題，因為它的目的是從數(shù)據(jù)中獲得一些見解。K-means 也從隨機選擇的聚類中心開始，所以它可能在不同的算法中產(chǎn)生不同的聚類結(jié)果。因此，結(jié)果可能不可重復(fù)并缺乏一致性。其他聚類方法更加一致。

K-Medians 是與 K-Means 有關(guān)的另一個聚類算法，除了不是用均值而是用組的中值向量來重新計算組中心。這種方法對異常值不敏感（因為使用中值），但對于較大的數(shù)據(jù)集要慢得多，因為在計算中值向量時，每次迭代都需要進行排序。

均值漂移聚類

均值漂移聚類是基于滑動窗口的算法，它試圖找到數(shù)據(jù)點的密集區(qū)域。這是一個基于質(zhì)心的算法，這意味著它的目標是定位每個組/類的中心點，通過將中心點的候選點更新為滑動窗口內(nèi)點的均值來完成。然后，在后處理階段對這些候選窗口進行過濾以消除近似重復(fù)，形成最終的中心點集及其相應(yīng)的組。請看下面的圖例。

均值漂移聚類用于單個滑動窗口

為了解釋均值漂移，我們將考慮二維空間中的一組點，如上圖所示。我們從一個以 C 點（隨機選擇）為中心，以半徑 r 為核心的圓形滑動窗口開始。均值漂移是一種爬山算法，它包括在每一步中迭代地向更高密度區(qū)域移動，直到收斂。

在每次迭代中，滑動窗口通過將中心點移向窗口內(nèi)點的均值（因此而得名）來移向更高密度區(qū)域?；瑒哟翱趦?nèi)的密度與其內(nèi)部點的數(shù)量成正比。自然地，通過向窗口內(nèi)點的均值移動，它會逐漸移向點密度更高的區(qū)域。

我們繼續(xù)按照均值移動滑動窗口直到?jīng)]有方向在核內(nèi)可以容納更多的點。請看上面的圖；我們一直移動這個圓直到密度不再增加（即窗口中的點數(shù)）。

步驟 1 到 3 的過程是通過許多滑動窗口完成的，直到所有的點位于一個窗口內(nèi)。當多個滑動窗口重疊時，保留包含最多點的窗口。然后根據(jù)數(shù)據(jù)點所在的滑動窗口進行聚類。

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

均值漂移聚類的整個過程

與 K-means 聚類相比，這種方法不需要選擇簇數(shù)量，因為均值漂移自動發(fā)現(xiàn)這一點。這是一個巨大的優(yōu)勢。聚類中心朝最大點密度聚集的事實也是非常令人滿意的，因為理解和適應(yīng)自然數(shù)據(jù)驅(qū)動的意義是非常直觀的。它的缺點是窗口大小/半徑「r」的選擇可能是不重要的。

基于密度的聚類方法（DBSCAN）

DBSCAN 是一種基于密度的聚類算法，它類似于均值漂移，但具有一些顯著的優(yōu)點。請看下面的另一個有趣的圖形，讓我們開始吧！

DBSCAN 聚類

DBSCAN 從一個沒有被訪問過的任意起始數(shù)據(jù)點開始。這個點的鄰域是用距離 ε（ε 距離內(nèi)的所有點都是鄰域點）提取的。

如果在這個鄰域內(nèi)有足夠數(shù)量的點（根據(jù) minPoints），則聚類過程開始，并且當前數(shù)據(jù)點成為新簇的第一個點。否則，該點將會被標記為噪聲（稍后這個噪聲點可能仍會成為聚類的一部分）。在這兩種情況下，該點都被標記為「已訪問」。

對于新簇中的第一個點，其 ε 距離鄰域內(nèi)的點也成為該簇的一部分。這個使所有 ε 鄰域內(nèi)的點都屬于同一個簇的過程將對所有剛剛添加到簇中的新點進行重復(fù)。

重復(fù)步驟 2 和 3，直到簇中所有的點都被確定，即簇的 ε 鄰域內(nèi)的所有點都被訪問和標記過。

一旦我們完成了當前的簇，一個新的未訪問點將被檢索和處理，導致發(fā)現(xiàn)另一個簇或噪聲。重復(fù)這個過程直到所有的點被標記為已訪問。由于所有點都已經(jīng)被訪問，所以每個點都屬于某個簇或噪聲。

DBSCAN 與其他聚類算法相比有很多優(yōu)點。首先，它根本不需要固定數(shù)量的簇。它也會將異常值識別為噪聲，而不像均值漂移，即使數(shù)據(jù)點非常不同，也會簡單地將它們分入簇中。另外，它能夠很好地找到任意大小和任意形狀的簇。

DBSCAN 的主要缺點是當簇的密度不同時，它的表現(xiàn)不如其他聚類算法。這是因為當密度變化時，用于識別鄰域點的距離閾值 ε 和 minPoints 的設(shè)置將會隨著簇而變化。這個缺點也會在非常高維度的數(shù)據(jù)中出現(xiàn)，因為距離閾值 ε 再次變得難以估計。

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

K-Means 的一個主要缺點是它對于聚類中心均值的簡單使用。通過下面的圖，我們可以明白為什么這不是最佳方法。在左側(cè)，可以非常清楚的看到有兩個具有不同半徑的圓形簇，以相同的均值作為中心。K-Means 不能處理這種情況，因為這些簇的均值是非常接近的。K-Means 在簇不是圓形的情況下也失敗了，同樣是由于使用均值作為聚類中心。

K-Means 的兩個失敗案例

高斯混合模型（GMMs）比 K-Means 給了我們更多的靈活性。對于 GMMs，我們假設(shè)數(shù)據(jù)點是高斯分布的；相對于使用均值來假設(shè)它們是圓形的，這是一個限制較少的假設(shè)。這樣，我們有兩個參數(shù)來描述簇的形狀：均值和標準差！以二維為例，這意味著，這些簇可以采取任何類型的橢圓形（因為我們在 x 和 y 方向都有標準差）。因此，每個高斯分布被分配給單個簇。

為了找到每個簇的高斯參數(shù)（例如均值和標準差），我們將用一個叫做最大期望（EM）的優(yōu)化算法。請看下面的圖表，這是一個高斯適合于簇的例子。然后我們可以使用 GMMs 繼續(xù)進行最大期望聚類的過程。

使用 GMMs 的 EM 聚類

我們首先選擇簇的數(shù)量（如 K-Means 所做的），并隨機初始化每個簇的高斯分布參數(shù)。也可以通過快速查看數(shù)據(jù)來嘗試為初始參數(shù)提供一個好的猜測。但是請注意，正如上圖所看到的，這不是 100% 必要的，因為高斯開始時我們很窮，但是很快就得到了優(yōu)化。

給定每個簇的高斯分布，計算每個數(shù)據(jù)點屬于一個特定簇的概率。一個點越靠近高斯的中心，它就越可能屬于該簇。這應(yīng)該是很直觀的，因為對于高斯分布我們假設(shè)大部分數(shù)據(jù)更靠近簇的中心。

基于這些概率，我們計算一組新的高斯分布參數(shù)使得簇內(nèi)的數(shù)據(jù)點的概率最大化。我們使用數(shù)據(jù)點位置的加權(quán)和來計算這些新參數(shù)，其中權(quán)重是數(shù)據(jù)點屬于該特定簇的概率。為了用可視化的方式解釋它，我們可以看一下上面的圖，特別是黃色的簇，我們以它來作為例子。分布在第一次迭代時隨即開始，但是我們可以看到大部分的黃點都在分布的右側(cè)。當我們計算一個概率加權(quán)和時，即使中心附近有一些點，但它們大部分都在右側(cè)。因此，分布的均值自然會接近這些點。我們也可以看到大部分的點分布在「從右上到左下」。因此改變標準差來創(chuàng)建更適合這些點的橢圓，以便最大化概率加權(quán)和。

重復(fù)步驟 2 和 3 直到收斂，其中分布在迭代中的變化不大。

使用 GMMs 有兩個關(guān)鍵的優(yōu)勢。首先，GMMs 比 K-Means 在簇協(xié)方差方面更靈活；因為標準差參數(shù)，簇可以呈現(xiàn)任何橢圓形狀，而不是被限制為圓形。K-Means 實際上是 GMM 的一個特殊情況，這種情況下每個簇的協(xié)方差在所有維度都接近 0。第二，因為 GMMs 使用概率，所以每個數(shù)據(jù)點可以有很多簇。因此如果一個數(shù)據(jù)點在兩個重疊的簇的中間，我們可以簡單地通過說它百分之 X 屬于類 1，百分之 Y 屬于類 2 來定義它的類。即 GMMs 支持混合資格。

凝聚層次聚類

層次聚類算法實際上分為兩類：自上而下或自下而上。自下而上的算法首先將每個數(shù)據(jù)點視為一個單一的簇，然后連續(xù)地合并（或聚合）兩個簇，直到所有的簇都合并成一個包含所有數(shù)據(jù)點的簇。因此，自下而上層次聚類被稱為凝聚式層次聚類或 HAC。這個簇的層次用樹（或樹狀圖）表示。樹的根是收集所有樣本的唯一簇，葉是僅僅具有一個樣本的簇。在進入算法步驟前，請看下面的圖例。

凝聚式層次聚類

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

在每次迭代中，我們將兩個簇合并成一個。這兩個要合并的簇應(yīng)具有最小的 average linkage。即根據(jù)我們選擇的距離度量標準，這兩個簇之間的距離最小，因此是最相似的，應(yīng)該合并在一起。

重復(fù)步驟 2 直到我們到達樹根，即我們只有一個包含所有數(shù)據(jù)點的簇。這樣我們只需要選擇何時停止合并簇，即何時停止構(gòu)建樹，來選擇最終需要多少個簇！

層次聚類不需要我們指定簇的數(shù)量，我們甚至可以選擇哪個數(shù)量的簇看起來最好，因為我們正在構(gòu)建一棵樹。另外，該算法對于距離度量標準的選擇并不敏感；他們都同樣表現(xiàn)很好，而對于其他聚類算法，距離度量標準的選擇是至關(guān)重要的。層次聚類方法的一個特別好的例子是當基礎(chǔ)數(shù)據(jù)具有層次結(jié)構(gòu)，并且你想要恢復(fù)層次時；其他聚類算法不能做到這一點。與 K-Means 和 GMM 的線性復(fù)雜度不同，層次聚類的這些優(yōu)點是以較低的效率為代價的，因為它具有 O(n3) 的時間復(fù)雜度。

圖團體檢測（Graph Community Detection）

當我們的數(shù)據(jù)可以被表示為一個網(wǎng)絡(luò)或圖（graph）時，我們可以使用圖團體檢測方法完成聚類。在這個算法中，圖團體（graph community）通常被定義為一種頂點（vertice）的子集，其中的頂點相對于網(wǎng)絡(luò)的其它部分要連接得更加緊密。

也許最直觀的案例就是社交網(wǎng)絡(luò)。其中的頂點表示人，連接頂點的邊表示他們是朋友或互粉的用戶。但是，若要將一個系統(tǒng)建模成一個網(wǎng)絡(luò)，我們就必須要找到一種有效連接各個不同組件的方式。將圖論用于聚類的一些創(chuàng)新應(yīng)用包括：對圖像數(shù)據(jù)的特征提取、分析基因調(diào)控網(wǎng)絡(luò)（gene regulatory networks）等。

下面是一個簡單的圖，展示了最近瀏覽過的 8 個網(wǎng)站，根據(jù)他們的維基百科頁面中的鏈接進行了連接。

這些頂點的顏色表示了它們的團體關(guān)系，大小是根據(jù)它們的中心度（centrality）確定的。這些聚類在現(xiàn)實生活中也很有意義，其中黃色頂點通常是參考/搜索網(wǎng)站，藍色頂點全部是在線發(fā)布網(wǎng)站（文章、微博或代碼）。

假設(shè)我們已經(jīng)將該網(wǎng)絡(luò)聚類成了一些團體。我們就可以使用該模塊性分數(shù)來評估聚類的質(zhì)量。分數(shù)更高表示我們將該網(wǎng)絡(luò)分割成了「準確的（accurate）」團體，而低分則表示我們的聚類更接近隨機。如下圖所示：

模塊性可以使用以下公式進行計算：

其中 L 代表網(wǎng)絡(luò)中邊的數(shù)量，k_i 和 k_j 是指每個頂點的 degree，它可以通過將每一行和每一列的項加起來而得到。兩者相乘再除以 2L 表示當該網(wǎng)絡(luò)是隨機分配的時候頂點 i 和 j 之間的預(yù)期邊數(shù)。

整體而言，括號中的項表示了該網(wǎng)絡(luò)的真實結(jié)構(gòu)和隨機組合時的預(yù)期結(jié)構(gòu)之間的差。研究它的值可以發(fā)現(xiàn)，當 A_ij = 1 且 ( k_i k_j ) / 2L 很小時，其返回的值最高。這意味著，當在定點 i 和 j 之間存在一個「非預(yù)期」的邊時，得到的值更高。

最后的 δc_i, c_j 就是大名鼎鼎的克羅內(nèi)克 δ 函數(shù)（Kronecker-delta function）。下面是其 Python 解釋：

通過以上公式可以計算圖的模塊性，且模塊性越高，該網(wǎng)絡(luò)聚類成不同團體的程度就越好。因此通過最優(yōu)化方法尋找最大模塊性就能發(fā)現(xiàn)聚類該網(wǎng)絡(luò)的最佳方法。

組合學（combinatorics）告訴我們對于一個僅有 8 個頂點的網(wǎng)絡(luò)，就存在 4140 種不同的聚類方式。16 個頂點的網(wǎng)絡(luò)的聚類方式將超過 100 億種。32 個頂點的網(wǎng)絡(luò)的可能聚類方式更是將超過 128 septillion（10^21）種；如果你的網(wǎng)絡(luò)有 80 個頂點，那么其可聚類的方式的數(shù)量就已經(jīng)超過了可觀測宇宙中的原子數(shù)量。

因此，我們必須求助于一種啟發(fā)式的方法，該方法在評估可以產(chǎn)生最高模塊性分數(shù)的聚類上效果良好，而且并不需要嘗試每一種可能性。這是一種被稱為 Fast-Greedy Modularity-Maximization（快速貪婪模塊性最大化）的算法，這種算法在一定程度上類似于上面描述的 agglomerative hierarchical clustering algorithm（集聚層次聚類算法）。只是 Mod-Max 并不根據(jù)距離（distance）來融合團體，而是根據(jù)模塊性的改變來對團體進行融合。

下面是其工作方式：

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

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

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

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

當所有的頂點都被分組成了一個巨型聚類時，就可以停止了。然后該算法會檢查這個過程中的記錄，然后找到其中返回了最高 M 值的聚類模式。這就是返回的團體結(jié)構(gòu)。

團體檢測（community detection）是現(xiàn)在圖論中一個熱門的研究領(lǐng)域，它的局限性主要體現(xiàn)在會忽略一些小的集群，且只適用于結(jié)構(gòu)化的圖模型。但這一類算法在典型的結(jié)構(gòu)化數(shù)據(jù)中和現(xiàn)實網(wǎng)狀數(shù)據(jù)都有非常好的性能。

結(jié)語

以上就是數(shù)據(jù)科學家應(yīng)該知道的 6 大聚類算法！我們將以展示各類算法的可視化效果結(jié)束本文！ 

原文鏈接：https://towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68