0

（这不是作业，也不是工作问题。这只是我个人的兴趣/职业，完全是虚构的。但我对好的算法或数据结构感兴趣。）

假设，我会经营一个约会网站。而我的特点是单曲与电影品味相匹配。（为什么不？）

在这种情况下，我需要一种方法来存储每个用户的电影评分。（到目前为止没问题。）我需要一个数据结构来找到最合适的用户。两种口味模式之间的距离将是两个用户做出的所有评分之间的平均距离。

例子

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 部电影评分的用户以及数以千计的用户。

（因为这是一个心理难题，而不是真正的问题，所以工作场所并没有真正的帮助。）

你的搜索算法或数据结构是什么？

4

3 回答 3

3

看起来您正在寻找电影空间中最近的邻居。你的距离函数是L1 度量。您可能可以使用某种空间索引。也许您可以使用协同过滤中的技术。

于 2009-01-20T19:04:02.103 回答
3

听起来很像Netflix Prize挑战赛，更具体地说是最受欢迎的方法的前半部分。您尝试做的事情的可能实现是多种多样的。它们都不是特别有效，并且 L1 度量对于可靠的相关性来说并不是一个特别好的选择。

于 2009-01-20T20:18:51.047 回答
0 
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

复杂度将是 O(n 1.5 )) 而不是 O(n 2 )，因为将与电影进行n比较sqrt(n)（每对填充在一起的电影的平均值）。

于 2009-01-20T18:58:05.857 回答