聚類是一種將數(shù)據(jù)點(diǎn)按一定規(guī)則分群的機(jī)器學(xué)習(xí)技術(shù)。

給定一組數(shù)據(jù)點(diǎn)，我們可以使用聚類算法將每個(gè)數(shù)據(jù)點(diǎn)分類到一個(gè)特定的簇中。理論上，屬于同一類的數(shù)據(jù)點(diǎn)應(yīng)具有相似的屬性或特征，而不同類中的數(shù)據(jù)點(diǎn)應(yīng)具有差異很大的屬性或特征。

聚類屬于無監(jiān)督學(xué)習(xí)中的一種方法，也是一種在許多領(lǐng)域中用于統(tǒng)計(jì)數(shù)據(jù)分析的常用技術(shù)。在數(shù)據(jù)科學(xué)中，我們可以使用聚類分析，來獲得一些有價(jià)值的信息。其手段是在應(yīng)用聚類算法時(shí)，查看數(shù)據(jù)點(diǎn)會落入哪些類。

現(xiàn)在，我們來看看數(shù)據(jù)科學(xué)家們需要掌握的5種常見聚類算法以及它們的優(yōu)缺點(diǎn)！　　▌K-均值聚類　　K-Means可能是最知名的聚類算法，沒有之一。在很多介紹性的數(shù)據(jù)科學(xué)和機(jī)器學(xué)習(xí)課程中，都有講授該算法。并且該算法的代碼很容易理解和實(shí)現(xiàn)！你可以通過看下面的插圖來理解它。

K均值聚類

1、首先，我們選擇一些要使用的類/組，并隨機(jī)初始化他們各自的中心點(diǎn)（質(zhì)心）。要計(jì)算出簇（類）的使用數(shù)量，最好的方法是快速查看一下數(shù)據(jù)并嘗試鑒別有多少不同的分組。中心點(diǎn)是一個(gè)矢量，它到每個(gè)數(shù)據(jù)點(diǎn)的矢量長度相同，在上圖中用“X”來表示。　　2、每個(gè)數(shù)據(jù)點(diǎn)通過計(jì)算該點(diǎn)與每個(gè)簇中心之間的距離來進(jìn)行分類，根據(jù)最小距離，將該點(diǎn)分類到對應(yīng)中心點(diǎn)的簇中。　　3、根據(jù)這些已分類的點(diǎn)，我們重新計(jì)算簇中所有向量的均值，來確定新的中心點(diǎn)。　　4、重復(fù)以上步驟來進(jìn)行一定數(shù)量的迭代，或者直到簇中心點(diǎn)在迭代之間變化不大。你也可以選擇多次隨機(jī)初始化簇中心點(diǎn)，然后選擇看起來像是最佳結(jié)果的數(shù)據(jù)，再來重復(fù)以上步驟。　　K-Means算法的優(yōu)勢在于它的速度非常快，因?yàn)槲覀兯龅闹皇怯?jì)算點(diǎn)和簇中心之間的距離; 這已經(jīng)是非常少的計(jì)算了！因此它具有線性的復(fù)雜度O(n)。　　但是，K-Means算法也是有一些缺點(diǎn)。首先，你必須手動(dòng)選擇有多少簇。

這是一個(gè)很大的弊端，理想情況下，我們是希望能使用一個(gè)聚類算法來幫助我們找出有多少簇，因?yàn)榫垲愃惴ǖ哪康木褪菑臄?shù)據(jù)中來獲得一些有用信息。

K-means算法的另一個(gè)缺點(diǎn)是從隨機(jī)選擇的簇中心點(diǎn)開始運(yùn)行，這導(dǎo)致每一次運(yùn)行該算法可能產(chǎn)生不同的聚類結(jié)果。

因此，該算法結(jié)果可能具有不可重復(fù)，缺乏一致性等性質(zhì)。而其他聚類算法的結(jié)果則會顯得更一致一些。　　K-Medians是與K-Means類似的另一種聚類算法，它是通過計(jì)算類中所有向量的中值，而不是平均值，來確定簇的中心點(diǎn)。

這種方法的優(yōu)點(diǎn)是對數(shù)據(jù)中的異常值不太敏感，但是在較大的數(shù)據(jù)集時(shí)進(jìn)行聚類時(shí)，速度要慢得多，造成這種現(xiàn)象的原因是這種方法每次迭代時(shí)，都需要對數(shù)據(jù)進(jìn)行排序。　　▌Mean-Shift聚類算法　　Mean-Shift是一種基于滑動(dòng)窗口的聚類算法。也可以說它是一種基于質(zhì)心的算法，這意思是它是通過計(jì)算滑動(dòng)窗口中的均值來更新中心點(diǎn)的候選框，以此達(dá)到找到每個(gè)簇中心點(diǎn)的目的。然后在剩下的處理階段中，對這些候選窗口進(jìn)行濾波以消除近似或重復(fù)的窗口，找到最終的中心點(diǎn)及其對應(yīng)的簇。看看下面的圖解。

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

