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