- 追加された行はこの色です。
- 削除された行はこの色です。
- BIRCH へ行く。
* Balanced Iterative Reducing and Clustering using Hierarchies (BIRCH) [#l1534f3f]
//ここには %項目の説明を書いてください．よろしければ署名しておいてください．
限定された主記憶で大規模データをクラスタリングする手法．データの走査は1回だけなので，データストリームの処理にも使える．データを圧縮して保持する部分はデータスカッシングとも見なせる．
*** CF木 (Clustering Feature tree) [#w0ae4cff]
CF木は，BIRCHで使うデータの圧縮表現．基本的には，直径がしきい値以内のデータを部分クラスタにまとめる．この部分クラスタ内のデータは，以後の大域クラスタリングではひとまとまりにして扱い，同じ最終クラスタに分類される．
この部分クラスタはCF(Clustering Feature)によってあらわす．これは，部分クラスタ中のデータ数，総和，2乗和の三つ組．この部分クラスタを木構造で格納したものがCF木．新たなデータが来たとき，CFは容易に逐次更新でき，また，部分クラスタの高速な参照を維持するためB+-treeの手法を用いて木をバランスさせる．
*** 大域クラスタ [#tea7ddee]
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}}\]
部分クラスタ間の距離が決まれば，あとは凝集型階層的クラスタリングなどで大域的なクラスタリングができる．
> -- しましま
** 関連項目 [#r97291f6]
//英語や同義語のあとに，#brで区切って関連する項目をリストしてください．
-[[クラスタリング]]
-[[データストリーム]]
-[[データスカッシング]]
#br
-[[検索:BIRCH]]
** リンク集 [#d67e77d4]
//関連するWWW資源があればリンクしてください．
** 関連文献 [#v277c1c3]
//この%項目%に関連する書籍や論文を紹介してください．
-基本文献：フルペーパー~
T.Zhang, R.Ramakrishnan, and M.Livny "BIRCH: A New Data Clustering Algorithm and Its Applications" Data Mining and Knowledge Discovery, vol.1, pp.141-182 (1997)~
[[GoogleScholarAll:BIRCH: A New Data Clustering Algorithm and Its Applications]]
-基本文献：国際会議~
T.Zhang, R.Ramakrishnan, and M.Livny "BIRCH: An Efficient Data Clustering Method for Very Large Databases" SIGMOD 1996, pp.103-114~
[[GoogleScholarAll:BIRCH: An Efficient Data Clustering Method for Very Large Databases]]
-[[Book/データマイニング(データサイエンスシリーズ3)]] 6.2.2節
-[[Book/人工知能学事典]] 13-11節
-[[Book/Data Mining - Concepts and Techniques]] 7.5.2節
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
