模式識別與人工智能之七-part1

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

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

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

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

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

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

7、單連接算法。當(dāng)一個算法使用最大距離 度量類間距離時，有時稱為最遠(yuǎn)鄰聚類算法。如果當(dāng)最近類之間的最大距離超過某個任意閾值時聚類過程便終止，則稱其為全連接算法。,10,單連接算法例子,先將五個樣本都分別看成是一個類，最靠近的兩個類是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間的距離不變，修改后的距離矩陣如圖所示，在四個類1，2，(34)，5中，最靠近的兩個類是1和5，它們具有最小類間距離D（1,5）＝7.0

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

10、非常關(guān)鍵的，因?yàn)橐坏┮唤M對象合并或者分裂，下一步的處理將對新生成的類進(jìn)行。不具有很好的可伸縮性，因?yàn)楹喜⒒蚍至训臎Q定需要檢查和估算大量的對象或類。,16,層次聚類的改進(jìn),一個有希望的方向是集成層次聚類和其他的聚類技術(shù)，形成多階段聚類。在下面的內(nèi)容中會介紹四種這類的方法：BIRCH：首先用樹結(jié)構(gòu)對對象進(jìn)行層次劃分，其中葉節(jié)點(diǎn)或者是低層次的非葉節(jié)點(diǎn)可以看作是由分辨率決定的“微類”，然后使用其他的聚類算法對這些微類進(jìn)行宏聚類。ROCK基

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

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

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

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

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

16、：分支因子B和閾值T。分支因子B定義了每個非葉節(jié)點(diǎn)子女的最大數(shù)目。而閾值T參數(shù)給出了存儲在樹的葉節(jié)點(diǎn)中的子類的最大直徑。這兩個參數(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,該算法的計算復(fù)雜度是O(n)，其中n是聚類的對象的數(shù)目。實(shí)驗(yàn)表明該算法關(guān)于對象數(shù)目是線性可伸縮的，并且具有較好的數(shù)據(jù)聚類質(zhì)量。然而，既然CF樹的每個節(jié)點(diǎn)由于大小限制只能包含有限數(shù)目的條目，一個CF樹節(jié)

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

36、法使用距離函數(shù)。然而，實(shí)驗(yàn)表明對分類數(shù)據(jù)聚類時，這些距離度量不能產(chǎn)生高質(zhì)量的類。此外，大多數(shù)聚類算法在進(jìn)行聚類時只估計點(diǎn)與點(diǎn)之間的相似度；也就是說，在每一步中那些最相似的點(diǎn)合并到一個類中。這種“局部”方法很容易導(dǎo)致錯誤。,Page ? 40,ROCK是一種層次聚類算法，針對具有分類屬性的數(shù)據(jù)使用了鏈接（指兩個對象間共同的近鄰數(shù)目）這一概念。ROCK采用一種比較全局的觀點(diǎn)，通過考慮成對點(diǎn)的鄰域情況進(jìn)行聚類。如果兩個相似的點(diǎn)同時具有相似

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

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

39、J(A,B)定義為1,Page ? 43,假定一個購物籃數(shù)據(jù)庫包含關(guān)于商品a,b,...,g的事務(wù)記錄?？紤]這些事務(wù)的兩個類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中任意一對事務(wù)之間的Jaccard系數(shù)都在0.2和0.5之間，而屬于不同類的兩個事務(wù)之間的Jaccard系數(shù)也可能達(dá)到0.5。很明顯，僅僅使用Jaccard系數(shù)本身，無法得到所期望的類。,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,P

41、age ? 44,另一方面，ROCK基于鏈接的方法可以成功地把這些事務(wù)劃分到恰當(dāng)?shù)念愔?。事?shí)證明，對于每一個事務(wù)，與之鏈接最多的那個事務(wù)總是和它處于同一個類中。令 =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}之間的鏈接

42、數(shù)僅為2（其共同的鄰居為 {a,b,f}，{a,b,g}）類似地，C2中的事務(wù){(diào)a,f,g}與C2中其他每個事務(wù)之間的鏈接數(shù)均為2，而與C1中所有事務(wù)的鏈接數(shù)都為0。因此，這種基于鏈接的方法能夠正確地區(qū)分出兩個不同的事務(wù)類，因?yàn)樗丝紤]對象間的相似度之外還考慮鄰域信息。,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,Page ? 45,構(gòu)造目標(biāo)函數(shù)：使得最終類之間的鏈接總數(shù)最小，

43、累內(nèi)的鏈接總數(shù)最大,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,Ci ->第i個類；K ->類的個數(shù)；ni->Ci的大?。颖军c(diǎn)的數(shù)量）f (θ) = (1-θ)/(1+θ). f(θ)一般具有以下性質(zhì)：Ci中的每個樣本點(diǎn)在Ci中有nif(θ)個鄰居。,Page ? 46,相似性度量：通過相似性度量不斷的凝聚對象至k個類，最終計算上面目標(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,算法：輸入：需要聚類的個數(shù) k，和相似度閾值 θ算法：開始每個點(diǎn)都是單獨(dú)的聚類，根據(jù)公式計算點(diǎn)與點(diǎn)間的相似度，生成相似度矩陣。根據(jù)相似度矩陣和相似度閾值 θ，計算鄰居矩陣 A。如果兩點(diǎn)相似度>=θ,取值1（鄰居），否則取值0.　計算鏈接矩陣 L=A x A計算相似性的度量（Goodness Measure），將相似性最高的兩個對象合并?；氐降?步進(jìn)行迭代直到形成k個聚類或聚類的數(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,很多聚類算法只擅長處理球形

52、或相似大小的聚類，另外有些聚類算法對孤立點(diǎn)比較敏感。,出現(xiàn)的原因：,Page ? 53,CURE算法解決了上述兩方面的問題，選擇基于質(zhì)心和基于代表對象方法之間的中間策略，即選擇空間中固定數(shù)目的具有代表性的點(diǎn)，而不是用單個中心或?qū)ο髞泶硪粋€類。類的代表點(diǎn)產(chǎn)生方式：首先選擇類中分散的對象，然后根據(jù)一個特定的分?jǐn)?shù)或收縮因子向類中心收縮或移動它們。在算法的每一步，有最近距離的代表點(diǎn)對（每個點(diǎn)來自于一個不同的類）的兩個類被合并該算法首先把每

53、個數(shù)據(jù)點(diǎn)看成一類，然后再以一個特定的收縮因子向類中心“收縮”它們，即合并兩個距離最近的代表點(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ù)對象中抽取一個隨機(jī)樣本S；將樣本S分割為

57、一組劃分；對每個劃分局部地聚類；通過隨機(jī)取樣剔除孤立點(diǎn)。如果一個類增長的太慢，就去掉它；對局部的類進(jìn)行聚類。落在每個新形成的類中的代表點(diǎn)根據(jù)用戶定義的一個收縮因子α收縮或向類中心移動。這些點(diǎn)代表了類的形狀；用相應(yīng)的類標(biāo)簽來標(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)非球形的幾何形狀。將一個類用

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

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

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

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

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

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

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