クラスタリングとは
クラスタリングとは、ある集合を非類似度に従って、部分集合(クラスター)に分けることです。
「非類似度」とは、どれくらい似ているか(似ていないか)ということです!
非類似度の定義の仕方は様々です。
数学的な説明は後述しますが、例えば、以下のような図形の集合があったとしましょう。
「形」を基準にすると、
「色」を基準にすると、
このように、分けるための基準を非類似度、あるいは類似度や単に距離と呼ぶこともあります。
クラスタリングは大きく \(2\) つに分けられます。
・階層的手法
樹形図によって表現されるような、集団の系統発生的な構造をさぐることによってクラスターを構成しようとするものです。各個体を \(1\) つのクラスターとして、ある基準に従って結合していく凝集型と分類すべき集合を \(1\) つのクラスターとしてある基準に従って分裂していく分裂型の \(2\) つに大別される。
・非階層的手法
クラスターの妥当性の基準として、クラスター内の変動をできるだけ小さくし、クラスター間の変動をできるだけ大きくしようとし、あらかじめクラスター数が決まっているような手法です。
クラスタリングを考える上で重要な \(3\) つの事柄
・個体間の類似度/非類似度
・算法(アルゴリズム)
・評価
個体間の類似度
扱うデータによって、類似度(距離)の定義は様々ですが、一般的には以下の \(3\) つが挙げられます。
ある個体を、\(x=(x_1\), \(x_2)\) と \(y=(y_1\), \(y_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|\}\)
\(l_2\) 距離(ユークリッド距離)は中学で学ぶ一番馴染み深い距離かなと思います。
このように、扱うデータによって様々な距離が存在しています!
算法(アルゴリズム)
アルゴリズムも距離と同様に扱うデータによって様々あります。階層的手法を扱う際の一般的なアルゴリズムは以下の \(3\) つです。
① 最短距離法
② 最長距離法
③ 郡平均法
以下、最短距離法の手順を説明します。
個体 \(1\) つ を含むクラスターとして考える。
各クラスター間(固体間)の距離を算出し、一番距離が小さい組み合わせを見つける。
距離最小の組み合わせを結合し新しいクラスターを作る。
STEP2, STEP3 を必要な回数繰り返す。
最短距離法の数値例
個体をそれぞれ
\(x_1=8\), \(x_2=7\), \(x_3=2\), \(x_4=13\), \(x_5=11\)
とする。まず個々の個体をクラスターとするので
\(G_1=\{x_1\}\), \(G_2=\{x_2\}\), \(G_3=\{x_3\}\), \(G_4=\{x_4\}\), \(G_5=\{x_5\}\)
としたとき、各クラスター間の \(L_1\) 距離を算出する。
STEP1
\(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\}\)
ここで、複数の個体を持つ \(G_1\) と他の個体との距離の計算方法として郡平均法を用いる。
\(G’_1\) の個体数を \(n’\), 結合前の \(G_1\) の個体数を \(n_1\), \(G_2\) の個体数を \(n_2\) とするとき、
\(D(G’_1, G_2)=\displaystyle\frac{n_1}{n’}D(G’_1, G_1)+\frac{n_2}{n’}D(G’_1, G_2)\)
のように計算する。
STEP2
\(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\}\)
STEP3
\(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\}\)
STEP4
\(D(G”_1\), \(G_2)=\frac{31}{4}\)
となり \(G”_1\) と \(G_2\) が結合する。
以上の計算をもとに樹形図を作成します。
STEP1での樹形図はこちら
STEP2での樹形図はこちら
STEP3での樹形図はこちら
下図のように、例えば高さ3のところで切ってあげると、
\(G_1=\{1\), \(2\}\), \(G_2=\{4\), \(5\}\), \(G_3=\{3\}\)
のように3つのクラスターに分類される。
おわりに
さいごまで読んでいただきありがとうございました!
【最新】こちらの記事がおすすめ!