KDツリーを使用してKNN検索を作成しようとしています。私はKDツリーをうまく形成することができます（または少なくとも、私はできると信じています！）。私の問題は、ポイントのリスト内のすべてのポイントに最も近い2つのネイバーを検索していることです。
それで、ポイントが実際にツリー内にある場合でも、KDツリーを使用してポイントに最も近いK個の近傍を見つける方法はありますか、またはポイントごとに個別のKDツリーを構築して、希望するポイントを除外する必要がありますか？検索するには？
私の実装言語はC++ですが、アルゴリズムまたは一般的なヘルプのいずれかを探しています。ありがとうございます。
ありがとう、スティーブン
ツリー内のK個の 正確な最近傍が必要な場合は、ツリーにK + 1個の近傍を照会するだけです（明らかに、最初の最近傍が照会になるため）。
これはあまり答えではありませんが、コメントに貼り付けたいものを収めることができません。とにかく、ウィキペディアからの関連テキストは次のとおりです。
アルゴリズムは、簡単な変更によっていくつかの方法で拡張できます。これは、1つではなくkの現在のベストを維持することにより、あるポイントにk最近傍を提供できます。ブランチは、k個の現在のベストのいずれよりも近いポイントを持つことができない場合にのみ削除されます。
また、より高速に実行するために近似アルゴリズムに変換することもできます。たとえば、ツリーで調べるポイントの数に上限を設定するか、リアルタイムクロックに基づいて検索プロセスを中断することで（ハードウェア実装でより適切な場合があります）、近似最近傍探索を実現できます。ツリー内にあるポイントの最近傍は、結果として距離がゼロになるノードの絞り込みを更新しないことですでに達成できます。これには、一意ではないが元の検索ポイントと同じ場所にあるポイントを破棄するという欠点があります。 。
近似最近傍は、最適なポイントを徹底的に検索しないことで速度が大幅に向上するため、ロボット工学などのリアルタイムアプリケーションで役立ちます。その実装の1つは、BestBinFirstです。
実装の詳細については、ANNを確認することをお勧めしますhttp://www.cs.umd.edu/~mount/ANN/
これは、おおよその最近傍検索用に設計されていますが、正確な最近傍検索も実行できます。これは、私が今までに見つけた中で最も明確で最もよく書かれたコードの一部でもあり、独自の実装が必要な場合でも、ある程度の洞察を提供するはずです。