階層型クラスタリング

直感 #

合宿で 50 人を住所の近い班に分けるとして、班の数がまだ決まっていない場面を考えます。まず、いちばん家が近い 2 人をペアにします。次に近い 2 人（またはペアと 1 人）をくっつける。この「近いものから順にまとめる」を繰り返すと、小さな塊が大きな塊に育ち、最後は全員が 1 つになります。くっつけた順番と、そのときの距離を枝の高さとして描いた図がデンドログラムです。

凝集型（Agglomerative）の手順は 3 つだけです。まず各サンプルを独立したクラスタとして初期化し、次に現在いちばん近い 2 クラスタを結合して、最後にこの結合を距離が閾値を超えるかクラスタ数が指定数になるまで繰り返します。k-means のように n_clusters を先に決める必要はなく、できあがったデンドログラムで枝の高さが急に跳ぶ所を切れば自然なクラスタ数が読めます。

何が起きているか（ステップで見る） #

コードを読む前に、この手法が図の上で何をしているかを追ってみましょう。「再生」を押すか、スライダーを動かすと 1 手順ずつ進みます。

見るポイント：結合距離が急に大きくなる直前が、クラスター数の目安（デンドログラムの切る高さ）。

式で書くと「クラスタ間の距離」をどう決めているか #

凝集型クラスタリングの各ステップで変わるのは「どの 2 クラスタを結合するか」だけで、その判断はクラスタ間距離（リンケージ基準）$d(C_i, C_j)$ で決まります。点と点の距離はユークリッド距離で決まっていても、点の集まり同士の距離には複数の定義があり、どれを選ぶかでデンドログラムの形が変わります。

Single Linkage（最短距離法） #

2 クラスタの間でいちばん近い点同士の距離を採用します。

近い点が 1 組あれば結合するので、数珠つなぎに並んだ点が端から端まで 1 クラスタになるチェイン効果を起こしやすい反面、三日月のような非球形のクラスタを拾えます。

Complete Linkage（最長距離法） #

2 クラスタの間でいちばん遠い点同士の距離を採用します。

全点が近くないと結合しないので、直径の小さいコンパクトな球状クラスタになり、外れ値 1 点に引きずられにくい点で Single Linkage より頑健です。

Average Linkage（UPGMA; 群平均法） #

2 クラスタ間の全点ペアの距離を平均します。

Single と Complete の中間的な性質を持ち、scikit-learn では linkage="average" で指定します。

Ward 法（分散最小化法） #

クラスタ $C_i$ と $C_j$ を結合したときのクラスタ内平方和（ESS）の増加量 $\Delta$ がいちばん小さいペアを選びます。

$\bar{x}i = \frac{1}{|C_i|}\sum{x \in C_i} x$ はクラスタ $C_i$ の重心、$|\cdot|$ はクラスタに含まれるサンプル数です。重心が近く、かつ小さいクラスタ同士を優先して結合するので、等サイズ・球状のクラスタを見つけやすく、linkage の既定値になっています。ユークリッド距離専用で、affinity を他の距離に変えると使えません。

Lance–Williams 漸化式（一般更新公式） #

クラスタ $C_i$ と $C_j$ を結合して新クラスタ $C_i \cup C_j$ を作ったとき、別のクラスタ $C_k$ との距離は結合前の 3 つの距離だけから更新できます。

4 つの係数をどう置くかでリンケージが決まります。

表の $n_i = |C_i|$, $n_j = |C_j|$, $n_k = |C_k|$ はクラスタのサンプル数です。この漸化式のおかげで、結合のたびに全点ペアの距離を再計算せずに済み、scipy の linkage は $n$ 点の結合を $O(n^2)$ のメモリで処理できます。

Pythonを用いた実験や説明 #

次のコードは make_blobs で 3 つの塊からなる 50 点を作り、scipy の linkage(method="ward") で結合の履歴を計算して dendrogram で樹形図を描きます。縦軸が結合距離で、3 本の太い枝が高い位置でつながる形になります。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import numpy as np
from sklearn.datasets import make_blobs
from scipy.cluster.hierarchy import dendrogram, linkage
import matplotlib.pyplot as plt

X, _ = make_blobs(n_samples=50, centers=3, cluster_std=0.7, random_state=42)

Z = linkage(X, method="ward")  # クラスタ内平方和が最小になるよう結合

plt.figure(figsize=(8, 4))
dendrogram(Z, truncate_mode="level", p=5)
plt.title("階層型クラスタリング（Ward 法）")
plt.xlabel("サンプル")
plt.ylabel("距離")
plt.show()

実行結果の読み方 #

横軸に 50 個のサンプル（または括弧付きの点数）が並び、下の方では高さ 5 以下で細かい結合が続きます。右側の 2 つの塊が高さ約 40 で 1 つになり、最後に左の塊と高さ約 70 でつながるので、高さ 50 で切れば 2 クラスタ、高さ 20 で切れば make_blobs の正解と同じ 3 クラスタになります。この「切る高さ」が次のコードの n_clusters や distance_threshold に対応します。

デンドログラムで切る高さを決めたら、AgglomerativeClustering で各点のラベルを取り出します。次のコードは n_clusters=3 を指定し、クラスタ間距離を群平均法（linkage="average"）で測ります。

1
2
3
4
5
6
7
8

from sklearn.cluster import AgglomerativeClustering

clustering = AgglomerativeClustering(
    n_clusters=3,
    linkage="average",
    affinity="euclidean",
)
labels = clustering.fit_predict(X)

カット高さとクラスタ数 #

スライダーで 30 点のデンドログラムを切る高さを変えると、水平線と交わる枝の本数がそのままクラスタ数になります。高さを 0.1 付近まで下げると細かい結合の下で 10 本以上に分かれ、高さを上げるにつれて 3 本、2 本、最後に 1 本になります。

AgglomerativeClustering でこの操作を再現するときは、distance_threshold に切る高さを渡します。distance_threshold と n_clusters は排他なので、必要な方だけ設定します。

使いどころと落とし穴 #

階層型クラスタリングが向くのは、数千点までのデータで「クラスタ数を決める前に構造を眺めたい」場面と、生物の系統樹や顧客セグメントの入れ子構造のように階層そのものに意味がある場面です。リンケージの選び方が結果を大きく変えます。single は鎖状の構造を拾う代わりにチェイン効果で 1 つに伸びやすく、ward と complete は球状の塊を好みます。一度結合した 2 点は後で分かれないので、k-means のように所属を途中で修正する機会はありません。計算量は $O(n^2)$ 以上です。10 万点を超えるなら k-means で粗く分けてから階層化するか、密度ベースで階層を作る HDBSCAN に切り替えます。

まとめ #

階層型クラスタリングは「いちばん近い 2 クラスタを結合する」を全体が 1 つになるまで繰り返し、結合距離を高さにしたデンドログラムとして履歴を残します。クラスタ間の距離は linkage（single・complete・average・ward）で定義が変わり、Lance–Williams の漸化式で 3 つの距離から効率よく更新されます。scipy の linkage と dendrogram で樹形図を描いて跳びの直前で切る高さを決め、AgglomerativeClustering の n_clusters か distance_threshold にその判断を渡すのが実装の流れです。数千点を超えるデータや鎖状のクラスタには、計算量とリンケージの性質を踏まえて代替手法を選びます。

参考文献 #