層次聚類分析超精彩演示

（優(yōu)選）層次聚類分析超精彩當(dāng)前第1頁\共有50頁\編于星期三\3點(diǎn)主要內(nèi)容

凝聚和分裂層次聚類01BIRCH：利用層次方法的平衡迭代歸約和聚類02Chameleon：利用動(dòng)態(tài)建模的層次聚類算法05ROCK:分類屬性的層次聚類算法03CURE：基于質(zhì)心和基于代表對(duì)象方法之間的中間策略04當(dāng)前第2頁\共有50頁\編于星期三\3點(diǎn)概要層次聚類方法將數(shù)據(jù)對(duì)象組成一棵聚類樹。根據(jù)層次分解是以自底向上（合并）還是自頂向下（分裂）方式，層次聚類方法可以進(jìn)一步分為凝聚的和分裂的。一種純粹的層次聚類方法的質(zhì)量受限于：一旦合并或分裂執(zhí)行，就不能修正。也就是說，如果某個(gè)合并或分裂決策在后來證明是不好的選擇，該方法無法退回并更正。當(dāng)前第3頁\共有50頁\編于星期三\3點(diǎn)主要內(nèi)容

凝聚和分裂層次聚類01BIRCH：利用層次方法的平衡迭代歸約和聚類02Chameleon：利用動(dòng)態(tài)建模的層次聚類算法05ROCK:分類屬性的層次聚類算法03CURE：基于質(zhì)心和基于代表對(duì)象方法之間的中間策略04當(dāng)前第4頁\共有50頁\編于星期三\3點(diǎn)層次聚類方法一般來說，有兩種類型的層次聚類方法：凝聚層次聚類：采用自底向上策略，首先將每個(gè)對(duì)象作為單獨(dú)的一個(gè)原子簇，然后合并這些原子簇形成越來越大的簇，直到所有的對(duì)象都在一個(gè)簇中（層次的最上層），或者達(dá)到一個(gè)終止條件。絕大多數(shù)層次聚類方法屬于這一類。分裂層次聚類：采用自頂向下策略，首先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分為越來越小的簇，直到每個(gè)對(duì)象自成一個(gè)簇，或者達(dá)到某個(gè)終止條件，例如達(dá)到了某個(gè)希望的簇的數(shù)目，或者兩個(gè)最近的簇之間的距離超過了某個(gè)閾值。

當(dāng)前第5頁\共有50頁\編于星期三\3點(diǎn)例子下圖描述了一種凝聚層次聚類算法AGNES和一種分裂層次聚類算法DIANA對(duì)一個(gè)包含五個(gè)對(duì)象的數(shù)據(jù)集合{a,b,c,d,e}的處理過程。Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)圖1

對(duì)數(shù)據(jù)對(duì)象{a,b,c,d,e}的凝聚和分裂層次聚類當(dāng)前第6頁\共有50頁\編于星期三\3點(diǎn)初始，AGNES將每個(gè)對(duì)象自為一簇，然后這些簇根據(jù)某種準(zhǔn)則逐步合并，直到所有的對(duì)象最終合并形成一個(gè)簇。例如，如果簇C1中的一個(gè)對(duì)象和簇C2中的一個(gè)對(duì)象之間的距離是所有屬于不同簇的對(duì)象間歐氏距離中最小的，則C1和C2合并。在DIANA中，所有的對(duì)象用于形成一個(gè)初始簇。根據(jù)某種原則（如，簇中最近的相鄰對(duì)象的最大歐氏距離），將該簇分裂。簇的分裂過程反復(fù)進(jìn)行，直到最終每個(gè)新簇只包含一個(gè)對(duì)象。在凝聚或者分裂層次聚類方法中，用戶可以定義希望得到的簇?cái)?shù)目作為一個(gè)終止條件。當(dāng)前第7頁\共有50頁\編于星期三\3點(diǎn)樹狀圖通常，使用一種稱作樹狀圖的樹形結(jié)構(gòu)表示層次聚類的過程。它展示出對(duì)象是如何一步步分組的。圖2顯示圖1的五個(gè)對(duì)象的樹狀圖。圖2數(shù)據(jù)對(duì)象{a,b,c,d,e}層次聚類的樹狀圖表示當(dāng)前第8頁\共有50頁\編于星期三\3點(diǎn)簇間距離四個(gè)廣泛采用的簇間距離度量方法如下，其中|p-p'|是兩個(gè)對(duì)象或點(diǎn)p和p'之間的距離，mi是簇Ci的均值，而ni是簇Ci中對(duì)象的數(shù)目。最小距離：最大距離：均值距離：平均距離：

