群集分析 (Cluster Analysis).ppt

1、1,群集分析 (Cluster Analysis),2,內容概要,簡介 資料的表示 相似度的計算與測量 分群法的採用 分割式分群法 非分割式分群法 分群法在大型資料集合之設計 評估分群的結果,3,簡介(1),群集分析的概念與目的 將資料集合中的資料記錄，又稱為資料點，加以分群成數個群集(cluster)，使得每個群集中的資料點間相似程度高於與其它群集中資料點的相似程度 主要的目地是分析資料彼此間的相似程度，藉由分析所找到的群集結果，推論出有用、隱含、令人感興趣的特性和現象 在群集分析的過程中，並沒有預先指定好的類別資訊，也沒有任何資訊可以表示資料記錄彼此之間是相關的，所以群集分析被視為一個非監

2、督式學習的過程,4,簡介(2),群集分析在資料探勘過程中所扮演的角色 資料精簡 將原本大量的資料加以分群成數個群集，並從每一個群集中挑選具有代表性的資料記錄來進行後續的處理 推斷假設的產生 推斷出所關注資料中可能存在的某些特性或現象 “年輕人通常年收入較低”、“中年人通常年收入較高” 推斷假設的驗證 對推斷假設作有效性的驗證 試圖驗證 “年輕人通常年收入較低，是否也代表其消費能力較低？”此假設性推斷時，可以對於 “年齡”、“年收入” 和 “消費金額” 所描述的資料記錄進行群集分析 歸屬預測 分群結果應用於未知分類之資料記錄，預測資料所歸屬的群集,5,簡介(3),線上購物網站的使用者族群與消費能

3、力,6,簡介(4),群集分析應用領域 交易行為分析 解各類型使用者的行為模式 空間資料分析 幫助使用者自動化分析圖像資料庫所產生的影像資料 ，了解感興趣的特性和現象 文件管理 將文件加以分門別類，幫助文件資料的管理和使用,7,簡介(5),群集分析五個主要的循序工作項目 資料的表示：找出代表性資料維度來表示資料點 相似度的計算與測量：計算資料點間相似的程度 分群法的採用：挑選適當的分群演算法 評估分群的結果：對群集分析的結果進行評估 群集的解釋：領域專家對分群結果做進一步解釋,8,資料的表示,將每一資料點利用有限、一致的資料維度表示 濾掉與所分析問題無關、偏差、重複的資料維度 不適切的資料維度將

4、造成分群結果凌亂、難以從中獲取各群聚的關係與差異 相對於 “性別” 和 “地址” 這兩個資料維度，“平均月收入” 與 “年齡” 這兩個資料維度將更能幫助了解各類型之會員族群 會員2將可以表示為 ，其中21為會員2在 “年齡” 此資料維度的資料數值，而26為會員2在 “平均月收入” 此資料維度的資料數值,9,相似度的計算與測量,衡量資料點間的相似度將決定資料記錄所歸屬的群聚，並影響整個分群的結果 相似度測量法是群集分析中最根本的課題 相似度的計算與測量的考量 資料型態的考量 應用範圍的考量 資料離散程度與複雜性的考量,10,資料型態的考量(1),連續性資料維度 通常利用簡單的空間距離計算公式，透

5、過衡量資料點間距離的遠近來判斷彼此間的相似程度 尤拉距離 (Euclidean distance) 資料點 xi = 和資料點 xj = 之間的尤拉距離： d2 (xi, xj) = = ( ) 曼哈頓距離 (Manhattan distance) dM (xi, xj) = =,11,資料型態的考量(2),尤拉距離與曼哈頓距離在二維空間上的物理意義 會員1= 與會員2= 之間的尤拉距離與曼哈頓距離分別如下所示 d2 (x1, x2) = 6 dM (x1, x2) = = 7,12,資料型態的考量(3),類別型態資料維度 利用字串比對的方式，對於資料數值完全相同時則相似度以1表示，否則以0表

6、示 透過專家事先訂定資料數值間的相似度與輔助之計算公式 先轉換或對應成連續性的資料數值，再套用距離計算公式來計算其相似度,13,應用範圍的考量(1),資料點之間的相似程度 群集間的相似程度,14,應用範圍的考量(2),15,資料離散程度與複雜性的考量,一般相似度計算公式通常對資料點中各資料維度給予相同的重要性，然而這將造成值域 (domain) 較大的資料維度將左右分群的結果 會員A = 、會員B = 與會員C = 透過尤拉距離的相似度公式計算後，將會認定會員A與會員C相似度較高；用人來判斷，會員A與會員B應該較可能屬於同一個族群,16,分群法的採用,分群法的種類 應用領域：應用的目的通常決定

