My Note - K-means Cluster
K-means 分群法 使用分割式分群法(partitional clustering)時,必須先指定群聚的數目,然後藉著反覆疊代運算,逐次降低一個誤差目標函數的值,直到目標函數不再變化,就達到分群的最後結果。 在所有的分割式分群法之中,最基本的方法,就是所謂的 K-means 分群法(k-means clustering),又稱為Forgy's algorithm。主要目標是在大量高維的資料點中找出具有代表性的資料點,這些資料點可以稱為是群中心(cluster centers)、代表點(prototypes)、codewords等,然後在根據這些群中心,進行後續的處理,這些處理可以包含: 1.資料壓縮:以少數的資料點來代表大量的資料,達到資料壓縮的功能。2.資料分類:以少數代表點來代表特定類別的資料,可以降低資料量及計算量,並可以避免雜訊的不良影響。分割式分群法的目的是希望盡量減小每個群聚中,每一點與群中心的距離平方誤差(square error)。E = Sk=1~c ek分群的方法,就變成是一個最佳化的問題,換句話說,要如何選取 c 個群聚以及相關的群中心,使得 E 的值為最小。 也可以用另一方式來描述,給定一組 n 點資料 X = {x1, ..., xn},每一點都有 d 維,k-means 分群法的任務是找到一組 m 個代表點 Y = {y1, ..., ym},每一點也是d維,以使下列的目標函數越小越好: J(X; Y, U) = Si=1nxi-yk2在演算法開始進行前,必須事先決定好預期分群的群聚數目。假設預期的分群群聚數目為c,則根據上述觀察,可經由下列步驟來進行 k-means 分群法: 1.隨機選取 c 個資料點,將之分別視為c 個群聚的群中心,這就是Y。 2.由固定的Y,產生最佳的U。換句話說,對每一個資料點x,尋找與之最接近的群中心,並將x加入該群聚。 3.計算目標函數 J(X; Y, U),如果保持不變,代表分群結果已經穩定不變,所以可以結束此疊代方法。 4.再由固定的U,產生最佳的Y。跳回第2個步驟。由於只能找到局部最小值,所以如何選一組好的起始點,就變得很重要。以上述方法來說,若要選取 c 個起始中心典,常用的選取方法有下列幾種: 1.從資料裡面隨意選出 c 點資料2.找出離所有資料平均值最遠的 c 個資料點3.找出離所有資...