數(shù)據(jù)科學(xué)中必須熟知的5種聚類算法

本文作者： AI研習(xí)社-譯站

2019-02-14 10:18

導(dǎo)語：聚類算法是機(jī)器學(xué)習(xí)中涉及對數(shù)據(jù)進(jìn)行分組的一種算法。

本文為 AI 研習(xí)社編譯的技術(shù)博客，原標(biāo)題：
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

聚類算法是機(jī)器學(xué)習(xí)中涉及對數(shù)據(jù)進(jìn)行分組的一種算法。在給定的數(shù)據(jù)集中，我們可以通過聚類算法將其分成一些不同的組。在理論上，相同的組的數(shù)據(jù)之間有相同的屬性或者是特征，不同組數(shù)據(jù)之間的屬性或者特征相差就會比較大。聚類算法是一種非監(jiān)督學(xué)習(xí)算法，并且作為一種常用的數(shù)據(jù)分析算法在很多領(lǐng)域上得到應(yīng)用。

在數(shù)據(jù)科學(xué)領(lǐng)域，我們利用聚類分析，通過將數(shù)據(jù)分組可以比較清晰的獲取到數(shù)據(jù)信息。今天我們來看看，作為數(shù)據(jù)科學(xué)家需要知道并掌握的五種比較比較流行的聚類算法。

K-means 聚類算法

K-means 聚類算法可能是大家最為熟悉的聚類算法。它在許多的工業(yè)級數(shù)據(jù)科學(xué)和機(jī)器學(xué)習(xí)課程中都有被講解。并且容易理解和實(shí)現(xiàn)相應(yīng)功能的代碼。比如以下的圖片：

數(shù)據(jù)科學(xué)中必須熟知的5種聚類算法

k-means聚類

首先，我們確定要聚類的數(shù)量，并隨機(jī)初始化它們各自的中心點(diǎn)。為了確定要聚類的數(shù)量，最好快速查看數(shù)據(jù)并嘗試識別任何不同的分組。中心點(diǎn)是與每個數(shù)據(jù)點(diǎn)向量長度相同的向量，是上圖中的“x”。
通過計算當(dāng)前點(diǎn)與每個組中心之間的距離，對每個數(shù)據(jù)點(diǎn)進(jìn)行分類，然后歸到與距離最近的中心的組中。
基于迭代后的結(jié)果，計算每一類內(nèi)，所有點(diǎn)的平均值，作為新簇中心。
迭代重復(fù)這些步驟，或者直到組中心在迭代之間變化不大。您還可以選擇隨機(jī)初始化組中心幾次，然后選擇看起來提供最佳結(jié)果。

k-means的優(yōu)點(diǎn)是速度非?？欤?yàn)槲覀冋嬲龅木褪怯嬎泓c(diǎn)和組中心之間的距離；計算量少！因此，它具有線性復(fù)雜性o（n）。

另一方面，k-means有兩個缺點(diǎn)。首先，您必須先確定聚類的簇數(shù)量。理想情況下，對于一個聚類算法，我們希望它能幫我們解決這些問題，因?yàn)樗哪康氖菑臄?shù)據(jù)中獲得一些洞察力。k-均值也從隨機(jī)選擇聚類中心開始，因此它可能在算法的不同運(yùn)行中產(chǎn)生不同的聚類結(jié)果。因此，結(jié)果可能不可重復(fù)，缺乏一致性。

K中位數(shù)是與K均值相關(guān)的另一種聚類算法，除了不使用平均值重新計算組中心點(diǎn)之外，我們使用組的中位數(shù)向量。這種方法對異常偏離值不太敏感（因?yàn)槭褂昧酥兄担?，但對于較大的數(shù)據(jù)集來說要慢得多，因?yàn)樵谟嬎阒兄迪蛄繒r，每次迭代都需要排序。

Mean-Shift 聚類

Mean-shift 聚類是一個基于滑窗的算法，嘗試找到數(shù)據(jù)點(diǎn)密集的區(qū)域。它是一個基于質(zhì)心的算法，也就是說他的目標(biāo)是通過更新中心點(diǎn)候選者定位每個組或類的中心點(diǎn)，將中心點(diǎn)候選者更新為滑窗內(nèi)點(diǎn)的均值。這些候選滑窗之后會在后處理階段被過濾，來減少臨近的重復(fù)點(diǎn)，最后形成了中心點(diǎn)的集合和他們對應(yīng)的組。查看下面的說明圖。