7、分群法的使用 分割式分群法適合找出類圓形和群集大小相似的群集 階層式分群法或以密集度導向分群法適合找出自然形狀 的群集任意大小的群集 資料內容 有些分群法相當容易受雜訊或偏移值的影響 資料維度與資料記錄數量的大小會影響分群法的成效 品質與速度的取捨 品質與速度的需求常常是矛盾而難以取捨的,17,分割式分群法(1),概念 將資料點歸屬到數個互不交集的群集中，讓每一群集中的資料點與該群集之群集中心 (clustering center) 相似程度高於與其它群集中心，企圖使得每個資料點距離它所屬的群集中心的距離偏移值為最小 將n個資料點分配k個互不交集的群中，其距離總偏移值 (total devia

8、tion) E： x表示一資料點，ui表示Si群集的群集中心,18,分割式分群法(2),最小距離總偏移值 除非資料點所有可能的組合都嘗試當作一開始之起始群集中心點，否則將無法保證在所設定之k個群集中，得到最小距離總偏移值 反覆重新配置技術 分割式分群法一開始會隨機先選擇k個資料點當作起始之群集中心 接著每一回合都企圖尋找更好的群集中心來降低距離總偏移值，一旦距離總偏移值不再變動或已執行一定的回合數，則終止處理並輸出分群結果 一開始所挑選之起始資料點的好壞，將對於分群結果優劣具有決定性的影響,19,分割式分群法(3),k-平均法 (k-means method) k-物件法 (k-medoids

9、 method) 反覆自我組織分析技術 (Iterative Self-Organ-izing Data Analysis Technique, ISODATA),20,k-平均法 (k-means method) k-物件法 (k-medoids method) 反覆自我組織分析技術 (Iterative Self-Organ-izing Data Analysis Technique, ISODATA),21,k-平均法(1),k-平均法的概念 k-平均法使用群集中的質量中心 (mean) 作為群集中心，因此上述之距離總偏移值可以為： 其中x表示一資料點，mi表示群集Si的質量中心，|Si

10、|表示群集Si中所涵蓋之資料點數量 k-平均法除了一開始需指定k個資料點當作群集之群中心外，其它回合都將產生新的群集中心點 除了尤拉距離計算公式外，也可以利用其他相似度計算公式將資料點歸屬到最接近的群集當中,22,k-平均法(2),k-平均法的運作過程 輸入：一資料集合以及使用者定義之群集數量k 輸出：k個互不交集的群集 步驟 1：隨機從資料集合中選擇任k個資料點當作起始k群的群集中心 步驟 2：利用相似度計算公式，將資料點分別歸屬到距其最近之群集中心所屬的群集，形成k個群集。 步驟 3：利用各群集中所包含的資料點，重新計算各群集之群集中心點 步驟 4：假如由步驟3所得到各群之群集中心與之前所

11、計算之群集中心相同，則表示分群結果已穩定並結束此處理程序並輸出各群結果，否則回到步驟2繼續執行,23,k-平均法(3),k = 3,24,k-平均法(4),25,k-平均法(5),k-平均法在概念與實作上相當的簡單，且在處理大量資料時相當有擴充性 (scalable) 且有效率，但是卻也存在一些缺點 無法處理類別性資料維度 容易受雜訊與偏移值影響其群集中心 起始群集中心選擇上的影響 群集數量決定上的困難,26,k-平均法(6),無法處理類別性資料維度 由於k-平均值法以群集中的質量中心當作群集中心，對於類別性資料維度所描述之資料集合而言，並無法求得群集的質量中心,27,k-平均法(7),容易受

12、雜訊與偏移值影響其群集中心,28,k-平均法(8),起始群集中心選擇上的影響,29,k-平均法(9),群集數量決定上的困難,30,k-平均法 (k-means method) k-物件法 (k-medoids method) 反覆自我組織分析技術 (Iterative Self-Organ-izing Data Analysis Technique, ISODATA),31,k-物件法(1),k-物件法的概念 改善k-平均法因質量中心所造成無法處理類別性資料和容易受偏移值影響的問題 k-物件法則使用位於每一群中最中心的資料點當作該群集中心 k-物件法在運作上與k-平均法相似，最大的不同是每回合

