Balanced Iterative Reducing and Clustering using Hierarchies (BIRCH)

限定された主記憶で大規模データをクラスタリングする手法.データの走査は1回だけなので,データストリームの処理にも使える.データを圧縮して保持する部分はデータスカッシングとも見なせる.

CF木 (Clustering Feature tree)

CF木は,BIRCHで使うデータの圧縮表現.基本的には,直径がしきい値以内のデータを部分クラスタにまとめる.この部分クラスタ内のデータは,以後の大域クラスタリングではひとまとまりにして扱い,同じ最終クラスタに分類される.

この部分クラスタはCF(Clustering Feature)によってあらわす.これは,部分クラスタ中のデータ数,総和,2乗和の三つ組.この部分クラスタを木構造で格納したものがCF木.新たなデータが来たとき,CFは容易に逐次更新でき,また,部分クラスタの高速な参照を維持するためB+-treeの手法を用いて木をバランスさせる.

大域クラスタ

CF木に格納された部分クラスタを要素としてデータ全体をクラスタリングする. 部分クラスタ数は,元のデータよりはるかに小さいので,元のデータが大規模でも扱える. 部分クラスタ間の距離だが,CFにある3種類の情報だけで計算できる,次式のようなものを幾つか示している. \[D2(C_i,C_j)=\sqrt{\frac{\sum_{\mathbf{x}_i\in C_i}\sum_{\mathbf{x}_j\in C_j}(\mathbf{x}_i-\mathbf{x}_j)^2}{n_in_j}}\] 部分クラスタ間の距離が決まれば,あとは凝集型階層的クラスタリングなどで大域的なクラスタリングができる.

-- しましま

関連項目

リンク集

関連文献


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:10:43