《群集分析（ClusterAnalysis）》由会员分享，可在线阅读，更多相关《群集分析（ClusterAnalysis）（75页珍藏版）》请在金锄头文库上搜索。
1、群集分析 (Cluster Analysis)1內容概要簡介資料的表示相似度的計算與測量分群法的採用分割式分群法非分割式分群法分群法在大型資料集合之設計評估分群的結果2簡介(1)群集分析的概念與目的將資料集合中的資料記錄，又稱為資料點，加以分群成數個群集(cluster)，使得每個群集中的資料點間相似程度高於與其它群集中資料點的相似程度 主要的目地是分析資料彼此間的相似程度，藉由分析所找到的群集結果，推論出有用、隱含、令人感興趣的特性和現象在群集分析的過程中，並沒有預先指定好的類別資訊，也沒有任何資訊可以表示資料記錄彼此之間是相關的，所以群集分析被視為一個非監督式學習的過程 3簡介(2)群集分
2、析在資料探勘過程中所扮演的角色資料精簡將原本大量的資料加以分群成數個群集，並從每一個群集中挑選具有代表性的資料記錄來進行後續的處理 推斷假設的產生推斷出所關注資料中可能存在的某些特性或現象“年輕人通常年收入較低”、“中年人通常年收入較高” 推斷假設的驗證對推斷假設作有效性的驗證試圖驗證 “年輕人通常年收入較低，是否也代表其消費能力較低？”此假設性推斷時，可以對於 “年齡”、“年收入” 和 “消費金額” 所描述的資料記錄進行群集分析 歸屬預測分群結果應用於未知分類之資料記錄，預測資料所歸屬的群集 4簡介(3)線上購物網站的使用者族群與消費能力會員年齡平均月收入 (千)12020221263222
3、5441305433265240755385簡介(4)群集分析應用領域交易行為分析解各類型使用者的行為模式空間資料分析幫助使用者自動化分析圖像資料庫所產生的影像資料 ，了解感興趣的特性和現象文件管理將文件加以分門別類，幫助文件資料的管理和使用6簡介(5)群集分析五個主要的循序工作項目資料的表示：找出代表性資料維度來表示資料點相似度的計算與測量：計算資料點間相似的程度分群法的採用：挑選適當的分群演算法評估分群的結果：對群集分析的結果進行評估群集的解釋：領域專家對分群結果做進一步解釋7資料的表示將每一資料點利用有限、一致的資料維度表示濾掉與所分析問題無關、偏差、重複的資料維度不適切的資料維度將造成
4、分群結果凌亂、難以從中獲取各群聚的關係與差異 相對於 “性別” 和 “地址” 這兩個資料維度，“平均月收入” 與 “年齡” 這兩個資料維度將更能幫助了解各類型之會員族群會員2將可以表示為 ，其中21為會員2在 “年齡” 此資料維度的資料數值，而26為會員2在 “平均月收入” 此資料維度的資料數值 8相似度的計算與測量衡量資料點間的相似度將決定資料記錄所歸屬的群聚，並影響整個分群的結果相似度測量法是群集分析中最根本的課題相似度的計算與測量的考量資料型態的考量應用範圍的考量資料離散程度與複雜性的考量 9資料型態的考量(1)連續性資料維度通常利用簡單的空間距離計算公式，透過衡量資料點間距離的遠近來判
5、斷彼此間的相似程度尤拉距離 (Euclidean distance)資料點 xi = 和資料點 xj = 之間的尤拉距離： d2 (xi, xj) = = ( )曼哈頓距離 (Manhattan distance)dM (xi, xj) = = 10資料型態的考量(2)尤拉距離與曼哈頓距離在二維空間上的物理意義會員1= 與會員2= 之間的尤拉距離與曼哈頓距離分別如下所示d2 (x1, x2) = 6dM (x1, x2) = = 7 11資料型態的考量(3)類別型態資料維度利用字串比對的方式，對於資料數值完全相同時則相似度以1表示，否則以0表示透過專家事先訂定資料數值間的相似度與輔助之計算公式
6、先轉換或對應成連續性的資料數值，再套用距離計算公式來計算其相似度 12應用範圍的考量(1)資料點之間的相似程度群集間的相似程度 13應用範圍的考量(2)14資料離散程度與複雜性的考量一般相似度計算公式通常對資料點中各資料維度給予相同的重要性，然而這將造成值域 (domain) 較大的資料維度將左右分群的結果會員A = 、會員B = 與會員C = 透過尤拉距離的相似度公式計算後，將會認定會員A與會員C相似度較高；用人來判斷，會員A與會員B應該較可能屬於同一個族群 15分群法的採用分群法的種類應用領域：應用的目的通常決定分群法的使用分割式分群法適合找出類圓形和群集大小相似的群集階層式分群法或以密集
7、度導向分群法適合找出自然形狀 的群集任意大小的群集資料內容有些分群法相當容易受雜訊或偏移值的影響 資料維度與資料記錄數量的大小會影響分群法的成效 品質與速度的取捨 品質與速度的需求常常是矛盾而難以取捨的 16分割式分群法(1)概念將資料點歸屬到數個互不交集的群集中，讓每一群集中的資料點與該群集之群集中心 (clustering center) 相似程度高於與其它群集中心，企圖使得每個資料點距離它所屬的群集中心的距離偏移值為最小 將n個資料點分配k個互不交集的群中，其距離總偏移值 (total deviation) E：x表示一資料點，ui表示Si群集的群集中心17分割式分群法(2)最小距離總偏
8、移值除非資料點所有可能的組合都嘗試當作一開始之起始群集中心點，否則將無法保證在所設定之k個群集中，得到最小距離總偏移值反覆重新配置技術分割式分群法一開始會隨機先選擇k個資料點當作起始之群集中心接著每一回合都企圖尋找更好的群集中心來降低距離總偏移值，一旦距離總偏移值不再變動或已執行一定的回合數，則終止處理並輸出分群結果一開始所挑選之起始資料點的好壞，將對於分群結果優劣具有決定性的影響 18分割式分群法(3)k-平均法 (k-means method)k-物件法 (k-medoids method)反覆自我組織分析技術 (Iterative Self-Organ-izing Data Analys
9、is Technique, ISODATA) 19 k-平均法 (k-means method)k-物件法 (k-medoids method)反覆自我組織分析技術 (Iterative Self-Organ-izing Data Analysis Technique, ISODATA) 20k-平均法(1) k-平均法的概念k-平均法使用群集中的質量中心 (mean) 作為群集中心，因此上述之距離總偏移值可以為：其中x表示一資料點，mi表示群集Si的質量中心，|Si|表示群集Si中所涵蓋之資料點數量k-平均法除了一開始需指定k個資料點當作群集之群中心外，其它回合都將產生新的群集中心點除了尤拉
10、距離計算公式外，也可以利用其他相似度計算公式將資料點歸屬到最接近的群集當中 21k-平均法(2)k-平均法的運作過程輸入：一資料集合以及使用者定義之群集數量k輸出：k個互不交集的群集步驟 1：隨機從資料集合中選擇任k個資料點當作起始k群的群集中心步驟 2：利用相似度計算公式，將資料點分別歸屬到距其最近之群集中心所屬的群集，形成k個群集。步驟 3：利用各群集中所包含的資料點，重新計算各群集之群集中心點步驟 4：假如由步驟3所得到各群之群集中心與之前所計算之群集中心相同，則表示分群結果已穩定並結束此處理程序並輸出各群結果，否則回到步驟2繼續執行 22k-平均法(3)k = 323k-平均法(4)2
11、4k-平均法(5)k-平均法在概念與實作上相當的簡單，且在處理大量資料時相當有擴充性 (scalable) 且有效率，但是卻也存在一些缺點無法處理類別性資料維度容易受雜訊與偏移值影響其群集中心 起始群集中心選擇上的影響群集數量決定上的困難 25k-平均法(6)無法處理類別性資料維度由於k-平均值法以群集中的質量中心當作群集中心，對於類別性資料維度所描述之資料集合而言，並無法求得群集的質量中心26k-平均法(7)容易受雜訊與偏移值影響其群集中心 27k-平均法(8)起始群集中心選擇上的影響 28k-平均法(9)群集數量決定上的困難29 k-平均法 (k-means method)k-物件法 (k
12、-medoids method)反覆自我組織分析技術 (Iterative Self-Organ-izing Data Analysis Technique, ISODATA) 30k-物件法(1)k-物件法的概念改善k-平均法因質量中心所造成無法處理類別性資料和容易受偏移值影響的問題k-物件法則使用位於每一群中最中心的資料點當作該群集中心k-物件法在運作上與k-平均法相似，最大的不同是每回合最多只改變一個群集中心，且此變動必須是能使準則函數值E下降分割環繞物件法(Partitioning Around Medoids, PAM) 31k-物件法(2)分割環繞物件法(PAM)的運作過程輸入：一
13、資料集合以及使用者定義之群集數量k輸出：k個互不交集的群集步驟 1：隨機從資料集合選擇任k個資料點當作起始k群的中心點步驟 2：利用相似度計算公式，將資料點分別歸屬到距其最近之群集中心，形成k個群集步驟 3：由資料集合中任選一非群集中心之資料點，並取代任一選取之群集中心，並計算距離總偏移值E步驟 4：假如取代後所求得之距離總偏移值E下降，取代就成立，同時回到步驟2展開下一個群集中心取代的動作步驟 5：如果所有非群集中心之資料點都無法取代已存在之群集中心，則結束此處理程序並輸出各群結果 32k-物件法(3)k = 333 k-平均法 (k-means method)k-物件法 (k-medoid
14、s method)反覆自我組織分析技術 (Iterative Self-Organ-izing Data Analysis Technique, ISODATA) 34ISODATA(1)ISODATA的概念改善k-平均法對於起始群集中心和群集數量這兩個問題針對初步分群後的結果，透過使用者所設定的門檻值，再進行合併群集或分裂群集的補救動作假如某一群集中的資料點分佈過於分散，使得群集變異值 (variance) 大於使用者所設定的門檻值，則將對此群集進行分裂成兩個群集的動作假如兩個群集彼此相當接近，使得兩群集之群集中心之距離小於使用者所給定之另一門檻值，則將其合併成一個群集 35ISODATA(
15、2)ISODATA的運作過程輸入：一資料集合、使用者定義之起始群集數量k、群集分裂門檻值ts、群集合併門檻值tm、群集資料點數量門檻值tn輸出：c個互不交集的群集 (c可能不等於k)步驟 1：隨機從資料集合中選擇任k個資料點當作起始中心點。步驟 2：利用相似度計算公式，將資料點分別歸屬到距其最近之群集中心所屬的群集，形成k個群集步驟 3：摒除資料點數量小於tn的群集，資料點數量小於tn的群集可以視為偏移值；並重新計算其他保留下來之群集的群集中心步驟 4：假如某一群集中的資料點分佈過於分散，使得群集變異值大於ts且群集內資料點數量大於 (2 * tn)，則將此群集分裂成兩個群集步驟 5：假如兩個
16、群集彼此相當接近，使得兩群集之群集中心之距離小於tm，則將其合併成一個群集步驟 6：重新計算分裂或合併所形成之群集的群集中心，並回到步驟2繼續處理；如果群集中心不再變動，表示分群結果已穩定，則結束此處理程序並輸出各群結果36ISODATA(3)起始k = 3 37非分割式分群法(1)分割式分群法對於自然形狀的群集與任意大小的群集的困難38非分割式分群法(2)階層式分群法(hierarchical method)密集度為導向的分群法(density-based algorithm)39 階層式分群法(hierarchical method)密集度為導向的分群法(density-based alg
17、orithm)40階層式分群法(1)概念將所要處理之資料集合的資料點，利用聚合或分裂的方式，將彼此相似度高的較小群集合併成較大的群集，或者將較大的群集進行分離最後利用樹狀結構圖 (dendrogram) 來表示群集間彼此關係利用所產生之樹狀結構，可以彈性地依據使用者不同的需求，對資料集合產生不同的群集數量41階層式分群法(2)會員資料表之樹狀結構圖t1代表會員2與會員3之相似程度，要求輸出為三個群集時，只要設定相似度門檻值在t4與t5之間 42階層式分群法(3)傳統階層式分群法聚合法(AGNES)一開始將每個資料點都視為是一個獨立的群集，然後依據群集間相似度計算公式，不斷地合併二個最相似的群集
18、，直到最後所有的群集都合併成一個大群集或達到某個終止條件分裂法(DIANA)分裂法是採用由上而下的處理方式，一開始時將所有資料點視為一個大群集，同樣不斷地依據相似度計算公式將大群集分裂成較小的子群集，直到最後每個物件各自為一個獨立的群集或達到某個終止條件為止 43階層式分群法(4)聚合法的運作過程輸入：一資料集合輸出：以樹狀結構所表示的群集關係步驟 1：將資料集合中每個資料點當作個別群集步驟 2：利用群集間相似度計算公式，將最相似的兩個群集加以合併，形成一新的群集，並以樹狀結構記錄此群集關係。重複執行步驟 2，直到所有的資料點都歸屬到同一群集或滿足使用者所設定之終止條件為止 44階層式分群法(
19、5)45階層式分群法(6)46階層式分群法(7)47階層式分群法(8)傳統階層式分群法的不足dmean、dmax和davg此三種群集相似度計算公式，可能產生以下分群結果 48階層式分群法(9)傳統階層式分群法的不足dmin此群集相似度計算公式，可能產生以下分群結果 49階層式分群法(10)多代表點分群法 (CURE)相對於傳統階層式分群法透過單點考量(例如：dmean) 或所有點考量(例如：dmin)來決定是否合併群集，多代表點分群法選擇用一定數量且分散得當的多個代表性的資料點來表示一個群集，並配合dmin來衡量是否合併兩個群集所選擇的代表性資料點可藉著事先定義好、介於0和1之間的收縮係數(s
20、hrinking factor)，以群集中心為基點做適當地收縮 (shrinking)，以防止因為偏移值造成群集中心的偏移，達到充分表示整個群集的效果兼容了單點考量與所有點考量的優點，對偏移值的處理上也較不敏感50階層式分群法(10)多代表點分群法的運作過程輸入：一資料集合、代表性資料點數量c、收縮係數。輸出：以樹狀結構所表示的群集關係步驟 1：將資料集合中每個資料點當作個別之群集步驟 2：對每一群集選擇c個代表性資料點，並根據做適當地收縮步驟 3：以每一群集所得到的代表性資料點為考量，將彼此距離最接近的兩個群集加以合併，形成一新的群集，並以階層結構記錄此群集關係。重複執行步驟 2，直到所有的
21、資料點都歸屬到同一群集或滿足使用者所設定之終止條件為止51階層式分群法(11)代表性資料點數量c = 352 階層式分群法(hierarchical method)密集度為導向的分群法(density-based algorithm)53密集度導向分群法(1)概念利用資料點間密度(density)的關係來分群將資料集合中較密集的資料視為一個群集；運用密集度的方法不但可用來濾除偏移值或雜訊，且可對任意形狀之群集進行分群 54密集度導向分群法(2)高密度關連區域分群法(DBSCAN)不斷地評估一個資料點的鄰近資料點是否夠密集，若周遭資料點分佈的密度夠大，就擴大群集邊界利用Eps和Minpts二個參
22、數，來計算距離此資料點Eps距離以內的資料點數量是否大於Minpts55密集度導向分群法(3)DBSCAN之相關定義距離資料點半徑長度Eps以內的鄰近區域，則為該資料點的Eps-鄰近區域資料點的Eps-鄰近區域中包含了至少Minpts個資料點，則該資料點為核心物件資料點p的位置是在某核心物件q的Eps-鄰近區域內，則資料點p可被稱為 “可由q直接密度可達(directly density-reachable)” 的物件假如資料點p可由q1直接密度可達、而q1可由q2直接密度可達、而qi-1是可由qi直接密度可達，則資料點p可以被稱為 “可由qi密度可達 (density-reachable)”
23、 的物件假如資料點p和q都可由o密度可達，則p和q可以被稱為 “密度連接(density-connected)” 56密集度導向分群法(4)57密集度導向分群法(5)DBSCAN對於群集和偏移值的定義對資料點p和q而言，假如q歸屬於群集A，且p可由q密度可達，則p也將歸屬於群集A；對於歸屬於相同群集A的p和q而言，p和q必為密度連接對無法歸屬到任何群集之資料點，將被視為雜訊、偏移值 58密集度導向分群法(6)DBSCAN的運作過程輸入：一資料集合、鄰近區域Eps、資料點數量門檻值Minpts輸出：互不交集之所有群集步驟 1：檢查資料集合中每個資料點是否為核心物件，並以所找到之核心物件為群集中心
24、，結合其Eps-鄰近區域中的所有資料點，形成初步之群集步驟 2：選擇任一核心物件，往外尋找可由此核心物件密度可達的資料點，假如發現會擴張到某個已有所屬群集的核心物件，則該群集將被合併，變成一個較大之群集；否則重新啟動步驟2，選擇其他未被合併或處理過之核心物件，繼續執行步驟 3：當所有核心物件都處理過為止 59密集度導向分群法(7) 60分群法在大型資料集合之設計動機與需求隨著資料維度與資料量越來越龐大，傳統分群法由於需處理每一資料點，並需要將整個資料集合載入到記憶體中做群集分析，變得困難而不可行當資料集合不斷有新的資料記錄加入，老舊的資料記錄也將移出並歸檔，如果資料集合必須重新再處理以更新群集
25、分析的結果，這將造成更多時間與空間的花費除了針對任意形狀與群集大小差異大等問題外，如何處理大量資料集合與動態更新群集分析結果，也是目前發展的主要趨勢 61分群法在大型資料集合之設計策略(1)抽樣處理由資料集合中抽取部分的樣本來代表整個資料集合母體概括處理將相似度高的資料點先行聚集成基本單元，只對基本單元進行群集分析，而不直接處理底層的資料點相似度很高的資料點，只利用其中一個資料點來代表 將資料集合中的資料點分配到許多較小、相似度高的子群集，並以子群集的群集中心來代表此群集將表示整個資料集合的空間區域切割成數個單元矩形，利用統計資訊，例如平均值、資料點統計分佈，來表示每一個小矩形 62分群法在大
26、型資料集合之設計策略(2)各個擊破遞迴式處理將一個大問題分解成數個可處理的小部分，如果所分解後的小部分問題在處理上仍相當困難，則繼續將其進一步分解成更小的部分，以此遞迴式處理；最後，將每一小部分問題的處理結果整合起來，達到解決整個問題的目的 平行處理將整個群集分析過程所要處理的工作，分給多個處理器或機器來共同完成資料集合分割成數個部分將資料點之資料維度切割成數個部分63分群法在大型資料集合之設計策略(3)漸進式處理隨著資料點的加入或移除，動態地更新分群結果當第一個資料點加入時，此資料點將自成一個群集；接著，對於後續加入的資料點，根據使用者設定之準則，例如：依加入之資料點與群集中心的距離是否低於
27、某一門檻值，決定加入已存在之群集或自成一個群集，直到所有的資料點都處理完畢為止以資料點陸續移出資料集合而言，一開始資料集合中已存在數個群集，當第一個資料點移出時，根據使用者設定之準則，對所對應之群集調整其群集中心或進行群集合併；直到所有欲移出之資料點都處理完畢為止 64分群法在大型資料集合之設計策略(4)漸進式處理所遭遇麻煩順序相依(order-dependence)的問題 65平衡式反覆化簡和分群法(1)平衡式反覆化簡和分群法(BIRCH)根據使用者所設定之群集涵蓋範圍，例如群集之半徑，先將資料集合中的資料點以漸進式處理方法分配到許多較小、相似度高的子群集利用類似聚合式階層分群法的方式，以這
28、些子群集為基本單元，反覆地將其聚合成較大的群集處理上其利用群集特徵(Clustering Feature, CF)來表示每個子群集，並不直接處理所有的資料點，在記憶體空間的利用上非常有效率為加速將資料點歸屬到所屬之子群集，其將動態構建出一類似B+樹 (B+ tree) 66平衡式反覆化簡和分群法(2)67平衡式反覆化簡和分群法(3)群集特徵是由三個概括性資訊 (summarized information) 所組成，假設一群集Si中包含有N個資料點，則該群集特徵CF被定義為: = 為這些N個點的線性總合，SS = 為N個點的平方和群集特徵能充分完整地表示一個群集，因為不論是在決定資料點所歸屬的
29、群集上或是在決定群集合併的順序68平衡式反覆化簡和分群法(4)群集特徵會員1= 與會員2= 的距離在使用者設定之群集涵蓋範圍內，BIRCH先將其形成一個子群集，則此子群集之群集特徵值將計算如下 = = SS = = (202+202)+(212+262) = 800+1117 = 1917 CF = (2, , 1917)69平衡式反覆化簡和分群法(5)群集特徵樹記錄子群集間的親疏遠近的關係每一非終端節點 (non-leaf node)，記錄所有隸屬之子節點 (children) 的概括性資訊每一終端節點 (leaf node)，則記錄所隸屬之子群集之概括性資訊一群集特徵樹包含三個參數非終端節
30、點之分支係數(B)：用以指定每個非終端節點所允許包含之最大子節點個數終端節點之分支係數(L)：用以指定每個終端節點所允許包含之最大子群集個數子群集之門檻值(T)：指定子群集所允許之涵蓋範圍，例如：群集半徑 70平衡式反覆化簡和分群法(6)群集特徵樹之建立資料點加入時，透過類似拜訪B+樹的方式，比對部分的非終端節點，決定資料點所歸屬之終端節點與子群集當資料點加入到位於終端節點的一子群集時，若造成該子群集的涵蓋範圍超過T，則產生一新的子群集，並將資料點加入此群集且計算此子群集特徵；否則，直接加入此資料點到子群集中，並更新該子群集之群集特徵若因產生新的子群集，造成終端節點之子群集的數量超過所設定之L
31、，則該終端節點將分裂成兩個，並以相差最遠之子群集當作種子(seed)，然後將其他子群集分別歸屬其中；同理，非終端節點進行分裂時，亦相同運作方式底層子群集之群集特徵的改變，將影響上層終端節點與非終端節點中的群集特徵，資訊將從從底端傳達到樹根 71平衡式反覆化簡和分群法(7)BIRCH的運作過程輸入：一資料集合、非終端節點之分支係數B、終端節點之分支係數L 、門檻值T輸出：以樹狀結構所表示的群集關係步驟 1：掃瞄資料集合中的資料點，建立一可以放在記憶體中執行之群集特徵樹。如果群集特徵樹無法載入到記憶體，則增加子群集所允許之T ，並由既有之群集特徵資訊，重新建立一群集特徵樹，以符合記憶體需求步驟 2
32、：將存在終端節點中包含偏移值的子群集由群集特徵樹中移除，去除偏移值對分群結果的影響步驟 3：利用聚合法 (AGNES) 處理群集特徵樹中所包含的子群集(只需處理其群集特徵)，產生最後之分群結果 72評估分群的結果在大多數的分群結果評估上，都是利用二維空間來表現，主要是因為用二維的資料較能夠直接看出分群的結果並進行驗證73總結(1)群集分析在許多應用領域中被廣泛認為是相當有用的工具，一般來講通常包含資料的表示、相似度的計算與測量、分群法的採用、評估分群的結果、群集的解釋等五個工作項目分割式分群法利用反覆重新配置技術，將資料點歸屬到數個互不交集的群集中，意圖找出類圓形且大小差不多的分群結果，但並不
33、適合於任意形狀或群集大小差異大之資料集合階層式分群法利用聚合或分裂的方式，將相似度高的較小群集合併成較大的群集，或者將較大的群集進行分離，利用樹狀結構圖來表示群集間彼此關係。在處理任意形狀群集、群集大小差異大、偏移值等方面比分割式分群法演算法更有效，但其處理的時間與空間需求上卻高出許多 74總結(2)密集度導向的分群法利用資料點間密度的關係來分群，不但可用來濾除偏移值或雜訊，且可對任意形狀之群集進行分群，但是對如何設定適當涵蓋範圍和評估緊密程度卻是一大難題隨著資料維度與資料量越來越龐大，傳統分群法變得困難而不可行；隨著時間的過往，資料集合必須重新再處理以更新群集分析的結果，這將造成更多時間與空間的花費。因此除了針對怎麼去解決任意形狀與群集大小差異大等問題外，如何處理大量資料集合與更新分群結果，也是主要的發展趨勢 75
