完全連結法で学ぶ階層的クラスタリングの基礎と実務活用：定義・アルゴリズム・前処理・デンドログラムの解釈
エバープレイ編集部完全連結法とは
完全連結法（かんぜんれんけつほう、complete linkage）は、階層的凝集型クラスタリング（階層的クラスタリング、agglomerative hierarchical clustering）のリンク法（linkage method）の一つです。クラスタ間の距離を「クラスタ内の全ての点の組み合わせの中で最も遠い点同士の距離（最大距離、furthest neighbor）」で定義し、その距離が最も小さくなるクラスタペアを順に結合していきます。結果として、各クラスタの「直径（diameter）」が比較的小さく抑えられる、いわゆる「緊密で球状に近い」クラスタを得やすい手法です。
形式的定義
点集合 X をクラスタとするとき、クラスタ A, B 間の完全連結距離 d_complete(A,B) は次で定義されます。
d_complete(A,B) = max_{x in A, y in B} d(x,y)
ここで d(x,y) は点同士の距離（ユークリッド距離、マンハッタン距離、コサイン距離など適宜選択）。完全連結法では、この距離を用いて最も近い（＝最大距離が最も小さい）クラスタペアを繰返しマージしていきます。
アルゴリズムの流れ（概要）
- 各データ点を1つのクラスタとして開始。
- 全てのクラスタペアについて完全連結距離を計算。
- 距離が最小のクラスタペアを結合し、新たなクラスタを作成。
- 新クラスタと残りのクラスタとの距離（完全連結距離）を再計算。
- クラスタ数が所望に達するか、距離を閾値でカットするまで 3–4 を繰返す。
特徴と直感的な挙動
- クラスタ直径の抑制：マージ条件がクラスタ間の最長距離に依存するため、内部の最大距離が大きくならないようなクラスタを作る傾向があります。結果として、比較的「均質で密な」クラスタが得られます。
- チェイニング現象の回避：単一連結法（single linkage）は「チェイニング（鎖状）」になりやすいのに対し、完全連結法はこれを抑制します。単一連結は最短距離で結合するため細長い連鎖ができやすいのに対し、完全連結は最大距離を使うため連鎖がつながりにくくなります。
- アウトライアの影響：最大距離に依存するため、クラスタ内に孤立した外れ値があるとそのクラスタの距離が大きくなり、マージが抑えられる・分割されることがあり得ます。したがって外れ値があるデータでは注意が必要です。
利点
- 比較的コンパクトで一様なサイズ・形状のクラスタを生成しやすい（特に球状に近いクラスタに適している）。
- チェイニングの問題が少なく、明確な塊（clusters）を見つけやすい。
- アルゴリズムの概念が単純で理解しやすい。
欠点・注意点
- 計算量とメモリ：階層的凝集クラスタリングの単純実装は計算量が O(n^3)（n はデータ数）だが、実装の工夫により O(n^2) 程度に改善される。とはいえ大規模データ（例えば数万点以上）には計算・メモリの負担が大きくなる。
- 外れ値への感度：外れ値がクラスタの最大間隔を押し上げ、マージを妨げることがある。
- クラスタ形状の制約：非球状・非等方的なクラスタ（長細い形状や密度が異なる領域）を正しく捉えにくいケースがある。
- リンク法の選択依存性：データに対してどのリンク法が良いかは一概に決まらず、単一連結・平均連結・Ward法などと比較検討が必要。
単一連結法や平均連結法との比較
- 単一連結（single linkage）：クラスタ間の最短距離を用いる。チェイニングが生じやすいが、非球状クラスターや連結構造を検出しやすい。
- 平均連結（average linkage、UPGMAなど）：クラスタ間の全ての点の平均距離を用いる。完全連結と単一連結の中間的挙動を示す。
- Ward法：分散の増加を基準にクラスタを結合し、通常はコンパクトで等分散なクラスタを形成する。完全連結と似ている性質を示す場合があるが、目的関数が異なる。
実務上の注意点（前処理と距離選択）
- 標準化・スケーリング：異なるスケールの特徴が混在する場合、距離計算で特定の特徴が支配的にならないよう標準化（zスコア）や正規化を行う。
- 距離指標の選択：ユークリッド距離は多く用いられるが、カテゴリ変数やコサイン類似度を使いたい場合は距離計を適切に選定する。
- 外れ値処理：外れ値が結果に大きく影響する可能性があるため、事前に検出・除去・ロバスト化（例：距離のロバスト化変換）を検討する。
デンドログラムの解釈と切断（カット）
完全連結法で得られるデンドログラム（樹形図）は、クラスタ間のマージ高さ（距離）が比較的均一に保たれる傾向があります。デンドログラムをカットすることで任意のクラスタ数を得られますが、どこで切るかはドメイン知識・シルエット幅やコフェネティック相関係数（cophenetic correlation coefficient）などの指標、あるいは閾値に基づいて決めます。
実装例（一般的なライブラリ）
- Python（SciPy）：scipy.cluster.hierarchy.linkage(X, method='complete') で完全連結を指定。dendrogram 関数で可視化可能。
- R：hclust(dist(X), method='complete') で実行。切断は cutree() で行う。
- 多くの機械学習ライブラリでサポートされており、距離行列さえ与えれば適用可能。
適用領域と実例
完全連結法は、顧客セグメンテーション、文書のクラスタリング（TF-IDF＋コサイン距離など適用可）、遺伝学での系統解析的近似（ただし専用手法が多い）、画像の特徴ベースクラスタリングなどで利用されます。特に「クラスタ内部が均一で、外側と明確に分離される」ことが期待されるケースで有効です。
評価と検証
- 内部評価指標：シルエット係数、Davies–Bouldin 指数、クラスタ内分散など。
- 外部評価指標：事前にラベルがある場合は Adjusted Rand Index（ARI）や正解率などで評価。
- コフェネティック相関係数：デンドログラムが元の距離行列をどれだけ忠実に表現しているかを測る指標として用いる。
まとめ：どんな時に使うべきか
完全連結法は、コンパクトで分離の良いクラスタを得たい場合に有効な階層的クラスタリング手法です。チェイニングを避けたい場面やクラスタの最大直径を制御したい場合に向いています。一方で外れ値や大規模データ、非球状クラスタに対しては適用前の前処理や他手法との比較検討が重要です。距離の選択、スケーリング、外れ値処理、クラスタ数の決定基準を慎重に扱うことで、実務で有用な結果が得られます。
参考文献
- 階層的クラスタリング - Wikipedia（日本語）
- Hierarchical clustering — Linkage methods (Wikipedia, English)
- scipy.cluster.hierarchy.linkage — SciPy documentation
- hclust — R Documentation (stats パッケージ)
- Kaufman, L. & Rousseeuw, P. J., Finding Groups in Data (1990) — クラスタリングの古典的教科書
投稿者プロフィール
