聚類算法實(shí)踐一層次聚類、K-means聚類

所謂聚類，就是將相似的事物聚集在一 起，而將不相似的事物劃分到不同的類別的過(guò)程，是數(shù)據(jù)分析之中十分重要的一種手段。比如古典生物學(xué)之中，人們通過(guò)物種的形貌特征將其分門(mén)別類，可以說(shuō)就是 一種樸素的人工聚類。如此，我們就可以將世界上紛繁復(fù)雜的信息，簡(jiǎn)化為少數(shù)方便人們理解的類別，可以說(shuō)是人類認(rèn)知這個(gè)世界的最基本方式之一。

在數(shù)據(jù)分析的術(shù)語(yǔ)之中，聚類和分類是兩種技術(shù)。分類是指我們已經(jīng)知道了事物的類別，需要從樣品中學(xué)習(xí)分類的規(guī)則，是一種有指導(dǎo)學(xué)習(xí)；而聚類則是由我們來(lái)給定簡(jiǎn)單的規(guī)則，從而得到分類，是一種無(wú)指導(dǎo)學(xué)習(xí)。兩者可以說(shuō)是相反的過(guò)程。

網(wǎng)上關(guān)于聚類算法的資料很多，但是其實(shí)大都是幾種最基本的方法，如K-means、層次聚類、SOM等，以及它們的許許多多的改進(jìn)變種。這里，我就來(lái)討論一下這些聚類算法，對(duì)它們的表現(xiàn)做一個(gè)簡(jiǎn)單的評(píng)估。因?yàn)閮?nèi)容有點(diǎn)多（其實(shí)主要是圖占位置……），所以準(zhǔn)備分幾次來(lái)完成。

基本測(cè)試

0、測(cè)試數(shù)據(jù)集

在介紹這些算法之前，這里先給出兩個(gè)簡(jiǎn)單的測(cè)試樣品組，下面每介紹完一個(gè)算法，可以直接看看它對(duì)這兩個(gè)樣品組的聚類結(jié)果，從而得到最直觀的認(rèn)識(shí)。

下圖就是兩個(gè)簡(jiǎn)單的二維樣品組：

1）第一組樣品屬于最基本的聚類測(cè)試，界線還是比較分明的，不過(guò)三個(gè)cluster的大小有較明顯差異，可以測(cè)試一下算法對(duì)cluster size的敏感度。樣品總共有2000個(gè)數(shù)據(jù)點(diǎn)

2）第二組是典型的甜甜圈形。使用這樣的測(cè)試組主要是為了考察算法對(duì)cluster形狀敏感度。共有1500個(gè)數(shù)據(jù)點(diǎn)。

對(duì)于這樣的兩個(gè)樣品組，人類憑肉眼可以很容易地判斷它們應(yīng)該分為三個(gè)cluster（特別是我還用顏色做了區(qū)分……），但對(duì)于計(jì)算機(jī)就不一定了，所以就需要有足夠優(yōu)秀的聚類算法。

1、相似性度量

對(duì)于聚類，關(guān)鍵的一步是要告訴計(jì)算機(jī)怎樣計(jì)算兩個(gè)數(shù)據(jù)點(diǎn)的“相似性”，不同的算法需要的“相似性”是不一樣的。

比如像以上兩組樣品，給出了每個(gè)數(shù)據(jù)點(diǎn)的空間坐標(biāo)，我們就可以用數(shù)據(jù)點(diǎn)之間的歐式距離來(lái)判斷，距離越近，數(shù)據(jù)點(diǎn)可以認(rèn)為越“相似”。當(dāng)然，也可以用其它的度量方式，這跟所涉及的具體問(wèn)題有關(guān)。

2、層次聚類

層次聚類，是一種很直觀的算法。顧名思義就是要一層一層地進(jìn)行聚類，可以從下而上地把小的cluster合并聚集，也可以從上而下地將大的cluster進(jìn)行分割。似乎一般用得比較多的是從下而上地聚集，因此這里我就只介紹這一種。

所謂從下而上地合并cluster，具體而言，就是每次找到距離最短的兩個(gè)cluster，然后進(jìn)行合并成一個(gè)大的cluster，直到全部合并為一個(gè)cluster。整個(gè)過(guò)程就是建立一個(gè)樹(shù)結(jié)構(gòu)，類似于下圖。

