問題タブ [knn]

私は3次元の点のセットを持っています。これらのポイントのいずれかの k 最近傍点の簡単なクエリが必要です。これを行う通常の方法はオクトツリーであることは知っていますが、以下に説明するデータ構造を使用すると、クエリははるかに高速になると思います。

次のプロパティを持つ頂点としてのポイントの最小限のグラフが必要です。

任意の 2 点 P1、P2 の間には、すべての内部点 P3 に対して次のパスがあります。

距離 (P1、P3) <= 距離 (P1、P2)。

私の問題は、手頃な時間でこの最小限のグラフを計算する方法を理解できないことです。

異なる場所に 50 個の要素を持つ 2D サーフェス ( Grid ) があります。特定のポイントに最も近い 10 個の要素を決定する必要があります。

さらに、指定されたポイントは常に移動しており、移動ごとに計算を行う必要があります。

各動きの各ポイントまでのユークリッド距離を計算できることはわかっていますが、より高速な方法が必要です。

ありがとう。

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

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

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

3-dの点は、（x、y、z）によって定義されます。任意の2点（X、Y、Z）と（x、y、z）の間の距離dは、d = Sqrt [（Xx）^ 2 +（Yy）^ 2 +（Zz）^2]です。現在、ファイルには100万のエントリがあり、各エントリは特定の順序ではなく、空間内のあるポイントです。任意のポイント（a、b、c）が与えられた場合、それに最も近い10ポイントを見つけます。百万ポイントをどのように保存し、そのデータ構造からそれらの10ポイントをどのように取得しますか。

現在、バランスの取れた KD ツリー(K=2)のすべてのノードの K Nearest Neighborを見つけようとしています。

私の実装は、ウィキペディアの記事のコードのバリエーションであり、任意のノードO(log N)の KNN を見つけるのはかなり高速です。

問題は、各ノードの KNN を見つける必要があるという事実にあります。 各ノードを反復処理して検索を実行すると、約 O(N log N) になります。

これを行うより効率的な方法はありますか？

KDツリーを使用してKNN検索を作成しようとしています。私はKDツリーをうまく形成することができます（または少なくとも、私はできると信じています！）。私の問題は、ポイントのリスト内のすべてのポイントに最も近い2つのネイバーを検索していることです。

それで、ポイントが実際にツリー内にある場合でも、KDツリーを使用してポイントに最も近いK個の近傍を見つける方法はありますか、またはポイントごとに個別のKDツリーを構築して、希望するポイントを除外する必要がありますか？検索するには？

私の実装言語はC++ですが、アルゴリズムまたは一般的なヘルプのいずれかを探しています。ありがとうございます。

ありがとう、スティーブン

だから私は画像のパターン（数字の4など）を認識できるようにしたいのですが、さまざまなアルゴリズムについて読んでいて、最近隣人アルゴリズムを本当に使いたいと思っています。 : http://people.revoledu.com/kardi/tutorial/KNN/KNN_Numerical-example.html 問題は、欠落しているデータセットを埋めるためにそれを使用する方法は理解していますが、画像形状認識を目的としたパターン認識ツールとして使用する方法がわかりません。このアルゴリズムがパターン認識でどのように機能するかについて、誰かが光を当てることができますか? OpenCV を使用したチュートリアルを見たことがありますが、自分で前処理を行う能力があるため、このライブラリを実際に使用したくありません。単純な最近傍であるべきもののためだけにこのライブラリを実装するのはばかげているようです。アルゴリズム。

Pythonで顔認識プログラムをコーディングしようとしています（分類にはk-nnアルゴリズムを適用します）。

まず、画像をグレースケールに変換してから、画像のピクセル（128x128 = 16384の機能の合計）を使用して（Opencvのimagedata関数を使用して）長い列ベクトルを作成しました。

したがって、次のようなデータセットを取得しました（最後の列はクラスラベルであり、16384ではなくデータセットの最初の7つの機能のみを表示しました）。

しかし、このデータセットにk-nnを適用すると、厄介な結果が得られます。画像をピクセル表現に変換するだけでなく、このデータセットに追加のプロセスを適用する必要がありますか？

ありがとう。

私の特徴ベクトルには、連続（または広範囲）コンポーネントとバイナリコンポーネントの両方があります。単にユークリッド距離を使用すると、連続成分の影響がはるかに大きくなります。

対称と非対称を0と1として表し、0から100の範囲の重要性の低い比率を表す場合、対称から非対称に変更すると、比率を25変更する場合と比較して、距離への影響はわずかです。

対称性に重みを追加することはできますが（たとえば、0または100にすることで）、これを行うためのより良い方法はありますか？