ウォード法

併合する組を決める基準

階層的クラスタリングのうち、データ点を1つずつのクラスタとして始め、近いものどうしを順に併合していくやり方では、各段階で「どの2つのクラスタを次に併合するか」を決める基準が必要です。ウォード法は、この基準の1つです。

ウォード法が見るのは、クラスタ内の誤差平方和(error sum of squares)です。あるクラスタの誤差平方和は、そのクラスタに属する各データ点と、クラスタの中心(属する点の平均)との距離を2乗し、すべて足し合わせた値です。値が小さいほど、クラスタ内の点が中心の近くにまとまっていることを表します。

2つのクラスタを1つに併合すると、新しいクラスタの中心は元の2つの中心の間に移るため、誤差平方和の合計は増えます。ウォード法は、候補となるすべての組について、この増加分を計算し、増加分が最も小さい組を併合します。言い換えると、併合のたびに「まとまりの悪さ」の増え方をできるだけ抑えていく手法です。

増加分と中心間の距離の関係

Wardの手法を調べたマータフ(Fionn Murtagh)とルジャンドル(Pierre Legendre)の2011年の論文は、先行研究の説明を引いて、この増加分がクラスタ中心どうしの2乗ユークリッド距離に比例すると述べています。中心どうしが離れているクラスタを併合するほど、新しい中心から見た点のばらつきが大きくなり、誤差平方和の増加も大きくなる、という関係です。

小さな数値例で確かめる

1次元の値で考えます。いま、次の3つのクラスタがあるとします。

• クラスタA: 1と2(中心1.5、誤差平方和0.5)
• クラスタB: 4(中心4、誤差平方和0)
• クラスタC: 10(中心10、誤差平方和0)

3通りの併合について、併合後の誤差平方和と増加分を計算します。

増加分が最も小さいのはAとBの組なので、ウォード法はまずAとBを併合します。中心間の距離の2乗はAとBが6.25、BとCが36、AとCが72.25で、この例でも中心どうしが近い組ほど増加分が小さくなっています。

使うときの前提と注意

• クラスタの中心を平均で求め、距離をユークリッド距離で測るので、平均や距離に意味がある数値の特徴量を前提にしています。
• 特徴量ごとに単位や尺度が大きく違うと、値の幅が大きい特徴量が距離をほぼ決めてしまいます。必要に応じて、あらかじめ尺度をそろえてから使います。
• ウォード法は併合の順序を決める基準であり、最終的にいくつのクラスタに分けるかは決めません。併合の過程を樹形図で表し、どの高さで切るかを別に判断します。

名前の由来

マータフとルジャンドルの論文によれば、手法の名前は、1963年の論文でこの手法を初めて記述したウォード(Joe H. Ward, Jr.)に由来し、それ以来非常に広く使われてきたとしています。