4

我正在尝试创建一个系统，该系统能够找到具有类似喜爱的电影/书籍/兴趣/等的用户，就像 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 个可能的兴趣）

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 回答