聚類演算法第二篇-層次聚類演算法Birch

02-12

1 BIRCH演算法概述

BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies）在設計之初就考慮到了大規模數據集上聚類的精確性（充分利用有限內存保證好的聚類效果）和最小化I/O代價（減少資料庫的讀寫，保證效率）之間的均衡。BIRCH能夠識別出數據集中數據分布的不均衡性，將分布在稠密區域中的點聚類，將分布在稀疏區域中的點視作異常點而移除。此外，BIRCH是一種增量聚類方法，針對每一個點的聚類決策都是基於當前已經處理過的數據點，而不是全局的數據點。

2 一些重要概念

2.1 基本概念

假設在一個類簇中有 $N$ 個數據點：{ $ar{X} _{i} , i=1,2,...,N$ }，針對單個類簇的度量有：

中心點 $ar{X}0=frac{sum_{i=1}^{N}{ar{X}_{i}} }{N}$

半徑 $R=(frac{sum_{i=1}^{N}{(ar{X}_{i}-ar{X}0)^{2}} }{N})^{frac{1}{2}}$

直徑 $D=(frac{sum_{i=1}^{N}sum_{j=1}^{N}(ar{X_{i}}-ar{X_{j}})^2}{N(N-1)})^{frac{1}{2}}$

針對兩個類簇之間的度量有：

中心點歐氏距離： $D0=((ar{X0_{1}}-ar{X0_{2}})^2)^{frac{1}{2}}$

中心點曼哈頓距離： $D1=|ar{X0_{1}}-ar{X0_{2}}|=sum_{i=1}^{d}{|ar{X0_{1}}^{(i)}-ar{X0_{2}}^{(i)}|}$

平均類間距離： $D2=(frac{sum_{i=1}^{N_{1}} sum_{j=N_{1}+1}^{N_{1}+N_{2}}{(ar{X_{i}}-ar{X_{j}})^{2}} }{N_{1}N_{2}})^{frac{1}{2}}$

平均類間距離： $D3=(frac{sum_{i=1}^{N_{1}} sum_{j=N_{1}+1}^{N_{1}+N_{2}}{(ar{X_{i}}-ar{X_{j}})^{2}} }{(N_{1}+N_{2})(N_{1}+N_{2}-1)})^{frac{1}{2}}$

方差增長距離： $D4=sum_{k=1}^{N_{1}+N_{2}}{(ar{X_{k}}-frac{sum_{i=1}^{N_{1}+N_{2}}{ar{X_{i}}} }{N_{1}+N_{2}})^{2}} -sum_{k=1}^{N_{1}}{(ar{X_{k}}-frac{sum_{i=1}^{N_{1}}{ar{X_{i}}} }{N_{1}})^{2}}-sum_{k=N_{1}+1}^{N_{1}+N_{2}}{(ar{X_{k}}-frac{sum_{i=N_{1}+1}^{N_{1}+N_{2}}{ar{X_{i}}} }{N_{2}})^{2}}$

2.2 核心概念

CF（Clustering Feature）：類簇總體信息三元組 $(N, LS, SS)$ ，其中 $N$ 是一個類簇中數據點個數， $LS$ 是類簇中所有數據點的加和值，即 $sum_{i=1}^{N}{ar{X_{i}}}$ ， $SS$ 是類簇中所有數據點的平方和 $sum_{i=1}^{N}{ar{X_{i}}^2}$ ，CF相當於對一個類簇的信息做了總結。

CF可加性定理：針對兩個不相交的類簇，其CF向量分別為 $CF_{1}=(N_{1}, LS_{1}, SS_{1})$ ， $CF_{2}=(N_{2}, LS_{2}, SS_{2})$ ，那麼這兩個不相交類簇合併後的CF向量為： $CF_{1}+CF_{2}=(N_{1}+N_{2}, LS_{1}+LS_{2}, SS_{1}+SS_{2})$ 。這裡的證明比較簡單，就略去了。

在BRICH中，針對一個類簇，通常只保留其CF向量信息，這樣做比較節省空間且高效，後續的聚類需要的計算只需要根據類簇的CF向量即可完成。

CF Tree：類似於B樹的一顆高度平衡樹，有三個參數：內部節點平衡因子B，葉節點平衡因子L，簇半徑T。每個非葉子節點至多包含B個項，形式為 $[CF_{i}, child_{i}]$ ，其中 $child_{i}$ 是指向第i個子節點的指針。每個葉子節點至多包含L個項，且包含指向前後葉子節點的指針prev和next，其中的每一項代表一個類簇，且滿足類簇直徑小於T。樹的結構如下圖：

