単連結法（Single Linkage）入門：階層的クラスタリングの基礎からMST・SLINKまで徹底解説
エバープレイ編集部単連結法（single linkage）とは
単連結法（たんれんけつほう、英: single linkage）は、階層的凝集型クラスタリング（Hierarchical Agglomerative Clustering, HAC）の代表的なリンク法の一つで、クラスタ間の距離を「クラスタに属する任意の2点間の距離の最小値」で定義して逐次クラスタを結合していく手法です。近接している個々のデータ点同士をつなげていくため、非球状の連続した形状（鎖状や曲線状）のクラスタを発見しやすい一方で、「チェイニング効果」により遠く離れた点同士が中間の点列によって連結されてしまいやすいという特徴があります。
基本アルゴリズムの流れ
- 入力：各データ点間の距離（または不相似度）行列 D（任意の距離指標が利用可能）。
- 初期化：各データ点を1つのクラスタとして扱う（n クラスタ）。
- 反復：
- 現在のクラスタ間の距離を単連結の定義（任意の点対間の最小距離）で評価する。
- 最も距離が小さい2つのクラスタを結合する。
- 結合後、クラスタ間距離を再計算する（単連結では新クラスタと他クラスタ間はそれぞれのクラスタ内の点間距離の最小値）。
- 必要なクラスタ数になるか、あるいは全点が1つのクラスタになるまで繰り返す。
数学的定義（距離の更新規則）
クラスタ A と B を結合して新クラスタ A∪B を作るとき、任意の他クラスタ C との距離 d(A∪B, C) は次で定められます：
d(A∪B, C) = min( d(A, C), d(B, C) )
ここで d(X, Y) はクラスタ X と Y の間の距離で、単連結法ではクラスタ内の任意の点 i∈X, j∈Y の間の距離 d(i,j) の最小値として定義されます。
特徴と長所・短所
- 長所
- クラスタの形状に柔軟で、非球状や細長いクラスタを検出しやすい。
- 任意の距離（ユークリッド、マンハッタン、コサイン類似度の不相似化など）を入力として扱える。
- しきい値（距離のカットオフ）により直感的にクラスタを切り出せる。
- 短所
- チェイニング効果：個々の近接点が連なって、本来別のまとまりであるべき集合がつながってしまうことがある。
- 外れ値やノイズに弱い（ノイズ点が橋渡し役をしてクラスタを連結してしまう）。
- 大規模データでは計算量が問題になる（距離行列のサイズや更新のコスト）。
単連結法と最小全域木（MST）の関係
単連結法は最小全域木（Minimum Spanning Tree, MST）との深い関係があります。完全グラフにおいて各辺の重みをデータ点間の距離とすると、Kruskal のアルゴリズムで得られる最小全域木を辺の長さが短い順に切断することで得られる連結成分は、単連結クラスタリングで同様の結合順序になります。言い換えれば、MST を構成してから長い辺を切ることで単連結のクラスタを効率的に得ることができます。MST ベースの手法を用いると、完全な距離行列を扱うよりも計算実装上有利な場合があります（例えば疎な近傍グラフを利用する場合）。
計算量と実装上の注意
- 単純な実装（距離行列を更新しながら最短距離ペアを毎回探索）では O(n^3) の時間がかかる場合があり、大きな n に対して非現実的です。
- しかし、単連結特化のアルゴリズムとして SLINK（Sibson, 1973）などがあり、O(n^2) 時間かつ O(n) の追加記憶で階層構造を生成可能です（出力として完全な結合距離行列やデンドログラムの形式次第でメモリ要件は変動します）。
- MST をまず構築し（例：Kruskal のアルゴリズム）、その後で距離に基づいてエッジを切る手法は、実装上効率的であり、実データにおける近傍グラフの構築と組み合わせることでさらに高速化できます。
- 多次元大規模データでは近似的手法やサンプリング、局所近傍探索（k-NN グラフ）と組み合わせるのが現実的です。
他のリンク法との比較
- 完全連結法（complete linkage）: クラスタ間距離を最大値で定義するため、よりコンパクトで球状に近いクラスタを作りやすく、チェイニングの影響は小さいが形状の自由度が下がる。
- 平均連結法（average linkage、UPGMA）: クラスタ間距離を平均値で定義し、single と complete の中間的な性質を持つ。
- ウォード法（Ward）: クラスタ内分散の増加量を基準に結合を行い、全体として分散最小化を目指す。球状クラスタや分散基準での性能が良い。
- 用途に応じてリンク法を選ぶことが重要。例えばクラスタが連続的に伸びる構造を捉えたい場合は単連結が有効だが、ノイズが多いデータや均衡したコンパクトなクラスタを求める場面では別の手法が適する。
実務上の使いどころと注意点
- 探索的データ解析：データの大まかな構造（連続性や鎖状の構造）を把握するときに有用。
- 閾値によるクラスタ抽出：特定の距離カットオフでクラスタを直感的に切り出せる。
- 前処理：スケーリング（標準化や正規化）や距離指標の選択はクラスタ結果に強く影響する。特に異なるスケールの特徴を持つデータでは標準化が必須。
- 距離の定義：数値データではユークリッド距離やマンハッタン距離が一般的だが、コサイン距離や相関距離など問題に応じて選ぶ。単連結は任意の非負の距離（不相似度）を使える。
- ノイズ対策：外れ値やノイズが多いデータでは事前に外れ値除去やロバストな距離尺度（例えば局所密度を利用するなど）を検討する。
実装例（ライブラリ）
Python 環境では以下のようなライブラリが代表的です：
- SciPy（scipy.cluster.hierarchy.linkage）: method='single' を指定すると単連結が使える。内部的に効率化された実装があり、デンドログラム描画や距離行列の取り扱いが容易。
- scikit-learn（sklearn.cluster.AgglomerativeClustering）: linkage='single' が選べる。大規模データや接続制約を与える場合のオプションがあるが、事前に距離行列を用意する際の注意点やメモリ使用量に留意。
- 専用実装として SLINK を用いた実装も存在し、特に単連結に最適化したアルゴリズムは計算資源を節約できる。
実例（直感的イメージ）
例えば円弧状に分布した2つの長いデータ列があった場合、単連結法はそれぞれのデータ列の近い点同士を順に結合して円弧を1つのクラスタとして認識しやすいです。一方、同じデータセットで完全連結法を使うと、各クラスタの「最遠点」が大きいため2つに分かれる可能性があります。
まとめ
単連結法はシンプルで直感的、非球状クラスタを捉えやすい一方でチェイニングやノイズに弱いというトレードオフがあります。計算資源やノイズの有無、期待するクラスタ形状に応じて適切なリンク法を選ぶことが重要です。MST といったアルゴリズム的な関係や SLINK のような最適化手法を活用することで、現実的なスケールでも利用可能です。
参考文献
- Single-linkage clustering — Wikipedia (英語)
- scipy.cluster.hierarchy.linkage — SciPy ドキュメント
- Hierarchical clustering — scikit-learn ドキュメント
- R. Sibson, "SLINK: an optimally efficient algorithm for single-link cluster analysis", The Computer Journal, 1973 (SLINK 論文)
- Minimum spanning tree — Wikipedia (英語)
投稿者プロフィール
