6. 發現叢集(Discovering Group, Clustering)

發現叢集(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):先指定群數後,再用一套疊代的數學運算法,找出最佳的分群方式以及相關的群中心。

所有的分群法都有相似的流程,大略可歸納為下列三點:

收集資料

  1. 使用某種方法進行分群
  2. 測試分群結果
  3. 檢測分群結果,如果未達預期效果,則回到步驟二,再一次進行分群

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 個群聚以及相關的群中心,使得的值為最小。 也可以用另一方式來描述,給定一組 n 點資料 X = {x1, ..., xn},每一點都有 d 維,k-means 分群法的任務是找到一組 m 個代表點 Y = {y1, ..., ym},每一點也是d維,以使下列的目標函數越小越好: J(X; Y, U) = Si=1n|xi-yk|2在演算法開始進行前,必須事先決定好預期分群的群聚數目。假設預期的分群群聚數目為c,則根據上述觀察,可經由下列步驟來進行 k-means 分群法: 1.隨機選取 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  


組間變異(between)、組內變異(within)、距離與亂度(entropy)

        上圖是一般資料分成三群後分別用不同的顏色表示,將它再進一步的簡化之後可以得到右圖那樣的圖形,而圖中的白點是每一群的中心稱為群中心點。而組內變異(within)和組間變異(between)是兩個統計上的名詞正好可以用在分群當中來判斷分群的效果好壞;組內變異(within),指的是在同一群中,每個點與群中心點距離的平方總合;而假設圖中的黑點是所有點的中心點,則每個群中心點與黑點距離的平方總合就是組間變異(between)

          一般來說,判斷分群的結果好壞,組內變異(within)的值要小,表示同一群裡面的點離散程度小、較密集;組間變異(between)的值要大,表示每一群之間的距離都夠遠。 

         但是我們判斷分群的好壞,除了用距離之外,還可以用亂度或是密度來測量。

        亂度()的概念是由德國物理學克勞修斯1865所提出,原本適用於熱力學中。但是在哲學中最小亂度在模式識別領域可應用於分類,數據分析和數據挖掘。在規律的數據結構下,亂度值是低的,而隨機性的數據結構的亂度值則是高的。亂度可以被理解為混亂程度的系統,也就是衡量一個分區的不確定性。 

 

這個證明表示說分的群數不同,但是在其他條件都相同的情況之下,分的群數少會比較好。  

 

這個證明表示分的群數都相同,但是較集中於某一群的亂度會較低。

 

舉例說明

   

另一個亂度的性質是它可以處理聚集和非聚集的情況。 

假設現在有

 

推導過程: 

 

PS.