BIRCH（バーチ）とは？大規模データ向けクラスタリング手法の仕組みを解説

BIRCH（バーチ）とは

BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies）は、大量の数値データレコードを効率よくクラスタリングするために設計されたアルゴリズムです。階層型クラスタリングと、反復分割法をはじめとする他のクラスタリング手法を統合したアプローチを採用しています。

BIRCHの中核となるのが、「クラスタリング特徴量（Clustering Feature：CF）」と「CFツリー」という2つの概念です。これらの構造によって、大規模データベース上でも高速かつ高いスケーラビリティを実現でき、継続的に流入してくるオブジェクトに対する増分的・動的なクラスタリングにも効果的に対応できます。

クラスタの重心・半径・直径

あるクラスタに含まれる n 個の d 次元データオブジェクト（点）を考えるとき、クラスタの重心 x₀、半径 R、直径 D はそれぞれ次の式で表されます。

$$x_{0}=\frac{\sum_{i=1}^{n}x_{i}}{n}$$

$$R=\sqrt{\frac{\sum_{i=1}^{n}(x_{i}-x_{0})^{2}}{n}}$$

$$D=\sqrt{\frac{\sum_{i=1}^{n}\sum_{j=1}^{n}(x_{i}-x_{j})^{2}}{n(n-1)}}$$

ここで、R は各メンバー要素から重心までの平均距離、D はクラスタ内部の点同士のペアごとの平均距離を意味します。R と D はいずれも、重心を中心としたクラスタの凝集度（タイトさ）を反映する指標です。

クラスタリング特徴量（CF）の定義

クラスタリング特徴量（CF）は、オブジェクトのクラスタに関する情報を要約する3次元ベクトルです。クラスタ内に n 個の d 次元オブジェクト {x_i} が存在するとき、そのクラスタの CF は次のように表現されます。

CF = (n, LS, SS)

• n：クラスタ内の点の数
• LS：n 個の点の線形和（$\sum_{i=1}^{n}x_{i}$）
• SS：データ点の平方和（$\sum_{i=1}^{n}x_{i}^{2}$）

統計的な観点から見ると、CF はクラスタのゼロ次・一次・二次モーメントに相当する要約統計量です。つまり、個々のデータ点を保持しなくても、クラスタの本質的な性質を把握できるのです。

CFの加算性

クラスタリング特徴量には「加算性」という重要な性質があります。例えば、互いに共通部分を持たない2つのクラスタ C1 と C2 が、それぞれ CF1 と CF2 というクラスタリング特徴量を持っているとします。このとき、C1 と C2 を統合して新たに形成されるクラスタの CF は、単純に CF1 + CF2 として求められます。

さらに、CF は BIRCH がクラスタリングの意思決定を行うために必要なすべての測定値を計算するのに十分な情報を備えています。BIRCH は CF を使ってクラスタ情報を要約することで記憶域を効率的に活用し、すべてのオブジェクトを保存する必要を排除しています。

CFツリーの構造とパラメータ

CFツリーは、階層的クラスタリングのためのクラスタリング特徴量を格納する高さ平衡木（height-balanced tree）です。ツリー内の非葉ノード（内部ノード）は子孫、すなわち「子」ノードを持ちます。非葉ノードはその子ノードたちの CF の合計値を保持するため、子ノード群に関するクラスタリング情報を要約することができます。

CFツリーの形状とサイズは、次の2つのパラメータによって制御されます。

• 分岐係数（Branching Factor：B）：各非葉ノードが持てる子ノードの最大数を定義します。
• しきい値（Threshold：T）：ツリーの葉ノードに格納されるサブクラスタの最大直径を定義します。

この2つのパラメータにより、結果として生成される CF ツリーのサイズが決定されます。適切な値を設定することで、メモリ使用量とクラスタリング精度のバランスを取ることが可能になります。