最小全域木(Minimum Spanning Tree)と格闘

普通にやると0(N^3)の計算量になってしまった...orz
O(N*LogN)の計算量で解けるらしいのだが、ヒープが良く分からない。
とりあえずO(N^2)まで頑張って効率化して、今日のところはO(N^2)で勘弁してやることにする。

が、ここでもっと致命的なことが発覚!!
10,000×10,000のdouble型の配列なんてメモリーにのりきらないよ!!!!
最小全域木以前に全データ間の距離がメモリーにのせられない。
初期化処理の最初の段階でスワップが...orz

もちろん適時距離計算すればいいんだけど、それはそれで計算負荷がかかりすぎる。
1万件以上のデータが出てきたらDB使うくらいしか思いつかない。
そして最終的に扱うデータ数は25万件!!

データマイニング、おそるべし...orz

1 trackbacks in legacy system
2006年06月02日 数式を使わないデータマイニング入門 隠れた法則を発見する - 野菜とネット - amaxoop2

データマイニングが従来の統計分析と一線を画して語られるのは、取り扱う情報が質と量の...