《數(shù)據(jù)挖掘?qū)哟尉垲恜pt課件》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)挖掘?qū)哟尉垲恜pt課件（34頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,層次聚類,*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,*,7.5,層次聚類方法,7.5層次聚類方法,1,2024/11/21,層次聚類,2,層次聚類方法概述,層次聚類方法將數(shù)據(jù)對象組成一棵聚類樹。,根據(jù)層次分解是自底向上（合并）還是自頂向下（分裂），進(jìn)一步分為凝聚的和分裂的。,2023/10/7層次聚類2層次聚類方法概述層次聚類方法將數(shù),2,2024/11/21,層次聚類,3,層次聚類方法概述,凝聚的層次聚類：一種自底向上的策略，首先將每個(gè)對象作為一個(gè)簇，然后

2、合并這些原子簇為越來越大的簇，直到某個(gè)終結(jié)條件被滿足。,分裂的層次聚類：采用自頂向下的策略，它首先將所有對象置于一個(gè)簇中，然后逐漸細(xì)分為越來越小的簇，直到達(dá)到了某個(gè)終結(jié)條件。,層次凝聚的代表是,AGNES,算法。層次分裂的代表是,DIANA,算法。,2023/10/7層次聚類3層次聚類方法概述凝聚的層次聚類：,3,2024/11/21,層次聚類,4,簇間距離,最小距離,2023/10/7層次聚類4簇間距離最小距離,4,2024/11/21,層次聚類,5,簇間距離,最大距離,2023/10/7層次聚類5簇間距離最大距離,5,2024/11/21,層次聚類,6,簇間距離,平均距離,2023/10/

3、7層次聚類6簇間距離平均距離,6,2024/11/21,層次聚類,7,簇間距離,均值距離,2023/10/7層次聚類7簇間距離均值距離,7,2024/11/21,層次聚類,8,AGNES,算法,AGNES(AGglomerative NESting),算法最初將每個(gè)對象作為一個(gè)簇，然后這些簇根據(jù)某些準(zhǔn)則被一步步地合并。,兩個(gè)簇間的相似度由這兩個(gè)不同簇中距離最近的數(shù)據(jù)點(diǎn)對的相似度來確定。,聚類的合并過程反復(fù)進(jìn)行直到所有的對象最終滿足簇?cái)?shù)目。,2023/10/7層次聚類8AGNES算法AGNES(AGg,8,2024/11/21,層次聚類,9,AGNES,算法,輸入：,n,個(gè)對象，終止條件簇的數(shù)目

4、,k,。,輸出：,k,個(gè)簇，達(dá)到終止條件規(guī)定簇?cái)?shù)目。,(1),將每個(gè)對象當(dāng)成一個(gè)初始簇；,(2)REPEAT,(3),根據(jù)兩個(gè)簇中最近的數(shù)據(jù)點(diǎn)找到最近的兩個(gè)簇；,(4),合并兩個(gè)簇，生成新的簇的集合；,(5)UNTIL,達(dá)到定義的簇的數(shù)目；,2023/10/7層次聚類9AGNES算法輸入：n個(gè)對象，終,9,2024/11/21,層次聚類,10,AGNES,算法例題,序號 屬性,1,屬性,2,1 1 1,2 1 2,3 2 1,4 2 2,5 3 4,6 3 5,7 4 4,8 4 5,第,1,步：根據(jù)初始簇計(jì)算每個(gè)簇之間的距離，隨機(jī)找出距離最小的兩個(gè)簇，進(jìn)行合并，最小距離為,1,，合并后,1,

5、2,兩個(gè)點(diǎn)合并為一個(gè)簇。,第,2,步：對上一次合并后的簇計(jì)算簇間距離，找出距離最近的兩個(gè)簇進(jìn)行合并，合并后,3,4,點(diǎn)成為一簇。,第,3,步：重復(fù)第,2,步的工作，,5,6,點(diǎn)成為一簇。,第,4,步：重復(fù)第,2,步的工作，,7,8,點(diǎn)成為一簇。,第,5,步：合并,1,2,，,3,4,成為一個(gè)包含四個(gè)點(diǎn)的簇。,第,6,步：合并,5,6,，,7,8,，由于合并后的簇的數(shù)目已經(jīng)達(dá)到了用戶輸入的終止條件，程序終止。,步驟 最近的簇距離 最近的兩個(gè)簇 合并后的新簇,1 1 1,，,2 1,2,，,3,，,4,，,5,，,6,，,7,，,8,1 3,，,4 1,2,，,3,4,，,5,，,6,，,7,，,

