セットを保存して、類似のパターンをすばやく見つける方法

StackOverflow https://stackoverflow.com/questions/462563

質問

（これは宿題や仕事の問題ではありません。個人的な興味/職業であり、完全に架空のものです。しかし、良いアルゴリズムやデータ構造に興味があります。）

出会い系サイトを運営すると仮定しましょう。そして、私の 特別な機能 は、シングルが映画のテイストにマッチしたことです。 （なぜですか？）

その場合、各ユーザーの映画評価を保存する方法が必要になります。 （これまでのところ問題ありません。）そして、最適なユーザーを見つけるためにデータ構造が必要になります。 2つのテイストパターン間の距離は、両方のユーザーが作成したすべての評価間の平均距離になります。

例 

movies   A B C D E F G H I J K L M ...
user Xm  9 5   1   1   5
user Ym      4 6 1         8
user Zf  9   6 4           7

距離（X、Z）= avg（abs（9-9）+ abs（1-4））= 1.5

距離（Y、Z）= avg（abs（4-6）+ abs（6-4）+ abs（8-7））= 1.666

したがって、X氏は、Y氏よりもZ氏にやや良く適合しています。

次のような解決策が好きです...

  • ...データベースで多くの操作を行う必要はありません
  • ...大量のデータを処理する必要はありません
  • ...高速で実行
  • ...最適な一致を提供
  • わかりました、おそらく私も良い近似を検討します。

これは、数千の映画、20〜50の映画のみを評価するユーザー、数千のユーザーに対しても機能することに注意してください。

（これは精神的なパズルであり、実際の問題ではないため、回避策は実際には役立ちません。）

検索アルゴリズムまたはデータ構造はどうなりますか

役に立ちましたか？

解決

Netflix Prize チャレンジ、より具体的には最も人気のあるアプローチの前半によく似ています。あなたがしようとしていることの可能な実装は多数あり、さまざまです。それらのどれも非常に効率的ではなく、L1メトリックは信頼できる相関のための特に良いオプションではありません。

他のヒント

CREATE TABLE data (user INTEGER, movie INTEGER, rate INTEGER);

SELECT  other.user, AVG(ABS(d1.rate - d2.rate)) AS distance
FROM    data me, data other
WHERE   me.user = :user
    AND other.user <> me.user
    AND other.movie = me.movie
GROUP BY
    other.user
ORDER BY
    distance
n映画との比較はsqrt(n)であるため（<=>ペアごとにまとめられた映画）。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top