1、為了闡釋Mean-shift算法，我們可以考慮二維空間中的一組點(diǎn)，如上圖所示。我們從一個(gè)以C點(diǎn)（隨機(jī)選擇）為中心，以半徑r為核心的圓滑動(dòng)窗口開始。Mean-shift可以看作是一種等高線算法，在每次迭代中，它能將核函數(shù)（圓滑動(dòng)窗口）移動(dòng)到每個(gè)迭代中較高密度的區(qū)域，直至收斂。　　2、在每次迭代中，通過將中心點(diǎn)移動(dòng)到窗口內(nèi)點(diǎn)的平均值處（因此得名），來使滑動(dòng)窗口移向更高密度的區(qū)域。滑動(dòng)窗口內(nèi)的數(shù)據(jù)密度與其內(nèi)部點(diǎn)的數(shù)目成正比。當(dāng)然，通過移動(dòng)窗口中點(diǎn)的平均值，它（滑動(dòng)窗口）就會逐漸移向點(diǎn)密度更高的區(qū)域。　　3、我們繼續(xù)根據(jù)平均值來移動(dòng)滑動(dòng)窗口，直到不能找到一個(gè)移動(dòng)方向，使滑動(dòng)窗口可以容納更多的點(diǎn)。看看上面圖片的動(dòng)畫效果；直到滑動(dòng)窗口內(nèi)不再增加密度（即窗口中的點(diǎn)數(shù)），我們才停止移動(dòng)這個(gè)圓圈。　　4、步驟1至步驟3的過程是由許多滑動(dòng)窗口來完成的，直到所有的點(diǎn)都能位于對應(yīng)窗口內(nèi)時(shí)才停止。當(dāng)多個(gè)滑動(dòng)窗口重疊時(shí)，該算法就保留包含最多點(diǎn)的窗口。最終所有數(shù)據(jù)點(diǎn)根據(jù)它們所在的滑動(dòng)窗口來確定分到哪一類。　　下圖顯示了所有滑動(dòng)窗口從頭到尾的整個(gè)移動(dòng)過程。每個(gè)黑點(diǎn)代表滑動(dòng)窗口的質(zhì)心，每個(gè)灰點(diǎn)代表一個(gè)數(shù)據(jù)點(diǎn)。

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

與K-means聚類算法相比，Mean-shift算法是不需要選擇簇的數(shù)量，因?yàn)樗亲詣?dòng)找尋有幾類。這是一個(gè)相比其他算法巨大的優(yōu)點(diǎn)。而且該算法的聚類效果也是非常理想的，在自然數(shù)據(jù)驅(qū)動(dòng)的情況下，它能非常直觀的展現(xiàn)和符合其意義。算法的缺點(diǎn)是固定了窗口大小/半徑“r”。　　▌基于密度的噪聲應(yīng)用空間聚類（DBSCAN）　　DBSCAN是一種基于密度的聚類算法，類似于Mean-shift算法，但具有一些顯著的優(yōu)點(diǎn)。我們從看下面這個(gè)奇特的圖形開始了解該算法。

DBSCAN笑臉人臉聚類

