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

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

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

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

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

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

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

7、單連接算法。當一個算法使用最大距離 度量類間距離時，有時稱為最遠鄰聚類算法。如果當最近類之間的最大距離超過某個任意閾值時聚類過程便終止，則稱其為全連接算法。,10,單連接算法例子,先將五個樣本都分別看成是一個類，最靠近的兩個類是3和4，因為他們具有最小的類間距離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,最小和最大度量代表了類間距離度量的兩個極端。它們趨向對離群點或噪聲數據過分敏感。使用均值距離和平均距離是對最小和最大距離之間的一種折中方法，而且可以克服離群點敏感性問題。盡管均值距離計算簡單，但是平均距離也有它的優(yōu)勢，因為它既能處理數值數據又能處理分類數據。,15,層次聚類方法的困難之處,層次聚類方法盡管簡單，但經常會遇到合并或分裂點選擇的困難。這樣的決定是

10、非常關鍵的，因為一旦一組對象合并或者分裂，下一步的處理將對新生成的類進行。不具有很好的可伸縮性，因為合并或分裂的決定需要檢查和估算大量的對象或類。,16,層次聚類的改進,一個有希望的方向是集成層次聚類和其他的聚類技術，形成多階段聚類。在下面的內容中會介紹四種這類的方法：BIRCH：首先用樹結構對對象進行層次劃分，其中葉節(jié)點或者是低層次的非葉節(jié)點可以看作是由分辨率決定的“微類”，然后使用其他的聚類算法對這些微類進行宏聚類。ROCK基

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

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

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

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

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

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

35、點并不總是對應于用戶所考慮的一個自然類。此外，如果類不是球形的，BIRCH不能很好地工作，因為它使用半徑或直徑的概念來控制類的邊界。,BIRCH（balanced iterative reducing and clustering using hierarchies）聚類,Page ? 39,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,對于聚類包含布爾或分類屬性的數據，傳統(tǒng)聚類算

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

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

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

39、J(A,B)定義為1,Page ? 43,假定一個購物籃數據庫包含關于商品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,

40、g}假設我們首先只考慮點間的相似度而忽略鄰域信息。C1中事務{a,b,c}和{b,d,e}之間的Jaccard系數為1/5=0.2。事實上，C1中任意一對事務之間的Jaccard系數都在0.2和0.5之間，而屬于不同類的兩個事務之間的Jaccard系數也可能達到0.5。很明顯，僅僅使用Jaccard系數本身，無法得到所期望的類。,ROCK（ RObust Clustering using linKs ）分類屬性的層次聚類算法,P

41、age ? 44,另一方面，ROCK基于鏈接的方法可以成功地把這些事務劃分到恰當的類中。事實證明，對于每一個事務，與之鏈接最多的那個事務總是和它處于同一個類中。令 =0.5，則C2中的事務{a,b,f}與同樣來自同一類中的事務{a,b,g}之間的鏈接數為5（因為它們有共同的近鄰{a,b,c}，{a,b,d}，{a,b,e}，{a,f,g}和{b,f,g}）然而，C2中的事務{b,f,g}與C1中的事務{a,b,c}之間的鏈接

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

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

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,算法：輸入：需要聚類的個數 k，和相似度閾值 θ算法：開始每個點都是單獨的聚類，根據公式計算點與點間的相似度，生成相似度矩陣。根據相似度矩陣和相似度閾值 θ，計算鄰居矩陣 A。如果兩點相似度>=θ,取值1（鄰居），否則取值0.　計算鏈接矩陣 L=A x A計算相似性的度量（Goodness Measure），將相似性最高的兩個對象合并?；氐降?步進行迭代直到形成k個聚類或聚類的數量

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、或相似大小的聚類，另外有些聚類算法對孤立點比較敏感。,出現的原因：,Page ? 53,CURE算法解決了上述兩方面的問題，選擇基于質心和基于代表對象方法之間的中間策略，即選擇空間中固定數目的具有代表性的點，而不是用單個中心或對象來代表一個類。類的代表點產生方式：首先選擇類中分散的對象，然后根據一個特定的分數或收縮因子向類中心收縮或移動它們。在算法的每一步，有最近距離的代表點對（每個點來自于一個不同的類）的兩個類被合并該算法首先把每

53、個數據點看成一類，然后再以一個特定的收縮因子向類中心“收縮”它們，即合并兩個距離最近的代表點的類。,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算法采用隨機取樣和劃分兩種方法的組合，核心步驟如下：從源數據對象中抽取一個隨機樣本S；將樣本S分割為

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

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

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

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

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

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

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

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