前言

一、Birch演算法基本思想

二、聚類特征CF和CF 樹

1.聚類特征CF

2.CF tree

3.CF tree 的生成

三、Birch演算法流程

1.birch演算法的優化

2.演算法優缺點

四、演算法實驗實體

1、研究不指定簇數的情況下，Birch演算法的聚類情況

2、研究聚類簇數對Birch演算法的影響

3、研究CF半徑閾值對Birch演算法的影響

4、研究每個節點內最大CF個數對Birch演算法的影響

實驗總結

參考文獻

前言

聚類演算法中的層次聚類方法是一種已得到廣泛使用的經典方法，是通過將資料物件組織成若干組并形成一個相應的樹來進行聚類，Birch演算法就是一種基于層次聚類的方法，所以我們在本文介紹一下Birch演算法

一、Birch演算法基本思想

BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies）全稱是：利用層次方法的平衡迭代規約和聚類，定義很長，但是其實只要明白它是用一棵樹來聚類和規約資料就可以了

先讓我們看看CF tree長什么樣，如上圖所示， BIRCH演算法利用了一個樹結構來幫助我們快速的聚類，這個數結構類似于平衡B+樹，一般將它稱之為聚類特征樹(Clustering Feature Tree，簡稱CF Tree)，這顆樹的每一個節點是由若干個聚類特征(Clustering Feature，簡稱CF)組成，從左圖我們可以看看聚類特征樹是什么樣子的：每個節點包括葉子節點都有若干個CF，而內部節點的CF有指向孩子節點的指標，所有的葉子節點用一個雙向鏈表鏈接起來，

二、聚類特征CF和CF 樹

1.聚類特征CF

如果某個簇包含N個d維的資料物件{o1，o2，…，oN}，則聚類特征定義為一個三元組CF=(N，LS，SS)，其中LS是N個物件的線性和，SS是N個物件的平方和，即：

聚類特征概括了物件簇的資訊，在BIRCH演算法中做聚類決策所需要的度量值，如簇的質心、半徑、直徑、簇間質心距離和平均簇間距離等都可以通過聚類特征CF計算出來，

質心計算公式：

半徑計算公式：

所以我們可以看到，其實聚類特征是包含了這個簇的很多資訊，但是它卻不需要全部存盤下來，只需要一個簡單的三元組就可以囊括了這個簇的所有資訊，使得記憶體占用空間大大減少，

舉個例子如圖，在CF Tree中的某一個節點的某一個CF中，有下面5個樣本(3,4), (2,6), (4,5), (4,7), (3,8)，則它對應的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

2.CF tree

CF有一個很好的性質，就是滿足線性關系，也就是CF1+CF2=(N1+N2,LS1+LS2,SS1+SS2)，這個性質從定義也很好理解，如果把這個性質放在CF Tree上，也就是說，在CF Tree中，對于每個父節點中的CF節點，它的(N,LS,SS)三元組的值等于這個CF節點所指向的所有子節點的三元組之和，

從上圖中可以看出，根節點的CF1的三元組的值，可以從它指向的6個子節點（CF7 - CF12）的值相加得到，這樣我們在更新CF Tree的時候，只需要進行簡單的加減操作，可以很高效的進行聚類，

CF tree可以分為根節點，內部節點，葉子節點3大類，其中每個節點都是有多個CF構成的，對于一顆CF tree, 有以下3個重要引數

1. 內部節點的最大CF數目，稱之為枝平衡因子B

2. 葉子節點的最大CF數目，稱之為葉平衡因子L

3. 葉子節點的空間閾值T，計算樣本點與CF的空間距離，如果小于閾值，則將樣本納入某個CF

3.CF tree 的生成

以下內容來自劉建平Pinard-博客園的學習筆記，總結如下：

我們先定義好CF Tree的引數：即內部節點的最大CF數B=3，葉子節點的最大CF數L=3，葉節點每個CF的最大樣本半徑閾值T，在最開始的時候，CF Tree是空的，沒有任何樣本，我們從訓練集讀入第一個樣本點，將它放入一個新的CF三元組A，這個三元組的N=1，將這個新的CF放入根節點，此時的CF Tree如圖：

現在我們繼續讀入第二個樣本點，我們發現這個樣本點和第一個樣本點A，在半徑為T的超球體范圍內，也就是說，他們屬于一個CF，我們將第二個點也加入CF A,此時需要更新A的三元組的值，此時A的三元組中N=2，此時的CF Tree如圖：

此時來了第三個節點，結果我們發現這個節點不能融入剛才前面的節點形成的超球體內，也就是說，我們需要一個新的CF三元組B，來容納這個新的值，此時根節點有兩個CF三元組A和B，此時的CF Tree如圖：

