階層型クラスタリング

直感 #

階層型クラスタリングは「似ているものからまとめていく」または「大きなクラスタを分割していく」ことで、クラスタの親子関係を構築します。
デンドログラム（樹形図）で距離の大きいところを切ると自然なクラスタ数を選べるため、クラスタ数を事前に決めたくない場合に便利です。凝集型（一般的な手法）では以下を繰り返します。

1. 各サンプルを独立したクラスタとして初期化。
2. 現在最も近い 2 クラスタを結合。
3. 距離が閾値を超えるまで、またはクラスタ数が指定数になるまで繰り返す。

具体的な数式 #

凝集型クラスタリングでは、各ステップで「どの 2 クラスタを結合するか」をクラスタ間距離（リンケージ基準）によって決定します。クラスタ $C_i$, $C_j$ の間の距離 $d(C_i, C_j)$ はリンケージの種類によって以下のように定義されます。

Single Linkage（最短距離法） #

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

チェイン効果（鎖状に伸びるクラスタ）を起こしやすい反面、非球形のクラスタを検出できる利点があります。

Complete Linkage（最長距離法） #

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

コンパクトな球状クラスタを作りやすく、外れ値に対して Single Linkage より頑健です。

Average Linkage（UPGMA; 群平均法） #

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

Single と Complete の中間的な性質を持ち、実用上バランスの取れた選択肢です。

Ward 法（分散最小化法） #

クラスタ $C_i$ と $C_j$ を結合したときのクラスタ内平方和（ESS）の増加量 $\Delta$ を最小化するようにペアを選びます。

ここで $\bar{x}i = \frac{1}{|C_i|}\sum{x \in C_i} x$ はクラスタ $C_i$ の重心、$|\cdot|$ はクラスタに含まれるサンプル数を表します。Ward 法はユークリッド距離専用ですが、等サイズ・球状のクラスタを見つけやすく、最もよく使われるリンケージの一つです。

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

クラスタ $C_i$ と $C_j$ を結合して新クラスタ $C_i \cup C_j$ を作ったとき、別のクラスタ $C_k$ との距離は次の漸化式で効率よく更新できます。

各リンケージに対応するパラメータは以下の通りです。

ここで $n_i = |C_i|$, $n_j = |C_j|$, $n_k = |C_k|$ です。この漸化式により、結合ごとにすべての点ペア距離を再計算する必要がなくなり、計算量を大幅に削減できます。

Pythonを用いた実験や説明 #

scipy でデンドログラムを描画し、AgglomerativeClustering で実際のラベルを得る例を示します。

 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()

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)

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

デンドログラムのカット高さを変えるとクラスタ数がどう変わるか確認できます。

参考文献 #