問題タブ [nearest-neighbor]

私はPostgresとSQLを初めて使用します。ある点から最も近い線上の投影された点に線を引く次のスクリプトを作成しました。同じ行数の5〜10ポイントの小さなデータセットで正常に機能します。ただし、2,000行の60ポイントで実行すると、クエリには約12時間かかります。これは、 http：//www.bostongis.com/downloads/pgis_nn.txtからも下に貼り付けられた最近傍関数に基づいています

pgis_fn_nnの編集ドキュメントはhttp://www.bostongis.com/PrinterFriendly.aspx?content_name=postgis_nearest_neighbor_genericで入手できます。

遅い部分はpgis_fn_nn（...）の実装です

1. 私は何が間違っているのですか？
2. これを高速化するためのヒントはありますか？
3. 両方のスクリプトを改善する方法はありますか？
4. 両方のクエリを1つにまとめたい場合、何をお勧めしますか？

my_script.sql

http://www.bostongis.com/downloads/pgis_nn.txtのpgis_fn_nn

最近隣内挿アルゴリズムを使用して、入力画像をスケールアップするための独自の関数を作成しようとしています。悪い部分は、それがどのように機能するかを見ることができますが、アルゴリズム自体を見つけることができないことです。どんな助けにも感謝します。

これが、入力画像を2倍に拡大するために試したものです。

これがマークの提案後の出力です

中央値選択アルゴリズムの中央値を使用して、O(n) の中央値を見つけることができます。また、アルゴリズムが完了した後、中央値の左側にあるすべての要素は中央値よりも小さく、右側にあるすべての要素は中央値よりも大きいことがわかっています。しかし、O(n) 時間で中央値に最も近い k 個を見つけるにはどうすればよいでしょうか?

中央値が n の場合、左側の数値は n 未満であり、右側の数値は n より大きいです。ただし、配列は左側または右側でソートされません。数値は、ユーザーが指定した個別の数値の任意のセットです。

問題は、Cormen によるアルゴリズムの紹介、問題 9.3-7 からのものです。

kd treesのウィキペディアのエントリでは、kd ツリーで最近傍検索を行うためのアルゴリズムが提示されています。私が理解していないのは、ステップ 3.2 の説明です。検索ポイントと現在のノードの分割座標の差が、検索ポイントの分割座標と現在のベストの差よりも大きいという理由だけで、より近いポイントがないことをどのように知ることができますか?

最近傍探索 2D の KD ツリーを使用した NN 探索のアニメーション

Nearest Neighbor (NN) アルゴリズムは、特定の入力ポイントに最も近いツリー内のポイントを見つけることを目的としています。この検索は、ツリー プロパティを使用して検索スペースの大部分をすばやく除外することで効率的に実行できます。kd ツリー内の最近傍の検索は、次のように進みます。

1. ルート ノードから始めて、検索ポイントが挿入された場合と同じ方法で、アルゴリズムは再帰的にツリーを下に移動します (つまり、ポイントが現在のノードよりも大きいか小さいかに応じて、右または左に移動します)。次元を分割します)。
2. アルゴリズムがリーフ ノードに到達すると、そのノード ポイントを「現在のベスト」として保存します。
3. アルゴリズムは、ツリーの再帰を巻き戻し、各ノードで次の手順を実行します。 1. 現在のノードが現在のベストよりも近い場合、それが現在のベストになります。2. アルゴリズムは、分割面の反対側に、現在の最適なポイントよりも検索ポイントに近いポイントがあるかどうかを確認します。概念的には、これは、現在の最も近い距離に等しい半径を持つ検索ポイントの周りの超球と分割超平面を交差させることによって行われます。超平面はすべて軸が揃っているため、これは単純な比較として実装され、検索ポイントと現在のノードの分割座標の差が、検索ポイントから現在のベストまでの距離 (全体の座標) より小さいかどうかを確認します。1. 超球が平面を横切る場合、平面の反対側により近い点がある可能性があるため、アルゴリズムは現在のノードからツリーの他のブランチを下に移動して、より近い点を探し、検索全体と同じ再帰プロセスに従います。 . 2. 超球が分割面と交差しない場合、アルゴリズムはツリーを上っていき、そのノードの反対側のブランチ全体が削除されます。
4. アルゴリズムがルート ノードのこのプロセスを終了すると、検索が完了します。

通常、このアルゴリズムでは、平方根の計算を避けるために、比較に二乗距離が使用されます。さらに、現在の最適距離の 2 乗を変数に保持して比較することで、計算を節約できます。

「x が好きで、y も好きな人」タイプのレコメンデーション システムの構築を検討しており、Vogoo の使用を検討していましたが、コードを調べたところ、評価に基づいて最近傍がたくさんあるようです。

