クラスタリングアルゴリズム５選〜Python

クラスタリングアルゴリズムは、教師なし学習アルゴリズムです。教師あり学習アルゴリズムと違って、クラスタリングアルゴリズムは事前にデータにラベルを付ける必要がなく、そのままデータをクラスタリングできます。

グループ分けがクラスタリングの目的ですが、クラスタリングアルゴリズムは、データセットからパターンを発見するために使用されます。グループ分けによって、データの特性をよりよく理解し、データに隠されているパターンと知識を掘り起こすのに役立ちます。例えば、ユーザーの年齢、性別、好みの商品の購入、購入頻度などに応じて、ユーザーをグループ化して、どのような顧客がどのような製品を購入する傾向があるかを分析できます。また、クラスタリングは、通常のデータを異常値から分離するなどの問題にも使用できます。

今回はscikit-learn機械学習ライブラリを使用して、一般的に使われている5つのクラスタリングアルゴリズムを実際に見てみましょう。

今回使用するデータ

この記事では、wine データセットを使用します。データ件数は 178 件。特徴量は13個。（wineデータに実際にラベルが既についていますが、実案件においてラベルがないのがほとんどです。手作業か、クラスタリング、分類などのアルゴリズムによってラベルが割り当てられます。まずはデータのラベルを無視して後ほど確認しましょう。）

次のPythonコードでデータを読み込みます。

from sklearn.datasets import load_wine

X = load_wine()
print(X[:5])

[[1.423e+01 1.710e+00 2.430e+00 1.560e+01 1.270e+02 2.800e+00 3.060e+00
  2.800e-01 2.290e+00 5.640e+00 1.040e+00 3.920e+00 1.065e+03]
 [1.320e+01 1.780e+00 2.140e+00 1.120e+01 1.000e+02 2.650e+00 2.760e+00
  2.600e-01 1.280e+00 4.380e+00 1.050e+00 3.400e+00 1.050e+03]
 [1.316e+01 2.360e+00 2.670e+00 1.860e+01 1.010e+02 2.800e+00 3.240e+00
  3.000e-01 2.810e+00 5.680e+00 1.030e+00 3.170e+00 1.185e+03]
 [1.437e+01 1.950e+00 2.500e+00 1.680e+01 1.130e+02 3.850e+00 3.490e+00
  2.400e-01 2.180e+00 7.800e+00 8.600e-01 3.450e+00 1.480e+03]
 [1.324e+01 2.590e+00 2.870e+00 2.100e+01 1.180e+02 2.800e+00 2.690e+00
  3.900e-01 1.820e+00 4.320e+00 1.040e+00 2.930e+00 7.350e+02]]

データは 13 列、つまり13 個の特性量があることがわかります。

データのスケーリング:
多くのクラスタリングアルゴリズムは、データをグループ化するために類似性または距離を使用して、密集した観測領域を検出します。スケーリングされたデータは、クラスタリングが容易になります。クラスタリングアルゴリズムを使用する前にデータをスケーリングすることをお勧めします。
上記のwineデータについて、最後の特徴量の数値が他の特徴量よりスケールがかなり大きく、e+03となっているので、データのスケーリングが考えられますが、この記事ではデータスケーリングを行わず、クラスタリングアルゴリズムのみに注目します。

クラスタリングアルゴリズム

scikit-learn ライブラリには、さまざまなクラスタリングアルゴリズムが用意されています。ここでは、よく使用される 5 つだけについて話します。

K-Means
DBSCAN
Mean Shift
Gaussian Mixture Model
Agglomerative Clustering（Hierarchical clustering）

私は、各アルゴリズムの理論と実装を深く説明しませんので、理論に興味がある方は、以下のリンクを参照ください。

クラスタリング結果を視覚化するには、13 個の特徴量（13次元）を 2次元の座標平面に表示する必要があります。ここでは次元圧縮するためにt-sne アルゴリズムを使用します。次元圧縮もしくは主成分分析アルゴリズムについては、他の記事で詳しく説明します。次元圧縮の他に、単純に13 個の特徴量から、問題を説明できる 2 つの代表を選択して可視化すれば良いです。データを可視化するとき、同じクラスタのデータに同じ色を与えます。これにより、クラスタリングアルゴリズムの効果を直接目で確認できます。

一部のクラスタリングアルゴリズムでは、検出すべきクラスタ数を指定する必要があります。ここではクラスタ数が 3 であると仮定して各アルゴリズムの説明に進みます。後ほどクラスタ数の決め方について説明します。

