機械学習：クラスタ分析　k-means法

教師無しのクラスタ分析とは、データの隠れた構造を見つけ出し、グループ内の類似性は高く、グループ間の類似性は低くなるような分割方法を探し出すことである。
　実装が簡単で、他のアルゴリズムと比べ計算効率の高いk-means法を扱う。
　
　k-means法は、各データがプロトタイプによって表現されるプロトタイプクラスタリングに属していて、このプロトタイプには、centroid、medoidの二つのタイプがある。
　centroidは特徴量が連続の場合に類似する点の中心を示し、medoidは特徴量がカテゴリ量である場合の最も代表的な点、すなわち特定のクラスタに属している点の中から、そのクラスタ外の全ての点から最も距離測度が大きい点となる。よって、全ての特徴量は標準化、またはスケール化しておく必要がある。

　k-means法は高次元データも扱えるが、一方でクラスタ数をあらかじめ決定しなければいけない欠点がある、この個数を決めるのに、エルボー法、またはシルエット法が使われる。

　また、最初のcentroidの位置を完全にランダムに選ぶと、収束が遅くなり計算効率が悪くなる場合がある。これを避けるために、centroidの初期値として、互いに離れた位置をとるようにおく初期条件をおく。

k-means++初期化の手順

1. 入力データからcentorid $${\mu^{(0)}}$$の初期値をランダムに選び、これを$${\bf{M}}$$とする。

2. $${\bf{M}}$$に属していない点$${\bf{x}^{(i)}}$$毎の、$${\bf{M}}$$の全centoridからの最小距離を、その点と$${\bf{M}}$$の距離、$${d\left( \bf{x}^{(i)}, \bf{M} \right)}$$とする。

3. 次のcentorid $${\mu^{(1)}}$$を、手順２で求めた距離を使い、重み、$${\displaystyle{ \frac{d\left( \bf{x}^{(i)}, \bf{M} \right)^2}{\Sigma_{i}d\left( \bf{x}^{(i)}, \bf{M} \right)^2} }}$$をつけて選ぶ。

4. $${\bf{M}}$$内のcentoridがあらかじめ指定されたクラスタ数になるまで手順2､３を続ける

この手順３によって、$${\bf{M}}$$内のcentoridと近い点ほど選ばれる確率は低くなり、最終的なcentroidは互いに遠く離れて配置される。この初期化はscikit-learnのkMeansにおいて、init='k-means++'で実装される。

k-means法　手順

1. クラスタ中心の初期値をk個選ぶ

2. 各点をそれに最も近いcentroid$${\mu^{(j)}, j\in \{1,\dots K\}}$$に割り当てる。

3. centroidに割り当てられたデータ点の中心にcentroidを移動する

4. データ点のクラスタ割り当てに変化がなくなるか、centroidの移動がなくなるまで、手順2､３を繰り返す。

データ点となるオブジェクト、$${\bf{x,y}}$$の類似点はユークリッド距離測度が使われることが多い。
$${d(\bf(x,y)^2=\sigma^{m}_{j=1}(x_j-y_j)^2=\|\bf{x}-\bf{y}\|^2}$$
$${m}$$は${\bf{x}}$$の特徴量の数で、$${x_j}$$はそのj番目の特徴量である。
　このユークリッド距離速度を使うと、k-means法はクラスタ内誤差平方和(SSE)を最小にする最適化問題となる。
$${SSE=\Sigma^{m}_{i}\Sigma^{k}_{j}\omega^{(i,j)}\|\bf{x}^{i}-{\bf \mu^{j}}\|^2}$$
$${\omega^{(i,j)} = \begin{cases} 1 & (x^{i} \in j) \\ 0 & (x^{i} \notin j) \end{cases}}$$

$${\omega^{(i,j)}}$$は、$${x^{i}}$$がクラスタ$${j}$$に入っているか、いないかの指標であるが、一つのクラスタにしか属せないハードクラスタリングでは$${0,1}$$をとるが、ソフトクラスタリングでは、各クラスタに属する確率（重み）に使われ、クラスタ$${j}$$に入っている確率が50%、$${j\pm 1}$$が其々25%とすると、
$${\omega^{(i,j)} = \begin{cases} 0.5 & (x^{i} \in j) \\ 0.25 & (x^{i} \in j\pm 1 \\ 0 & (x^{i} \notin j, j\pm 1) \end{cases}}$$
となる。
　ただし、scikit-learnのKMeansには、ソフトクラスタリングは実装されていない。
　
　scikit-learnのKMeansを使い、k-meansのクラスタリングを実行するにあたり、2次元のデータセット sklearn.datasetsのmake_blobsをサンプルデータセットに使う。

from sklearn.datasets import make_blobs

X, y = make_blobs(n_samples=150, n_features=2, centers=3, cluster_std=0.5, 
                  shuffle=True, random_state=0)

Xをプロットしてみると、

import matplotlib.pyplot as plt

plt.scatter(X[:, 0], X[:, 1], c='white', marker='o', edgecolor='black',
            s=50)
plt.grid()
plt.tight_layout()
plt.show()

blobs

であり、$${\bf{y}}$$は、centers=3で設定された三つのクラスタの属しているインデックスが入っている。
　このデータセットのクラスタリングをkMeansで行う。

from sklearn.cluster import KMeans

km = KMeans(n_clusters=3, init='k-means++', n_init=10, max_iter=300,
            tol=1e-04,random_state=0)

y_km = km.fit_predict(X)

$${\bf{y_{km}}}$$にKMeansによるクラスタリングの結果の番号が入っている。このベクトルの中身は$${\bf{y}}$$と一致する必要はない。クラスタリングのインデックスが違っていても、分割結果が同じであれば問題はない。
　$${\bf{X}}$$を$${\bf{y_{km}}}$$の値別に色を変えて、クラスタの中心点と共にプロットしてみる。

plt.scatter(X[y_km == 0, 0],X[y_km == 0, 1],s=50, c='lightgreen',
            marker='s', edgecolor='black',label='Cluster 1')
plt.scatter(X[y_km == 1, 0],X[y_km == 1, 1],s=50, c='orange',
            marker='o', edgecolor='black',label='Cluster 2')
plt.scatter(X[y_km == 2, 0],X[y_km == 2, 1],s=50, c='lightblue',
            marker='v', edgecolor='black',label='Cluster 3')

plt.scatter(km.cluster_centers_[:, 0],km.cluster_centers_[:, 1],
            s=250, marker='*',c='red', edgecolor='black',
            label='Centroids')
plt.legend(scatterpoints=1)
plt.grid()
plt.tight_layout()
plt.show()

k-means clustering