【python】階層型クラスタリングとデンドログラムの実装について
クラスタリングには、階層型と非階層型があります。今回は、階層型のクラスタリングについて解説しようと思います。
実装で使うデータは、【共線性解決】pythonで主成分分析をやってみたでも使った、学生のテストのデータを使っております。
階層型クラスタリング・ウォード法
階層型のクラスタリングとは、最も類似度が高い(さまざまな測り方あり)組み合わせからまとめていく手法です。
もともとデータ一つ一つがクラスターを構成していると仮定し、類似性のあるデータから結合させていき、ある程度意味のある集団までクラスター数を減らしていこうという考え方です。
結果として出力される樹形図から、分類の過程でできるクラスターがどのように結合されていくのか確認できるというメリットがあります。
また、K-means法とは異なりクラスター数を事前に決めなくて良いが、距離尺度(ユークリッド距離)と併合方法(ウォード法,中心法,群平均)をハイパーパラメータとして設定する必要はあります。
樹形図はデンドログラムと呼ばれ、統計検定準一級の試験範囲にもなっています。
距離尺度
ここでは、距離尺度を3種類ご紹介します。
ユークリッド距離
$$\sum_{i=1}^n(x_{i}-y_{i})^2$$
マンハッタン距離
$$\sum_{i=1}^n|x_{i}-y_{i}|$$
マハラノビス距離
$$\sqrt{(x_{i}-y_{i})^T\sum^{-1}(x_{i}-y_{i})}$$
マハラノビス距離は相関関係を考慮した距離尺度になっており、真ん中の項に分散共分散行列が用いられています。
一番有名なのは、ユークリッド距離です。
ユークリッド距離は後ほど解説する階層型クラスタリング手法「ウォード法」にも登場します。
また正規化されたベクトルではコサイン類似度とほぼ同じ意味合いを持ちます。
【python】コサイン類似度は高校数学の知識で理解できます！
早速実装していきましょう。
CODE：ウォード法
今回は、国語と技術のテストの点数から生徒をクラスタリングしてみようと思います。
階層型のメリットとして、クラスター数を事前に設定する必要はありません。
#各ライブラリの読み込み
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline
import sklearn
#データの読み込み
seiseki = pd.read_csv('seiseki.csv')
seiseki
SeisekiList = []
for i in range(len(seiseki)):
SeisekiList.append([seiseki["kokugo"][i], seiseki["gika"][i]])
SeisekiListライブラリを読み込みます。今回のデータは、以下のようになっています。列としてはgika(技科ですかね？)とkokugoを使います。
| kokugo | shakai | sugaku | rika | ongaku | bijutu | taiiku | gika | eigo | |
| 0 | 30 | 43 | 51 | 63 | 60 | 66 | 37 | 44 | 20 |
| 1 | 39 | 21 | 49 | 56 | 70 | 72 | 56 | 63 | 16 |
| 2 | 29 | 30 | 23 | 57 | 69 | 76 | 33 | 54 | 6 |
| 3 | 95 | 87 | 77 | 100 | 77 | 82 | 78 | 96 | 87 |
| 4 | 70 | 71 | 78 | 67 | 72 | 82 | 46 | 63 | 44 |
| … | … | … | … | … | … | … | … | … | … |
データフレームから目的の要素を抽出して、多重配列に入れます。
多重配列は、多次元配列とも呼ばれるもので、リストの中にリストが入っている構造です。
import numpy as np
X = np.array([[30, 44],[39, 63],[29, 54],[95, 96],[70, 63],[67, 66],[29, 43],[56, 67],[45, 46],[68, 72],[50, 65],[70, 67], [46, 45],[23, 48],[77, 88],[15, 17],[37, 55],[55, 68],[0, 6],[35, 39],[60, 57],[70, 70],[82, 99],[44, 22], [54, 61],[80, 68],[46, 46], [48, 52], [51, 41], [37, 35], [31, 7], [35, 33], [50, 60], [33, 33], [27, 58], [36, 49], [77, 49], [61, 52], [84, 100], [78, 44], [7, 18], [57, 38], [60, 52], [17, 9], [82, 61], [37, 40], [40, 62], [72, 74], [74, 50], [87, 73], [66, 51], [90, 68], [43, 31], [24, 11], [41, 55], [42, 90], [33, 20], [29, 4], [83, 84], [73, 69], [66, 33], [71, 55], [62, 61], [47, 65], [53, 51], [61, 34], [21, 10], [74, 77], [72, 74], [50, 57], [5, 18], [32, 61], [23, 37], [34, 55], [70, 69], [9, 17], [61, 74], [34, 45], [38, 35], [72, 37], [32, 21], [52, 59], [96, 75], [58, 45], [35, 47], [40, 36], [48, 25], [46, 26], [32, 27], [50, 13], [76, 73], [64, 80], [62, 44], [76, 32], [81, 35], [69, 78], [89, 51], [27, 23], [39, 39], [62, 55], [73, 72], [49, 32], [35, 27], [36, 20], [16, 11], [60, 30], [74, 92], [22, 11], [47, 33], [43, 49], [84, 44], [65, 70], [49, 33], [31, 29], [83, 78], [87, 76], [68, 66], [68, 77], [28, 47], [42, 85], [42, 45], [70, 52], [58, 55], [57, 31], [8, 5], [44, 21], [65, 43], [81, 51], [57, 59], [64, 7], [86, 79], [34, 38], [84, 50], [4, 4], [23, 13], [66, 72], [53, 50], [70, 27], [78, 32], [39, 23], [74, 74], [33, 53], [43, 46], [54, 18], [26, 54], [58, 24], [29, 23], [73, 73], [59, 67], [58, 52], [70, 61], [19, 19], [29, 24], [32, 19], [77, 82], [91, 74], [50, 49], [63, 31], [42, 20], [68, 49], [70, 32], [82, 78], [0, 2], [45, 40], [73, 48], [60, 45]])インデックスのリストを指定して値を取得するのは、Python の組み込みのリストでは対応していないで、numpy の ndarray を使います。
#サンプルデータの可視化
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
fig = plt.figure(figsize=(6,6))
ax = fig.add_subplot(1,1,1,title="test")
plt.scatter(X[:,0],X[:,1])
for i, element in enumerate(X):
plt.text(element[0]+0.02,element[1]+0.02,i)
plt.show() 
#階層型クラスタリング
#ウォード法
from scipy.cluster.hierarchy import linkage
Z = linkage(X,method="ward",metric="euclidean")
pd.DataFrame(Z)| 0 | 1 | 2 | 3 | |
| 0 | 47.0 | 68.0 | 0.000000 | 2.0 |
| 1 | 5.0 | 116.0 | 1.000000 | 2.0 |
| 2 | 8.0 | 26.0 | 1.000000 | 2.0 |
| 3 | 21.0 | 74.0 | 1.000000 | 2.0 |
| 4 | 23.0 | 125.0 | 1.000000 | 2.0 |
データフレームの解説 1列目と2列目：結合されたクラスターの番号 3列目：クラスター間の距離 4列目：結合後に新しくできたクラスタの中に入っている元のデータの数
ここでウォード法を使っています。
ウォード法は、クラスタ同士が結合すると仮定した時、結合後の全てのクラスタにおいて、クラスタの重心とクラスタ内の各点の距離の平方和の合計が最小となるように、クラスタを結合させていく方法です。
階層型クラスタリングの一種で、クラスタ間の距離を最小化するようにクラスタを結合します。
具体的には、ウォード法はクラスタ間の距離を、クラスターを結合したときに生じる全体の平方和の増加量\(ΔSS(C, C’)\)と定義します。
これは、クラスタ内のデータポイントがクラスタの中心からどれだけ離れているかを測定することで、クラスタ内のばらつきを最小化することを目指しています。
$$ΔSS(C, C’) = \frac{|C|×|C’|}{|C|+|C’|} × d(C, C’)^2$$
\(|C|\)と\(|C’|\)はそれぞれクラスタ\(C\)と\(C’\)のデータポイントの数を表します。
\(d(C, C’)\)はクラスタCとC’の中心間のユークリッド距離を表します。
この\(ΔSS(C, C’)\)が最小となるクラスタのペアを見つけ、それらを結合することを繰り返します。
このプロセスは、指定されたクラスタ数に達するまで、または全てのデータポイントが1つのクラスタに結合されるまで続けられます。
補論：ウォード法を使うときに、データは正規分布に従うべき？
ウォード法で使う、全体の平方和の増加量にはデータが正規分布に従っていることは仮定されていません。
ただ、ウォード法が特に正規分布に従うデータに対して有効です。
その理由は、クラスタ内の平方和（つまり、クラスタ内の分散）を最小化することを目指しているからです。
正規分布は、その特性上、データの大部分が平均値（つまり、クラスタの中心）の近くに集中しています。
したがって、正規分布に従うデータに対してウォード法を適用すると、自然にクラスタ内の分散が最小化され、より「密集した」クラスタが形成される傾向があります。
クラスタ内の分散を最小化することを目指している以上、データが凸型(Convex)(下図左)になることを前提としており、クラスタの形が非凸型(Non-Convex)(下図右)のデータなどはDBSCANやスペクトラルクラスタリングによる分類を検討することが良いでしょう。
デンドログラム
#デンドログラム
#視覚的にどうクラスターを分けたかわかる。
from scipy.cluster.hierarchy import dendrogram
import matplotlib.pyplot as plt
fig2,ax2 = plt.subplots(figsize=(20,5))
ax2 = dendrogram(Z)
fig2.show()
このように樹形図でクラスター分けの様子が見れます。
赤、緑、黄色の3色であり、3つのクラスターに分けてくれたことがわかります。
また、距離水準を3よりも大きく取るともっと細かくクラスター分けすることも可能であり、クラスター数を柔軟に決定することができます。
from scipy.cluster.hierarchy import fcluster
clusters = fcluster(Z,t=3,criterion="maxclust")
for i,c in enumerate(clusters):
print(i,c)最後に、どの生徒がどのクラスターに分けられたのかを見てみましょう。
0 3 1 3 2 3 3 2 4 2 5 2 6 3 7 3 8 3 9 2 ‥
以上が出力結果です。これが縦に人数分続く形になっています。
さて、ここまで技術と国語のテストの点数を指標にして生徒をクラスターに分けると、3つが「ちょうどいい」というのが教師なし機械学習の提案です。
ただ、一つ問題があります。教師なし学習は指標がないので、「このクラスターにはこういう特徴がある」のような分析結果につなげる示唆が得られにくいということです。
実際の業務では、「なぜそういう分類になったのか」「こうしたクラスターの購買行動は○○だから、こうしたアプローチをとってみよう」のような「分析にとどまらない戦略の提案」が必須になります。
そういった点では、事前に分析者がクラスター数を設定する非階層型のクラスタリングの方が、「便利」なのかもしれませんね。
k-means法との違い
今回取り上げたウォード法は、教師なし学習のクラスタリングの中でも「階層型」と呼ばれる型に分類されます。
階層型の短所として、計算量が多いことが挙げられます。
k-means法については、【非階層型】K-means法でクラスタリングをしてみましょう。をご覧ください。
| merit | demerit | |
| 非階層 | 次元が多い場合にも対応する | 事前にクラスター個数を指定する |
| 階層 | 分類過程を視覚的に見れる | 計算量が多い |
事前にクラスターの数を指定しない階層型ですが、正解データがなく解釈や評価が難しい教師なし学習では大きな問題点と思われるかもしれませんね。
