Must Know！數(shù)據(jù)科學(xué)家們必須知道的5種聚類算法

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

2018-03-13 09:56

導(dǎo)語：聚類是一種無監(jiān)督學(xué)習(xí)方法，也是一種統(tǒng)計(jì)數(shù)據(jù)分析的常用技術(shù)，被廣泛應(yīng)用于眾多領(lǐng)域。

本文為雷鋒字幕組編譯的技術(shù)博客，原標(biāo)題The 5 Clustering Algorithms Data Scientists Need to Know，作者為George Seif。

翻譯 | 姜波整理 | 凡江吳璇

聚類是一種關(guān)于數(shù)據(jù)點(diǎn)分組的機(jī)器學(xué)習(xí)技術(shù)。給出一組數(shù)據(jù)點(diǎn)，我們可以使用聚類算法將每個(gè)數(shù)據(jù)點(diǎn)分類到特定的組中。理論上，同一組中的數(shù)據(jù)點(diǎn)應(yīng)具有相似的屬性或特征，而不同組中的數(shù)據(jù)點(diǎn)應(yīng)具有相當(dāng)不同的屬性或特征（即類內(nèi)差異小，類間差異大）。聚類是一種無監(jiān)督學(xué)習(xí)方法，也是一種統(tǒng)計(jì)數(shù)據(jù)分析的常用技術(shù)，被廣泛應(yīng)用于眾多領(lǐng)域。

在數(shù)據(jù)科學(xué)中，我們可以通過聚類算法，查看數(shù)據(jù)點(diǎn)屬于哪些組，并且從這些數(shù)據(jù)中獲得一些有價(jià)值的信息。今天，我們一起來看看數(shù)據(jù)科學(xué)家需要了解的5種流行聚類算法以及它們的優(yōu)缺點(diǎn)。

一、K均值聚類

K-Means可能是最知名的聚類算法了。在數(shù)據(jù)科學(xué)或機(jī)器學(xué)習(xí)課程中都有過它的介紹。K-Means的代碼也非常容易理解和實(shí)現(xiàn)。請(qǐng)查看下面的圖片：

Must Know！數(shù)據(jù)科學(xué)家們必須知道的5種聚類算法

開始，我們先選取一些類型或者組類，分別隨機(jī)初始化它們的中心點(diǎn)。要計(jì)算出使用的類的數(shù)量，最好快速查看數(shù)據(jù)并嘗試識(shí)別不同的分組。中心點(diǎn)是與每個(gè)數(shù)據(jù)點(diǎn)向量長(zhǎng)度相同的向量，并且是上圖中的‘X’s’。
每一個(gè)數(shù)據(jù)點(diǎn)，是通過計(jì)算該點(diǎn)與每一組中的點(diǎn)之間的距離，來進(jìn)行分類的，然后將該點(diǎn)歸類到距離中心最近的組。
基于這些分類的點(diǎn)，我們通過求取每一組中所有向量的均值，重復(fù)計(jì)算每一組的中心點(diǎn)。
重復(fù)上述步驟，直到每一組的中心點(diǎn)不再發(fā)生變化或者變化不大為止。你也可以選擇對(duì)組中心點(diǎn)進(jìn)行多次隨機(jī)初始化，選擇運(yùn)行效果最好的即可。
由于我們所做的只是計(jì)算點(diǎn)和組中心之間的距離，計(jì)算量較小，因此K-Means的一大優(yōu)點(diǎn)就是運(yùn)行速度非?？?。所以它具有線性復(fù)雜度O(n）。

當(dāng)然，K-Means也有兩個(gè)缺點(diǎn)。首先，你必須選擇有分類組的數(shù)目（如聚為3類，則K=3）。這并不能忽略，理想情況下，我們希望它使用聚類算法來幫助我們理解這些數(shù)據(jù)，因?yàn)樗闹攸c(diǎn)在于從數(shù)據(jù)中獲得一些有價(jià)值的發(fā)現(xiàn)。由于K-means算法選擇的聚類中心是隨機(jī)的（即初始化是隨機(jī)的），因此它可能會(huì)因?yàn)轭悢?shù)不同而運(yùn)行算法中產(chǎn)生不同的聚類結(jié)果。因此，結(jié)果可能不可重復(fù)且缺乏一致性。相反，其他集群方法更一致。

K-Medians是與K-Means有關(guān)的另一種聚類算法，不同之處在于我們使用組的中值向量來重新計(jì)算組中心點(diǎn)。該方法對(duì)異常值不敏感（因?yàn)槭褂弥兄担?，但?duì)于較大的數(shù)據(jù)集運(yùn)行速度就要慢得多，因?yàn)樵谟?jì)算中值向量時(shí)，需要在每次迭代時(shí)進(jìn)行排序。

