引言
BIRCH聚類算法屬于增量聚類算法差油，聚類的過程只需要單遍依次遍歷數(shù)據(jù)集中的樣本即可以完成聚類，不需要一次性全部把所有樣本加載到內(nèi)存完成聚類。因此該算法比較適合大數(shù)據(jù)量唇跨，增量型的聚類過程狭吼。BIRCH聚類是一個構(gòu)建Cluster Feature Tree的過程层坠，而Cluster Feature Tree和B+樹非常相似，因此了解BIRCH聚類算法之前刁笙，有必要了解一下B+樹破花。
BIRCH相關(guān)概念
Cluster Feature 聚類特征
- Cluster Feature 簡稱CF，一個CF是一個三元組疲吸，可以用（N座每，LS，SS）表示摘悴。其中N代表了這個CF中擁有的樣本點的數(shù)量峭梳，這個好理解；LS代表了這個CF中擁有的樣本點各特征維度的和向量
蹂喻，SS代表了這個CF中擁有的樣本點各特征維度的平方和
葱椭。舉例說明，如下面五個樣本點所示：
口四，
,
孵运。
- CF有一個很好的性質(zhì)，就是滿足線性關(guān)系窃祝，也就是
掐松。這個性質(zhì)從定義也很好理解。如果把這個性質(zhì)放在CF Tree上粪小，也就是說大磺，在CF Tree中，對于每個父節(jié)點中的CF節(jié)點探膊，它的
三元組的值等于這個CF節(jié)點所指向的所有子節(jié)點的三元組之和杠愧。如下圖所示：
image.png
從上圖中可以看出，根節(jié)點的的三元組的值逞壁，可以從它指向的6個子節(jié)點
的值相加得到流济。這樣我們在更新CF Tree的時候锐锣，可以很高效。
- 對于CF Tree绳瘟，我們一般有幾個重要參數(shù)雕憔，第一個參數(shù)是每個內(nèi)部節(jié)點的最大CF數(shù)B，第二個參數(shù)是每個葉子節(jié)點的最大CF數(shù)L糖声，第三個參數(shù)是針對葉子節(jié)點中某個CF中的樣本點來說的斤彼，它是葉節(jié)點每個CF的最大樣本半徑閾值T，也就是說蘸泻，在這個CF中的所有樣本點一定要在半徑小于T的一個超球體內(nèi)琉苇。對于上圖中的CF Tree，限定了B=7悦施， L=5并扇， 也就是說內(nèi)部節(jié)點最多有7個CF，而葉子節(jié)點最多有5個CF抡诞。
Cluster Feature Tree 聚類特征樹
Cluster Feature Tree簡記為CF Tree穷蛹，其中的每一個節(jié)點由若干個CF組成。構(gòu)建CF Tree的過程就是對樣本完成聚類昼汗。構(gòu)建CF Tree的過程如下：
-
在最開始的時候俩莽，CF Tree是空的，沒有任何樣本乔遮，我們從訓(xùn)練集讀入第一個樣本點扮超，將它放入一個新的CF三元組A，這個三元組的N=1蹋肮，將這個新的CF放入根節(jié)點出刷，此時的CF Tree如下圖：image.png
-
現(xiàn)在我們繼續(xù)讀入第二個樣本點，我們發(fā)現(xiàn)這個樣本點和第一個樣本點A坯辩，在半徑為T的超球體范圍內(nèi)馁龟，也就是說，他們屬于一個CF漆魔，我們將第二個點也加入CF A,此時需要更新A的三元組的值坷檩。此時A的三元組中N=2。此時的CF Tree如下圖：image.png
-
此時來了第三個節(jié)點改抡，結(jié)果我們發(fā)現(xiàn)這個節(jié)點不能融入剛才前面的節(jié)點形成的超球體內(nèi)矢炼，也就是說，我們需要一個新的CF三元組B阿纤，來容納這個新的值句灌。此時根節(jié)點有兩個CF三元組A和B，此時的CF Tree如下圖：image.png
-
當(dāng)來到第四個樣本點的時候，我們發(fā)現(xiàn)和B在半徑小于T的超球體胰锌，這樣更新后的CF Tree如下圖：image.png
-
那個什么時候CF Tree的節(jié)點需要分裂呢骗绕？假設(shè)我們現(xiàn)在的CF Tree 如下圖， 葉子節(jié)點LN1有三個CF资昧， LN2和LN3各有兩個CF酬土。我們的葉子節(jié)點的最大CF數(shù)L=3。此時一個新的樣本點來了格带，我們發(fā)現(xiàn)它離LN1節(jié)點最近诺凡，因此開始判斷它是否在sc1,sc2,sc3這3個CF對應(yīng)的超球體之內(nèi)，但是很不幸践惑，它不在，因此它需要建立一個新的CF嘶卧，即sc8來容納它尔觉。問題是我們的L=3，也就是說LN1的CF個數(shù)已經(jīng)達到最大值了芥吟，不能再創(chuàng)建新的CF了侦铜，怎么辦？此時就要將LN1葉子節(jié)點一分為二了钟鸵。image.png
-
我們將LN1里所有CF元組中钉稍，找到兩個最遠的CF做這兩個新葉子節(jié)點的種子CF，然后將LN1節(jié)點里所有CF sc1, sc2, sc3棺耍，以及新樣本點的新元組sc8劃分到兩個新的葉子節(jié)點上贡未。將LN1節(jié)點劃分后的CF Tree如下圖：image.png
-
如果我們的內(nèi)部節(jié)點的最大CF數(shù)B=3，則此時葉子節(jié)點一分為二會導(dǎo)致根節(jié)點的最大CF數(shù)超了蒙袍，也就是說俊卤，我們的根節(jié)點現(xiàn)在也要分裂，分裂的方法和葉子節(jié)點分裂一樣害幅，分裂后的CF Tree如下圖：image.png
- 總結(jié)CF Tree的建樹過程如下：
第一步：從根節(jié)點開始向下尋找與新樣本距離最近的葉子節(jié)點（PS. 沒有去閱讀原論文消恍，個人直覺猜測這里的距離計算應(yīng)該是通過CF三元組中的計算得到），以及找到該葉子節(jié)點中和新樣本距離最近的CF以现。
第二步：如果新樣本插入CF后狠怨，該CF對應(yīng)的超球體半徑依然小于預(yù)設(shè)的閾值T，則更新路徑中所有的CF三元組邑遏，新樣本插入結(jié)束佣赖，否則轉(zhuǎn)入3。
第三步：如果新樣本加入當(dāng)前葉子節(jié)點中任何一個CF记盒，超球體半徑都會超過閾值T茵汰，并且此時葉子節(jié)點的CF個數(shù)小于L，則新建一個CF并將新樣本納入其中孽鸡，更新路徑上所有的CF三元組蹂午，插入結(jié)束栏豺。
第四步：如果第三步中葉子節(jié)點中的CF數(shù)量已經(jīng)超過了L個，則將當(dāng)前葉子節(jié)點劃分為兩個新葉子節(jié)點豆胸，選擇舊葉子節(jié)點中所有CF三元組里超球體距離最遠的兩個CF元組奥洼，分別作為兩個新葉子節(jié)點的第一個CF節(jié)點。將其他元組和新樣本元組按照距離遠近原則放入對應(yīng)的葉子節(jié)點晚胡。依次向上檢查父節(jié)點是否也要分裂灵奖，如果需要按和葉子節(jié)點分裂方式相同。
BIRCH算法
上面講了半天的CF Tree估盘，終于我們可以步入正題BIRCH算法瓷患，其實將所有的訓(xùn)練集樣本建立了CF Tree，一個基本的BIRCH算法就完成了遣妥，對應(yīng)的輸出就是若干個CF節(jié)點擅编，每個節(jié)點里的樣本點就是一個聚類的簇。也就是說BIRCH算法的主要過程箫踩，就是建立CF Tree的過程爱态。
當(dāng)然，真實的BIRCH算法除了建立CF Tree來聚類境钟，其實還有一些可選的算法步驟的锦担，現(xiàn)在我們就來看看 BIRCH算法的流程。
- 將所有的樣本依次讀入慨削，在內(nèi)存中建立一顆CF Tree, 建立的方法參考上一節(jié)洞渔。
2.（可選）將第一步建立的CF Tree進行篩選，去除一些異常CF節(jié)點缚态，這些節(jié)點一般里面的樣本點很少痘煤。對于一些超球體距離非常近的元組進行合并
3.（可選）利用其它的一些聚類算法比如K-Means對所有的CF元組進行聚類，得到一顆比較好的CF Tree.這一步的主要目的是消除由于樣本讀入順序?qū)е碌牟缓侠淼臉浣Y(jié)構(gòu)猿规，以及一些由于節(jié)點CF個數(shù)限制導(dǎo)致的樹結(jié)構(gòu)分裂衷快。
4.（可選）利用第三步生成的CF Tree的所有CF節(jié)點的質(zhì)心，作為初始質(zhì)心點姨俩，對所有的樣本點按距離遠近進行聚類蘸拔。這樣進一步減少了由于CF Tree的一些限制導(dǎo)致的聚類不合理的情況。
從上面可以看出环葵，BIRCH算法的關(guān)鍵就是步驟1调窍，也就是CF Tree的生成，其他步驟都是為了優(yōu)化最后的聚類結(jié)果张遭。
總結(jié)：
BIRCH算法的主要優(yōu)點有：
- 節(jié)約內(nèi)存邓萨，所有的樣本都在磁盤上，CF Tree僅僅存了CF節(jié)點和對應(yīng)的指針。
- 聚類速度快缔恳，只需要一遍掃描訓(xùn)練集就可以建立CF Tree宝剖，CF Tree的增刪改都很快。
- 可以識別噪音點歉甚，還可以對數(shù)據(jù)集進行初步分類的預(yù)處理
BIRCH算法的主要缺點有： - 由于CF Tree對每個節(jié)點的CF個數(shù)有限制万细，導(dǎo)致聚類的結(jié)果可能和真實的類別分布不同.
- 對高維特征的數(shù)據(jù)聚類效果不好。此時可以選擇Mini Batch K-Means;
- 如果數(shù)據(jù)集的分布簇不是類似于超球體纸泄，或者說不是凸的赖钞，則聚類效果不好。
