メニュー
yu-to
管理者
本ブログを運営しているyu-toと申します。

高校数学の解説や公務員試験問題の解説、データサイエンスについての記事を書いていきます!

「データサイエンス×教育」に興味があり、日々勉学に励んでいます。

少しでも役に立つ情報の発信をしていきますのでぜひ読んでください。

また、同志からのお声がけはとても励みになります。ぜひ、コメントやメール、SNS等でご連絡ください!
カテゴリー
統計学初学者サポートこちらをクリック

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

目次

データアナリストへの道

少し数字に強い理系大学卒から駆け出しデータアナリストになるまでに、実際に読んだ50冊以上の本から厳選して、基本的な理論から実践的スキルまでを身につけられるようにデータ分析初学者向けにまとめました。>>記事を読む

クラスタリングとは

クラスタリングとは、ある集合を非類似度に従って、部分集合(クラスター)に分けることです。

「非類似度」とは、どれくらい似ているか(似ていないか)ということです!

非類似度の定義の仕方は様々です。

数学的な説明は後述しますが、例えば、以下のような図形の集合があったとしましょう。

「形」を基準にすると、

「色」を基準にすると、

このように、分けるための基準を非類似度、あるいは類似度や単に距離と呼ぶこともあります。

クラスタリングは大きく \(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\) つです。

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

以下、最短距離法の手順を説明します。

STEP
個々の個体をクラスターとする

個体 \(1\) つ を含むクラスターとして考える。

STEP
距離最小の組み合わせ

各クラスター間(固体間)の距離を算出し、一番距離が小さい組み合わせを見つける。

STEP
結合

距離最小の組み合わせを結合し新しいクラスターを作る。

STEP
繰り返し

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つのクラスターに分類される。

得たい情報によって評価方法は異なります。

おわりに

さいごまで読んでいただきありがとうございました!

このブログは統計学を学びたい学生/社会人向けに記事を書いています。

【最新】こちらの記事がおすすめ!

>>

 

  • URLをコピーしました!
目次