問題タブ [nearest-neighbor]

特徴記述子 [SIFT、SURF など] を使用する場合 - 近似最近傍は画像間のマッチングを行うための最速の方法ですか?

本当の質問があります。

次のようなスキーマを持つデータベースがあります。

アイテム

• ID
• 説明
• その他ジャンク

鬼ごっこ

• ID
• 名前

item2tag

• item_id
• tag_id
• カウント

基本的に、各アイテムはさまざまな数で最大 10 個のアイテムとしてタグ付けされます。50,000 個のアイテムと 50,000 個のタグがあり、items2tag には約 500,000 個のエントリがあります。1 つのアイテムを指定して、「最も類似した」アイテムを見つけたいと思います。

「最も似ている」とは、タグの組み合わせが最も似ているアイテムを意味します...何かが「面白い」の2倍「クール」である場合、他のすべてのものをほぼ2倍「クール」で見つけたいと思います彼らが「面白い」限り。もちろん、これは 2 つだけでなく 10 個のタグにも適用されます。

何か案は？

ここ数日、遺伝的アルゴリズムを使用した TS ソリューションを紹介しているいくつかのWeb サイトに注目しました。

TSP 問題で、最も短いツアーを生成するアプローチはどれですか?最近傍または遺伝的アルゴリズム?

次の状況を処理するための効率的な SQL クエリを考え出すのに問題があります。

2 つの列を持つテーブルがあるとします。

テーブルが巨大です (数百万行)。「groupId」ごとにさまざまな量の「値」があります。たとえば、100 から 50.000 の間です。すべての float 値は 0 以上ですが、それ以外は無制限です。

特定の groupId に対して、クエリは類似度の降順で並べ替えられた他のすべてのグループを返す必要があります。「類似」は、2 つのグループ内の 30 個の値のすべての可能なペア間の最小ユークリッド距離として定義されます。

類似性のその定義は、私を殺すものです。上記で定義された類似度を計算するには、単純なアルゴリズムは O(n^2) であると思います。現在、「類似性」を再定義するか、上記を効率的に実装するためのアイデアを探しています。PostGis 幾何学的最近傍または最大共通サブシーケンス アルゴリズムのような k 最近傍を含むソリューションを想像できます (ただし、後者の「ファジー」実装が必要なのは、「値」が完全に等しいことはほとんどないためです)。 .

問題が発生した場合に備えて、現在mySQLを使用しています。

乾杯、

Googleニュースに似ていますが、基本的なトピックが何であるかを判断し、次にどのトピックが関連しているかを判断できるという意味で異なる2つのニュースアイテムのコンテンツの類似性を判断したいと思います。

したがって、記事がサダム・​​フセインに関するものである場合、アルゴリズムは、ドナルド・ラムズフェルドのイラクでの商取引に関する何かを推奨する可能性があります。

k最近傍法のようなキーワードとそれらが機能する理由についての少しの説明を投げかけることができれば（可能であれば）、残りの調査を行い、アルゴリズムを微調整します。誰かが以前に似たようなことを試みたに違いないことを私は知っているので、始める場所を探しているだけです。

SCVT (Spherical Centroidal Voronoi Tesselation) を実装するプログラムを書いています。単位球上に分布する点のセットから始めます (ランダム点または等面積スパイラルのオプションがあります)。数百からおそらく 64K ポイントがあります。

次に、おそらく数百万のランダムなサンプル ポイントを生成する必要があります。各サンプルについて、セット内の最も近いポイントを見つけ、それを使用してそのポイントの「重み」を計算します。(この重みは、別の球面セットから検索する必要がある場合がありますが、そのセットは、アルゴリズムの任意の実行に対して静的なままです。)

次に、元のポイントを計算されたポイントに移動し、プロセスをおそらく 10 回または 20 回繰り返します。これにより、後で使用するボロノイ タイルの中心が得られます。

