聚類分析-層次聚類

智能數(shù)據(jù)挖掘Topic3--聚類分析層次聚類方法（HierarchicalMethods）層次方法層次的聚類方法將數(shù)據(jù)對(duì)象組成一棵聚類的樹根據(jù)層次分解是自底向上,還是自頂向下形成,層次的聚類方法可以進(jìn)一步分為凝聚的(agglomerative)和分裂的(divisive)層次聚類

純粹的層次聚類方法的聚類質(zhì)量受限于如下特點(diǎn)：一旦一個(gè)合并或分裂被執(zhí)行，就不能修正最近的研究集中于凝聚層次聚類和迭代重定位方法的集成

使用距離矩陣作為聚類標(biāo)準(zhǔn).該方法不需要輸入聚類數(shù)目k,但需要終止條件11/10/2023層次方法(續(xù))凝聚的(agglomerative)和分裂的(divisive)層次聚類圖示Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)11/10/2023AGNES(AgglomerativeNesting)由Kaufmann和Rousseeuw提出(1990)已在一些統(tǒng)計(jì)分析軟件包中實(shí)現(xiàn).如Splus使用單鏈接(Single-Link)方法和相異度矩陣合并具有最小相異度的節(jié)點(diǎn)以非遞減的方式繼續(xù)最終所有的節(jié)點(diǎn)屬于同一個(gè)簇11/10/2023DIANA(DivisiveAnalysis)由Kaufmann和Rousseeuw提出(1990)已在一些統(tǒng)計(jì)分析軟件包中實(shí)現(xiàn).如Splus是AGNES的逆最終每個(gè)節(jié)點(diǎn)自己形成一個(gè)簇11/10/2023層次方法(續(xù))四個(gè)廣泛采用的簇間距離度量方法

最小距離：dmin(Ci,Cj)=min

p∈Ci,p’∈Cj

|p-p’|

最大距離：dmax(Ci,Cj)=max

p∈Ci,p’∈Cj|p-p’|

平均值的距離：dmean(Ci,Cj)=|mi-mj|

平均距離(簇的直徑D)：davg(Ci,Cj)=∑p∈Ci∑p’∈Cj|p-p’|

/ninj其中,|p-p’|是兩個(gè)對(duì)象p和p’之間的距離

mi是簇Ci

的平均值，ni是簇Ci中對(duì)象的數(shù)目

11/10/2023層次方法(續(xù))層次聚類的主要缺點(diǎn)不具有很好的可伸縮性:時(shí)間復(fù)雜性至少是O(n2),其中n

對(duì)象總數(shù)合并或分裂的決定需要檢查和估算大量的對(duì)象或簇不能撤消已做的處理,聚類之間不能交換對(duì)象.如果某一步?jīng)]有很好地選擇合并或分裂的決定,可能會(huì)導(dǎo)致低質(zhì)量的聚類結(jié)果

11/10/2023層次方法(續(xù))改進(jìn)層次方法的聚類質(zhì)量的方法:將層次聚類和其他的聚類技術(shù)進(jìn)行集成,形成多階段聚類BIRCH(1996):使用CF-tree對(duì)對(duì)象進(jìn)行層次劃分,然后采用其他的聚類算法對(duì)聚類結(jié)果進(jìn)行求精ROCK1999：基于簇間的互聯(lián)性進(jìn)行合并CHAMELEON(1999):使用動(dòng)態(tài)模型進(jìn)行層次聚類CURE(1998):采用固定數(shù)目的代表對(duì)象來表示每個(gè)簇，然后依據(jù)一個(gè)指定的收縮因子向著聚類中心對(duì)它們進(jìn)行收縮11/10/2023BIRCH(1996)Birch(BalancedIterativeReducingandClusteringusingHierarchies):利用層次方法的平衡迭代歸約和聚類由Zhang,Ramakrishnan和Livny提出(SIGMOD’96),該算法的特點(diǎn)是能利用有限的內(nèi)存資源完成對(duì)大數(shù)據(jù)集的高質(zhì)量的聚類，同時(shí)通過單遍掃描數(shù)據(jù)集能最小化I/O代價(jià)。