當(dāng)前第9頁\共有50頁\編于星期三\3點(diǎn)最小距離最大距離均值距離平均距離當(dāng)前第10頁\共有50頁\編于星期三\3點(diǎn)當(dāng)算法使用最小距離衡量簇間距離時(shí)，有時(shí)稱它為最近鄰聚類算法。此外，如果當(dāng)最近的簇之間的距離超過某個(gè)任意的閾值時(shí)聚類過程就會(huì)終止，則稱其為單連接算法。當(dāng)一個(gè)算法使用最大距離度量簇間距離時(shí)，有時(shí)稱為最遠(yuǎn)鄰聚類算法。如果當(dāng)最近簇之間的最大距離超過某個(gè)任意閾值時(shí)聚類過程便終止，則稱其為全連接算法。當(dāng)前第11頁\共有50頁\編于星期三\3點(diǎn)單連接算法例子先將五個(gè)樣本都分別看成是一個(gè)簇，最靠近的兩個(gè)簇是3和4，因?yàn)樗麄兙哂凶钚〉拇亻g距離D（3，4）=5.0。第一步：合并簇3和4，得到新簇集合1，2，（34），5當(dāng)前第12頁\共有50頁\編于星期三\3點(diǎn)更新距離矩陣：

D(1,(34))=min(D(1,3)，D(1,4))=min(20.6，22.4)=20.6

D(2,(34))=min(D(2,3)，D(2,4))=min(14.1，11.2)=11.2

D(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。當(dāng)前第13頁\共有50頁\編于星期三\3點(diǎn)當(dāng)前第14頁\共有50頁\編于星期三\3點(diǎn)當(dāng)前第15頁\共有50頁\編于星期三\3點(diǎn)最小和最大度量代表了簇間距離度量的兩個(gè)極端。它們趨向?qū)﹄x群點(diǎn)或噪聲數(shù)據(jù)過分敏感。使用均值距離和平均距離是對(duì)最小和最大距離之間的一種折中方法，而且可以克服離群點(diǎn)敏感性問題。盡管均值距離計(jì)算簡(jiǎn)單，但是平均距離也有它的優(yōu)勢(shì)，因?yàn)樗饶芴幚頂?shù)值數(shù)據(jù)又能處理分類數(shù)據(jù)。當(dāng)前第16頁\共有50頁\編于星期三\3點(diǎn)層次聚類方法的困難之處層次聚類方法盡管簡(jiǎn)單，但經(jīng)常會(huì)遇到合并或分裂點(diǎn)選擇的困難。這樣的決定是非常關(guān)鍵的，因?yàn)橐坏┮唤M對(duì)象合并或者分裂，下一步的處理將對(duì)新生成的簇進(jìn)行。不具有很好的可伸縮性，因?yàn)楹喜⒒蚍至训臎Q定需要檢查和估算大量的對(duì)象或簇。當(dāng)前第17頁\共有50頁\編于星期三\3點(diǎn)層次聚類的改進(jìn)一個(gè)有希望的方向是集成層次聚類和其他的聚類技術(shù)，形成多階段聚類。在下面的內(nèi)容中會(huì)介紹四種這類的方法：BIRCH：首先用樹結(jié)構(gòu)對(duì)對(duì)象進(jìn)行層次劃分，其中葉節(jié)點(diǎn)或者是低層次的非葉節(jié)點(diǎn)可以看作是由分辨率決定的“微簇”，然后使用其他的聚類算法對(duì)這些微簇進(jìn)行宏聚類。ROCK基于簇間的互聯(lián)性進(jìn)行合并。CURE選擇基于質(zhì)心和基于代表對(duì)象方法之間的中間策略。Chameleon探查層次聚類的動(dòng)態(tài)建模。當(dāng)前第18頁\共有50頁\編于星期三\3點(diǎn)主要內(nèi)容凝聚和分裂層次聚類01