13、最多只改變一個群集中心，且此變動必須是能使準則函數值E下降 分割環繞物件法(Partitioning Around Medoids, PAM),32,k-物件法(2),分割環繞物件法(PAM)的運作過程 輸入：一資料集合以及使用者定義之群集數量k 輸出：k個互不交集的群集 步驟 1：隨機從資料集合選擇任k個資料點當作起始k群的中心點 步驟 2：利用相似度計算公式，將資料點分別歸屬到距其最近之群集中心，形成k個群集 步驟 3：由資料集合中任選一非群集中心之資料點，並取代任一選取之群集中心，並計算距離總偏移值E 步驟 4：假如取代後所求得之距離總偏移值E下降，取代就成立，同時回到步驟2展開下一個群

14、集中心取代的動作 步驟 5：如果所有非群集中心之資料點都無法取代已存在之群集中心，則結束此處理程序並輸出各群結果,33,k-物件法(3),k = 3,34,k-平均法 (k-means method) k-物件法 (k-medoids method) 反覆自我組織分析技術 (Iterative Self-Organ-izing Data Analysis Technique, ISODATA),35,ISODATA(1),ISODATA的概念 改善k-平均法對於起始群集中心和群集數量這兩個問題 針對初步分群後的結果，透過使用者所設定的門檻值，再進行合併群集或分裂群集的補救動作 假如某一群集中的

15、資料點分佈過於分散，使得群集變異值 (variance) 大於使用者所設定的門檻值，則將對此群集進行分裂成兩個群集的動作 假如兩個群集彼此相當接近，使得兩群集之群集中心之距離小於使用者所給定之另一門檻值，則將其合併成一個群集,36,ISODATA(2),ISODATA的運作過程 輸入：一資料集合、使用者定義之起始群集數量k、群集分裂門檻值ts、群集合併門檻值tm、群集資料點數量門檻值tn 輸出：c個互不交集的群集 (c可能不等於k) 步驟 1：隨機從資料集合中選擇任k個資料點當作起始中心點。 步驟 2：利用相似度計算公式，將資料點分別歸屬到距其最近之群集中心所屬的群集，形成k個群集 步驟 3：

16、摒除資料點數量小於tn的群集，資料點數量小於tn的群集可以視為偏移值；並重新計算其他保留下來之群集的群集中心 步驟 4：假如某一群集中的資料點分佈過於分散，使得群集變異值大於ts且群集內資料點數量大於 (2 * tn)，則將此群集分裂成兩個群集 步驟 5：假如兩個群集彼此相當接近，使得兩群集之群集中心之距離小於tm，則將其合併成一個群集 步驟 6：重新計算分裂或合併所形成之群集的群集中心，並回到步驟2繼續處理；如果群集中心不再變動，表示分群結果已穩定，則結束此處理程序並輸出各群結果,37,ISODATA(3),起始k = 3,38,非分割式分群法(1),分割式分群法對於自然形狀的群集與任意大小

17、的群集的困難,39,非分割式分群法(2),階層式分群法(hierarchical method) 密集度為導向的分群法(density-based algorithm),40,階層式分群法(hierarchical method) 密集度為導向的分群法(density-based algorithm),41,階層式分群法(1),概念 將所要處理之資料集合的資料點，利用聚合或分裂的方式，將彼此相似度高的較小群集合併成較大的群集，或者將較大的群集進行分離 最後利用樹狀結構圖 (dendrogram) 來表示群集間彼此關係 利用所產生之樹狀結構，可以彈性地依據使用者不同的需求，對資料集合產生不同的群

18、集數量,42,階層式分群法(2),會員資料表之樹狀結構圖 t1代表會員2與會員3之相似程度，要求輸出為三個群集時，只要設定相似度門檻值在t4與t5之間,43,階層式分群法(3),傳統階層式分群法 聚合法(AGNES) 一開始將每個資料點都視為是一個獨立的群集，然後依據群集間相似度計算公式，不斷地合併二個最相似的群集，直到最後所有的群集都合併成一個大群集或達到某個終止條件 分裂法(DIANA) 分裂法是採用由上而下的處理方式，一開始時將所有資料點視為一個大群集，同樣不斷地依據相似度計算公式將大群集分裂成較小的子群集，直到最後每個物件各自為一個獨立的群集或達到某個終止條件為止,44,階層式分群法(

19、4),聚合法的運作過程 輸入：一資料集合 輸出：以樹狀結構所表示的群集關係 步驟 1：將資料集合中每個資料點當作個別群集 步驟 2：利用群集間相似度計算公式，將最相似的兩個群集加以合併，形成一新的群集，並以樹狀結構記錄此群集關係。重複執行步驟 2，直到所有的資料點都歸屬到同一群集或滿足使用者所設定之終止條件為止,45,階層式分群法(5),46,階層式分群法(6),47,階層式分群法(7),48,階層式分群法(8),傳統階層式分群法的不足 dmean、dmax和davg此三種群集相似度計算公式，可能產生以下分群結果,49,階層式分群法(9),傳統階層式分群法的不足 dmin此群集相似度計算公式，

