層次聚類分析-超精彩.ppt

《層次聚類分析-超精彩.ppt》由會員分享，可在線閱讀，更多相關《層次聚類分析-超精彩.ppt（51頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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