【統計学の応用】階層的クラスタリング

・階層的手法
樹形図によって表現されるような、集団の系統発生的な構造をさぐることによってクラスターを構成しようとするものです。各個体を $1$ つのクラスターとして、ある基準に従って結合していく凝集型と分類すべき集合を $1$ つのクラスターとしてある基準に従って分裂していく分裂型の $2$ つに大別される。

・非階層的手法
クラスターの妥当性の基準として、クラスター内の変動をできるだけ小さくし、クラスター間の変動をできるだけ大きくしようとし、あらかじめクラスター数が決まっているような手法です。

・個体間の類似度/非類似度
・算法（アルゴリズム）
・評価

$L_1$ 距離（直角距離）

　$D(x,y)=|x_1-y_1|+|x_2-y_2|$

$L_2$ 距離（ユークリッド距離）

　$D(x,y)=\sqrt{(x_1-y_1{)}^2+(x_2-y_2{)}^2}$

$L_{\mathrm{\infty }}$ 距離（チェビシェフ距離）

　$D(x,y)=max\{|x_1-y_1|$,　$|x_2-y_2|\}$

① 最短距離法
② 最長距離法
③ 郡平均法

STEP１　

　$D(G_1$,　$G_2)=1$
　$D(G_1$,　$G_3)=6$
　$D(G_1$,　$G_4)=5$
　$D(G_1$,　$G_5)=3$
　$D(G_2$,　$G_3)=5$
　$D(G_2$,　$G_4)=6$
　$D(G_2$,　$G_5)=4$
　$D(G_3$,　$G_4)=11$
　$D(G_3$,　$G_5)=9$
　$D(G_4$,　$G_5)=2$

となるので、距離が一番小さいのは $D(G_1$,　$G_2)=1$ となり、$G_1$ と $G_2$ が結合し新たに $G_1^{\prime }$ が生成される。

　$G_1^{\prime }=\{x_1$,　$x_2\}$,　$G_2=\{x_3\}$,　$G_3=\{x_4\}$,　$G_4=\{x_5\}$

STEP２

　$D(G_1^{\prime }$,　$G_2)=\frac{11}{2}$
　$D(G_1^{\prime }$,　$G_3)=\frac{11}{2}$
　$D(G_1^{\prime }$,　$G_4)=\frac{7}{2}$
　$D(G_2$,　$G_3)=11$
　$D(G_2$,　$G_4)=9$
　$D(G_3$,　$G_4)=2$

となるので、距離が一番小さいのは $D(G_3$,　$G_4)=2$ となり、$G_3$ と $G_4$ が結合し新たに $G_2^{\prime }$ が生成される。

　$G_1^{\prime }=\{x_1$,　$x_2\}$,　$G_2=\{x_3\}$,　$G_3^{\prime }=\{x_4$,　$x_5\}$

STEP３　

　$D(G_1^{\prime }$,　$G_2)=\frac{11}{2}$
　$D(G_1^{\prime }$,　$G_3^{\prime })=\frac{9}{2}$
　$D(G_2$,　$G_3^{\prime })=10$

となるので、距離が一番小さいのは $D(G_1^{\prime }$,　$G_3^{\prime })=\frac{9}{2}$ となり、$G_1^{\prime }$ と $G_3^{\prime }$ が結合し新たに $G{”}_1$ が生成される。

　$G{”}_1=\{x_1$,　$x_2$,　$x_4$,　$x_5\}$,　$G_2=\{x_3\}$

STEP４

　$D(G{”}_1$,　$G_2)=\frac{31}{4}$

となり $G{”}_1$ と $G_2$ が結合する。