問題タブ [similarity]

last.fmの近所の人と同じように、似たようなお気に入りの映画/本/興味などを持つユーザーを見つけることができるシステムを作成しようとしています。最も相互利益を共有しているユーザーは、最も一致度が高く、ユーザープロファイルに表示されます（5つ程度の最適一致）。

これを行うための合理的に速い方法はありますか？明らかな解決策は、ユーザーIDとインタレストIDを使用してテーブルを作成し、ユーザーを他のすべてのユーザーと比較することですが、それは、それぞれ20のインタレストを持つ100万人のユーザーがいるテーブルでは永遠にかかります。

last.fmは非常にうまく機能しているので、いくつかの効率的な解決策が存在すると思います。mySQLやpgSQLなどの一般的なSQLデータベースを使用することをお勧めしますが、何でもかまいません。

あなたの提案をありがとう。

更新：結局のところ
、最大の問題はSQLデータベースで最も近いネイバーを見つけることです。オープンソースのものはどれもこの種の検索をサポートしていないからです。
したがって、私の解決策は、サービスとして実行するようにANNを変更し、PHPからクエリを実行することです（たとえば、ソケットを使用）。たとえば、メモリに7次元のユーザーが何百万人もいることはそれほど大きな問題ではなく、信じられないほど高速に実行されます。

小さなデータセットの別の解決策は、この単純なクエリです。

20〜50ミリ秒、10万人のユーザーがそれぞれ平均で約20の関心（10000の可能な関心のうち）を持っている

類似のテキストにインデックスを付けるための一種のハッシュ関数を探しています。したがって、たとえば、「A」と「B」という2つの非常に長いテキストがあり、AとBの差がそれほど大きくない場合、AとBに適用されるハッシュ関数（Hと呼ばれる）は同じ数値を返す必要があります。

したがって、H（A）= H（B）ここで、AとBは類似したテキストです。

「DoubleMetaphone」（イタリア語のテキストを使用）を試しましたが、文字列のプレフィックスに非常に強く依存していることがわかりました。例えば：

A="これは私がハッシュしたい非常に長いテキストです"B="これは非常に"

==> doubleMetaPhone（A）= doubleMetaPhone（B）

そして、これは私にとってあまり良くありません。同じプレフィックスを持つ文字列は類似していると比較される可能性があり、私はこれを望まないからです。

誰かが私に他の方法を提案できますか？

すでに TF-IDF が計算されているドキュメントの大規模なコレクションがあります。コレクションにさらにドキュメントを追加する準備をしています。データベース全体を再処理せずに新しいドキュメントに TF-IDF スコアを追加する方法があるかどうか疑問に思っています。

matlab で類似検索を実装したいと考えています。私はそれが可能か知りたいですか？

私の計画は、ユークリッド距離と動的時間ワーピングという 2 つの一般的な類似性測定を使用することです。これらは両方とも時系列データセットに適用されます。この時点での私の質問は、これら 2 つの測定性能と精度の両方をどのように評価できるかということです。K-NNアルゴリズムを使用する必要があるという文献を見ました。

次に、時系列データセットに次元削減を適用する予定です。データセットの次元を減らした後。R ツリーまたは利用可能なインデックス作成手法を使用して、データセットにインデックスを付ける必要があります。

しかし、私の問題は、これを行うには、インターネットでほとんど見つけることができないRツリーのmatlabコードが必要なことです...

類似性検索の実装のほとんどは C++、C、および Java で行われていることに気付きました...しかし、私はそれらに慣れていません。私はMatlabでこれらを実装できることを望んでいます...どの教祖もこれで私を助けることができますか?

また、各アルゴリズムのパフォーマンスを評価するには、どのような評価を行うことができますか。

ありがとう

類似性順に並べられたレコードをクエリするにはどうすればよいですか？

例えば。「StockOverflow」を検索すると

1. スタックオーバーフロー
2. SharePointオーバーフロー
3. 数学のオーバーフロー
4. 政治的オーバーフロー
5. VFXオーバーフロー

例えば。「LO」を検索すると、次のようになります。

1. パブロ・ピカソ
2. ミケランジェロ
3. ジャクソン・ポロック

助けが必要なもの：