6、8,1 5,，,6 1,2,，,3,4,，,5,6,，,7,，,8,1 7,，,8 1,2,，,3,4,，,5,6,，,7,8,1 1,2,3,4 1,2,3,4,，,5,6,，,7,8,1 5,6,，,7,8 1,2,3,4,，,5,6,7,8,結(jié)束,2023/10/7層次聚類10AGNES算法例題序號,10,2024/11/21,層次聚類,11,2023/10/7層次聚類11,11,2024/11/21,層次聚類,12,2023/10/7層次聚類12,12,2024/11/21,層次聚類,13,2023/10/7層次聚類13,13,2024/11/21,層次聚類,14,AGNES,特點(diǎn),A

7、GNES,算法比較簡單，但經(jīng)常會遇到合并點(diǎn)選擇的困難。假如一旦一組對象被合并，下一步的處理將在新生成的簇上進(jìn)行。已做處理不能撤銷，聚類之間也不能交換對象。如果在某一步?jīng)]有很好的選擇合并的決定，可能會導(dǎo)致低質(zhì)量的聚類結(jié)果。,2023/10/7層次聚類14AGNES特點(diǎn)AGNES算法比,14,2024/11/21,層次聚類,15,DIANA,算法,DIANA,（,Divisive ANAlysis),算法是典型的分裂聚類方法。,在聚類中，用戶能定義希望得到的簇?cái)?shù)目作為一個(gè)結(jié)束條件。,2023/10/7層次聚類15DIANA算法DIANA（Di,15,算法,DIANA,（自頂向下分裂算法）,輸入：,

8、n,個(gè)對象，終止條件簇的數(shù)目,k,。,輸出：,k,個(gè)簇，達(dá)到終止條件規(guī)定簇?cái)?shù)目。,（,1,）將所有對象整個(gè)當(dāng)成一個(gè)初始簇；,（,2,）,FOR,（,i=1;ik;i+)DO BEGIN,（,3,）在所有簇中挑出具有最大直徑的簇,C,；,（,4,）找出,C,中與其它點(diǎn)平均相異度最大的一個(gè)點(diǎn),p,并把,p,放入,splinter group,，剩余的放在,old party,中；,（,5,）,REPEAT,（,6,）在,old party,里找出到最近的,splinter group,中的點(diǎn)的距離不大于到,old party,中最近點(diǎn)的距離的點(diǎn)，并將該點(diǎn)加入,splinter group,。,（,

9、7,）,UNTIL,沒有新的,old party,的點(diǎn)被分配給,splinter group,；,（,8,）,splinter group,和,old party,為被選中的簇分裂成的兩個(gè)簇，與其它簇一起組成新的簇集合。,（,9,）,END.,算法 DIANA（自頂向下分裂算法）,16,序號屬性,1,屬性,2,111,212,321,422,534,635,744,845,DIANA,算法例題,第,1,步，找到具有最大直徑的簇，對簇中的每個(gè)點(diǎn)計(jì)算平均相異度（假定采用是歐式距離）。,1,的平均距離：（,1+1+1.414+3.6+4.24+4.47+5,）,/7=2.96,類似地，,2,的平均距

10、離為,2.526,；,3,的平均距離為,2.68,；,4,的平均距離為,2.18,；,5,的平均距離為,2.18,；,6,的平均距離為,2.68,；,7,的平均距離為,2.526,；,8,的平均距離為,2.96,。,找出平均相異度最大的點(diǎn),1,放到,splinter group,中，剩余點(diǎn)在,old party,中。,第,2,步，在,old party,里找出到最近的,splinter group,中的點(diǎn)的距離不大于到,old party,中最近的點(diǎn)的距離的點(diǎn)，將該點(diǎn)放入,splinter group,中，該點(diǎn)是,2,。,第,3,步，重復(fù)第,2,步的工作，,splinter group,中放入

11、點(diǎn),3,。,第,4,步，重復(fù)第,2,步的工作，,splinter group,中放入點(diǎn),4,。,第,5,步，沒有在,old party,中的點(diǎn)放入了,splinter group,中且達(dá)到終止條件（,k=2,），程序終止。如果沒有到終止條件，因該從分裂好的簇中選一個(gè)直徑最大的簇繼續(xù)分裂。,步驟具有最大直徑的簇,splinter groupOld party,11,，,2,，,3,，,4,，,5,，,6,，,7,，,8 12,，,3,，,4,，,5,，,6,，,7,，,8,21,，,2,，,3,，,4,，,5,，,6,，,7,，,8 1,，,23,，,4,，,5,，,6,，,7,，,8,31,，

12、,2,，,3,，,4,，,5,，,6,，,7,，,8 1,，,2,，,34,，,5,，,6,，,7,，,8,41,，,2,，,3,，,4,，,5,，,6,，,7,，,8 1,，,2,，,3,，,45,，,6,，,7,，,8,51,，,2,，,3,，,4,，,5,，,6,，,7,，,8 1,，,2,，,3,，,45,，,6,，,7,，,8,終止,序號屬性 1屬性 2DIANA算法例題第1步，找到具有,17,2024/11/21,層次聚類,18,層次聚類方法的改進(jìn),層次聚類方法盡管簡單，但經(jīng)常會遇到合并或分裂點(diǎn)的選擇的困難。,改進(jìn)層次方法的聚類質(zhì)量的一個(gè)有希望的方向是將層次聚類和其他聚類技術(shù)進(jìn)行集

