chapter6群集分析clusteranalysis-資料下載頁
2025-10-15 17:58本頁面
【導讀】相似度的計算與測量。分群法在大型資料集合之設計。群集分析的概念與目的。將資料集合中的資料記錄，又稱為資料點，加。主要的目地是分析資料彼此間的相似程度，藉。在群集分析的過程中，並沒有預先指定好的類。群集分析在資料探勘過程中所扮演的角色。將原本大量的資料加以分群成數(shù)個群集，並從每一個群集中挑。推斷出所關(guān)注資料中可能存在的某些特性或現(xiàn)象。對推斷假設作有效性的驗證。試圖驗證“年輕人通常年收入較低，是否也代表其消費能力較。此假設性推斷時，可以對於“年齡”、“年收入”和。分群結(jié)果應用於未知分類之資料記錄，預測資料所歸屬的群集。線上購物網(wǎng)站的使用者族群與消費能力。幫助使用者自動化分析圖像資料庫所產(chǎn)生的影像資料，將文件加以分門別類，幫助文件資料的管理和使用。群集分析五個主要的循序工作項目。將每一資料點利用有限、一致的資料維度表示。不適切的資料維度將造成分群結(jié)果凌亂、難以從中。有些分群法相當容易受雜訊或偏移值的
【正文】 成數(shù)個可處理的小部分，如果所分解後的小部分問題在處理上仍相當困難，則繼續(xù)將其進一步分解成更小的部分，以此遞迴式處理；最後，將每一小部分問題的處理結(jié)果整合起來，達到解決整個問題的目的 ? 平行處理 ?將整個群集分析過程所要處理的工作，分給多個處理器或機器來共同完成 ?資料集合分割成數(shù)個部分 ?將資料點之資料維度切割成數(shù)個部分 64 分群法在大型資料集合之設計策略 (3) ? 漸進式處理 ?隨著資料點的加入或移除，動態(tài)地更新分群結(jié)果 ?當?shù)谝粋€資料點加入時，此資料點將自成一個群集；接著，對於後續(xù)加入的資料點，根據(jù)使用者設定之準則，例如：依加入之資料點與群集中心的距離是否低於某一門檻值，決定加入已存在之群集或自成一個群集，直到所有的資料點都處理完畢為止 ?以資料點陸續(xù)移出資料集合而言，一開始資料集合中已存在數(shù)個群集，當?shù)谝粋€資料點移出時，根據(jù)使用者設定之準則，對所對應之群集調(diào)整其群集中心或進行群集合併；直到所有欲移出之資料點都處理完畢為止 65 分群法在大型資料集合之設計策略 (4) ? 漸進式處理所遭遇麻煩 ?順序相依 (orderdependence)的問題 YX123 45666 平衡式反覆化簡和分群法 ＊ (1) ? 平衡式反覆化簡和分群法 (BIRCH) ?根據(jù)使用者所設定之群集涵蓋範圍，例如群集之半徑，先將資料集合中的資料點以漸進式處理方法分配到許多較小、相似度高的子群集 ?利用類似聚合式階層分群法的方式，以這些子群集為基本單元，反覆地將其聚合成較大的群集 ?處理上其利用群集特徵 (Clustering Feature, CF)來表示每個子群集，並不直接處理所有的資料點，在記憶體空間的利用上非常有效率 ?為加速將資料點歸屬到所屬之子群集，其將動態(tài)構(gòu)建出一類似 B+樹 (B+ tree) 67 平衡式反覆化簡和分群法 ＊ (2) CF1 C F2 ……… C FBCF11 C F12 … … … C F1BCFB1 C FB2 … … … C FBBCF1 1 1 C F112 … … … C F1 1 L……樹頂非終端節(jié)點終端節(jié)點子群集………… ……………… …… ……68 平衡式反覆化簡和分群法 ＊ (3) ? 群集特徵 ?是由三個概括性資訊 (summarized information) 所組成，假設一群集 Si中包含有 N個資料點，則該群集特徵 CF被定義為 : ? = 為這些 N個點的線性總合， SS = 為 N個點的平方和 ?群集特徵能充分完整地表示一個群集，因為不論是在決定資料點所歸屬的群集上或是在決定群集合併的順序 ? ?, SSLSNCF ?LS ??iSxx? ??iSxx2?69 平衡式反覆化簡和分群法 ＊ (4) ? 群集特徵 ?會員 1=20, 20 與會員 2=21, 26 的距離在使用者設定之群集涵蓋範圍內(nèi)， BIRCH先將其形成一個子群集，則此子群集之群集特徵值將計算如下 ? = = 20+21, 20+26 = 41, 46 ? SS = = (202+202)+(212+262) = 800+1117 = 1917 ? CF = (2, 41, 46, 1917) LS ??iSxx?2ixSx??70 平衡式反覆化簡和分群法 ＊ (5) ? 群集特徵樹 ?記錄子群集間的親疏遠近的關(guān)係 ?每一非終端節(jié)點 (nonleaf node)，記錄所有隸屬之子節(jié)點 (children) 的概括性資訊 ?每一終端節(jié)點 (leaf node)，則記錄所隸屬之子群集之概括性資訊 ?一群集特徵樹包含三個參數(shù) ?非終端節(jié)點之分支係數(shù) (B)：用以指定每個非終端節(jié)點所允許包含之最大子節(jié)點個數(shù) ?終端節(jié)點之分支係數(shù) (L)：用以指定每個終端節(jié)點所允許包含之最大子群集個數(shù) ?子群集之門檻值 (T)：指定子群集所允許之涵蓋範圍，例如：群集半徑 71 平衡式反覆化簡和分群法 ＊ (6) ? 群集特徵樹之建立 ?資料點加入時，透過類似拜訪 B+樹的方式，比對部分的非終端節(jié)點，決定資料點所歸屬之終端節(jié)點與子群集 ?當資料點加入到位於終端節(jié)點的一子群集時，若造成該子群集的涵蓋範圍超過 T，則產(chǎn)生一新的子群集，並將資料點加入此群集且計算此子群集特徵；否則，直接加入此資料點到子群集中，並更新該子群集之群集特徵 ?若因產(chǎn)生新的子群集，造成終端節(jié)點之子群集的數(shù)量超過所設定之 L，則該終端節(jié)點將分裂成兩個，並以相差最遠之子群集當作種子 (seed)，然後將其他子群集分別歸屬其中；同理，非終端節(jié)點進行分裂時，亦相同運作方式 ?底層子群集之群集特徵的改變，將影響上層終端節(jié)點與非終端節(jié)點中的群集特徵，資訊將從從底端傳達到樹根 72 平衡式反覆化簡和分群法 ＊ (7) ? BIRCH的運作過程 ?輸入：一資料集合、非終端節(jié)點之分支係數(shù) B、終端節(jié)點之分支係數(shù) L 、門檻值 T ?輸出：以樹狀結(jié)構(gòu)所表示的群集關(guān)係 ?步驟 1：掃瞄資料集合中的資料點，建立一可以放在記憶體中執(zhí)行之群集特徵樹。如果群集特徵樹無法載入到記憶體，則增加子群集所允許之 T ，並由既有之群集特徵資訊，重新建立一群集特徵樹，以符合記憶體需求 ?步驟 2：將存在終端節(jié)點中包含偏移值的子群集由群集特徵樹中移除，去除偏移值對分群結(jié)果的影響 ?步驟 3：利用聚合法 (AGNES) 處理群集特徵樹中所包含的子群集 (只需處理其群集特徵 )，產(chǎn)生最後之分群結(jié)果 73 評估分群的結(jié)果 ? 在大多數(shù)的分群結(jié)果評估上，都是利用二維空間來表現(xiàn)，主要是因為用二維的資料較能夠直接看出分群的結(jié)果並進行驗證 年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)( a )年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)( b)74 總結(jié) (1) ? 群集分析在許多應用領域中被廣泛認為是相當有用的工具，一般來講通常包含 資料的表示 、 相似度的計算與測量 、 分群法的採用 、 評估分群的結(jié)果 、 群集的解釋 等五個工作項目 ? 分割式分群法利用反覆重新配置技術(shù) ，將資料點歸屬到數(shù)個互不交集的群集中， 意圖找出類圓形且大小差不多的分群結(jié)果 ，但並 不適合 於 任意形狀 或 群集大小差異大之資料集合 ? 階層式分群法利用聚合或分裂的方式 ，將相似度高的較小群集合併成較大的群集，或者將較大的群集進行分離，利用樹狀結(jié)構(gòu)圖來表示群集間彼此關(guān)係 。在處理任意形狀群集、群集大小差異大、偏移值等方面比分割式分群法演算法更有效，但其處理的時間與空間需求上卻高出許多 75 總結(jié) (2) ? 密集度導向的分群法利用資料點間密度的關(guān)係來分群 ，不但可用來濾除偏移值或雜訊，且可對任意形狀之群集進行分群，但是對如何設定適當涵蓋範圍和評估緊密程度卻是一大難題 ? 隨著資料維度與資料量越來越龐大，傳統(tǒng)分群法變得困難而不可行；隨著時間的過往，資料集合必頇重新再處理以更新群集分析的結(jié)果，這將造成更多時間與空間的花費。因此除了針對怎麼去解決任意形狀與群集大小差異大等問題外，如何處理大量資料集合與更新分群結(jié)果，也是主要的發(fā)展趨勢
教學課件相關(guān)推薦
鄂ICP備17016276號-1