數(shù)據(jù)科學(xué)中必須熟知的5種聚類算法

單滑窗的 Mean-Shift 聚類

為了解釋 mean-shift，我們將考慮一個二維空間中的點(diǎn)集，像上圖所示那樣。我們以一個圓心在C點(diǎn)（隨機(jī)選擇）的圓形滑窗開始，以半徑 r 作為核。Mean shift 是一個爬山算法，它每一步都迭代地把核移動到更高密度的區(qū)域，直到收斂位置。
在每次迭代時，通過移動中心點(diǎn)到滑窗中點(diǎn)的均值處，將滑窗移動到密度更高的區(qū)域（這也是這種算法名字的由來）。滑窗內(nèi)的密度與在其內(nèi)部點(diǎn)的數(shù)量成正比。很自然地，通過將中心移動到窗內(nèi)點(diǎn)的均值處，可以逐步的移向有個高的密度的區(qū)域。
我們繼續(xù)根據(jù)均值來移動滑窗，直到有沒有哪個方向可以使核中容納更多的點(diǎn)。查看上面的圖，我們一直移動圓圈直到密度不再增長。（即窗內(nèi)點(diǎn)的數(shù)量不再增長）。
用很多滑窗重復(fù)1-3這個過程，直到所有的點(diǎn)都包含在了窗內(nèi)。當(dāng)多個滑動窗口重疊時，包含最多點(diǎn)的窗口將被保留。然后，根據(jù)數(shù)據(jù)點(diǎn)所在的滑動窗口對數(shù)據(jù)點(diǎn)進(jìn)行聚類。

下圖展示了所有滑動窗口從端到端的整個過程。每個黑色的點(diǎn)都代表滑窗的質(zhì)心，每個灰色的點(diǎn)都是數(shù)據(jù)點(diǎn)。

數(shù)據(jù)科學(xué)中必須熟知的5種聚類算法

Mean-Shift 聚類的全部過程

與 K-means 聚類不同的是，Mean-Shift 不需要選擇聚類的數(shù)量，因?yàn)閙ean-shift 自動發(fā)現(xiàn)它。這是一個很大的優(yōu)點(diǎn)。事實(shí)上聚類中心向著有最大密度的點(diǎn)收斂也是我們非常想要的，因?yàn)檫@很容易理解并且很適合于自然的數(shù)據(jù)驅(qū)動的場景。缺點(diǎn)是滑窗尺寸/半徑“r“的選擇需要仔細(xì)考慮。

基于密度的帶噪聲的空間聚類的應(yīng)用（DBSCAN)

DBSCAN 是一個基于密度的聚類算法，與 mean-shift 相似，但是有幾個值得注意的優(yōu)點(diǎn)。查看下面這個花哨的圖片，我們開始吧！

數(shù)據(jù)科學(xué)中必須熟知的5種聚類算法

DBSCAN 笑臉聚類

DBSCAN 從一個任意的還沒有被訪問過的啟動數(shù)據(jù)點(diǎn)開始。用一個距離 epsilon ε 將這個點(diǎn)的鄰域提取出來（所有再距離 ε 內(nèi)的點(diǎn)都視為鄰居點(diǎn)）。
如果在鄰域內(nèi)有足夠數(shù)量的點(diǎn)（根據(jù) minPoints) ，那么聚類過程開始，并且當(dāng)前數(shù)據(jù)點(diǎn)變成新集群中的第一個點(diǎn)。否則，該點(diǎn)將被標(biāo)記為噪聲（之后這個噪聲點(diǎn)可能會變成集群中的一部分）。在這兩種情況中的點(diǎn)都被標(biāo)記為”已訪問“。
對于這個新集群中的第一個點(diǎn)，在它 ε 距離鄰域內(nèi)的點(diǎn)已將變成相同集群中的一部分。這個讓所有在 ε 鄰域內(nèi)的點(diǎn)都屬于相同集群的過程在之后會一直被重復(fù)做，直到所有新點(diǎn)都被加進(jìn)集群分組中。
第 2，3 步的過程會一直重復(fù)直到集群內(nèi)所有點(diǎn)都被確定，即所有在 ε 鄰域內(nèi)的點(diǎn)都被訪問且被打上標(biāo)簽。
一旦我們在當(dāng)前集群做完這些，一個新的未被訪問的點(diǎn)會被提取并處理，從而會接著發(fā)現(xiàn)下一個集群或噪聲。這個過程反復(fù)進(jìn)行直到所有的點(diǎn)都被編輯為已訪問。既然在最后所有的點(diǎn)都被訪問，那么每個點(diǎn)都被標(biāo)記為屬于一個集群或者是噪聲。

