凝集型クラスタリング徹底解説：デンドログラムと結合基準・距離尺度の実務活用
エバープレイ編集部凝集型クラスタリングとは
凝集型クラスタリング（agglomerative clustering、凝集型階層クラスタリングとも呼ばれる）は、個々のデータ点からスタートして類似したデータ点同士を段階的に結合していく階層的クラスタリング手法の一つです。まず各データ点を1つのクラスタとみなし、最も近い（あるいは最も類似した）クラスタの対を繰り返し結合していくことで、最終的に1つのクラスタに統合するまでの階層構造（デンドログラム）を構築します。教師なし学習の代表的手法で、クラスタ数を事前に指定しなくても階層を切ることで任意のクラスタ数を得られる点が特徴です。
基本アルゴリズムの流れ
- 初期化：n個のデータ点それぞれを1クラスタとして扱う。
- クラスタ間距離の計算：クラスタ間の距離（または類似度）を定義する。
- 最小距離対を結合：最も距離が小さいクラスタペアを結合して新しいクラスタを作る。
- 距離行列の更新：新クラスタと他クラスタ間の距離を再計算する（結合規則に依る）。
- 停止条件：クラスタ数が所望値になる、または距離閾値を超えたところで階層を切る。
この繰り返しにより、データ点の結合履歴がツリー構造（デンドログラム）として記録されます。
クラスタ間距離（結合基準）
凝集型クラスタリングで最も重要なのは「どのようにクラスタ同士の距離を定義するか（結合基準）」です。代表的な方法は次のとおりです。
- 単連結（single linkage）：二つのクラスタ間で最も近い点同士の距離を使う。チェイニング（鎖状に伸びる）現象が起きやすいが、非球状のクラスタを見つけやすい。
- 完全連結（complete linkage）：二つのクラスタ間で最も遠い点同士の距離を使う。コンパクトで径の小さいクラスタを好む。
- 平均連結（average linkage, UPGMA）：クラスタ間のすべての点対距離の平均を使う。単・完全の中間的性質を持つ。
- ワード法（Ward法）：クラスタ内分散の増加が最小になるように結合を行う。結果としてほぼ球状のクラスタを生成する傾向があり、特に実数ベクトル空間（ユークリッド距離）で有効。
各手法はデータの分布やノイズに対して感度が異なるため、目的やデータ特性に応じて使い分ける必要があります。
距離尺度（メトリック）の選び方
距離尺度（ユークリッド距離、マンハッタン距離、コサイン類似度など）も結果に大きく影響します。ワード法は基本的にユークリッド距離に対応するため、連続値データでは標準化（平均0、分散1）を行うことが推奨されます。テキストのような高次元かつスパースなデータではコサイン類似度などが適する場合があります。カテゴリカル変数が混在する場合はガワー距離（Gower distance）など混合型距離を検討します。
デンドログラムとクラスタの切り方
凝集型クラスタリングの出力はデンドログラムとして視覚化するのが一般的です。デンドログラムの垂直軸は結合時の距離（不一致度）を示し、枝を水平にカットすることで所望のクラスタ数を得られます。クラスタ数kを直接指定して探索する方法のほか、距離の閾値で切る方法、さらにはシルエット係数やDavies–Bouldin指数など外的／内的評価指標を用いて最適な切り位置を推定する方法があります。
計算量とスケーラビリティの課題
凝集型クラスタリングの計算量は実装方法や結合基準により異なりますが、一般に距離行列を保持するためメモリはO(n^2)、計算量は最悪でO(n^3)になることがあります。近年の改良（最近傍チェーン法など）でO(n^2)まで下げられる場合が多いですが、大規模データ（数万〜数百万サンプル）には不向きです。そのため大規模データでは以下の代替手段を検討します。
- BIRCH（分割と要約を組み合わせる手法）
- K-meansやミニバッチK-meansで前処理的に粗クラスタを作る
- 近似近傍探索（ANN）や局所的な凝集による加速
- 密度ベースの手法（HDBSCANなど）や分割型階層（DIANA）の採用
長所・短所
- 長所
- 階層構造を得られるため、異なる粒度でクラスタを観察できる。
- クラスタ数を事前に決める必要がない（デンドログラムの切り方で決定）。
- 非凸形状や異なる大きさのクラスタを検出できる場合がある（特に単連結）。
- 短所
- 計算コストとメモリコストが大きく、大規模データには向かない。
- ノイズや異常値に敏感で、特に単連結はチェイニングを生じやすい。
- 結合の初期段階の誤った結合がその後の階層全体に影響を与える（局所最適）。
実務でのポイントと実装上の注意
- 特徴量のスケーリング：距離ベースのため標準化や正規化は必須に近い。
- 欠損値処理：距離計算前に適切に欠損を扱う（補完や削除）。
- 結合基準の選択：データの期待されるクラスタ形状に応じてsingle/complete/average/Wardを選ぶ。
- ワード法は通常ユークリッド距離専用である点に注意（実装により異なる）。
- Python実装ではscipy.cluster.hierarchy（linkage, dendrogram）やscikit-learnのAgglomerativeClusteringがよく使われる。scikit-learnの実装は大規模データ向けに近似的最適化がなされている場合があるが、距離行列を事前に与えるときの制約（Wardでは不可など）に注意する。
- クラスタ数の決定は内的評価（シルエット等）やドメイン知識、デンドログラムの急激な距離増加点（エルボー）などを組み合わせる。
実用的なテクニックと改善方法
- 前処理で主成分分析（PCA）など次元削減を行い、距離計算を安定化させる。
- まずサンプリングで凝集型を適用し、代表クラスタ中心を基に全体を割り当てる。
- 近接グラフ（k近傍グラフ）を使った局所結合や制約付きクラスタリング（connectivity）で計算を削減。
- 外れ値の除去やロバストスケーリング（median/MAD）でノイズの影響を抑える。
代表的な適用例
- 少〜中規模のデータセットの探索的データ分析（EDA）で階層的構造を把握する。
- 文書や遺伝子発現データのような階層的なトピック／機能分類の発見。
- マーケティングでの顧客セグメンテーション（少数の特徴量で可視化しやすい場合）。
- 生物学の系統解析（ただし専門の系統樹推定法が別にある）。
まとめ
凝集型クラスタリングは、データを階層的にまとめ上げるシンプルで理解しやすい手法です。デンドログラムによる可視化や多段階の粒度でクラスタを観察できる利点がある一方、計算量やノイズへの感度が課題です。実務では前処理（スケーリング、次元削減）、適切な結合基準の選択、そしてクラスタ数の決定基準の組み合わせがカギになります。大規模データやノイズ多めのデータには、BIRCHやHDBSCAN、K-meansを併用するなど実装面での工夫が必要です。
参考文献
- Hierarchical clustering — Wikipedia
- scikit-learn: Hierarchical clustering — AgglomerativeClustering
- SciPy: scipy.cluster.hierarchy.linkage
- Ward's method — 解説（参考）
- T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning
- Kaufman, L. and Rousseeuw, P.J., Finding Groups in Data: An Introduction to Cluster Analysis (参考書)
投稿者プロフィール
