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 はいくらでも減る
#calc of distance = 37428
scan rate = 7.56121
recall = 0.9905#calc of distance = 19792
scan rate = 3.99838
recall = 0.921#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\) じゃないとこのアルゴリズムのほうが遅いことはあり得る