【クラスタリング】最短距離法を用いた階層的クラスタリング

・階層的手法
樹形図によって表現されるような、集団の系統発生的な構造をさぐることによってクラスターを構成しようとするものです。各個体を \(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_{\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\) が生成される。

　\(G’_1=\{x_1\),　\(x_2\}\),　\(G_2=\{x_3\}\),　\(G_3=\{x_4\}\),　\(G_4=\{x_5\}\)

STEP２

　\(D(G’_1\),　\(G_2)=\frac{11}{2}\)
　\(D(G’_1\),　\(G_3)=\frac{11}{2}\)
　\(D(G’_1\),　\(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\) が生成される。

　\(G’_1=\{x_1\),　\(x_2\}\),　\(G_2=\{x_3\}\),　\(G’_3=\{x_4\),　\(x_5\}\)

STEP３　

　\(D(G’_1\),　\(G_2)=\frac{11}{2}\)
　\(D(G’_1\),　\(G’_3)=\frac{9}{2}\)
　\(D(G_2\),　\(G’_3)=10\)

となるので、距離が一番小さいのは \(D(G’_1\),　\(G’_3)=\frac{9}{2}\) となり、\(G’_1\) と \(G’_3\) が結合し新たに \(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\) が結合する。