Birch層次聚類(lèi)算法

標(biāo)簽（空格分隔）： CF樹(shù)建立

主要借鑒的網(wǎng)文地址，并進(jìn)行大量引用：【非常淺顯易懂】
http://www.cnblogs.com/pinard/p/6179132.html 【主要以此文為主】
http://www.cnblogs.com/tiaozistudy/p/6129425.html
根據(jù)上述第二個(gè)網(wǎng)址的步驟，進(jìn)行代碼化的代碼地址：
https://github.com/AresAnt/ML-DL/tree/master/Clustering/Birch

BIRCH算法比較適合于數(shù)據(jù)量大，類(lèi)別數(shù)K也比較多的情況。它運(yùn)行速度很快，只需要單遍掃描數(shù)據(jù)集就能進(jìn)行聚類(lèi)，當(dāng)然需要用到一些技巧，下面我們就對(duì)BIRCH算法做一個(gè)總結(jié)。
【個(gè)人建議，如想要自己寫(xiě)CF樹(shù)生成代碼前，請(qǐng)先了解一下B+樹(shù)的構(gòu)造與寫(xiě)法對(duì)之后的代碼完成將會(huì)有幫助?！?/p>

1.聚類(lèi)特征CF與聚類(lèi)特征樹(shù)CF Tree

在聚類(lèi)特征樹(shù)中，一個(gè)聚類(lèi)特征CF是這樣定義的：每一個(gè)CF是一個(gè)三元組，可以用（N，LS，SS）表示。其中N代表了這個(gè)CF中擁有的樣本點(diǎn)的數(shù)量，這個(gè)好理解；LS代表了這個(gè)CF中擁有的樣本點(diǎn)各特征維度的和向量，SS代表了這個(gè)CF中擁有的樣本點(diǎn)各特征維度的平方和。舉個(gè)例子如下圖，在CF Tree中的某一個(gè)節(jié)點(diǎn)的某一個(gè)CF中，有下面5個(gè)樣本(3,4), (2,6), (4,5), (4,7), (3,8)。則它對(duì)應(yīng)的N=5， LS= (3+2+4+4+3,4+6+5+7+8) =(16,30), SS = (32+22+42+42+32+42+62+52+72+82) = (54+190) = 244。具體內(nèi)容可如下所示：

CF有一個(gè)很好的性質(zhì)，就是滿足線性關(guān)系，也就是CF1+CF2=(N1+N2,LS1+LS2,SS1+SS2)。這個(gè)性質(zhì)從定義也很好理解。如果把這個(gè)性質(zhì)放在CF Tree上，也就是說(shuō)，在CF Tree中，對(duì)于每個(gè)父節(jié)點(diǎn)中的CF節(jié)點(diǎn)，它的(N,LS,SS)三元組的值等于這個(gè)CF節(jié)點(diǎn)所指向的所有子節(jié)點(diǎn)的三元組之和。如下圖所示：

從上圖中可以看出，根節(jié)點(diǎn)的CF1的三元組的值，可以從它指向的6個(gè)子節(jié)點(diǎn)（CF7 - CF12）的值相加得到。這樣我們?cè)诟翪F Tree的時(shí)候，可以很高效。

對(duì)于CF Tree，我們一般有幾個(gè)重要參數(shù)，第一個(gè)參數(shù)是每個(gè)內(nèi)部節(jié)點(diǎn)的最大CF數(shù)B，第二個(gè)參數(shù)是每個(gè)葉子節(jié)點(diǎn)的最大CF數(shù)L，第三個(gè)參數(shù)是針對(duì)葉子節(jié)點(diǎn)中某個(gè)CF中的樣本點(diǎn)來(lái)說(shuō)的，它是葉節(jié)點(diǎn)每個(gè)CF的最大樣本半徑閾值T，也就是說(shuō)，在這個(gè)CF中的所有樣本點(diǎn)一定要在半徑小于T的一個(gè)超球體內(nèi)。對(duì)于上圖中的CF Tree，限定了B=7， L=5，也就是說(shuō)內(nèi)部節(jié)點(diǎn)最多有7個(gè)CF，而葉子節(jié)點(diǎn)最多有5個(gè)CF。