二、Mean-Shift聚類

平均移位聚類是基于滑動(dòng)窗口的算法，試圖找到密集的數(shù)據(jù)點(diǎn)區(qū)域。這是一種基于質(zhì)心的算法，意味著目標(biāo)是定位每個(gè)組/類的中心點(diǎn)，通過更新中心點(diǎn)的候選點(diǎn)作為滑動(dòng)窗口內(nèi)點(diǎn)的平均值來工作。然后在后處理（相對(duì)‘預(yù)處理’來說的）階段對(duì)這些候選窗口進(jìn)行濾波以消除近似重復(fù)，形成最終的中心點(diǎn)集及其相應(yīng)的組。請(qǐng)查看下面的圖片：

Must Know！數(shù)據(jù)科學(xué)家們必須知道的5種聚類算法

Mean-Shift聚類用于單個(gè)滑動(dòng)窗口

為了解釋平均偏移，我們將考慮像上圖那樣的二維空間中的一組點(diǎn)。我們從以C點(diǎn)（隨機(jī)選擇）為中心并以半徑r為核心的圓滑動(dòng)窗口開始。平均偏移是一種爬山算法，它涉及將這個(gè)核迭代地轉(zhuǎn)移到每個(gè)步驟中更高密度的區(qū)域，直到收斂。
在每次迭代中，通過將中心點(diǎn)移動(dòng)到窗口內(nèi)的點(diǎn)的平均值（因此得名），將滑動(dòng)窗口移向較高密度的區(qū)域?；瑒?dòng)窗口內(nèi)的密度與其內(nèi)部的點(diǎn)數(shù)成正比。當(dāng)然，通過轉(zhuǎn)換到窗口中的點(diǎn)的平均值，它將逐漸走向更高點(diǎn)密度的區(qū)域。
我們繼續(xù)根據(jù)平均值移動(dòng)滑動(dòng)窗口，直到?jīng)]有方向移位可以在內(nèi)核中容納更多點(diǎn)。看看上面的圖片;我們繼續(xù)移動(dòng)該圓，直到我們不再增加密度（即窗口中的點(diǎn)數(shù)）。
步驟1至3的這個(gè)過程用許多滑動(dòng)窗口完成，直到所有點(diǎn)位于一個(gè)窗口內(nèi)。當(dāng)多個(gè)滑動(dòng)窗口重疊時(shí)，保留包含最多點(diǎn)的窗口。數(shù)據(jù)點(diǎn)然后根據(jù)它們所在的滑動(dòng)窗口聚類。

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

Must Know！數(shù)據(jù)科學(xué)家們必須知道的5種聚類算法

Mean-Shift聚類的整個(gè)過程

與K均值聚類相比，不需要選擇聚類數(shù)量，因?yàn)榫灯瓶梢宰詣?dòng)發(fā)現(xiàn)。這是一個(gè)巨大的優(yōu)勢(shì)。聚類中心向最大密度點(diǎn)聚合的結(jié)果也是非常令人滿意的，因?yàn)樗睦斫獗容^符合數(shù)據(jù)驅(qū)動(dòng)的規(guī)律，且十分直觀。缺點(diǎn)是窗口大小/半徑r的選擇是非常重要的，換句話說半徑的選擇決定了運(yùn)行結(jié)果。

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

DBSCAN是一種基于密度的聚類算法，類似于mean-shift，但其擁有一些顯著的優(yōu)點(diǎn)。看看下面的另一個(gè)花哨的圖形，讓我們開始吧！

Must Know！數(shù)據(jù)科學(xué)家們必須知道的5種聚類算法

DBSCAN以任何尚未訪問過的任意起始數(shù)據(jù)點(diǎn)開始。這個(gè)點(diǎn)的鄰域用距離epsilon提?。é啪嚯x內(nèi)的所有點(diǎn)都是鄰域點(diǎn)）。
如果在該鄰域內(nèi)有足夠數(shù)量的點(diǎn)（根據(jù)minPoints），則聚類過程將開始并且當(dāng)前數(shù)據(jù)點(diǎn)將成為新聚類中的第一個(gè)點(diǎn)。否則，該點(diǎn)將被標(biāo)記為噪聲（稍后，這個(gè)噪聲點(diǎn)可能會(huì)成為群集的一部分）。在這兩種情況下，該點(diǎn)都被標(biāo)記為“已訪問”。
對(duì)于新簇中的第一個(gè)點(diǎn)，ε距離鄰域內(nèi)的點(diǎn)也成為同一個(gè)簇的一部分。然后對(duì)已經(jīng)添加到群集組中的所有新點(diǎn)重復(fù)使ε鄰域中的所有點(diǎn)屬于同一個(gè)群集的過程。
重復(fù)步驟2和3的這個(gè)過程直到聚類中的所有點(diǎn)都被確定，即聚類的ε鄰域內(nèi)的所有點(diǎn)都被訪問和標(biāo)記。
一旦我們完成了當(dāng)前的集群，一個(gè)新的未訪問點(diǎn)被檢索和處理，導(dǎo)致發(fā)現(xiàn)更多的集群或噪聲。重復(fù)此過程，直到所有點(diǎn)都被標(biāo)記為已訪問。由于所有點(diǎn)已經(jīng)被訪問完畢，每個(gè)點(diǎn)都被標(biāo)記為屬于一個(gè)簇或是噪聲。
與其他聚類算法相比，DBSCAN具有一些很大的優(yōu)勢(shì)。首先，它根本不需要pe-set數(shù)量的簇。它還將異常值識(shí)別為噪聲，而不像mean-shift，即使數(shù)據(jù)點(diǎn)非常不同，它們也會(huì)將它們引入群集中。另外，它能夠很好地找到任意大小和任意形狀的簇。

