問題タブ [nearest-neighbor]

クラスターが特定のサイズに制限されている場合、特定のデータセットの最も多くのポイントを含む N 個のクラスターを見つけることを任されました。現在、データを kd ツリーにプラグインし、データを繰り返し処理して最も近い隣人を見つけ、それらが作成するクラスターが制限を超えていない場合はポイントをマージすることで、これを実行しようとしています。このアプローチがグローバルなソリューションを提供してくれるかどうかわからないので、微調整する方法を探しています。これがどのような種類の問題になるか教えていただければ、それも素晴らしいことです。

100 次元空間に 500,000 点のデータベースがあり、最も近い 2 点を見つけたいと考えています。どうすればいいのですか？

更新: スペースはユークリッドです。申し訳ありません。そして、すべての答えに感謝します。ところで、これは宿題ではありません。

2D 空間のポイントを表す約 100,000 (X, Y) ペアのデータセットがあります。各点について、その k 最近傍点を見つけたいと思います。

それで、私の質問は、全体の実行時間を絶対に最小限に抑えたいと仮定すると、どのデータ構造/アルゴリズムが適切な選択になるでしょうか?

私はコードを探しているのではなく、適切なアプローチへの単なるポインタです。関連性があると思われる選択肢の範囲 (四分木、R 木、kd 木など) に少し戸惑っています。

最良のアプローチは、データ構造を構築してから、各ポイントに対してある種の k 最近傍検索を実行することだと考えています。ただし、(a) 事前にポイントを知っており、(b) すべてのポイントの検索を 1 回だけ実行する必要があることを知っているので、おそらくより良いアプローチがあるでしょうか?

追加の詳細:

• 全体の実行時間を最小限に抑えたいので、大部分の時間が構造と検索に費やされてもかまいません。
• (X, Y) のペアはかなり分散しているため、ほぼ均一な分布であると想定できます。

したがって、約 16,000 の 75 次元データ ポイントがあり、各ポイントについて、k 個の最近傍を見つけたいと考えています (ユークリッド距離を使用して、現在は k=2 で簡単にできます)。

私が最初に考えたのは、これに kd ツリーを使用することでしたが、実際には、次元の数が増えるにつれてかなり非効率になることがわかりました。私のサンプル実装では、徹底的な検索よりもわずかに高速です。

私の次のアイデアは、PCA (主成分分析) を使用して次元数を減らすことですが、疑問に思っていました: これを適切な時間内に正確に解決するための巧妙なアルゴリズムまたはデータ構造はありますか?

そこで、最近傍探索を行うためにKDツリーを実装しています。ツリー部分の構築は機能していますが、検索部分を完全には理解していないと思います。

隣人を探すために木を横断することについて、ウィキペディアの記事は次のように述べています。

「スピットディメンションの現在のノードよりも大きいまたは小さい」とはどういう意味ですか？クエリからの距離に基づいてポイントを比較しますか、それとも分割ディメンションでポイントを比較しますか？

また、誰かが超空間と超平面についての部分を説明できますか？理解できた気がしますが、よくわからないのでもう少し説明をお願いします。

ありがとう！

データセットの各点について、最も近いすべての点を見つける必要があります。データセットには約が含まれています。1000 万の 2D ポイント。データはグリッドに近いですが、正確なグリッドを形成していません...

このオプションは、(私の意見では) KD ツリーの使用を除外します。基本的な前提は、同じ x 座標と y 座標を持つポイントがないことです。

この問題を解決するには、O（n）以上の高速アルゴリズムが必要です（ただし、実装にはそれほど難しくありません:-)））...ブーストは標準化されていないため、使用したくありません...

回答またはコードサンプルをありがとう...

KD ツリー (静的ケース) を構築しようとしています。ポイントは x 座標と y 座標の両方でソートされていると仮定します。

再帰の深さを均一にするために、セットは中央の x 座標を通る垂直線で 2 つのサブセットに分割されます。