那 么，如何判斷兩個(gè)cluster之間的距離呢？一開(kāi)始每個(gè)數(shù)據(jù)點(diǎn)獨(dú)自作為一個(gè)類，它們的距離就是這兩個(gè)點(diǎn)之間的距離。而對(duì)于包含不止一個(gè)數(shù)據(jù)點(diǎn)的 cluster，就可以選擇多種方法了。最常用的，就是average-linkage，即計(jì)算兩個(gè)cluster各自數(shù)據(jù)點(diǎn)的兩兩距離的平均值。類似的 還有single-linkage/complete-linkage，選擇兩個(gè)cluster中距離最短/最長(zhǎng)的一對(duì)數(shù)據(jù)點(diǎn)的距離作為類的距離。個(gè)人經(jīng) 驗(yàn)complete-linkage基本沒(méi)用，single-linkage通過(guò)關(guān)注局域連接，可以得到一些形狀奇特的cluster，但是因?yàn)樘^(guò)極 端，所以效果也不是太好。

層 次聚類最大的優(yōu)點(diǎn)，就是它一次性地得到了整個(gè)聚類的過(guò)程，只要得到了上面那樣的聚類樹(shù)，想要分多少個(gè)cluster都可以直接根據(jù)樹(shù)結(jié)構(gòu)來(lái)得到結(jié)果，改變 cluster數(shù)目不需要再次計(jì)算數(shù)據(jù)點(diǎn)的歸屬。層次聚類的缺點(diǎn)是計(jì)算量比較大，因?yàn)橐看味家?jì)算多個(gè)cluster內(nèi)所有數(shù)據(jù)點(diǎn)的兩兩距離。另外，由 于層次聚類使用的是貪心算法，得到的顯然只是局域最優(yōu)，不一定就是全局最優(yōu)，這可以通過(guò)加入隨機(jī)效應(yīng)解決，這就是另外的問(wèn)題了。

聚類結(jié)果

對(duì)樣品組1使用average-linkage，選擇聚類數(shù)目為4，可以得到下面的結(jié)果。右上方的一些異常點(diǎn)被獨(dú)立地分為一類，而其余的數(shù)據(jù)點(diǎn)的分類基本符合我們的預(yù)期。

如果選擇聚類數(shù)目為5，則是下面的結(jié)果。其中一個(gè)大的cluster被分割，但沒(méi)有出現(xiàn)均勻分割的情況（比如K-means），只有少量的數(shù)據(jù)點(diǎn)被分離，大體的分類還是比較正確的。因此這個(gè)算法可以處理大小差別比較大的聚類問(wèn)題，對(duì)cluster size不太敏感。

如 何確定應(yīng)該取多少個(gè)cluster？這是聚類里面的一個(gè)非常重要的問(wèn)題。對(duì)于層次聚類，可以根據(jù)聚類過(guò)程中，每次合并的兩個(gè)cluster的距離來(lái)作大概 判斷，如下圖。因?yàn)榭偣灿?000個(gè)數(shù)據(jù)點(diǎn)，每次合并兩個(gè)cluster，所以總共要做2000次合并。從圖中可以看到在后期合并的兩個(gè)cluster的 距離會(huì)有一個(gè)陡增。假如數(shù)據(jù)的分類是十分顯然的，就是應(yīng)該被分為K個(gè)大的cluster，K個(gè)cluster之間有明顯的間隙。那么如果合并的兩個(gè)小 cluster同屬于一個(gè)目標(biāo)cluster，那么它們的距離就不會(huì)太大。但當(dāng)合并出來(lái)K個(gè)目標(biāo)cluster后，再進(jìn)行合并，就是在這K個(gè) cluster間進(jìn)行合并了，這樣合并的cluster的距離就會(huì)有一個(gè)非常明顯的突變。當(dāng)然，這是十分理想的情況，現(xiàn)實(shí)情況下突變沒(méi)有這么明顯，我們只 能根據(jù)下圖做個(gè)大致的估計(jì)。

對(duì)于測(cè)試樣品2，average-linkage可謂完全失效，這是由于它對(duì)“相似性”的理解造成的，所以只能得到凸型的cluster。

總體而言，像average-linkage這樣的算法還是比較穩(wěn)定的，可以大致地判斷聚類數(shù)目，聚類效果也不錯(cuò)，在數(shù)據(jù)量比較小的時(shí)候可以使用。

3、K-means算法

K-means是最為常用的聚類方法之一，盡管它有著很多不足，但是它有著一個(gè)很關(guān)鍵的優(yōu)點(diǎn)：快！K-means的計(jì)算復(fù)雜度只有O(tkn)，t是迭代次數(shù)，k是設(shè)定的聚類數(shù)目，而n是數(shù)據(jù)量，相比起很多其它算法，K-means算是比較高效的。