DBSCAN的主要缺點(diǎn)是，當(dāng)簇的密度不同時(shí)，DBSCAN的性能不如其他組織。這是因?yàn)楫?dāng)密度變化時(shí)，用于識(shí)別鄰近點(diǎn)的距離閾值ε和minPoints的設(shè)置將隨著群集而變化。對(duì)于非常高維的數(shù)據(jù)也會(huì)出現(xiàn)這種缺點(diǎn)，因?yàn)榫嚯x閾值ε再次難以估計(jì)。

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

K-Means的主要缺點(diǎn)之一是其使用了集群中心的平均值。通過查看下面的圖片，我們可以明白為什么這不是選取聚類中心的最佳方式。在左側(cè)，人眼看起來非常明顯的是，有兩個(gè)半徑不同的圓形星團(tuán)以相同的平均值為中心。K-Means無法處理這個(gè)問題，因?yàn)檫@些集群的平均值非常接近。K-Means在集群不是圓形的情況下也會(huì)出錯(cuò)，這也是因?yàn)槭褂镁底鳛榧褐行牡脑颉?/p>

Must Know！數(shù)據(jù)科學(xué)家們必須知道的5種聚類算法

K-Means的兩個(gè)失敗案例

高斯混合模型（GMMs）比K-Means更具靈活性。對(duì)于GMM，我們假設(shè)數(shù)據(jù)點(diǎn)是高斯分布的。這是一個(gè)限制較少的假設(shè)，而不是用均值來表示它們是循環(huán)的。這樣，我們有兩個(gè)參數(shù)來描述群集的形狀，均值和標(biāo)準(zhǔn)差。以二維數(shù)據(jù)為例，這意味著群集可以采取任何類型的橢圓形（因?yàn)槲覀冊(cè)趚和y方向都有標(biāo)準(zhǔn)偏差）。因此，每個(gè)高斯分布被分配給單個(gè)集群。

為了找到每個(gè)群集的高斯參數(shù)（例如平均值和標(biāo)準(zhǔn)偏差），我們將使用期望最大化（EM）的優(yōu)化算法。看看下面的圖表，作為適合群集的高斯圖的例證。然后我們可以繼續(xù)進(jìn)行使用GMM的期望最大化聚類過程

Must Know！數(shù)據(jù)科學(xué)家們必須知道的5種聚類算法

使用GMM的EM聚類

我們首先選擇簇的數(shù)量（如K-Means）并隨機(jī)初始化每個(gè)簇的高斯分布參數(shù)。人們可以嘗試通過快速查看數(shù)據(jù)來為初始參數(shù)提供良好的假設(shè)。請(qǐng)注意，這不是100％必要的，因?yàn)殚_始時(shí)高斯分布化非常弱，雖然從上圖可以看出，但隨著算法的運(yùn)行很快就能得到優(yōu)化。
給定每個(gè)群集的這些高斯分布，計(jì)算每個(gè)數(shù)據(jù)點(diǎn)屬于特定群集的概率。一個(gè)點(diǎn)越接近高斯中心，它越可能屬于該群。這應(yīng)該是直觀的，因?yàn)閷?duì)于高斯分布，我們假設(shè)大部分?jǐn)?shù)據(jù)更靠近集群的中心。
基于這些概率，我們?yōu)楦咚狗植加?jì)算一組新的參數(shù)，以便使集群內(nèi)數(shù)據(jù)點(diǎn)的概率最大化。我們使用數(shù)據(jù)點(diǎn)位置的加權(quán)和來計(jì)算這些新參數(shù)，其中權(quán)重是屬于該特定群集中的數(shù)據(jù)點(diǎn)的概率。為了以可視化的方式解釋這一點(diǎn)，我們可以看看上面的圖片，特別是黃色的群集。分布從第一次迭代開始隨機(jī)開始，但我們可以看到大部分黃點(diǎn)都在該分布的右側(cè)。當(dāng)我們計(jì)算一個(gè)按概率加權(quán)的和時(shí)，即使中心附近有一些點(diǎn)，它們中的大部分都在右邊。因此，分配的均值自然會(huì)更接近這些點(diǎn)的集合。我們也可以看到，大部分要點(diǎn)都是“從右上到左下”。因此，標(biāo)準(zhǔn)偏差改變以創(chuàng)建更適合這些點(diǎn)的橢圓，以便最大化由概率加權(quán)的總和。
步驟2和3迭代地重復(fù)直到收斂，其中分布從迭代到迭代的變化不大。

