凝集型階層クラスタリング徹底ガイド：アルゴリズム・距離尺度・デンドログラムの読み方と実務応用
エバープレイ編集部凝集型階層クラスタリングとは
凝集型階層クラスタリング（agglomerative hierarchical clustering、以下「凝集型」）は、データポイントを階層的にまとめていくボトムアップ方式のクラスタリング手法です。最初は各データ点をそれぞれ1つのクラスタとみなし、反復的に最も近い2つのクラスタを結合していきます。結合の履歴はデンドログラム（樹形図）として表現でき、任意の高さで切ることで任意の個数のクラスタを得ることができます。
基本アルゴリズムの流れ
初期化：各データ点を個別のクラスタとして扱う（クラスタ数 = N）。
距離行列の計算：すべてのクラスタ間の距離（または類似度）を計算する。
反復処理：最も近い（距離が最小の）2クラスタを見つけて結合する。結合によりクラスタ数を1つ減らす。
距離の更新：新しくできたクラスタと残りのクラスタ間の距離を再計算する（連結法による）。
停止条件：目的のクラスタ数に達するか、距離がしきい値を超えるまで続ける。
距離尺度と連結法（リンク関数）
凝集型で重要なのは「クラスタ間距離」をどのように定義するかです。代表的な連結法は次のとおりです。
single linkage（最短連結）：クラスタ間の点対の最小距離。ノイズや「チェイニング（鎖状結合）」の影響を受けやすい。
complete linkage（最長連結）：クラスタ間の点対の最大距離。コンパクトで分離されたクラスタを好む。
average linkage（平均連結）：すべての点対距離の平均（UPGMAなどの変種あり）。バランスの取れた挙動を示す。
Ward法：クラスタ内分散の増加を最小化する統計的な結合基準。ユークリッド距離に基づく分散最小化で、球状のクラスタに適している。
デンドログラムの読み方とクラスタ数の決め方
デンドログラムは結合の順序と距離を可視化します。垂直軸（または水平軸）が結合時の距離や不一致度を表すことが多く、高い位置で結合されるほど「遠い」クラスタ同士の結合です。任意のカットオフ（高さ）で切ることで、データをいくつかのクラスタに分割できます。
クラスタ数の決定はしばしば主観的ですが、次のような手法が使われます：
デンドログラムの「大きなジャンプ（距離の急激増）」を探す
シルエット係数、ダビーズ・ボルダン指標などの内部評価指標を使う
コフェネティック相関係数（cophenetic correlation coefficient）でデンドログラムが元の距離をどの程度保持しているかを評価する
計算量とスケーラビリティ
凝集型階層クラスタリングは全てのペア距離を扱うため、距離行列のメモリは O(N^2) が必要です。実装によって計算時間は異なりますが、単純な実装では O(N^3) の時間がかかることがあります。多くの実装（Lance–Williams の更新式など）や最適化により、一般的なケースでは O(N^2) 時間で動作することが多いです。ただし、N が数万を超えるような大規模データでは現実的ではなく、サンプリング、近似アルゴリズム、あるいは k-means など別手法の検討が必要です。
前処理と距離尺度の選択
凝集型は距離定義に敏感です。実用上の注意点：
スケーリング：各特徴量のスケールが異なる場合は標準化（zスコア）や最小最大スケーリングが必須。
欠損値処理：距離計算前に欠損を埋める、あるいは距離関数で扱えるようにする。
カテゴリ変数：同種の距離（例えば Gower 距離）を使うか、ワンホット化／埋め込みを検討。
ノイズと外れ値：外れ値はクラスタ構造に大きく影響するため検出・処理が必要。
評価指標と妥当性確認
クラスタの妥当性を評価する指標：
シルエット係数：各点が自クラスタ内でどれだけ適切に位置するかを測る。
ダビーズ・ボールダン指数、カルインスキー・ハラバス指数など
コフェネティック相関係数：デンドログラムの距離と元の距離行列の一致度を測定。
外部ラベルがある場合は正解ラベルとの比較（ARI、NMI）
実装・ライブラリと注意点
主要な実装と留意点：
scikit-learn（Python）：AgglomerativeClustering クラス。リンク法により挙動が異なる。Ward を選ぶ場合は距離はユークリッドのみ（注意：最近のバージョンでの仕様確認が必要）。大規模データではメモリ制約に注意。
SciPy（Python）：scipy.cluster.hierarchy モジュール。linkage、dendrogram、cophenet 等の関数が揃う。距離行列を直接扱える。
R：hclust 関数など。豊富なリンク法を提供。
長所・短所
長所：デンドログラムにより階層構造を可視化でき、異なる粒度でクラスタを観察可能。事前にクラスタ数を決める必要がない（後から切れる）。
短所：計算コストとメモリ消費が大きい。連結法に依存する感度（single linkage のチェイニングなど）。ノイズや外れ値に弱い。
実務での使いどころと応用例
凝集型は次のようなケースで有用です：
データ間の階層的関係を調べたい探索的解析（例：生物系の系統解析、テキストの階層的トピック分析の初期探索）
中小規模なデータで、クラスタの数を事前に決めにくい場合
異なる粒度でのグルーピングを比較したい場合（デンドログラムのカットで容易に変更可能）
実践的なヒント
種類の異なる連結法を試し、結果の違いをデンドログラムで確認する。
距離行列を事前に可視化（ヒートマップ等）すると、構造の有無が分かりやすい。
大きなデータではまずサンプリングして安定性を確認し、その後代表点でクラスタリングを行う。
クラスタリング結果は必ずドメイン知識で解釈し、外部評価（ラベルや業務指標）で確認する。
まとめ
凝集型階層クラスタリングは、データの階層的構造を直感的に可視化できる有力なクラスタリング手法です。連結法や距離尺度、前処理の選択に結果が敏感に依存するため、複数の設定で比較・評価することが重要です。スケーラビリティの制約はあるものの、中小規模データや探索的解析、階層構造を重要視するケースでは非常に有用です。
参考文献
- Hierarchical clustering — Wikipedia
- Ward's method — Wikipedia
- Lance–Williams algorithms — Wikipedia
- SciPy: scipy.cluster.hierarchy — Documentation
- scikit-learn: Agglomerative Clustering — Documentation
- T. Hastie, R. Tibshirani, J. Friedman, "The Elements of Statistical Learning" — 公式サイト
投稿者プロフィール
