3-3 K-means Clustering

[english][all]
(請注意：中文版本並未隨英文版本同步更新！)
Slides
在所有的分割式分群法之中，最基本的方法，就是所謂的 K-means 分群法（k-means clustering），又稱為Forgy's algorithm [6]。其主要目標是要在大量高維的資料點中找出具有代表性的資料點，這些資料點可以稱為是群中心（cluster centers）、代表點（prototypes）、codewords等，然後在根據這些群中心，進行後續的處理，這些處理可以包含：

資料壓縮：以少數的資料點來代表大量的資料，達到資料壓縮的功能。
資料分類：以少數代表點來代表特定類別的資料，可以降低資料量及計算量，並可以避免雜訊的不良影響。

在使用分割式分群法（partitional clustering）時，我們必須先指定群聚的數目，然後藉著反覆疊代運算，逐次降低一個誤差目標函數的值，直到目標函數不再變化，就達到分群的最後結果。
分割式分群法的目的是希望盡量減小每個群聚中，每一點與群中心的距離平方誤差（square error）。假設我們現在有一組包含c個群聚的資料，其中第 p 個群聚可以用集合 G_p 來表示，假設 G_p 包含n_p筆資料 {x₁, x₂, …, x_np），此群聚中心為c_p，則該群聚的平方誤差 e_p可以定義為： $$ e_j=\sum_{x_i \in G_j} \| x_i-c_j\|^2. $$
而這c個群聚的總和平方誤差E便是每個群聚的平方誤差總和，可稱為分群的「誤差函數」（error function）或「失真度」（distortion）：
E = S_p=1^m e_p
我們分群的方法，就變成是一個最佳化的問題，換句話說，我們要如何選取 c 個群聚以及相關的群中心，使得 E 的值為最小。
我們也可以使用另一套數學來描述，給定一組 n 點資料 X = {x₁, ..., x_n}，每一點都有 d 維，k-means 分群法的任務是找到一組 m 個代表點 C = {c₁, ..., c_m}，每一點也是d維，以使下列的目標函數越小越好：
J(X; C, A) = S_{x_i in G_p}|x_i-c_p|²,
其中 x_i屬於 G_p 而且 c_p 是 G_p 的代表點。同時在上述目標函數中，A 是一個 mxn 的分組矩陣，每一個元素值都是 0 或 1，而且每一直行的總和等於 1，如果 A(i, j) = 1，代表第j個資料點是屬於第i組。（請注意： A 是以隱含的方式出現在上述方程式的等號右方。）
若要直接對上述目標函數進行最小化，是一件蠻困難的事，因為這個目標函數有 m*n+m*d個可變參數，同時又有n個限制條件，很難直接採用傳統的方式來進行最佳化，但我們可以觀察到兩個現象：

當C（群中心）固定時，我們可以很容易地找到對應的A（資料分群方式），使J(X; C, A)的值為最小。此最佳的A值，即代表最佳的分群方式，因此若將每個資料點歸類到距離最近的代表點，即可完成此目標。
當A（資料分群方式）固定實，我們也可以很快地找到對應的C（群中心），使J(X; C, A)的值為最小。此最佳的C集合，代表每個代表點至其組員的距離平方和為最小，因此此最佳的C集合即是每一群的平均點。
在演算法開始進行前，我們必須事先決定好預期分群的群聚數目。假設預期的分群群聚數目為c，則根據上述觀察，我們可以經由下列步驟來進行 k-means 分群法：

隨機選取 m 個資料點，將之分別視為 m 個群聚的群中心，這就是C。
由固定的C，產生最佳的A。換句話說，對每一個資料點x，尋找與之最接近的群中心，並將x加入該群聚。
計算目標函數 J(X; C, A)，如果保持不變，代表分群結果已經穩定不變，所以可以結束此疊代方法。
再由固定的U，產生最佳的C。跳回第2個步驟。

在上述方法中，我們是先找群中心，再開始反覆疊代的過程。事實上，我們也可以先進行任意分群，然後再進行反覆疊代的過程，得到的結果應該很類似。
這是一個反覆的過程，但在整個迴圈的過程中，我們可以保證J(X; C, A)絕對不會遞增（可用數學證明，請見上述前述兩點觀察），只會遞減或維持不變，一旦維持不變，我們就可以跳出迴圈、結束演算法。下面這個範例，顯示k-means分群法對於一組二維資料的分群效果：
Example 1: kMeans01.m

在上圖中，左圖是在迭代過程中，目標函數遞減的圖形，右圖則是最後的分群結果。在上述範例中，由於啟始中心點是由亂數產生，所以每次執行程式碼，所得到的圖形都會不太一樣。
下面這個範例，我們使用同一組二維資料來進行 k-means，並顯示在迭代過程中，中心點的移動過程：
Example 2: kMeans02.m

在上圖中：

左上圖是啟始的群中心和分群的結果。
右上圖是最後的群中心和分群的結果。
左下圖是目標函數J(X; C, A)隨著疊代次數而遞減的情況。
右下圖是群中心雖著疊代次數而移動的路徑。

在上述資料中，我們可以很明顯地看出，資料原先就可以概分為四群，如果我們也設定群數等於4，然後開始跑k-means，所得到的結果通常是正確的，但是如何決定適當的群數，這是尚待解決的另一個問題，此問題通稱為cluster validation，請見後續章節的說明。
下面這個範例，顯示k-means分群法對於另一組二維資料（甜甜圈）的分群效果：
Example 3: kMeans03.m

有關於k-means的方法，還需要注意幾點：

這個方法只能保證J(X; C, A)越來越小，但無法保證能夠找到J(X; C, A)的絕對最小值，因此若時間許可，應該由不同的啟始群中心，多跑幾次，然後再選取最好的結果。
啟始群中心對於最後的分群結果有很大的影響，因此如何以很快的方法找到比較好的群中心，就變成重要的研究課題。以上述方法來說，若要選取 c 個起始中心典，常用的選取方法有下列幾種：

從資料裡面隨意選出 m 點資料
找出離所有資料平均值最遠的 m 個資料點
找出離所有資料平均值最近的 m 個資料點
找出距離平方和最小的 m 個資料點
但是這些找出起始群中心點的方法也都無法保證達到更好的目標函數值。如果計算時間不是太久，建議在選取啟始群中心時，多試用不同的方法，找出多組啟始群中心，同時進行 k-means，最後再以目標函數最小的結果來作為最後分群的結果。
另一個可能發生的問題，就是在進行 k-means 的過程中，有可能出現一個空的群聚，此群聚是空集合，沒有資料點。碰到這種情況，一個簡單的解決方式，就是直接將另一個群聚拆解為兩個，這樣才能保持群聚數目的不變。至於要找那一個群聚來切成兩個，可已有下列標準：

找資料點最多的群聚
找貢獻於目標函數最大的群聚

我們前述的方法是先找群中心，然後進行反覆疊代。我們也可以先分群，然後再反覆疊代，也可以得到類似的效果。
雖然我們可以證明此方法一定收斂，但是此方法只能找到目標函數的局部最小值（local minimum），我們並無法證明此方法所找到的群聚及群中心會使目標函數到達全域最小值（global minimum）。而事實上到目前為止，也沒有出現任何一種方法，能保證所找到的分群結果可使目標函數達到全域最小值。
上述討論的方法，通常又稱為 batch k-means algorithm，另一個類似的方法稱為 sequential k-means algorithm 或是 on-line k-mean algorithm，則是每當收集到一筆資料時，就可以更新群中心，方法如下：

隨機選取c的起始點，將之分別視為c個群聚的群中心
對每一個資料點x，尋找與之最接近的群中心，並將x加入該群聚，隨即計算新的群聚中心（該群聚中原有的資料點加上x後的平均向量）
檢查每一個資料點目前與之最接近的群聚中心是否和他的群聚分配一致，如果不是，則回到步驟二，反覆疊代，直到收斂。

一般而言， sequential k-mean algorithm的優點如下：

適用於資料特性隨時間而變的情況。
計算簡單，適用於硬體實現。
除非有特殊情況，否則我們很少使用 sequential k-mean algorithm。
Data Clustering and Pattern Recognition (資料分群與樣式辨認)