1. より良い結果を得るために、検索エンジンを使用してMySQLテーブルにインデックスを付けて検索する

   • PHPでSphinx検索エンジンを使用する

   • PHPでLuceneエンジンを使用する

2. フルテキストインデックスを使用して、類似した/含まれている文字列を検索する

うまくいかないもの

• レーベンシュタイン距離は非常に不安定です。（UDF、Query）
  「犬」を検索すると次のようになります。
  1. 犬
  2. ボグ
  3. 前
  4. 大きい
  5. エコー
• LIKEより良い結果を返しますが、同様の文字列が存在するにもかかわらず、長いクエリに対しては何も返しません
  1. 犬
  2. dogid
  3. ドガラル
  4. ドグマ

入力データを userid,itemid 形式で指定すると、次のようになります。

各グループ内の項目のすべての組み合わせ (順序は重要ではありません) を生成したいと思います。最終的には、グループ内のアイテムに対してジャカードの類似性を実行するつもりです。

理想的には、バイグラムが生成され、出力を次のようにフラット化します。

ユーザー ID を表す文字 ABC は、出力に実際には必要ありません。説明のために表示しているだけです。そこから、ジャカードを計算するために各バイグラムの出現回数を数えます。他の誰かが同様の類似度計算に pig を使用しているかどうかを知りたいです（申し訳ありません！）、すでにこれに遭遇しました。

豚のチュートリアルで提供されている NGramGenerator を見てきましたが、私が達成しようとしているものと実際には一致しません。おそらく Python ストリーミング UDF が適しているかどうか疑問に思っています。

コールド リードをクライアントのデータベースと照合する必要があります。

見込み客はサード パーティ プロバイダーから大量に (数千件のレコード) 寄せられており、営業担当者は (彼らの言葉で) 「クライアントを除外する」ように私たちに求めています。

明らかに、リードにスペルミスがあります。Charles は Charlie になり、Joseph は Joe になります。したがって、lead_first_name と client_first_name を比較するだけのフィルターを実行することはできません。

ある種の文字列類似メカニズムを使用する必要があります。

現在、素敵なdifflibを使用して、リードの名字と姓を で生成されたリストと比較していClient.objects.all()ます。動作しますが、クライアントの数が多いため遅くなる傾向があります。

私は、ほとんどの SQL データベースに soundex と difference 関数があることを知っています。以下の更新で私のテストを参照してください-それはdifflibほどうまく機能しません。

別の解決策はありますか？より良い解決策はありますか？

編集：

少なくとも私のデータベースでは、Soundex は difflib ほどうまく動作しません。

以下は簡単なテストです。「Joseph Lopes」を含むテーブルで「Joe Lopes」を探します。

上記は、"Joe Satriani" を唯一の一致として返します。類似性のしきい値を 2 に減らしても、"Joseph Lopes" は潜在的な一致として返されません。

しかし、difflib の方がはるかに優れています。

gruszczy の応答後に編集します。

独自の情報を作成する前に、すべての知識のリポジトリでレーベンシュタイン距離の T-SQL 実装を探して見つけました。

テストでは、まだ difflib よりも優れたマッチング ジョブを実行しません。

これにより、difflib の背後にあるアルゴリズムを調査することになりました。Ratcliff-Obershelpアルゴリズムの修正版のようです。

残念ながら、difflib に基づいて T-SQL の実装を既に作成している他の親切な魂を見つけることができないようです... できるときに試してみます。

今後数日以内に誰もより良い答えを思いつかない場合は、gruszczy に許可します。ありがとう、親切な先生。

誰かがASCII文字に似ているUnicodeの文字を見つける簡単な方法を知っていますか。例として、「キリル文字の小さな文字DZE（ѕ）」があります。似たような文字を検索して置き換えたいのですが。同様に、私は人間が読める形式を意味します。見ても違いはわかりません。

一方の文書が他方の文書に含まれている場合に、2 つのテキスト文書が類似しているかどうかを調べるアルゴリズムを探しています。

よろしくお願いします。

「悪い」ハッシュ関数を探しています。文字列をハッシュして、同様の文字列を 1 つのバケットに入れたいと考えています。

研究をどこから始めればよいかヒントをいただけますか? いくつかのメソッドまたはアルゴリズム名...