1、DBSCAN算法從一個(gè)未被訪問的任意的數(shù)據(jù)點(diǎn)開始。這個(gè)點(diǎn)的鄰域是用距離epsilon來定義（即該點(diǎn)ε距離范圍內(nèi)的所有點(diǎn)都是鄰域點(diǎn)）。　　2、如果在該鄰域內(nèi)有足夠數(shù)量的點(diǎn)（根據(jù)minPoints的值），則聚類過程開始，并且當(dāng)前數(shù)據(jù)點(diǎn)成為新簇中的第一個(gè)點(diǎn)。否則，該點(diǎn)將被標(biāo)記為噪聲（稍后，這個(gè)噪聲點(diǎn)可能成為聚類中的一部分）。在這兩種情況下，該點(diǎn)都會被標(biāo)記為“已訪問”。　　3、對于新簇中的第一個(gè)點(diǎn)，它的ε距離鄰域內(nèi)的點(diǎn)也會成為同簇的一部分。這個(gè)過程使ε鄰域內(nèi)的所有點(diǎn)都屬于同一個(gè)簇，然后對才添加到簇中的所有新點(diǎn)重復(fù)上述過程。　　4、重復(fù)步驟2和3兩個(gè)過程直到確定了聚類中的所有點(diǎn)才停止，即訪問和標(biāo)記了聚類的ε鄰域內(nèi)的所有點(diǎn)。　　5、一旦我們完成了當(dāng)前的聚類，就檢索和處理新的未訪問的點(diǎn)，就能進(jìn)一步發(fā)現(xiàn)新的簇或者是噪聲。重復(fù)上述過程，直到所有點(diǎn)被標(biāo)記為已訪問才停止。由于所有點(diǎn)已經(jīng)被訪問完畢，每個(gè)點(diǎn)都被標(biāo)記為屬于一個(gè)簇或是噪聲。　　與其他聚類算法相比，DBSCAN具有很多優(yōu)點(diǎn)。首先，它根本不需要確定簇的數(shù)量。不同于Mean-shift算法，當(dāng)數(shù)據(jù)點(diǎn)非常不同時(shí)，會將它們單純地引入簇中，DBSCAN能將異常值識別為噪聲。另外，它能夠很好地找到任意大小和任意形狀的簇。　　DBSCAN算法的主要缺點(diǎn)是，當(dāng)數(shù)據(jù)簇密度不均勻時(shí)，它的效果不如其他算法好。這是因?yàn)楫?dāng)密度變化時(shí)，用于識別鄰近點(diǎn)的距離閾值ε和minPoints的設(shè)置將隨著簇而變化。在處理高維數(shù)據(jù)時(shí)也會出現(xiàn)這種缺點(diǎn)，因?yàn)殡y以估計(jì)距離閾值ε。　　▌使用高斯混合模型（GMM）的期望最大化（EM）聚類　　K-Means算法的主要缺點(diǎn)之一就是它對于聚類中心平均值的使用太單一。

通過查看下面的圖例，我們可以明白為什么它不是使用均值最佳的方式。

在左側(cè)，人眼看起來非常明顯的是，具有相同均值的數(shù)據(jù)中心點(diǎn)，卻是不同半徑長度的兩個(gè)圓形簇。

而K-Means算法不能解決這樣的數(shù)據(jù)問題，因?yàn)檫@些簇的均值是非常接近的。

K-Means算法在簇不是圓形的情況下也一樣無效，也是由于使用均值作為集群中心。

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

相較于K-means算法，高斯混合模型（GMMs）能處理更多的情況。對于GMM，我們假設(shè)數(shù)據(jù)點(diǎn)是高斯分布的; 這是一個(gè)限制較少的假設(shè)，而不是用均值來表示它們是圓形的。這樣，我們有兩個(gè)參數(shù)來描述簇的形狀：即均值和標(biāo)準(zhǔn)差！以二維為例，這意味著這些簇可以是任何類型的橢圓形（因?yàn)镚MM在x和y方向上都有標(biāo)準(zhǔn)偏差）。因此，每個(gè)高斯分布都被單個(gè)簇所指定。　　為了找到每個(gè)簇的高斯參數(shù)（例如平均值和標(biāo)準(zhǔn)差），我們將使用期望最大化（EM）的優(yōu)化算法。請看下面的圖表，可以作為匹配簇的高斯圖的闡釋。然后我們來完成使用GMM的期望最大化聚類過程。

使用GMM的EM聚類

