← 生方 誠希のページ K-MEANS を学ぶ 01 → 02 → 03

点を動かして学ぶ、k-meansの入口

データを1つの点で代表するなら、
どこに置く？

1個の代表点から、2個でデータを分担する考え方へ。点を動かしながら、k-meansの基本をたどります。

STEP 01 · 1個の代表点を置く

どこに置くと、全体に近づける？

灰色の点1つが、データ1個です。全体を1つの位置で表すために置く青い点を、代表点と呼びます。この青い点を動かして、置き場所を考えます。

各データまでの距離をそれぞれ2乗して足した値が、2乗誤差（距離の2乗和）です。この値が小さくなる場所を探しましょう。

  1. 動かす青い点を、データから遠い場所と中央付近に置いてみよう。
  2. 比べる2乗誤差の値とグラフを見て、小さくなる場所を探そう。
  3. 確かめる探せたら「重心へ移動」で、平均の位置と比べよう。

青い代表点を動かそう

40 個のデータ
データ 代表点 p
2次元データと1つの代表点 横軸と縦軸はともに0から10。同じ長さが同じ距離を表します。代表点から全データへの線を描きます。代表点にフォーカスして矢印キーでも操作できます。

グラフの横軸：位置を記録した順番 →

青い点をドラッグして動かします。図をクリック・タップするか、位置のスライダーでも動かせます。

各データを同じ重みで扱います。横と縦は同じ目盛りです。数値は小数点以下2桁に丸めて表示しています。

動かして分かったこと

1個の代表点なら、重心で2乗誤差が最小になる。

「重心へ移動」で最小値を確かめたら、そこから少し動かしてみましょう。どの方向に動かしても、2乗誤差は増えます。

代表点は、置き場所を試している点。重心は、データの平均から決まる位置。代表点を重心に重ねたとき、全体とのずれを最も小さくできます。

ただし、データがばらついていれば、全部の線を同時に長さ0にはできません。だから、最小になっても誤差は0にはなりません。

もう少し詳しく：距離の2乗和を式で読む

1本の線から、全部の線へ

デモで見た2乗誤差は、次の2つの計算を順番に行ったものです。

1本の線について

まず、1つのデータまでの距離を2乗する

i 番目のデータの横・縦の位置を (xᵢ, yᵢ)、代表点の横・縦の位置を (pₓ, pᵧ) とします。

dᵢ² = (xᵢ − pₓ)² + (yᵢ − pᵧ)²

dᵢ は、この2点を結ぶ線の長さです。横のずれと縦のずれをそれぞれ2乗して足すと、斜めの線の長さの2乗になります。これは三平方の定理です。

すべての線について

次に、全部のデータについて足す

データが n 個あれば、線も n 本あります。それぞれで計算した距離の2乗を足します。

J(p) = ∑ dᵢ² = d₁² + d₂² + ⋯ + dₙ²

先に各距離を2乗し、そのあとで合計する順番です。距離が2倍なら、その線から足される値は4倍になります。遠いデータとのずれが、大きく数えられる仕組みです。

もう少し詳しく：重心で最小になる理由

重心の位置を、式で書いてみよう。

データの個数を n、i 番目のデータの横・縦の位置を (xᵢ, yᵢ) とします。平均は「全部足して、個数で割る」計算です。横の平均を mₓ、縦の平均を mᵧ と書くと、次のようになります。

mₓ = (x₁ + x₂ + ⋯ + xₙ) / n
mᵧ = (y₁ + y₂ + ⋯ + yₙ) / n

この点を m = (mₓ, mᵧ) とすると、どこに代表点 p を置いても、次の関係が成り立ちます。

J(p)現在の2乗誤差
=
J(m)重心での2乗誤差
+
n ‖p − m‖²重心から離れた分の増加

‖p − m‖ は代表点から重心までの距離です。最後の項は必ず0以上で、代表点が重心に一致したときだけ0になります。だから、重心は距離の2乗和を最小にする唯一の位置です。

この関係は、データがどんな形に並んでいても成り立ちます。次の実験では、離れた2つのまとまりにも、この性質を使います。

式の導出も見る

横方向だけを考え、ずれを次のように分けて2乗します。

xᵢ − pₓ = (xᵢ − mₓ) + (mₓ − pₓ)
∑(xᵢ − pₓ)² = ∑(xᵢ − mₓ)² + 2(mₓ − pₓ)∑(xᵢ − mₓ) + n(mₓ − pₓ)²

平均からのずれの和 ∑(xᵢ − mₓ) = 0 なので、中央の項は消えます。縦方向も同じように展開して足すと、上の式になります。

ここまでは、ひとまとまりのデータでした。まとまりが2つに離れていても、全体の重心1個で十分でしょうか。
次は、離れたデータで試そう ↓