相較于其他聚類算法，DBSCAN 提出了一些很棒的優(yōu)點(diǎn)。首先，它根本不需要預(yù)置集群的數(shù)量。它還將離群值認(rèn)定為噪聲，不像 mean-shift 中僅僅是將它們?nèi)拥揭粋€集群里，甚至即使該數(shù)據(jù)點(diǎn)的差異性很大也這么做。另外，這個算法還可以很好的找到任意尺寸核任意形狀的集群。

SBSCAN 最大的缺點(diǎn)是當(dāng)集群的密度變化時，它表現(xiàn)的不像其他算法那樣好。這是因?yàn)楫?dāng)密度變化時，距離的閾值 ε 和用于確定鄰居點(diǎn)的 minPoints 也將會隨之改變。這個缺點(diǎn)也會發(fā)生在很高為的數(shù)據(jù)中，因?yàn)榫嚯x閾值 ε 變得很難被估計。

基于高斯混合模型(GMM)的期望最大化（EM）聚類

k-means的一個主要缺點(diǎn)是它簡單地使用了集群中心的平均值。通過下面的圖片，我們可以看到為什么這不是最好的方式。在左手邊，人眼可以很明顯地看到，有兩個半徑不同的圓形星團(tuán)以相同的平均值為中心。k-means不能處理這個問題，因?yàn)椴煌氐钠骄捣浅＝咏．?dāng)簇不是圓形時，k均值也會失效，這也是將均值用作簇中心的后果。

數(shù)據(jù)科學(xué)中必須熟知的5種聚類算法

K-means不適用的case

高斯混合模型（gmms）具有更好的靈活性比K-means。使用GMMs，我們需要假設(shè)數(shù)據(jù)點(diǎn)是高斯分布，相對于環(huán)形的數(shù)據(jù)而言，這個假設(shè)的嚴(yán)格程度與均值相比弱很多。這樣的話，我們有兩個參數(shù)來描述簇的形狀：均值和標(biāo)準(zhǔn)差。以二維為例，意味簇可以是任何一種橢圓形（因?yàn)槲覀冇袃蓚€標(biāo)準(zhǔn)差在x和y方向）。因此，每個高斯分布會被分配到單一的聚類簇。

為了在每個聚類簇中找到這兩個高斯參數(shù)（e.g均值和標(biāo)準(zhǔn)差），我們將使用的優(yōu)化算法稱為expectation–maximization（EM）。請看下面的圖片，以說明將高斯擬合聚類簇。然后，我們可以處理EM聚類過程使用gmms。

數(shù)據(jù)科學(xué)中必須熟知的5種聚類算法

使用GMMs的EM聚類

我們首先設(shè)定聚類簇的數(shù)量（如k-means），然后隨機(jī)初始化每個集群的高斯分布參數(shù)。我們也可以通過快速查看數(shù)據(jù)來為初始參數(shù)提供一個很好的猜測。正如上圖所示，這不是100%必要的，因?yàn)楦咚共僮鏖_始時候是非常差的，但很快優(yōu)化。
給定每個簇的高斯分布，計算每個數(shù)據(jù)點(diǎn)屬于特定簇的概率。一個點(diǎn)越靠近高斯中心，它就越可能屬于該簇。這應(yīng)該是直觀的，因?yàn)閷τ诟咚狗植迹覀兗僭O(shè)大多數(shù)數(shù)據(jù)都靠近集群的中心。
基于這些概率，我們?yōu)楦咚狗植加嬎懔艘唤M新的參數(shù)，這樣我們就可以最大化群集中數(shù)據(jù)點(diǎn)的概率。我們使用數(shù)據(jù)點(diǎn)位置的加權(quán)和計算這些新參數(shù)，其中權(quán)重是屬于特定集群的數(shù)據(jù)點(diǎn)的概率。為了以可視化的方式解釋這一點(diǎn)，我們可以查看上面的圖形，特別是以黃色集群為例。在第一次迭代中，分布是隨機(jī)開始的，但是我們可以看到大多數(shù)黃點(diǎn)都在分布的右邊。當(dāng)我們計算一個由概率加權(quán)的和時，即使在中心附近有一些點(diǎn)，但大多數(shù)都在右邊。因此，分布的平均值很自然地移近這些點(diǎn)集。我們還可以看到，大多數(shù)點(diǎn)是“從右上到左下”。因此，標(biāo)準(zhǔn)偏差會發(fā)生變化，以創(chuàng)建一個更適合這些點(diǎn)的橢圓，以便最大化概率加權(quán)的和。
第2步和第3步重復(fù)進(jìn)行，直到收斂，也就是在收斂過程中，迭代變化不大。

