數(shù)據(jù)挖掘?qū)哟尉垲恜pt課件

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

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

2、合并這些原子簇為越來越大的簇，直到某個終結(jié)條件被滿足。,分裂的層次聚類：采用自頂向下的策略，它首先將所有對象置于一個簇中，然后逐漸細分為越來越小的簇，直到達到了某個終結(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),算法最初將每個對象作為一個簇，然后這些簇根據(jù)某些準則被一步步地合并。,兩個簇間的相似度由這兩個不同簇中距離最近的數(shù)據(jù)點對的相似度來確定。,聚類的合并過程反復進行直到所有的對象最終滿足簇數(shù)目。,2023/10/7層次聚類8AGNES算法AGNES(AGg,8,2024/11/21,層次聚類,9,AGNES,算法,輸入：,n,個對象，終止條件簇的數(shù)目

4、,k,。,輸出：,k,個簇，達到終止條件規(guī)定簇數(shù)目。,(1),將每個對象當成一個初始簇；,(2)REPEAT,(3),根據(jù)兩個簇中最近的數(shù)據(jù)點找到最近的兩個簇；,(4),合并兩個簇，生成新的簇的集合；,(5)UNTIL,達到定義的簇的數(shù)目；,2023/10/7層次聚類9AGNES算法輸入：n個對象，終,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ù)初始簇計算每個簇之間的距離，隨機找出距離最小的兩個簇，進行合并，最小距離為,1,，合并后,1,

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

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

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

9、7,）,UNTIL,沒有新的,old party,的點被分配給,splinter group,；,（,8,）,splinter group,和,old party,為被選中的簇分裂成的兩個簇，與其它簇一起組成新的簇集合。,（,9,）,END.,算法 DIANA（自頂向下分裂算法）,16,序號屬性,1,屬性,2,111,212,321,422,534,635,744,845,DIANA,算法例題,第,1,步，找到具有最大直徑的簇，對簇中的每個點計算平均相異度（假定采用是歐式距離）。,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,。,找出平均相異度最大的點,1,放到,splinter group,中，剩余點在,old party,中。,第,2,步，在,old party,里找出到最近的,splinter group,中的點的距離不大于到,old party,中最近的點的距離的點，將該點放入,splinter group,中，該點是,2,。,第,3,步，重復第,2,步的工作，,splinter group,中放入

11、點,3,。,第,4,步，重復第,2,步的工作，,splinter group,中放入點,4,。,第,5,步，沒有在,old party,中的點放入了,splinter group,中且達到終止條件（,k=2,），程序終止。如果沒有到終止條件，因該從分裂好的簇中選一個直徑最大的簇繼續(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īng)常會遇到合并或分裂點的選擇的困難。,改進層次方法的聚類質(zhì)量的一個有希望的方向是將層次聚類和其他聚類技術(shù)進行集

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

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

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

16、數(shù)聚類算法在進行聚類時只估計點與點之間的相似度，即在每一步中那些最相似的幾個點合并到一個簇中。這種“局部”方法很容易導致錯誤。例如：兩個完全不同的簇可能有少數(shù)幾個點的距離較近，僅僅依據(jù)點與點之間的相似度來做出聚類決定就會導致這兩個簇合并。,ROCK,采用一種比較全局的觀點，通過考慮成對點的鄰域情況進行聚類。,2023/10/7層次聚類23ROCKROCK(Robust,23,2024/11/21,層次聚類,24,ROCK,兩個概念：近鄰和鏈接,近鄰：兩個點,pi,和,pj,是近鄰，如果,sim(pi,pj)=,sim,是相似度函數(shù)，,是指定的閾值,鏈接：兩個點,pi,和,pj,的鏈接數(shù)定義為這兩點的共同近鄰個數(shù)。,由于在確定點對之間的關(guān)系時考慮鄰近的數(shù)據(jù)點，因此比只關(guān)注相似度的聚類方法更加魯棒。,2023/10/7層次聚類24ROCK兩個概念：近鄰和鏈接,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