クラスタリングの定番アルゴリズム K-means 法（K平均法）の動作原理を理解するために、D3.js を使って可視化してみました。

• 図をクリックするか [ステップ] ボタンを押すと、1ステップずつ処理を行います
• [最初から] ボタンを押すと、最初の状態に戻ります
• [新規作成] ボタンを押すと、N (ノード数) と K (クラスタ数) の値で新しく初期化します
• 古いブラウザーではうまく表示できない可能性があります (IE 10、Firefox 25、Chrome 30 で動作確認しています)

K-Means 法とは

英語版 Wikipedia の k-means clustering - Wikipedia, the free encyclopedia の手順に沿って実装しています。

英語版の手順をザックリと書くとこんなイメージになります。

1. 初期化: N 個のノード (丸印) と K 個のクラスター (×印) を作成する
2. Assignment ステップ: 各ノードを一番近いクラスターに所属させる
3. Update ステップ: クラスターをノードの重心に移動させる
4. ステップ 2 に戻る

最初は 1 の状態で表示していて、クリックするごとに、ステップ 2 とステップ 3 を実行していきます。

ステップを繰り返すにしたがって、クラスターの重心 (×印) が移動しながら、塊ができていく様子を確認できると思います。

D3.js と ActionScript 3

ここからはプログラミングの話です。

お気づきの方もいるかもしれませんが、このビジュアライズは 4 年ほど前に ActionScript 3 で作った クラスタリングの定番アルゴリズム「K-means法」をビジュアライズしてみた の焼き直しです。

同じものを D3.js と ActionScript 3 で実装してみて気づいたことがいくつかあります。

実装のしやすさ

ActionScript 版にくらべて、D3.js 版では

• クラスタが変わるときの色の変化のアニメーション
• 重心が移動するときの線のアニメーション
• 新規作成のときのアニメーション

を追加しています。

D3.js の data() や enter() といった API を活用すれば、このようなアニメーションが簡単に実現できました。ActionScript で同じことを実現するのは、かなり面倒です。data() や enter() の嬉しいところについては、D3.js の Data-Driven な DOM 操作がおもしろい で書いているので、興味があれば読んでください。

ただ、D3.js で作る場合は、data() などの API にあわせてデータ構造を作りあげる必要があるので、少し慣れが必要でした。

表示速度

やっぱり Flash は速い。

D3.js 版では、ノードが増えたときのコマ落ちが目立ちます。このあたりは、ブラウザーの将来の進化に期待したいところです。

まとめ

• K means 法をビジュアライズしてみたよ
• D3.js 便利
• ブラウザーの進化に期待

JavaScript のソースは k-means.js においてます。