問題タブ [nearest-neighbor]

都市情報と対応する緯度と経度、および都市に関連する他の多くの情報を含むテーブル (DB2 データベース) があります。私の要件は次のとおりです。

アプリケーションへの入力は緯度と経度であり、DB に保存されている正確な緯度と経度ではない場合があります。入力された緯度と経度を使用して、テーブルから最も近い都市情報を見つける必要があります。どんな助けでも大歓迎です。

これに利用できるJavaまたはSQLでこれを処理するための最近傍実装はありますか

K-nearest-neighbors アルゴリズムを実行して画像を分類したい場合、画像から特徴をどのように抽出するのでしょうか? 最も簡単で効果的な方法は何ですか?

KD ツリーは最近傍検索に最適であると常に宣伝されています。ただし、データ セットがすべて離散値であり、実際の距離メトリックがない場合でも、それらは効率的でしょうか?

たとえば、属性が[black, blue, red], [bread, milk, cheese], [right, left, straight, curved]連続性がなく、距離を測定する唯一の方法がハミング距離のようなものである場合 (テスト例と同等の数を確認します)。これらのシナリオでも KD ツリーは有効に機能しますか? どうして？

KDツリーのウィキペディアページを見ています。例として、リストされているkdツリーを構築するためのアルゴリズムをPythonで実装しました。

ただし、KDツリーを使用してKNN検索を実行するためのアルゴリズムは言語を切り替え、完全には明確ではありません。英語の説明は意味をなし始めますが、その一部（他のリーフノードをチェックするために「再帰をほどく」領域など）は、私には実際には意味がありません。

これはどのように機能し、PythonでKDツリーを使用してKNN検索を実行するにはどうすればよいですか？これは"send me the code!"タイプの質問を意味するものではなく、私はそれを期待していません。簡単な説明をお願いします:)

次の形式のデータセットがあります。

日時 | 緯度 | 経度 | 身長 | 温度

これらのデータは、さまざまな空間と時間での大気温度測定値に基づいてユーザーが入力できます。空間は緯度、経度、高さで表されます。このデータ セットから、任意の空間と時間での温度を次のように取得する必要があります。補間.そのようなシナリオでどのようなデータ構造を使用する必要があるかわかりません.Kd-treeについて読みましたが、それはオプションですか?

2次元平面上に特定の位置と半径を持つ一連の円があります。すべての円について、他の円と交差しているかどうか、および 2 つを分離するために必要な距離を判断したいと考えています。私の現在の実装では、考えられるすべての円の組み合わせを調べてから計算を行います。残念ながら、このアルゴリズムは O(n^2) であり、低速です。

円は通常、グループにまとめられ、半径は似ていますが異なります。円の数のおおよその最大値は約 200 です。アルゴリズムは正確である必要はありませんが、それに近い必要があります。

これは私が現在 JavaScript で持っている (遅い) 実装です:

また、よいアルゴリズム(KD Tree?)を分かりやすい英語で説明していただけるとありがたいです:-/

クォータニオン値が与えられた場合、一連のクォータニオンで最も近いものを見つけたいと思います。これを行うには、2 つの四元数間の「距離」を比較する方法が明らかに必要です。このような比較にはどのような距離表現が必要で、どのように計算されますか?

ありがとう、

ジョシュ

一連のポイントの中から「近くの」隣人を見つける必要があります。

上の画像には10個のポイントがあります。赤い線はドロネー三角形分割からのエッジであり、黒い星はエッジの正中線を示し、青い線はボロノイテッセレーションです。ポイント1には、3つの「近い」ネイバー、つまり4、6、および7がありますが、2と3はありません。これらは、エッジ1〜7とほぼ一致していますが、はるかに離れています。

近くの隣人（または「良い」エッジ）を識別するための良い方法は何ですか？図を見ると、中点がボロノイ線との交点に当たるエッジを選択するか、ボロノイセルに接触しているエッジを「近く」と見なすのが良い解決策であると思われます（3〜5の分類）。どちらにでも行くことができます）。Matlabでいずれかのソリューションを実装する効率的な方法はありますか（Matlabに変換できる優れた一般的なアルゴリズムを入手できれば幸いです）？

そこで、マイケル・ラビンによるアルゴリズムの詳細を見つけようとしています。このアルゴリズムは、O（n）時間で2Dの点のセットが与えられた場合に最近傍を見つけます。何らかの理由で、グーグル検索は完全に私を失敗させています。私が見つけた最高の（そして唯一の）説明はここにあります：http：//rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/。

誰かがこれについて何か知っているか、主題に関する本や論文をどこで見つけるかを知っているなら（できればオンラインで！）、私はあなたが量り込んでくれて本当に感謝しています。

カバー ツリーを使用して K-Nearest-Neighbors を実行する方法を知っていると思います。(ちなみに、これの実行時の複雑さの分析を教えてくれる人はいますか?)、しかし、私はすべてのkNNを探しています (つまり、ツリー内のすべてのポイントの kNN を見つけます)。