2.聚類(lèi)特征樹(shù)CF Tree的生成

下面我們看看怎么生成CF Tree。我們先定義好CF Tree的參數(shù)：即內(nèi)部節(jié)點(diǎn)的最大CF數(shù)B，葉子節(jié)點(diǎn)的最大CF數(shù)L，葉節(jié)點(diǎn)每個(gè)CF的最大樣本半徑閾值T

在最開(kāi)始的時(shí)候，CF Tree是空的，沒(méi)有任何樣本，我們從訓(xùn)練集讀入第一個(gè)樣本點(diǎn)，將它放入一個(gè)新的CF三元組A，這個(gè)三元組的N=1，將這個(gè)新的CF放入根節(jié)點(diǎn)，此時(shí)的CF Tree如下圖：

現(xiàn)在我們繼續(xù)讀入第二個(gè)樣本點(diǎn)，我們發(fā)現(xiàn)這個(gè)樣本點(diǎn)和第一個(gè)樣本點(diǎn)A，在半徑為T(mén)的超球體范圍內(nèi)，也就是說(shuō)，他們屬于一個(gè)CF，我們將第二個(gè)點(diǎn)也加入CF A,此時(shí)需要更新A的三元組的值。此時(shí)A的三元組中N=2。此時(shí)的CF Tree如下圖：

此時(shí)來(lái)了第三個(gè)節(jié)點(diǎn)，結(jié)果我們發(fā)現(xiàn)這個(gè)節(jié)點(diǎn)不能融入剛才前面的節(jié)點(diǎn)形成的超球體內(nèi)，也就是說(shuō)，我們需要一個(gè)新的CF三元組B，來(lái)容納這個(gè)新的值。此時(shí)根節(jié)點(diǎn)有兩個(gè)CF三元組A和B，此時(shí)的CF Tree如下圖：

當(dāng)來(lái)到第四個(gè)樣本點(diǎn)的時(shí)候，我們發(fā)現(xiàn)和B在半徑小于T的超球體，這樣更新后的CF Tree如下圖：

那個(gè)什么時(shí)候CF Tree的節(jié)點(diǎn)需要分裂呢？假設(shè)我們現(xiàn)在的CF Tree 如下圖，葉子節(jié)點(diǎn)LN1有三個(gè)CF， LN2和LN3各有兩個(gè)CF。我們的葉子節(jié)點(diǎn)的最大CF數(shù)L=3。此時(shí)一個(gè)新的樣本點(diǎn)來(lái)了，我們發(fā)現(xiàn)它離LN1節(jié)點(diǎn)最近，因此開(kāi)始判斷它是否在sc1,sc2,sc3這3個(gè)CF對(duì)應(yīng)的超球體之內(nèi)，但是很不幸，它不在，因此它需要建立一個(gè)新的CF，即sc8來(lái)容納它。問(wèn)題是我們的L=3，也就是說(shuō)LN1的CF個(gè)數(shù)已經(jīng)達(dá)到最大值了，不能再創(chuàng)建新的CF了，怎么辦？此時(shí)就要將LN1葉子節(jié)點(diǎn)一分為二了。

我們將LN1里所有CF元組中，找到兩個(gè)最遠(yuǎn)的CF做這兩個(gè)新葉子節(jié)點(diǎn)的種子CF，然后將LN1節(jié)點(diǎn)里所有CF sc1, sc2, sc3，以及新樣本點(diǎn)的新元組sc8劃分到兩個(gè)新的葉子節(jié)點(diǎn)上。將LN1節(jié)點(diǎn)劃分后的CF Tree如下圖：

如果我們的內(nèi)部節(jié)點(diǎn)的最大CF數(shù)B=3，則此時(shí)葉子節(jié)點(diǎn)一分為二會(huì)導(dǎo)致根節(jié)點(diǎn)的最大CF數(shù)超了，也就是說(shuō)，我們的根節(jié)點(diǎn)現(xiàn)在也要分裂，分裂的方法和葉子節(jié)點(diǎn)分裂一樣，分裂后的CF Tree如下圖：

