層次聚類(lèi)分析-超精彩.ppt

《層次聚類(lèi)分析-超精彩.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《層次聚類(lèi)分析-超精彩.ppt（51頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

層次聚類(lèi)方法 戴奇 Page 2 主要內(nèi)容 凝聚和分裂層次聚類(lèi) 01 BIRCH 利用層次方法的平衡迭代歸約和聚類(lèi) 02 Chameleon 利用動(dòng)態(tài)建模的層次聚類(lèi)算法 05 ROCK 分類(lèi)屬性的層次聚類(lèi)算法 03 CURE 基于質(zhì)心和基于代表對(duì)象方法之間的中間策略 04 Page 3 概要 層次聚類(lèi)方法將數(shù)據(jù)對(duì)象組成一棵聚類(lèi)樹(shù) 根據(jù)層次分解是以自底向上 合并 還是自頂向下 分裂 方式 層次聚類(lèi)方法可以進(jìn)一步分為凝聚的和分裂的 一種純粹的層次聚類(lèi)方法的質(zhì)量受限于 一旦合并或分裂執(zhí)行 就不能修正 也就是說(shuō) 如果某個(gè)合并或分裂決策在后來(lái)證明是不好的選擇 該方法無(wú)法退回并更正 Page 4 主要內(nèi)容 凝聚和分裂層次聚類(lèi) 01 BIRCH 利用層次方法的平衡迭代歸約和聚類(lèi) 02 Chameleon 利用動(dòng)態(tài)建模的層次聚類(lèi)算法 05 ROCK 分類(lèi)屬性的層次聚類(lèi)算法 03 CURE 基于質(zhì)心和基于代表對(duì)象方法之間的中間策略 04 Page 5 層次聚類(lèi)方法 一般來(lái)說(shuō) 有兩種類(lèi)型的層次聚類(lèi)方法 凝聚層次聚類(lèi) 采用自底向上策略 首先將每個(gè)對(duì)象作為單獨(dú)的一個(gè)原子簇 然后合并這些原子簇形成越來(lái)越大的簇 直到所有的對(duì)象都在一個(gè)簇中 層次的最上層 或者達(dá)到一個(gè)終止條件 絕大多數(shù)層次聚類(lèi)方法屬于這一類(lèi) 分裂層次聚類(lèi) 采用自頂向下策略 首先將所有對(duì)象置于一個(gè)簇中 然后逐漸細(xì)分為越來(lái)越小的簇 直到每個(gè)對(duì)象自成一個(gè)簇 或者達(dá)到某個(gè)終止條件 例如達(dá)到了某個(gè)希望的簇的數(shù)目 或者兩個(gè)最近的簇之間的距離超過(guò)了某個(gè)閾值 Page 6 例子 下圖描述了一種凝聚層次聚類(lèi)算法AGNES和一種分裂層次聚類(lèi)算法DIANA對(duì)一個(gè)包含五個(gè)對(duì)象的數(shù)據(jù)集合 a b c d e 的處理過(guò)程 圖1對(duì)數(shù)據(jù)對(duì)象 a b c d e 的凝聚和分裂層次聚類(lèi) Page 7 初始 AGNES將每個(gè)對(duì)象自為一簇 然后這些簇根據(jù)某種準(zhǔn)則逐步合并 直到所有的對(duì)象最終合并形成一個(gè)簇 例如 如果簇C1中的一個(gè)對(duì)象和簇C2中的一個(gè)對(duì)象之間的距離是所有屬于不同簇的對(duì)象間歐氏距離中最小的 則C1和C2合并 在DIANA中 所有的對(duì)象用于形成一個(gè)初始簇 根據(jù)某種原則 如 簇中最近的相鄰對(duì)象的最大歐氏距離 將該簇分裂 簇的分裂過(guò)程反復(fù)進(jìn)行 直到最終每個(gè)新簇只包含一個(gè)對(duì)象 在凝聚或者分裂層次聚類(lèi)方法中 用戶可以定義希望得到的簇?cái)?shù)目作為一個(gè)終止條件 Page 8 樹(shù)狀圖 通常 使用一種稱作樹(shù)狀圖的樹(shù)形結(jié)構(gòu)表示層次聚類(lèi)的過(guò)程 它展示出對(duì)象是如何一步步分組的 圖2顯示圖1的五個(gè)對(duì)象的樹(shù)狀圖 圖2數(shù)據(jù)對(duì)象 a b c d e 層次聚類(lèi)的樹(shù)狀圖表示 Page 9 簇間距離 四個(gè)廣泛采用的簇間距離度量方法如下 其中 p p 是兩個(gè)對(duì)象或點(diǎn)p和p 之間的距離 mi是簇Ci的均值 而ni是簇Ci中對(duì)象的數(shù)目 最小距離 最大距離 均值距離 平均距離 Page 10 最小距離 最大距離 均值距離 平均距離 Page 11 當(dāng)算法使用最小距離衡量簇間距離時(shí) 有時(shí)稱它為最近鄰聚類(lèi)算法 此外 如果當(dāng)最近的簇之間的距離超過(guò)某個(gè)任意的閾值時(shí)聚類(lèi)過(guò)程就會(huì)終止 則稱其為單連接算法 當(dāng)一個(gè)算法使用最大距離度量簇間距離時(shí) 有時(shí)稱為最遠(yuǎn)鄰聚類(lèi)算法 如果當(dāng)最近簇之間的最大距離超過(guò)某個(gè)任意閾值時(shí)聚類(lèi)過(guò)程便終止 則稱其為全連接算法 Page 12 單連接算法例子 先將五個(gè)樣本都分別看成是一個(gè)簇 最靠近的兩個(gè)簇是3和4 因?yàn)樗麄兙哂凶钚〉拇亻g距離D 3 4 5 0 第一步 合并簇3和4 得到新簇集合1 2 34 5 Page 13 更新距離矩陣 D 1 34 min D 1 3 D 1 4 min 20 6 22 4 20 6D 2 34 min D 2 3 D 2 4 min 14 1 11 2 11 2D 5 34 min D 3 5 D 4 5 min 25 0 25 5 25 0原有簇1 2 5間的距離不變 修改后的距離矩陣如圖所示 在四個(gè)簇1 2 34 5中 最靠近的兩個(gè)簇是1和5 它們具有最小簇間距離D 1 5 7 07 Page 14 Page 15 Page 16 最小和最大度量代表了簇間距離度量的兩個(gè)極端 它們趨向?qū)﹄x群點(diǎn)或噪聲數(shù)據(jù)過(guò)分敏感 使用均值距離和平均距離是對(duì)最小和最大距離之間的一種折中方法 而且可以克服離群點(diǎn)敏感性問(wèn)題 盡管均值距離計(jì)算簡(jiǎn)單 但是平均距離也有它的優(yōu)勢(shì) 因?yàn)樗饶芴幚頂?shù)值數(shù)據(jù)又能處理分類(lèi)數(shù)據(jù) Page 17 層次聚類(lèi)方法的困難之處 層次聚類(lèi)方法盡管簡(jiǎn)單 但經(jīng)常會(huì)遇到合并或分裂點(diǎn)選擇的困難 這樣的決定是非常關(guān)鍵的 因?yàn)橐坏┮唤M對(duì)象合并或者分裂 下一步的處理將對(duì)新生成的簇進(jìn)行 不具有很好的可伸縮性 因?yàn)楹喜⒒蚍至训臎Q定需要檢查和估算大量的對(duì)象或簇 Page 18 層次聚類(lèi)的改進(jìn) 一個(gè)有希望的方向是集成層次聚類(lèi)和其他的聚類(lèi)技術(shù) 形成多階段聚類(lèi) 在下面的內(nèi)容中會(huì)介紹四種這類(lèi)的方法 BIRCH 首先用樹(shù)結(jié)構(gòu)對(duì)對(duì)象進(jìn)行層次劃分 其中葉節(jié)點(diǎn)或者是低層次的非葉節(jié)點(diǎn)可以看作是由分辨率決定的 微簇 然后使用其他的聚類(lèi)算法對(duì)這些微簇進(jìn)行宏聚類(lèi) ROCK基于簇間的互聯(lián)性進(jìn)行合并 CURE選擇基于質(zhì)心和基于代表對(duì)象方法之間的中間策略 Chameleon探查層次聚類(lèi)的動(dòng)態(tài)建模 Page 19 主要內(nèi)容 凝聚和分裂層次聚類(lèi) 01 BIRCH 利用層次方法的平衡迭代歸約和聚類(lèi) 02 Chameleon 利用動(dòng)態(tài)建模的層次聚類(lèi)算法 05 ROCK 分類(lèi)屬性的層次聚類(lèi)算法 03 CURE 基于質(zhì)心和基于代表對(duì)象方法之間的中間策略 04 Page 20 BIRCH方法通過(guò)集成層次聚類(lèi)和其他聚類(lèi)算法來(lái)對(duì)大量數(shù)值數(shù)據(jù)進(jìn)行聚類(lèi) 其中層次聚類(lèi)用于初始的微聚類(lèi)階段 而其他方法如迭代劃分 在后來(lái)的宏聚類(lèi)階段 它克服了凝聚聚類(lèi)方法所面臨的兩個(gè)困難 可伸縮性 不能撤銷(xiāo)前一步所做的工作 BIRCH使用聚類(lèi)特征來(lái)概括一個(gè)簇 使用聚類(lèi)特征樹(shù) CF樹(shù) 來(lái)表示聚類(lèi)的層次結(jié)構(gòu) 這些結(jié)構(gòu)幫助聚類(lèi)方法在大型數(shù)據(jù)庫(kù)中取得好的速度和伸縮性 還使得BIRCH方法對(duì)新對(duì)象增量和動(dòng)態(tài)聚類(lèi)也非常有效 Page 21 聚類(lèi)特征 CF 考慮一個(gè)n個(gè)d維的數(shù)據(jù)對(duì)象或點(diǎn)的簇 簇的聚類(lèi)特征是一個(gè)3維向量 匯總了對(duì)象簇的信息 定義如下CF 其中 n是簇中點(diǎn)的數(shù)目 LS是n個(gè)點(diǎn)的線性和 即 SS是數(shù)據(jù)點(diǎn)的平方和 即 聚類(lèi)特征本質(zhì)上是給定簇的統(tǒng)計(jì)匯總 從統(tǒng)計(jì)學(xué)的觀點(diǎn)來(lái)看 它是簇的零階矩 一階矩和二階矩 Page 22 使用聚類(lèi)特征 我們可以很容易地推導(dǎo)出簇的許多有用的統(tǒng)計(jì)量 例如 簇的形心x0 半徑R和直徑D分別是 其中R是成員對(duì)象到形心的平均距離 D是簇中逐對(duì)對(duì)象的平均距離 R和D都反映了形心周?chē)氐木o湊程度 Page 23 使用聚類(lèi)特征概括簇可以避免存儲(chǔ)個(gè)體對(duì)象或點(diǎn)的詳細(xì)信息 我們只需要固定大小的空間來(lái)存放聚類(lèi)特征 這是空間中BIRCH有效性的關(guān)鍵 聚類(lèi)特征是可加的 也就是說(shuō) 對(duì)于兩個(gè)不相交的簇C1和C2 其聚類(lèi)特征分別為CF1 和CF2 合并C1和C2后的簇的聚類(lèi)特征是CF1 CF2 Page 24 例子 假定在簇C1中有三個(gè)點(diǎn) 2 5 3 2 和 4 3 C1的聚類(lèi)特征是 CF1 假定C1和第2個(gè)簇C2是不相交的 其中CF2 C1和C2合并形成一個(gè)新的簇C3 其聚類(lèi)特征便是CF1和CF2之和 即 CF3 Page 25 CF樹(shù) CF樹(shù)是一棵高度平衡的樹(shù) 它存儲(chǔ)了層次聚類(lèi)的聚類(lèi)特征 圖3給出了一個(gè)例子 根據(jù)定義 樹(shù)中的非葉節(jié)點(diǎn)有后代或 子女 非葉節(jié)點(diǎn)存儲(chǔ)了其子女的CF的總和 因而匯總了關(guān)于其子女的聚類(lèi)信息 CF樹(shù)有兩個(gè)參數(shù) 分支因子B和閾值T 分支因子定義了每個(gè)非葉節(jié)點(diǎn)子女的最大數(shù)目 而閾值參數(shù)給出了存儲(chǔ)在樹(shù)的葉節(jié)點(diǎn)中的子簇的最大直徑 這兩個(gè)參數(shù)影響結(jié)果數(shù)的大小 Page 26 圖3CF樹(shù)結(jié)構(gòu) Page 27 BIRCH試圖利用可用的資源生成最好的簇 給定有限的主存 一個(gè)重要的考慮是最小化I O所需時(shí)間 BIRCH采用了一種多階段聚類(lèi)技術(shù) 數(shù)據(jù)集的單遍掃描產(chǎn)生一個(gè)基本的好聚類(lèi) 一或多遍的額外掃描可以用來(lái)進(jìn)一步 優(yōu)化 改進(jìn)聚類(lèi)質(zhì)量 它主要包括兩個(gè)階段 階段一 BIRCH掃描數(shù)據(jù)庫(kù) 建立一棵存放于內(nèi)存的初始CF樹(shù) 它可以看作數(shù)據(jù)的多層壓縮 試圖保留數(shù)據(jù)的內(nèi)在的聚類(lèi)結(jié)構(gòu) 階段二 BIRCH采用某個(gè) 選定的 聚類(lèi)算法對(duì)CF樹(shù)的葉節(jié)點(diǎn)進(jìn)行聚類(lèi) 把稀疏的簇當(dāng)作離群點(diǎn)刪除 而把稠密的簇合并為更大的簇 Page 28 CF樹(shù)的構(gòu)造 在階段一中 隨著對(duì)象被插入 CF樹(shù)被動(dòng)態(tài)地構(gòu)造 這樣 該方法支持增量聚類(lèi) 一個(gè)對(duì)象被插入到最近的葉條目 子簇 如果在插入后 存儲(chǔ)在葉節(jié)點(diǎn)中的子簇的直徑大于閾值 則該葉節(jié)點(diǎn)和可能的其他節(jié)點(diǎn)被分裂 新對(duì)象插入后 關(guān)于該對(duì)象的信息向樹(shù)根節(jié)點(diǎn)傳遞 通過(guò)修改閾值 CF樹(shù)的大小可以改變 如果存儲(chǔ)CF樹(shù)需要的內(nèi)存大于主存的大小 可以定義較大的閾值 并重建CF樹(shù) Page 29 在CF樹(shù)重建過(guò)程中 通過(guò)利用老樹(shù)的葉節(jié)點(diǎn)來(lái)重新構(gòu)建一棵新樹(shù) 因而樹(shù)的重建過(guò)程不需要訪問(wèn)所有點(diǎn) 即構(gòu)建CF樹(shù)只需訪問(wèn)數(shù)據(jù)一次就行 可以在階段二使用任意聚類(lèi)算法 例如典型的劃分方法 Page 30 BIRCH的有效性 該算法的計(jì)算復(fù)雜度是O n 其中n是聚類(lèi)的對(duì)象的數(shù)目 實(shí)驗(yàn)表明該算法關(guān)于對(duì)象數(shù)目是線性可伸縮的 并且具有較好的數(shù)據(jù)聚類(lèi)質(zhì)量 然而 既然CF樹(shù)的每個(gè)節(jié)點(diǎn)由于大小限制只能包含有限數(shù)目的條目 一個(gè)CF樹(shù)節(jié)點(diǎn)并不總是對(duì)應(yīng)于用戶所考慮的一個(gè)自然簇 此外 如果簇不是球形的 BIRCH不能很好地工作 因?yàn)樗褂冒霃交蛑睆降母拍顏?lái)控制簇的邊界 Page 31 主要內(nèi)容 凝聚和分裂層次聚類(lèi) 01 BIRCH 利用層次方法的平衡迭代歸約和聚類(lèi) 02 Chameleon 利用動(dòng)態(tài)建模的層次聚類(lèi)算法 05 ROCK 分類(lèi)屬性的層次聚類(lèi)算法 03 CURE 基于質(zhì)心和基于代表對(duì)象方法之間的中間策略 04 Page 32 對(duì)于聚類(lèi)包含布爾或分類(lèi)屬性的數(shù)據(jù) 傳統(tǒng)聚類(lèi)算法使用距離函數(shù) 然而 實(shí)驗(yàn)表明對(duì)分類(lèi)數(shù)據(jù)聚類(lèi)時(shí) 這些距離度量不能產(chǎn)生高質(zhì)量的簇 此外 大多數(shù)聚類(lèi)算法在進(jìn)行聚類(lèi)時(shí)只估計(jì)點(diǎn)與點(diǎn)之間的相似度 也就是說(shuō) 在每一步中那些最相似的點(diǎn)合并到一個(gè)簇中 這種 局部 方法很容易導(dǎo)致錯(cuò)誤 Page 33 ROCK是一種層次聚類(lèi)算法 針對(duì)具有分類(lèi)屬性的數(shù)據(jù)使用了鏈接 指兩個(gè)對(duì)象間共同的近鄰數(shù)目 這一概念 ROCK采用一種比較全局的觀點(diǎn) 通過(guò)考慮成對(duì)點(diǎn)的鄰域情況進(jìn)行聚類(lèi) 如果兩個(gè)相似的點(diǎn)同時(shí)具有相似的鄰域 那么這兩個(gè)點(diǎn)可能屬于同一個(gè)簇而合并 Page 34 兩個(gè)點(diǎn)pi和pj是近鄰 如果其中sim是相似度函數(shù) sim可以選擇為距離度量 甚至可以選擇為非度量 非度量被規(guī)范化 使其值落在0和1之間 值越大表明兩個(gè)點(diǎn)越相似 是用戶指定的閾值 pi和pj之間的鏈接數(shù)定義為這兩點(diǎn)的共同近鄰個(gè)數(shù) 如果兩個(gè)點(diǎn)的鏈接數(shù)很大 則他們很可能屬于相同的簇 由于在確定點(diǎn)對(duì)之間的關(guān)系時(shí)考慮鄰近的數(shù)據(jù)點(diǎn) ROCK比起只關(guān)注點(diǎn)間相似度的標(biāo)準(zhǔn)聚類(lèi)方法就顯得更加魯棒 Page 35 包含分類(lèi)屬性數(shù)據(jù)的一個(gè)很好的例子就是購(gòu)物籃數(shù)據(jù) 這種數(shù)據(jù)由事務(wù)數(shù)據(jù)庫(kù)組成 其中每個(gè)事務(wù)都是商品的集合事務(wù)看作具有布爾屬性的記錄 每個(gè)屬性對(duì)應(yīng)于一個(gè)單獨(dú)的商品 如面包或奶酪 如果一個(gè)事務(wù)包含某個(gè)商品 那么該事務(wù)的記錄中對(duì)應(yīng)于此商品的屬性值就為真 否則為假 其他含有分類(lèi)屬性的數(shù)據(jù)集可以用類(lèi)似的方式處理 ROCK中近鄰和鏈接的概念將在下面的例子中闡述 其中兩個(gè) 點(diǎn) 即兩個(gè)事務(wù)Ti和Tj之間的相似度用Jaccard系數(shù)定義為 Page 36 例子 假定一個(gè)購(gòu)物籃數(shù)據(jù)庫(kù)包含關(guān)于商品a b g的事務(wù)記錄 考慮這些事務(wù)的兩個(gè)簇C1和C2 C1涉及商品 a b c d e 包含事務(wù) a b c a b d a b e a c d a c e a d e b c d b c e b d e c d e C2涉及商品 a b f g 包含事務(wù) a b f a b g a f g b f g 假設(shè)我們首先只考慮點(diǎn)間的相似度而忽略鄰域信息 C1中事務(wù) a b c 和 b d e 之間的Jaccard系數(shù)為1 5 0 2 事實(shí)上 C1中任意一對(duì)事務(wù)之間的Jaccard系數(shù)都在0 2和0 5之間 而屬于不同簇的兩個(gè)事務(wù)之間的Jaccard系數(shù)也可能達(dá)到0 5 很明顯 僅僅使用Jaccard系數(shù)本身 無(wú)法得到所期望的簇 Page 37 另一方面 ROCK基于鏈接的方法可以成功地把這些事務(wù)劃分到恰當(dāng)?shù)拇刂?事實(shí)證明 對(duì)于每一個(gè)事務(wù) 與之鏈接最多的那個(gè)事務(wù)總是和它處于同一個(gè)簇中 例如 令 0 5 則C2中的事務(wù) a b f 與同樣來(lái)自同一簇中的事務(wù) a b g 之間的鏈接數(shù)為5 因?yàn)樗鼈冇泄餐慕?a b c a b d a b e a f g 和 b f g 然而 C2中的事務(wù) b f g 與C1中的事務(wù) a b c 之間的鏈接數(shù)僅為3 其共同的鄰居為 a b d a b e a b g 類(lèi)似地 C2中的事務(wù) a f g 與C2中其他每個(gè)事務(wù)之間的鏈接數(shù)均為2 而與C1中所有事務(wù)的鏈接數(shù)都為0 因此 這種基于鏈接的方法能夠正確地區(qū)分出兩個(gè)不同的事務(wù)簇 因?yàn)樗丝紤]對(duì)象間的相似度之外還考慮鄰域信息 Page 38 基于這些思想 ROCK使用一個(gè)相似度閾值和共享近鄰的概念從一個(gè)給定的數(shù)據(jù)相似度矩陣中首先構(gòu)建一個(gè)稀疏圖 然后在這個(gè)稀疏圖上執(zhí)行凝聚層次聚類(lèi) ROCK算法在最壞情況下的時(shí)間復(fù)雜度為其中和分別是近鄰數(shù)目的最大值和平均值 n是對(duì)象的個(gè)數(shù) Page 39 主要內(nèi)容 凝聚和分裂層次聚類(lèi) 01 BIRCH 利用層次方法的平衡迭代歸約和聚類(lèi) 02 Chameleon 利用動(dòng)態(tài)建模的層次聚類(lèi)算法 05 ROCK 分類(lèi)屬性的層次聚類(lèi)算法 03 CURE 基于質(zhì)心和基于代表對(duì)象方法之間的中間策略 04 Page 40 很多聚類(lèi)算法只擅長(zhǎng)處理球形或相似大小的聚類(lèi) 另外有些聚類(lèi)算法對(duì)孤立點(diǎn)比較敏感 CURE算法解決了上述兩方面的問(wèn)題 選擇基于質(zhì)心和基于代表對(duì)象方法之間的中間策略 即選擇空間中固定數(shù)目的具有代表性的點(diǎn) 而不是用單個(gè)中心或?qū)ο髞?lái)代表一個(gè)簇 簇的代表點(diǎn)產(chǎn)生方式 首先選擇簇中分散的對(duì)象 然后根據(jù)一個(gè)特定的分?jǐn)?shù)或收縮因子向簇中心收縮或移動(dòng)它們 在算法的每一步 有最近距離的代表點(diǎn)對(duì) 每個(gè)點(diǎn)來(lái)自于一個(gè)不同的簇 的兩個(gè)簇被合并該算法首先把每個(gè)數(shù)據(jù)點(diǎn)看成一簇 然后再以一個(gè)特定的收縮因子向簇中心 收縮 它們 即合并兩個(gè)距離最近的代表點(diǎn)的簇 Page 41 核心步驟 CURE算法采用隨機(jī)取樣和劃分兩種方法的組合 核心步驟如下 從源數(shù)據(jù)對(duì)象中抽取一個(gè)隨機(jī)樣本S 將樣本S分割為一組劃分 對(duì)每個(gè)劃分局部地聚類(lèi) 通過(guò)隨機(jī)取樣剔除孤立點(diǎn) 如果一個(gè)簇增長(zhǎng)的太慢 就去掉它 對(duì)局部的簇進(jìn)行聚類(lèi) 落在每個(gè)新形成的簇中的代表點(diǎn)根據(jù)用戶定義的一個(gè)收縮因子 收縮或向簇中心移動(dòng) 這些點(diǎn)代表了簇的形狀 用相應(yīng)的簇標(biāo)簽來(lái)標(biāo)記數(shù)據(jù) Page 42 優(yōu)點(diǎn) CURE算法優(yōu)點(diǎn) 可以適應(yīng)非球形的幾何形狀 將一個(gè)簇用多個(gè)代表點(diǎn)來(lái)表示 使得類(lèi)的外延可以向非球形的形狀擴(kuò)展 從而可調(diào)整類(lèi)的形狀以表達(dá)那些非球形的類(lèi) 對(duì)孤立點(diǎn)的處理更加健壯 收縮因子降底了噪音對(duì)聚類(lèi)的影響 從而使CURE對(duì)孤立點(diǎn)的處理更加健壯而且能夠識(shí)別非球形和大小變化較大的簇 對(duì)大型數(shù)據(jù)庫(kù)有良好的伸縮性 CURE算法的復(fù)雜性為O n n是對(duì)象的數(shù)目 所以該算法適合大型數(shù)據(jù)的聚類(lèi) Page 43 主要內(nèi)容 凝聚和分裂層次聚類(lèi) 01 BIRCH 利用層次方法的平衡迭代歸約和聚類(lèi) 02 Chameleon 利用動(dòng)態(tài)建模的層次聚類(lèi)算法 05 ROCK 分類(lèi)屬性的層次聚類(lèi)算法 03 CURE 基于質(zhì)心和基于代表對(duì)象方法之間的中間策略 04 Page 44 Chameleon是一種層次聚類(lèi)算法 它采用動(dòng)態(tài)建模來(lái)確定一對(duì)簇之間的相似度 在Chameleon中 簇的相似度依據(jù)如下兩點(diǎn)評(píng)估 1 簇中對(duì)象的連接情況 2 簇的鄰近性也就是說(shuō) 如果兩個(gè)簇的互連性都很高并且它們又靠的很近就將其合并 Page 45 Chameleon怎樣工作 構(gòu)造稀疏圖 劃分圖 合并劃分 最終的簇 數(shù)據(jù)集 45 k最近鄰圖 Page 46 算法思想 Chameleon算法的思想是 首先使用一種圖劃分算法將k最近鄰圖劃分成大量相對(duì)較小的子簇 然后使用凝聚層次聚類(lèi)算法 基于子簇的相似度反復(fù)地合并子簇 Page 47 圖劃分算法劃分標(biāo)準(zhǔn) 為了確定最相似的子簇對(duì) 它既考慮每個(gè)簇的互連性 又考慮簇的鄰近性 圖劃分算法劃分k最近鄰圖 使得割邊最小化 也就是說(shuō) 簇C劃分為兩個(gè)子簇Ci和Cj時(shí)需要切斷的邊的加權(quán)和最小 割邊用EC Ci Cj 表示 用于評(píng)估簇Ci和Cj之間的絕對(duì)互連性 Page 48 Chameleon根據(jù)每對(duì)簇Ci和Cj的相對(duì)互連度RI Ci Cj 和相對(duì)接近度RC Ci Cj 來(lái)決定它們之間的相似度 兩個(gè)簇Ci和Cj之間的相對(duì)互連度RI Ci Cj 定義為Ci和Cj之間的絕對(duì)互連度關(guān)于兩個(gè)簇Ci和Cj的內(nèi)部互連度的規(guī)范化 即其中是包含Ci和Cj的簇的割邊 如上面所定義 類(lèi)似地 或 是將Ci 或Cj 劃分成大致相等的兩部分的割邊的最小和 Page 49 兩個(gè)簇Ci和Cj的的相對(duì)接近度RC Ci Cj 定義為Ci和Cj之間的絕對(duì)接近度關(guān)于兩個(gè)簇Ci和Cj的內(nèi)部接近度的規(guī)范化 定義如下 其中是連接Ci中頂點(diǎn)和Cj中頂點(diǎn)的邊的平均權(quán)重 或 是最小二分簇Ci 或Cj 的邊的平均權(quán)重 Page 50 特點(diǎn) 與一些著名的算法 如BIRCH和基于密度的DBSCAN 相比 Chameleon在發(fā)現(xiàn)高質(zhì)量的任意形狀的簇方面具有很強(qiáng)的能力 然而 在最壞的情況下 高維數(shù)據(jù)的處理代價(jià)可能對(duì)n個(gè)對(duì)象需要的時(shí)間 51 謝謝大家