STEP 02 · 1個では伝わらないこと

まとまりが2つなら、
全体の重心はどこに来る？

今度のデータは、左右の2か所に集まっています。代表点は、まだ1個。誤差も、先ほどと同じように、全データまでの距離をそれぞれ2乗して足します。

左のまとまりに代表点を置くと、右のデータまでの線が長くなります。では、代表点を右へ動かすと、全体の誤差はどう変わるでしょうか。

  1. 左右で比べる代表点を左と右のまとまりに置き、長い線と誤差を見よう。
  2. 間でも試す2つのまとまりの間へ動かして、誤差を比べよう。
  3. 重心を確かめる「全体の重心へ移動」を押し、その周りにデータがあるか見よう。

離れたデータを、1個で代表する

60 個のデータ
データ代表点 p
離れた2つの分布を1個の代表点で表す実験

グラフの横軸：位置を記録した順番 →

操作は先ほどと同じです。青い点をドラッグするか、図の中をクリック・タップして動かします。

この実験のデータについて

左右に30個ずつ、2つの正規分布から生成しています。中央の空白をはっきり示すため、各分布の端の広がりを制限しています。「データを作り直す」を押すと、次のSTEP 03も同じ新しいデータに切り替わります。

誤差の値と、図を見比べよう

誤差は最小。でも、どちらのまとまりからも離れている。

全体の重心は、左右のデータのない間に来ます。左へ寄ると右から遠ざかり、右へ寄ると左から遠ざかる。その全体のずれが最も小さくなるのが、この位置です。

平均の位置にデータ点がないこと自体は、よくあります。ここで注目したいのは、この1点だけでは「左右に2つのまとまりがある」と伝えにくいことです。

それぞれのまとまりを表すには、どうすればよいでしょうか。次は代表点を2個に増やし、データを分担してみましょう。

同じデータを、2個の代表点で表してみよう ↓
STEP 03 · 2個で分担する

近い代表点に任せたら、
それぞれをどこに置く？

上とまったく同じ60個のデータに、今度は代表点を2個置きます。データは変えず、代表点の数を変えて比べます。

2個あると、各データをどちらに任せるか決める必要があります。ここでは距離が近い方の代表点に任せることにします。このように担当を決めることを、割り当てと呼びます。

  1. 2個を置く代表点1と2を、それぞれ左右のまとまりへ動かそう。
  2. 担当を見る代表点1を代表点2の近くまで動かし、色と線の変化を見よう。
  3. 平均で整える「それぞれの重心へ移動」を押して、誤差を比べよう。

色と線が、今の担当を表す

同じ60個のデータ
代表点1・丸のデータ1の担当：丸代表点2・四角のデータ2の担当：四角
2個の代表点と、近い方へのデータの割り当て

グラフの横軸：位置を記録した順番 →

1・2の点をそれぞれドラッグできます。空いている場所をクリックすると、選択中の代表点が動きます。

データの位置は変わりません。色と線だけが、近い代表点に合わせて自動で切り替わります。

1個の重心の考え方を、それぞれの担当へ

担当を決める。担当の平均へ動かす。また担当を決める。

担当するデータを固定すると、代表点ごとにSTEP 01の問題になります。だから、それぞれの担当データの重心へ動かせば、その担当に対する2乗誤差を最小にできます。

ただし、代表点が動くと、近い方が入れ替わるデータもあります。担当が変われば、平均をとるデータも変わるので、もう一度重心へ動かします。

  1. 割り当てる各データを、今いちばん近い代表点に任せる。
  2. 重心へ動かす各代表点を、今の担当データの平均の位置へ動かす。

この2つを繰り返し、割り当てと代表点の位置が変わらなくなったら一区切りです。このデモでは割り当ては常に自動で行い、重心への移動をボタンで1回ずつ試せます。

これが、k-meansの基本です。

1つの代表点に割り当てられたデータの集まりを、クラスタと呼びます。k-meansの k は代表点の個数、meansは「平均」を意味します。ここでは k = 2 と決めて、2つのクラスタを作りました。

最初は「全体を1個の平均で表す」問題でした。その考え方を、「各クラスタを、それぞれの平均で表す」ところまで広げたのです。

うまく分かれないときは？

代表点を2個に増やしても、遠い場所に置けば誤差は大きくなります。まず左右のまとまりに1個ずつ置いてから、重心へ移動してみましょう。

繰り返して動かなくなっても、あらゆる置き方の中で最良とは限りません。初めに置く場所で結果が変わることは、k-meansの次の学習につながります。

担当が0個なら平均を計算できないため、このデモではその代表点を動かしません。自分で別のまとまりへ動かして試せます。距離が同じデータは代表点1に割り当てます。