私は実際に高次元データ (〜 50.000-100.000 の機能) に取り組んでおり、最近傍検索を実行する必要があります。次元が大きくなるにつれて KD-Trees のパフォーマンスが低下することを知っています。また、一般に、すべての空間分割データ構造は、高次元データで徹底的な検索を実行する傾向があることも読みました。
さらに、考慮すべき重要な事実が 2 つあります (関連性の高い順に並べてあります)。
そこで、次のことについてアドバイスが必要です。
高次元空間で NN 検索を実行できますか?
いいえ。次元の呪いのため、最近傍検索を低次元で適切に実行するデータ構造は、高次元の場所ではうまく機能しません。実際のところ、クエリ時間は力ずくの場合とほぼ同じになるため、価値がありません。
その結果、高次元空間では、近似最近傍(ANN) 検索を行う必要があります。正直なところ、それは必須です。
ANN を実行するデータ構造は?
LSH、またはいくつかの RKD ツリーをお勧めします。ここでの私の回答では、C++ で ANN を実行するいくつかの優れたライブラリについて言及しています。ただし、LSH は R 最近隣問題を解決したことに注意してください。したがって、実際には半径であるパラメーター R を指定します。次に、LSH はクエリ ポイントからその R 内の NN を検索します。したがって、k 個の NN を実際に要求することはできません。
一方、RKD ツリーはそれを行うことができ、k 個の NN を返します。RKD ツリーのフォレストを構築し、C++ で ANN 検索を実行するプロジェクトがありますが、高次元のみを対象としています。960 次元の 10^6 画像の GIST データセットを 1 秒未満で処理でき、約 90% の出力が真の最近傍です。名前はkd-GeRaFです。翌月には配布バージョンで更新されますが、すでにテスト済みで、すぐに使用できます。かわいいロゴも入っています。:)
また、最適なデータ構造はデータに依存するという私の回答を読む必要があると思います。
このような高次元データでクラスタリングを行うのは賢明ではないと思います。寸法問題の呪いがあります。
特定のデータセット内の任意の 2 点間の距離は収束するため、次元の数が増えるにつれて、距離の概念は正確ではなくなります。
高次元空間での直接のユークリッド距離ではなく、距離の適切な尺度を見つけることをお勧めします。
このページにいくつかの可能な解決策がリストされています 。
2.1 部分空間クラスタリング
2.2 射影クラスタリング
2.3 ハイブリッドアプローチ
2.4 相関クラスタリング