模式識(shí)別與人工智能之七-part1

1、Pattern Recognition & artificial IntelligenceLecture 7: 聚類算法（三）,1,主要內(nèi)容,Hierarchical Clustering 基于分層的聚類算法,凝聚和分裂層次聚類,,01,BIRCH：利用層次方法的平衡迭代歸約和聚類,,02,Chameleon：利用動(dòng)態(tài)建模的層次聚類算法,,05,ROCK:分類屬性的層次聚類算法,,03,CURE：基于質(zhì)心和基于代表對(duì)象

2、方法之間的中間策略,,04,2,概要,層次聚類方法將數(shù)據(jù)對(duì)象組成一棵聚類樹。根據(jù)層次分解是以自底向上（合并）還是自頂向下（分裂）方式，層次聚類方法可以進(jìn)一步分為凝聚的和分裂的。一種純粹的層次聚類方法的質(zhì)量受限于：一旦合并或分裂執(zhí)行，就不能修正。也就是說，如果某個(gè)合并或分裂決策在后來(lái)證明是不好的選擇，該方法無(wú)法退回并更正。,3,層次聚類方法,一般來(lái)說，有兩種類型的層次聚類方法：凝聚層次聚類：采用自底向上策略，首先將每個(gè)對(duì)象作為單獨(dú)的

3、一個(gè)原子類，然后合并這些原子類形成越來(lái)越大的類，直到所有的對(duì)象都在一個(gè)類中（層次的最上層），或者達(dá)到一個(gè)終止條件。絕大多數(shù)層次聚類方法屬于這一類。分裂層次聚類：采用自頂向下策略，首先將所有對(duì)象置于一個(gè)類中，然后逐漸細(xì)分為越來(lái)越小的類，直到每個(gè)對(duì)象自成一個(gè)類，或者達(dá)到某個(gè)終止條件，例如達(dá)到了某個(gè)希望的類的數(shù)目，或者兩個(gè)最近的類之間的距離超過了某個(gè)閾值。,4,例子,下圖描述了一種凝聚層次聚類算法AGNES（AGlomerative NES

4、ting）和一種分裂層次聚類算法DIANA （ Divisive Analysis ）對(duì)一個(gè)包含五個(gè)對(duì)象的數(shù)據(jù)集合{a,b,c,d,e}的處理過程。,圖1 對(duì)數(shù)據(jù)對(duì)象{a,b,c,d,e}的凝聚和分裂層次聚類,5,初始，AGNES將每個(gè)對(duì)象自為一類，然后這些類根據(jù)某種準(zhǔn)則逐步合并，直到所有的對(duì)象最終合并形成一個(gè)類。例如，如果類C1中的一個(gè)對(duì)象和類C2中的一個(gè)對(duì)象之間的距離是所有屬于不同類的對(duì)象間歐氏距離中最小的，則C1和C2合并。在

5、DIANA中，所有的對(duì)象用于形成一個(gè)初始類。根據(jù)某種原則（如，類中最近的相鄰對(duì)象的最大歐氏距離），將該類分裂。類的分裂過程反復(fù)進(jìn)行，直到最終每個(gè)新類只包含一個(gè)對(duì)象。在凝聚或者分裂層次聚類方法中，用戶可以定義希望得到的類數(shù)目作為一個(gè)終止條件。,例子,6,樹狀圖,通常，使用一種稱作樹狀圖的樹形結(jié)構(gòu)表示層次聚類的過程。它展示出對(duì)象是如何一步步分組的。圖2顯示圖1的五個(gè)對(duì)象的樹狀圖。,圖2 數(shù)據(jù)對(duì)象{a,b,c,d,e}層次聚類的樹狀圖表示,

6、7,類間距離,四個(gè)廣泛采用的類間距離度量方法如下，其中|p-p'|是兩個(gè)對(duì)象或點(diǎn)p和p'之間的距離，mi是類Ci的均值，而ni是類Ci中對(duì)象的數(shù)目。最小距離：最大距離：均值距離：平均距離：,8,最小距離,最大距離,均值距離,平均距離,類間距離,9,當(dāng)算法使用最小距離 衡量類間距離時(shí)，有時(shí)稱它為最近鄰聚類算法。此外，如果當(dāng)最近的類之間的距離超過某個(gè)任意的閾值時(shí)聚類過程就會(huì)終止，則稱其為

