4

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

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

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

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

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

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

SELECT b.user_id, COUNT(1) AS mutual_interests
FROM `users_interests` a JOIN `users_interests` b ON (a.interest_id = b.interest_id)
WHERE a.user_id = 5 AND b.user_id != 5
GROUP BY b.user_id ORDER BY mutual_interests DESC, b.user_id ASC

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

4

1 に答える 1

0

おおよその最近傍問題を解きたいとします。ユーザーの特性をある空間でベクトルとしてエンコードし、その空間で最も近い他のユーザーをほぼ見つけます。

正確にどの空間、どの距離メトリックを使用するかは、おそらくデータに基づいて実験的に評価するものです。幸いなことに、ニーズに合わせてさまざまなメトリックとアルゴリズムでこの問題を解決するために使用できる C++ パッケージがあります: http://www.cs.umd.edu/~mount/ANN/

編集：ここでの実行時間は機能の数に依存するというのは本当です。しかし、高次元幾何学には便利な定理があり、任意の高次元に n 個の点があり、おおよその距離だけを気にする場合、それらを損失なしで O(log n) 次元に投影できるというものです。こちらを参照してください ( http://en.wikipedia.org/wiki/Johnson-Lindenstrauss_lemma )。(ランダムな投影は、ポイントにランダムな +1/-1 値の行列を掛けることによって実行されます)。たとえば、log(1,000,000) = 6 であることに注意してください。

于 2010-07-11T19:53:35.577 に答える