chapter6群集分析clusteranalysis

chapter6群集分析clusteranalysis内容摘要：

所造成無法處理 類別性資料 和 容易受偏移值影響的問題 k物件法則使用位於 每一群中 最中心的資料點 當作該群集中心 k物件法在運作上與 k平均法相似， 最大的不同是 每回合最多只改變一個群集中心 ，且此變動必頇是能使準則函數值 E下降  分割環繞物件法 (Partitioning Around Medoids, PAM) 32 k物件法 (2)  分割環繞物件法 (PAM)的運作過程 輸入 ：一資料集合以及使用者定義之群集數量 k 輸出 ： k個互不交集的群集 步驟 1：隨機從資料集合選擇 任 k個資料點 當作 起始 k群的中心點 步驟 2：利用 相似度計算公式 ，將資料點分別 歸屬到距其最近之群集中心 ，形成 k個群集 步驟 3：由資料集合中 任選一非群集中心之資料點 ，並取代 任一選取之群集中心 ，並 計算距離總偏移值 E 步驟 4：假如取代後所求得之 距離總偏移值 E下降 ， 取代就成立 ，同時回到 步驟 2展開下一個群集中心取代的動作 步驟 5：如果所有非群集中心之資料點 都無法取代已存在之群集中心 ，則結束此處理程序並 輸出各群結果 33 k物件法 (3)  k = 3 年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)( a ) ( b)( c )ijhijhijhijh( d)34  k平均法 (kmeans method)  k物件法 (kmedoids method)  反覆自我組織分析技術 (Iterative SelfOrganizing Data Analysis Technique, ISODATA) 35 (Iterative SelfOrganizing Data Analysis Technique (ISODATA)(1)  ISODATA的概念 改善 k平均法 對於 起始群集中心 和 群集數量 這兩個問題 針對 初步分群後的結果 ，透過使用者所設定的 門檻值 ，再進行 合併群集 或 分裂群集 的補救動作 假如某一群集中的 資料點分佈過於分散 ，使得 群集變異值 (variance) 大於 使用者所設定的門檻值 ，則將對此群集進行 分裂成兩個群集 的動作 假如 兩個群集彼此相當接近 ，使得兩群集之 群集中心之距離 小於 使用者所給定之另一門檻值 ，則將其 合併成一個群集 36 ISODATA(2)  ISODATA的運作過程 輸入 ：一資料集合、使用者定義之 起始群集數量 k、群集 分裂門檻值ts、 群集合併門檻值 tm、 群集資料點數量門檻值 tn 輸出 ： c個互不交集的群集 (c可能不等於 k) 步驟 1： 隨機 從資料集合中 選擇任 k個資料點 當作 起始中心點。 步驟 2：利用 相似度計算公式 ，將資料點 分別歸屬到距其最近之群集中心所屬的群集 ，形成 k個群集 步驟 3： 摒除資料點數量小於 tn的群集 ， 資料點數量小於 tn的群集 可以視為 偏移值 ；並重新計算其他 保留下來 之群集的群集中心 步驟 4：假如某一群集中的 資料點分佈過於分散 ，使得 群集變異值大於 ts且群集內 資料點數量大於 (2 * tn)，則將此群集 分裂成兩個群集 步驟 5：假如兩個群集 彼此相當接近 ，使得兩群集之 群集中心之距離小於 tm，則將其 合併成一個群集 步驟 6： 重新計算分裂 或 合併 所形成之群集的 群集中心 ，並回到 步驟 2繼續處理；如果 群集中心不再變動 ，表示分群結果已穩定，則結束此處理程序並 輸出各群結果 37 ISODATA(3)  起始 k = 3 年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)( a ) ( b)( c ) ( d)年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)CiCjCk38 非分割式分群法 (1)  分割式分群法對於自然形狀的群集與任意大小的群集的困難 39 非分割式分群法 (2)  階層式分群法 (hierarchical method)  密集度為導向的分群法 (densitybased algorithm) 40  階層式分群法 (hierarchical method)  密集度為導向的分群法 (densitybased algorithm) 41 階層式分群法 (1)  概念 將所要處理之資料集合的資料點，利用聚合或分裂的方式，將彼此相似度高的較小群集合併成較大的群集，或者將較大的群集進行分離 最後利用樹狀結構圖 (dendrogram) 來表示群集間彼此關係 利用所產生之樹狀結構，可以彈性地依據使用者不同的需求，對資料集合產生不同的群集數量 42 階層式分群法 (2)  會員資料表之樹狀結構圖 t1代表會員 2與會員 3之相似程度，要求輸出為三個群集時，只要設定相似度門檻值在 t4與 t5之間 會員 1 會員 2 會員 3 會員 4 會員 5 會員 6 會員 7t6t5t4t1t3t243 階層式分群法 (3)  傳統階層式分群法 聚合法 (AGNES) 一開始將每個資料點都視為是一個獨立的群集，然後依據群集間相似度計算公式，不斷地合併二個最相似的群集，直到最後所有的群集都合併成一個大群集或達到某個終止條件 分裂法 (DIANA) 分裂法是採用由上而下的處理方式，一開始時將所有資料點視為一個大群集，同樣不斷地依據相似度計算公式將大群集分裂成較小的子群集，直到最後每個物件各自為一個獨立的群集或達到某個終止條件為止 44 階層式分群法 (4)  聚合法的運作過程 輸入：一資料集合 輸出：以樹狀結構所表示的群集關係 步驟 1：將資料集合中每個資料點當作個別群集 步驟 2：利用群集間相似度計算公式，將最相似的兩個群集加以合併，形成一新的群集，並以樹狀結構記錄此群集關係。 重複執行步驟 2，直到所有的資料點都歸屬到同一群集或滿足使用者所設定之終止條件為止 45 階層式分群法 (5) 年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)年齡與平均月收入散佈圖01。