7、單連接算法。當(dāng)一個(gè)算法使用最大距離 度量類間距離時(shí)，有時(shí)稱為最遠(yuǎn)鄰聚類算法。如果當(dāng)最近類之間的最大距離超過某個(gè)任意閾值時(shí)聚類過程便終止，則稱其為全連接算法。,10,單連接算法例子,先將五個(gè)樣本都分別看成是一個(gè)類，最靠近的兩個(gè)類是3和4，因?yàn)樗麄兙哂凶钚〉念愰g距離D（3，4）=5.0。第一步：合并類3和4，得到新類集合1，2，（34），5,11,更新距離矩陣： D(1,(34))=min(D(1,

8、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.0

9、7。,單連接算法例子,12,,單連接算法例子,13,,單連接算法例子,14,最小和最大度量代表了類間距離度量的兩個(gè)極端。它們趨向?qū)﹄x群點(diǎn)或噪聲數(shù)據(jù)過分敏感。使用均值距離和平均距離是對(duì)最小和最大距離之間的一種折中方法，而且可以克服離群點(diǎn)敏感性問題。盡管均值距離計(jì)算簡(jiǎn)單，但是平均距離也有它的優(yōu)勢(shì)，因?yàn)樗饶芴幚頂?shù)值數(shù)據(jù)又能處理分類數(shù)據(jù)。,15,層次聚類方法的困難之處,層次聚類方法盡管簡(jiǎn)單，但經(jīng)常會(huì)遇到合并或分裂點(diǎn)選擇的困難。這樣的決定是

