BIRCH

Zhang等人提出了Birch（Blanced Iterative Reducing and Clustering）演演算法來對大規模數據集進行聚類。Birch演演算法是一種非常有效的、傳統的層次聚類演演算法，該演演算法能夠用一遍掃描有效地進行聚類，並能夠有效地處理離群點。Birch演演算法是基於距離的層次聚類，綜合了層次凝聚和迭代的重定位方法，首先用自底向上的層次演演算法，然後用迭代的重定位來改進結果。[2]層次凝聚是採用自底向上策略，首先將每個對象作為一個原子簇，然後合併這些原子簇形成更大的簇，減少簇的數目，直到所有的對象都在一個簇中，或某個終結條件被滿足。

Birch演演算法的主要思想是：通過掃描資料庫，建立一個初始存放於內存中的聚類特徵樹，然後對聚類特徵樹的葉結點進行聚類。它的核心是聚類特徵（CF）和聚類特徵樹（CF Tree）。2.1.1CF CF是指三元組CF=（N，LS，SS），用來概括子簇信息，而不是存儲所有的數據點。其中：N：簇中d維點的數目；LS：N個點的線性和；SS：N個點的平方和。比如給定一個由二維點組成的集合{(3,4),(2,6),(4,5)}，那麼：CF結構概括了簇的基本信息，並且是高度壓縮的，它存儲了小於實際數據點的聚類信息。[3]同時CF的三元結構設置使得計算簇的半徑、簇的直徑、簇與簇之間的距離等非常容易。

CF樹是一棵具有兩個參數的高度平衡樹，用來存儲層次聚類的聚類特徵。它涉及到兩個參數分支因子和閾值。其中，分支因子B指定子節點的最大數目，即每個非葉節點可以擁有的孩子的最大數目。閾值T指定存儲在葉節點的子簇的最大直徑，它影響著CF樹的大小。改變閾值可以改變樹的大小。CF樹是隨著數據點的插入而動態創建的，因此該方法是增量的。CF樹的構造過程實際上是一個數據點的插入過程[4]，其步驟為:

(1)從根節點root開始遞歸往下，計算當前條目與要插入數據點之間的距離，尋找距離最小的那個路徑，直到找到與該數據點最接近的葉節點中的條目。

(2)比較計算出的距離是否小於閾值T，如果小於則當前條目吸收該數據點；反之，則繼續第三步。

(3)判斷當前條目所在葉節點的條目個數是否小於L，如果是，則直接將數據點插入作為該數據點的新條目，否則需要分裂該葉節點。分裂的原則是尋找該葉節點中距離最遠的兩個條目並以這兩個條目作為分裂后新的兩個葉節點的起始條目，其他剩下的條目根據距離最小原則分配到這兩個新的葉節點中，刪除原葉節點並更新整個CF樹。

當數據點無法插入時，這個時候需要提升閾值T並重建樹來吸收更多的葉節點條目，直到把所有數據點全部插入完畢。

在CF樹重建過程中，通過利用老樹的葉節點來重新構建一棵新樹，因而樹的重建過程不需要訪問所有點，即構建CF樹只需訪問數據一次就行

Birch演演算法主要分為以下兩個階段：

(1)掃描資料庫，動態的建立一棵存放在內存的CF樹。若內存不夠，則增大閾值，在原樹基礎上構造一棵較小的樹。

(2)對葉節點進一步利用一個全局性的聚類演演算法，改進聚類質量。由於CF樹的葉節點代表的聚類可能不是自然的聚類結果，原因是給定的閾值限制了簇的大小，並且數據的輸入順序也會影響到聚類結果。因此，需要對葉節點進一步利用一個全局性的聚類演演算法，改進聚類質量。