2006.08.19

Research

MOCKを少し改良

2次元なら13,000データまで、スワップ起こさずに扱えるようになった。実行時間は数時間程度。そして大部分が初期化処理に費やされている。全体が1時間だったら50分くらい初期化かな?

Square1というk-meansで最も解きやすいテスト問題を、1,000データから13,000データにして、クラスタ数を2から13に増やして実験してみたところ、性能は落ちるものの全く解けなくなることは無いかなという感触。

実行時間は初期化以外はちゃんとO(N)で行けてるので、問題は

  • 初期化時のO(N^2)の処理
  • メモリー容量

初期化部分は総当たりの距離計算とソート処理なので、少なくとも距離計算は並列化できそう。あとは並列化で使えるメモリーを増やしてやりさえすれば、SuperNova全部のメモリー使って大体130,000データは扱えるかなと。最悪距離計算の結果を配列で持たずに適時計算してやれば、それだけでメモリー制約からは解放される。計算時間がものすごい増えそうだけど。。。


あと、データが増えるとクラスタ間の結合が強くなる傾向が見受けられる(具体的にはクラスタ間を横断するリンクの本数が増える)為、

  • ランダム抽出
  • 初期化でk-meansを使って初期解の精度を上げる
  • 凝集法的なやり方でデータ数を絞る

とかなんかしないとダメかなぁという感じ。どちらを使うかは、データの性質次第?