SciPyのlinkageメソッドによる凝集型クラスタリング

はじめに

凝集型クラスタリング (agglomerative clustering) は、個々のデータ点をクラスタとして開始し、似ているクラスタ同士を1つずつ結合していくクラスタリング手法です。終了条件（残ったクラスタ数など）を満たすまでクラスタの結合を繰り返します。似ているクラスタを判定する尺度には、結合度 (linkage) を用います。結合度には以下のようなものがあります。

ward: 結合したときにクラスタ内の分散 (variance) の増加が最小となるように2つのクラスタを選択。
average: クラスタに含まれる点の平均距離が最小となるように2つのクラスタを選択。
complete (maximum): 2つのクラスタの点間の距離の最大値が最小となるように2つのクラスタを選択。
single: 2つのクラスタの点間の距離の最小値が最小となるように2つのクラスタを選択。

これらの中ではwardがよく用いられます。

この記事ではPythonとSciPyによるサンプルコードも示します。実行環境は以下の通りです。

Python: 3.9.7
NumPy: 1.20.3
SciPy: 1.7.1

SciPyの凝集型クラスタリング

linkageメソッド

SciPyではscipy.cluster.hierarchy.linkageというメソッドに凝集型クラスタリングが実装されています（scikit-learnにも実装されていますが可視化機能がないため、SciPyを使用します）。

1
2


scipy.cluster.hierarchy.linkage(y, method='single',
    metric='euclidean', optimal_ordering=False)

主なパラメータの意味は以下の通りです。

y (2D array): クラスタリングするデータ
method (str): = 結合度のアルゴリズムを指定。'single'（デフォルト）, 'complete', 'average', 'centroid', 'median', 'ward', 'weighted'を選択できる。
metric (str): 距離の計算方法。'euclidean'（デフォルト）, 'mahalanobis', 'cosine'などを選択できる。
optimal_ordering (bool): Trueにすると、葉の距離同士が最小になるように結果がソートされます。可視化時に有用な場合がありますが、計算が遅くなります（デフォルトはFalse）。

また、クラスタの階層を可視化するにはscipy.cluster.hierarchy.dendrogramというメソッドを用います。

使用例

linkageメソッドの使用例を示します。簡単のため、1次元のデータを用います。

1
2
3
4
5
6


import numpy as np
from scipy.cluster.hierarchy import linkage, dendrogram

X = np.array([[0],[1],[5],[7],[20],[25]])
Z = linkage(X, 'ward', optimal_ordering=True)
dn = dendrogram(Z)

実行すると以下のグラフが出力されます。横軸の数字はデータのインデックスです。また、グラフの高さは結合するノード同士の距離を表しています。例えば、オレンジの部分は4, 5番目のデータ（20と25）の距離が5であることを示します。

agglomerative result

参考

scipy.cluster.hierarchy.linkage — SciPy Manual