ミニプロジェクト:k-means を自分で作る
前のレッスンの k-means を、ライブラリを使わずに NumPy だけで作ります。データは、標準化したワインのデータ(178本、13個の成分)です。
作るもの
def kmeans(X, init_centers, n_iter=20):
centers = init_centers.copy() # はじめの中心(k 行 × 特徴量の数)
for _ in range(n_iter):
dist = ... # 1. 各点と各中心との距離(点の数 × k の表)
labels = ... # 2. 割り当て: 各点の、一番近い中心の番号
centers = ... # 3. 中心の更新: クラスタごとの平均の位置
...
1の距離の表は、次の1行で作れます(演習では書いてあります)。
dist = np.sqrt(((X[:, None, :] - centers[None, :, :]) ** 2).sum(axis=2))
X[:, None, :] は「点の数 × 1 × 特徴量の数」、centers[None, :, :] は「1 × k × 特徴量の数」の形です。引き算すると、NumPy が足りない方向を自動で広げて(ブロードキャスト)、「点の数 × k × 特徴量の数」の、すべての点とすべての中心の差になります。それを2乗して特徴量の方向(axis=2)に足し、平方根をとると、「点の数 × k」の距離の表になります。
実験の結果
はじめの中心を「データの最初の3本」にして、自分で作った k-means を動かしました。クラスタ内の誤差の2乗和は、繰り返すたびに次のように小さくなりました。
| 繰り返し | 1回目 | 2回目 | 3回目 | 4回目 | 5回目 | 8回目 |
|---|---|---|---|---|---|---|
| 誤差の2乗和 | 1945.2 | 1578.4 | 1364.2 | 1287.7 | 1282.1 | 1279.7 |
scikit-learn の KMeans に、同じはじめの中心を渡して(init=、n_init=1)比べると、178本すべてのクラスタの割り当てが一致し、中心も一致しました(差は ほどで、計算機の誤差の範囲)。
はじめの中心で、結果が変わる
| はじめの中心 | 最後の誤差の2乗和 |
|---|---|
| データの最初の3本(どれも品種0) | 1279.7 |
| 品種ごとに1本ずつ(0番・60番・130番) | 1282.5 |
| scikit-learn の既定(k-means++ で10回やり直し、一番よい結果) | 1277.9 |
同じデータ・同じ手順でも、はじめの中心によって、止まる場所(最後の分け方)が少し違いました。k-means は、「今より誤差が小さくなる方向」にしか動かないので、はじめの位置の近くの、一番よいとは限らない分け方で止まることがあります。下り坂だけを進んで山を下りると、近くの小さなくぼみで止まってしまい、もっと低い谷にたどり着けないのと同じです(このような場所を 局所最適解 と呼びます。ニューラルネットワークの勾配降下法でも起こりうる問題です)。scikit-learn が、はじめの中心を変えて何回もやり直すのは、このためです。