聚類算法實踐一層次聚類、K-means聚類

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

在數據分析的術語之中，聚類和分類是兩種技術。分類是指我們已經知道了事物的類別，需要從樣品中學習分類的規則，是一種有指導學習；而聚類則是由我們來給定簡單的規則，從而得到分類，是一種無指導學習。兩者可以說是相反的過程。

網上關于聚類算法的資料很多，但是其實大都是幾種最基本的方法，如K-means、層次聚類、SOM等，以及它們的許許多多的改進變種。這里，我就來討論一下這些聚類算法，對它們的表現做一個簡單的評估。因為內容有點多（其實主要是圖占位置……），所以準備分幾次來完成。

基本測試

0、測試數據集

在介紹這些算法之前，這里先給出兩個簡單的測試樣品組，下面每介紹完一個算法，可以直接看看它對這兩個樣品組的聚類結果，從而得到最直觀的認識。

下圖就是兩個簡單的二維樣品組：

1）第一組樣品屬于最基本的聚類測試，界線還是比較分明的，不過三個cluster的大小有較明顯差異，可以測試一下算法對cluster size的敏感度。樣品總共有2000個數據點

2）第二組是典型的甜甜圈形。使用這樣的測試組主要是為了考察算法對cluster形狀敏感度。共有1500個數據點。

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

1、相似性度量

對于聚類，關鍵的一步是要告訴計算機怎樣計算兩個數據點的“相似性”，不同的算法需要的“相似性”是不一樣的。

比如像以上兩組樣品，給出了每個數據點的空間坐標，我們就可以用數據點之間的歐式距離來判斷，距離越近，數據點可以認為越“相似”。當然，也可以用其它的度量方式，這跟所涉及的具體問題有關。

2、層次聚類

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

所謂從下而上地合并cluster，具體而言，就是每次找到距離最短的兩個cluster，然后進行合并成一個大的cluster，直到全部合并為一個cluster。整個過程就是建立一個樹結構，類似于下圖。

那 么，如何判斷兩個cluster之間的距離呢？一開始每個數據點獨自作為一個類，它們的距離就是這兩個點之間的距離。而對于包含不止一個數據點的 cluster，就可以選擇多種方法了。最常用的，就是average-linkage，即計算兩個cluster各自數據點的兩兩距離的平均值。類似的 還有single-linkage/complete-linkage，選擇兩個cluster中距離最短/最長的一對數據點的距離作為類的距離。個人經 驗complete-linkage基本沒用，single-linkage通過關注局域連接，可以得到一些形狀奇特的cluster，但是因為太過極 端，所以效果也不是太好。

層 次聚類最大的優點，就是它一次性地得到了整個聚類的過程，只要得到了上面那樣的聚類樹，想要分多少個cluster都可以直接根據樹結構來得到結果，改變 cluster數目不需要再次計算數據點的歸屬。層次聚類的缺點是計算量比較大，因為要每次都要計算多個cluster內所有數據點的兩兩距離。另外，由 于層次聚類使用的是貪心算法，得到的顯然只是局域最優，不一定就是全局最優，這可以通過加入隨機效應解決，這就是另外的問題了。

聚類結果

對樣品組1使用average-linkage，選擇聚類數目為4，可以得到下面的結果。右上方的一些異常點被獨立地分為一類，而其余的數據點的分類基本符合我們的預期。

如果選擇聚類數目為5，則是下面的結果。其中一個大的cluster被分割，但沒有出現均勻分割的情況（比如K-means），只有少量的數據點被分離，大體的分類還是比較正確的。因此這個算法可以處理大小差別比較大的聚類問題，對cluster size不太敏感。

如 何確定應該取多少個cluster？這是聚類里面的一個非常重要的問題。對于層次聚類，可以根據聚類過程中，每次合并的兩個cluster的距離來作大概 判斷，如下圖。因為總共有2000個數據點，每次合并兩個cluster，所以總共要做2000次合并。從圖中可以看到在后期合并的兩個cluster的 距離會有一個陡增。假如數據的分類是十分顯然的，就是應該被分為K個大的cluster，K個cluster之間有明顯的間隙。那么如果合并的兩個小 cluster同屬于一個目標cluster，那么它們的距離就不會太大。但當合并出來K個目標cluster后，再進行合并，就是在這K個 cluster間進行合并了，這樣合并的cluster的距離就會有一個非常明顯的突變。當然，這是十分理想的情況，現實情況下突變沒有這么明顯，我們只 能根據下圖做個大致的估計。

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

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

3、K-means算法

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

K-means的目標是要將數據點劃分為k個cluster，找到這每個cluster的中心，并且最小化函數

其中就是第i個cluster的中心。上式就是要求每個數據點要與它們所屬cluster的中心盡量接近。

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

K-means實際上是EM算法的一個特例（關于EM算法，請猛擊這里和這里），根據中心點決定數據點歸屬是expectation，而根據構造出來的cluster更新中心則是maximization。理解了K-means，也就順帶了解了基本的EM算法思路。

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

K- means算法相比起上面提到的層次聚類，還有一個很大的不同，那就是它需要數據點的坐標，因為它必須要求取平均，而層次聚類實際上并不需要坐標數據，只 需要知道數據點之間的距離而已。這也就是說K-means只適用于使用歐氏距離來計算數據點相似性的情況，因為如果采用非歐距離，那么也不能通過簡單的平 均來得到cluster中心。

聚類結果

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

對甜甜圈樣品組，K-means也是完全沒轍。

從 上面的結果可以看出，K-means的聚類效果確實不是很好。用戶如果選擇了不正確的聚類數目，會使得本應同一個cluster的數據被判定為屬于兩個大 的類別，這是我們不想看到的。因為需要數據點的坐標，這個方法的適用性也受到限制。但是效率是它的一個優勢，在數據量大或者對聚類結果要求不是太高的情況 下，可以采用K-means算法來計算，也可以在實驗初期用來做測試看看數據集的大致情況。