10、非常關(guān)鍵的，因?yàn)橐坏┮唤M對(duì)象合并或者分裂，下一步的處理將對(duì)新生成的類進(jìn)行。不具有很好的可伸縮性，因?yàn)楹喜⒒蚍至训臎Q定需要檢查和估算大量的對(duì)象或類。,16,層次聚類的改進(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基

11、于類間的互聯(lián)性進(jìn)行合并。CURE選擇基于質(zhì)心和基于代表對(duì)象方法之間的中間策略。Chameleon探查層次聚類的動(dòng)態(tài)建模。,17,BIRCH方法通過集成層次聚類和其他聚類算法來(lái)對(duì)大量數(shù)值數(shù)據(jù)進(jìn)行聚類。其中層次聚類用于初始的微聚類階段，而其他方法如迭代劃分（在后來(lái)的宏聚類階段）。它克服了凝聚聚類方法所面臨的兩個(gè)困難： 可伸縮性；不能撤銷前一步所做的工作。BIRCH使用聚類特征來(lái)概括一個(gè)類，使用聚類特征樹（CF樹）來(lái)表示聚類的層次

12、結(jié)構(gòu)。這些結(jié)構(gòu)幫助聚類方法在大型數(shù)據(jù)庫(kù)中取得好的速度和伸縮性，還使得BIRCH方法對(duì)新對(duì)象增量和動(dòng)態(tài)聚類也非常有效。,BIRCH（balanced iterative reducing and clustering using hierarchies）聚類,18,聚類特征（CF）,考慮一個(gè)n個(gè)d維的數(shù)據(jù)對(duì)象或點(diǎn)的類，類的聚類特征是一個(gè)3維向量，匯總了對(duì)象類的信息。定義如下：

13、 CF= 其中，n是類中點(diǎn)的數(shù)目，LS是n個(gè)點(diǎn)的線性和（即 ）， SS是數(shù)據(jù)點(diǎn)的平方和（即 ）。聚類特征本質(zhì)上是給定類的統(tǒng)計(jì)匯總：從統(tǒng)計(jì)學(xué)的觀點(diǎn)來(lái)看，它是類的零階矩、一階矩和二階矩。,19,使用聚類特征，我們可以很容易地推導(dǎo)出類的許多有用的統(tǒng)計(jì)量。例如，類的形心x0，半徑R和直徑D分別是： 其中R是成員對(duì)象到形心的平均距離，D是類中逐對(duì)對(duì)象的平均距離。R和D都反

14、映了形心周圍類的緊湊程度。,聚類特征（CF）,20,Page ? 21,使用聚類特征概括類可以避免存儲(chǔ)個(gè)體對(duì)象或點(diǎn)的詳細(xì)信息。我們只需要固定大小的空間來(lái)存放聚類特征。這是空間中BIRCH有效性的關(guān)鍵。聚類特征是可加的。也就是說，對(duì)于兩個(gè)不相交的類C1和C2，其聚類特征分別為CF1=和CF2=，合并C1和C2后的類的聚類特征是 CF1+CF2=,聚類特征（CF）,Page ? 22,例子,假定在類C1中有三個(gè)點(diǎn)

15、（2,5），（3,2）和（4,3）。 C1的聚類特征是：CF1== 假定C1和第2個(gè)類C2是不相交的，其中CF2=。 C1和C2合并形成一個(gè)新的類C3，其聚類特征便是CF1和 CF2之和，即： CF3==,CF樹,CF樹是一棵高度平衡的樹，它存儲(chǔ)了層次聚類的聚類特征。根據(jù)定義，樹中的非葉節(jié)點(diǎn)有后代或“子女”。非葉節(jié)點(diǎn)存儲(chǔ)了其子女的CF的總和，因而匯總了關(guān)于其子女的聚類信息。CF樹有兩個(gè)參數(shù)

16、：分支因子B和閾值T。分支因子B定義了每個(gè)非葉節(jié)點(diǎn)子女的最大數(shù)目。而閾值T參數(shù)給出了存儲(chǔ)在樹的葉節(jié)點(diǎn)中的子類的最大直徑。這兩個(gè)參數(shù)影響結(jié)果樹的大小。,23,CF樹,24,BIRCH: The Idea by example,Data Objects,,1,Clustering Process (build a tree),,,,Cluster1,,1,2,3,4,5,6,2,,If cluster 1 becomes too l

17、arge (not compact) by adding object 2,then split the cluster,Leaf node,BIRCH: The Idea by example,Data Objects,1,Clustering Process (build a tree),,,,Cluster1,,1,2,3,4,5,6,2,Leaf node,,,Cluster2,entry 1,entry 2,Leaf no

18、de with two entries,BIRCH: The Idea by example,Data Objects,1,Clustering Process (build a tree),,,,Cluster1,,1,2,3,4,5,6,2,Leaf node,,,Cluster2,3,entry1 is the closest to object 3If cluster 1 becomes too large by addi

19、ng object 3,then split the cluster,entry 1,entry 2,BIRCH: The Idea by example,Data Objects,1,Clustering Process (build a tree),,,,Cluster1,,1,2,3,4,5,6,2,Leaf node,,Cluster2,3,,,entry 1,,entry 2,entry 3,Cluster3,Leaf n

20、ode with three entries,BIRCH: The Idea by example,Data Objects,1,Clustering Process (build a tree),,,,Cluster1,,1,2,3,4,5,6,2,Leaf node,,Cluster2,3,,,entry 1,,entry 2,entry 3,Cluster3,4,entry3 is the closest to object 4

21、Cluster 2 remains compact when adding object 4then add object 4 to cluster 2,,Cluster2,BIRCH: The Idea by example,Data Objects,1,Clustering Process (build a tree),,,,Cluster1,,1,2,3,4,5,6,2,Leaf node,3,,,entry 1,,en

22、try 2,entry 3,Cluster3,4,entry2 is the closest to object 5Cluster 3 becomes too large by adding object 5then split cluster 3?BUT there is a limit to the number of entries a node can haveThus, split the node,,Clust

23、er2,5,BIRCH: The Idea by example,Data Objects,1,Clustering Process (build a tree),,,Cluster1,,1,2,3,4,5,6,2,Leaf node,3,,Cluster3,4,,Cluster2,5,,,entry 1,entry 2,,,entry 1.1,entry 1.2,,,entry 2.1,entry 2.2,Leaf node,Non

24、-Leaf node,,Cluster4,,,BIRCH: The Idea by example,Data Objects,1,Clustering Process (build a tree),,,Cluster1,,1,2,3,4,5,6,2,Leaf node,3,,Cluster3,4,,Cluster2,5,,,entry 1,entry 2,,,entry 1.1,entry 1.2,,,entry 2.1,entry

25、2.2,Leaf node,Non-Leaf node,,Cluster4,,,6,entry1.2 is the closest to object 6Cluster 3 remains compact when adding object 6then add object 6 to cluster 3,,Cluster3,CF Tree,B = Branching Factor, maximum child

26、ren in a non-leaf nodeT = Threshold for diameter or radius of the cluster in a leafL = number of entries in a leafCF entry in parent = sum of CF entries of a child of that entryIn-

27、memory, height-balanced tree,,,,…,…,…,…,…,,,,Root level,Firstlevel,CF Tree Insertion,Start with the rootFind the CF entry in the root closest to the data point, move to that child and repeat the process until a close

28、st leaf entry is found.At the leafIf the point can be accommodated in the cluster, update the entryIf this addition violates the threshold T, split the entry, if this violates the limit imposed by L, split the leaf.

29、 If its parent node too is full, split that and so onUpdate the CF entries from the root to the leaf to accommodate this point,,Phase 1: Load into memory by building a CF tree,,Phase 2 (optional): Condense tree into de

30、sirable range by building a smaller CF tree,,Initial CF tree,Data,,Phase 3: Global Clustering,,Smaller CF tree,,Good Clusters,Phase 4: (optional and offline): Cluster Refining,Better Clusters,,,,Birch Algorithm,Birch Alg

31、orithm: Phase 1,Choose an initial value for threshold, start inserting the data points one by one into the tree as per the insertion algorithmIf, in the middle of the above step, the size of the CF tree exceeds the siz

32、e of the available memory, increase the value of thresholdConvert the partially built tree into a new treeRepeat the above steps until the entire dataset is scanned and a full tree is builtOutlier Handling,Birch Al

33、gorithm: Phase 2,3, and 4,Phase 2A bridge between phase 1 and phase 3Builds a smaller CF tree by increasing the thresholdPhase 3Apply global clustering algorithm to the sub-clusters given by leaf entries of the CF

34、 treeImproves clustering qualityPhase 4Scan the entire dataset to label the data pointsOutlier handling,Page ? 38,該算法的計(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é)

35、點(diǎn)并不總是對(duì)應(yīng)于用戶所考慮的一個(gè)自然類。此外，如果類不是球形的，BIRCH不能很好地工作，因?yàn)樗褂冒霃交蛑睆降母拍顏?lái)控制類的邊界。,BIRCH（balanced iterative reducing and clustering using hierarchies）聚類,Page ? 39,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,對(duì)于聚類包含布爾或分類屬性的數(shù)據(jù)，傳統(tǒng)聚類算

