機(jī)器學(xué)習(xí)中五種常用的聚類算法

聚類是機(jī)器學(xué)習(xí)中一種重要的無(wú)監(jiān)督算法，它可以將數(shù)據(jù)點(diǎn)歸結(jié)為一系列特定的組合。理論上歸為一類的數(shù)據(jù)點(diǎn)具有相同的特性，而不同類別的數(shù)據(jù)點(diǎn)則具有各不相同的屬性。在數(shù)據(jù)科學(xué)中聚類會(huì)從數(shù)據(jù)中發(fā)掘出很多分析和理解的視角，讓我們更深入的把握數(shù)據(jù)資源的價(jià)值、并據(jù)此指導(dǎo)生產(chǎn)生活。以下是五種常用的聚類算法。

K均值聚類

這一最著名的聚類算法主要基于數(shù)據(jù)點(diǎn)之間的均值和與聚類中心的聚類迭代而成。它主要的優(yōu)點(diǎn)是十分的高效，由于只需要計(jì)算數(shù)據(jù)點(diǎn)與劇類中心的距離，其計(jì)算復(fù)雜度只有O(n)。其工作原理主要分為以下四步：

1.首先我們需要預(yù)先給定聚類的數(shù)目同時(shí)隨機(jī)初始化聚類中心。我們可以初略的觀察數(shù)據(jù)并給出較為準(zhǔn)確的聚類數(shù)目；

2.每一個(gè)數(shù)據(jù)點(diǎn)通過(guò)計(jì)算與聚類中心的距離了來(lái)分類到最鄰近的一類中；

3.根據(jù)分類結(jié)果，利用分類后的數(shù)據(jù)點(diǎn)重新計(jì)算聚類中心；

4.重復(fù)步驟二三直到聚類中心不再變化。（可以隨機(jī)初始化不同的聚類中心以選取最好的結(jié)果）

這種方法在理解和實(shí)現(xiàn)上都十分簡(jiǎn)單，但缺點(diǎn)卻也十分明顯，十分依賴于初始給定的聚類數(shù)目；同時(shí)隨機(jī)初始化可能會(huì)生成不同的聚類效果，所以它缺乏重復(fù)性和連續(xù)性。

和K均值類似的K中值算法，在計(jì)算過(guò)程中利用中值來(lái)計(jì)算聚類中心，使得局外點(diǎn)對(duì)它的影響大大減弱；但每一次循環(huán)計(jì)算中值矢量帶來(lái)了計(jì)算速度的大大下降。

均值漂移算法

這是一種基于滑動(dòng)窗口的均值算法，用于尋找數(shù)據(jù)點(diǎn)中密度最大的區(qū)域。其目標(biāo)是找出每一個(gè)類的中心點(diǎn)，并通過(guò)計(jì)算滑窗內(nèi)點(diǎn)的均值更新滑窗的中心點(diǎn)。最終消除臨近重復(fù)值的影響并形成中心點(diǎn)，找到其對(duì)應(yīng)的類別。

1.首先以隨機(jī)選取的點(diǎn)為圓心r為半徑做一個(gè)圓形的滑窗。其目標(biāo)是找出數(shù)據(jù)點(diǎn)中密度最高點(diǎn)并作為中心；

2.在每個(gè)迭代后滑動(dòng)窗口的中心將為想著較高密度的方向移動(dòng)；

3.連續(xù)移動(dòng)，直到任何方向的移動(dòng)都不能增加滑窗中點(diǎn)的數(shù)量，此時(shí)滑窗收斂；

4.將上述步驟在多個(gè)滑窗上進(jìn)行以覆蓋所有的點(diǎn)。當(dāng)過(guò)個(gè)滑窗收斂重疊時(shí)，其經(jīng)過(guò)的點(diǎn)將會(huì)通過(guò)其滑窗聚類為一個(gè)類；

下圖中每一個(gè)黑點(diǎn)都代表一個(gè)滑窗的中心，他們最終重疊在每一類的中心；

與K均值相比最大的優(yōu)點(diǎn)是我們無(wú)需指定指定聚類數(shù)目，聚類中心處于最高密度處也是符合直覺(jué)認(rèn)知的結(jié)果。但其最大的缺點(diǎn)在于滑窗大小r的選取，對(duì)于結(jié)果有著很大的影響。

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

DBSCAN同樣是基于密度的聚類算法，但其原理卻與均值漂移大不相同：

1.首先從沒(méi)有被遍歷的任一點(diǎn)開(kāi)始，利用鄰域距離epsilon來(lái)獲取周圍點(diǎn)；

2.如果鄰域內(nèi)點(diǎn)的數(shù)量滿足閾值則此點(diǎn)成為核心點(diǎn)并以此開(kāi)始新一類的聚類。（如果不是則標(biāo)記為噪聲）；

3.其鄰域內(nèi)的所有點(diǎn)也屬于同一類，將所有的鄰域內(nèi)點(diǎn)以epsilon為半徑進(jìn)行步驟二的計(jì)算；

