ウォード法とは？階層的凝集クラスタリングの最小分散法を徹底解説
エバープレイ編集部ウォード法とは──概要
ウォード法（Ward's method）は、階層的凝集クラスタリング（hierarchical agglomerative clustering）の一手法で、「クラスタ内の分散の増加を最小にする」ことを基準にクラスタを次々と結合していくアルゴリズムです。別名「最小分散法（minimum variance method）」とも呼ばれ、各ステップで結合するクラスタのペアを選ぶ際に、結合によって生じる総クラス内平方和（within-cluster sum of squares, WSS）の増加量を評価して、これを最小化するペアをマージします。
アルゴリズムの直感と特徴
直感的には、ウォード法は「各クラスタの中心（平均）をベースにした結合」を行います。点群をクラスタに分けたときの誤差の総和（SSE/WSS）を評価し、異なるクラスタを結合したときにその誤差がどれだけ増えるかを計算して最小の増加となる結合を繰り返します。そのため、
- クラスタは比較的「球状（等方的）で均一な大きさ」を形成しやすい
- 外れ値やスケールに敏感（変数の標準化が重要）
- 非ユークリッド距離や任意の距離には直接適用できない（通常はユークリッド距離の二乗に基づく）
数学的定義（増加量の式）
2つのクラスタ A, B を結合したときに総WSSがどれだけ増えるか（Δ(A,B)）は、ユークリッド距離とクラスタサイズ（データ点数 n_A, n_B）を用いて次のように書けます：
Δ(A,B) = (n_A * n_B) / (n_A + n_B) * ||μ_A - μ_B||^2
ここで μ_A, μ_B はそれぞれクラスタ A, B の平均（重心）ベクトルで、||·|| はユークリッドノルムです。つまり、クラスタ間の重心距離の二乗に重み（調和的なサイズ因子）が掛かって増加量が決まります。この増加量が最小のペアを逐次マージしていくのがウォード法の核心です。
Lance–Williams 更新式との関係
階層的凝集法は多くの場合、既存の距離（非類似度）行列を更新するために Lance–Williams の一般的な再帰式を使います。ウォード法はその特殊例として、3つのクラスタ i, j, k があるときの距離更新が次の形で表現できます：
d(i∪j, k) = ((n_i + n_k) d(i, k) + (n_j + n_k) d(j, k) - n_k d(i, j)) / (n_i + n_j + n_k)
ここで d(·,·) はクラスタ間の（通常は二乗）ユークリッド距離、n_x はクラスタ x のサイズです。この式により、効率的に距離行列を更新できます。実装によっては距離ではなく「二乗距離」を扱うことに注意してください。
実装上の注意点とソフトウェア間の差異
ウォード法は理論的には総WSSを最小化する方法ですが、ソフトウェア実装には細かな差が存在します。代表的な注意点は次の通りです：
- ユークリッド距離の二乗を使うことが前提：多くの実装（SciPy、scikit-learn の linkage/ward 実装など）はユークリッド距離（または特徴行列）を前提にしています。非ユークリッド距離や事前に計算した距離行列を直接与えると期待した結果にならないことがあります。
- R の hclust では method="ward.D" と method="ward.D2" の2種類があり、挙動が異なる点に注意が必要です。一般に "ward.D2" の方が数学的に「最小分散法（squared Euclidean）」の基準と一致する実装で、他ライブラリと結果が同じになることが多い、と説明されることがあります（環境・データの扱いによって違いが出ます）。
- 前処理（スケーリング、標準化、外れ値処理）が結果に強く影響します。変数ごとのスケール差があると距離計算により大きく影響するため、標準化（zスコア等）や主成分分析（PCA）で次元削減を行うことが推奨されます。
計算量と実装の実際
単純な実装では、データ点数 n に対して O(n^3) の時間計算量を要することが多く、大規模データには不向きです。ただし、Lance–Williams の再帰式を利用することで距離行列更新を効率化でき、実用的なライブラリ（SciPy、scikit-learn、R など）は最適化済みの実装を提供しています。それでも数万点規模のデータを扱う場合は計算・メモリ負荷が大きく、近似法や別のクラスタリング手法（k-means、DBSCAN、スペクトラルクラスタリング等）の検討が現実的です。
長所・短所（まとめ）
- 長所
- クラスタの内部分散を直接抑えるため、コンパクトで均質なクラスタを得やすい。
- 階層的情報（デンドログラム）を同時に得られるので、クラスタ数を変えて分析できる。
- 短所
- 外れ値に敏感で、外れ値があるとクラスタ構造を歪めやすい。
- スケール依存（前処理が必須）。
- 大規模データでは計算負荷が高い。
実務での使いどころと応用例
ウォード法は次のような場面で有用です：
- 顧客データのセグメンテーションで、均一な集団を作りたいとき（数変数の数値データ）
- 遺伝子発現データやプロファイリングで、類似したパターンを示すグループを階層的に解析したい場合
- 可視化目的でのデンドログラム作成（階層を観察して最適なクラスタ数を決める）
ただし、変数が多く高次元な場合は距離の集中化やノイズの影響が出やすいため、PCA 等で次元削減してから適用することが多いです。
実際に使うときのチェックリスト
- データが数値（連続）であるか確認する。カテゴリ変数は距離定義が異なるため注意。
- 変数ごとにスケールが揃っているか（標準化の実施）。
- 外れ値処理を行う（必要なら除外やロバストな前処理）。
- 使用するソフトウェアの「ウォード」の実装差（例：Rの ward.D と ward.D2）を理解しておく。
- 得られたデンドログラムを可視化し、適切なクラスタ数を確認する（エルボー、シルエット等で補助評価）。
まとめ
ウォード法は「クラスタ内分散の最小化」という明確な目的関数に基づく階層的凝集法で、コンパクトで均一なクラスタを作りやすい一方、外れ値やスケールに敏感で大規模データには計算負荷が高いという実用上の制約があります。使う際は前処理（標準化や外れ値対策）と実装差（ソフトウェアごとの扱い）に注意すれば、探索的データ解析や階層構造の把握に強力なツールとなります。
参考文献
- Ward, J. H. (1963). Hierarchical Grouping to Optimize an Objective Function. Journal of the American Statistical Association, 58(301), 236–244.
- Wikipedia: Ward's method
- SciPy docs: scipy.cluster.hierarchy.ward
- scikit-learn: Hierarchical clustering (Ward)
- R: hclust (stats package) — ward.D と ward.D2 の説明を含むドキュメント
投稿者プロフィール