36、法使用距離函數(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ò)誤。,Page ? 40,ROCK是一種層次聚類算法，針對(duì)具有分類屬性的數(shù)據(jù)使用了鏈接（指兩個(gè)對(duì)象間共同的近鄰數(shù)目）這一概念。ROCK采用一種比較全局的觀點(diǎn)，通過考慮成對(duì)點(diǎn)的鄰域情況進(jìn)行聚類。如果兩個(gè)相似的點(diǎn)同時(shí)具有相似

37、的鄰域，那么這兩個(gè)點(diǎn)可能屬于同一個(gè)類而合并。,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,兩個(gè)點(diǎn)pi和pj是近鄰，如果 其中sim是相似度函數(shù)，sim可以選擇為距離度量； θ是用戶指定的閾值。pi和pj之間的鏈接數(shù)定義為這兩點(diǎn)的共同近鄰個(gè)數(shù)。如果兩個(gè)點(diǎn)的鏈接數(shù)很大，則他們很可能屬于相同的類。由于在確定點(diǎn)對(duì)之間的關(guān)系時(shí)考慮鄰近的

38、數(shù)據(jù)點(diǎn)，ROCK比起只關(guān)注點(diǎn)間相似度的標(biāo)準(zhǔn)聚類方法就顯得更加魯棒。,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,41,Page ? 42,ROCK中近鄰和鏈接的概念將在下面的例子中闡述，其中兩個(gè)“點(diǎn)”即兩個(gè)事務(wù)Ti和Tj之間的相似度用Jaccard系數(shù)定義為：,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,當(dāng)集合A，B都為空時(shí)，

