はじめに
k-meansは教師なし学習に該当し、与えられたデータを任意の数のグループに分ける手法です。
本記事ではk-meansのアルゴリズムについて解説します。
k-meansとは？
k-meansは与えられたデータをk個のグループに分けるクラスタリングの手法です。k-meansではデータの類似度に基づいてグループ分けを行います。類似度はクラスタの中心(後述)とデータの距離が近ければ類似度が高いと判定します。具体的なアルゴリズムは次の章で説明します。
k-meansのアルゴリズム
k-meansのアルゴリズムの手順は下記の通り:
- 初期化: クラスタの中心となるk個の点(セントロイド)をデータセットの中からランダムに選ぶ
- クラスタへの割り当て: 各データは最も近いセントロイドのクラスタに割り当てられる。近さはユークリッド距離(2点間の直線距離)で判定される
- セントロイドの更新: 各クラスタ内でデータの平均位置にセントロイドを移動させる。
- 反復: 2, 3を繰り返してクラスタの割り当てが変わらなくなるか、ユーザーが定義した収束条件(繰り返し回数など)を満たせば、終了
図で描くと以下のようになります
まずは、下図のようなデータがあるとします。〇はデータ点です。
-
初期化: セントロイドとなる点をランダムに選びます(星印がセントロイド)。今回はk=2としています。
-
クラスタへの割り当て: データ点はセントロイドに近いクラスタに割り当てられます。
-
セントロイドの更新: クラスタ内のデータ点から平均位置を算出し、新しいセントロイドとします。例えば、緑に属している4点を$(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)$とした場合、緑のクラスタの新しいセントロイドは$(\frac{\sum_{n=1}^4x_n}{4}, \frac{\sum_{n=1}^4y_n}{4})$となります。(平均値を算出しています)
- クラスタの割り当て: 新しいセントロイドでデータ点をクラスタに割り当てます
ライブラリを用いずk-meansを実装
scikit-learnなどのライブラリを使わずにk-meansを実装したいと思います。
import numpy as np
import random
from matplotlib import pyplot as plt
# データ作成
np.random.seed(0)
points1 = np.random.normal(5, 4, (50, 2))
points2 = np.random.normal(20, 4, (50, 2))
points = np.r_[points1, points2]
np.random.shuffle(points)
for point in points:
plt.scatter(point[0], point[1], marker="o", color="blue")
plt.show()
データはこんな感じ
def calc_euclidean_distance(centroids, data):
norms = []
for centroid in centroids:
norms.append([np.linalg.norm(centroid - data_point) for data_point in data])
return np.array(norms).T
def k_means(n_cluster, data, iter=1000):
# 初期化
init_centroid_indices = [random.randint(0, data.shape[0]) for i in range(n_cluster)]
centroids = np.array(data[init_centroid_indices])
for _ in range(iter):
# セントロイドとデータ点との距離を計算
distances = calc_euclidean_distance(centroids, data)
# セントロイドとの距離が最小となるクラスターに割り当て
clusters = np.argmin(distances, axis=1)
# クラスタごとに平均を算出
for i_cluster in range(n_cluster):
# 該当のクラスタに割り当てられたデータを抽出
data_indices = [i for i, x in enumerate(clusters) if x == i_cluster]
data_in_cluster = [data[i] for i in data_indices]
# 平均値を算出し、セントロイドを更新
centroids[i_cluster] = np.array(data_in_cluster).mean(axis=0)
return clusters
clusters = k_means(2, points)
for cluster, point in zip(clusters,points):
if cluster == 0:
plt.scatter(point[0], point[1], marker="o", color="blue")
else:
plt.scatter(point[0], point[1], marker="o", color="red")
plt.show()
クラスタリング結果はこんな感じで2つのクラスタに分かれました。(初期値によってはうまく2つにわかれないこともある)
k-meansの問題点
k-meansは初期化のステップでランダムにセントロイドを選択しているため、下記の問題点があります。
- 初期値によって最適なクラスタリングが行われない可能性がある
- 初期値によって結果の収束までに時間がかかる可能性がある
終わりに
k-meansの問題点を解決するために、k-means++という手法が開発されています。
k-means++の概要については次回以降の記事で解説したいと思います。
補足
k-meansの記事をいくつか見ましたが、初期化の手順として各データ点をランダムにクラスタに割り当てる方法を散見しました。
scikit-learnの実装を見ると、初期化ではセントロイドはデータ点からランダムに選択しているようなので、本記事ではこちらの手順を初期化として採用しました。
参考