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 Tree

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

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

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

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

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

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

算法步驟

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

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