投稿者: Yutaro

再び階層的クラスタリングの記事の続きです。
参考:scipyで階層的クラスタリング

この記事中では、元のデータの点と点の距離はユークリッド距離を採用しました。
metric='euclidean'と指定しているところがそれです。

# ユークリッド距離とウォード法を使用してクラスタリング
z = linkage(X, metric='euclidean', method='ward')

しかし実際は、これ以外にも多くの距離関数が利用できます。
ドキュメントを読むと、 pdistのページを読めと書いてあるのでそちらをみてみましょう。
scipy.cluster.hierarchy.linkage

metric : str, optional
The distance metric to use. See the distance.pdist function for a list of valid distance metrics.

ちなみに method のほうで指定できる値とその意味は、ちゃんとlinkageのページに載っています。
’single’/’complete’/’average’/’weighted’/’centroid’/’median’/’ward’

scipy.spatial.distance.pdist

metric : str or function, optional
The distance metric to use. The distance function can be ‘braycurtis’, ‘canberra’, ‘chebyshev’, ‘cityblock’, ‘correlation’, ‘cosine’, ‘dice’, ‘euclidean’, ‘hamming’, ‘jaccard’, ‘jensenshannon’, ‘kulsinski’, ‘mahalanobis’, ‘matching’, ‘minkowski’, ‘rogerstanimoto’, ‘russellrao’, ‘seuclidean’, ‘sokalmichener’, ‘sokalsneath’, ‘sqeuclidean’, ‘yule’.

この他、自分で定義した関数も使えるようです。

Y = pdist(X, f)
Computes the distance between all pairs of vectors in X using the user supplied 2-arity function f. For example, Euclidean distance between the vectors could be computed as follows:

dm = pdist(X, lambda u, v: np.sqrt(((u-v)**2).sum()))

それぞれの距離関数はこちらのページから辿っていくと確認しやすいです。
Distance computations (scipy.spatial.distance)

前回の記事の続きです。
参考:scipyで階層的クラスタリング

前回の記事で階層的クラスタリングを実行し可視化するところまで紹介しましたが、
今回は一歩戻ってlinkage関数の戻り値の中身を見てみます。
とりあえず、 linkage matrix をprintして結果を見てみましょう。

from sklearn.datasets import load_iris
from scipy.cluster.hierarchy import linkage
X = load_iris().data[::10, 2:4]
print(X.shape)  # (15, 2)
# ユークリッド距離とウォード法を使用してクラスタリング
z = linkage(X, metric='euclidean', method='ward')
print(z.shape)  # (14, 4)
print(z)
# 以下出力
[[ 2.          3.          0.1         2.        ]
 [ 0.          1.          0.1         2.        ]
 [12.         14.          0.14142136  2.        ]
 [ 4.         16.          0.2081666   3.        ]
 [ 6.          8.          0.31622777  2.        ]
 [ 5.          9.          0.36055513  2.        ]
 [ 7.         11.          0.36055513  2.        ]
 [15.         18.          0.39072582  5.        ]
 [10.         17.          0.43969687  3.        ]
 [13.         23.          0.73598007  4.        ]
 [20.         21.          1.0198039   4.        ]
 [19.         25.          2.00831604  6.        ]
 [24.         26.          3.72312593 10.        ]
 [22.         27.          9.80221064 15.        ]]

前回の記事で可視化したのと同じデータなので、以降の説明は前回の記事中の図と見比べながら読むとわかりやすいと思います。
結果のlinkage matrixは、z.shape の値から分かる通り、14行4列の行列の形をしています。
で、この14という値は、元のデータの個数15個から1減らした値です。
階層的クラスタリングのプロセスの中で、1個ずつグルーピングして集約し、もともと15個あったグループを1つにまとめるのでこうなってます。

そして、列ですが、pythonのインデックスいうと 0列目と1列目はあたらに同じグループに含まれるデータのインデックス、
2列目はそれらの要素orクラスタ間の距離、３列めはそこで新たに作られたクラスタに含まれれるデータの個数を意味します。

具体的には、次のデータは、X[2]とX[3]の距離が0.1で、この二つをまとめて要素が２個のクラスタを作ったことを意味します。
[ 2. 3. 0.1 2. ]
そして、明示はされていませんが、その新しいクラスタには、インデックス15が振られます。(元のデータが0~14の15個なので。)

同様に、次のデータで0と1がまとめられてインデックス16のクラスタが作られます。
[ 0. 1. 0.1 2. ]
で、このインデックス16のクラスタは次のデータで4番目の要素とグルーピングされて、要素数3個のクラスタになります。
[ 4. 16. 0.2081666 3. ]
前回の記事のデンドログラムで確かに0と1でできたクラスタに4が合流しているのが描かれていますね。

