search - kNN 検索に効率的な kd ツリーです。k 最近傍探索

Question

kd-treeで10次元データのk最近傍検索を実装する必要があります。

しかし、問題は、私のアルゴリズムが k=1 の場合は非常に高速ですが、k>1 (k=2,5,10,20,100) の場合は 2000 倍も遅くなることです。

これは kd ツリーの正常な動作ですか?

Answer 1

まあ、それは主にあなたの特定の実装とデータセットに依存します。

ツリーのバランスが悪いと、必要以上に多くのデータを検索する必要があります。あなたのツリー構造が正気であることを確認してください。

また、k近傍を見つける方法にも依存する可能性があります。アルゴリズムがツリーで最も近いネイバーを検索して保存し、次に2番目に近いものを検索して保存する場合など、検索はあまり効率的に行われません。代わりに、ツリーを横断するより近いものを見つけたら、リストからk最近傍とバンプポイントの実行リストを保持します。このようにして、k回ではなく1回検索します。

いずれにせよ、あなたはコースのためにこれをしているように聞こえます。教授、TA、またはクラスメートと話して、結果が典型的なものかどうかを確認してください。

Answer 2

この質問には回答済みですが、kd ツリーを使用した KNN 検索の詳細については、Bentley (1975:514)、Communications of the ACM 18(9)、9 月を参照してください。