クラスタリングのアルゴリズムは多く存在します。分野や扱うデータの種類によってアルゴリズムは変わってきますが、この記事ではクラスタリングの中でも階層的クラスタリングの最短距離法というアルゴリズムを紹介していきます。
★この記事を書いた人★
名前: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
結合
距離最小の組み合わせを結合し新しいクラスターを作る。
最短距離法の数値例
個体をそれぞれ
\(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つのクラスターに分類される。
得たい情報によって評価方法は異なります。
おわりに
さいごまで読んでいただきありがとうございました!
このブログでは、統計スキルを身につけたいけど数学があまり得意ではないという方向けに、
高校数学から統計学の実践まで様々な記事を収録しています!
統計スキル習得のスタート地点
第一部 データの性質に関する基礎知識
観測は簡単ではない/誤差とばらつき/データに含まれるバイアス/交絡因子と因果関係/データサンプリングの方法論
第二部 データの分析に関する基礎知識
データの扱い/一変数データの振る舞い/変数の間の関係を調べる/多変量データの解釈する/数理モデリングの要点
第三部 データの解釈・活用に関する基礎知識
データ分析の罠/データ解釈の罠/データ活用の罠
数学っぽい説明はあまり多くなく、普段仕事とかで目にするデータの見方を変えてくれる良書です。
ぜひ読んでみてください!
分析者のためのデータ解釈学入門 データの本質をとらえる技術
2,860円
データを分析して背後にあるメカニズムを解釈したり,データに基づいた意思決定や問題解決を行う際に,分析者が知っておかなければならない知識をわかりやすく網羅的に解説した教科書です。
質問や感想はコメントへ!