クラスタリングを勉強してみる（4） hierarchical clustering

1. 概要

階層的なクラスター構造を持つ集合を作成する手法を hierarchical clustering と言います。

1-1. AGNES（Agglomerative Nesting）

• 凝縮型（bottom-up）によるアプローチ
• すべてのオブジェクトが、それぞれ1つずつのクラスターである地点から開始
• 最終的に 1つの大きなクラスターになるまで続ける
• ほとんどの hierarchical clustering は、このアプローチに該当する

1-2. DIANA（Divisive Analysis）

• 分割型（top-down）によるアプローチ
• すべてのオブジェクトを内包した1つの大きなクラスターである地点から開始
• クラスターをより小さいクラスターに細分する
• あまり一般的でない

2. HAC（hierarchical agglomerative clustering）

凝集型階層的クラスタリングを HACと言います。超距離（ultrametric）の階層的なクラスター構造であるため、デンドログラム（dendrogram）と呼ばれる樹形図によって表現されます。
クラスターを結合する操作過程は、単調（monotonicity）であり、逆転（inversion）は発生しません。

2-1. アルゴリズム

1. すべてのクラスターの組に対して、クラスター間距離を求める
2. クラスター間の非類似度を最小とするクラスターの組を結合し、新たなクラスターを作成する
3. 新たなクラスターとその他のクラスター間の距離（更新距離）を求める
4. クラスター数があらかじめ決められた数（通常は１）になるまで 2 ~ 3 を繰り返す

2-2. クラスター間の非類似度の算出方法

2-2-1. 最短距離法（single-link）

異なるクラスターに属するオブジェクト間の非類似性の中で、最も近いオブジェクト間の非類似性を、クラスター間の距離として選択する手法です。

• Cons.
  • 鎖（chaining）効果が発生してしまう。
  • 鎖効果とは、ある１つのクラスターにオブジェクトが１つずつ順に吸収されてクラスター形成がされる状態を言います。

2-2-2. 最長距離法（complete-link）

異なるクラスターに属するオブジェクト間の非類似性の中で、最も遠いオブジェクト間の非類似性を、クラスター間の距離として選択する手法です。

• Cons.
  • 外れ値の影響を受けやすい。

2-2-3. 群平均法（group-average agglomerative clustering）

異なるクラスターに属するすべてのオブジェクト間非類似性の平均を、クラスター間の距離として選択する手法です。

2-2-4. 重心法（cnetroid clustering）

それぞれのクラスターに属するオブジェクトの重心間の非類似性を、クラスター間の距離として選択する手法です。

• Cons.
  • 逆転（inversion）が発生する可能性があります。

2-2-5. Ward法（ward method）

それぞれのクラスターに属するオブジェクトの重心間の重み付きの非類似性を、クラスター間の距離として選択する手法です。

2-3. Pros.

• 多くの研究者は、hierarchical algorithms の方が partitioning algorithms よりも良い分類結果が期待できると考えている

2-4. Cons.

• スケールしない
• 事前の操作をアン・ドゥできない（can never undo what was done previously）

3. 参考文献

Introduction to Information Retrieval