上傳人：石***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：藍(lán)**（實(shí)名認(rèn)證）

IP屬地：廣東

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

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

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。找出平均相異度最大的點(diǎn)1放到splintergroup中，剩余點(diǎn)在oldparty中。第2步，在oldparty里找出到最近的splintergroup中的點(diǎn)的距離不大于到oldparty中最近的點(diǎn)的距離的點(diǎn)，將該點(diǎn)放入splintergroup中，該點(diǎn)是2。第3步，重復(fù)第2步的工作，splintergroup中放入點(diǎn)3。第4步，重復(fù)第2步的工作，splintergroup中放入點(diǎn)4。第5步，沒有在oldparty中的點(diǎn)放入了splintergroup中且達(dá)到終止條件（k=2），程序終止。如果沒有到終止條件，因該從分裂好的簇中選一個(gè)直徑最大的簇繼續(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頁，2023年，2月20日，星期六2023/4/21層次聚類18層次聚類方法的改進(jìn)層次聚類方法盡管簡單，但經(jīng)常會遇到合并或分裂點(diǎn)的選擇的困難。改進(jìn)層次方法的聚類質(zhì)量的一個(gè)有希望的方向是將層次聚類和其他聚類技術(shù)進(jìn)行集成，形成多階段聚類。下面介紹3個(gè)改進(jìn)的層次聚類方法BIRTH，ROCK和Chameleon。第18頁，共34頁，2023年，2月20日，星期六2023/4/21層次聚類19BIRCH算法BIRCH（BalancedIterativeReducingandClustering）利用層次方法的平衡迭代歸約和聚類用聚類特征（CF）和聚類特征樹來概括聚類描述。該算法通過聚類特征可以方便地進(jìn)行中心、半徑、直徑及類內(nèi)、類間距離的運(yùn)算。第19頁，共34頁，2023年，2月20日，星期六2023/4/21層次聚類20聚類特征（CF）CF(ClusteringFeature)：包含簇信息的三元組(N,LS,SS)，N：簇的數(shù)據(jù)點(diǎn)；LS：線性和；SS：平方和假定在簇C1中有三個(gè)點(diǎn)(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頁，2023年，2月20日，星期六2023/4/21層次聚類21聚類特征樹CF樹是一個(gè)具有兩個(gè)參數(shù)分支因子B和閾值T的高度平衡樹。分支因子B：非葉節(jié)點(diǎn)可以擁有的孩子數(shù)閾值T：葉子節(jié)點(diǎn)中的子聚類的最大直徑第21頁，共34頁，2023年，2月20日，星期六2023/4/21層次聚類22

階段一：掃描數(shù)據(jù)庫，建立一個(gè)初始的CF樹，它可以被看作一個(gè)數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)內(nèi)在的聚類結(jié)構(gòu)。當(dāng)一個(gè)對象被插入到最近的葉節(jié)點(diǎn)（子聚類）中時(shí)，隨著對象的插入，CF樹被動態(tài)地構(gòu)造，因此，BIRTH方法對增量或動態(tài)聚類也非常有效。階段二：采用某個(gè)聚類算法對CF樹的葉節(jié)點(diǎn)進(jìn)行聚類。在這個(gè)階段可以執(zhí)行任何聚類算法。BIRCH算法第22頁，共34頁，2023年，2月20日，星期六2023/4/21層次聚類23ROCKROCK(RobustClusteringusinglinKs,使用連接的魯棒聚類大多數(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)行聚類。第23頁，共34頁，2023年，2月20日，星期六2023/4/21層次聚類24ROCK兩個(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)注相似度的聚類方法更加魯棒。第24頁，共34頁，2023年，2月20日，星期六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}之間的Jaccard系數(shù)是0.2

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

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

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