BIRCH：利用層次方法的平衡迭代歸約和聚類02Chameleon：利用動(dòng)態(tài)建模的層次聚類算法05ROCK:分類屬性的層次聚類算法03CURE：基于質(zhì)心和基于代表對(duì)象方法之間的中間策略04當(dāng)前第19頁\共有50頁\編于星期三\3點(diǎn)BIRCH方法通過集成層次聚類和其他聚類算法來對(duì)大量數(shù)值數(shù)據(jù)進(jìn)行聚類。其中層次聚類用于初始的微聚類階段，而其他方法如迭代劃分（在后來的宏聚類階段）。它克服了凝聚聚類方法所面臨的兩個(gè)困難：可伸縮性；不能撤銷前一步所做的工作。BIRCH使用聚類特征來概括一個(gè)簇，使用聚類特征樹（CF樹）來表示聚類的層次結(jié)構(gòu)。這些結(jié)構(gòu)幫助聚類方法在大型數(shù)據(jù)庫中取得好的速度和伸縮性，還使得BIRCH方法對(duì)新對(duì)象增量和動(dòng)態(tài)聚類也非常有效。當(dāng)前第20頁\共有50頁\編于星期三\3點(diǎn)聚類特征（CF）考慮一個(gè)n個(gè)d維的數(shù)據(jù)對(duì)象或點(diǎn)的簇，簇的聚類特征是一個(gè)3維向量，匯總了對(duì)象簇的信息。定義如下

CF=<n,LS,SS>其中，n是簇中點(diǎn)的數(shù)目，LS是n個(gè)點(diǎn)的線性和（即），SS是數(shù)據(jù)點(diǎn)的平方和（即）。聚類特征本質(zhì)上是給定簇的統(tǒng)計(jì)匯總：從統(tǒng)計(jì)學(xué)的觀點(diǎn)來看，它是簇的零階矩、一階矩和二階矩。當(dāng)前第21頁\共有50頁\編于星期三\3點(diǎn)使用聚類特征，我們可以很容易地推導(dǎo)出簇的許多有用的統(tǒng)計(jì)量。例如，簇的形心x0，半徑R和直徑D分別是：

其中R是成員對(duì)象到形心的平均距離，D是簇中逐對(duì)對(duì)象的平均距離。R和D都反映了形心周圍簇的緊湊程度。當(dāng)前第22頁\共有50頁\編于星期三\3點(diǎn)使用聚類特征概括簇可以避免存儲(chǔ)個(gè)體對(duì)象或點(diǎn)的詳細(xì)信息。我們只需要固定大小的空間來存放聚類特征。這是空間中BIRCH有效性的關(guān)鍵。聚類特征是可加的。也就是說，對(duì)于兩個(gè)不相交的簇C1和C2，其聚類特征分別為CF1=<n1，LS1，SS1>和CF2=<n2，LS2，SS2>，合并C1和C2后的簇的聚類特征是CF1+CF2=<n1+n2，LS1+LS2，SS1+SS2>當(dāng)前第23頁\共有50頁\編于星期三\3點(diǎn)例子假定在簇C1中有三個(gè)點(diǎn)（2,5），（3,2）和（4,3）。C1的聚類特征是：CF1=<3，(2+3+4,5+2+3),(22+32+42,52+22+32)>=<3,(9,10,(29,38))>

