したがって、約 16,000 の 75 次元データ ポイントがあり、各ポイントについて、k 個の最近傍を見つけたいと考えています (ユークリッド距離を使用して、現在は k=2 で簡単にできます)。
私が最初に考えたのは、これに kd ツリーを使用することでしたが、実際には、次元の数が増えるにつれてかなり非効率になることがわかりました。私のサンプル実装では、徹底的な検索よりもわずかに高速です。
私の次のアイデアは、PCA (主成分分析) を使用して次元数を減らすことですが、疑問に思っていました: これを適切な時間内に正確に解決するための巧妙なアルゴリズムまたはデータ構造はありますか?
kd-trees のウィキペディアの記事には、ANN ライブラリへのリンクがあります。
ANN は C++ で記述されたライブラリであり、任意の高次元での正確な最近傍検索と近似最近傍検索の両方のデータ構造とアルゴリズムをサポートしています。
私たち自身の経験に基づくと、ANN は、サイズが数千から数十万、 次元が 20までの点集合に対して非常に効率的に機能します。(非常に高い次元のアプリケーションの場合、結果はかなりむらがありますが、とにかく試してみてください。)
アルゴリズム/データ構造に関する限り:
このライブラリは、kd-trees とbox-decomposition treesに基づいて多数の異なるデータ構造を実装し、いくつかの異なる検索戦略を採用しています。
最初に直接試して、満足のいく結果が得られない場合は、PCA/ICA を適用した後にデータセットで使用します (kd ツリーが扱う）。
これが NP 完全であると信じる理由はありません。あなたは本当に何も最適化していないので、これを別の NP 完全問題に変換する方法を理解するのに苦労します (棚にGarey and Johnsonがあり、同様のものを見つけることができません)。本当に、検索と並べ替えのより効率的な方法を追求したいと思います。n 個の観測がある場合、nxn の距離を事前に計算する必要があります。次に、観測ごとに、上位 k 個の最近傍を選択する必要があります。これは、距離計算では n 二乗、並べ替えでは n log (n) ですが、並べ替えを n 回実行する必要があります (n の値ごとに異なります)。面倒ですが、答えを得るにはまだ多項式時間です。
BK-Tree はそれほど悪い考えではありません。レーベンシュタイン オートマトンに関するニックのブログをご覧ください。彼はストリングスに焦点を当てていますが、他のアプローチへの出発点となるはずです。他に考えられるのはR-Treeですが、それらが大きな次元に一般化されているかどうかはわかりません。私はそれらを直接使用したり、自分で実装したりしていないので、それ以上は言えません。
Morton Codesを使用することも考えられますが、75 次元では巨大になります。また、16,000 個のデータ ポイントしかない場合は、徹底的な検索にそれほど時間はかかりません。
非常に一般的な実装の 1 つは、データ ポイントごとに計算した Nearest Neighbors配列を並べ替えることです。配列全体の並べ替えは非常にコストがかかる可能性があるため、Python Numpy ライブラリの Numpy.argpartition などの間接的な並べ替えなどの方法を使用して、関心のある最も近い K 値のみを並べ替えることができます。配列全体を並べ替える必要はありません。
上記の@Gremboの回答は大幅に削減する必要があります。K個の最も近い値のみが必要なためです。また、各ポイントからの距離全体を並べ替える必要はありません。
K個の隣人だけが必要な場合、この方法は非常にうまく機能し、計算コストと時間の複雑さを軽減します。
ソートされた K 個の近傍が必要な場合は、出力を再度ソートします
見る