【正文】 在處理任意形狀群集、群集大小差異大、偏移值等方面比分割式分群法演算法更有效，但其處理的時(shí)間與空間需求上卻高出許多 75 總結(jié) (2) ? 密集度導(dǎo)向的分群法利用資料點(diǎn)間密度的關(guān)係來(lái)分群 ，不但可用來(lái)濾除偏移值或雜訊，且可對(duì)任意形狀之群集進(jìn)行分群，但是對(duì)如何設(shè)定適當(dāng)涵蓋範(fàn)圍和評(píng)估緊密程度卻是一大難題 ? 隨著資料維度與資料量越來(lái)越龐大，傳統(tǒng)分群法變得困難而不可行；隨著時(shí)間的過(guò)往，資料集合必頇重新再處理以更新群集分析的結(jié)果，這將造成更多時(shí)間與空間的花費(fèi)。重複執(zhí)行步驟 2，直到所有的資料點(diǎn)都?xì)w屬到同一群集或滿足使用者所設(shè)定之終止條件為止 52 階層式分群法 (11) ? 代表性資料點(diǎn)數(shù)量 c = 3 53 ? 階層式分群法 (hierarchical method) ? 密集度為導(dǎo)向的分群法 (densitybased algorithm) 54 密集度導(dǎo)向分群法 ＊ (1) ? 概念 ?利用資料點(diǎn)間密度 (density)的關(guān)係來(lái)分群 ?將資料集合中較密集的資料視為一個(gè)群集；運(yùn)用密集度的方法不但可用來(lái)濾除偏移值或雜訊，且可對(duì)任意形狀之群集進(jìn)行分群 55 密集度導(dǎo)向分群法 ＊ (2) ? 高密度關(guān)連區(qū)域分群法 (DBSCAN) ?不斷地評(píng)估一個(gè)資料點(diǎn)的鄰近資料點(diǎn)是否夠密集，若周遭資料點(diǎn)分佈的密度夠大，就擴(kuò)大群集邊界 ?利用 Eps和 Minpts二個(gè)參數(shù)，來(lái)計(jì)算距離此資料點(diǎn) Eps距離以內(nèi)的資料點(diǎn)數(shù)量是否大於 Minpts 56 密集度導(dǎo)向分群法 ＊ (3) ? DBSCAN之相關(guān)定義 ?距離資料點(diǎn)半徑長(zhǎng)度 Eps以內(nèi)的鄰近區(qū)域，則為該資料點(diǎn)的 Eps鄰近區(qū)域 ?資料點(diǎn)的 Eps鄰近區(qū)域中包含了至少 Minpts個(gè)資料點(diǎn)，則該資料點(diǎn)為 核心物件 ?資料點(diǎn) p的位置是在某核心物件 q的 Eps鄰近區(qū)域內(nèi)，則資料點(diǎn) p可被稱為 “ 可由 q直接密度可達(dá) (directly densityreachable)” 的物件 ?假如資料點(diǎn) p可由 q1直接密度可達(dá)、而 q1可由 q2直接密度可達(dá)、 …… 、而 qi1是可由 qi直接密度可達(dá)，則資料點(diǎn) p可以被稱為 “ 可由 qi密度可達(dá) (densityreachable)” 的物件 ?假如資料點(diǎn) p和 q都可由 o密度可達(dá)，則 p和 q可以被稱為 “ 密度連接 (densityconnected)” 57 密集度導(dǎo)向分群法 ＊ (4) 58 密集度導(dǎo)向分群法 ＊ (5) ? DBSCAN對(duì)於群集和偏移值的定義 ?對(duì)資料點(diǎn) p和 q而言，假如 q歸屬於群集 A，且 p可由 q密度可達(dá)，則 p也將歸屬於群集 A；對(duì)於歸屬於相同群集 A的 p和 q而言， p和 q必為密度連接 ?對(duì)無(wú)法歸屬到任何群集之資料點(diǎn)，將被視為雜訊、偏移值 59 密集度導(dǎo)向分群法 ＊ (6) ? DBSCAN的運(yùn)作過(guò)程 ?輸入：一資料集合、鄰近區(qū)域 Eps、資料點(diǎn)數(shù)量門(mén)檻值Minpts ?輸出：互不交集之所有群集 ?步驟 1：檢查資料集合中每個(gè)資料點(diǎn)是否為核心物件，並以所找到之核心物件為群集中心，結(jié)合其 Eps鄰近區(qū)域中的所有資料點(diǎn)，形成初步之群集 ?步驟 2：選擇任一核心物件，往外尋找可由此核心物件密度可達(dá)的資料點(diǎn)，假如發(fā)現(xiàn)會(huì)擴(kuò)張到某個(gè)已有所屬群集的核心物件，則該群集將被合併，變成一個(gè)較大之群集；否則重新啟動(dòng)步驟 2，選擇其他未被合併或處理過(guò)之核心物件，繼續(xù)執(zhí)行 ?步驟 3：當(dāng)所有核心物件都處理過(guò)為止 60 密集度導(dǎo)向分群法 ＊ (7) 61 分群法在大型資料集合之設(shè)計(jì) ? 動(dòng)機(jī)與需求 ?隨著資料維度與資料量越來(lái)越龐大，傳統(tǒng)分群法由於需處理每一資料點(diǎn)，並需要將整個(gè)資料集合載入到記憶體中做群集分析，變得困難而不可行 ?當(dāng)資料集合不斷有新的資料記錄加入，老舊的資料記錄也將移出並歸檔，如果資料集合必頇重新再處理以更新群集分析的結(jié)果，這將造成更多時(shí)間與空間的花費(fèi) ?除了針對(duì)任意形狀與群集大小差異大等問(wèn)題外，如何處理大量資料集合與動(dòng)態(tài)更新群集分析結(jié)果，也是目前發(fā)展的主要趨勢(shì) 62 分群法在大型資料集合之設(shè)計(jì)策略 (1) ? 抽樣處理 ?由資料集合中抽取部分的樣本來(lái)代表整個(gè)資料集合母體 ? 概括處理 ?將相似度高的資料點(diǎn)先行聚集成基本單元，只對(duì)基本單元進(jìn)行群集分析，而不直接處理底層的資料點(diǎn) ? 相似度很高的資料點(diǎn)，只利用其中一個(gè)資料點(diǎn)來(lái)代表 ? 將資料集合中的資料點(diǎn)分配到許多較小、相似度高的子群集，並以子群集的群集中心來(lái)代表此群集 ? 將表示整個(gè)資料集合的空間區(qū)域切割成數(shù)個(gè)單元矩形，利用統(tǒng)計(jì)資訊，例如平均值、資料點(diǎn)統(tǒng)計(jì)分佈，來(lái)表示每一個(gè)小矩形 63 分群法在大型資料集合之設(shè)計(jì)策略 (2) ? 各個(gè)擊破遞迴式處理 ?將一個(gè)大問(wèn)題分解成數(shù)個(gè)可處理的小部分，如果所分解後的小部分問(wèn)題在處理上仍相當(dāng)困難，則繼續(xù)將其進(jìn)一步分解成更小的部分，以此遞迴式處理；最後，將每一小部分問(wèn)題的處理結(jié)果整合起來(lái)，達(dá)到解決整個(gè)問(wèn)題的目的 ? 平行處理 ?將整個(gè)群集分析過(guò)程所要處理的工作，分給多個(gè)處理器或機(jī)器來(lái)共同完成 ?資料集合分割成數(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)與群集中心的距離是否低於某一門(mén)檻值，決定加入已存在之群集或自成一個(gè)群集，直到所有的資料點(diǎn)都處理完畢為止 ?以資料點(diǎn)陸續(xù)移出資料集合而言，一開(kāi)始資料集合中已存在數(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)的問(wèn)題 YX123 45666 平衡式反覆化簡(jiǎn)和分群法 ＊ (1) ? 平衡式反覆化簡(jiǎn)和分群法 (BIRCH) ?根據(jù)使用者所設(shè)定之群集涵蓋範(fàn)圍，例如群集之半徑，先將資料集合中的資料點(diǎn)以漸進(jìn)式處理方法分配到許多較小、相似度高的子群集 ?利用類似聚合式階層分群法的方式，以這些子群集為基本單元，反覆地將其聚合成較大的群集 ?處理上其利用群集特徵 (Clustering Feature, CF)來(lái)表示每個(gè)子群集，並不直接處理所有的資料點(diǎn)，在記憶體空間的利用上非常有效率 ?為加速將資料點(diǎn)歸屬到所屬之子群集，其將動(dòng)態(tài)構(gòu)建出一類似 B+樹(shù) (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……樹(shù)頂非終端節(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 =