假定C1和第2個(gè)簇C2是不相交的，其中CF2=<3,(35,36),(417,440)>。C1和C2合并形成一個(gè)新的簇C3，其聚類特征便是CF1和CF2之和，即：CF3=<3+3,(9+35,10+36),(29+417,38+440)>=<6,(44,46),(446,478)>當(dāng)前第24頁\共有50頁\編于星期三\3點(diǎn)CF樹CF樹是一棵高度平衡的樹，它存儲(chǔ)了層次聚類的聚類特征。圖3給出了一個(gè)例子。根據(jù)定義，樹中的非葉節(jié)點(diǎn)有后代或“子女”。非葉節(jié)點(diǎn)存儲(chǔ)了其子女的CF的總和，因而匯總了關(guān)于其子女的聚類信息。CF樹有兩個(gè)參數(shù)：分支因子B和閾值T。分支因子定義了每個(gè)非葉節(jié)點(diǎn)子女的最大數(shù)目。而閾值參數(shù)給出了存儲(chǔ)在樹的葉節(jié)點(diǎn)中的子簇的最大直徑。這兩個(gè)參數(shù)影響結(jié)果數(shù)的大小。當(dāng)前第25頁\共有50頁\編于星期三\3點(diǎn)圖3CF樹結(jié)構(gòu)當(dāng)前第26頁\共有50頁\編于星期三\3點(diǎn)BIRCH試圖利用可用的資源生成最好的簇。給定有限的主存，一個(gè)重要的考慮是最小化I/O所需時(shí)間。BIRCH采用了一種多階段聚類技術(shù)：數(shù)據(jù)集的單遍掃描產(chǎn)生一個(gè)基本的好聚類，一或多遍的額外掃描可以用來進(jìn)一步（優(yōu)化）改進(jìn)聚類質(zhì)量。它主要包括兩個(gè)階段：階段一：BIRCH掃描數(shù)據(jù)庫，建立一棵存放于內(nèi)存的初始CF樹，它可以看作數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)的內(nèi)在的聚類結(jié)構(gòu)。階段二：BIRCH采用某個(gè)（選定的）聚類算法對(duì)CF樹的葉節(jié)點(diǎn)進(jìn)行聚類，把稀疏的簇當(dāng)作離群點(diǎn)刪除，而把稠密的簇合并為更大的簇。當(dāng)前第27頁\共有50頁\編于星期三\3點(diǎn)CF樹的構(gòu)造在階段一中，隨著對(duì)象被插入，CF樹被動(dòng)態(tài)地構(gòu)造。這樣，該方法支持增量聚類。一個(gè)對(duì)象被插入到最近的葉條目（子簇）。如果在插入后，存儲(chǔ)在葉節(jié)點(diǎn)中的子簇的直徑大于閾值，則該葉節(jié)點(diǎn)和可能的其他節(jié)點(diǎn)被分裂。新對(duì)象插入后，關(guān)于該對(duì)象的信息向樹根節(jié)點(diǎn)傳遞。通過修改閾值，CF樹的大小可以改變。如果存儲(chǔ)CF樹需要的內(nèi)存大于主存的大小，可以定義較大的閾值，并重建CF樹。當(dāng)前第28頁\共有50頁\編于星期三\3點(diǎn)在CF樹重建過程中，通過利用老樹的葉節(jié)點(diǎn)來重新構(gòu)建一棵新樹，因而樹的重建過程不需要訪問所有點(diǎn)，即構(gòu)建CF樹只需訪問數(shù)據(jù)一次就行?？梢栽陔A段二使用任意聚類算法，例如典型的劃分方法。當(dāng)前第29頁\共有50頁\編于星期三\3點(diǎn)BIRCH的有效性該算法的計(jì)算復(fù)雜度是O(n)，其中n是聚類的對(duì)象的數(shù)目。實(shí)驗(yàn)表明該算法關(guān)于對(duì)象數(shù)目是線性可伸縮的，并且具有較好的數(shù)據(jù)聚類質(zhì)量。然而，既然CF樹的每個(gè)節(jié)點(diǎn)由于大小限制只能包含有限數(shù)目的條目，一個(gè)CF樹節(jié)點(diǎn)并不總是對(duì)應(yīng)于用戶所考慮的一個(gè)自然簇。此外，如果簇不是球形的，BIRCH不能很好地工作，因?yàn)樗褂冒霃交蛑睆降母拍顏砜刂拼氐倪吔纭．?dāng)前第30頁\共有50頁\編于星期三\3點(diǎn)主要內(nèi)容凝聚和分裂層次聚類01

BIRCH：利用層次方法的平衡迭代歸約和聚類02Chameleon：利用動(dòng)態(tài)建模的層次聚類算法05

