姓名：梁祥????????學(xué)號：17021210935
【嵌牛導(dǎo)讀】：層次聚類方法作為一種能夠在一定程度上將聚類過程顯化的聚類方法，在很多時候都能大顯身手全闷，因此在這里介紹一下層次聚類方法的主要思想，并以BIRCH算法為例進行了詳細分析斑鸦。
【嵌牛鼻子】：層次聚類担租，BIRCH
【嵌牛提問】：層次聚類過程中，從頭到腳與自下而上有區(qū)別嗎喷众？在聚類的過程中數(shù)據(jù)是怎么慢慢分散或者逐漸聚攏的呢？
【嵌牛正文】：
一紧憾、層次聚類
層次的聚類方法將數(shù)據(jù)對象組成一棵聚類的樹到千。根據(jù)層次分解是底向上, 還是自頂向下形成, 層次的聚類方法可以進一步分為凝聚的(agglomerative)和分裂的(divisive)層次聚類。
凝聚的和分裂的層次聚類圖示：
層次聚類的主要缺點：
不具有很好的可伸縮性：時間復(fù)雜性至少是平方級赴穗；合并和分裂的決定需要檢查和估算大量的對象或簇憔四；不能撤銷已做的處理，聚類之間不能交換對象般眉。如果某一步?jīng)]有很好地選擇合并或分裂的決定了赵，可能會導(dǎo)致低質(zhì)量的聚類結(jié)果。該算法的特點是能利用有限的內(nèi)存資源完成對大數(shù)據(jù)集的高質(zhì)量的聚類甸赃，同時通過單遍掃描數(shù)據(jù)集能最小化I/O代價柿汛。
二、 改進層次方法的聚類質(zhì)量的方法:
將層次聚類和其他的聚類技術(shù)進行集成, 形成多階段聚類埠对。其中络断，BIRCH方法使用CF-tree對對象進行層次劃分裁替，然后采用其他的聚類算法對聚類結(jié)果進行求精。
2.1 兩個重要的概念：
聚類特征（Clustering Feature貌笨，CF）
聚類特征樹（Cluttering Feature Tree胯究，CF樹）
2.2 聚類特征
聚類特征(CF)是一個三元組，給出對象子類的信息的匯總描述躁绸。
設(shè)某個子類中有N個d維的點或?qū)ο笤Ｑ瑒t該子類的CF定義如下：
其中，N表示數(shù)據(jù)點數(shù)目净刮，LS表示全體數(shù)據(jù)的和剥哑，SS表示全體數(shù)據(jù)的平方和。從統(tǒng)計學(xué)的觀點來看淹父，聚類特征是對給定子類統(tǒng)計匯總: 子聚類的0階, 1階和 2階矩株婴。記錄了計算聚類和有效利用存儲的關(guān)鍵度量, 并有效地利用了存儲,因為它匯總了關(guān)于子類的信息，而不是存儲所有的對象暑认。
2.3 聚類特征樹
CF 樹是高度平衡的樹困介，它存儲了層次聚類的聚類特征。樹中的非葉節(jié)點有后代或“孩子”蘸际，非葉節(jié)點存儲了其孩子的CF的總和座哩，即匯總了關(guān)于其孩子的聚類信息。CF樹有兩個參數(shù) ----影響CF樹的大辛竿：分支因子B根穷，定義非樹葉節(jié)點的孩子的最大個數(shù)；閾值T:导坟，給出了存儲在樹的葉子節(jié)點中的子類的最大直徑屿良。
CF tree的結(jié)構(gòu)類似于一棵B-樹，它有3個參數(shù)：內(nèi)部節(jié)點平衡因子B惫周，葉節(jié)點平衡因子L尘惧，簇直徑閾值T。樹中每個Nlonleaf節(jié)點最多包含B個孩子節(jié)點递递，Leaf最多只能有L個MinCluster（初始劃分子簇）喷橙，而一個MinCluster的直徑不能超過T。
CF樹構(gòu)造過程：
(1)從根節(jié)點開始漾狼，自上而下選擇最近的孩子節(jié)點重慢；
(2)到達葉子節(jié)點后，檢查最近的元組CFi能否吸收此數(shù)據(jù)點逊躁；
????是，更新CF值隅熙；
????否稽煤，是否可以添加一個新的元組核芽；
????????是，添加一個新的元組酵熙；
????????否則轧简，分裂最遠的一對元組，作為種子匾二，按最近距離重新分配其它元組哮独；
(3)更新每個非葉節(jié)點的CF信息，如果分裂節(jié)點察藐，在父節(jié)點中插入新的元組皮璧，檢查分裂，直到root分飞。
算法起初悴务，我們掃描數(shù)據(jù)庫，拿到第一個data point instance--（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值晕换。
當(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值。
插入新節(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遏考。
重建過程從舊樹的葉子節(jié)點建造一個新樹。這樣蓝谨，重建樹的過程不需要重讀所有的對象 ----建樹只需讀一次數(shù)據(jù)灌具。在階段三和四采用任何聚類算法，例如典型的劃分方法譬巫。
2.3 BIRCH的性能
支持增量聚類：（1）因為它對每一個數(shù)據(jù)點的聚類的決策都是基于當(dāng)前已經(jīng)處理過的數(shù)據(jù)點咖楣，而不是基于全局的數(shù)據(jù)點。（2）線性可伸縮性: 計算復(fù)雜性O(shè)(n), 單遍掃描, 附加的掃描可以改善聚類質(zhì)量芦昔。（3）具有較好的聚類質(zhì)量诱贿。
2.4 缺點
（1）只能處理數(shù)值數(shù)據(jù)；（2）對數(shù)據(jù)的輸入次序敏感咕缎；（3）CF樹結(jié)點不總是對應(yīng)于[用戶考慮的]自然簇(參數(shù)B和T)珠十；（4）簇非球形時效果不好(使用半徑/直徑控制簇邊界).