兩個(gè)重要概念聚類特征(ClusteringFeature,CF)聚類特征樹(ClusteringFeatureTree,

CF樹)聚類特征聚類特征(CF)是一個(gè)三元組，給出對(duì)象子類的信息的匯總描述設(shè)某個(gè)子類中有N個(gè)d維的點(diǎn)或?qū)ο髙oI}，則該子類的CF定義如下

11/10/2023聚類特征ClusteringFeature:CF=(N,LS,SS)N:數(shù)據(jù)點(diǎn)數(shù)目LS:

Ni=1XiSS:

Ni=1Xi2CF=(5,(16,30),(54,190))(3,4)(2,6)(4,5)(4,7)(3,8)11/10/2023聚類特征假定簇C1中有兩個(gè)點(diǎn)（1，2，3），（3，2，1），簇C2有三個(gè)點(diǎn)（1，1，2），（2，2，1），（2，1，2），簇3由C1和C2構(gòu)成，則：CF1=（2，（1+3，2+2，3+1），（

））=（2，（4，4，4），（10，8，10））CF2=（3，（1+2+2，1+2+1，2+1+2），（

））=（3，（5，4，5），（9，6，9））因此得到CF3為：CF3=（2+3，（4+5，4+4，4+5），（10+9，8+6，10+9））=（5，（9，8，9），（19，14，19））11/10/2023簇的質(zhì)心和簇的半徑。假如一個(gè)簇中包含n個(gè)數(shù)據(jù)點(diǎn)：{Xi}，i=1,2,3...n.，則質(zhì)心C和半徑R計(jì)算公式如下：C=(X1+X2+...+Xn)/n，（這里X1+X2+...+Xn是向量加）R=(|X1-C|^2+|X2-C|^2+...+|Xn-C|^2)/n

其中，簇半徑表示簇中所有點(diǎn)到簇質(zhì)心的平均距離。CF中存儲(chǔ)的是簇中所有數(shù)據(jù)點(diǎn)的特性的統(tǒng)計(jì)和，所以當(dāng)我們把一個(gè)數(shù)據(jù)點(diǎn)加入某個(gè)簇的時(shí)候，那么這個(gè)數(shù)據(jù)點(diǎn)的詳細(xì)特征，例如屬性值，就丟失了，由于這個(gè)特征，BIRCH聚類可以在很大程度上對(duì)數(shù)據(jù)集進(jìn)行壓縮。11/10/2023有意思的是簇中心、簇半徑、簇直徑以及兩簇之間的距離D0到D3都可以由CF來計(jì)算，比如簇直徑

簇間距離這里的N，LS和SS是指兩簇合并后大簇的N，LS和SS。所謂兩簇合并只需要兩個(gè)對(duì)應(yīng)的CF相加那可11/10/2023BIRCH的CF樹聚類特征從統(tǒng)計(jì)學(xué)的觀點(diǎn)來看，聚類特征是對(duì)給定子類統(tǒng)計(jì)匯總:子聚類的0階,1階和2階矩(moments)記錄了計(jì)算聚類和有效利用存儲(chǔ)的關(guān)鍵度量,并有效地利用了存儲(chǔ),因?yàn)樗鼌R總了關(guān)于子類的信息，而不是存儲(chǔ)所有的對(duì)象CF樹是高度平衡的樹，它存儲(chǔ)了層次聚類的聚類特征

樹中的非葉節(jié)點(diǎn)有后代或“孩子”

非葉節(jié)點(diǎn)存儲(chǔ)了其孩子的CF的總和，即匯總了關(guān)于其孩子的聚類信息

CF樹有兩個(gè)參數(shù)----影響CF樹的大小分支因子B:定義非樹葉節(jié)點(diǎn)的孩子的最大個(gè)數(shù)閾值T:給出了存儲(chǔ)在樹的葉子節(jié)點(diǎn)中的子類的最大直徑