from matplotlib import pyplot
from numpy import where
from sklearn.manifold import TSNE

# tsne is only used to decrease dimension for visualization
tsne = TSNE(n_components=2, init='pca', random_state=0)
x = tsne.fit_transform(X)

def plot_clusters(X, cluster_ids):
    for class_value in range(3):
        row_ix = where(cluster_ids == class_value)
        pyplot.scatter(X[row_ix, 0], X[row_ix, 1])
    pyplot.show()

K-Means

K-Meansは、おそらく最も有名なクラスタリングアルゴリズムです。 K-Means は、それぞれのクラスタ間の分散（距離として考えると理解しやすい）を最小限に抑えることで、どのデータをどのクラスタに配置するかを決定します。

メインパラメータ：

n_cluster：クラスタ数

n_clusterの決め方については、記事の付録をご参照ください。より早いアルゴリズムを求める場合は、アルゴリズムの収束が早いMini-Batch K-Meansがおすすめです。

K-Meansを使用して wineデータをクラスタリングするソースコード及びクラスタリング結果は次のとおりです：

from sklearn.cluster import KMeans
kmeans_model = KMeans(n_clusters=3)
kmeans_model.fit(X)
yhat = kmeans_model.predict(X)
plot_clusters(x, yhat)

K-Meansアルゴリズムは、wine データを 3 つのクラスタに明確に分割しましたね。

DBSCAN

DBSCAN（Density-Based Spatial Clustering of Applications with Noise的略称）は密度に基づくアルゴリズムです。DBSCANは高密度領域を探索し、特徴空間で高密度領域を拡張することでそれぞれのクラスタを決定します。

メインパラメータ：

eps：パラメータεの値を適切に取ることが非常に重要です。 εはクラスタの重心とデータの距離を指定します。εが小さすぎると、ほとんどのデータがノイズとしてマークされ、εが大きすぎると、全データが同じクラスタに配属される可能性があります。

DBSCANを使用して wineデータをクラスタリングするソースコード及びクラスタリング結果は次のとおりです：

from sklearn.cluster import DBSCAN
model = DBSCAN(eps=20)
yhat = model.fit_predict(X)
plot_clusters(x, yhat)

eps=10の時では、ほとんどのデータがノイズとしてマークされ、可視化できませんでした。対して、eps を大きくして40に設定した場合はほとんどのデータが同じクラスタに配属されてしまいましたね。wineデータにおいては、DBSCANの結果はあまりよくありませんでした。

Mean Shift

Mean Shiftクラスタリングは、重心に基づくアルゴリズムです。データの密度を使用して重心を探索し、調整します。 Mean Shiftアルゴリズムを使用する場合は、クラスタ数を考慮する必要はありません。

メインパラメータ：なし

Mean Shiftを使用して wineデータをクラスタリングするソースコード及びクラスタリング結果は次のとおりです：

from sklearn.cluster import MeanShift
model = MeanShift()
yhat = model.fit_predict(X)
plot_clusters(x, yhat)

Mean Shiftはwineデータを三つのクラスに分けましたが、オレンジ色のクラスタは少し微妙でしたね。

Gaussian Mixture Model

Gaussian混合モデル(GMM)は、複数のガウス分布関数の線形組み合わせです。Gaussian混合モデル (GMM) は、通常、データセットに複数の分布が含まれている場合に、K-Meansよりも有利です。したがって、データに異なる分布が含まれていることが事前に分かっている場合は、Gaussian混合モデル(GMM) でクラスタリングを行うのが良いでしょう。また、他のアルゴリズムと違って、Gaussian混合モデル(GMM) は、各データが各クラスタに属する確率を計算しますので、データがクラスタへの依存度を分析したい時に役たちます。

メインパラメータ：

n_cluster：Cluster的个数

高斯混合模型（GMM）を使用して wineデータをクラスタリングするソースコード及びクラスタリング結果は次のとおりです：

from sklearn.mixture import GaussianMixture
model = GaussianMixture(n_components=3)
model.fit(X)
yhat = model.predict(X)
plot_clusters(x, yhat)

wine データには、複数の分布が存在していないようです。 Gaussian混合モデル(GMM)のクラスタリング結果はよくありませんでした。

Agglomerative Clustering

