k-means法

データのクラスタリングに用いられる手法である。
分類問題における「教師なし学習」に属する。

アルゴリズムは比較的単純で、次の手順となる。

特徴空間上にｋ個のランダムな代表点（セントロイド）をプロットする。クラスタ数のｋはハイパーパラメータであり、あらかじめ指定する。
各データとセントロイドの距離を求め、各データを最も近いセントロイドのグループに分類する。
上記２のグループでの重心（平均）を求め、新たなセントロイドとする。
上記２、３を繰り返す。
セントロイドが更新されなくなれば終了し、分類を確定する。

f:id:cochineal19:20210524003450p:plain

数式としては、以下の関数を最小化する問題である。
「各クラスタ $C_{k}$ に属するデータ $x_{i}$ とセントロイド $\overline{x_{k}}$ との距離（ユーグリッド距離）の総和」（クラスタ内誤差平方和）を最小化できるセントロイドを求める。

クラスタ内誤差平方和（Sum of Squared errors of prediction、SSE）

$\quad J=\sum ^{K}_{k=1}\sum _{i\in C_{k}}\left\| x_{i}-\overline{x_{k}}\right\| ^{2}$

$\qquad K:\verb|クラスタ数|,\ C_{k}:\verb|k番目のクラスタ|$

$\qquad x_{i}:\verb|i番目のデータ|,\ \overline{x_{k}}:\verb|k番目のクラスタのセントロイド|$

k-means++法

k-means法では、初期値のセントロイドをランダムな位置にプロットするため、複数のセントロイドが近くに位置する可能性があり、分類がうまくいかないことがある。

この問題の改良としてk-means++法があり、セントロイド同士が離れた位置にプロットされやすくなるアルゴリズムである。

エルボー法によるクラスタ数の推定

k-means法でのクラスタ数はハイパーパラメータであり、あらかじめ指定する必要がある。このクラスタ数の推定方法として「エルボー法」がある。

エルボー法は、クラスタ数ごとのクラスタ内誤差平方和（SSE）を横に並べ、プロットがゆるやかになる位置を最適なクラスタ数とする方法である。

f:id:cochineal19:20210524021551p:plain:w450

Pythonコード

sklearn の cluster の KMeans で実装できる。
パラメタ説明はコメントアウトに記載する。

#--  k-means法
km1 = KMeans(n_clusters=4      # クラスター数指定。
             ,init="k-means++" # 'k-means++' or 'random'(k-means) 。default:'k-means++'
             ,n_init=10        # k-meansの実行回数
             ,random_state=0   # 乱数シード
             )
Y_km = km.fit_predict(X)  # 各データのクラスタ番号を求める
 
#-- SSE値を出力
print("Distortion: %.2f" % km.inertia_)

Irisデータでエルボー法のプロットを作ってみる。
クラスタ数（n_clusters=i）を１～10までループして、各クラスタ数のSSE（km.inertia_ で取得可）をプロットする。

from sklearn import datasets, cluster
import numpy as np
import matplotlib.pyplot as plt
 
#-- データ取得
X = datasets.load_iris()
 
#-- エルボー法（クラスタ数10まで）
SSE = []
for i in range(1, 11):
    km = cluster.KMeans(n_clusters = i
                ,init="k-means++"
                ,n_init=10
                ,random_state=1)
    km.fit(X.data)
    SSE.append(km.inertia_)
 
# グラフのプロット
plt.plot(range(1, 11), SSE, marker="o")
plt.xticks(np.arange(1, 11, 1))
plt.xlabel("クラスタ数")
plt.ylabel("クラスタ内誤差平方和（SSE）")
plt.show()