Sun May 10 09:32:08 JST 2015

kNNグラフの近似的な構築

Efficient k-nearest neighbor graph construction for generic similarity measures
を読んで, 簡単そうだったから実装してみた

入力 (点の集合) は距離空間によらない多次元多データであっていいと謳っているが
大規模なデータは用意できないから

import random
 
def plot():
    x = random.random() * 100
    y = random.random() * 100
    print x, y

for i in xrange(100):
    plot()

とした。
すなわち, 二次元区間 \([0,100] \times [0,100]\) 内に一様分布させた 100点だけである (\(n = 100\))

論文はグラフを厳密に作る代わりに近似的に作ることで構成する
というわけで評価尺度は, 2点間の距離を計算する回数でもってどのくらい高速であるか, と
グラフの正しさを recall で測る

https://gist.github.com/cympfh/24fe11b272de43e861ee
これは \(k=20\) で実験をする
結果は以下の通り

#calc of distance = 116788
scan rate = 23.5935
recall = 0.9925

十分に正しいものが得られた。
scan rate というのが, 距離を計算した回数を \(n (n-1)/2\) で割ったものである
\(n (n-1)/2\) というのは, ナイーブに全ての組み合わせの距離を計算した場合の回数

であるから, 高速であるというにはscan rate は1未満であるべきで小さいほど良いことになる
逆に, 1以上なら, ナイーブに計算したほうがいいことになってしまう
論文だと, 0.01 程度の数字が示されてたけど,
私の結果だとずっと大きくなった
そもそも全然違う挙動をしていて,

収束するまでループを回す箇所があるのだが, 私のプログラムはまるで収束する気配がなくて, しょうがなく13回だけ回してる。 これを減らせば scan rate はいくらでも減る

ループ 4回

#calc of distance = 37428
scan rate = 7.56121
recall = 0.9905

ループ 2回

#calc of distance = 19792
scan rate = 3.99838
recall = 0.921

ループ 1回

#calc of distance = 10930
scan rate = 2.20808
recall = 0.6335

少なくともループは1回以上回すはずなのに,
そのじてんで scan rate が1を超えているというのは???

ナイーブには \(n (n-1)/2\) に対して, このアルゴリズムは \(c n k^2\) 程度
其のループ一回で \(nk^2\) なのだった \(n \gg k\) じゃないとこのアルゴリズムのほうが遅いことはあり得る