Agglomerative Clusteringは階層クラスタリングアルゴリズムです。Agglomerative Clusteringは、最初に全データを 1 つのクラスタとして考え始め、クラスタをどんどんマージすることでアルゴリズムの収束に達します。クラスタの階層は、ツリーマップ (dendrogram) で表すことができます。Agglomerative ClusteringはK-Meansのようなアルゴリズムとは異なり、クラスタ数を指定せずに行うことができます。このアルゴリズムはパラメータの影響を受けつらいです。ただし、階層クラスタリングは、データに階層関係が含まれていることを事前にわかる場合、もうしくはデータの階層を明確することが目的の場合に使用されるので、一般的な手法ではありません。

メインパラメータ：

n_cluster：Cluster的个数

Agglomerative Clusteringを使用して wineデータをクラスタリングするソースコード及びクラスタリング結果は次のとおりです：

from sklearn.cluster import AgglomerativeClustering
model = AgglomerativeClustering(n_clusters=3)
yhat = model.fit_predict(X)
plot_clusters(x, yhat)

Agglomerative Clusteringのクラスタリング結果は、K-meansの結果とよく似ています。wineデータには、ある程度の階層関係が存在する可能性があると考えられますね。

汎用的なアルゴリズムは存在しません。必ずデータによって異なるクラスタリングアルゴリズムを使用する必要があります。より多くのクラスタリングアルゴリズムについては、scikit-learnの公式サイトをご参照ください。

補足１：クラスタ数（n_clusterパラメタ）の決め方について

K-Means等のアルゴリズムを使用する前に、クラスタ数を決定する必要があることを先ほど説明しました。クラスタ数の決定は通常経験に基づいて行いますが、データに詳しくない場合状態でクラスタ数を決定するのは困難です。通常、クラスタリング結果をn_clusterパラメータにフィードバックし、継続的なtry and errorのプロセスです。勿論、統計的な方法も存在し使うことができます。一番簡単な手法は、Elbow関数を使用することです。Elbow 関数の横軸はn_clusterで、縦軸は歪み（distortions）です。 distortions は、各データポイントから割り当てられた重心までの距離の平方和を計算します。実装を見てみましょう。

import numpy as np
from sklearn.cluster import KMeans
from scipy.spatial.distance import cdist

distortions = []
K = range(1,10)
for k in K:
    kmeanModel = KMeans(n_clusters=k).fit(X)
    kmeanModel.fit(X)
    distortions.append(sum(np.min(cdist(X, kmeanModel.cluster_centers_, 'euclidean'), axis=1)) / X.shape[0])

# Plot the elbow
pyplot.plot(K, distortions, 'bx-')
pyplot.xlabel('n_cluster')
pyplot.ylabel('Distortion')
pyplot.title('The Elbow Method showing the optimal k')
pyplot.show()

n_cluster=3の特に関数が大きく回っていたことが分かりますね。この大きく回っていたところが真のクラスタ数を示しています。wine データのクラスタ数はは 3であることが分かります。

また、wineデータ自体にラベルがあるので、見て見ましょう。

from sklearn.datasets import load_wine

X, y = load_wine(return_X_y=True)
print(y)

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2]

wineの178件のデータに、0/1/2 の3 つのラベルがありますね。したがって、実際のクラスタ数を3と考えるのが妥当でしょう。Elbow関数を使用して計算されたクラスタ数と一致するので、Elbow関数の結果は正しいことが分かります。

補足２：クラスタリング結果の評価方法について

クラスタリング結果の評価方法について、多くの科学的な手法がありますが、学術的な比較であり、実際のケースでは、評価効果は理想的ではありません。クラスタリングの評価は主観的であり、データの領域の専門家が必要です。ドメインエキスパートのドメイン知識、見解はクラスタリング結果の評価に非常に役立ちます。クラスタリングの学術的評価方法は、scikit-learnの公式サイトをご参照ください。

また、実際のケースでは、ドメインエキスパートの力を借りてもクラスタリングの結果を解釈できない非常に厄介なデータに遭遇することがよくありますが、この時、通常次の2 つの状況があります：

データには大量なノイズデータがあり、もしくはデータの分布は非常に歪んでいる。この場合は厄介ですが、処理方法も多いです。例えば、外れ値の削除、より多くのデータまたは特徴量を追加する等が考えられます。
使用されるアルゴリズムが正しくない。いくつかのアルゴリズムを同時に試して比較した方が良いでしょう。クラスタリングアルゴリズムは多数ありますが、汎用的なアルゴリズムはありません。一般的に、初期段階ではK-Meansを最初に試し、結果によって他のアルゴリズムを試します。クラスタ数を先に決定するのが難しい場合はMean-Shiftを使うのが良いでしょう。