20、可能產生以下分群結果,50,階層式分群法(10),多代表點分群法 (CURE) 相對於傳統階層式分群法透過單點考量(例如：dmean) 或所有點考量(例如：dmin)來決定是否合併群集，多代表點分群法選擇用一定數量且分散得當的多個代表性的資料點來表示一個群集，並配合dmin來衡量是否合併兩個群集 所選擇的代表性資料點可藉著事先定義好、介於0和1之間的收縮係數(shrinking factor)，以群集中心為基點做適當地收縮 (shrinking)，以防止因為偏移值造成群集中心的偏移，達到充分表示整個群集的效果 兼容了單點考量與所有點考量的優點，對偏移值的處理上也較不敏感,51,階層式分群法(1

21、0),多代表點分群法的運作過程 輸入：一資料集合、代表性資料點數量c、收縮係數。 輸出：以樹狀結構所表示的群集關係 步驟 1：將資料集合中每個資料點當作個別之群集 步驟 2：對每一群集選擇c個代表性資料點，並根據做適當地收縮 步驟 3：以每一群集所得到的代表性資料點為考量，將彼此距離最接近的兩個群集加以合併，形成一新的群集，並以階層結構記錄此群集關係。重複執行步驟 2，直到所有的資料點都歸屬到同一群集或滿足使用者所設定之終止條件為止,52,階層式分群法(11),代表性資料點數量c = 3,53,階層式分群法(hierarchical method) 密集度為導向的分群法(density-bas

22、ed algorithm),54,密集度導向分群法(1),概念 利用資料點間密度(density)的關係來分群 將資料集合中較密集的資料視為一個群集；運用密集度的方法不但可用來濾除偏移值或雜訊，且可對任意形狀之群集進行分群,55,密集度導向分群法(2),高密度關連區域分群法(DBSCAN) 不斷地評估一個資料點的鄰近資料點是否夠密集，若周遭資料點分佈的密度夠大，就擴大群集邊界 利用Eps和Minpts二個參數，來計算距離此資料點Eps距離以內的資料點數量是否大於Minpts,56,密集度導向分群法(3),DBSCAN之相關定義 距離資料點半徑長度Eps以內的鄰近區域，則為該資料點的Eps-鄰近

23、區域 資料點的Eps-鄰近區域中包含了至少Minpts個資料點，則該資料點為核心物件 資料點p的位置是在某核心物件q的Eps-鄰近區域內，則資料點p可被稱為 “可由q直接密度可達(directly density-reachable)” 的物件 假如資料點p可由q1直接密度可達、而q1可由q2直接密度可達、而qi-1是可由qi直接密度可達，則資料點p可以被稱為 “可由qi密度可達 (density-reachable)” 的物件 假如資料點p和q都可由o密度可達，則p和q可以被稱為 “密度連接(density-connected)”,57,密集度導向分群法(4),58,密集度導向分群法(5),

24、DBSCAN對於群集和偏移值的定義 對資料點p和q而言，假如q歸屬於群集A，且p可由q密度可達，則p也將歸屬於群集A；對於歸屬於相同群集A的p和q而言，p和q必為密度連接 對無法歸屬到任何群集之資料點，將被視為雜訊、偏移值,59,密集度導向分群法(6),DBSCAN的運作過程 輸入：一資料集合、鄰近區域Eps、資料點數量門檻值Minpts 輸出：互不交集之所有群集 步驟 1：檢查資料集合中每個資料點是否為核心物件，並以所找到之核心物件為群集中心，結合其Eps-鄰近區域中的所有資料點，形成初步之群集 步驟 2：選擇任一核心物件，往外尋找可由此核心物件密度可達的資料點，假如發現會擴張到某個已有所屬

25、群集的核心物件，則該群集將被合併，變成一個較大之群集；否則重新啟動步驟2，選擇其他未被合併或處理過之核心物件，繼續執行 步驟 3：當所有核心物件都處理過為止,60,密集度導向分群法(7),61,分群法在大型資料集合之設計,動機與需求 隨著資料維度與資料量越來越龐大，傳統分群法由於需處理每一資料點，並需要將整個資料集合載入到記憶體中做群集分析，變得困難而不可行 當資料集合不斷有新的資料記錄加入，老舊的資料記錄也將移出並歸檔，如果資料集合必須重新再處理以更新群集分析的結果，這將造成更多時間與空間的花費 除了針對任意形狀與群集大小差異大等問題外，如何處理大量資料集合與動態更新群集分析結果，也是目前發

