如何利用兴趣找到相似用户

Question

我正在尝试创建一个系统，该系统能够找到具有相似喜爱的电影/书籍/兴趣/等的用户，就像last.fm 上的邻居一样。具有最多共同兴趣的用户将具有最高的匹配度，并将显示在用户个人资料中（5 个最佳匹配左右）。

有没有相当快的方法来做到这一点？显而易见的解决方案是创建一个包含用户 id 和兴趣 id 的表，并将一个用户与所有其他用户进行比较，但这在一个表上需要很长时间......假设百万个用户每个都有 20 个兴趣。

我认为存在一些有效的解决方案，因为 last.fm 运行得很好。我更喜欢使用一些常见的 SQL 数据库，如 mySQL 或 pgSQL，但任何东西都可以。

感谢您的建议。

---

更新：
事实证明，最大的问题是在 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 个兴趣（10 000 个可能的兴趣）

Answer 1

您想要解决近似最近邻问题。将用户特征编码为某个空间中的向量，然后在该空间中找到近似最近的其他用户。

确切地说，您想要使用什么空间以及什么距离度量可能需要根据您的数据进行实验评估。幸运的是，您可以使用一个 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。