本文為 AI 研習社編譯的技術(shù)博客，原標題 ：
The 5 Clustering Algorithms Data Scientists Need to Know
作者 |George Seif
翻譯 | 鄧普斯?杰弗、arnold_hua、小Y的彩筆
校對 | 鄧普斯?杰弗 審核| Lam-W 整理 | 菠蘿妹
原文鏈接：
https://towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68
聚類(lèi)算法是機器學(xué)習中涉及對數據進(jìn)行分組的一種算法。在給定的數據集中，我們可以通過(guò)聚類(lèi)算法將其分成一些不同的組。在理論上，相同的組的數據之間有相同的屬性或者是特征，不同組數據之間的屬性或者特征相差就會(huì )比較大。聚類(lèi)算法是一種非監督學(xué)習算法，并且作為一種常用的數據分析算法在很多領(lǐng)域上得到應用。
在數據科學(xué)領(lǐng)域，我們利用聚類(lèi)分析，通過(guò)將數據分組可以比較清晰的獲取到數據信息。今天我們來(lái)看看，作為數據科學(xué)家需要知道并掌握的五種比較比較流行的聚類(lèi)算法。
K-means 聚類(lèi)算法
K-means 聚類(lèi)算法 可能是大家最為熟悉的聚類(lèi)算法。它在許多的工業(yè)級數據科學(xué)和機器學(xué)習課程中都有被講解。并且容易理解和實(shí)現相應功能的代碼 。 比如以下的圖片：
k-means聚類(lèi)
首先，我們確定要聚類(lèi)的數量，并隨機初始化它們各自的中心點(diǎn)。為了確定要聚類(lèi)的數量，最好快速查看數據并嘗試識別任何不同的分組。中心點(diǎn)是與每個(gè)數據點(diǎn)向量長(cháng)度相同的向量，是上圖中的x。
通過(guò)計算當前點(diǎn)與每個(gè)組中心之間的距離，對每個(gè)數據點(diǎn)進(jìn)行分類(lèi)，然后歸到與距離最近的中心的組中。
基于迭代后的結果，計算每一類(lèi)內，所有點(diǎn)的平均值，作為新簇中心。
迭代重復這些步驟，或者直到組中心在迭代之間變化不大。您還可以選擇隨機初始化組中心幾次，然后選擇看起來(lái)提供最佳結果。
k-means的優(yōu)點(diǎn)是速度非?？?，因為我們真正要做的就是計算點(diǎn)和組中心之間的距離；計算量少！因此，它具有線(xiàn)性復雜性o（n）。
另一方面，k-means有兩個(gè)缺點(diǎn)。首先，您必須先確定聚類(lèi)的簇數量。理想情況下，對于一個(gè)聚類(lèi)算法，我們希望它能幫我們解決這些問(wèn)題，因為它的目的是從數據中獲得一些洞察力。k-均值也從隨機選擇聚類(lèi)中心開(kāi)始，因此它可能在算法的不同運行中產(chǎn)生不同的聚類(lèi)結果。因此，結果可能不可重復，缺乏一致性。
K中位數是與K均值相關(guān)的另一種聚類(lèi)算法，除了不使用平均值重新計算組中心點(diǎn)之外，我們使用組的中位數向量。這種方法對異常偏離值不太敏感（因為使用了中值），但對于較大的數據集來(lái)說(shuō)要慢得多，因為在計算中值向量時(shí)，每次迭代都需要排序。
Mean-Shift 聚類(lèi)
Mean-shift 聚類(lèi)是一個(gè)基于滑窗的算法，嘗試找到數據點(diǎn)密集的區域。它是一個(gè)基于質(zhì)心的算法，也就是說(shuō)他的目標是通過(guò)更新中心點(diǎn)候選者定位每個(gè)組或類(lèi)的中心點(diǎn)，將中心點(diǎn)候選者更新為滑窗內點(diǎn)的均值。這些候選滑窗之后會(huì )在后處理階段被過(guò)濾，來(lái)減少臨近的重復點(diǎn)，最后形成了中心點(diǎn)的集合和他們對應的組。查看下面的說(shuō)明圖。
單滑窗的 Mean-Shift 聚類(lèi)
為了解釋 mean-shift，我們將考慮一個(gè)二維空間中的點(diǎn)集，像上圖所示那樣。我們以一個(gè)圓心在C點(diǎn)（隨機選擇）的圓形滑窗開(kāi)始，以半徑 r 作為核。Mean shift 是一個(gè)爬山算法，它每一步都迭代地把核移動(dòng)到更高密度的區域，直到收斂位置。
在每次迭代時(shí)，通過(guò)移動(dòng)中心點(diǎn)到滑窗中點(diǎn)的均值處，將滑窗移動(dòng)到密度更高的區域（這也是這種算法名字的由來(lái)）?；皟鹊拿芏扰c在其內部點(diǎn)的數量成正比。很自然地，通過(guò)將中心移動(dòng)到窗內點(diǎn)的均值處，可以逐步的移向有個(gè)高的密度的區域。
我們繼續根據均值來(lái)移動(dòng)滑窗，直到有沒(méi)有哪個(gè)方向可以使核中容納更多的點(diǎn)。查看上面的圖，我們一直移動(dòng)圓圈直到密度不再增長(cháng)。（即窗內點(diǎn)的數量不再增長(cháng)）。
用很多滑窗重復1-3這個(gè)過(guò)程，直到所有的點(diǎn)都包含在了窗內。當多個(gè)滑動(dòng)窗口重疊時(shí)，包含最多點(diǎn)的窗口將被保留。然后，根據數據點(diǎn)所在的滑動(dòng)窗口對數據點(diǎn)進(jìn)行聚類(lèi)。
下圖展示了所有滑動(dòng)窗口從端到端的整個(gè)過(guò)程。每個(gè)黑色的點(diǎn)都代表滑窗的質(zhì)心，每個(gè)灰色的點(diǎn)都是數據點(diǎn)。
Mean-Shift 聚類(lèi)的全部過(guò)程
與 K-means 聚類(lèi)不同的是，Mean-Shift 不需要選擇聚類(lèi)的數量，因為mean-shift 自動(dòng)發(fā)現它。這是一個(gè)很大的優(yōu)點(diǎn)。事實(shí)上聚類(lèi)中心向著(zhù)有最大密度的點(diǎn)收斂也是我們非常想要的，因為這很容易理解并且很適合于自然的數據驅動(dòng)的場(chǎng)景。缺點(diǎn)是滑窗尺寸/半徑r的選擇需要仔細考慮。
基于密度的帶噪聲的空間聚類(lèi)的應用（DBSCAN)
DBSCAN 是一個(gè)基于密度的聚類(lèi)算法，與 mean-shift 相似，但是有幾個(gè)值得注意的優(yōu)點(diǎn)。查看下面這個(gè)花哨的圖片，我們開(kāi)始吧！
DBSCAN 笑臉聚類(lèi)
DBSCAN 從一個(gè)任意的還沒(méi)有被訪(fǎng)問(wèn)過(guò)的啟動(dòng)數據點(diǎn)開(kāi)始。用一個(gè)距離 epsilon ε 將這個(gè)點(diǎn)的鄰域提取出來(lái)（所有再距離 ε 內的點(diǎn)都視為鄰居點(diǎn)）。
如果在鄰域內有足夠數量的點(diǎn)（根據 minPoints) ，那么聚類(lèi)過(guò)程開(kāi)始，并且當前數據點(diǎn)變成新集群中的第一個(gè)點(diǎn)。否則，該點(diǎn)將被標記為噪聲（之后這個(gè)噪聲點(diǎn)可能會(huì )變成集群中的一部分）。在這兩種情況中的點(diǎn)都被標記為已訪(fǎng)問(wèn)。
對于這個(gè)新集群中的第一個(gè)點(diǎn)，在它 ε 距離鄰域內的點(diǎn)已將變成相同集群中的一部分。這個(gè)讓所有在 ε 鄰域內的點(diǎn)都屬于相同集群的過(guò)程在之后會(huì )一直被重復做，直到所有新點(diǎn)都被加進(jìn)集群分組中。
第 2，3 步的過(guò)程會(huì )一直重復直到集群內所有點(diǎn)都被確定，即所有在 ε 鄰域內的點(diǎn)都被訪(fǎng)問(wèn)且被打上標簽。
一旦我們在當前集群做完這些，一個(gè)新的未被訪(fǎng)問(wèn)的點(diǎn)會(huì )被提取并處理，從而會(huì )接著(zhù)發(fā)現下一個(gè)集群或噪聲。這個(gè)過(guò)程反復進(jìn)行直到所有的點(diǎn)都被編輯為已訪(fǎng)問(wèn)。既然在最后所有的點(diǎn)都被訪(fǎng)問(wèn)，那么每個(gè)點(diǎn)都被標記為屬于一個(gè)集群或者是噪聲。
相較于其他聚類(lèi)算法，DBSCAN 提出了一些很棒的優(yōu)點(diǎn)。首先，它根本不需要預置集群的數量。它還將離群值認定為噪聲，不像 mean-shift 中僅僅是將它們扔到一個(gè)集群里，甚至即使該數據點(diǎn)的差異性很大也這么做。另外，這個(gè)算法還可以很好的找到任意尺寸核任意形狀的集群。
SBSCAN 最大的缺點(diǎn)是當集群的密度變化時(shí)，它表現的不像其他算法那樣好。這是因為當密度變化時(shí)，距離的閾值 ε 和用于確定鄰居點(diǎn)的 minPoints 也將會(huì )隨之改變。這個(gè)缺點(diǎn)也會(huì )發(fā)生在很高為的數據中，因為距離閾值 ε 變得很難被估計。
基于高斯混合模型(GMM)的期望最大化（EM）聚類(lèi)
k-means的一個(gè)主要缺點(diǎn)是它簡(jiǎn)單地使用了集群中心的平均值。通過(guò)下面的圖片，我們可以看到為什么這不是最好的方式。在左手邊，人眼可以很明顯地看到，有兩個(gè)半徑不同的圓形星團以相同的平均值為中心。k-means不能處理這個(gè)問(wèn)題，因為不同簇的平均值非常接近。當簇不是圓形時(shí)，k均值也會(huì )失效，這也是將均值用作簇中心的后果。
K-means不適用的case
高斯混合模型（gmms）具有更好的靈活性比K-means。使用GMMs，我們需要假設數據點(diǎn)是高斯分布，相對于環(huán)形的數據而言，這個(gè)假設的嚴格程度與均值相比弱很多。這樣的話(huà)，我們有兩個(gè)參數來(lái)描述簇的形狀：均值和標準差。以二維為例，意味簇可以是任何一種橢圓形（因為我們有兩個(gè)標準差在x和y方向）。因此，每個(gè)高斯分布會(huì )被分配到單一的聚類(lèi)簇。
為了在每個(gè)聚類(lèi)簇中找到這兩個(gè)高斯參數（e.g均值和標準差），我們將使用的優(yōu)化算法稱(chēng)為expectation–maximization（EM）。請看下面的圖片，以說(shuō)明將高斯擬合聚類(lèi)簇。然后，我們可以處理EM聚類(lèi)過(guò)程使用gmms。
使用GMMs的EM聚類(lèi)
我們首先設定聚類(lèi)簇的數量（如k-means），然后隨機初始化每個(gè)集群的高斯分布參數。我們也可以通過(guò)快速查看數據來(lái)為初始參數提供一個(gè)很好的猜測。正如上圖所示，這不是100%必要的，因為高斯操作開(kāi)始時(shí)候是非常差的，但很快優(yōu)化。
給定每個(gè)簇的高斯分布，計算每個(gè)數據點(diǎn)屬于特定簇的概率。一個(gè)點(diǎn)越靠近高斯中心，它就越可能屬于該簇。這應該是直觀(guān)的，因為對于高斯分布，我們假設大多數數據都靠近集群的中心。
基于這些概率，我們?yōu)楦咚狗植加嬎懔艘唤M新的參數，這樣我們就可以最大化群集中數據點(diǎn)的概率。我們使用數據點(diǎn)位置的加權和計算這些新參數，其中權重是屬于特定集群的數據點(diǎn)的概率。為了以可視化的方式解釋這一點(diǎn)，我們可以查看上面的圖形，特別是以黃色集群為例。在第一次迭代中，分布是隨機開(kāi)始的，但是我們可以看到大多數黃點(diǎn)都在分布的右邊。當我們計算一個(gè)由概率加權的和時(shí)，即使在中心附近有一些點(diǎn)，但大多數都在右邊。因此，分布的平均值很自然地移近這些點(diǎn)集。我們還可以看到，大多數點(diǎn)是從右上到左下。因此，標準偏差會(huì )發(fā)生變化，以創(chuàng )建一個(gè)更適合這些點(diǎn)的橢圓，以便最大化概率加權的和。
第2步和第3步重復進(jìn)行，直到收斂，也就是在收斂過(guò)程中，迭代變化不大。
使用GMMS有兩個(gè)關(guān)鍵優(yōu)勢。首先，GMMS在簇協(xié)方差方面比K均值靈活得多；由于標準偏差參數的存在，簇可以呈現任何橢圓形狀，而不局限于圓形。k均值實(shí)際上是GMM的一個(gè)特例，其中每個(gè)簇的所有維協(xié)方差都接近于0。其次，由于GMM使用概率，因此每個(gè)數據點(diǎn)可以有多個(gè)集群。因此，如果一個(gè)數據點(diǎn)位于兩個(gè)重疊集群的中間，我們可以簡(jiǎn)單地定義它的類(lèi)，方法是說(shuō)它屬于類(lèi)1的X%，屬于類(lèi)2的Y%。即GMMS支持混合成員。
凝聚層次聚類(lèi)
凝聚層次聚類(lèi)算法實(shí)際上分為 2 類(lèi)：自上而下或自下而上。自下而上算法在一開(kāi)始將每個(gè)數據點(diǎn)當作一個(gè)單個(gè)集群對待，然后逐步的合并（或凝聚）成對的集群，直到所有的集群被合并到一個(gè)集群中，這個(gè)集群包含所有的點(diǎn)。自下而上層次聚類(lèi)因此被叫做層次凝聚的聚類(lèi)或者 HAC。這個(gè)聚類(lèi)的層次被表示為一棵樹(shù)（或者樹(shù)狀圖）。樹(shù)根是唯一的集群，他聚集了所有的樣本，葉子是只有一個(gè)樣本的集群。在接著(zhù)看算法步驟之前，請查看下面的圖示說(shuō)明。
凝聚層次聚類(lèi)
我們通過(guò)將每個(gè)點(diǎn)視作一個(gè)單個(gè)集群作為開(kāi)始，即如果我們的數據集中有 X 個(gè)數據點(diǎn)，那么我們就有 X 個(gè)集群。我們然后選擇一個(gè)距離度量標準來(lái)測量?jì)蓚€(gè)集群之間的距離。作為一個(gè)例子，我們將用到平均連接，它將兩個(gè)集群之間的距離定義為第一個(gè)集群中的數據點(diǎn)與第二個(gè)集群中數據點(diǎn)的平均距離。
在每次迭代時(shí)，我們將兩個(gè)集群組合成一個(gè)。兩個(gè)將被組合的集群是在那些有最小平均連接的集群中選出來(lái)的，即根據我們選擇的距離度量標準，這些兩兩集群之間有最小的距離，且因此是最相似的也最應該被組合。
一直重復第二步，直到我們到達樹(shù)的根部，即我們只有一個(gè)包含所有數據點(diǎn)的集群。通過(guò)這種方法，我們僅僅通過(guò)選擇停止組合的集群的時(shí)機，即選擇何時(shí)停止樹(shù)的構建，就可以挑選出最終我們想要的集群數。
層次聚類(lèi)不要求我們指定集群的數目，并且我們甚至可以選擇看上去最好的集群的數目，因為我們正在構建一棵樹(shù)。另外，算法對于距離度量的選擇也是不敏感的；所有的這些都和其他聚類(lèi)算法的效果一樣好，而對于其他算法，距離度量的選擇是很關(guān)鍵的。層次聚類(lèi)方法的一個(gè)典型的使用案例是當底層數據具有層次結構并且要恢復層次結構時(shí)； 其他聚類(lèi)算法做不到這個(gè)。這些層次聚類(lèi)的優(yōu)點(diǎn)的代價(jià)是效率很低，因為它的時(shí)間復雜度是O(n3)，不像有線(xiàn)性復雜度的 K-Means 和 GMM 那樣。
結論
以上就是數據科學(xué)家最應該了解的5中聚類(lèi)算法！我們將以一個(gè)很漂亮的可視化來(lái)作為結束，可視化展示了這些算法和一些其算法表現得多么出色，這要歸功于 Scikit Learn庫！
想要繼續查看該篇文章相關(guān)鏈接和參考文獻？
長(cháng)按鏈接點(diǎn)擊打開(kāi)或點(diǎn)擊【數據科學(xué)中必須熟知的5種聚類(lèi)算法】：
https://ai.yanxishe.com/page/TextTranslation/1404
AI研習社每日更新精彩內容，觀(guān)看更多精彩內容：雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)
盤(pán)點(diǎn)圖像分類(lèi)的竅門(mén)
深度學(xué)習目標檢測算法綜述
生成模型：基于單張圖片找到物體位置
注意力的動(dòng)畫(huà)解析（以機器翻譯為例）
等你來(lái)譯：