階層型クラスタリング手法とは？仕組みと2つの種類を徹底解説

階層型クラスタリング（Hierarchical Clustering）は、データオブジェクトをクラスタの木構造へと統合していく手法です。アルゴリズムは「トップダウン型」と「ボトムアップ型」のいずれかに分類されます。ただし、階層型クラスタリング手法には、マージ（併合）や分割の決定が一度完了すると後から調整できないという弱点があり、その結果、クラスタリングの品質が低下する可能性があります。

クラスタの併合は、クラスタ間の距離に基づいて行われます。クラスタ間距離として広く使われている尺度は以下の通りです。ここで、mi はクラスタ Ci の平均値、ni は Ci に含まれる点の数、|p − p′| は2点 p と p′ 間の距離を表します。

階層型クラスタリング手法の種類

階層型クラスタリング手法には、主に以下の2種類があります。

凝集型階層クラスタリング（AHC）

AHC（Agglomerative Hierarchical Clustering）はボトムアップ型のクラスタリング手法で、クラスタの中にサブクラスタがあり、さらにそのサブクラスタの中にもサブクラスタがあるといった階層構造を特徴とします。まず各オブジェクトをそれぞれ個別のクラスタに配置し、これらの原子クラスタを徐々により大きなクラスタへと併合していきます。すべてのオブジェクトが単一のクラスタにまとまるか、特定の終了条件を満たすまで処理を続けます。階層型クラスタリング手法の多くはこのタイプに属しており、手法ごとの違いはクラスタ間類似度の定義方法のみにあります。

例えば、AGNES（Agglomerative Nesting）と呼ばれる手法は、シングルリンク法を採用しています。長方形の領域内に配置された一連のオブジェクトを想定すると、最初は各オブジェクトがそれぞれ独立したクラスタに置かれます。その後、「クラスタ内の最も近いオブジェクト間のユークリッド距離が最小となるクラスタ同士を併合する」といった原則に従って、段階的にクラスタが統合されていきます。

分割型階層クラスタリング（DHC）

DHC（Divisive Hierarchical Clustering）はトップダウン型のアプローチで、凝集型ほど一般的には利用されていません。仕組みは凝集型クラスタリングと似ていますが、処理の方向が正反対です。この手法では、すべてのオブジェクトを含む単一のクラスタから出発し、得られたクラスタを順次分割していきます。単一オブジェクトのみからなるクラスタだけが残るまで、あるいは「望みのクラスタ数に達した」「最も近い2つのクラスタ間の距離が特定の閾値を超えた」といった終了条件を満たすまで処理を続けます。

分割型手法は、上位レベルでの適切な分割判断が難しいため、実装例が少なく、実際に使われることも稀です。DIANA（Divisive Analysis）は分割型階層クラスタリング手法の一例です。処理の順序は凝集型とは逆で、最初にすべてのオブジェクトが1つのクラスタに配置されます。その後、「クラスタ内の近傍オブジェクト間のユークリッド距離が最大となる位置で分割する」といった原則に基づき、クラスタが段階的に分割されていきます。