BIRCH

BIRCH（英文全稱：balanced iterative reducing and clustering using hierarchies，中文：利用層次方法的平衡迭代規約和聚類）^[1]是一個非監督式分層聚類算法，於1996年由 Tian Zhang 提出。算法的優勢在於能夠利用有限的內存資源完成對大數據集的高質量的聚類。^[2]該算法通過構建聚類特徵樹（Clustering Feature Tree，簡稱CF Tree），在接下來的聚類過程中，直接對聚類特徵進行聚類，而無需對原始數據集進行聚類。^[3]因此在多數情況下只需要掃描一次資料庫即可進行聚類，IO成本與數據集尺寸呈線性關係。^[4]

聚類特徵樹

算法利用構建聚類特徵樹進行計算，樹上的節點稱作聚類特徵（${\displaystyle CF}$）。 聚類特徵為一個三維向量${\displaystyle (n,LS,SS)}$^[5]，${\displaystyle n}$表示子類中節點的數目，${\displaystyle LS}$表示${\displaystyle n}$個點的線性和，${\displaystyle SS}$表示${\displaystyle n}$個點的平方和。