はじめに

階層的クラスタリング（Hierarchical clustering）という手法を知った。
詳しい使い方や解説は、以下を参照してほしい。

具体的な使用法はscipyを使用した場合は以下のようになる。

from scipy.cluster.hierarchy import linkage, fcluster

X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]]

Z = linkage(X, method='average', metric='euclidean')
clusters = fcluster(Z, t=0.15, criterion='distance')

問題

しかし、入力の数（Xのサイズ）が大きくなってくると、非常に時間がかかるようになる。
3000次元のベクトルを10000個なんて入れた日には目も当てられない。

階層的クラスタリングの場合、計算量は$O(n^2\log n)$や$O(n^2)$¹となるらしい。
各要素間の距離情報が必要であり、要素の組み合わせの数だけ計算が必要になるため、非常に計算コストがかかることになる。

解決方法

処理に時間がかかっているのは距離行列を求めるところであるため、計算アルゴリズムの速い関数を使って、事前に距離行列を求めておきlinkageに入力する。

import numpy as np
from sklearn.metrics import pairwise_distances_chunked
from scipy.cluster.hierarchy import linkage, fcluster

gen = pairwise_distances_chunked(X, metric='euclidean')
s_tmp = np.concatenate(list(gen), axis=0)
S = s_tmp[np.triu_indices(s_tmp.shape[0], k=1)]
Z = linkage(S, method='average')
clusters = fcluster(Z, t=0.15, criterion='distance')

全然計算速度が違う。感動もの！
この方法はここで見つけた（metricをmethodと書き間違えていたり、カッコ（]）を書き忘れたりしてるので注意）。

解説

linkage関数は、入力したデータに対し、距離行列を求めてクラスタリングを行っているが、距離行列を入力することもできる。
linkageの処理は以下の様に書き直すことが出来る。

Z = linkage(X, method='average', metric='euclidean')

↓

from scipy.spatial.distance import pdist
from scipy.cluster.hierarchy import linkage

S = pdist(X, metric='euclidean')
Z = linkage(S, method='average')

pdist関数は、距離行列を計算する関数である。
このpdistがあまり早くないようで、これをpairwise_distances関数に変更する。
↓

import numpy as np
from sklearn.metrics import pairwise_distances
from scipy.cluster.hierarchy import linkage

gen = pairwise_distances(X, metric='euclidean')
S = gen[np.triu_indices(gen.shape[0], k=1)]
Z = linkage(S, method='average')

pairwise_distances関数が早いのは、おそらく並列処理をしていると思われる。
np.triu_indices関数を使って配列を操作しているのは凝集距離行列にするためである。
pairwise_distances関数は、各要素間の距離を要素数×要素数の行列で出力する。これは対称行列であり、階層的クラスタリングでは、対角要素と片方は不要となる。
必要な距離のみを再配置した行列を凝集距離行列（a condensed distance matrix）と呼ぶらしい。
np.triu_indices関数は上三角のインデックスを取得する関数であり、距離行列の必要な距離情報を抽出するのに使われている。

ただ大規模なデータの場合、pairwise_distances関数がエラーを返すことがあるらしい。その問題を回避するために、チャンクごとに距離行列を計算するpairwise_distances_chunked関数を用いると良いとのこと。（ただし、これは古い情報かもしれない）
↓

import numpy as np
from sklearn.metrics import pairwise_distances_chunked
from scipy.cluster.hierarchy import linkage, fcluster

gen = pairwise_distances_chunked(X, metric='euclidean')
s_tmp = np.concatenate(list(gen), axis=0)
S = s_tmp[np.triu_indices(s_tmp.shape[0], k=1)]
Z = linkage(S, method='average')

おわりに

扱うデータの大きさも増えてきて、「数の暴力」に圧倒される日々が続きますが、先人が切り開いたイケてるアルゴリズムとマシンパワーで乗り切りたいと思います。

クラスタリング (クラスター分析) ↩