39、J(A,B)定義為1,Page ? 43,假定一個(gè)購(gòu)物籃數(shù)據(jù)庫(kù)包含關(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,

40、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ù)本身，無(wú)法得到所期望的類。,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,P

41、age ? 44,另一方面，ROCK基于鏈接的方法可以成功地把這些事務(wù)劃分到恰當(dāng)?shù)念愔?。事?shí)證明，對(duì)于每一個(gè)事務(wù)，與之鏈接最多的那個(gè)事務(wù)總是和它處于同一個(gè)類中。令 =0.5，則C2中的事務(wù){(diào)a,b,f}與同樣來(lái)自同一類中的事務(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}之間的鏈接

42、數(shù)僅為2（其共同的鄰居為 {a,b,f}，{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ì)象間的相似度之外還考慮鄰域信息。,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,Page ? 45,構(gòu)造目標(biāo)函數(shù)：使得最終類之間的鏈接總數(shù)最小，

43、累內(nèi)的鏈接總數(shù)最大,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,Ci ->第i個(gè)類；K ->類的個(gè)數(shù)；ni->Ci的大?。颖军c(diǎn)的數(shù)量）f (θ) = (1-θ)/(1+θ). f(θ)一般具有以下性質(zhì)：Ci中的每個(gè)樣本點(diǎn)在Ci中有nif(θ)個(gè)鄰居。,Page ? 46,相似性度量：通過相似性度量不斷的凝聚對(duì)象至k個(gè)類，最終計(jì)算上面目標(biāo)函數(shù)值必然是最大的。

44、,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,ROCK,Suppose we have four verses contains some subjects , as follows:P1={ judgment, faith, prayer, fair}P2={ fasting, faith, prayer}P3={ fair, fasting, faith}P4={ fa

45、sting, prayer, pilgrimage}the similarity threshold = 0.3, and number of required cluster is 2.using Jaccard coefficient as a similarity measure, we obtain the following similarity table :,Example：,ROCK,Example：,Since w

46、e have a similarity threshold equal to 0.3, then we derive the adjacency table:?By multiplying the adjacency table with itself, we derive the following table which shows the number of links (or common neighbors) :?,ROCK

47、,Example：,we compute the goodness measure for all adjacent points ,assuming that f(?) =1-? / 1+? we obtain the following table?: we have an equal goodness measure for merging ((P1,P2), (P2,P1), (P3,P

48、1)),ROCK,Example：,Now, after merging P1 and P2, we have only three clusters. The following table shows the number of common neighbors for these clusters:?Then we can obtain the following goodness measures for all adjace

49、nt clusters:?,Since the number of required clusters is 2, then we finish the clustering algorithm by merging C(P1,P2) and P3, obtaining a new cluster C(P1,P2,P3) which contains {P1,P2,P3} leaving P4 alone in a separate c

50、luster.,Page ? 51,算法：輸入：需要聚類的個(gè)數(shù) k，和相似度閾值 θ算法：開始每個(gè)點(diǎn)都是單獨(dú)的聚類，根據(jù)公式計(jì)算點(diǎn)與點(diǎn)間的相似度，生成相似度矩陣。根據(jù)相似度矩陣和相似度閾值 θ，計(jì)算鄰居矩陣 A。如果兩點(diǎn)相似度>=θ,取值1（鄰居），否則取值0.　計(jì)算鏈接矩陣 L=A x A計(jì)算相似性的度量（Goodness Measure），將相似性最高的兩個(gè)對(duì)象合并?；氐降?步進(jìn)行迭代直到形成k個(gè)聚類或聚類的數(shù)量

