k-means 法の可視化

使い方

• データの形・クラスタの数 k・初期化の方法を選んで「再生」を押すと、中心が動いてクラスタが決まっていく様子をアニメーションで見られます。
• 「1 手」は、割り当て（各点の色を一番近い中心の色にする）と更新（中心をクラスタの平均へ動かす）のどちらか 1 つです。1 手ずつ進めたり戻したりして確かめられます。
• 「別の初期値で試す」を押すと、同じデータ・同じ k で最初の中心だけを選び直します。結果は下の試行の記録に並び、初期値によって結果が変わる様子を比べられます。
• 散布図をクリックすると点を足せます。「点をすべて消す」のあとにクリックしていけば、自分で描いたデータを分けることもできます。初期化を「手動」にしたときは、クリックで最初の中心を置きます。
• 「領域を塗る」は、平面を一番近い中心ごとに塗り分けます（ボロノイ図）。「中心の跡」は、中心がこれまでに動いた道すじです。
• キーボードでは Space で再生 / 一時停止、← → で 1 手戻る / 進む、Home で最初へ、End で最後へ移動します。

k-means のしくみ

1. 最初の中心を k 個決めます（初期化）。
2. 各点を、一番近い中心のクラスタに入れます（割り当て）。
3. 各クラスタの中心を、そのクラスタの点の平均の位置に動かします（更新）。点が 1 つもないクラスタの中心は動かしません。
4. 割り当てで所属の変わる点がなくなるまで 2 と 3 を繰り返します（このアプリでは最大 100 回）。

割り当ても更新も SSE（各点と中心の距離の 2 乗の合計）を減らす操作なので、k-means は必ず有限回で止まります。ただし止まった先が一番よい分け方（大域解）とは限らず、最初の中心の置き方によっては、まとまりを 2 つに割ったり 2 つのまとまりを 1 つにしたりしたまま止まります（局所解）。実際には初期値を変えて何回か試し、SSE の一番小さい結果を使います。

初期化の方法

ランダムな点（Forgy 法）

データの中から k 個の点を選び、そのまま最初の中心にします。近い点を選ぶと、1 つのまとまりを 2 つに割ったまま収束しやすくなります。

k-means++

1 個目はランダムに選び、2 個目からは「すでに選んだ中心からの距離の 2 乗」に比例する確率で点を選びます。中心が散らばるので、悪い結果になりにくい方法です。

ランダム分割

すべての点をランダムなクラスタに割り振り、その平均を最初の中心にします。中心はどれもデータ全体の真ん中付近に集まります。

手動

散布図をクリックして、k 個の中心を自分で置きます。わざと悪い位置に置いて、局所解に落ちる様子を確かめられます。

データの形と k-means の相性

まとまり

同じくらいの大きさの丸いまとまり（3〜5 個）。k-means が得意な形です。

大きさ違い

広がりも点の数も違う 3 つのまとまり。境界が大きいまとまりの内側に食い込みます。

細長い

同じ向きに引き伸ばした 3 つのまとまり。k-means は丸いまとまりを前提にするので、横に切ってしまうことがあります。

三日月

かみ合った 2 つの三日月。まとまりが凸でないため、k-means では分けられません。

同心円

内側の円と外側の輪。中心からの距離で分かれているので、k-means では分けられません。

一様

まとまりのない一様な点。それでも k-means は k 個に区切ります。

k-means はどのクラスタも同じくらいの広がりの丸い形だと仮定しているので、三日月や同心円のような形は、k をいくつにしても見た目どおりには分けられません。こうしたデータには、密度で分ける DBSCAN や、点のつながりで分けるスペクトラルクラスタリングなどを使います。