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.找出離所有資料平均值最近的 c 個資料點 4.找出距離平方和最小的 c 個資料點上述討論的方法，通常又稱為 batch k-means algorithm，另一個類似的方法稱為 sequential k-means algorithm 或是 on-line k-mean algorithm，則是每當收集到一筆資料時，就可以更新群中心，方法如下： 1.隨機選取c的起始點，將之分別視為c個群聚的群中心 2.對每一個資料點x，尋找與之最接近的群中心，並將x加入該群聚，隨即計算新的群聚中心（該群聚中原有的資料點加上x後的平均向量） 3.檢查每一個資料點目前與之最接近的群聚中心是否和他的群聚分配一致，如果不是，則回到步驟二，反覆疊代，直到收斂。 一般而言， sequential k-mean algorithm的優點如下： 1.適用於資料特性隨時間而變的情況。 2.計算簡單，適用於硬體實現。
除非有特殊情況，否則很少使用 sequential k-mean algorithm。
發現叢集(Discovering Group, Clustering)
群集分析(cluster analysis)又稱為資料切割(data segmentation)、非監督式分分類(unsupervised classification)，他是一種多變量統計分析(multivariate statistical analysis)的技術，主要目的是將資料集合中的資料紀錄，又稱為資料點、觀察值或案例，加以分群成數個群集(cluster)，使的每個群集中的資料點間相似程度高於其他群集中資料點的相似程度。因此群集分析主要的杜地在於分析資料彼此間的相似程度，藉由分析所找到的群集結果，推論出有用、隱含、令人感興趣的特性和現象。相對於分類法中每一筆訓練資料紀錄都給訂一個類別資訊，並企圖從中找出一個判斷模式來預測未知類別資訊得資料紀錄;在群集分析的過程中，並沒有預先指定好的類別資訊，也沒有任何資訊可以表示資料紀錄彼此之間是相關的，所以群集分析被視為一個非監督式學習(unsupervised learning)的過程。
群集在data mining中所扮演的角色:
*資料精簡:透過群集分析將原本大量的資料加以分群成數個群集，並從每一個群集中挑選具有代表性的資料
記錄來進行後續的處理。
*推論假設的產生:利用群集分析推斷出所關注資料中可能存在的某些特性或現象。
*推論假設的驗證:可以對推論假設作有效性的驗證。
*歸屬預測:將群集分析後的分群結果應用於未知分類之資料記錄上，以預測資料所歸屬的群集。
資料分群（data clustering）或是分群演算法（clustering algorithms）是一種將資料分類成群的方法，其主要的目的乃在於找出資料中較相似的幾個群聚（clusters），並找出各個群聚的代表點，稱為中心點（centroids）或是原型（prototypes）。使用這些中心點來代表原先大量的資料點，就可以達到兩個基本目標：
降低計算量
資料壓縮
一般而言，分群法可以大致歸為兩大類：
階層式分群法（hierarchical clustering）：群數（number of clusters）可以由大變小，或是由小變大，來進群聚的合併或分裂，最後再選取最佳的群數。
分割式分群法（partitional clustering）：先指定群數後，再用一套疊代的數學運算法，找出最佳的分群方式以及相關的群中心。
所有的分群法都有相似的流程，大略可歸納為下列三點：
收集資料
使用某種方法進行分群
測試分群結果
檢測分群結果，如果未達預期效果，則回到步驟二，再一次進行分群