使用GMMS有兩個關(guān)鍵優(yōu)勢。首先，GMMS在簇協(xié)方差方面比K均值靈活得多；由于標(biāo)準(zhǔn)偏差參數(shù)的存在，簇可以呈現(xiàn)任何橢圓形狀，而不局限于圓形。k均值實(shí)際上是GMM的一個特例，其中每個簇的所有維協(xié)方差都接近于0。其次，由于GMM使用概率，因此每個數(shù)據(jù)點(diǎn)可以有多個集群。因此，如果一個數(shù)據(jù)點(diǎn)位于兩個重疊集群的中間，我們可以簡單地定義它的類，方法是說它屬于類1的X%，屬于類2的Y%。即GMMS支持混合成員。

凝聚層次聚類

凝聚層次聚類算法實(shí)際上分為 2 類：自上而下或自下而上。自下而上算法在一開始將每個數(shù)據(jù)點(diǎn)當(dāng)作一個單個集群對待，然后逐步的合并（或凝聚）成對的集群，直到所有的集群被合并到一個集群中，這個集群包含所有的點(diǎn)。自下而上層次聚類因此被叫做層次凝聚的聚類或者 HAC。這個聚類的層次被表示為一棵樹（或者樹狀圖）。樹根是唯一的集群，他聚集了所有的樣本，葉子是只有一個樣本的集群。在接著看算法步驟之前，請查看下面的圖示說明。

數(shù)據(jù)科學(xué)中必須熟知的5種聚類算法

凝聚層次聚類

我們通過將每個點(diǎn)視作一個單個集群作為開始，即如果我們的數(shù)據(jù)集中有 X 個數(shù)據(jù)點(diǎn)，那么我們就有 X 個集群。我們?nèi)缓筮x擇一個距離度量標(biāo)準(zhǔn)來測量兩個集群之間的距離。作為一個例子，我們將用到平均連接，它將兩個集群之間的距離定義為第一個集群中的數(shù)據(jù)點(diǎn)與第二個集群中數(shù)據(jù)點(diǎn)的平均距離。
在每次迭代時，我們將兩個集群組合成一個。兩個將被組合的集群是在那些有最小平均連接的集群中選出來的，即根據(jù)我們選擇的距離度量標(biāo)準(zhǔn)，這些兩兩集群之間有最小的距離，且因此是最相似的也最應(yīng)該被組合。
一直重復(fù)第二步，直到我們到達(dá)樹的根部，即我們只有一個包含所有數(shù)據(jù)點(diǎn)的集群。通過這種方法，我們僅僅通過選擇停止組合的集群的時機(jī)，即選擇何時停止樹的構(gòu)建，就可以挑選出最終我們想要的集群數(shù)。

層次聚類不要求我們指定集群的數(shù)目，并且我們甚至可以選擇看上去最好的集群的數(shù)目，因?yàn)槲覀冋跇?gòu)建一棵樹。另外，算法對于距離度量的選擇也是不敏感的；所有的這些都和其他聚類算法的效果一樣好，而對于其他算法，距離度量的選擇是很關(guān)鍵的。層次聚類方法的一個典型的使用案例是當(dāng)?shù)讓訑?shù)據(jù)具有層次結(jié)構(gòu)并且要恢復(fù)層次結(jié)構(gòu)時；其他聚類算法做不到這個。這些層次聚類的優(yōu)點(diǎn)的代價是效率很低，因?yàn)樗臅r間復(fù)雜度是O(n3)，不像有線性復(fù)雜度的 K-Means 和 GMM 那樣。