11/10/2023CFtree的結(jié)構(gòu)類似于一棵B-樹，它有3個(gè)參數(shù)：內(nèi)部節(jié)點(diǎn)平衡因子B，葉節(jié)點(diǎn)平衡因子L，簇直徑閾值T。樹中每個(gè)Nlonleaf節(jié)點(diǎn)最多包含B個(gè)孩子節(jié)點(diǎn)，Leaf最多只能有L個(gè)MinCluster（初始劃分子簇），而一個(gè)MinCluster的直徑不能超過T。例如，一棵高度為3，B為6，L為5的一棵CF樹的例子如圖所示：11/10/2023CF樹的樣子11/10/2023CFTreeCF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB=5L=6RootNon-leafnodeLeafnodeLeafnode11/10/2023CF樹構(gòu)造過程(1)從根節(jié)點(diǎn)開始，自上而下選擇最近的孩子節(jié)點(diǎn)

(2)到達(dá)葉子節(jié)點(diǎn)后，檢查最近的元組CFi能否吸收此數(shù)據(jù)點(diǎn)

是，更新CF值

否，是否可以添加一個(gè)新的元組

是，添加一個(gè)新的元組

否則，分裂最遠(yuǎn)的一對(duì)元組，作為種子，按最近距離重新分配其它元組

(3)更新每個(gè)非葉節(jié)點(diǎn)的CF信息，如果分裂節(jié)點(diǎn)，在父節(jié)點(diǎn)中插入新的元組，檢查分裂，直到root

11/10/2023構(gòu)造CF樹算法起初，我們掃描數(shù)據(jù)庫，拿到第一個(gè)datapointinstance--（1,2,3）,我們創(chuàng)建一個(gè)空的Leaf和MinCluster，把點(diǎn)（1,2,3）的id值放入Mincluster，更新MinCluster的CF值為（1,（1,2,3），（1,4,9）），把MinCluster作為Leaf的一個(gè)孩子，更新Leaf的CF值為（1,（1,2,3），（1,4,9））。實(shí)際上只要往樹中放入一個(gè)CF（這里我們用CF作為Nonleaf、Leaf、MinCluster的統(tǒng)稱），就要更新從Root到該葉子節(jié)點(diǎn)的路徑上所有節(jié)點(diǎn)的CF值。11/10/2023插入一個(gè)節(jié)點(diǎn)當(dāng)又有一個(gè)數(shù)據(jù)點(diǎn)要插入樹中時(shí)，把這個(gè)點(diǎn)封裝為一個(gè)MinCluster（這樣它就有了一個(gè)CF值），把新到的數(shù)據(jù)點(diǎn)記為CF_new，我們拿到樹的根節(jié)點(diǎn)的各個(gè)孩子節(jié)點(diǎn)的CF值，根據(jù)D2來找到CF_new與哪個(gè)節(jié)點(diǎn)最近，就把CF_new加入那個(gè)子樹上面去。這是一個(gè)遞歸的過程。遞歸的終止點(diǎn)是要把CF_new加入到一個(gè)MinCluster中，如果加入之后MinCluster的直徑?jīng)]有超過T，則直接加入，否則譔CF_new要單獨(dú)作為一個(gè)簇，成為MinCluster的兄弟結(jié)點(diǎn)。插入之后注意更新該節(jié)點(diǎn)及其所有祖先節(jié)點(diǎn)的CF值。11/10/2023節(jié)點(diǎn)分裂插入新節(jié)點(diǎn)后，可能有些節(jié)點(diǎn)的孩子數(shù)大于了B（或L），此時(shí)該節(jié)點(diǎn)要分裂。對(duì)于Leaf，它現(xiàn)在有L+1個(gè)MinCluster，我們要新創(chuàng)建一個(gè)Leaf，使它作為原Leaf的兄弟結(jié)點(diǎn)，同時(shí)注意每新創(chuàng)建一個(gè)Leaf都要把它插入到雙向鏈表中。L+1個(gè)MinCluster要分到這兩個(gè)Leaf中，怎么分呢？找出這L+1個(gè)MinCluster中距離最遠(yuǎn)的兩個(gè)Cluster（根據(jù)D2），剩下的Cluster看離哪個(gè)近就跟誰站在一起。分好后更新兩個(gè)Leaf的CF值，其祖先節(jié)點(diǎn)的CF值沒有變化，不需要更新。這可能導(dǎo)致祖先節(jié)點(diǎn)的遞歸分裂，因?yàn)長eaf分裂后恰好其父節(jié)點(diǎn)的孩子數(shù)超過了B。Nonleaf的分裂方法與Leaf的相似，只不過產(chǎn)生新的Nonleaf后不需要把它放入一個(gè)雙向鏈表中。如果是樹的根節(jié)點(diǎn)要分裂，則樹的高度加1。11/10/2023Birch算法的階段：

