凝集型階層的クラスタリング

これらのキーワードがハイライトされています：クラスタリング クラスター分析 clustering

凝集型階層的クラスタリング (aggregative hierarchical clustering)†

全てのクラスタがちょうど一つの対象を含む(singletonな)状態から始めて，再帰的にクラスタを併合して階層構造を獲得するクラスタリング手法．併合するクラスタを選ぶ規準の違いにより多くの手法がある．

最短距離法，最長距離法，群平均法，Ward法などについては，併合前のそれぞれのクラスタと，これら２つ以外のクラスタとの距離が，併合後に増加するという可約性 (reducibility) がある．この性質により，次のアルゴリズムで，最近傍グラフを利用して $n$ に対し $O(n^2)$ の計算量で実行可能．

任意のデータ点から開始
現在のデータ点から最も近いデータ点を見つけ，そのデータ点へ有向辺を作り，移動する
最近傍グラフでは，最も近い対のところでのみ有向辺が折り返されてループになる．よって，もし折り返しが生じたらその対を併合し，距離行列を更新し，併合後のクラスタに相当するデータ点を追加する．そして，併合前の２つのデータ点を取り除き，そのもう一つ前のデータ点へ移動し，ステップ2へ移る
- ただし，併合によって辺を持つデータ点がなくなったらステップ1へ
データ点が１つになったら終了