クラスタリングを勉強してみる（7） BARCH

1. 概要

既存の hierarchical clustering や partitioning clustering とは異なるクラスタリング手法に、
BARCH（Balanced Interactive Reducing and Clustering using Hierarchies）[Zhang 96, Zhang 97]という手法があります。
BIRCH は、最初にデータ全体を走査して CF-tree（Clustering Feature Tree）というデータの要約情報を生成し、以後の走査をこの CF-tree に限定する特徴があります。

2. CF-tree

CF-tree は、 $CF$ という部分クラスタの要約情報を付随させたバランス木で、分岐係数（ $B$ は非終端、 $L$ は終端）としきい値 $T$ をパラメータとします。

各非終端ノードは、最大 $B$ 個の子ノードへのリンクを、子ノードが表す部分クラスタの $CF$ と共に保持し、終端ノードは最大 $L$ 個の $CF$ と、終端ノード間の双方向リンクを保持します。つまり、以下のようになります。

子供の数は高々 $B$
葉がクラスタを表す
- 要素の分散平均が $T$ 以下
- クラスタの要素数は $L$ 以下

パラメータ $B$ と $L$ は、主記憶のページの大きさを考慮して定めます。また $T$ は、終端ノードの $CF$ が表す部分クラスタ $C$ の直径

$\sqrt{ \frac{\sum_{x_i, x_j\in{C}, x_i\ne{x_j}}(x_i - x_j){(x_i - x_j)}}{n(n-1)} }$

の最大値を定めます。
CF-tree は、直径 $T$ 未満の対象集合（部分クラスタ）の要約情報だけを終端ノードに保持するため、 $N$ に対して非常に小さくなります。
要約情報 $CF$ は、その子孫の葉に属する要素数、要素の重心と分散和を管理します。

$CF=(n, \sum_{x_i\in{C}}{x_i}, \sum_{x_i\in{C}}{c_i\cdot{c_i}})$

この $CF$ は、二つの部分クラスタ $C_i$ と $C_j$ の $CF$ から、部分クラスタ $C_i\cup{C_j}$ が計算できる性質があります。
さらに、Zhang らは $CF$ のみから計算可能な部分クラスタ間の距離 $D0$ ~ $D4$ も示しています。次式はその一つです。

$D2({C_i, C_j}) = \sqrt{ \frac{\sum_{x_j\in{C_i}}\sum_{x_j\in{C_j}}(x_i - x_j){(x_i - x_j)}}{n_i{n_j}} }$

$CF$ のこれらの性質により、BIRCH はデータ全体を参照することなく、CF-tree を更新できます。クラスタリングの過程では、終端ノードの部分クラスタを、あたかもひとつの対象のようにまとめて扱います。ただし、同じ部分クラスタ中の対象が違うクラスタに分類されることはありませんが、同じノードの部分クラスタは違うクラスタに分類される可能性があります。

3. アルゴリズム

主記憶への読み込みと CF-tree の構築
- 最初はルートのみ
- 要素をひとつずつ加える
  - 重心の近い子供をたどっていく
  - 葉のクラスタに入れても分散平均が $T$ 以下、要素数 $L$ 以下のままであれば、そのまま追加する
  - そうでない場合は、二つに分割する
    - 通常の2分割のクラスタリング（k-meansなど）を行う
    - 親の次数が $B$ を超えたら親も分割
    - 全体をバランスさせる必要があれば、バランスさせる
CF-tree の縮小
大域的なクラスタリング
クラスタの精錬

Phase1 と Phase3 は必須で、Phase2 と Phase4 はオプションです。

Phase1 は BIRCH の中心的な段階で、データを読み込んで CF-tree を生成します。生成手順は、B+-tree というバランス木の生成手順と同様です。つまり、各対象は CF-tree のルートから終端ノードに向かって一番近い（ $D0$ ~ $D4$ の一つで測る）部分クラスタを表すリンクを辿ります。
もし、終端ノードの中で一番近い $CF$ に新しい対象を加えても、その直径が $T$ 未満であれば、その $CF$ にその対象を追加します。そうでなければ、終端ノードに $CF$ を追加します。
ただし、追加後に $CF$ の数が $L$ より大きくなる場合は、その終端ノードを二つに分け、親の非終端ノードの子ノードを増やします。
さらに、その非終端ノードの子ノード数が $B$ より大きくなる場合は、さらに上位の非終端ノードの子ノード数を増やし、ルートノードの子ノード数が制限を超える場合は木を一段回深くします。

Phase2 では、前の段階で生成された初期 CF-tree を縮小して、次の Phase のクラスタリングをより容易にさせます。具体的には、少数の対象しか含まない孤立した $CF$ を外れ値として除外したり、非常に近い $CF$ をまとめるといった操作をします。

Phase3 では、既存のクラスタリング手法を用いてクラスタを生成します。論文中では、 $D0$ ~ $D4$ の距離（ $D2$ と $D4$ を推奨）を用いて凝集型階層的手法を適用しています。

最後の Phase4 は、クラスタを精錬する段階です。Phase3 で求めたクラスタのセントロイドを求め、すべての対象を最も近いセントロイドに再分類します。この段階を実行すると、データを2度操作することになるので、データベースの JOIN 演算が必要な場合など I/O コストが非常に大きい場合には省略できます。

4. Pros.

線形にスケールする： $O(N)$

5. Cons.

数値データ（numeric data）しか扱うことができない
データの投入順序（the order of the data record）に影響を受けやすい