ウォード法とは

/機械学習

ウォード法

ウォード法とは、クラスタ分析の手法の1つで、クラスタ内の平方和を最も小さくする基準でクラスタを形成していく方法です。

尚、クラスタ分析とは、対象(サンプル)間の距離を定義し、距離の近さによって対象を分類する分析方法の総称です。

クラスタ内の平方和 $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=\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}=\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}=\frac{n_xn_y}{n_x+n_y}\sum_{j=1}^p(\bar{x}_j-\bar{y}_j)^2  -⑤$$

平方和の差分($\Delta S_{XY}$)がクラスタ間の距離に相当し、クラスタ同士を結合する際の判断基準となります。

平方和の差分の計算

以下で、平方和の差分⑤が成り立つことを確認します。①に②③④を代入して、②と④の第1項まとめたものを(1)、③と④の第2項まとめたものを(2)と置きます。

$$\Delta S_{XY}=S_{XY}-S_X-S_Y\equiv\sum_{j=1}^p\Big((1)+(2)\Big)$$

このとき(1)と(2)は以下になります。

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

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

これに $\bar{z}_j$ を代入すると、

$$\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$$

これより⑤が成り立っていることが分かります。

 

応用数学
情報理論、暗号理論、機械学習、金融工学、ゲーム理論
散策路TOP
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

 

タイトルとURLをコピーしました