假設我們現在的CF Tree 如圖，葉子節點LN1有三個CF， LN2和LN3各有兩個CF，我們的葉子節點的最大CF數L=3，此時一個新的樣本點來了，我們發現它離LN1節點最近，因此開始判斷它是否在sc1,sc2,sc3這3個CF對應的超球體之內，但是很不幸，它不在，因此它需要建立一個新的CF，即sc8來容納它，問題是我們的L=3，也就是說LN1的CF個數已經達到最大值了，不能再創建新的CF了，怎么辦？此時就要將LN1葉子節點一分為二了，

具體怎么分，如圖所示，我們在CF元組中的所有資料中，找到最遠的兩個點作為種子節點（如圖中紅點），然后根據距離把剩下的點劃分到兩個節點中，形成兩個簇，

回到之前的圖，我們將LN1里所有CF元組中，找到兩個最遠的CF做這兩個新葉子節點的種子CF，然后將LN1節點里所有CF sc1, sc2, sc3，以及新樣本點的新元組sc8劃分到兩個新的葉子節點上，將LN1節點劃分后的CF Tree如下圖

更新完葉子結點，回傳上一層，檢查父節點是否需要分裂，如果需要，按照葉子結點分裂方法進行分裂，一直檢查到根節點，

因為我們的內部節點的最大CF數B=3，則此時葉子節點一分為二會導致根節點的最大CF數超了，也就是說，我們的根節點現在也要分裂，分裂的方法和葉子節點分裂一樣，最后分裂后的CF Tree如下圖：

總結下CF Tree的插入：

1. 從根節點向下尋找和新樣本距離最近的葉子節點和葉子節點里最近的CF節點

2. 到達葉子結點后，檢查最近的CF節點能否吸收

是，這個CF節點對應的超球體半徑仍然滿足小于閾值T，則更新路徑上所有的CF三元組

否，如果當前葉子節點的CF節點個數小于閾值L，是否可以添加一個新的CF節點

是，放入新樣本，將新的CF節點放入這個葉子節點，更新路徑上所有的CF三元組

否，分裂當前葉子結點中距離最遠的兩個CF元組，作為種子，按最近距離重新分配

3.更新每個非葉節點的CF資訊，依次向上檢查父節點是否也要分裂，如果需要按和葉子節點分裂方式相同，

三、Birch演算法流程

1.birch演算法的優化

上面扯了半天CF tree，那我們的Birch演算法到底是啥呢？接下來我們言歸正傳，說一下Birch演算法的演算法流程，首先，既然演算法是根據一棵樹來進行聚類，那么顯然我們可以通過優化這棵樹來提升聚類效果，話不多說，直接上圖，

現在我們就來看看 BIRCH演算法的流程，

1）將所有的樣本依次讀入，在記憶體中建立一顆CF Tree, 建立的方法參考上一節，

2）（可選）將第一步建立的CF Tree進行篩選，去除一些例外CF節點，這些節點一般里面的樣本點很少，對于一些超球體距離非常近的元組進行合并

3）（可選）利用其它的一些聚類演算法比如K-Means對所有的CF元組進行聚類，得到一顆比較好的CF Tree.這一步的主要目的是消除由于樣本讀入順序導致的不合理的樹結構，以及一些由于節點CF個數限制導致的樹結構分裂，

4）（可選）利用第三步生成的CF Tree的所有CF節點的質心，作為初始質心點，對所有的樣本點按距離遠近進行聚類，這樣進一步減少了由于CF Tree的一些限制導致的聚類不合理的情況，

從上面可以看出，BIRCH演算法的關鍵就是步驟1，也就是CF Tree的生成，其他步驟都是為了優化最后的聚類結果，所以我們前面只要搞懂這棵樹怎么來的，birch演算法的思想你就掌握啦

2.演算法優缺點

BIRCH演算法的主要優點有：

１、節省記憶體，葉子節點放在磁盤磁區上，非葉子節點僅僅是存盤了一個CF值，外加指向父節點和孩子節點的指標，

2、快，計算兩個簇的距離只需要用到(N,LS,SS)這三個值足矣，

3、只需掃描一遍資料集即可建樹，即一個資料集就是一棵樹，

4、可識別噪聲點，建立好CF樹后把那些包含資料點少的子簇剔除，

缺點：

1、對非球狀的簇聚類效果不好，這取決于簇直徑和簇間距離的計算方法，

2、對高維資料聚類效果不好，

3、由于每個節點只能包含一定數目的子節點，最后得出來的簇可能和自然簇相差很大，

4、整個程序中演算法一旦中斷，一切必須從頭再來，

四、演算法實驗實體

實驗資料：scikit中的make_blobs方法常被用來生成聚類演算法的測驗資料，make_blobs可以根據用戶指定的特征數量、樣本數量、類別數、每個類別的方差等來生成幾類資料，這些資料可用于測驗聚類演算法的效果，本實驗的設定是生成5000個樣本，每個樣本有2個特征，共生成5個簇，簇中心分別在[-1,-1], [0,0], [1,1],[1,-1],[-1,1]，每個簇的方差分別為0.4, 0.3, 0.4, 0.3,0.4，樣本示意圖如圖所示