再帰の深さが奇数の場合、セットは 2 つのサブセットに分割され、水平線は中央の y 座標を通過します。

中央値は、x / y 座標に従ってソートされたセットから決定できます。このステップは、セットを分割する前に行っています。そして、それがツリーの構築を遅らせる原因になっていると思います。

1. コードをチェックして最適化するのを手伝ってくれませんか?
2. k 番目の最近傍が見つかりません。誰かコードを手伝ってくれませんか?

あなたの助けと忍耐に感謝します...

サンプル コードを参照してください。

K最近傍、または距離d内のすべての近傍を見つける必要があるデータセットがあります。データセットにはカスタム距離が定義されていますが、ユークリッド距離ではありません。

私は以前にメトリックツリーを使用しましたが、ほとんどはカバーツリーです。ただし、この場合、私のデータセットは使用可能なメモリよりも大きくなります。では、ディスクに保存されたデータセットの最近傍に使用できるデータ構造はありますか？この操作に適したデータベースインデックスも役立ちます。

粒子相互作用のシミュレーションに取り組んでいるときに、効率的な最近傍セル検索を提供すると見なされているMorton オーダー (Z オーダー) ( Wikipedia リンク)のグリッド インデックス付けに出くわしました。私が読んだ主な理由は、メモリ内の空間的に近いセルのほぼ連続した順序付けです。

最初の実装の途中であるため、特に基本的な均一グリッドと比較して、最近傍のアルゴリズムを効率的に実装する方法について頭を悩ませることはできません。

1. セル (x,y) が与えられた場合、8 つの隣接セル インデックスを取得し、それぞれの z インデックスを計算するのは簡単です。これにより、要素への一定のアクセス時間が提供されますが、z-index を計算するか、事前定義されたテーブルで検索する必要があります (軸ごとに分離し、OR を計算します)。どうすればこれがより効率的になるでしょうか? 配列 A の要素に A[0] -> A 1 -> A[3] -> A[4] -> ... という順序でアクセスすると、A[1023 の順序よりも効率的です。 ] -> A[12] -> A[456] -> A[56] -> ...?

2. Z オーダーで最近傍を見つけるためのより単純なアルゴリズムが存在することを期待していました。線に沿った何か: 隣接セルの最初のセルを見つけて、反復します。しかし、これは 2^4 サイズのブロック内でのみうまく機能するため、そうではありません。ただし、2 つの問題があります。セルが境界上にない場合、ブロックの最初のセルを簡単に特定してブロック内のセルを反復処理できますが、セルが最近傍セルであるかどうかを確認する必要があります。セルが境界上にある場合は、2^5 個のセルを考慮する必要がある場合よりも悪いことになります。ここで何が欠けていますか？私が必要とすることを行う比較的単純で効率的なアルゴリズムはありますか?

ポイント 1. の質問は簡単にテストできますが、記述されたアクセス パターンが生成する基本的な命令についてはあまり詳しくなく、舞台裏で何が起こっているのかを本当に理解したいと思っています。

ヘルプ、参考文献など、事前に感謝します...

---

編集：
ポイント1を明確にしていただきありがとうございます！ということで、Z-orderingを使うと隣接セルのキャッシュヒット率が平均的に上がるというのは興味深いですね。キャッシュのヒット/ミス率をプロファイリングする方法はありますか?

ポイント2に関して：インデックスi = f（x1、x2、...、xd）がビットごとのインターレースなどから取得されるR ^ dの点群のモートン順序配列を構築する方法を理解していることを追加する必要があります.私が理解しようとしているのは、次の単純な ansatz よりも、最近傍を取得するためのより良い方法があるかどうかです (ここでは d=2、「疑似コード」)。

インクリメンタルに更新できる Python で実装された最近傍アルゴリズムを知っている人はいますか? this oneなど、私が見つけたものはすべてバッチプロセスのようです。インクリメンタルNNアルゴリズムを実装することは可能ですか?