4.重復(fù)步驟二、三直到變量完所有核心點(diǎn)的鄰域點(diǎn)；

5.此類聚類完成，同時(shí)又以任意未遍歷點(diǎn)開(kāi)始步驟一到四直到所有數(shù)據(jù)點(diǎn)都被處理；最終每個(gè)數(shù)據(jù)點(diǎn)都有自己的歸屬類別或者屬于噪聲。

這種方法最大的優(yōu)點(diǎn)在于無(wú)需定義類的數(shù)量，其次可以識(shí)別出局外點(diǎn)和噪聲點(diǎn)、并且可以對(duì)任意形狀的數(shù)據(jù)進(jìn)行聚類。

但也存在不可回避的缺點(diǎn)，當(dāng)數(shù)據(jù)密度變化劇烈時(shí)，不同類別的密度閾值點(diǎn)和領(lǐng)域半徑會(huì)產(chǎn)生很大的變化。同時(shí)在高維空間中準(zhǔn)確估計(jì)領(lǐng)域半徑也是不小的挑戰(zhàn)。

利用高斯混合模型進(jìn)行最大期望估計(jì)

對(duì)于較為復(fù)雜的分布K均值將會(huì)產(chǎn)生如下圖般較為離譜的聚類結(jié)果。

而高斯混合模型卻具有更高的靈活性。通過(guò)假設(shè)數(shù)據(jù)點(diǎn)符合均值和標(biāo)準(zhǔn)差描述的高斯混合模型來(lái)實(shí)現(xiàn)的。下圖以二維情況下為例描述了如何利用最大期望優(yōu)化算法來(lái)獲取分布參數(shù)的過(guò)程：

1.首先確定聚類的數(shù)量，并隨機(jī)初始化每一個(gè)聚類的高斯分布參數(shù)；

2.通過(guò)計(jì)算每一個(gè)點(diǎn)屬于高斯分布的概率來(lái)進(jìn)行聚類。與高斯中心越近的點(diǎn)越有可能屬于這個(gè)類；

3.基于上一步數(shù)據(jù)點(diǎn)的概率權(quán)重，通過(guò)最大似然估計(jì)的方法計(jì)算出每一類數(shù)據(jù)點(diǎn)最有可能屬于這一聚類的高斯參數(shù)；

4.基于新的高斯參數(shù)，重新估計(jì)每一點(diǎn)歸屬各類的概率，重復(fù)并充分2,3步驟直到參數(shù)不再變化收斂為止。

在使用高斯混合模型時(shí)有兩個(gè)關(guān)鍵的地方，首先高斯混合模型十分靈活，可以擬合任意形狀的橢圓；其次這是一種基于概率的算法，每個(gè)點(diǎn)可以擁有屬于多類的概率，支持混合屬性。

凝聚層次聚類

層次聚類法主要有自頂向下和自底向上兩種方式。其中自底向上的方式，最初將每個(gè)點(diǎn)看做是獨(dú)立的類別，隨后通過(guò)一步步的凝聚最后形成獨(dú)立的一大類，并包含所有的數(shù)據(jù)點(diǎn)。這會(huì)形成一個(gè)樹(shù)形結(jié)構(gòu)，并在這一過(guò)程中形成聚類。

1.首先將每一個(gè)數(shù)據(jù)點(diǎn)看成一個(gè)類別，通過(guò)計(jì)算點(diǎn)與點(diǎn)之間的距離將距離近的點(diǎn)歸為一個(gè)子類，作為下一次聚類的基礎(chǔ)；

2.每一次迭代將兩個(gè)元素聚類成一個(gè)，上述的子類中距離最近的兩兩又合并為新的子類。最相近的都被合并在一起；

3.重復(fù)步驟二直到所有的類別都合并為一個(gè)根節(jié)點(diǎn)?；诖宋覀兛梢赃x擇我們需要聚類的數(shù)目，并根據(jù)樹(shù)來(lái)進(jìn)行選擇。

層次聚類無(wú)需事先指定類的數(shù)目，并且對(duì)于距離的度量不敏感。這種方法最好的應(yīng)用在于恢復(fù)出數(shù)據(jù)的層次化結(jié)構(gòu)。但其計(jì)算復(fù)雜度較高達(dá)到了O（n^3）.

每個(gè)聚類算法都有各自的優(yōu)缺點(diǎn)，我們需要根據(jù)計(jì)算需求和應(yīng)用需求選擇合適的算法來(lái)進(jìn)行處理。隨著深度學(xué)習(xí)的出現(xiàn)，更多的神經(jīng)網(wǎng)絡(luò)、自編碼器被用來(lái)提取數(shù)據(jù)中的高維特征用于分類，是值得注意的研究熱點(diǎn)。

最后如果想練練手的話，scikit Learn上有很多例子可以操練，實(shí)踐才是最好的老師~~http://scikit-learn.org/stable/modules/clustering.html#clustering