凝集型階層クラスタリングとは？仕組みと基本アルゴリズムを徹底解説

凝集型階層クラスタリングの概要

凝集型階層クラスタリング（Agglomerative Hierarchical Clustering）は、ボトムアップ型のアプローチを採用するクラスタリング手法です。この手法では、各クラスターがサブクラスターを含み、そのサブクラスターがさらに小さなサブクラスターを持つという入れ子状の階層構造が形成されます。

処理は、すべてのオブジェクトをそれぞれ個別のクラスターに配置することから始まります。その後、これらの原子クラスター（単一要素のクラスター）を段階的に統合し、より大きなクラスターへと発展させていきます。最終的に、すべてのオブジェクトが1つのクラスターにまとまるか、あらかじめ定められた終了条件が満たされるまで統合を繰り返します。階層クラスタリングには複数の手法が存在しますが、それらの違いはクラスター間の類似度の定義方法のみにあります。

AGNES（Agglomerative Nesting）の例

代表的な手法の一つであるAGNES（Agglomerative Nesting）は、シングルリンク法を使用し、以下のように動作します。長方形の中に配置されたオブジェクトの集合を想定してください。初期状態では、各オブジェクトがそれぞれ独立したクラスターに割り当てられます。続いて、「クラスター内の最も近いオブジェクト同士のユークリッド距離が最小となるペアを優先的にマージする」という原理に基づき、クラスターが段階的に統合されていきます。

デンドログラムによる可視化

階層クラスタリングの結果は、デンドログラムと呼ばれる木構造の図で視覚的に表現されます。デンドログラムには、クラスターとサブクラスターの関係性だけでなく、クラスターが統合された順序（凝集ビュー）、あるいは分割された順序（分割ビュー）も示されます。

基本的な凝集型階層クラスタリングアルゴリズムの手順

1. 必要に応じて近接行列を計算する。
2. 最も近い2つのクラスターをマージする。
3. 新しいクラスターと既存の各クラスターとの近接性を反映するよう、近接行列を更新する。
4. クラスターが1つだけ残るまで、手順2～3を繰り返す。

クラスター間の近接性の定義：MINとMAX

クラスター間の近接性は、通常、特定のクラスタータイプに基づいて定義されます。たとえば、MIN（最小距離法）、MAX（最大距離法）、群平均法といった多くの凝集型階層クラスタリング技法は、グラフベースのクラスター観から派生したものです。

MIN（最小距離）： 異なるクラスターに属する最も近い2点間の距離をクラスター間の近接性と定義します。グラフ理論の観点では、異なるノード部分集合間をつなぐ最短エッジに相当します。

MAX（最大距離）： 異なるクラスター間で最も遠い2点間の距離をクラスター間の近接性とみなします。グラフ理論では、異なるノード部分集合間の最長エッジに対応します。

空間計算量

前述の凝集型階層クラスタリングアルゴリズムでは、近接行列の保持が必須となります。近接行列は対称であるため、保存が必要な近接値の数は ½m² 個です（ここで m はデータポイント数）。また、クラスター情報の追跡に必要な記憶領域は、単一要素クラスターを除くとクラスター数（m − 1 個）に比例します。したがって、全体の空間計算量は O(m²) となります。

時間計算量

計算コストの面でも、この基本的なアルゴリズムの分析は容易です。まず、近接行列の計算に O(m²) の時間が必要です。その後の処理では、開始時に m 個のクラスターが存在し、反復ごとに2つのクラスターがマージされるため、マージと近接行列更新のステップが m − 1 回実行されます。