?

階段一：掃描數(shù)據(jù)庫，構(gòu)造一顆CF樹，并定義相關(guān)閾值，把稠密數(shù)據(jù)分成簇。?

階段二：對(duì)CF樹進(jìn)行壓縮，通過改變T值，將部分簇進(jìn)行壓縮合并，建立一個(gè)更小的CF樹。?

階段三：采用其他的聚類算法對(duì)其葉節(jié)點(diǎn)進(jìn)行聚類，將稀疏的簇當(dāng)作離群值進(jìn)行刪除，補(bǔ)救由于輸入順序和頁面大小帶來的分裂。?

階段四：通過上階段得出聚類質(zhì)心，將其作為種子節(jié)點(diǎn)，將其他對(duì)象分配給質(zhì)心，構(gòu)成新的聚類。11/10/2023BIRCH算法流程如下圖所示：

BIRCH算法流程如下圖所示：

11/10/2023BIRCH(續(xù))重建過程從舊樹的葉子節(jié)點(diǎn)建造一個(gè)新樹。這樣，重建樹的過程不需要重讀所有的對(duì)象----建樹只需讀一次數(shù)據(jù)在階段三和四采用任何聚類算法，例如典型的劃分方法BIRCH的性能支持增量聚類：因?yàn)樗鼘?duì)每一個(gè)數(shù)據(jù)點(diǎn)的聚類的決策都是基于當(dāng)前已經(jīng)處理過的數(shù)據(jù)點(diǎn)，而不是基于全局的數(shù)據(jù)點(diǎn)。

線性可伸縮性:計(jì)算復(fù)雜性O(shè)(n),單遍掃描,附加的掃描可以改善聚類質(zhì)量較好的聚類質(zhì)量缺點(diǎn)只能處理數(shù)值數(shù)據(jù)對(duì)數(shù)據(jù)的輸入次序敏感CF樹結(jié)點(diǎn)不總是對(duì)應(yīng)于[用戶考慮的]自然簇(參數(shù)B和T)簇非球形時(shí)效果不好(使用半徑/直徑控制簇邊界)11/10/2023CURE(1998)CURE(ClusteringUsingREpresentatives):由Guha,Rastogi和Shim提出(1998)絕大多數(shù)聚類算法或者擅長處理球形和相似大小的聚類，或者在存在孤立點(diǎn)時(shí)變得比較脆弱CURE解決了偏好球形的問題，在處理孤立點(diǎn)上也更加健壯CURE采用了一種新的層次聚類算法選擇基于質(zhì)心和基于代表對(duì)象方法之間的中間策略.它不用單個(gè)質(zhì)心或?qū)ο髞泶硪粋€(gè)簇,而是選擇了數(shù)據(jù)空間中固定數(shù)目的具有代表性的點(diǎn)首先選擇簇中分散的對(duì)象,然后根據(jù)一個(gè)特定的收縮因子向簇中心“收縮”11/10/2023CURE(續(xù))每個(gè)簇有多于一個(gè)的代表點(diǎn)使得CURE可以適應(yīng)非球形的任意形狀的聚類簇的收縮或凝聚可以有助于控制孤立點(diǎn)的影響CURE的優(yōu)點(diǎn)CURE對(duì)孤立點(diǎn)的處理更加健壯能夠識(shí)別非球形和大小變化較大的簇對(duì)于大規(guī)模數(shù)據(jù)庫,它也具有良好的伸縮性,而且沒有犧牲聚類質(zhì)量

