PythonでMean-Shift（平均シフト）アルゴリズムを実装する方法

機械学習にはさまざまな種類のクラスタリングアルゴリズムが存在し、その多くはPythonで実装できます。本記事では、教師なし学習手法として用いられるクラスタリングアルゴリズムの一つである「Mean-Shift（平均シフト）」について、その仕組みとPythonによる実装方法を解説します。

Mean-Shiftアルゴリズムとは

Mean-Shiftアルゴリズムは、データ分布に関する事前の仮定を必要としないノンパラメトリックな手法です。このアルゴリズムでは、各データポイントを反復的に移動させながら、データポイントが最も密集している領域（高密度領域）へとシフトさせることで、クラスタへの割り当てを行います。

このデータポイントの高密度領域は、クラスタの重心（セントロイド）として知られています。Mean-ShiftとK-means法の大きな違いは、K-meansではクラスタ数を事前に指定する必要があるのに対し、Mean-Shiftはデータそのものから自動的に最適なクラスタ数を見つけ出せる点にあります。この柔軟性により、クラスタ数が未知のデータセットでも直感的に分析できるのが特徴です。

Mean-Shiftアルゴリズムの処理手順

• 各データポイントを、それぞれ独立したクラスタに割り当てます。
• これらのクラスタの重心を求めます。
• 重心の位置を反復的に更新します。
• より密度の高い領域へと処理を進めます。
• 重心がそれ以上動ける場所がなくなった時点で、処理を終了します。

それでは、scikit-learnを使用して、Pythonでどのように実装するのかを見ていきましょう。

サンプルコード

import numpy as np
from sklearn.cluster import MeanShift
import matplotlib.pyplot as plt
from matplotlib import style
style.use("ggplot")
from sklearn.datasets import make_blobs

centers = [[3, 3, 1], [4, 5, 5], [11, 10, 10]]
X, _ = make_blobs(n_samples=950, centers=centers, cluster_std=0.89)

plt.title("Implementation of Mean-Shift algorithm")
plt.xlabel("X-axis")
plt.ylabel("Y-axis")
plt.scatter(X[:, 0], X[:, 1])
plt.show()

ms = MeanShift()
ms.fit(X)
labels = ms.labels_
clusterCent = ms.cluster_centers_
print(clusterCent)

numCluster = len(np.unique(labels))
print("Estimated clusters:", numCluster)

colors = 10 * ['r.', 'g.', 'b.', 'c.', 'k.', 'y.', 'm.']
for i in range(len(X)):
    plt.plot(X[i][0], X[i][1], colors[labels[i]], markersize=3)
plt.scatter(clusterCent[:, 0], clusterCent[:, 1],
            marker=".", color='k', s=20, linewidths=5, zorder=10)
plt.show()

※ 古いバージョンのscikit-learnでは sklearn.datasets.samples_generator モジュールから make_blobs をインポートしていましたが、現在は非推奨のため、上記のように sklearn.datasets から直接インポートする方法を採用しています。

実行結果

[[ 3.05250924  3.03734994  1.06159541]
 [ 3.92913017  4.99956874  4.86668482]
 [10.99127523 10.02361122 10.00084718]]
Estimated clusters: 3

実行すると、まず生成されたデータポイントの散布図が表示され、その後、Mean-Shiftによって推定されたクラスタごとに色分けされたプロットと、黒色で示された各クラスタの重心が描画されます。コンソールには検出された重心の座標と、推定されたクラスタ数（この例では3）が出力されます。

コードの解説

• 必要なパッケージをインポートし、扱いやすいようにエイリアスを定義します。
• style クラスの use 関数に「ggplot」を指定し、グラフの見た目を整えます。
• make_blobs 関数を使用して、クラスタ状のテストデータを生成します。
• xlabel、ylabel、title の各関数で、X軸・Y軸のラベルとグラフタイトルを設定します。
• MeanShift クラスのインスタンスを作成し、変数に代入します。
• fit メソッドで、生成したデータをモデルに適合させます。
• labels_ と cluster_centers_ から、各データのラベルおよびクラスタの重心を取得します。
• 一意なラベル数を数えることで、推定されたクラスタ数を算出します。
• データを色分けしてプロットし、重心を黒点で強調表示した散布図を出力します。
• show 関数によって、結果を画面に表示します。

まとめ

Mean-Shiftアルゴリズムは、クラスタ数を事前に指定する必要がなく、データの密度構造に基づいて自動的にグループを発見できる強力な教師なし学習手法です。画像セグメンテーションや物体追跡など、さまざまな分野で応用されており、scikit-learnを使えば数行のコードで簡単に試すことができます。ぜひ実際のデータセットにも適用してみてください。