聚類分析層次聚類課件

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

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

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

最小距離：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’|是兩個對象p和p’之間的距離

mi是簇Ci

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

12/17/2022層次方法(續(xù))四個廣泛采用的簇間距離度量方法12/14/2層次方法(續(xù))層次聚類的主要缺點不具有很好的可伸縮性:時間復(fù)雜性至少是O(n2),其中n

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

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

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

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

12/17/2022BIRCH(1996)Birch(BalancedIt聚類特征ClusteringFeature:CF=(N,LS,SS)N:數(shù)據(jù)點數(shù)目LS:Ni=1XiSS:Ni=1Xi2CF=(5,(16,30),(54,190))(3,4)(2,6)(4,5)(4,7)(3,8)12/17/2022聚類特征ClusteringFeature:CF=(N聚類特征假定簇C1中有兩個點（1，2，3），（3，2，1），簇C2有三個點（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））12/17/2022聚類特征假定簇C1中有兩個點（1，2，3），（3，2，1），簇的質(zhì)心和簇的半徑。假如一個簇中包含n個數(shù)據(jù)點：{Xi}，i=1,2,3...n.，則質(zhì)心C和半徑R計算公式如下：C=(X1+X2+...+Xn)/n，（這里X1+X2+...+Xn是向量加）R=(|X1-C|^2+|X2-C|^2+...+|Xn-C|^2)/n

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

簇間距離這里的N，LS和SS是指兩簇合并后大簇的N，LS和SS。所謂兩簇合并只需要兩個對應(yīng)的CF相加那可12/17/2022有意思的是簇中心、簇半徑、簇直徑以及兩簇之間的距離D0到D3BIRCH的CF樹聚類特征從統(tǒng)計學(xué)的觀點來看，聚類特征是對給定子類統(tǒng)計匯總:子聚類的0階,1階和2階矩(moments)記錄了計算聚類和有效利用存儲的關(guān)鍵度量,并有效地利用了存儲,因為它匯總了關(guān)于子類的信息，而不是存儲所有的對象CF樹是高度平衡的樹，它存儲了層次聚類的聚類特征

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

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

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

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

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

是，更新CF值

否，是否可以添加一個新的元組

是，添加一個新的元組

否則，分裂最遠的一對元組，作為種子，按最近距離重新分配其它元組

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

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

?

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

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

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

階段四：通過上階段得出聚類質(zhì)心，將其作為種子節(jié)點，將其他對象分配給質(zhì)心，構(gòu)成新的聚類。12/17/2022Birch算法的階段：

?

階段一：掃描數(shù)據(jù)庫，構(gòu)造一顆CBIRCH算法流程如下圖所示：

BIRCH算法流程如下圖所示：

12/17/2022BIRCH算法流程如下圖所示：

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

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

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

12/17/2022CURE(續(xù))每個簇有多于一個的代表點使得CURE可以適應(yīng)非Cure(續(xù))CURE算法核心:從源數(shù)據(jù)對象中抽取一個隨機樣本集S.將樣本S分割為p個劃分,每個的大小為

s/p將每個劃分局部地聚類成s/pq

個簇刪除孤立點通過隨機選樣如果一個簇增長太慢,就刪除它.對局部聚類進行聚類.用相應(yīng)的簇標簽來標記數(shù)據(jù)12/17/2022Cure(續(xù))CURE算法核心:12/14/2022CURE:例s=50p=2s/p=25xxxyyyyxyxs/pq=512/17/2022CURE:例s=50xxxyyyyxyxs/pq=CURE:例(續(xù))多個代表點向重心以因子移動,進行收縮或凝聚多個代表點描述了每個簇的形狀xyxy12/17/2022CURE:例(續(xù))多個代表點向重心以因子移動,進行對分類數(shù)據(jù)聚類:ROCKROCK(RObustClusteringusinglinKs)由S.Guha,R.Rastogi,K.Shim提出(ICDE’99).使用鏈接(link)度量相似性/接近性鏈接：兩個對象間共同的近鄰的數(shù)目不是基于距離的計算復(fù)雜性:基本思想:相似性函數(shù):Jaccard系數(shù)

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

k-最近鄰圖Gk動態(tài)地捕捉鄰域的概念：一個對象的鄰域半徑由對象所在區(qū)域的密度所決定在一個密集區(qū)域,鄰域的定義范圍相對狹窄;在一個稀疏區(qū)域,它的定義范圍相對較寬

區(qū)域的密度作為邊的權(quán)重被記錄下來一個密集區(qū)域的邊趨向于比稀疏區(qū)域的邊有更大的權(quán)重

12/17/2022CHAMELEON(續(xù))k-最近鄰圖Gk:圖中的每個點代表CHAMELEON(續(xù))Chameleon通過兩個簇的相對互連性RI(Ci,Cj)和相對接近度RC(Ci,Cj)來決定簇間的相似度

RI(Ci,Cj)定義為Ci和Cj之間的絕對互聯(lián)性關(guān)于兩個簇的內(nèi)部互連性的規(guī)范化

其中,EC{Ci，Cj}是包含Ci和Cj的簇分裂為Ci和Cj的割邊,ECCi（或ECCj）是它的最小截斷等分線的大小（即將圖劃分為兩個大致相等的部分需要切斷的邊的加權(quán)和）

12/17/2022CHAMELEON(續(xù))Chameleon通過兩個簇的相對互CHAMELEON(續(xù))RC(Ci,Cj)定義為Ci和Cj之間的絕對接近度關(guān)于兩個簇的內(nèi)部接近度的規(guī)范化

其中,是連接Ci和Cj頂點的邊的平均權(quán)重

是Ci的最小二等分的邊的平均權(quán)重

12/17/2022CHAMELEON(續(xù))RC(Ci,Cj)定義為Ci和Cj作業(yè)（Duedate：11月9日）專題思路：把搜下來的網(wǎng)頁進行聚類，將聚類結(jié)果顯示給用戶，用戶可以選擇其中的一個類，標為關(guān)注，類的關(guān)鍵詞作為主題，用戶就可以跟蹤這主題、了解主題的文章的情感（就是其它部分的功能）12/17/2022作業(yè)（Duedate：11月9日）專智能數(shù)據(jù)挖掘Topic3--聚類分析層次聚類方法（HierarchicalMethods）智能數(shù)據(jù)挖掘Topic3--聚類分析層次方法層次的聚類方法將數(shù)據(jù)對象組成一棵聚類的樹根據(jù)層次分解是自底向上,還是自頂向下形成,層次的聚類方法可以進一步分為凝聚的(agglomerative)和分裂的(divisive)層次聚類

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

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

最小距離：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’|是兩個對象p和p’之間的距離

mi是簇Ci

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

12/17/2022層次方法(續(xù))四個廣泛采用的簇間距離度量方法12/14/2層次方法(續(xù))層次聚類的主要缺點不具有很好的可伸縮性:時間復(fù)雜性至少是O(n2),其中n

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

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

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

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

12/17/2022BIRCH(1996)Birch(BalancedIt聚類特征ClusteringFeature:CF=(N,LS,SS)N:數(shù)據(jù)點數(shù)目LS:Ni=1XiSS:Ni=1Xi2CF=(5,(16,30),(54,190))(3,4)(2,6)(4,5)(4,7)(3,8)12/17/2022聚類特征ClusteringFeature:CF=(N聚類特征假定簇C1中有兩個點（1，2，3），（3，2，1），簇C2有三個點（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））12/17/2022聚類特征假定簇C1中有兩個點（1，2，3），（3，2，1），簇的質(zhì)心和簇的半徑。假如一個簇中包含n個數(shù)據(jù)點：{Xi}，i=1,2,3...n.，則質(zhì)心C和半徑R計算公式如下：C=(X1+X2+...+Xn)/n，（這里X1+X2+...+Xn是向量加）R=(|X1-C|^2+|X2-C|^2+...+|Xn-C|^2)/n

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

簇間距離這里的N，LS和SS是指兩簇合并后大簇的N，LS和SS。所謂兩簇合并只需要兩個對應(yīng)的CF相加那可12/17/2022有意思的是簇中心、簇半徑、簇直徑以及兩簇之間的距離D0到D3BIRCH的CF樹聚類特征從統(tǒng)計學(xué)的觀點來看，聚類特征是對給定子類統(tǒng)計匯總:子聚類的0階,1階和2階矩(moments)記錄了計算聚類和有效利用存儲的關(guān)鍵度量,并有效地利用了存儲,因為它匯總了關(guān)于子類的信息，而不是存儲所有的對象CF樹是高度平衡的樹，它存儲了層次聚類的聚類特征

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

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

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

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

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

是，更新CF值

否，是否可以添加一個新的元組

是，添加一個新的元組

否則，分裂最遠的一對元組，作為種子，按最近距離重新分配其它元組

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

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

?

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

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

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

階段四：通過上階段得出聚類質(zhì)心，將其作為種子節(jié)點，將其他對象分配給質(zhì)心，構(gòu)成新的聚類。12/17/2022Birch算法的階段：

?

階段一：掃描數(shù)據(jù)庫，構(gòu)造一顆CBIRCH算法流程如下圖所示：

BIRCH算法流程如下圖所示：

12/17/2022BIRCH算法流程如下圖所示：

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

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

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

12/17/2022CURE(續(xù))每個簇有多于一個的代表點使得CURE可以適應(yīng)非Cure(續(xù))CURE算法核心:從源數(shù)據(jù)對象中抽取一個隨機樣本集S.將樣本S分割為p個劃分,每個的大小為

s/p將每個劃分局部地聚類成s/pq

個簇刪除孤立點通過隨機選樣如果一個簇增長太慢,就刪除它.對局部聚類進行聚類.用相應(yīng)的簇標簽來標記數(shù)據(jù)12/17/2022Cure(續(xù))CURE算法核心:12/14/2022CURE:例s=50p=2s/p=25xxxyyyyxyxs/pq=512/17/2022CURE:例s=50xxxyyyyxyxs/pq=CURE:例(續(xù))多個代表點向重心以因子移動,進行收縮或凝聚多個代表點描述了每個簇的形狀xyxy12/17/2022CURE:例(續(xù))多個代表點向重心以因子移動,進行對分類數(shù)據(jù)聚類:ROCKROCK(RObustClusteringusinglinKs)由S.Guha,R.Rastogi,K.Shim提出(ICDE’99).使用鏈接(link)度量相似性/接近性鏈接：兩個對象間共同的近鄰的數(shù)目不是基于距離的計算復(fù)雜性:基本思想:相似性函數(shù):Jaccard系數(shù)

設(shè)T1={1,2,3},T2={3,4,5}