針對(duì)大型數(shù)據(jù)庫,CURE采用了隨機(jī)取樣和劃分兩種方法的組合首先劃分一個(gè)隨機(jī)樣本,每個(gè)劃分被部分聚類然后對(duì)這些結(jié)果簇聚類,產(chǎn)生希望的結(jié)果

11/10/2023Cure(續(xù))CURE算法核心:從源數(shù)據(jù)對(duì)象中抽取一個(gè)隨機(jī)樣本集S.將樣本S分割為p個(gè)劃分,每個(gè)的大小為

s/p將每個(gè)劃分局部地聚類成s/pq

個(gè)簇刪除孤立點(diǎn)通過隨機(jī)選樣如果一個(gè)簇增長太慢,就刪除它.對(duì)局部聚類進(jìn)行聚類.用相應(yīng)的簇標(biāo)簽來標(biāo)記數(shù)據(jù)11/10/2023CURE:例s=50p=2s/p=25xxxyyyyxyxs/pq=511/10/2023CURE:例(續(xù))多個(gè)代表點(diǎn)向重心以因子

移動(dòng),進(jìn)行收縮或凝聚多個(gè)代表點(diǎn)描述了每個(gè)簇的形狀xyxy11/10/2023對(duì)分類數(shù)據(jù)聚類:ROCKROCK(RObustClusteringusinglinKs)由S.Guha,R.Rastogi,K.Shim提出(ICDE’99).使用鏈接(link)度量相似性/接近性鏈接：兩個(gè)對(duì)象間共同的近鄰的數(shù)目不是基于距離的計(jì)算復(fù)雜性:基本思想:相似性函數(shù):Jaccard系數(shù)

設(shè)T1={1,2,3},T2={3,4,5}11/10/2023Rock(續(xù))兩個(gè)點(diǎn)pi和pj是近鄰，如果sim(pi,pj)>=用戶指定閾值link(pi,pj)是兩個(gè)點(diǎn)pi和pj共同的近鄰的數(shù)目兩個(gè)簇Ci和Cj的互連性被定義為兩個(gè)簇間交叉鏈（crosslink）的數(shù)目ROCK首先根據(jù)相似度閥值和共享近鄰的概念，從給定的數(shù)據(jù)相似度矩陣構(gòu)建一個(gè)稀疏的圖，然后在這個(gè)稀疏圖上運(yùn)行一個(gè)層次聚類算法11/10/2023CHAMELEONCHAMELEON:一個(gè)利用動(dòng)態(tài)模型的層次聚類算法(Hierarchicalclusteringusingdynamicmodeling)由G.Karypis,E.H.Han,andV.Kumar’99提出對(duì)CURE和ROCK缺點(diǎn)的觀察:Cure忽略了關(guān)于兩個(gè)不同簇中對(duì)象的聚集互連性的信息Rock強(qiáng)調(diào)對(duì)象間互連性,卻忽略了關(guān)于對(duì)象間近似度的信息CHAMELEON基于動(dòng)態(tài)模型度量相似性如果兩個(gè)簇間的互連性和近似度與簇內(nèi)部對(duì)象間的互連性和近似度高度相關(guān),則合并這兩個(gè)簇11/10/2023CHAMELEON(續(xù))兩階段算法使用圖劃分算法:將數(shù)據(jù)對(duì)象聚類為大量相對(duì)較小的子類逐步用圖劃分算法把k近鄰圖分成相對(duì)較小de子簇，最小化割邊。使用凝聚的層次聚類算法：通過反復(fù)地合并子類來找到真正的結(jié)果簇既考慮互連性,又考慮簇間的近似度,特別是簇內(nèi)部的特征,來確定最相似的子類.這樣,它不依賴于靜態(tài)的用戶提供的模型,能夠自動(dòng)地適應(yīng)被合并的簇的內(nèi)部特征割邊最小化——簇c劃分為兩個(gè)子簇Ci和Cj時(shí)需要割斷的邊的加權(quán)和最小。割邊用EC{Ci，Cj}表示，評(píng)估Ci和Cj的簇間的絕對(duì)互聯(lián)性。11/10/2023C