1、我們首先選擇簇的數(shù)量（如K-Means），然后隨機(jī)初始化每個(gè)簇的高斯分布參數(shù)。可以通過快速查看數(shù)據(jù)的方式，來嘗試為初始參數(shù)提供一個(gè)較好的猜測。不過請注意，從上圖可以看出，這不是100％必要的，因?yàn)榧词故菑囊粋€(gè)很差的高斯分布開始，算法也能很快的優(yōu)化它。　　2、給定每個(gè)簇的高斯分布，計(jì)算每個(gè)數(shù)據(jù)點(diǎn)屬于特定簇的概率。一個(gè)點(diǎn)越靠近高斯的中心，它越可能屬于該簇。在使用高斯分布時(shí)這應(yīng)該是非常直觀的，因?yàn)槲覀兗僭O(shè)大部分?jǐn)?shù)據(jù)更靠近簇的中心。　　3、基于這些概率，我們?yōu)楦咚狗植加?jì)算一組新的參數(shù)，使得我們能最大化簇內(nèi)數(shù)據(jù)點(diǎn)的概率。我們使用數(shù)據(jù)點(diǎn)位置的加權(quán)和來計(jì)算這些新參數(shù)，其中權(quán)重是數(shù)據(jù)點(diǎn)屬于該特定簇的概率。為了更直觀的解釋這個(gè)，我們可以看看上面的圖片，特別是黃色的簇。第一次迭代時(shí)，分布是隨機(jī)開始，但是我們可以看到大部分黃點(diǎn)都在分布的右側(cè)。當(dāng)我們計(jì)算按概率加權(quán)的和時(shí)，即使中心附近的點(diǎn)大部分都在右邊，通過分配的均值自然就會接近這些點(diǎn)。我們也可以看到，大部分?jǐn)?shù)據(jù)點(diǎn)都是“從右上到左下”。因此，改變標(biāo)準(zhǔn)差的值，可以找到一個(gè)更適合這些點(diǎn)的橢圓，以最大化概率加權(quán)的總和。　　4、重復(fù)迭步驟2和3，直到收斂，也就是分布在迭代中基本再無變化。　　使用GMM方法有兩個(gè)很重要的優(yōu)點(diǎn)。 首先，GMM方法在聚類協(xié)方差上比K-Means靈活得多; 由于使用了標(biāo)準(zhǔn)偏差參數(shù)，簇可以呈現(xiàn)任何橢圓形狀，而不是被限制為圓形。 K-mean算法實(shí)際上是GMM的一個(gè)特殊情況，即每個(gè)簇的協(xié)方差在所有維度上都接近0。其次，由于GMM使用了概率，每個(gè)數(shù)據(jù)點(diǎn)可以有多個(gè)簇。因此，如果一個(gè)數(shù)據(jù)點(diǎn)位于兩個(gè)重疊的簇的中間，我們可以簡單地定義它的類，即屬于類1的概率是百分之X，屬于類2的概率是百分之Y。即，GMM支持混合類這種情況。　　▌凝聚層次聚類　　分層聚類算法實(shí)際上分為兩類：自上而下或自下而上。

自下而上的算法首先將每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)單一的簇，然后連續(xù)地合并（或聚合）成對的簇，直到所有的簇都合并成一個(gè)包含所有數(shù)據(jù)點(diǎn)的簇。

因此，自下而上的分層聚類被稱為合成聚類或HAC。

這個(gè)簇的層次可以用樹（或樹狀圖）表示。樹的根是收集所有樣本的唯一簇，葉是僅具有一個(gè)樣本的簇。

在進(jìn)入算法步驟之前，請查看下面的圖解。

合成聚類

1、我們首先將每個(gè)數(shù)據(jù)點(diǎn)視為一個(gè)單一的簇，即如果我們的數(shù)據(jù)集中有X個(gè)數(shù)據(jù)點(diǎn)，那么我們就有X個(gè)簇。然后，我們選擇一個(gè)距離度量，來度量兩個(gè)簇之間距離。作為一個(gè)例子，我們將使用平均關(guān)聯(lián)度量，它將兩個(gè)簇之間的距離定義為第一個(gè)簇中的數(shù)據(jù)點(diǎn)與第二個(gè)簇中的數(shù)據(jù)點(diǎn)之間的平均距離。　　2、在每次迭代中，我們將兩個(gè)簇合并成一個(gè)簇。選擇平均關(guān)聯(lián)值最小的兩個(gè)簇進(jìn)行合并。根據(jù)我們選擇的距離度量，這兩個(gè)簇之間的距離最小，因此是最相似的，所有應(yīng)該合并。　　3、重復(fù)步驟2直到我們到達(dá)樹的根，即我們只有一個(gè)包含所有數(shù)據(jù)點(diǎn)的簇。通過這種方式，我們可以選擇最終需要多少個(gè)簇。方法就是選擇何時(shí)停止合并簇，即停止構(gòu)建樹時(shí)！　　分層次聚類不需要我們指定簇的數(shù)量，我們甚至可以在構(gòu)建樹的同時(shí)，選擇一個(gè)看起來效果最好的簇的數(shù)量。

另外，該算法對距離度量的選擇并不敏感；

與其他距離度量選擇很重要的聚類算法相比，該算法下的所有距離度量方法都表現(xiàn)得很好。

當(dāng)基礎(chǔ)數(shù)據(jù)具有層次結(jié)構(gòu)，并且想要恢復(fù)層次結(jié)構(gòu)時(shí)，層次聚類算法能實(shí)現(xiàn)這一目標(biāo)；

而其他聚類算法則不能做到這一點(diǎn)。

與K-Means和GMM的線性復(fù)雜性不同，層次聚類的這些優(yōu)點(diǎn)是以較低的效率為代價(jià)，即它具有O（n3）的時(shí)間復(fù)雜度。