51、不在發(fā)生變換。輸出：類和異常值（不一定存在）,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,52,,Figure 1: result of dmean,CURE（ Clustering Using Representatives）,,Figure 2: result of dmean,,Figure 3: result of dmin,很多聚類算法只擅長(zhǎng)處理球形

52、或相似大小的聚類，另外有些聚類算法對(duì)孤立點(diǎn)比較敏感。,出現(xiàn)的原因：,Page ? 53,CURE算法解決了上述兩方面的問題，選擇基于質(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è)類被合并該算法首先把每

53、個(gè)數(shù)據(jù)點(diǎn)看成一類，然后再以一個(gè)特定的收縮因子向類中心“收縮”它們，即合并兩個(gè)距離最近的代表點(diǎn)的類。,CURE（ Clustering Using Representatives）,Page ? 54,CURE（ Clustering Using Representatives）,Set a target representative points number c, for each cluste

54、r, select c well scattered points attempting to capture the physical shape and geometry of the clusterThe chosen scattered points are then shrunk toward the centroid in a fraction of ? where 0 <?<1,具體步驟,CURE（ Clus

55、tering Using Representatives）,具體步驟,These points are used as representatives and at each step of the algorithm, two clusters with closest pair of representatives are merged (dmin)After each merging, another c p

56、oints are selected from original representatives of previous clusters to represent new clusterCluster merging stops until target k clusters are found,55,Page ? 56,CURE算法采用隨機(jī)取樣和劃分兩種方法的組合，核心步驟如下：從源數(shù)據(jù)對(duì)象中抽取一個(gè)隨機(jī)樣本S；將樣本S分割為

57、一組劃分；對(duì)每個(gè)劃分局部地聚類；通過隨機(jī)取樣剔除孤立點(diǎn)。如果一個(gè)類增長(zhǎng)的太慢，就去掉它；對(duì)局部的類進(jìn)行聚類。落在每個(gè)新形成的類中的代表點(diǎn)根據(jù)用戶定義的一個(gè)收縮因子α收縮或向類中心移動(dòng)。這些點(diǎn)代表了類的形狀；用相應(yīng)的類標(biāo)簽來(lái)標(biāo)記數(shù)據(jù)。,CURE（ Clustering Using Representatives）,CURE（ Clustering Using Representatives）

58、,57,CURE（ Clustering Using Representatives）,58,Sensitivity to parametersParameters,,59,Different shrinking factor ?,CURE（ Clustering Using Representatives）,,60,Different number of representatives c,,

59、CURE（ Clustering Using Representatives）,61,Relation of execution time, different partition number p, and different sample points s,CURE（ Clustering Using Representatives）,CURE算法優(yōu)點(diǎn)：可以適應(yīng)非球形的幾何形狀。將一個(gè)類用

60、多個(gè)代表點(diǎn)來(lái)表示，使得類的外延可以向非球形的形狀擴(kuò)展，從而可調(diào)整類的形狀以表達(dá)那些非球形的類。對(duì)孤立點(diǎn)的處理更加健壯。收縮因子降底了噪音對(duì)聚類的影響，從而使CURE對(duì)孤立點(diǎn)的處理更加健壯而且能夠識(shí)別非球形和大小變化較大的類。對(duì)大型數(shù)據(jù)庫(kù)有良好的伸縮性。CURE算法的復(fù)雜性為O(n)。n是對(duì)象的數(shù)目，所以該算法適合大型數(shù)據(jù)的聚類。,CURE（ Clustering Using Representatives）

61、,62,Chameleon是一種層次聚類算法，它采用動(dòng)態(tài)建模來(lái)確定一對(duì)類之間的相似度。在Chameleon中，類的相似度依據(jù)如下兩點(diǎn)評(píng)估： 類中對(duì)象的連接情況 類的鄰近性也就是說，如果兩個(gè)類的互連性都很高并且它們又靠的很近就將其合并。,Chameleon：變色龍聚類方法,63,Page ? 64,,,,,構(gòu)造稀疏圖,,劃分圖,合并劃分,,,,最終的類,數(shù)據(jù)集,64,k最近鄰圖,Chameleon：變色龍聚類方法,Chameleo

