BIRCH(英文全称:balanced iterative reducing and clustering using hierarchies,中文:利用层次方法的平衡迭代规约和聚类)[1]是一个非监督式分层聚类算法,于1996年由 Tian Zhang 提出。算法的优势在于能够利用有限的内存资源完成对大数据集的高质量的聚类。[2]该算法通过构建聚类特征树(Clustering Feature Tree,简称CF Tree),在接下来的聚类过程中,直接对聚类特征进行聚类,而无需对原始数据集进行聚类。[3]因此在多数情况下只需要扫描一次数据库即可进行聚类,IO成本与数据集尺寸呈线性关系。[4]
算法利用构建聚类特征树进行计算,树上的节点称作聚类特征( C F {\displaystyle CF} )。 聚类特征为一个三维向量 ( n , L S , S S ) {\displaystyle (n,LS,SS)} [5], n {\displaystyle n} 表示子类中节点的数目, L S {\displaystyle LS} 表示 n {\displaystyle n} 个点的线性和, S S {\displaystyle SS} 表示 n {\displaystyle n} 个点的平方和。