ROCK:分類屬性的層次聚類算法03CURE：基于質(zhì)心和基于代表對(duì)象方法之間的中間策略04當(dāng)前第31頁\共有50頁\編于星期三\3點(diǎn)對(duì)于聚類包含布爾或分類屬性的數(shù)據(jù)，傳統(tǒng)聚類算法使用距離函數(shù)。然而，實(shí)驗(yàn)表明對(duì)分類數(shù)據(jù)聚類時(shí)，這些距離度量不能產(chǎn)生高質(zhì)量的簇。此外，大多數(shù)聚類算法在進(jìn)行聚類時(shí)只估計(jì)點(diǎn)與點(diǎn)之間的相似度；也就是說，在每一步中那些最相似的點(diǎn)合并到一個(gè)簇中。這種“局部”方法很容易導(dǎo)致錯(cuò)誤。當(dāng)前第32頁\共有50頁\編于星期三\3點(diǎn)ROCK是一種層次聚類算法，針對(duì)具有分類屬性的數(shù)據(jù)使用了鏈接（指兩個(gè)對(duì)象間共同的近鄰數(shù)目）這一概念。ROCK采用一種比較全局的觀點(diǎn)，通過考慮成對(duì)點(diǎn)的鄰域情況進(jìn)行聚類。如果兩個(gè)相似的點(diǎn)同時(shí)具有相似的鄰域，那么這兩個(gè)點(diǎn)可能屬于同一個(gè)簇而合并。當(dāng)前第33頁\共有50頁\編于星期三\3點(diǎn)兩個(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)聚類方法就顯得更加魯棒。當(dāng)前第34頁\共有50頁\編于星期三\3點(diǎn)包含分類屬性數(shù)據(jù)的一個(gè)很好的例子就是購物籃數(shù)據(jù)。這種數(shù)據(jù)由事務(wù)數(shù)據(jù)庫組成，其中每個(gè)事務(wù)都是商品的集合事務(wù)看作具有布爾屬性的記錄，每個(gè)屬性對(duì)應(yīng)于一個(gè)單獨(dú)的商品，如面包或奶酪。如果一個(gè)事務(wù)包含某個(gè)商品，那么該事務(wù)的記錄中對(duì)應(yīng)于此商品的屬性值就為真；否則為假。其他含有分類屬性的數(shù)據(jù)集可以用類似的方式處理。ROCK中近鄰和鏈接的概念將在下面的例子中闡述，其中兩個(gè)“點(diǎn)”即兩個(gè)事務(wù)Ti和Tj之間的相似度用Jaccard系數(shù)定義為：當(dāng)前第35頁\共有50頁\編于星期三\3點(diǎn)例子假定一個(gè)購物籃數(shù)據(jù)庫包含關(guān)于商品a,b,...,g的事務(wù)記錄?？紤]這些事務(wù)的兩個(gè)簇C1和C2。C1涉及商品{a,b,c,d,e}，包含事務(wù){(diào)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ù){(diào)a,b,f}，{a,b,g}，{a,f,g}，{b,f,g}假設(shè)我們首先只考慮點(diǎn)間的相似度而忽略鄰域信息。C1中事務(wù){(diào)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ù)本身，無法得到所期望的簇。當(dāng)前第36頁\共有50頁\編于星期三\3點(diǎn)另一方面，ROCK基于鏈接的方法可以成功地把這些事務(wù)劃分到恰當(dāng)?shù)拇刂?。事?shí)證明，對(duì)于每一個(gè)事務(wù)，與之鏈接最多的那個(gè)事務(wù)總是和它處于同一個(gè)簇中。例如，令=0.5，則C2中的事務(wù){(diào)a,b,f}與同樣來自同一簇中的事務(wù){(diào)a,b,g}之間的鏈接數(shù)為5（因?yàn)樗鼈冇泄餐慕弡a,b,c}，{a,b,d}，{a,b,e}，{a,f,g}和{b,f,g}）然而，C2中的事務(wù){(diào)b,f,g}與C1中的事務(wù){(diào)a,b,c}之間的鏈接數(shù)僅為3（其共同的鄰居為{a,b,d}，{a,b,e}，{a,b,g}）類似地，C2中的事務(wù){(diào)a,f,g}與C2中其他每個(gè)事務(wù)之間的鏈接數(shù)均為2，而與C1中所有事務(wù)的鏈接數(shù)都為0。因此，這種基于鏈接的方法能夠正確地區(qū)分出兩個(gè)不同的事務(wù)簇，因?yàn)樗丝紤]對(duì)象間的相似度之外還考慮鄰域信息。當(dāng)前第37頁\共有50頁\編于星期三\3點(diǎn)基于這些思想，ROCK使用一個(gè)相似度閾值和共享近鄰的概念從一個(gè)給定的數(shù)據(jù)相似度矩陣中首先構(gòu)建一個(gè)稀疏圖。然后在這個(gè)稀疏圖上執(zhí)行凝聚層次聚類。ROCK算法在最壞情況下的時(shí)間復(fù)雜度為其中和分別是近鄰數(shù)目的最大值和平均值，n是對(duì)象的個(gè)數(shù)。當(dāng)前第38頁\共有50頁\編于星期三\3點(diǎn)主要內(nèi)容凝聚和分裂層次聚類01BIRCH：利用層次方法的平衡迭代歸約和聚類02Chameleon：利用動(dòng)態(tài)建模的層次聚類算法05ROCK:分類屬性的層次聚類算法03