有了上面這一系列的圖，相信大家對(duì)于CF Tree的插入就沒(méi)有什么問(wèn)題了，總結(jié)下CF Tree的插入：

從根節(jié)點(diǎn)向下尋找和新樣本距離最近的葉子節(jié)點(diǎn)和葉子節(jié)點(diǎn)里最近的CF節(jié)點(diǎn)
如果新樣本加入后，這個(gè)CF節(jié)點(diǎn)對(duì)應(yīng)的超球體半徑仍然滿足小于閾值T，則更新路徑上所有的CF三元組，插入結(jié)束。否則轉(zhuǎn)入3.
如果當(dāng)前葉子節(jié)點(diǎn)的CF節(jié)點(diǎn)個(gè)數(shù)小于閾值L，則創(chuàng)建一個(gè)新的CF節(jié)點(diǎn)，放入新樣本，將新的CF節(jié)點(diǎn)放入這個(gè)葉子節(jié)點(diǎn)，更新路徑上所有的CF三元組，插入結(jié)束。否則轉(zhuǎn)入4。
將當(dāng)前葉子節(jié)點(diǎn)劃分為兩個(gè)新葉子節(jié)點(diǎn)，選擇舊葉子節(jié)點(diǎn)中所有CF元組里超球體距離最遠(yuǎn)的兩個(gè)CF元組，分布作為兩個(gè)新葉子節(jié)點(diǎn)的第一個(gè)CF節(jié)點(diǎn)。將其他元組和新樣本元組按照距離遠(yuǎn)近原則放入對(duì)應(yīng)的葉子節(jié)點(diǎn)。依次向上檢查父節(jié)點(diǎn)是否也要分裂，如果需要按和葉子節(jié)點(diǎn)分裂方式相同

3.Birch算法流程

如不愿看下列粗糙流程，可以參考：http://www.cnblogs.com/tiaozistudy/p/twostep_cluster_algorithm.html【之前給出的第二個(gè)網(wǎng)站，根據(jù)其步驟進(jìn)行操作】

# 獲取的初始化參數(shù)的值，枝平衡銀子β，葉平衡因子λ，空間閾值T，以及是否
class Birch_Class():

    # 獲取的初始化參數(shù)的值，枝平衡因子β，葉平衡因子λ，空間閾值T，以及是否
    def __init__(self,branch_balance=2,leaf_balance=3,threshold=3,compute_labels=True):
        self.branch_balance = branch_balance
        self.leaf_balance = leaf_balance
        self.threshod = threshold
        self.compute_labels=compute_labels

傳入?yún)?shù):

分支平衡參數(shù)： branch_balance
葉子平衡參數(shù)： leaf_balance
空間閾值： threshold
---以上三者數(shù)據(jù)用來(lái)初始化類(lèi)的基本屬性

1.初始化CF樹(shù)為空樹(shù)（建立一個(gè)TreeNode,每個(gè)TreeNode有N個(gè)CFNode）【N與分支平衡因子與葉平衡因子有關(guān)】
2.逐條導(dǎo)入數(shù)據(jù)（后面統(tǒng)一用簇來(lái)代替），進(jìn)行CF樹(shù)的填充
3.判斷當(dāng)前插入的簇與TreeNode中最近的的CFNode（CF簇），然后篩選出該簇，進(jìn)行同樣的遞歸計(jì)算，直到葉子節(jié)點(diǎn)。

#偽代碼：
    if TreeNode is Leaf:
        find nearest CFNode
    else:
        TreeNode = min(Dist(TreeNode.CFnode,傳進(jìn)來(lái)的簇))

