さて、3日目。
前回 aipacommander.hatenablog.jp
k-meansを何度か試したらなんとなーく理解してきたのでまとめ
ソースはこちら
k-means計算内容まとめ
読み方変更について
色々ごちゃごちゃしてきたので、wikiに合わせます。
計算手順
1.クラスタ情報をランダムにポイント
コードではクラスタはgroup
って変数で入っています。
2.データ情報をランダムにポイント
データはdot
です。
3.クラスタにデータを割り当てる
それぞれ距離を求めて紐付けていく。
コードはこちら
k-means.js :225行目
/** * クラスタとデータの割当てを行う */ function updateGroups() { groups.forEach(function(g) { g.dots = []; }); // 再計算するため、クラスタに割り当てたデータを初期化 /** * データの数だけループしていく * んで、そのデータの位置とすべてのクラスタ位置を計算して一番近いクラスタを探す。 * それが見つかればそのクラスタにデータを割り当てる */ dots.forEach(function(dot) { var min = Infinity; var group; groups.forEach(function(g) { var d = Math.pow(g.center.x - dot.x, 2) + Math.pow(g.center.y - dot.y, 2); // 位置を計算する式 if (d < min) { min = d; group = g; } }); group.dots.push(dot); // ここが割り当てる箇所 dot.group = group; // データにもクラスタの情報を渡す }); }
これで、割当が再計算されます。
4.割当てたデータの真ん中を計算し、クラスタの位置を更新
3でデータの割当が完了したら、それらの中心を出します。
んで、出したら、そのポイント(x,y)でクラスタの位置を更新
コードは(ry
k-means.js :204行目
/** * クラスタの位置を更新する */ function moveCenter() { groups.forEach(function(group, i) { if (group.dots.length == 0) return; // 割当てられているデータが0の場合は計算する必要なし var x = 0, y = 0; /** * 中心の求め方の式はよくわからないが * 全部のデータの位置(x,y)を足してデータの数で割る -> 平均をとったらそれは真ん中になるとのこと * 数学赤点の俺にはよくわからん^q^ */ group.dots.forEach(function(dot) { x += dot.x; y += dot.y; }); // 平均を出す -> クラスタの位置を更新 group.center = { x: x / group.dots.length, y: y / group.dots.length }; }); }
5. 収束するまで手順3と手順4を繰り返す
手順4で位置を更新することにより、クラスタとデータの距離が変わります。なので、手順3を実行。
手順3を実行することにより、割当てたデータ達の中心が変更になります。なので、手順4を実行
これら手順が繰り返されるgifアニメーションを用意しました。
んで、途中だんだんクラスタが動かなくなってきます。全く動かなくなったら計算終了です。
なぜ動かなくなるの?
何度かステップを進めるとクラスタそれぞれが割り当てられたデータの距離が変わらなくなります。
すると、平均も変わらなくなるので、クラスタの位置も更新されなくなるから。。。なのかな?
多分「いちばん最適な割当ての状態が作られた!」ってことなんでしょうかね。
感想
やっと理解した感じじゃない?(d3.jsの使い方は全然スルーしているけど)
それでね。
これで何ができるのかな?(°ω°?
k-meansでクラスわけをするってことはわかった!
どうやって画像とかテキストのデータを座標に割り当てていくんだおい(^ω^
続く