【重要】サービス終了のお知らせ

Forked from: kazuki_nagasawa's KKZ 法による k-means クラスタリング View Diff (67)

k-means++ クラスタリング

kazuki_nagasawa

License: MIT License

Fork
1
Fav
2
View
6888
  • Play

Fullscreen

Smart Phone

Fork tree

  • Readme
  • JavaScript 528 lines
  • HTML 32 lines
  • CSS 26 lines
( 前回 => http://jsdo.it/kazuki_nagasawa/clustering-kmeans-003 )

視覚化版 k-means クラスタリングの 3つ目。k-means++ によるクラスタリングを実装してみました。


■ k-means++ による、k-means の初期値決定

 1) 与えられた全データからランダムに 1点を決め、それを 1つ目のクラスタ中心点にする。

 2) 全データに対して、「既に決定されたクラスタ中心点とデータの最短距離」を求める。 ( d とする。)

 3) 2) の値 d をそれぞれ 2乗する。 ( pow_d とする。)

 4) 全データの pow_d をそれぞれ合計した値 ( sum_pow_d ) を用いて、各データの割合 ( pow_d / sum_pow_d ) を求める。

 5) 4) で求めた割合を用いてルーレット選択を行い、新たなクラスタ中心点とする。

 6) 2) ~ 5) を必要数繰り返す。

 7) 初期のクラスタ中心点がすべて決定したら、後は普通の k-means。


 ※ 参照

  基本は、以下の論文を参照:
   http://www.ymd.nii.ac.jp/lab/publication/conference/2011/JSAI-2011-Onoda.pdf

  ただし、この k-means++ の定義の式は間違っている ( 不等式が逆になっている!! ) ので、
  こちら ( 元の k-means++ の論文らしい ) も参照した:
   http://ilpubs.stanford.edu:8090/778/1/2006-13.pdf


■ KKZ 法と比較して

 KKZ 法は、最も遠い点同士をクラスタ中心点にしたため、うまくクラスタ分けし易かった。
 ただし、この方法だと外れ値が多い場合に対応できなくなる問題がある。
 ( 「最も遠い点同士を選ぶ」=> 外れ値が選ばれる可能性が高い!! )

 上記問題を、k-means++ では確率的に初期値を選択することで対処している。
 外れ値が選ばれる可能性を下げている。
 ( 5) ルーレット選択 のところ )

 ※ それでも「確率的」なので、『正しいクラスタ分けか』と言われると…


■ 使い方

 データ数とクラスタ数を指定して「実行」ボタンで計算が始まります。

 1 step が 1000msec で動き、収束したらアラートで知らせます。

 データは 2次元。( x, y ) 共に 0 ~ 100 の実数です。

 データ数とクラスタ数を変更したら、初期化ボタンで初期化し直してください。


■ 備考

 k-means++ による初期値決定を見易くするため、
 「実行」ボタンを押して初期重心点決定した後、3000msec で次のステップに続きます。

 それ以後は 1ステップ 1000msec です。


■ 注意等

 create.js を使用しています。
 canvas に対応しているブラウザのみ閲覧可能です。


  • k-means++ クラスタリング
  • CreateJS 2013.02.12
  • Underscore.js v1.4.4
  • bootstrap.js 3.0.0
  • jQuery v2.0.3
  • k-means++ クラスタリング
  • bootstrap.css 3.0.0

play

Complete!

Description What kind of game?

Control Device

jsdo.it websocket controller

Mouse

keyboard

smartphone

Fullscreen

kazuki_nagasawa

Author

Three.js や Processing.js など、描画系のライブラリで遊んでます。 色々描けるようになりたいにゃ~。

Default Panel

Size

  • Width: px
  • Height: px

code

QR Code

Discussion

Questions on this code?

Tags

Favorite by

Forked

sort by