CF Tree會隨著新的數據點的加入而動態的建立起來，其插入過程包含以下幾步：

（1）從根節點開始，遞歸向下選擇最近的孩子節點，這裡最近的度量是根據前面提到的 $D0, D1, D2, D3, D4$ 中任意一個確定；

（2）如果在（1）中找到了最近的葉子節點中的一個 $L_{t}$ ，檢查其中最近的CF元組能否不超過閾值T吸收此數據點，若能，更新CF值；若不能，是否有空間（這裡每個節點能分配的空間有限，可參見下面的參數表）添加新的元組，若能則添加新的元組，若不能，分裂距離最遠的一對元組到兩個葉子節點，作為初始的種子，將其他元組按距離最近原則重新分配到兩個新的葉子節點上。

（3）從葉子節點向上回溯修改每個非葉子節點的CF值，若葉子節點發生分裂，則在父節點中增加相應的CF元組，同樣，父節點也可能需要分裂，則持續分裂直至根節點，最終如果根節點發生分類，則樹的高度需要加1。

3 BIRCH演算法流程

Phase2是可選的，主要是因為Phase3對輸入的即將進行全局聚類的聚簇的個數有要求（這裡考慮到Phase3的全局聚類演算法在小數據集上效果更好），所以Phase2主要掃描初始構建的CF Tree的葉子節點來重新構建一個更小的CF Tree，同時會移除異常點並把相聚較近中的子類合併成更大的類。

Phase3針對數據中存在極大的分布不均衡情況，上述Phase1中的插入順序不同也會導致分類效果不好，所以這裡的Phase3使用全局或半全局聚類演算法（層次聚類）來重新聚類所有的葉子節點（這裡直接利用每個子簇的CF向量在聚簇級別進行重新聚類）。

Phase4是可選的，針對的是個別類簇中數據點的誤放導致的結果不精確問題，使用Phase3中產生的聚類的中心點作為種子，重新分布數據點到最近的種子中，在這一步會最終生成每個數據點的聚類標籤，並能剔除一些異常點。

4 BIRCH演算法參數及默認值

上面是Birch原始論文中給出的參數及其默認值表，這裡的Memory是初始分配的內存80kb，Disk是用於保存異常點的磁碟空間，Distance度量類簇之間的距離，Quality代表所有類簇的直徑加權平均值，衡量聚類效果。這裡的Phase3的Input Range值為1000，意味著大多數全局聚類演算法能很好的處理1000個點。詳細的參數作用細節（如Threshold）這裡不再詳述，可參考原始論文[1]。

5 Birch實驗

本次實驗使用的scikit-learn中針對birch的樣例，這裡手工合成了100000個2維的樣本，並給出了使用和不使用上述Phase3的全局聚類方法時聚類的效果。下面作圖中的類簇個數是158，右圖中的類簇個數是100。

6 總結

下面總結一下Birch演算法的優缺點：

優點：（1）節省內存。葉子節點放在磁碟分區上，非葉子節點僅僅是存儲了一個CF值，外加指向父節點和孩子節點的指針。

（2）速度快。合併兩個兩簇只需要兩個類簇的CF元組直接相加即可，計算兩個簇的距離只需要用到(N,LS,SS)這三個值。

（3）一遍掃描資料庫即可建立CF Tree。

（4）可識別雜訊點。建立好CF Tree後把那些包含數據點少的MinCluster當作outlier。（5）由於CF Tree是高度平衡的，所以在樹上進行插入或查找操作很快。

缺點：（1）結果依賴於數據點的插入順序。本屬於同一個簇的點可能由於插入順序相差很遠而分到不同的簇中，即使同一個點在不同的時刻被插入，也會被分到不同的簇中。

（2）對非球狀的簇聚類效果不好。這取決於簇直徑和簇間距離的計算方法。

（3）對高維數據聚類效果不好。

（4）由於每個節點只能包含一定數目的子節點，最後得出來的簇可能和自然簇相差很大。BIRCH適合於需要產生大量的子簇的場景，但在整個過程中演算法一旦中斷，一切必須從頭再來。

（5）局部性導致了BIRCH的聚類效果欠佳。當一個新數據點要插入時，它只跟很少一部分簇進行了相似性（通過計算簇間距離）比較，高效率不一定帶來好效果。

參考資料

【1】BIRCH: An Efficient Data Clustering Method for very Large Databases

【2】BIRCH演算法學習

【3】聚類演算法之BIRCH（Java實現）