使用GMM有兩個(gè)關(guān)鍵優(yōu)勢(shì)。首先GMM比K-Means在群協(xié)方面更靈活。由于標(biāo)準(zhǔn)偏差參數(shù)，集群可以采取任何橢圓形狀，而不是限于圓形。K均值實(shí)際上是GMM的一個(gè)特例，其中每個(gè)群的協(xié)方差在所有維上都接近0。其次，由于GMM使用概率，每個(gè)數(shù)據(jù)點(diǎn)可以有多個(gè)群。因此，如果一個(gè)數(shù)據(jù)點(diǎn)位于兩個(gè)重疊的簇的中間，我們可以簡(jiǎn)單地定義它的類，將其歸類為類1的概率為百分之x，類2的概率為百分之y。

五、凝聚層次聚類

分層聚類算法實(shí)際上分為兩類：自上而下或自下而上。自下而上算法首先將每個(gè)數(shù)據(jù)點(diǎn)視為單個(gè)群集，然后連續(xù)合并（或聚合）成對(duì)的群集，直到所有群集合并成包含所有數(shù)據(jù)點(diǎn)的單個(gè)群集。自下而上的層次聚類因此被稱為分層凝聚聚類或HAC。該簇的層次結(jié)構(gòu)被表示為樹（或樹狀圖）。樹的根是收集所有樣本的唯一聚類，葉是僅有一個(gè)樣本的聚類。在進(jìn)入算法步驟之前，請(qǐng)查看下面的圖解。

Must Know！數(shù)據(jù)科學(xué)家們必須知道的5種聚類算法

凝聚層次聚類

我們首先將每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)單一的聚類，即如果我們的數(shù)據(jù)集中有X個(gè)數(shù)據(jù)點(diǎn)，則我們有X個(gè)聚類。然后我們選擇一個(gè)度量?jī)蓚€(gè)集群之間距離的距離度量。作為一個(gè)例子，我們將使用平均關(guān)聯(lián)，它將兩個(gè)集群之間的距離定義為第一個(gè)集群中的數(shù)據(jù)點(diǎn)與第二個(gè)集群中的數(shù)據(jù)點(diǎn)之間的平均距離。
在每次迭代中，我們將兩個(gè)群集合并成一個(gè)群集。將要組合的兩個(gè)群被選為平均聯(lián)系最小的群。即根據(jù)我們選擇的距離度量，這兩個(gè)群集之間的距離最小，因此是最相似的，應(yīng)該結(jié)合起來。
重復(fù)步驟2直到我們到達(dá)樹的根部，即我們只有一個(gè)包含所有數(shù)據(jù)點(diǎn)的聚類。通過這種方式，我們可以最終選擇我們想要的簇?cái)?shù)量，只需選擇何時(shí)停止組合簇，即停止構(gòu)建樹。

分層聚類不需要我們指定聚類的數(shù)量，我們甚至可以選擇哪個(gè)數(shù)量的聚類看起來最好，因?yàn)槲覀冋跇?gòu)建一棵樹。另外，該算法對(duì)距離度量的選擇不敏感;他們都傾向于工作同樣好，而與其他聚類算法，距離度量的選擇是至關(guān)重要的。分層聚類方法的一個(gè)特別好的用例是基礎(chǔ)數(shù)據(jù)具有層次結(jié)構(gòu)并且您想要恢復(fù)層次結(jié)構(gòu);其他聚類算法無法做到這一點(diǎn)。與K-Means和GMM的線性復(fù)雜性不同，這種層次聚類的優(yōu)點(diǎn)是以較低的效率為代價(jià)，因?yàn)樗哂蠴（n3）的時(shí)間復(fù)雜度。

結(jié)論

數(shù)據(jù)科學(xué)家應(yīng)該知道的這5個(gè)聚類算法！我們將期待一些其他的算法的執(zhí)行情況以及可視化，敬請(qǐng)期待Scikit Learn！

Must Know！數(shù)據(jù)科學(xué)家們必須知道的5種聚類算法