このようにして、 linkage matrix の中身を直接読むことができます。

今回紹介するのは階層型クラスタリングをscipyで実施する方法です。

階層型クラスタリングの各種アルゴリズム自体は、まだエンジニアを本職にしてたころに知り、その時はこれは面白い手法だと感心していたのですが、
いざデータサイエンティストに転職してからはあまり使ってきませんでした。
クラスタリングする時はk-meansなど、クラスタ数を指定する手法を使うことが多いし、
どれとどれが近いとか言った分析は距離行列眺めたり、次元削減してプロットしたりすることが多かったので。
ただ、他の職種のメンバーに説明するときの樹形図(デンドログラム)のわかりやすさを活用したくなり最近使い始めています

さて、本題に戻ります。

階層型クラスタリングを雑に説明すると、一旦個々のデータを全部別々のクラスタに分類し、
その中から近いものを順番に一つのクラスタにまとめるという操作を繰り返し、最終的に全データを1個のクラスタにまとめる方法です。
この操作を途中で打ち切ることで、任意の個数のクラスタにここのデータを分類することができます。
この際、個々の要素の距離をどう定義するのか、またクラスタと要素、クラスタとクラスタの距離をどのように定義するかによって、
手法が複数存在し、結果も変わります。

この階層型クラスタリングを行う関数が、scipyに用意されています。
Hierarchical clustering (scipy.cluster.hierarchy)

非常に多くの関数がありますが使うのは次の3つです。

scipy.cluster.hierarchy.linkage ・・・ 主役。これが階層型クラスタリングの実装。
scipy.cluster.hierarchy.fcluster ・・・ 各要素について、クラスタリングの結果どのクラスタに属するのかを取得する。
scipy.cluster.hierarchy.dendrogram ・・・ 樹形図(デンドログラム)を描く。

ここまで読んであまりイメージがつかめないと思うので、とりあえずやってみましょう。
データは何でもいいのですが、いつものirisでやります。
(そんなに多くの件数も必要ないので、1/10の件数のデータに絞って使い、4つある特徴量のうち2個だけ使います)

# データ取得。 (15件だけ取得し、特徴量も petal lengthとpetal width に絞る
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
X = load_iris().data[::10, 2:4]

# データを可視化。
fig = plt.figure(figsize=(6, 6))
ax = fig.add_subplot(1, 1, 1, title="iris (sample)")
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
from scipy.cluster.hierarchy import dendrogram

# ユークリッド距離とウォード法を使用してクラスタリング
z = linkage(X, metric='euclidean', method='ward')

# 結果を可視化
fig = plt.figure(figsize=(12, 6))
ax = fig.add_subplot(1, 1, 1, title="樹形図")
dendrogram(z)
plt.show()

結果がこちら。

0,1,2,3,4 が早い段階で一つのクラスタにまとまっていたり、 12と14、6と8が早々にまとまっていたりと納得性のある形になっています。

あとは、もっと扱いやすい形で、何番のデータが何番目のクラスタに所属するのかのリストを作りましょう。
ここで fcluster 関数を使います。
詳しくはドキュメントにありますが、 criterion に ‘maxclust’を指定して、最大クラスタ数で決めたり、
criterion に’distance’ を指定して、距離で閾値を指定したりできます。

ドキュメントを読むよりやってみたほうがわかりやすいと思うのでそれぞれやってみます。
(この辺の話は専用に別記事を用意して取り上げるかも。)

from scipy.cluster.hierarchy import fcluster

# クラスタ数を指定してクラスタリング
clusters = fcluster(z, t=3, criterion='maxclust')
for i, c in enumerate(clusters):
    print(i, c)

# 以下出力
0 1
1 1
2 1
3 1
4 1
5 3
6 3
7 3
8 3
9 3
10 2
11 3
12 2
13 2
14 2

0,1,2,3,4 と 5,6,7,8,9,11 と 10,12,13,14 の3グループにきちんと別れました。

この他、樹形樹に横線を引いてその位置で分けることもできます。
距離=3くらいで分ければ同じ３グループに分かれるのですが、せっかくなので別のところで切りましょう。
距離=1.7を閾値にして、4グループに分かれるのを確認します。

# 距離の閾値を決めてクラスタリング
clusters1 = fcluster(z, 1.7, criterion='distance')
for i, c in enumerate(clusters1):
    print(i, c)

# 以下出力
0 1
1 1
2 1
3 1
4 1
5 4
6 3
7 4
8 3
9 4
10 2
11 4
12 2
13 2
14 2

クラスタ1や、クラスタ2は先ほどと同じですが、6,8 と 5,7,9,11 が別のクラスタに別れました。
これらが分かれる理由は上の樹形図を見ていただければ理解できると思います。