最小連結法（単連結法）の基本・実装・応用ガイド｜デンドログラムとSLINK・MSTの活用方法
エバープレイ編集部最小連結法（単連結法）とは
最小連結法（さいしょうれんけつほう、英: single-linkage clustering、単連結法とも呼ばれる）は、階層的凝集（凝集型階層クラスタリング）の一手法で、クラスタ間の距離を「一番近い点どうしの距離」によって定義し、近いクラスタ同士を繰り返し結合していくアルゴリズムです。点群やオブジェクト間の類似度・距離行列を入力として、デンドログラム（樹形図）を作成し、任意の閾値で切ることでクラスタを得ます。
定義と基本的な手順
クラスタ Ci と Cj の間の単連結距離は次で定義されます。
d(Ci, Cj) = min_{x in Ci, y in Cj} d(x, y)
ここで d(x,y) はオブジェクト x と y の距離（例えばユークリッド距離、マンハッタン距離、1−相関係数など）です。基本手順は次の通りです。
- 初期状態：各オブジェクトを1つのクラスタとする（n個のクラスタ）。
- 最も近い2クラスタ（最小の d(Ci,Cj)）を結合する。
- クラスタ数が目的の数になるか、距離閾値まで結合を繰り返す。
- 結合の履歴を記録してデンドログラムを構築する。
アルゴリズム的特徴と計算量
階層的凝集法の単純な実装は、各反復で最小距離ペアを探索して結合し、距離行列を更新するため、実装次第で計算量が大きくなり得ます。一般的なまとめは以下の通りです。
- 単純な実装：O(n^3)（全ペア探索と行列更新を繰り返す場合）
- 改善した実装：ヒープや最近傍探索を用いると O(n^2 log n) 程度に改善可能
- SLINK（Sibson, 1973）：単連結法に特化したアルゴリズムで、O(n^2) の時間複雑度かつ O(n) の追加記憶量でデンドログラム（結合情報）を得られる
また、単連結法は最小全域木（MST：Minimum Spanning Tree）と密接に関連しています。完全グラフに観測点を頂点、距離を辺重みとして置くと、単連結のデンドログラムはその MST の辺を距離順に加える（または重い辺を切る）ことで得られます。したがって、Kruskal のアルゴリズムで MST を作れば、単連結クラスタリングの結合順序が得られ、MST を使った実装は効率的です。
長所（利点）
- 局所的な近接関係を重視するため、細長い形や非球状のクラスタを検出しやすい。
- パラメータが少なく、直感的に理解しやすい（距離定義とカットの閾値のみ）。
- MST を利用することで大規模データに対しても比較的効率的に実装可能（SLINKや Kruskal を利用）。
短所（欠点） — チェイニング効果と感度
単連結法の代表的な問題は「チェイニング（連鎖）効果」です。点が一列につながる（低密度の接続で隣接する点がわずかに近い）場合、実際には別のクラスターであるべき点群が一本の長いチェーンとなって一つのクラスタにまとめられてしまうことがあります。これにより、真のクラスタ構造が不適切に結合されることがあります。
また、外れ値やノイズに敏感で、孤立した点が別のクラスタと連結されることでクラスタ分割が歪むことがあります。距離尺度（スケーリング）に依存するため、前処理として特徴量の正規化や適切な距離尺度の選定が重要です。
実用上の留意点・適用のコツ
- 距離尺度の選定：データの性質に応じてユークリッド、コサイン、相関距離などを選ぶ。特徴量が異次元なら標準化（zスコアなど）を必ず行う。
- デンドログラムの切り方：固定クラスタ数で切る方法のほか、距離の急激な増加（エルボー）や不連続性、inconsistency 指標を用いる。
- ノイズの存在：外れ値除去や、事前に密度ベース（例：DBSCAN）でノイズを除いてから適用するなどの対策を検討する。
- 計算面：データ点数が数万以上になる場合、全距離行列計算はメモリと時間のボトルネックになりやすい。近似手法やサンプリング、または MST ベースの実装を検討する。
他の連結法との比較
- 最大連結法（complete linkage）：クラスタ間距離を「最大距離」で定義。単連結よりチェイニングに強く、コンパクトなクラスタを作る傾向がある。
- 群平均法（average linkage）：クラスタ間の全ての対の平均距離を用いる。バランス型で中間的性質。
- ウォード法（Ward's method）：分散最小化基準に基づきクラスタを結合する。球状クラスタを好む。
用途に応じて、チェイニングの影響を避けたいなら最大連結やウォード法を選ぶのが一般的です。
応用例
- 生物学（系統解析や配列クラスタリング）：類似性に基づく階層構造の抽出。
- 地理情報やセンサーデータ：連続的に変化する空間データのクラスタリング（細長い領域を検出しやすい）。
- 画像処理：ピクセルの近接性を基にした領域分割の一部手法。
- データ可視化：デンドログラムによる階層構造の理解。
実装のヒント（疑似コード）
非常に簡略化した手順の疑似コード：
- 距離行列 D を計算（対角は∞や大きな値にしておく）。
- クラスタ集合を各点の単独集合で初期化。
- while（クラスタ数 > 1）:
- D 内の最小値を持つクラスタペア (i,j) を見つける。
- クラスタ i と j を結合し、結合距離を記録（デンドログラム用）。
- 結合後のクラスタと他のクラスタとの距離を d_new = min(d(i, k), d(j, k)) で更新。
ただし大規模データでは SLINK や MST（Kruskal）に基づく実装を使うことを推奨します。
クラスタの評価
単連結法の評価には一般的なクラスタ評価指標（シルエット係数、ダビーズ・ボルディン指数、輪郭幅など）を用いますが、チェイニングの影響でシルエットが低く出る場合があります。ドメイン知識に基づく可視化（デンドログラム、MDS や t-SNE による散布図）と組み合わせて検証するのが現実的です。
まとめ
最小連結法（単連結法）は、近接性を重視した階層的凝集法であり、細長い形状のクラスタを検出しやすい一方でチェイニング現象やノイズに弱いという特徴があります。MST と深い関係があり、効率的な実装（SLINK や MST を利用）により実用的に利用できます。用途やデータの性質に応じて距離尺度や前処理、他の連結法との比較を行うことが重要です。
参考文献
- 単連結法 - Wikipedia（日本語）
- scikit-learn: Hierarchical clustering — Agglomerative Clustering
- R. Sibson (1973), "SLINK: an optimally efficient algorithm for single-link cluster analysis", The Computer Journal, 16(1), 30–34.
- Single-linkage clustering - Wikipedia (English)
- Kaufman, L. & Rousseeuw, P. J. (1990). Finding Groups in Data: An Introduction to Cluster Analysis. Springer.
投稿者プロフィール
