上傳人：卓***

認證信息

認證類型：個人認證

認證主體：卓**（實名認證）

IP屬地：廣東

IP屬地：廣東 上傳時間：2023-07-24 格式：PPT 頁數(shù)：34 大?。?.85MB 積分：15 舉報 版權(quán)申訴

數(shù)據(jù)挖掘?qū)哟尉垲惖?頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類2層次聚類方法概述層次聚類方法將數(shù)據(jù)對象組成一棵聚類樹。根據(jù)層次分解是自底向上（合并）還是自頂向下（分裂），進一步分為凝聚的和分裂的。第2頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類3層次聚類方法概述凝聚的層次聚類：一種自底向上的策略，首先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到某個終結(jié)條件被滿足。分裂的層次聚類：采用自頂向下的策略，它首先將所有對象置于一個簇中，然后逐漸細分為越來越小的簇，直到達到了某個終結(jié)條件。層次凝聚的代表是AGNES算法。層次分裂的代表是DIANA算法。第3頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類4簇間距離最小距離第4頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類5簇間距離最大距離第5頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類6簇間距離平均距離第6頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類7簇間距離均值距離第7頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類8AGNES算法AGNES(AGglomerativeNESting)算法最初將每個對象作為一個簇，然后這些簇根據(jù)某些準則被一步步地合并。兩個簇間的相似度由這兩個不同簇中距離最近的數(shù)據(jù)點對的相似度來確定。聚類的合并過程反復進行直到所有的對象最終滿足簇數(shù)目。第8頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類9AGNES算法輸入：n個對象，終止條件簇的數(shù)目k。輸出：k個簇，達到終止條件規(guī)定簇數(shù)目。(1)將每個對象當成一個初始簇；(2)REPEAT(3)根據(jù)兩個簇中最近的數(shù)據(jù)點找到最近的兩個簇；(4)合并兩個簇，生成新的簇的集合；(5)UNTIL達到定義的簇的數(shù)目；第9頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類10AGNES算法例題序號屬性1屬性2111212321422534635744845第1步：根據(jù)初始簇計算每個簇之間的距離，隨機找出距離最小的兩個簇，進行合并，最小距離為1，合并后1,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)達到了用戶輸入的終止條件，程序終止。步驟最近的簇距離最近的兩個簇合并后的新簇11{1}，{2}{1,2}，{3}，{4}，{5}，{6}，{7}，{8}1{3}，{4}{1,2}，{3,4}，{5}，{6}，{7}，{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é)束第10頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類11第11頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類12第12頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類13第13頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類14AGNES特點AGNES算法比較簡單，但經(jīng)常會遇到合并點選擇的困難。假如一旦一組對象被合并，下一步的處理將在新生成的簇上進行。已做處理不能撤銷，聚類之間也不能交換對象。如果在某一步?jīng)]有很好的選擇合并的決定，可能會導致低質(zhì)量的聚類結(jié)果。第14頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類15DIANA算法DIANA（DivisiveANAlysis)算法是典型的分裂聚類方法。在聚類中，用戶能定義希望得到的簇數(shù)目作為一個結(jié)束條件。第15頁，課件共34頁，創(chuàng)作于2023年2月算法DIANA（自頂向下分裂算法）輸入：n個對象，終止條件簇的數(shù)目k。輸出：k個簇，達到終止條件規(guī)定簇數(shù)目。（1）將所有對象整個當成一個初始簇；（2）FOR（i=1;i≠k;i++)DOBEGIN（3）在所有簇中挑出具有最大直徑的簇C；（4）找出C中與其它點平均相異度最大的一個點p并把p放入splintergroup，剩余的放在oldparty中；（5）REPEAT（6）在oldparty里找出到最近的splintergroup中的點的距離不大于到oldparty中最近點的距離的點，并將該點加入splintergroup。（7）UNTIL沒有新的oldparty的點被分配給splintergroup；（8）splintergroup和oldparty為被選中的簇分裂成的兩個簇，與其它簇一起組成新的簇集合。（9）END.第16頁，課件共34頁，創(chuàng)作于2023年2月序號 屬性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

DIANA算法例題第1步，找到具有最大直徑的簇，對簇中的每個點計算平均相異度（假定采用是歐式距離）。

1的平均距離：（1+1+1.414+3.6+4.24+4.47+5）/7=2.96

