K-means クラスタリング
K-means はラベルなしの n 点を k 群へ分けます。各点を最寄りの重心に割り当て、各重心を所属点の平均へ移す二操作を交互に行い、割当てが変わらなくなると止まります。目的の inertia は所属重心までの平方距離の合計です。
旗に人が集まり、旗が集団の平均へ動き、再び近い旗を選ぶ過程です。本課の決定的な規則と厳密な算術では Lloyd 反復は停止します。ただし終点はデータと初期位置の両方に依存し、停止は大域最適性の証明ではありません。
仕組みと停止の根拠
点は学習データであり、ないのはクラスの正解です。重心は空間上の位置なので標本と一致する必要はありません。
- 割当て。 各点が k 重心を比較します。15 点と 3 重心なら距離計算は 45 回です。
- 更新。 非空クラスタの重心を所属点の平均へ移します。中央値や任意の一標本ではありません。
inertia の単位は二乗で、28.80 は距離ではありません。割当てはより遠くない重心を選ぶため目的値を増やしません。非空の固定集合では平均が平方距離和の一意な最小点なので、重心が動けばその部分は厳密に下がります。空クラスタは位置を保ち、「空集合にも唯一の平均がある」とは扱いません。
非増加だけでは同値の循環を除けません。本課は等距離を最小番号に決め、割当てを重心の関数にします。有限個の割当てに対して非空重心は決まった平均、空重心は据置きです。非空重心の実移動は目的を厳密に下げます。この性質と決定的な同点処理により安定割当てへ到達します。浮動小数点誤差や数値的な許容値は実装上の追加事項です。
最近重心の領域は Voronoi セルで、境界は重心間の垂直二等分線の有効部分です。単クラスタの領域は凸のセルになり、環や三日月を一領域にはできません。ユークリッド距離が意味を持ち、尺度が比較可能で、まとまった群に向きます。細長い形、入れ子、単位の違いでは表現と目的の適合を調べます。
ステップごとの例
15 点は左上五点、左下五点、右の縦長五点。k=3、初期重心は中央の (0,2)、(0,0)、(0,−2) です。
- 第 1 割当て。 c₀ は左上五点と
(4,3)、(4,1)の計 7、c₁ は(5,0)と(4,−1)の 2、c₂ は左下五点と(4,−3)の 6。右群が分裂し、inertia は 265.00 です。 - 第 1 更新。
c₀=(−1.57,3.00)、c₁=(4.50,−0.50)、c₂=(−2.50,−3.33)へ移り、151.55 に低下します。ラベルはまだ旧値なので、(4,3)は新 c₁ に近くても c₀ 所属です。次の割当てが必要な理由です。 - 第 2 割当て。
(4,3)、(4,1)、(4,−3)が c₁ に移り、64.60、各 5 点になります。 - 第 2 更新。 重心は
(−3.80,3.40)、(4.20,0.00)、(−3.80,−3.40)、inertia は 28.80。 - 第 3 割当ての確認。 全 15 点が不変で
new==labels、停止します。二回の更新後の固定点なので、同じ操作を追加しても改善しません。
次に同じデータと k で、(−4,−4)、(4,3)、(4,−3) を種に再実行します。三ラウンド後は 133.10。左の二群が十点の一群、右上 (4,3) が単独、右の残り四点が一群になります。どちらも安定ですが目的値は異なります。
左の階段は下降を記録します。更新の拍では旧割当ての地図を残し、重心移動後の不一致を見せます。次の割当てで地図を更新するため、一時的な旧色を最終的な最近重心判定と読まないでください。
収束と最適性
15 点から三種を選ぶ全 455 組中、332 組は 28.80、123 組はそれより悪く、最大 215.53 で止まります。一回の停止判定は変化の有無だけを見て、良い解かは判断しません。
複数初期値から実行して最小 inertia を残せます。K-means++ は既存種への最短平方距離に比例して次の種を選び、悪い初期値の危険を減らします。どちらも大域最適を保証しません。分割が初期値を変えても安定するかも調べます。ライブラリの既定値は版と設定に依存し、n_init="auto" が複数再実行とは限りません。
k は inertia だけで選べません。分野の目的、シルエット係数などを組み合わせます。大域最適値は k とともに増えませんが、別々の局所実行では順序が逆になる場合もあります。本例の k=4 最良は 15.33、k=3 は 28.80、k=n はゼロにもなります。目的だけを最小化すれば単独点へ分ける方へ偏ります。
計算量
| 項目 | 費用 |
|---|---|
| 一ラウンド | O(nkd) |
| ラベルと重心 | O(n)+O(kd)、入力を除く |
| 全反復 | O(nkdi)、i はラウンド数 |
| 新点の予測 | O(kd) |
初期例は二更新と三回目の停止確認です。最悪のラウンド数は指数的になり、平面にもその構成があります。全体最良分割の一般問題は NP-hard ですが、小さな例では厳密解法も使えます。
この反復が学習で、重心は学習パラメータです。画面は 12 ラウンドで打ち切り、その場合は報告します。理論上の停止はこの上限に依存せず、用意した設定は到達しません。
境界ケース
- 空クラスタ。 平均がないため本課は重心を据え置きます。k=4 の 1365 組の種では 75 組が空クラスタを残します。他実装は再配置する場合があり、規則を確認します。
- 等距離。 最小番号を選びます。決定性は停止の議論に関わります。
- 最初から固定点。 三群の平均から始めると最初の更新は不変です。コードの初期ラベルは未知なので、その後の割当て確認で停止を検出します。
- 異なる位置が k 未満。 重なる重心は番号で票を奪い、空になるものが出ます。入力は重複初期位置を拒否します。
- 同心環。 全 153 組の二点初期値が両環を切ります。二つの Voronoi セルで内環と外環を各一群にはできず、初期値だけの問題ではありません。
よくある間違い
- inertia だけで k を選ぶ。群を増やす方向へ偏るため用途の基準が必要です。
- 一回の収束を信頼する。悪い固定点も止まるので初期値と結果を比べます。
- 平均を中央値へ変えて同じ目的だとする。平均は平方距離、座標ごとの中央値は L1 距離の k-medians、幾何中央値はユークリッド距離和に対応します。目的と証明を一緒に変えます。
- 同じ群サイズを期待する。均衡項はなく、10、4、1 も有効です。
- 単位と尺度を無視する。大きな数の列が支配し得るため、標準化や重みを用途に合わせて決めます。
簡略化の範囲
Lloyd の割当て、平均更新、停止、空クラスタ保護を示します。K-means++、複数開始、Elkan、mini-batch、特徴前処理は省略しています。二次元十五点では高次元の距離集中も目立ちません。機構、初期値依存、形の制約を学び、利用時は実装設定と検証結果も確認します。