* 凝集型階層的クラスタリング (aggregative hierarchical clustering) [#a53a3b2d]
//ここには %項目の説明を書いてください．よろしければ署名しておいてください．
全てのクラスタがちょうど一つの対象を含む(singletonな)状態から始めて，再帰的にクラスタを併合して階層構造を獲得するクラスタリング手法．
併合するクラスタを選ぶ規準の違いにより多くの手法がある．
最短距離法，最長距離法，群平均法，Ward法などについては，併合前のそれぞれのクラスタと，これら２つ以外のクラスタとの距離が，併合後に増加するという可約性 (reducibility) がある．この性質により，次のアルゴリズムで，最近傍グラフを利用して \(n\) に対し \(O(n^2)\) の計算量で実行可能．
+ 任意のデータ点から開始
+ 現在のデータ点から最も近いデータ点を見つけ，そのデータ点へ有向辺を作り，移動する
+ 最近傍グラフでは，最も近い対のところでのみ有向辺が折り返されてループになる．よって，もし折り返しが生じたらその対を併合し，距離行列を更新し，併合後のクラスタに相当するデータ点を追加する．そして，併合前の２つのデータ点を取り除き，そのもう一つ前のデータ点へ移動し，ステップ2へ移る
-- ただし，併合によって辺を持つデータ点がなくなったらステップ1へ
+ データ点が１つになったら終了
> -- しましま
**関連項目 [#jee298e1]
//英語や同義語のあとに，#brで区切って関連する項目をリストしてください．
-[[aggregative hierarchical clustering]]
-[[aggregative clustering]]
#br
-[[クラスタリング]]
-[[分割型階層的クラスタリング]]
-[[デンドログラム]]
-[[超距離]]
-[[cophenetic correlation coefficient]]
-[[Lance-Williams updating formula]]
-主な手法
--[[単リンク法]]
--[[完全リンク法]]
--[[群平均法]]
--[[Ward法]]
--[[セントロイド法]] ([[重心法]])
--[[メジアン法]]
#br
-[[検索:凝集型階層的クラスタリング]]
**リンク集 [#m6da4bfa]
//関連するWWW資源があればリンクしてください．
-[[クラスタリングとは (クラスター分析とは) >http://www.kamishima.net/jp/clustering/]] @ 神嶌敏弘：基本的な手法の説明とクラスタリングを用いた分析での注意点
-[[RjpWiki:stats(R 統計)パッケージ中のオブジェクト一覧]]
hclust関数で凝集型階層的クラスタリングができる
**関連文献 [#s211bbde]
//この%項目%に関連する書籍や論文を紹介してください．
-[[Paper/ICML-2002-p283]] 凝集型階層的クラスタリングの背後にある確率モデルについて述べた論文．各手法の暗黙の仮定が，そのモデルから分かる．
-Lance-Williams updating formula や凝集型階層的クラスタリングの計算量について詳しい．~
C.F.Olson, "Parallel Algorithms for Hierarchical Clustering", Parallel Computing, vol.21, pp.1313-1325 (1995)~
[[GoogleScholarAll:Parallel Algorithms for Hierarchical Clustering]]
-[[Book/データマイニングの基礎]] 3.2.1-3.2.2節
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
