問題タブ [nearest-neighbor]

ここで助けが必要です。私は実験的な Web フォーム デザインを行う数字が苦手な UI デザイナーであり、Web ページでクリックされたポイントに最も近い入力要素を知る必要があります。ポイントで最近傍を行う方法は知っていますが、入力要素はポイントではなく長方形であるため、行き詰まっています。

私はjQueryを使用しています。この小さなアルゴについて助けが必要です。実験が終わったら、私が何をしているかを皆さんにお見せします。

アップデート

どうすればうまくいくかを考えました。この図を見てください：

各長方形には、重要な 8 つのポイント (または 4 つのポイントと 4 つの線) があります。水平点 (赤い点) では x 値のみが重要であり、垂直点 (緑色の点) では y 値のみが重要です。コーナーでは x と y の両方が重要です。

Orange crosses are the points to be measured against – mouse clicks in my use case. The light purple lines are the distances between the orange cross and it's possible nearest point.

So… for any given orange cross, loop through each of the 8 points n every rectangle to find the nearest edge or corner closest of each rectangle to the orange cross. The rectangle with the lowest value is the nearest one.

I can conceptualize and visualize it but can't put it into code. Help!

そして、私が探している別のアルゴリズム: 最近隣問題までの平均距離の無料の C/C++ 実装。

したがって、基本的に私は 3D の点群を持っており、すべての点とそれぞれの最も近い点の間の距離の平均が必要です。これを行う最も簡単な方法は、すべてのポイントの最近傍を見つけ、その近傍からポイントまでの距離を計算し、それらの距離の合計をポイントの数で割ることです。ただし、これには多くの冗長性があり、近似がさらに高速に実行されるため、はるかに優れたアルゴリズムがあります。これらのより優れたアルゴリズムの無料の C/C++ 実装を探しています。

うまくいけばε近似。

非常にスパースなデータに対して、K最近傍アルゴリズムを実装しています。テストインスタンスとトレーニングセット内の各サンプルの間の距離を計算したいのですが、混乱しています。

トレーニングサンプルのほとんどの機能がテストインスタンスに存在しないか、その逆であるためです（機能がありません）。

この状況で距離を計算するにはどうすればよいですか？

画面にレンダリングしている詳細度の低い画像がいくつかあります。ビットマップをバッファとして使用しています。.net で (「最近隣」を使用して) ビットマップのサイズを変更する方法はありますか?

私は VB.net を使用しているので、すべての .net ソリューションが受け入れられます。

整数AとB（サイズが）A以下の2つのセットがあり、「どれくらい近いか」Bという質問に答えたいと思います。私がこの質問に答えたい方法は、inを見つけるために与えられたinからどれだけ遠くまで行かなければならないかの尺度を作成することです。 ABaAbB

私が作成したい特定のメジャーは次のことを行います。それぞれaについて、最も近いものを見つけます。b唯一のキャッチは、aをと一致させるbと、それを使用して他のを一致させるaことができなくなることです。（編集：私が実装しようとしているアルゴリズムは、常に短い一致を優先します。したがって、が複数に最も近い場合は、最も近いものを選択してください。複数が同じ距離にある場合はどうすればよいかわかりません。に、今私は前にあるものを選んでいますbabaababab、ただし、これは非常に恣意的であり、必ずしも最適ではありません。）最終製品であるこれらのセットを作成するための測定値は、縦軸にペアの数、x軸にペアの距離を示すヒストグラムです。

したがって、A = {1, 3, 4}との場合、B = {1, 5, 6, 7}次のa,bペアを取得します：1,1、、。これらのデータの場合、ヒストグラムには、距離が0のペア、距離が1のペア、距離が3のペアが表示されます。4,53,6

（これらのセットの実際のサイズには約100,000要素の上限があり、すでに低から高にソートされているディスクから読み込みます。整数の範囲は1から〜20,000,000です。編集：また、との要素AはB一意です。つまり、繰り返される要素。）

私が思いついた解決策は少し不格好に感じます。私はPerlを使用していますが、問題は多かれ少なかれ言語に依存しません。

