ウォード法

統計学において、ウォード法は階層的クラスター分析に適用される基準です。ウォードの最小分散法は、もともとジョー・H・ウォード・ジュニア^{[1]によって提示された}目的関数アプローチの特殊なケースです。ウォードは、各ステップでマージするクラスターのペアを選択する基準が目的関数の最適値に基づく、一般的な凝集型階層的クラスタリング手順を提案しました。この目的関数は、「調査者の目的を反映する任意の関数」である可能性があります。標準的なクラスタリング手順の多くは、この非常に一般的なクラスに含まれています。手順を説明するために、ウォードは目的関数が誤差の二乗和である例を使用しました。この例は、ウォード法、またはより正確にはウォードの最小分散法として知られています。

最近傍連鎖アルゴリズムを使用すると、ウォード法で定義された同じクラスタリングを、入力距離行列のサイズに比例した時間と、クラスタリングされるポイントの数に比例した空間で見つけることができます。

Ward の最小分散基準は、クラスター内の総分散を最小化します。この方法を実装するには、各ステップで、マージ後のクラスター内の総分散の増加が最小になるクラスターのペアを見つけます。この増加は、クラスターの中心間の重み付き二乗距離です。最初のステップでは、すべてのクラスターはシングルトン (単一のポイントを含むクラスター) です。この目的関数で再帰アルゴリズムを適用するには、個々のオブジェクト間の初期距離は、ユークリッド距離の二乗 (に比例) である必要があります。

したがって、ウォードの最小分散法における初期クラスター距離は、ポイント間のユークリッド距離の二乗として定義されます。

${\displaystyle d_{ij}=d(\{X_{i}\},\{X_{j}\})={\|X_{i}-X_{j}\|^{2}}.}$

注: Ward 法を実装するソフトウェアでは、関数の引数でユークリッド距離を指定するか、ユークリッド距離の 2 乗を指定するかを確認することが重要です。

Ward の最小分散法は、Lance-Williams アルゴリズムによって再帰的に定義および実装できます。Lance-Williams アルゴリズムは、各ステップ (クラスターのペアがマージされるたびに) でクラスター距離を更新するための再帰式で表される、凝集型階層的クラスタリング アルゴリズムの無限ファミリです。各ステップで、目的関数を最適化する必要があります (マージするクラスターの最適なペアを見つける)。再帰式により、最適なペアを簡単に見つけることができます。

次にクラスターと がマージされると仮定します。この時点で、現在のペアワイズクラスター距離はすべてわかっています。再帰式は、保留中のクラスターとのマージ後の更新されたクラスター距離を示します。 ${\displaystyle C_{i}}$${\displaystyle C_{j}}$${\displaystyle C_{i}}$${\displaystyle C_{j}}$

• ${\displaystyle d_{ij}}$、、をそれぞれクラスター、、および間のペアワイズ距離とする。${\displaystyle d_{ik}}$${\displaystyle d_{jk}}$${\displaystyle C_{i}}$${\displaystyle C_{j}}$${\displaystyle C_{k}}$
• ${\displaystyle d_{(ij)k}}$新しいクラスターとの間の距離です。${\displaystyle C_{i}\cup C_{j}}$${\displaystyle C_{k}}$

更新されたクラスタ距離が再帰的に計算できる 場合、そのアルゴリズムはランス・ウィリアムズ族に属する。${\displaystyle d_{(ij)k}}$

${\displaystyle d_{(ij)k}=\alpha _{i}d_{ik}+\alpha _{j}d_{jk}+\beta d_{ij}+\gamma |d_{ik}-d_{ jk}|,}$

ここで、およびは、クラスターのサイズに依存する可能性のあるパラメータであり、クラスター距離関数とともにクラスタリングアルゴリズムを決定します。シングルリンク、完全リンク、グループ平均法などのいくつかの標準的なクラスタリングアルゴリズムには、上記タイプの再帰式があります。標準的な方法のパラメータ表は、複数の著者によって提供されています。^{[2] [3] [4]}${\displaystyle \alpha _{i},\alpha _{j},\beta ,}$${\displaystyle \gamma}$${\displaystyle d_{ij}}$

ウォードの最小分散法は、ランス・ウィリアムズの公式によって実装できます。サイズがそれぞれ と である互いに交わらないクラスターとの場合: ${\displaystyle C_{i},C_{j},}$${\displaystyle C_{k}}$${\displaystyle n_{i},n_{j},}$${\displaystyle n_{k}}$

${\displaystyle d(C_{i}\cup C_{j},C_{k})={\frac {n_{i}+n_{k}}{n_{i}+n_{j}+n_{k}}}\;d(C_{i},C_{k})+{\frac {n_{j}+n_{k}}{n_{i}+n_{j}+n_{k}}}\;d(C_{j},C_{k})-{\frac {n_{k}}{n_{i}+n_{j}+n_{k}}}\;d(C_{i},C_{j}).}$

したがって、ウォード法はランス・ウィリアムズアルゴリズムとして実装することができ、

${\displaystyle \alpha _{i}={\frac {n_{i}+n_{k}}{n_{i}+n_{j}+n_{k}}},\qquad \alpha _{j} ={\frac {n_{j}+n_{k}}{n_{i}+n_{j}+n_{k}}},\qquad \beta ={\frac {-n_{k}}{n_{i}+n_{j}+n_{k}}}、\qquad \gamma =0.}$

Ward法の人気により、そのバリエーションも生まれました。例えば、Ward _pは、特徴は異なるクラスターで異なる関連性の度合いを持つ可能性があるという直感的な考えに従って、クラスター固有の特徴の重みの使用を導入しました。^[5]

• Everitt, BS、Landau, S.、Leese, M. (2001)、Cluster Analysis、第 4 版、Oxford University Press、 Inc .、ニューヨーク、Arnold、ロンドン。ISBN 0340761199 
• Hartigan, JA (1975)、「クラスタリング アルゴリズム」、ニューヨーク: Wiley。
• Jain, AKおよび Dubes, RC (1988)、「Algorithms for Clustering Data」、ニュージャージー州: Prentice–Hall。
• Kaufman, L. および Rousseeuw, PJ (1990)、「データ内のグループの検索: クラスター分析入門」、ニューヨーク: Wiley。