CURE：基于質(zhì)心和基于代表對(duì)象方法之間的中間策略04當(dāng)前第39頁\共有50頁\編于星期三\3點(diǎn)很多聚類算法只擅長(zhǎng)處理球形或相似大小的聚類，另外有些聚類算法對(duì)孤立點(diǎn)比較敏感。CURE算法解決了上述兩方面的問題，選擇基于質(zhì)心和基于代表對(duì)象方法之間的中間策略，即選擇空間中固定數(shù)目的具有代表性的點(diǎn)，而不是用單個(gè)中心或?qū)ο髞泶硪粋€(gè)簇。簇的代表點(diǎn)產(chǎn)生方式：首先選擇簇中分散的對(duì)象，然后根據(jù)一個(gè)特定的分?jǐn)?shù)或收縮因子向簇中心收縮或移動(dòng)它們。在算法的每一步，有最近距離的代表點(diǎn)對(duì)（每個(gè)點(diǎn)來自于一個(gè)不同的簇）的兩個(gè)簇被合并該算法首先把每個(gè)數(shù)據(jù)點(diǎn)看成一簇，然后再以一個(gè)特定的收縮因子向簇中心“收縮”它們，即合并兩個(gè)距離最近的代表點(diǎn)的簇。當(dāng)前第40頁\共有50頁\編于星期三\3點(diǎn)核心步驟CURE算法采用隨機(jī)取樣和劃分兩種方法的組合，核心步驟如下：從源數(shù)據(jù)對(duì)象中抽取一個(gè)隨機(jī)樣本S；將樣本S分割為一組劃分；對(duì)每個(gè)劃分局部地聚類；通過隨機(jī)取樣剔除孤立點(diǎn)。如果一個(gè)簇增長(zhǎng)的太慢，就去掉它；對(duì)局部的簇進(jìn)行聚類。落在每個(gè)新形成的簇中的代表點(diǎn)根據(jù)用戶定義的一個(gè)收縮因子α收縮或向簇中心移動(dòng)。這些點(diǎn)代表了簇的形狀；用相應(yīng)的簇標(biāo)簽來標(biāo)記數(shù)據(jù)。當(dāng)前第41頁\共有50頁\編于星期三\3點(diǎn)優(yōu)點(diǎn)CURE算法優(yōu)點(diǎn)：可以適應(yīng)非球形的幾何形狀。將一個(gè)簇用多個(gè)代表點(diǎn)來表示，使得類的外延可以向非球形的形狀擴(kuò)展，從而可調(diào)整類的形狀以表達(dá)那些非球形的類。對(duì)孤立點(diǎn)的處理更加健壯。收縮因子降底了噪音對(duì)聚類的影響，從而使CURE對(duì)孤立點(diǎn)的處理更加健壯而且能夠識(shí)別非球形和大小變化較大的簇。對(duì)大型數(shù)據(jù)庫有良好的伸縮性。CURE算法的復(fù)雜性為O(n)。n是對(duì)象的數(shù)目，所以該算法適合大型數(shù)據(jù)的聚類。當(dāng)前第42頁\共有50頁\編于星期三\3點(diǎn)主要內(nèi)容凝聚和分裂層次聚類01BIRCH：利用層次方法的平衡迭代歸約和聚類02

Chameleon：利用動(dòng)態(tài)建模的層次聚類算法05ROCK:分類屬性的層次聚類算法03CURE：基于質(zhì)心和基于代表對(duì)象方法之間的中間策略04當(dāng)前第43頁\共有50頁\編于星期三\3點(diǎn)Chameleon是一種層次聚類算法，它采用動(dòng)態(tài)建模來確定一對(duì)簇之間的相似度。在Chameleon中，簇的相似度依據(jù)如下兩點(diǎn)評(píng)估：（1）簇中對(duì)象的連接情況（2）簇的鄰近性也就是說，如果兩個(gè)簇的互連性都很高并且它們又靠的很近就將其合并。當(dāng)前第44頁\共有50頁\編于星期三\3點(diǎn)Chameleon怎樣工作?構(gòu)造稀疏圖劃分圖合并劃分最終的簇?cái)?shù)據(jù)集45