ここ数週間、ほとんどの人がまったく評価しないか、5 と評価しているという記事をいくつか見ましたhttp://youtube-global.blogspot.com/2009/09/five-stars-dominate- rating.html

私は現在、レーティング システムを実装していません。また、適用されるすべてのレーティングが変動しないのであれば、実装する必要もないと思います。

これは、KNN はあまり価値がないということですか?

過去の視聴履歴に基づいて類似のレコメンデーションを取得するシステム (パッシブ フィルタリング) を開発するための推奨事項はありますか?

私が扱っているデータはイベントベースなので、男子ダブルステニス、ブルージェイズ野球、大学女子バスケットボールなどを見たことがあるなら、他の人が見たあなたの地域で現在開催されている他のイベントをお勧めします.システム全体で同様のイベントも見ています。

私は主に PHP を使用していますが、Python を学び始めています (それが役立つ場合は、おそらく Java を学ぶ必要があります)。

最も近い隣人を見つけるためのアルゴリズムの 1 つにSpace Partitioningがあります。それはどのように機能しますか？

点 (x 座標と y 座標) の 2D セットがあり、点 (a,b) が与えられているとします。このアルゴリズムはどのようにして最近傍を見つけますか?

補間なしの私のプレーンコード：

このコードはブラックスポットを作成します、問題は補間を行う方法ですか？イルミネーションありがとうございます。PS組み込み関数を要求しない：imrotate（im1,1 / thet、'nearest'）;

これはCにあります。

同じ空間をサンプリングする 2 つの 2D 配列 ArrayA と ArrayB があります。B は ArrayA とは異なる属性をサンプリングする頻度が ArrayA よりも低いため、A よりも小さくなります。

いくつかの変数を定義してみます。

ArrayA と ArrayB は、配列の先頭へのポインタです。最初に X の行が格納され、次に Y がインクリメントされ、X の次の行が格納されます (Y=1)。

そのため、指定された indexA から indexB を設定して、indexA の値に関連付ける最近傍サンプルにする必要があります。

ここに私がいます (エラーがあれば修正してください! インデックス 0 から開始していることに注意してください): indexA = 0 posB 0,0; インデックスB = 0

posA 8,0; indexA = 8 (最初の行の終わり) posB 2,0; インデックス B = 2

posA 0,1; indexA = 9 posB 0,0; indexB = 0 (まだ底点に近い)

posA 0,3; indexA = 27 posB 0,1; インデックスB = 3

posA 8,8; indexA = 80 (最後のポイント) posB 2,2; インデックス B = 8

これまでのところ、indexA = posAX + (posAY * SizeAX) があります。

私が試したこと (そしてもちろん失敗しました): indexB = (int) (indexA * (SizeBX * SizeBY / (SizeAX * SizeAY)) + 0.5) // 最初の行と最後の値に対してのみ機能するように見えます..しかしこれは明らかに機能しません - しかし、2つをどのように正確にマッピングするかについては興味がありますが、修正後に調べます..

posAY や posAX にはアクセスできず、indexA だけでしたが、mod と剰余を使用して分解できるはずですよね? または、より効率的なより高速な方法はありますか？あ

私もこれを試しました：

indexB = (posAY * SizeBY / SizeAY) * SizeBY + (posAX * SizeBX / SizeAX)

問題は、X インデックスと Y インデックスを別々に丸め、その後 SizeBX と SizeBY を使用する必要があることだと思いますか?

追加の注意点として、ArrayA と ArrayB は、どちらもより大きな空間をサンプリングするより大きなデータ セットから取得されます。四角形は任意であるため、ArrayA または ArrayB のいずれかが四角形の境界に最も近い点を持つ可能性があり、最も近い隣人が実際にグラブしている方法に関する他の問題につながります。これに対処する方法についてもわかりません。

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

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

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

使用例: クライアント A が販売情報を要求しに来て、郵便番号を入力すると、担当者 X に誘導されます。

事実上無数の郵便番号があるため、すべての郵便番号にエージェントが割り当てられるわけではなく、郡レベルに移動し、郡の地域に移動し、最終的に州レベルで終了します。

このシナリオをモデル化するには、どのタイプの関係が最適ですか?

担当者が割り当てられた最も近い郡に郵便番号を近似できる地域を具体的に定義する必要性をなくす方法はありますか?もしそうなら、完全な地理位置情報を調べて距離比較を行って最も近い代表を見つけるか、またはおそらく、郵便番号自体を使用して距離を近似することはできますか?

明確化: この質問の本当の意図は、郡と地域の完全な関連付けテーブルを維持する必要なく、地域の近似をどのように解決するか、またはこの問題の解決策が非常に複雑であるため、手動で関係を維持するコストがそれほど高くないということですか?