26、展的主要趨勢,62,分群法在大型資料集合之設計策略(1),抽樣處理 由資料集合中抽取部分的樣本來代表整個資料集合母體 概括處理 將相似度高的資料點先行聚集成基本單元，只對基本單元進行群集分析，而不直接處理底層的資料點 相似度很高的資料點，只利用其中一個資料點來代表 將資料集合中的資料點分配到許多較小、相似度高的子群集，並以子群集的群集中心來代表此群集 將表示整個資料集合的空間區域切割成數個單元矩形，利用統計資訊，例如平均值、資料點統計分佈，來表示每一個小矩形,63,分群法在大型資料集合之設計策略(2),各個擊破遞迴式處理 將一個大問題分解成數個可處理的小部分，如果所分解後的小部分問題在處理上仍

27、相當困難，則繼續將其進一步分解成更小的部分，以此遞迴式處理；最後，將每一小部分問題的處理結果整合起來，達到解決整個問題的目的 平行處理 將整個群集分析過程所要處理的工作，分給多個處理器或機器來共同完成 資料集合分割成數個部分 將資料點之資料維度切割成數個部分,64,分群法在大型資料集合之設計策略(3),漸進式處理 隨著資料點的加入或移除，動態地更新分群結果 當第一個資料點加入時，此資料點將自成一個群集；接著，對於後續加入的資料點，根據使用者設定之準則，例如：依加入之資料點與群集中心的距離是否低於某一門檻值，決定加入已存在之群集或自成一個群集，直到所有的資料點都處理完畢為止 以資料點陸續移出資料

28、集合而言，一開始資料集合中已存在數個群集，當第一個資料點移出時，根據使用者設定之準則，對所對應之群集調整其群集中心或進行群集合併；直到所有欲移出之資料點都處理完畢為止,65,分群法在大型資料集合之設計策略(4),漸進式處理所遭遇麻煩 順序相依(order-dependence)的問題,66,平衡式反覆化簡和分群法(1),平衡式反覆化簡和分群法(BIRCH) 根據使用者所設定之群集涵蓋範圍，例如群集之半徑，先將資料集合中的資料點以漸進式處理方法分配到許多較小、相似度高的子群集 利用類似聚合式階層分群法的方式，以這些子群集為基本單元，反覆地將其聚合成較大的群集 處理上其利用群集特徵(Cluster

29、ing Feature, CF)來表示每個子群集，並不直接處理所有的資料點，在記憶體空間的利用上非常有效率 為加速將資料點歸屬到所屬之子群集，其將動態構建出一類似B+樹 (B+ tree),67,平衡式反覆化簡和分群法(2),68,平衡式反覆化簡和分群法(3),群集特徵 是由三個概括性資訊 (summarized information) 所組成，假設一群集Si中包含有N個資料點，則該群集特徵CF被定義為: = 為這些N個點的線性總合，SS = 為N個點的平方和 群集特徵能充分完整地表示一個群集，因為不論是在決定資料點所歸屬的群集上或是在決定群集合併的順序,69,平衡式反覆化簡和分群法(4),

30、群集特徵 會員1= 與會員2= 的距離在使用者設定之群集涵蓋範圍內，BIRCH先將其形成一個子群集，則此子群集之群集特徵值將計算如下 = = SS = = (202+202)+(212+262) = 800+1117 = 1917 CF = (2, , 1917),70,平衡式反覆化簡和分群法(5),群集特徵樹 記錄子群集間的親疏遠近的關係 每一非終端節點 (non-leaf node)，記錄所有隸屬之子節點 (children) 的概括性資訊 每一終端節點 (leaf node)，則記錄所隸屬之子群集之概括性資訊 一群集特徵樹包含三個參數 非終端節點之分支係數(B)：用以指定每個非終端節點所允許包含之最大子節點個數 終端節點之分支係數(L)：用以指定每個終端節點所允許包含之最大子群集個數 子群集之門檻值(T)：指定子群集所允許之涵蓋範圍，例如：群集半徑,71,平衡式反覆化簡和分群法(6),群集特徵樹之建立 資料點加入時，透過類似拜訪B+樹的方式，比對部分的非終端節點，決定資料點所歸屬之終端節點與子群集 當資料點加入到位於終端節點的一子群集時，若造成該子群集的涵蓋範圍超過T，則產生一新的子群集，並將資料點加入此群集且計算此子群集特徵；否則，直接加入此資料點到子