數(shù)據(jù)挖掘?qū)哟尉垲?lèi)

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

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

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

階段一：掃描數(shù)據(jù)庫(kù)，建立一個(gè)初始的CF樹(shù)，它可以被看作一個(gè)數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)內(nèi)在的聚類(lèi)結(jié)構(gòu)。當(dāng)一個(gè)對(duì)象被插入到最近的葉節(jié)點(diǎn)（子聚類(lèi)）中時(shí)，隨著對(duì)象的插入，CF樹(shù)被動(dòng)態(tài)地構(gòu)造，因此，BIRTH方法對(duì)增量或動(dòng)態(tài)聚類(lèi)也非常有效。階段二：采用某個(gè)聚類(lèi)算法對(duì)CF樹(shù)的葉節(jié)點(diǎn)進(jìn)行聚類(lèi)。在這個(gè)階段可以執(zhí)行任何聚類(lèi)算法。BIRCH算法第22頁(yè)，共34頁(yè)，2023年，2月20日，星期六2023/4/21層次聚類(lèi)23ROCKROCK(RobustClusteringusinglinKs,使用連接的魯棒聚類(lèi)大多數(shù)聚類(lèi)算法在進(jìn)行聚類(lèi)時(shí)只估計(jì)點(diǎn)與點(diǎn)之間的相似度，即在每一步中那些最相似的幾個(gè)點(diǎn)合并到一個(gè)簇中。這種“局部”方法很容易導(dǎo)致錯(cuò)誤。例如：兩個(gè)完全不同的簇可能有少數(shù)幾個(gè)點(diǎn)的距離較近，僅僅依據(jù)點(diǎn)與點(diǎn)之間的相似度來(lái)做出聚類(lèi)決定就會(huì)導(dǎo)致這兩個(gè)簇合并。ROCK采用一種比較全局的觀點(diǎn)，通過(guò)考慮成對(duì)點(diǎn)的鄰域情況進(jìn)行聚類(lèi)。第23頁(yè)，共34頁(yè)，2023年，2月20日，星期六2023/4/21層次聚類(lèi)24ROCK兩個(gè)概念：近鄰和鏈接近鄰：兩個(gè)點(diǎn)pi和pj是近鄰，如果sim(pi,pj)>=θ,sim是相似度函數(shù)，θ是指定的閾值鏈接：兩個(gè)點(diǎn)pi和pj的鏈接數(shù)定義為這兩點(diǎn)的共同近鄰個(gè)數(shù)。由于在確定點(diǎn)對(duì)之間的關(guān)系時(shí)考慮鄰近的數(shù)據(jù)點(diǎn)，因此比只關(guān)注相似度的聚類(lèi)方法更加魯棒。第24頁(yè)，共34頁(yè)，2023年，2月20日，星期六ROCK例：購(gòu)物籃數(shù)據(jù)庫(kù)包含關(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說(shuō)明：僅根據(jù)Jaccard系數(shù)，很容易導(dǎo)致錯(cuò)誤。第25頁(yè)，共34頁(yè)，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頁(yè)，共34頁(yè)，2023年，2月20日，星期六2023/4/21層次聚類(lèi)27Chameleon利用動(dòng)態(tài)建模的層次聚類(lèi)算法。采用動(dòng)態(tài)建模確定簇之間的相似度。簇之間的相似度依據(jù)簇中對(duì)象的互連度和簇的鄰近度，即如果兩個(gè)簇的互連性都很高且它們又靠得很近則將其合并。第27頁(yè)，共34頁(yè)，2023年，2月20日，星期六2023/4/21層次聚類(lèi)28變色龍算法的聚類(lèi)步驟Chameleon算法首先由數(shù)據(jù)集構(gòu)造成一個(gè)K-最近鄰圖Gk,再通過(guò)一個(gè)圖的劃分算法將圖Gk劃分成大量的子圖,每個(gè)子圖代表一個(gè)初始子簇,最后用一個(gè)凝聚的層次聚類(lèi)算法反復(fù)合并子簇，找到真正的結(jié)果簇；第28頁(yè)，共34頁(yè)，2023年，2月20日，星期六2023/4/21層次聚類(lèi)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è)最小值之一,則稱(chēng)數(shù)據(jù)點(diǎn)ai是數(shù)據(jù)點(diǎn)bi的K-最臨近對(duì)象，則在這兩個(gè)點(diǎn)之間加一條帶權(quán)邊,邊的權(quán)重表示這兩個(gè)數(shù)據(jù)點(diǎn)之間的近似度,即它們之間的距離越大,則它們之間的近似度越小,它們之間的邊的權(quán)重也越小。第29頁(yè)，共34頁(yè)，2023年，2月20日，星期六2023/4/21層次聚類(lèi)30割邊圖劃分算法劃分k近鄰圖，使得割邊最小，即簇C劃分為兩個(gè)子簇Ci和C