適切なクラスタ数を推定するX-means法

K-means法によるクラスタリングでは、あらかじめクラスタ数Kを固定する必要があります。HatenarMapsでもK-means法を使っているのですが、クラスタ数は（特に根拠もなく）200個に決め打ちになっていました。

これに対して、X-means法というK-means法の拡張が提案されていることを知りました。X-means法を使うと、データに応じて最適なクラスタ数を推定できます。

K-means and X-means implementations
http://www-2.cs.cmu.edu/~dpelleg/download/xmeans.pdf

X-means法の考え方は、K=2で再帰的にK-means法を実行していくというもので、クラスタの分割前と分割後でBIC（ベイズ情報量規準）を比較し、値が改善しなくなるまで分割を続けます。

調べたところ、JavaのデータマイニングツールのWekaの中にもX-meansのコードが含まれています。ただ、BICの算出法が論文とは微妙に違っています。

Wekaも参考にしながらX-means法を実装して、以前書いたK-means++と組み合わせてHatenarMapsに採用してみました。

今のところHatenarMapsでは、はてなダイアリーユーザのブックマーク数上位約3000人をクラスタリングしているのですが、X-means法で推定されたクラスタ数は100前後になりました。

以下はK-means法でクラスタ数を固定して生成していた、従来のHatenarMapsです。クラスタ数が最適化されていなかったせいか、K-means法の後に実行する階層クラスタリング結果のツリーの平衡が悪くて、赤で囲んだエリアが周りに比べて渦巻き状に深くなってしまっています。

以下は、X-means法に変えた結果です。上に比べて、何となくバランスが良くなっている気がします。