K-means的目標(biāo)是要將數(shù)據(jù)點(diǎn)劃分為k個(gè)cluster，找到這每個(gè)cluster的中心，并且最小化函數(shù)

其中就是第i個(gè)cluster的中心。上式就是要求每個(gè)數(shù)據(jù)點(diǎn)要與它們所屬cluster的中心盡量接近。

為了得到每個(gè)cluster的中心，K-means迭代地進(jìn)行兩步操作。首先隨機(jī)地給出k個(gè)中心的位置，然后把每個(gè)數(shù)據(jù)點(diǎn)歸類到離它最近的中心，這樣我們就構(gòu)造了k個(gè)cluster。但是，這k個(gè)中心的位置顯然是不正確的，所以要把中心轉(zhuǎn)移到得到的cluster內(nèi)部的數(shù)據(jù)點(diǎn)的平均位置。實(shí)際上也就是計(jì)算，在每個(gè)數(shù)據(jù)點(diǎn)的歸類確定的情況下，上面函數(shù)取極值的位置，然后再次構(gòu)造新的k個(gè)cluster。這個(gè)過(guò)程中，中心點(diǎn)的位置不斷地改變，構(gòu)造出來(lái)的cluster的也在變化（動(dòng)畫(huà)請(qǐng)看這里）。通過(guò)多次的迭代，這k個(gè)中心最終會(huì)收斂并不再移動(dòng)。

K-means實(shí)際上是EM算法的一個(gè)特例（關(guān)于EM算法，請(qǐng)猛擊這里和這里），根據(jù)中心點(diǎn)決定數(shù)據(jù)點(diǎn)歸屬是expectation，而根據(jù)構(gòu)造出來(lái)的cluster更新中心則是maximization。理解了K-means，也就順帶了解了基本的EM算法思路。

實(shí)際應(yīng)用里，人們指出了很多K-means的不足。比如需要用戶事先給出聚類數(shù)目k，而這個(gè)往往是很難判斷的；又如K-means得到的是局域最優(yōu)，跟初始給定的中心值有關(guān)，所以往往要嘗試多個(gè)初始值；總是傾向于得到大小接近的凸型cluster等等。

K- means算法相比起上面提到的層次聚類，還有一個(gè)很大的不同，那就是它需要數(shù)據(jù)點(diǎn)的坐標(biāo)，因?yàn)樗仨氁笕∑骄?，而層?a href='/map/julei/' style='color:#000;font-size:inherit;'>聚類實(shí)際上并不需要坐標(biāo)數(shù)據(jù)，只 需要知道數(shù)據(jù)點(diǎn)之間的距離而已。這也就是說(shuō)K-means只適用于使用歐氏距離來(lái)計(jì)算數(shù)據(jù)點(diǎn)相似性的情況，因?yàn)槿绻捎梅菤W距離，那么也不能通過(guò)簡(jiǎn)單的平 均來(lái)得到cluster中心。

聚類結(jié)果

取 k=3，K-means對(duì)樣品組1聚類得到下面兩張圖。為什么是兩張圖呢？正如前面所說(shuō)，K-means的聚類結(jié)果跟初始中心選擇有關(guān)，而不是所以的初始 值都能保證聚類成功的，下面第二張就是失敗的例子。另外由于K-means總傾向于得到接近大小的cluster，所以可以看到兩個(gè)小的cluster對(duì) 大cluster的“入侵”。

對(duì)甜甜圈樣品組，K-means也是完全沒(méi)轍。

從 上面的結(jié)果可以看出，K-means的聚類效果確實(shí)不是很好。用戶如果選擇了不正確的聚類數(shù)目，會(huì)使得本應(yīng)同一個(gè)cluster的數(shù)據(jù)被判定為屬于兩個(gè)大 的類別，這是我們不想看到的。因?yàn)樾枰獢?shù)據(jù)點(diǎn)的坐標(biāo)，這個(gè)方法的適用性也受到限制。但是效率是它的一個(gè)優(yōu)勢(shì)，在數(shù)據(jù)量大或者對(duì)聚類結(jié)果要求不是太高的情況 下，可以采用K-means算法來(lái)計(jì)算，也可以在實(shí)驗(yàn)初期用來(lái)做測(cè)試看看數(shù)據(jù)集的大致情況。