後で、ユーザーがクリックしたタイルを確認するために、特定のポイントの最近傍を見つける必要があります。これは上記の問題の中で自明に解決され、とにかく超高速である必要はありません。私が効率的である必要があるのは、単位球上の何百万もの最近傍です。ポインタはありますか？

ああ、私は x、y、z 座標を使用していますが、それは決まったものではありません。物事を単純化するように見えます。私も C を使用していますが、これは C に最も慣れているためですが、その選択にも執着していません。:)

サンプル ポイントにスパイラル パターンを使用することを検討しました。これにより、次の検索の良い出発点として、少なくとも最後に見つかったポイントの近傍が得られるからです。しかし、そうすると、どんなツリー検索も役に立たなくなりそうです。

編集：[申し訳ありませんが、タイトルとタグで明確だと思っていました。ランダムポイントを簡単に生成できます。問題は最近傍探索です。すべての点が単位球上にある場合の効率的なアルゴリズムは?]

データベースがあり、単一のクエリを使用して、ID順に並べられた前と次のレコードを検索したいと思います。ユニオンをしようとしましたが、うまくいきません。:(

何か案は？どうもありがとう。

あるデータベースから別のデータベースに大量のデータをダンプするメンテナンス スクリプトがあります。

私はデータを取得しようとしています

現在の行のランク 2 で取得しようとしているのは、ランク 1 が null でない最も近いランク 2 です。ランク1がランク2の効果的な代替品であると仮定しています

だから、私は2つの問題があると思います。

1. ネストされたselectステートメントで使用するrank2があるとは思わない
2. 「現在に最も近づく」と言う方法がわかりませんrank2<rank2。

ランク 1 の値は 0 ～ 20,000 の範囲で、ランク 2 の範囲は 0 ～ 150,000 です (なぜそれが重要なのかわかりません)。ランク間に効果的な相関関係はありません。

ランク 1 は常により信頼性の高い数値ですが、多くの場合 null であるため、このタイプの代替品で注文をごまかそうとしています。

例として使用するサンプル データを次に示します。

2、5、4、6、7、3、1、8、9、10の注文を取り戻したいと思っています。またはそれに近いもの。基本的に、ランク2にnullがある場合、最も近いランク1の最も近いランク2を取得します。

これが「完璧」であるとは思いませんが、ランク1でソートするよりはましです。

これは、私が PostGIS メーリング リストに送信した電子メールからのクロス ポストです。

これまでのところ、点と線上の投影位置との間に線を作成する試みは長かったですが、ほぼそこに到達しました。昨日の時点で、最近傍分析を含める前に、次の画像に示す結果を得ました。

ご覧のとおり、ピンクの各ポイントは投影されたすべてのポイントに接続していますが、ピンクの各 x をそれぞれの投影に接続したいだけです。

IRC では、BostonGIS の最近傍法を使用するように勧められました。関数を PostgreSQL に入力し、以下に概説するように失敗しました。エラーの原因は、パラメーターの型が間違っているためだと思います。私はそれをいじって、いくつかの列の型を varchar に変更しましたが、それでも動作しません。

私が間違っていることについてのアイデアはありますか? それを修正する方法に関する提案はありますか？

コード：

エラー

KD ツリーを使用してポイントを保存し、別の特定のポイントに近いポイントの一部をすばやく反復処理できることを知っています。ラインに似たようなものがあるのだろうかと思っています。

3Dの一連の行 L (そのデータ構造に格納される) と別の「クエリ行」q が与えられた場合、q に「十分に近い」L 内のすべての行をすばやく反復できるようにしたいと考えています。私が使用しようとしている距離は、2 つの点 u と v の間の最小ユークリッド距離です。ここで、u は最初の線上のある点で、v は 2 番目の線上のある点です。その距離を計算することは問題ではありません (外積に関する優れたトリックがあります)。

たぶん、皆さんは良いアイデアを持っているか、論文や説明などを探す場所を知っているでしょう...

TIA、s。