BIRCH

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

Birch 算法的主要思想是：通過掃描數據庫，建立一個初始存放於內存中的聚類特徵樹， 然後對聚類特徵樹的葉結點進行聚類。它的核心是聚類特徵（CF）和聚類特徵樹（CF Tree）。 2.1.1 CF 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 樹的葉節點代表的聚類可能不是自然的聚類結果，原因是給定的閾值限制了簇 的大小，並且數據的輸入順序也會影響到聚類結果。因此，需要對葉節點進一步利用一個全 局性的聚類算法，改進聚類質量。