眺めて学ぶ最短距離クラスタリングデモ
ずいぶん前ににJavaScriptで実装した最短距離法クラスタリングデモを公開します.
使い方
- プロットするデータ数をdata numberに入力します
- plot dataを押すと,ランダムにdata number数だけ2次元平面に一様にプロットされます
- 1stepボタンを押すと,プロットされたデータの中から最も近い同士のデータを結合します
- この際,show cluster infoをチェックしていると,クラスタが結合していく様を右側に表示します.
- 連続クリックするのがだるい人は10stepとかを使ってください
注意点
バカ正直に最短距離を計算しているので,最短距離の計算にN^2のオーダがかかります.プロット数を大きくしすぎるとブラウザがかたまるので注意してください.
雑記
最短距離法とは,特徴空間に存在するデータ点のうち,最も近い距離にある2点を同じクラスタに併合していく方法.詳しくはわかりやすい解説がウェブ上にごろごろしているのでそちらを参照してください.
このデモでは一様にデータ点をちらばめているので,綺麗な網目模様を描きながら併合していく.データが偏ったときなど,ひたすらそのエリアでクラスタが大きくなっていき,距離が離れているデータが無視され続けるといった弊害が発生する.
階層的クラスタリングといっておきながら階層情報を保持していないので,あまりありがたみがわかりません.網目模様きれいだなー,と思ってください.クラスタリングといってもノード同士のエッジで結んでいるので,あまりクラスタリングぽく見えないのは仕様です.
元々のモチベーションは,高次元空間にランダムにばらまいた点を最短距離法でクラスタリング (身近なノードと手をつないでいくと) スモールワールドネットワークが形成されるという研究を聞いて (元論文は失念.Kleinberg先生の論文だったと思います) ,原理的にはクラスタリングと一緒じゃね? と思ったのが始まりだったような,違ったような...さらには結局2次元クラスタリングというオチ.
なんかこれ書いた当時JavaScript勉強中で,初心者スキルで実装できるものを色々実装していた時期だったのでみたい.ナイーブベイズとか,転置インデクスもこの時期に実装しているし.
これを見てクラスタリングのイメージをつけるのは間違っている気もしますが,まぁ,何かのお役に立てば幸いです.文句,要望,プゲラ大歓迎です.