類似地，2的平均距離為2.526；3的平均距離為2.68；4的平均距離為2.18；5的平均距離為2.18；6的平均距離為2.68；7的平均距離為2.526；8的平均距離為2.96。找出平均相異度最大的點1放到splintergroup中，剩余點在oldparty中。第2步，在oldparty里找出到最近的splintergroup中的點的距離不大于到oldparty中最近的點的距離的點，將該點放入splintergroup中，該點是2。第3步，重復第2步的工作，splintergroup中放入點3。第4步，重復第2步的工作，splintergroup中放入點4。第5步，沒有在oldparty中的點放入了splintergroup中且達到終止條件（k=2），程序終止。如果沒有到終止條件，因該從分裂好的簇中選一個直徑最大的簇繼續(xù)分裂。步驟 具有最大直徑的簇 splintergroup Oldparty 1 {1，2，3，4，5，6，7，8} {1} {2，3，4，5，6，7，8}2 {1，2，3，4，5，6，7，8} {1，2} {3，4，5，6，7，8} 3 {1，2，3，4，5，6，7，8} {1，2，3} {4，5，6，7，8} 4 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8} 5 {1，2，3，4，5，6，7，8} {1，2，3，4} {5，6，7，8}終止第17頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類18層次聚類方法的改進層次聚類方法盡管簡單，但經(jīng)常會遇到合并或分裂點的選擇的困難。改進層次方法的聚類質(zhì)量的一個有希望的方向是將層次聚類和其他聚類技術(shù)進行集成，形成多階段聚類。下面介紹3個改進的層次聚類方法BIRTH，ROCK和Chameleon。第18頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類19BIRCH算法BIRCH（BalancedIterativeReducingandClustering）利用層次方法的平衡迭代歸約和聚類用聚類特征（CF）和聚類特征樹來概括聚類描述。該算法通過聚類特征可以方便地進行中心、半徑、直徑及類內(nèi)、類間距離的運算。第19頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類20聚類特征（CF）CF(ClusteringFeature)：包含簇信息的三元組(N,LS,SS)，N：簇的數(shù)據(jù)點；LS：線性和；SS：平方和假定在簇C1中有三個點(2,5),(3,2),(4,3)聚類特征是：CF1=<3,(2+3+4,5+2+3),(22+32+42,52+22+32)>=<3,(9,10),(29,38)>第20頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類21聚類特征樹CF樹是一個具有兩個參數(shù)分支因子B和閾值T的高度平衡樹。分支因子B：非葉節(jié)點可以擁有的孩子數(shù)閾值T：葉子節(jié)點中的子聚類的最大直徑第21頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類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算法第22頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類23ROCKROCK(RobustClusteringusinglinKs,使用連接的魯棒聚類大多數(shù)聚類算法在進行聚類時只估計點與點之間的相似度，即在每一步中那些最相似的幾個點合并到一個簇中。這種“局部”方法很容易導致錯誤。例如：兩個完全不同的簇可能有少數(shù)幾個點的距離較近，僅僅依據(jù)點與點之間的相似度來做出聚類決定就會導致這兩個簇合并。ROCK采用一種比較全局的觀點，通過考慮成對點的鄰域情況進行聚類。第23頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類24ROCK兩個概念：近鄰和鏈接近鄰：兩個點pi和pj是近鄰，如果sim(pi,pj)>=θ,sim是相似度函數(shù)，θ是指定的閾值鏈接：兩個點pi和pj的鏈接數(shù)定義為這兩點的共同近鄰個數(shù)。由于在確定點對之間的關(guān)系時考慮鄰近的數(shù)據(jù)點，因此比只關(guān)注相似度的聚類方法更加魯棒。第24頁，課件共34頁，創(chuàng)作于2023年2月ROCK例：購物籃數(shù)據(jù)庫包含關(guān)于商品a,b,…g的事物記錄。簇C1涉及商品{a,b,c,d,e},簇C2涉及商品{a,b,f,g}假設：只考慮相似度而忽略鄰域信息。

C1中{a,b,c}和{b,d,e}之間的Jaccard系數(shù)是0.2

而C1中的{a,b,c}和C2中的{a,b,f}的Jaccard系數(shù)是0.5說明：僅根據(jù)Jaccard系數(shù)，很容易導致錯誤。第25頁，課件共34頁，創(chuàng)作于2023年2月另一方面，如果考慮鏈接數(shù)，可以成功地把這些事務劃分到恰當?shù)卮刂?。例如：令?0.5，則C2中的事務

{a,b,f}與{a,b,g}的鏈接數(shù)是5

而C2中的事務{(diào)a,b,f}與C1中的事務{(diào)a,b,c}之間的鏈接數(shù)是3.因此，ROCK能夠正確地區(qū)分出兩個不同的事務簇。第26頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類27Chameleon利用動態(tài)建模的層次聚類算法。采用動態(tài)建模確定簇之間的相似度。簇之間的相似度依據(jù)簇中對象的互連度和簇的鄰近度，即如果兩個簇的互連性都很高且它們又靠得很近則將其合并。第27頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類28變色龍算法的聚類步驟Chameleon算法首先由數(shù)據(jù)集構(gòu)造成一個K-最近鄰圖Gk,再通過一個圖的劃分算法將圖Gk劃分成大量的子圖,每個子圖代表一個初始子簇,最后用一個凝聚的層次聚類算法反復合并子簇，找到真正的結(jié)果簇；第28頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類29K最近鄰圖Gk圖中的每個點表示數(shù)據(jù)集中的一個數(shù)據(jù)點；若數(shù)據(jù)點ai到另一個數(shù)據(jù)點bi的距離值是所有數(shù)據(jù)點到數(shù)據(jù)點bi的距離值中K個最小值之一,則稱數(shù)據(jù)點ai是數(shù)據(jù)點bi的K-最臨近對象，則在這兩個點之間加一條帶權(quán)邊,邊的權(quán)重表示這兩個數(shù)據(jù)點之間的近似度,即它們之間的距離越大,則它們之間的近似度越小,它們之間的邊的權(quán)重也越小。第29頁，課件共34頁，創(chuàng)作于2023年2月2023/7/24層次聚類30割邊圖劃分算法劃分k近鄰圖，使得割邊最小，即簇C劃分為兩個子簇C