群集分析（ClusterAnalysis）.ppt
75页
群集分析 (Cluster Analysis)1 內容概要簡介資料的表示相似度的計算與測量分群法的採用分割式分群法非分割式分群法分群法在大型資料集合之設計評估分群的結果2 簡介(1)群集分析的概念與目的¥將資料集合中的資料記錄，又稱為資料點，加以分群成數個群集(cluster)，使得每個群集中的資料點間相似程度高於與其它群集中資料點的相似程度 ¥主要的目地是分析資料彼此間的相似程度，藉由分析所找到的群集結果，推論出有用、隱含、令人感興趣的特性和現象¥在群集分析的過程中，並沒有預先指定好的類別資訊，也沒有任何資訊可以表示資料記錄彼此之間是相關的，所以群集分析被視為一個非監督式學習的過程 3 簡介(2)群集分析在資料探勘過程中所扮演的角色¥資料精簡將原本大量的資料加以分群成數個群集，並從每一個群集中挑選具有代表性的資料記錄來進行後續的處理 ¥推斷假設的產生推斷出所關注資料中可能存在的某些特性或現象“年輕人通常年收入較低”、“中年人通常年收入較高” ¥推斷假設的驗證對推斷假設作有效性的驗證試圖驗證 “年輕人通常年收入較低，是否也代表其消費能力較低？”此假設性推斷時，可以對於 “年齡”、“年收入” 和 “消費金額” 所描述的資料記錄進行群集分析 ¥歸屬預測分群結果應用於未知分類之資料記錄，，預測資料所歸屬的群集 4 簡介(3)線上購物網站的使用者族群與消費能力會員年齡平均月收入 (千)120202212632225441305433265240755385 簡介(4)群集分析應用領域¥交易行為分析解各類型使用者的行為模式¥空間資料分析幫助使用者自動化分析圖像資料庫所產生的影像資料 ，了解感興趣的特性和現象¥文件管理將文件加以分門別類，幫助文件資料的管理和使用6 簡介(5)群集分析五個主要的循序工作項目¥資料的表示：：找出代表性資料維度來表示資料點¥相似度的計算與測量：：計算資料點間相似的程度¥分群法的採用：：挑選適當的分群演算法¥評估分群的結果：：對群集分析的結果進行評估¥群集的解釋：：領域專家對分群結果做進一步解釋7 資料的表示將每一資料點利用有限、、一致的資料維度表示濾掉與所分析問題無關、、偏差、、重複的資料維度不適切的資料維度將造成分群結果凌亂、、難以從中獲取各群聚的關係與差異 ¥相對於 “性別” 和 “地址” 這兩個資料維度，“平均月收入” 與 “年齡” 這兩個資料維度將更能幫助了解各類型之會員族群¥會員2將可以表示為 <21, 26 >，其中21為會員2在 “年齡” 此資料維度的資料數值，而26為會員2在 “平均月收入” 此資料維度的資料數值 8 相似度的計算與測量衡量資料點間的相似度將決定資料記錄所歸屬的群聚，，並影響整個分群的結果相似度測量法是群集分析中最根本的課題相似度的計算與測量的考量¥資料型態的考量¥應用範圍的考量¥資料離散程度與複雜性的考量 9 資料型態的考量(1)連續性資料維度¥通常利用簡單的空間距離計算公式，透過衡量資料點間距離的遠近來判斷彼此間的相似程度¥尤拉距離 (Euclidean distance)資料點 xi =
¥步驟 3：利用各群集中所包含的資料點，重新計算各群集之群集中心點¥步驟 4：假如由步驟3所得到各群之群集中心與之前所計算之群集中心相同，則表示分群結果已穩定並結束此處理程序並輸出各群結果，否則回到步驟2繼續執行 22 k-平均法(3)k = 323 k-平均法(4)24 k-平均法(5)k-平均法在概念與實作上相當的簡單，，且在處理大量資料時相當有擴充性 (scalable) 且有效率，，但是卻也存在一些缺點¥無法處理類別性資料維度¥容易受雜訊與偏移值影響其群集中心 ¥起始群集中心選擇上的影響¥群集數量決定上的困難 25 k-平均法(6)無法處理類別性資料維度¥由於k-平均值法以群集中的質量中心當作群集中心，對於類別性資料維度所描述之資料集合而言，並無法求得群集的質量中心26 k-平均法(7)容易受雜訊與偏移值影響其群集中心 27 k-平均法(8)起始群集中心選擇上的影響 28 k-平均法(9)群集數量決定上的困難29 k-平均法 (k-means method)k-物件法 (k-medoids method)反覆自我組織分析技術 (Iterative Self-Organ-izing Data Analysis Technique, ISODATA) 30 k-物件法(1)k-物件法的概念¥改善k-平均法因質量中心所造成無法處理類別性資料和容易受偏移值影響的問題¥k-物件法則使用位於每一群中最中心的資料點當作該群集中心¥k-物件法在運作上與k-平均法相似，最大的不同是每回合最多只改變一個群集中心，，且此變動必須是能使準則函數值E下降分割環繞物件法(Partitioning Around Medoids, PAM) 31 k-物件法(2)分割環繞物件法(PAM)的運作過程¥輸入：一資料集合以及使用者定義之群集數量k¥輸出：k個互不交集的群集¥步驟 1：隨機從資料集合選擇任k個資料點當作起始k群的中心點¥步驟 2：利用相似度計算公式，將資料點分別歸屬到距其最近之群集中心，形成k個群集¥步驟 3：由資料集合中任選一非群集中心之資料點，並取代任一選取之群集中心，並計算距離總偏移值E¥步驟 4：假如取代後所求得之距離總偏移值E下降，取代就成立，同時回到步驟2展開下一個群集中心取代的動作¥步驟 5：如果所有非群集中心之資料點都無法取代已存在之群集中心，則結束此處理程序並輸出各群結果 32 k-物件法(3)k = 333 k-平均法 (k-means method)k-物件法 (k-medoids method)反覆自我組織分析技術 (Iterative Self-Organ-izing Data Analysis Technique, ISODATA) 34 ISODATA(1)ISODATA的概念¥改善k-平均法對於起始群集中心和群集數量這兩個問題¥針對初步分群後的結果，透過使用者所設定的門檻值，再進行合併群集或分裂群集的補救動作假如某一群集中的資料點分佈過於分散，使得群集變異值 (variance) 大於使用者所設定的門檻值，則將對此群集進行分裂成兩個群集的動作假如兩個群集彼此相當接近，使得兩群集之群集中心之距離小於使用者所給定之另一門檻值，則將其合併成一個群集 35 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繼續處理；如果群集中心不再變動，表示分群結果已穩定，則結束此處理程序並輸出各群結果36 ISODATA(3)起始k = 3 37 非分割式分群法(1)分割式分群法對於自然形狀的群集與任意大小的群集的困難38 非分割式分群法(2)階層式分群法(hierarchical method)密集度為導向的分群法(density-based algorithm)39 階層式分群法(hierarchical method)密集度為導向的分群法(density-based algorithm)40 階層式分群法(1)概念¥將所要處理之資料集合的資料點，利用聚合或分裂的方式，將彼此相似度高的較小群集合併成較大的群集，或者將較大的群集進行分離¥最後利用樹狀結構圖 (dendrogram) 來表示群集間彼此關係¥利用所產生之樹狀結構，可以彈性地依據使用者不同的需求，對資料集合產生不同的群集數量41 階層式分群法(2)會員資料表之樹狀結構圖¥t1代表會員2與會員3之相似程度，要求輸出為三個群集時，只要設定相似度門檻值在t4與t5之間 42 階層式分群法(3)傳統階層式分群法¥聚合法(AGNES)一開始將每個資料點都視為是一個獨立的群集，然後依據群集間相似度計算公式，不斷地合併二個最相似的群集，直到最後所有的群集都合併成一個大群集或達到某個終止條件¥分裂法(DIANA)分裂法是採用由上而下的處理方式，一開始時將所有資料點視為一個大群集，同樣不斷地依據相似度計算公式將大群集分裂成較小的子群集，直到最後每個物件各自為一個獨立的群集或達到某個終止條件為止 43 階層式分群法(4)聚合法的運作過程¥輸入：一資料集合¥輸出：以樹狀結構所表示的群集關係¥步驟 1：將資料集合中每個資料點當作個別群集¥步驟 2：利用群集間相似度計算公式，將最相似的兩個群集加以合併，形成一新的群集，並以樹狀結構記錄此群集關係。
重複執行步驟 2，直到所有的資料點都歸屬到同一群集或滿足使用者所設定之終止條件為止 44 階層式分群法(5)45 階層式分群法(6)46 階層式分群法(7)47 階層式分群法(8)傳統階層式分群法的不足¥dmean、dmax和davg此三種群集相似度計算公式，可能產生以下分群結果 48 階層式分群法(9)傳統階層式分群法的不足¥dmin此群集相似度計算公式，可能產生以下分群結果 49 階層式分群法(10)多代表點分群法 (CURE)¥相對於傳統階層式分群法透過單點考量(例如：dmean) 或所有點考量(例如：dmin)來決定是否合併群集，多代表點分群法選擇用一定數量且分散得當的多個代表性的資料點來表示一個群集，並配合dmin來衡量是否合併兩個群集¥所選擇的代表性資料點可藉著事先定義好、介於0和1之間的收縮係數(shrinking factor)，以群集中心為基點做適當地收縮 (shrinking)，以防止因為偏移值造成群集中心的偏移，達到充分表示整個群集的效果¥兼容了單點考量與所有點考量的優點，對偏移值的處理上也較不敏感50 階層式分群法(10)多代表點分群法的運作過程¥輸入：一資料集合、代表性資料點數量c、收縮係數。
¥輸出：以樹狀結構所表示的群集關係¥步驟 1：將資料集合中每個資料點當作個別之群集¥步驟 2：對每一群集選擇c個代表性資料點，並根據做適當地收縮¥步驟 3：以每一群集所得到的代表性資料點為考量，將彼此距離最接近的兩個群集加以合併，形成一新的群集，並以階層結構記錄此群集關係重複執行步驟 2，直到所有的資料點都歸屬到同一群集或滿足使用者所設定之終止條件為止51 階層式分群法(11)代表性資料點數量c = 352 階層式分群法(hierarchical method)密集度為導向的分群法(density-based algorithm)53 密集度導向分群法＊＊(1)概念¥利用資料點間密度(density)的關係來分群¥將資料集合中較密集的資料視為一個群集；運用密集度的方法不但可用來濾除偏移值或雜訊，且可對任意形狀之群集進行分群 54 密集度導向分群法＊＊(2)高密度關連區域分群法(DBSCAN)¥不斷地評估一個資料點的鄰近資料點是否夠密集，若周遭資料點分佈的密度夠大，就擴大群集邊界¥利用Eps和Minpts二個參數，來計算距離此資料點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)” 的物件¥假如資料點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：檢查資料集合中每個資料點是否為核心物件，並以所找到之核心物件為群集中心，結合其Eps-鄰近區域中的所有資料點，形成初步之群集¥步驟 2：選擇任一核心物件，往外尋找可由此核心物件密度可達的資料點，假如發現會擴張到某個已有所屬群集的核心物件，則該群集將被合併，變成一個較大之群集；否則重新啟動步驟2，選擇其他未被合併或處理過之核心物件，繼續執行¥步驟 3：當所有核心物件都處理過為止 59 密集度導向分群法＊＊(7) 60 分群法在大型資料集合之設計動機與需求¥隨著資料維度與資料量越來越龐大，傳統分群法由於需處理每一資料點，並需要將整個資料集合載入到記憶體中做群集分析，變得困難而不可行¥當資料集合不斷有新的資料記錄加入，老舊的資料記錄也將移出並歸檔，如果資料集合必須重新再處理以更新群集分析的結果，這將造成更多時間與空間的花費¥除了針對任意形狀與群集大小差異大等問題外，如何處理大量資料集合與動態更新群集分析結果，也是目前發展的主要趨勢 61 分群法在大型資料集合之設計策略(1)抽樣處理¥由資料集合中抽取部分的樣本來代表整個資料集合母體概括處理¥將相似度高的資料點先行聚集成基本單元，只對基本單元進行群集分析，而不直接處理底層的資料點相似度很高的資料點，只利用其中一個資料點來代表 將資料集合中的資料點分配到許多較小、相似度高的子群集，並以子群集的群集中心來代表此群集將表示整個資料集合的空間區域切割成數個單元矩形，利用統計資訊，例如平均值、資料點統計分佈，來表示每一個小矩形 62 分群法在大型資料集合之設計策略(2)各個擊破遞迴式處理¥將一個大問題分解成數個可處理的小部分，如果所分解後的小部分問題在處理上仍相當困難，則繼續將其進一步分解成更小的部分，以此遞迴式處理；最後，將每一小部分問題的處理結果整合起來，達到解決整個問題的目的 平行處理¥將整個群集分析過程所要處理的工作，分給多個處理器或機器來共同完成資料集合分割成數個部分將資料點之資料維度切割成數個部分63 分群法在大型資料集合之設計策略(3)漸進式處理¥隨著資料點的加入或移除，動態地更新分群結果¥當第一個資料點加入時，此資料點將自成一個群集；接著，對於後續加入的資料點，根據使用者設定之準則，例如：依加入之資料點與群集中心的距離是否低於某一門檻值，決定加入已存在之群集或自成一個群集，直到所有的資料點都處理完畢為止¥以資料點陸續移出資料集合而言，一開始資料集合中已存在數個群集，當第一個資料點移出時，根據使用者設定之準則，對所對應之群集調整其群集中心或進行群集合併；直到所有欲移出之資料點都處理完畢為止 64 分群法在大型資料集合之設計策略(4)漸進式處理所遭遇麻煩¥順序相依(order-dependence)的問題 65 平衡式反覆化簡和分群法＊＊(1)平衡式反覆化簡和分群法(BIRCH)¥根據使用者所設定之群集涵蓋範圍，例如群集之半徑，先將資料集合中的資料點以漸進式處理方法分配到許多較小、相似度高的子群集¥利用類似聚合式階層分群法的方式，以這些子群集為基本單元，反覆地將其聚合成較大的群集¥處理上其利用群集特徵(Clustering Feature, CF)來表示每個子群集，並不直接處理所有的資料點，在記憶體空間的利用上非常有效率¥為加速將資料點歸屬到所屬之子群集，其將動態構建出一類似B+樹 (B+ tree) 66 平衡式反覆化簡和分群法＊＊(2)67 平衡式反覆化簡和分群法＊＊(3)群集特徵¥是由三個概括性資訊 (summarized information) 所組成，假設一群集Si中包含有N個資料點，則該群集特徵CF被定義為: = 為這些N個點的線性總合，SS = 為N個點的平方和¥群集特徵能充分完整地表示一個群集，因為不論是在決定資料點所歸屬的群集上或是在決定群集合併的順序68 平衡式反覆化簡和分群法＊＊(4)群集特徵¥會員1=<20, 20> 與會員2=<21, 26> 的距離在使用者設定之群集涵蓋範圍內，BIRCH先將其形成一個子群集，則此子群集之群集特徵值將計算如下 == <20+21, 20+26> = <41, 46> SS = = (202+202)+(212+262) = 800+1117 = 1917 CF = (2, <41, 46>, 1917)69 平衡式反覆化簡和分群法＊＊(5)群集特徵樹¥記錄子群集間的親疏遠近的關係每一非終端節點 (non-leaf node)，記錄所有隸屬之子節點 (children) 的概括性資訊每一終端節點 (leaf node)，則記錄所隸屬之子群集之概括性資訊¥一群集特徵樹包含三個參數非終端節點之分支係數(B)：用以指定每個非終端節點所允許包含之最大子節點個數終端節點之分支係數(L)：用以指定每個終端節點所允許包含之最大子群集個數子群集之門檻值(T)：指定子群集所允許之涵蓋範圍，例如：群集半徑 70 平衡式反覆化簡和分群法＊＊(6)群集特徵樹之建立¥資料點加入時，透過類似拜訪B+樹的方式，比對部分的非終端節點，決定資料點所歸屬之終端節點與子群集¥當資料點加入到位於終端節點的一子群集時，若造成該子群集的涵蓋範圍超過T，則產生一新的子群集，並將資料點加入此群集且計算此子群集特徵；否則，直接加入此資料點到子群集中，並更新該子群集之群集特徵¥若因產生新的子群集，造成終端節點之子群集的數量超過所設定之L，則該終端節點將分裂成兩個，並以相差最遠之子群集當作種子(seed)，然後將其他子群集分別歸屬其中；同理，非終端節點進行分裂時，亦相同運作方式¥底層子群集之群集特徵的改變，將影響上層終端節點與非終端節點中的群集特徵，資訊將從從底端傳達到樹根 71 平衡式反覆化簡和分群法＊＊(7)BIRCH的運作過程¥輸入：一資料集合、非終端節點之分支係數B、終端節點之分支係數L 、門檻值T¥輸出：以樹狀結構所表示的群集關係¥步驟 1：掃瞄資料集合中的資料點，建立一可以放在記憶體中執行之群集特徵樹。
如果群集特徵樹無法載入到記憶體，則增加子群集所允許之T ，並由既有之群集特徵資訊，重新建立一群集特徵樹，以符合記憶體需求¥步驟 2：將存在終端節點中包含偏移值的子群集由群集特徵樹中移除，去除偏移值對分群結果的影響¥步驟 3：利用聚合法 (AGNES) 處理群集特徵樹中所包含的子群集(只需處理其群集特徵)，產生最後之分群結果 72 評估分群的結果在大多數的分群結果評估上，，都是利用二維空間來表現，，主要是因為用二維的資料較能夠直接看出分群的結果並進行驗證73 總結(1)群集分析在許多應用領域中被廣泛認為是相當有用的工具，，一般來講通常包含資料的表示、、相似度的計算與測量、、分群法的採用、、評估分群的結果、、群集的解釋等五個工作項目分割式分群法利用反覆重新配置技術，，將資料點歸屬到數個互不交集的群集中，，意圖找出類圓形且大小差不多的分群結果，，但並不適合於任意形狀或群集大小差異大之資料集合階層式分群法利用聚合或分裂的方式，，將相似度高的較小群集合併成較大的群集，，或者將較大的群集進行分離，，利用樹狀結構圖來表示群集間彼此關係在處理任意形狀群集、、群集大小差異大、、偏移值等方面比分割式分群法演算法更有效，，但其處理的時間與空間需求上卻高出許多 74 總結(2)密集度導向的分群法利用資料點間密度的關係來分群，，不但可用來濾除偏移值或雜訊，，且可對任意形狀之群集進行分群，，但是對如何設定適當涵蓋範圍和評估緊密程度卻是一大難題隨著資料維度與資料量越來越龐大，，傳統分群法變得困難而不可行；；隨著時間的過往，，資料集合必須重新再處理以更新群集分析的結果，，這將造成更多時間與空間的花費。
因此除了針對怎麼去解決任意形狀與群集大小差異大等問題外，，如何處理大量資料集合與更新分群結果，，也是主要的發展趨勢 75 。
中级消防设施操作员监控26道线下抽考题.pdf人教精通版（2024）新教材四年级英语上册Unit 4 Lesson 1 教学课件.pptx区域研究与区域规划课件-ppt101页.ppt2024-2025学年初中七年级上学期数学第一次月考卷及答案（北师大版）.pdf指伸屈肌腱断裂.ppt幼儿园月后勤工作总结ppt.pptx共享单车动态定价机制-深度研究.pptx(完整word)混凝土结构设计原理期末试题库及其参考答案.doc中考英语二轮复习专题讲与练： 宾语从句（含详解）.doc主动脉夹层的围手术期护理课件.ppt2020年高考语文学科北京卷《阅卷纵横》.doc国有土地使用权挂牌出让须知.doc
