【正文】 ?, 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) ? 群集特徵樹(shù) ?記錄子群集間的親疏遠(yuǎn)近的關(guān)係 ?每一非終端節(jié)點(diǎn) (nonleaf node)，記錄所有隸屬之子節(jié)點(diǎn) (children) 的概括性資訊 ?每一終端節(jié)點(diǎn) (leaf node)，則記錄所隸屬之子群集之概括性資訊 ?一群集特徵樹(shù)包含三個(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ù) ?子群集之門(mén)檻值 (T)：指定子群集所允許之涵蓋範(fàn)圍，例如：群集半徑 71 平衡式反覆化簡(jiǎn)和分群法 ＊ (6) ? 群集特徵樹(shù)之建立 ?資料點(diǎn)加入時(shí)，透過(guò)類(lèi)似拜訪(fǎng) B+樹(shù)的方式，比對(duì)部分的非終端節(jié)點(diǎn)，決定資料點(diǎn)所歸屬之終端節(jié)點(diǎn)與子群集 ?當(dāng)資料點(diǎn)加入到位於終端節(jié)點(diǎn)的一子群集時(shí)，若造成該子群集的涵蓋範(fàn)圍超過(guò) T，則產(chǎn)生一新的子群集，並將資料點(diǎn)加入此群集且計(jì)算此子群集特徵；否則，直接加入此資料點(diǎn)到子群集中，並更新該子群集之群集特徵 ?若因產(chǎn)生新的子群集，造成終端節(jié)點(diǎn)之子群集的數(shù)量超過(guò)所設(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á)到樹(shù)根 72 平衡式反覆化簡(jiǎn)和分群法 ＊ (7) ? BIRCH的運(yùn)作過(guò)程 ?輸入：一資料集合、非終端節(jié)點(diǎn)之分支係數(shù) B、終端節(jié)點(diǎn)之分支係數(shù) L 、門(mén)檻值 T ?輸出：以樹(shù)狀結(jié)構(gòu)所表示的群集關(guān)係 ?步驟 1：掃瞄資料集合中的資料點(diǎn)，建立一可以放在記憶體中執(zhí)行之群集特徵樹(shù)。重複執(zhí)行步驟 2，直到所有的資料點(diǎn)都?xì)w屬到同一群集或滿(mǎn)足使用者所設(shè)定之終止條件為止 45 階層式分群法 (5) 年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)( b) ( c )( a )46 階層式分群法 (6) 年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)年齡與平均月收入散佈圖010203040500 10 20 30 40 50 60年齡平均月收入(千)( d) ( e )( f ) ( g )47 階層式分群法 (7) 會(huì)員 1 會(huì)員 2 會(huì)員 3 會(huì)員 4 會(huì)員 5 會(huì)員 6 會(huì)員 7會(huì)員 1 0 7 7 31 35 52 53會(huì)員 2 0 2 24 28 45 46會(huì)員 3 0 24 28 45 46會(huì)員 4 0 4 21 22會(huì)員 5 0 17 18會(huì)員 6 0 5會(huì)員 7 0會(huì)員 1 會(huì)員 2 會(huì)員 3 會(huì)員 4 會(huì)員 5 會(huì)員 6 會(huì)員 7回合三: t2=4回合二: t1=2回合四: t3=5回合五: t4=7回合六: t5=17回合七: t6=24回合一: t0=048 階層式分群法 (8) ? 傳統(tǒng)階層式分群法的不足 ?dmean、 dmax和 davg此三種群集相似度計(jì)算公式，可能產(chǎn)生以下分群結(jié)果 49 階層式分群法 (9) ? 傳統(tǒng)階層式分群法的不足 ?dmin此群集相似度計(jì)算公式，可能產(chǎn)生以下分群結(jié)果 50 階層式分群法 (10) ? 多代表點(diǎn)分群法 (CURE) ?相對(duì)於傳統(tǒng)階層式分群法透過(guò)單點(diǎn)考量 (例如： dmean) 或所有點(diǎn)考量 (例如： dmin)來(lái)決定是否合併群集，多代表點(diǎn)分群法選擇 用一定數(shù)量且分散得當(dāng)?shù)亩鄠€(gè)代表性的資料點(diǎn)來(lái)表示一個(gè)群集 ，並配合 dmin來(lái)衡量是否合併兩個(gè)群集 ?所選擇的代表性資料點(diǎn)可藉著事先定義好、介於 0和 1之間的收縮係數(shù) (shrinking factor)，以群集中心為基點(diǎn)做適當(dāng)?shù)厥湛s (shrinking)，以防止因?yàn)槠浦翟斐扇杭行牡钠疲_(dá)到充分表示整個(gè)群集的效果 ?兼容了單點(diǎn)考量與所有點(diǎn)考量的優(yōu)點(diǎn) ，對(duì)偏移值的處理上也較不敏感 51 階層式分群法 (10) ? 多代表點(diǎn)分群法的運(yùn)作過(guò)程 ?輸入：一資料集合、代表性資料點(diǎn)數(shù)量 c、收縮係數(shù) ?。, ppdm i nCCdji CpCpjim i n?? ??? ? )(, jijim e a n mmdCCd ??? ? ? ?? ? ??i jCp Cpjijia v gppdnnCCd 39。(, 39。如果群集特徵樹(shù)無(wú)法載入到記憶體，則增加子群集所允許之 T ，並由既有之群集特徵資訊，重新建立一群集特徵樹(shù)，以符合記憶體需求 ?步驟 2：將存在終端節(jié)點(diǎn)中包含偏移值的子群集由群集特徵樹(shù)中移除，去除偏移值對(duì)分群結(jié)果的影響 ?步驟 3：利用聚合法 (AGNES) 處理群集特徵樹(shù)中所包含的子群集 (只需處理其群集特徵 )，產(chǎn)生最後之分群結(jié)果 73 評(píng)估分群的結(jié)果 ? 在大多數(shù)的分群結(jié)果評(píng)估上，都是利用二維空間來(lái)表現(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)有用的工具，一般來(lái)講通常包含 資料的表示 、 相似度的計(jì)算與測(cè)量 、 分群法的採(cǎi)用 、 評(píng)估分群的結(jié)果 、 群集的解釋 等五個(gè)工作項(xiàng)目 ? 分割式分群法利用反覆重新配置技術(shù) ，將資料點(diǎn)歸屬到數(shù)個(gè)互不交集的群集中， 意圖找出類(lèi)圓形且大小差不多的分群結(jié)果 ，但並 不適合 於 任意形狀 或 群集大小差異大之資料集合 ? 階層式分群法利用聚合或分裂的方式 ，將相似度高的較小群集合併成較大的群集，或者將較大的群集進(jìn)行分離，利用樹(shù)狀結(jié)構(gòu)圖來(lái)表示群集間彼此關(guān)係 。 ?步驟 2：利用 相似度計(jì)算