1. まず、ハッシュを作成します。との和集合に表示される数値ごとに1つのキーと、各数値が、、、Aまたは両方にB表示されるかどうかを示す値を使用します。たとえば、数値5が両方のデータセットに表示される場合などです。（にのみ表示された場合は、があります。）AB$hash{5} = {a=>1, b=>1}A$hash{5} = {a=>1}

2. 次に、とにA表示されるすべてのハッシュ要素を繰り返して検索し、メジャーでそれらをマークして、ハッシュから削除します。AB

3. 次に、すべてのハッシュキーを並べ替えて、ハッシュの各要素がリンクリストのように最近傍を指すようにします。ここで、特定のハッシュ要素はのようになり$hash{6} = {b=>1, previous=>4, next=>8}ます。Aリンクリストは、次の要素と前の要素がにあるか、にあるかを認識していませんB。

4. 次に、で始まるペアの距離をループしd=1、距離のあるすべてのペアを見つけてdマークを付け、一致する要素がなくなるまでハッシュから削除しますA。

ループは次のようになります。

bこのループは明らかに、'sより後に表示される'sに一致するペアを優先しaます。後が前よりも優れているかどうかを判断するための賢明な方法があるかどうかはわかりません（ペアを近づけるという点で優れています）。私が興味を持っている主な最適化は処理時間です。

ボロノイ分割からk最近傍の集合を計算するのは比較的簡単です。逆の問題はどうですか？私はすでにk最近傍のセット（3D）を持っており、ボロノイセルの体積と中心を計算したいと思います。直感的には、それを行うO（n）アルゴリズムがあるはずですよね？

誰かがこのようなものがどこかに実装されているのを見たことがありますか？

前もって感謝します

PS：ボロノイセルにはk個を超えるエッジがないと思います（ポイントの位置に関するこの事前知識は、次元に関係なく、O（n）でダイアグラムを計算することを可能にするものです）。

PPS：さらに、特定の点について、ボロノイセルの頂点がkNNのセットに属していると仮定します（以下のコメントを参照）。

AとBの2つのセットがあります。これらのセットはN次元の点で構成され、順序付けられています（N <10）。BのAに​​最も近い部分を見つける必要があります。最も近い部分がB1であるとしましょう。B1のポイントの数はAと同じである必要があり、B1のすべてのポイントからAまでの距離の合計は最小である必要があります。

kdツリーを確認しました。セット内で最も近い点を見つけるのに役立つだけです。では、最も近い範囲をすばやく見つけるためのアルゴリズムはありますか？

ありがとう。

私はk最近傍分類アルゴリズムに完全に慣れていません。誰かがデータセットを提供する優れたチュートリアル/講義へのリンクを教えてください。そうすれば、k最近傍法を適用できます。

私は本当にこれを学ぶ必要がありますが、例が不足しているため、このタスクを非常に難しくしています。

ポイントの最も近い単一の近傍を求めて Kd ツリーをトラバースする関数の作成に成功しました。

ただし、この関数を切り替えて、単一の隣人ではなく K 最近隣人を見つけるようにしています。これは、私が最初に想像したよりもはるかに困難な作業であることが証明されており、助けが必要であることがわかりました...

kDツリーに関するウィキペディアの記事には、次のように書かれています。

このアルゴリズムは、単純な変更によっていくつかの方法で拡張できます。1 つだけではなく k 個の現在のベストを維持することにより、ポイントに k 最近傍を提供できます。ブランチは、k 個の現在のベストのいずれよりも近いポイントを持つことができない場合にのみ削除されます。

…が、初期の現在のベストを取得する方法については何も述べていません。最初の「ベスト」を見つけるのは簡単ですが、以前のベストを削除して最初からやり直すことなく、残りのk-currentベストを見つける方法がわかりません...これは基本的に、アルゴリズムが速いため、k 回 (私の場合は 17 回) 実行する必要があります。

17 の最初の「ベスト」のリストが入力されている場合、アルゴリズムは正しいポイントを見つけると思います。

これが曖昧な場合は申し訳ありません。コード サンプルが必要な場合は、喜んで提供します。この問題について簡単な説明があれば、おそらく投稿する必要はないので、最初は投稿しません。

前もって感謝します！