13、成，形成多階段聚類。,下面介紹,3,個(gè)改進(jìn)的層次聚類方法,BIRTH,，,ROCK,和,Chameleon,。,2023/10/7層次聚類18層次聚類方法的改進(jìn)層次聚類方法,18,2024/11/21,層次聚類,19,BIRCH,算法,BIRCH,（,Balanced Iterative Reducing and Clustering,）利用層次方法的平衡迭代歸約和聚類,用聚類特征（,CF,）和聚類特征樹來概括聚類描述。,該算法通過聚類特征可以方便地進(jìn)行中心、半徑、直徑及類內(nèi)、類間距離的運(yùn)算。,2023/10/7層次聚類19BIRCH算法BIRCH（B,19,2024/11/21,層次聚類,2

14、0,聚類特征（CF）,CF(Clustering Feature),：包含簇信息的三元組,(N,LS,SS),，,N,：簇的數(shù)據(jù)點(diǎn)；,LS,：線性和；,SS,：平方和,假定在簇,C1,中有三個(gè)點(diǎn),(2,5),(3,2),(4,3),聚類特征是：,CF1=,=,2023/10/7層次聚類20聚類特征（CF）CF(Clus,20,2024/11/21,層次聚類,21,聚類特征,樹,CF,樹是一個(gè)具有兩個(gè)參數(shù)分支因子,B,和閾值,T,的高度平衡樹。,分支因子,B,：非葉節(jié)點(diǎn)可以擁有的孩子數(shù),閾值,T,：葉子節(jié)點(diǎn)中的子聚類的最大直徑,2023/10/7層次聚類21聚類特征樹CF樹是一個(gè)具有兩個(gè),21,

15、2024/11/21,層次聚類,22,階段一：掃描數(shù)據(jù)庫，建立一個(gè)初始的,CF,樹，它可以被看作一個(gè)數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)內(nèi)在的聚類結(jié)構(gòu)。當(dāng)一個(gè)對象被插入到最近的葉節(jié)點(diǎn)（子聚類）中時(shí)，隨著對象的插入，,CF,樹被動(dòng)態(tài)地構(gòu)造，因此，,BIRTH,方法對增量或動(dòng)態(tài)聚類也非常有效。,階段二：采用某個(gè)聚類算法對,CF,樹的葉節(jié)點(diǎn)進(jìn)行聚類。在這個(gè)階段可以執(zhí)行任何聚類算法。,BIRCH,算法,2023/10/7層次聚類22 階段一：掃描數(shù)據(jù)庫，建立一個(gè),22,2024/11/21,層次聚類,23,ROCK,ROCK(Robust Clustering using linKs,使用連接的魯棒聚類,大多

16、數(shù)聚類算法在進(jìn)行聚類時(shí)只估計(jì)點(diǎn)與點(diǎn)之間的相似度，即在每一步中那些最相似的幾個(gè)點(diǎn)合并到一個(gè)簇中。這種“局部”方法很容易導(dǎo)致錯(cuò)誤。例如：兩個(gè)完全不同的簇可能有少數(shù)幾個(gè)點(diǎn)的距離較近，僅僅依據(jù)點(diǎn)與點(diǎn)之間的相似度來做出聚類決定就會導(dǎo)致這兩個(gè)簇合并。,ROCK,采用一種比較全局的觀點(diǎn)，通過考慮成對點(diǎn)的鄰域情況進(jìn)行聚類。,2023/10/7層次聚類23ROCKROCK(Robust,23,2024/11/21,層次聚類,24,ROCK,兩個(gè)概念：近鄰和鏈接,近鄰：兩個(gè)點(diǎn),pi,和,pj,是近鄰，如果,sim(pi,pj)=,sim,是相似度函數(shù)，,是指定的閾值,鏈接：兩個(gè)點(diǎn),pi,和,pj,的鏈接數(shù)定義為這兩點(diǎn)的共同近鄰個(gè)數(shù)。,由于在確定點(diǎn)對之間的關(guān)系時(shí)考慮鄰近的數(shù)據(jù)點(diǎn)，因此比只關(guān)注相似度的聚類方法更加魯棒。,2023/10/7層次聚類24ROCK兩個(gè)概念：近鄰和鏈接,24,ROCK,例：購物籃數(shù)據(jù)庫包含關(guān)于商品,a,b,g,的事物記錄。簇,C1,涉及商品,a,b,c,d,e,簇,C2,涉及商品,a,b,f,g,假設(shè)：只考慮相似度而忽略鄰域信息。,C1,中,a,b,c,和,b,d,e,之間的,Jac