メニュー
スマイルゼミ
カテゴリー
yu-to
オンライン家庭教師/ブログ運営
本ブログを運営しているyu-toと申します。

数学は非常に難しい科目です。
学校の授業や塾の授業だけだと足りないという方も多くいるのではないでしょうか?そんな方に向けて、なるべく途中式を飛ばさずに丁寧に解説をしたブログとなっています。

高校数学/公務員試験頻出問題の解説や学習に役立つTipsだったり、モチベを上げてくれるような記事も書いていきますので、ぜひ読んでくださいね!

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

  • URLをコピーしました!

クラスタリングのアルゴリズムは多く存在します。分野や扱うデータの種類によってアルゴリズムは変わってきますが、この記事ではクラスタリングの中でも階層的クラスタリングの最短距離法というアルゴリズムを紹介していきます。

★この記事を書いた人★

名前:yu-to
出身:青森県
生年月日:1993年4月2日

大学/大学院
統計手法のクラスター分析を研究
〈経歴〉
塾講師 5年
高校教員 2年
家庭教師 9年
実績
早稲田大学、横浜国立大学、明治大学、立教大学、東洋大学、神奈川大学 etc.

現在は教員をしながら本サイト(Math kit)を運営しています。

目次

クラスタリングとは

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

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

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

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

「形」を基準にすると、

「色」を基準にすると、

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

クラスタリングには大きく \(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をコピーしました!
  • URLをコピーしました!

コメントはお気軽に♪

コメントする

目次