4.到葉子節(jié)點(diǎn)后發(fā)現(xiàn)，不滿足葉平衡因子，或計(jì)算的閾值超出了范圍，則進(jìn)行葉節(jié)點(diǎn)分裂。
5.葉節(jié)點(diǎn)分裂后，會(huì)增加分支節(jié)點(diǎn)上的CFNode增加，此時(shí)需要判斷增加CFNode后的TreeNode是否滿足分支平衡因子，如果不滿足則當(dāng)前分支節(jié)點(diǎn)進(jìn)行分裂，同時(shí)上一層的分支節(jié)點(diǎn)進(jìn)行CFNode數(shù)量增加。

#偽代碼：
    # 計(jì)算葉節(jié)點(diǎn)是否要分裂,len(TreeNode)就是指CFNode的數(shù)量
    if len(TreeNode) < leaf_balance or Dist(CFNode,傳入的簇) < threshold:
        TreeNode.add(CFNode)
    else:
        TreeNode.split()
        
        # 分裂后，判斷上一層分支數(shù)量會(huì)不會(huì)超出
        @遞歸的函數(shù) 
        if len(TreeNode.parent) < branch_balance:
            TreeNode.parent.add(TreeNode)
        else:
            TreeNode = TreeNode.parent （開(kāi)始上面的函數(shù)遞歸）

6.簇插入到葉子節(jié)點(diǎn)時(shí)候，需要更新當(dāng)前插入路徑下的聚類(lèi)特征值，即L，SS，LS等
7.輸出CF樹(shù)，然后可以進(jìn)行優(yōu)化

4.Birch算法小結(jié)

BIRCH算法可以不用輸入類(lèi)別數(shù)K值，這點(diǎn)和K-Means，Mini Batch K-Means不同。如果不輸入K值，則最后的CF元組的組數(shù)即為最終的K，否則會(huì)按照輸入的K值對(duì)CF元組按距離大小進(jìn)行合并。

一般來(lái)說(shuō)，BIRCH算法適用于樣本量較大的情況，這點(diǎn)和Mini Batch K-Means類(lèi)似，但是BIRCH適用于類(lèi)別數(shù)比較大的情況，而Mini Batch K-Means一般用于類(lèi)別數(shù)適中或者較少的時(shí)候。BIRCH除了聚類(lèi)還可以額外做一些異常點(diǎn)檢測(cè)和數(shù)據(jù)初步按類(lèi)別規(guī)約的預(yù)處理。但是如果數(shù)據(jù)特征的維度非常大，比如大于20，則BIRCH不太適合，此時(shí)Mini Batch K-Means的表現(xiàn)較好。

對(duì)于調(diào)參，BIRCH要比K-Means，Mini Batch K-Means復(fù)雜，因?yàn)樗枰獙?duì)CF Tree的幾個(gè)關(guān)鍵的參數(shù)進(jìn)行調(diào)參，這幾個(gè)參數(shù)對(duì)CF Tree的最終形式影響很大。

最后總結(jié)下BIRCH算法的優(yōu)缺點(diǎn)：

BIRCH算法的主要優(yōu)點(diǎn)有：

1) 節(jié)約內(nèi)存，所有的樣本都在磁盤(pán)上，CF Tree僅僅存了CF節(jié)點(diǎn)和對(duì)應(yīng)的指針。

2) 聚類(lèi)速度快，只需要一遍掃描訓(xùn)練集就可以建立CF Tree，CF Tree的增刪改都很快。

3) 可以識(shí)別噪音點(diǎn)，還可以對(duì)數(shù)據(jù)集進(jìn)行初步分類(lèi)的預(yù)處理

BIRCH算法的主要缺點(diǎn)有：

1) 由于CF Tree對(duì)每個(gè)節(jié)點(diǎn)的CF個(gè)數(shù)有限制，導(dǎo)致聚類(lèi)的結(jié)果可能和真實(shí)的類(lèi)別分布不同.

2) 對(duì)高維特征的數(shù)據(jù)聚類(lèi)效果不好。此時(shí)可以選擇Mini Batch K-Means

3) 如果數(shù)據(jù)集的分布簇不是類(lèi)似于超球體，或者說(shuō)不是凸的，則聚類(lèi)效果不好。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

Birch層次聚類(lèi)