62、n：變色龍聚類方法,節(jié)點(diǎn)表示數(shù)據(jù)項(xiàng)邊表示數(shù)據(jù)項(xiàng)的相似度圖的表示基于k-最近鄰居圖的方法好處：距離很遠(yuǎn)的數(shù)據(jù)項(xiàng)完全不相連邊的權(quán)重代表了潛在的空間密度信息在密集和稀疏區(qū)域的數(shù)據(jù)項(xiàng)都同樣能建模表示的稀疏便于使用有效的算法,65,算法思想,Chameleon算法的思想是：首先使用一種圖劃分算法將k最近鄰圖劃分成大量相對(duì)較小的子類。然后使用凝聚層次聚類算法，基于子類的相似度反復(fù)地合并子類。,Chameleon：變色龍聚類方法,

63、Chameleon：變色龍聚類方法,K近鄰圖中的每個(gè)點(diǎn)表示數(shù)據(jù)集中的一個(gè)數(shù)據(jù)點(diǎn)；若數(shù)據(jù)點(diǎn)ai 到另一個(gè)數(shù)據(jù)點(diǎn)bi 的距離值是所有數(shù)據(jù)點(diǎn)到數(shù)據(jù)點(diǎn)bi 的距離值中K個(gè)最小值之一,則稱數(shù)據(jù)點(diǎn)ai 是數(shù)據(jù)點(diǎn)bi 的K-最臨近對(duì)象，則在這兩個(gè)點(diǎn)之間加一條帶權(quán)邊,邊的權(quán)重表示這兩個(gè)數(shù)據(jù)點(diǎn)之間的近似度,即它們之間的距離越大,則它們之間的近似度越小,它們之間的邊的權(quán)重也越小。,K近鄰圖,67,Chameleon：變色龍聚類方法,互連性：類間距離較近數(shù)據(jù)

64、對(duì)的多少,近似性：類間數(shù)據(jù)對(duì)的相似度(最近距離),變色龍算法同時(shí)考慮了互連性和近似性,68,Chameleon：變色龍聚類方法,圖劃分算法劃分k近鄰圖，使得割邊最小，即類C劃分為兩個(gè)子類Ci和Cj時(shí)需切斷的邊的加權(quán)和最小。割邊用EC(Ci,Cj)表示，用于評(píng)估兩個(gè)類之間的絕對(duì)互連度。Chameleon根據(jù)每對(duì)類Ci和Cj的相對(duì)互連度RI(Ci,Cj)和相對(duì)接近度RC(Ci,Cj)來(lái)決定它們之間的相似度。,割邊,69,Chameleo

65、n：變色龍聚類方法,相對(duì)互連度(RI),相對(duì)互連性RI{Ci ,Cj} :子類Ci 和子類Cj之間絕對(duì)互連度關(guān)于兩個(gè)類間的內(nèi)部互連度的規(guī)范化。 絕對(duì)互連度EC{Ci ,Cj} :連接子類Ci 和子類Cj 之間的邊的權(quán)重之和。內(nèi)部互連度EC{Ci} :是將類Ci劃分成大致相等的兩部分的割邊的最小和。,70,Chameleon：變色龍聚類方法,相對(duì)近似度(RC),,71,Chameleon：變色龍聚類方法,聚類：,,第一階段：得到子簇

66、原因：準(zhǔn)確計(jì)算簇內(nèi)的互連性和近似性要求簇足夠數(shù)據(jù)項(xiàng)用hMetis算法 hMetis算法根據(jù)最小化截?cái)嗟倪叺臋?quán)重和來(lái)分割k-最近鄰居圖,72,Chameleon：變色龍聚類方法,聚類：,,第二階段：合并子簇用戶指定閾值(TRI和TRC)訪問每個(gè)簇，計(jì)算與它臨近簇的RI和RC。合并RI和RC分別超過TRI和TRC的簇對(duì)。若滿足條件的臨近簇多于一個(gè)，合并具有最高絕對(duì)互連性的簇。重復(fù)上兩步，直到?jīng)]有可合并的簇。函數(shù)定義度量函數(shù)：