基于投票的用户相似性

Question

假设我有一组用户、一组歌曲，还有每首歌的投票记录：

=========== =========== =======
User        Song        Vote
=========== =========== =======
user1       song1       [score]
user1       song2       [score]
user1       song3       [score]
user2       song1       [score]
user2       song2       [score]
user2       song3       [score]
user3       song1       [score]
user3       song2       [score]
user3       song3       [score]
user-n      song-n      [score]
=========== =========== =======

那么，怎样才能最有效地计算用户之间的相似度，基于他们对歌曲的投票呢？有没有比对每个用户和每首歌的每个投票逐个比较更好的方法？

Answer 1

如果你想要最准确的结果，那就得把所有的东西都检查一遍。

不过，如果你的数据库很大，你可以选择做一个统计抽样，比如说随机选取1,000到10,000个用户来进行匹配。

另外，建议你在数据库里多加一些表格，存储结果，并且不需要每次都实时计算，而是定期更新一下，这样会更好。

Answer 2

我推荐一本书，叫做《编程集体智能》，作者是托比·塞加兰。书中的第三章讲了几种不同的聚类方法，比如层次聚类和K均值聚类。

书中示例的源代码可以在这里找到。

Answer 3

有两种常用的方法可以用来找出用户之间的相似性：

1. 欧几里得距离，这就是你想的那样：想象一个多维图表，每个轴代表一个被两个用户（u1 和 u2）评分的歌曲，轴上的值就是评分。你可以用下面的公式轻松计算相似性：

   对于每一首被 u1 和 u2 评分的歌曲，计算 pow(u1.song.score - u2.song.score, 2)，然后把所有的结果加起来，得到 sum_of_powers。相似性系数可以用 1 / (1 + (sqrt(sum_of_powers))) 来表示。

2. 皮尔逊相关系数：这是一个更好的方法，用来找出两个数据集之间的关系。这种方法使用了更复杂的公式和一些统计学的知识，详细信息可以查看这里：wiki。你会为每对用户绘制一个图表，然后根据评分来标记点。例如，如果 aSong 被 u1 评分为 2，而 u2 评分为 4，那么就会在图上标记点 (2,4)（假设 u1 在 x 轴，u2 在 y 轴）。

为了更清楚地说明，你会使用 线性回归 来找到两个系数 A 和 B，这两个系数描述了一条线，这条线能最小化图上所有点到它的距离。这条线的公式是：y = Ax + B。如果两个数据集相似，点应该靠近主对角线，这样 A 应该接近 1，而 B 应该接近 0。不要把这个解释当作完整的参考，因为它缺乏严谨性和典型的数学形式，只是给你一个大概念。

编辑：正如其他人所说，还有更复杂的数据聚类算法，比如 k-means，但我建议你从简单的开始（其实你只有在发现结果不够时，才需要更复杂的东西）。