ウォード法
ウォード法とは、クラスタ分析の手法の１つで、クラスタを統合する際に、統合後のクラスタ内の平方和を最も小さくする基準でクラスタを形成していく方法です。
尚、クラスタ分析とは、対象（サンプル）間の距離を定義し、距離の近さによって対象を分類する分析方法の総称です。
クラスタ内の平方和 $S$ は、サンプル数を $n$（$i=1\sim n$）、変数の数を $p$（$j=1\sim p$）とすると以下で定義されます。尚、$\bar{x}_j$ は変数 $j$ についてのサンプル間の平均値です。
$$S\equiv\sum_{i=1}^n\sum_{j=1}^p(x_{ij}-\bar{x}_j)^2$$$$\bar{x}_j=\frac{1}{n}\sum_{i=1}^nx_{ij}$$
クラスタの結合
クラスタ $X$ とクラスタ $Y$ を結合した場合の平方和の合計 $S_{XY}$ は以下より計算されます。各クラスタのサンプル数はそれぞれ $n_x,n_y$ としています。
$$S_{XY}=S_X+S_Y+\Delta S_{XY} －①$$
結合前のクラスタの平方和 $S_X$ 、$S_Y$ は以下で得られ、
$$S_X=\sum_{i=1}^{n_x}\sum_{j=1}^p(x_{ij}-\bar{x}_j)^2 －②$$$$\bar{x}_j=\frac{1}{n_x}\sum_{i=1}^{n_x}x_{ij}$$$$S_Y=\sum_{i=1}^{n_y}\sum_{j=1}^p(y_{ij}-\bar{y}_j)^2 －③$$$$\bar{y}_j=\frac{1}{n_y}\sum_{i=1}^{n_y}y_{ij}$$
結合後のクラスタの平方和 $S_{XY}$ は以下になります。尚、$\bar{z}_j$ は変数 $j$ についての全サンプルの平均値です。
$$S_{XY}=\sum_{j=1}^p\Big(\sum_{i=1}^{n_x}(x_{ij}-\bar{z}_j)^2+\sum_{i=1}^{n_y}(y_{ij}-\bar{z}_j)^2\Big) －④$$$$\bar{z}_j=\frac{1}{n_x+n_y}\Big(\sum_{i=1}^{n_x}x_{ij}+\sum_{i=1}^{n_y}y_{ij}\Big)=\frac{n_x\bar{x}_j+n_y\bar{y}_j}{n_x+n_y}$$
$\Delta S_{XY}$ はクラスタを結合した場合に増加する平方和で、この平方和の差分が結合前のクラスタ間の距離に相当します。これはクラスタ同士を結合する際の判断基準となり、増加する平方和が少ない結合が選択されます。
$$\Delta S_{XY}=\frac{n_xn_y}{n_x+n_y}\sum_{j=1}^p(\bar{x}_j-\bar{y}_j)^2 －⑤$$
⑤を導く
平方和の差分⑤が成り立つことを確認します。①に②③④を代入して、②と④の第１項まとめたものを (1) 、③と④の第２項まとめたものを (2) と置きます。
$$\Delta S_{XY}=S_{XY}-S_X-S_Y\equiv\sum_{j=1}^p\Big((1)+(2)\Big)$$
このとき (1) は以下になります。
$$(1)\equiv\sum_{i=1}^{n_x}\Big((x_{ij}-\bar{z}_j)^2-(x_{ij}-\bar{x}_j)^2\Big)$$$$=\sum_{i=1}^{n_x}(\bar{x}_j-\bar{z}_j)(2x_{ij}-\bar{x}_j-\bar{z}_j)=n_x(\bar{x}_j-\bar{z}_j)^2$$$$=n_x\Big(\frac{n_y(\bar{x}_j-\bar{y}_j)}{n_x+n_y}\Big)^2$$
ここで、最後は $\bar{z}_j$ を代入しています。次に (2) も同様に計算すると、
$$(2)\equiv\sum_{i=1}^{n_y}\Big((y_{ij}-\bar{z}_j)^2-(y_{ij}-\bar{y}_j)^2\Big)$$$$=\sum_{i=1}^{n_y}(\bar{y}_j-\bar{z}_j)(2y_{ij}-\bar{y}_j-\bar{z}_j)=n_y(\bar{y}_j-\bar{z}_j)^2$$$$=n_y\Big(\frac{n_x(\bar{y}_j-\bar{x}_j)}{n_x+n_y}\Big)^2$$
以上より (1) と (2) の和をとると、
$$\sum_{j=1}^p\Big((1)+(2)\Big)=\frac{n_xn_y}{n_x+n_y}\sum_{j=1}^p(\bar{x}_j-\bar{y}_j)^2$$
これより⑤が成り立っていることが分かります。
変数が２個の例
５つのサンプル $A\sim E$ の２つの変数によるクラスタ分けの例をとります。簡単のため、変数の値は５段階とします。
| サンプル | $A$ | $B$ | $C$ | $D$ | $E$ |
| 変数１ | １ | ５ | ５ | ５ | ４ |
| 変数２ | ５ | ４ | １ | ５ | ２ |
⑤より２つのサンプル間のウォード法での距離 $\Delta S_{XY}$ を計算します。この時点では各１個であるため、$n_x=n_y=1$ となります。例えば、間のウォード法での距離は、
$$\Delta S_{A-B}=\frac{1\cdot1}{1+1}\Big((1-5)^2+(5-4)^2\Big)=8.5$$
これにより、全てのサンプル間で計算すると、
| － | $A$ | $B$ | $C$ | $D$ |
| $B$ | 8.5 | － | － | － |
| $C$ | 16.0 | 4.5 | － | － |
| $D$ | 8.0 | 0.5 | 8.0 | － |
| $E$ | 9.0 | 2.5 | 1.0 | 5.0 |
これを見ると、$BD$ 間（0.5）と $CE$ 間（1.0）がウォード法での距離が近いことが分かります。これらをクラスタにまとめると、
| サンプル | $A$ | $BD$ | $CE$ |
| 変数１ | １ | ５ | 4.５ |
| 変数２ | ５ | ４.5 | １.5 |
これを基にしてウォード法での距離を計算すると、
$$\Delta S_{A-BD}=\frac{1\cdot2}{1+2}\Big((1-5)^2+(5-4.5)^2\Big)=10.8$$$$\Delta S_{A-CE}=\frac{1\cdot2}{1+2}\Big((1-4.5)^2+(5-1.5)^2\Big)=16.3$$$$\Delta S_{BD-CE}=\frac{2\cdot2}{2+2}\Big((1-5)^2+(5-4.5)^2\Big)=9.25$$
これらをまとめると以下のようになります。
| － | $A$ | $BD$ |
| $BD$ | 10.8 | － |
| $CE$ | 16.3 | 9.25 |
もしクラスタ数を２つにするのであれば、$BD$ と $CE$ を統合して、$A$ と $BCDE$ に分けることができます。
