1

我的平台是 Ruby——一个特别使用 Rails 3.2 的 webapp。

我正在尝试根据对象（人）对某些项目的评分来匹配对象（人）。人们可能会像其他人一样评价所有、部分或不评价相同的项目。评分是 0 到 5 之间的整数。可评分的项目数量和用户数量都可以被认为是重要的。

一个简单的例子 -

数据说明

蛮力方法是遍历所有人，计算每个项目的差异。在 Ruby 风格的伪代码中 -

MATCHES = {}
for each (PERSON in (people except USER)) do
  for each (RATING that PERSON has made) do
    if (USER has rated the item that RATING refers to) do
      MATCHES[PERSON's id] += difference between PERSON's rating and USER's rating
    end
  end
end
lowest values in MATCHES are the best matches for USER

这里的问题是，随着项目、评分和人数的增加，这段代码将需要很长时间才能运行，并且暂时忽略缓存，这是必须运行很多的代码，因为这种匹配是主要的我的应用程序的功能。

我对更聪明的算法和更聪明的数据库持开放态度来实现这一点，但是通过算法来实现它并因此允许我将所有内容保存在 MySQL 或 PostgreSQL 中会让我的生活更轻松。我唯一要说的是数据确实需要持久化。

如果任何更多细节会有所帮助，请随时询问。非常感谢任何帮助！

4

3 回答 3

1

查看KD-Tree。它专门用于加快 N 维空间中的邻居查找速度，例如您的评级系统（第 1 个人是沿 X 轴的 3 个单位，沿 Y 轴的 4 个单位，依此类推）。

您可能必须使用实际的编程语言来执行此操作。一些数据库有空间索引，但它们通常是为地理工作而设计的，比如PostGIS（它使用GiST索引），并且只支持两个或三个维度。

也就是说，我确实在 PostGIS 上找到了这篇诱人的博客文章。然后我找不到任何其他参考，但也许你的运气会比我的好......

希望有帮助！

于 2013-02-13T22:20:58.790 回答
0

从技术上讲，您的任务是匹配由 5 个字母组成的长字符串。这种东西在计算生物学领域得到了广泛的研究。（通常使用 4 个字母）。如果您不知道这本书http://www.amazon.com/Algorithms-Strings-Trees-Sequences-Computational/dp/0521585198，那么您可能想要获取一份副本。恕我直言，这是关于序列模糊匹配/评分的标准书。

于 2013-02-13T22:16:09.257 回答
0

你的数据稀疏吗？通过评分，大多数时候并不是每个用户都会对每个对象进行评分。

天真地比较每个对象是O(n*n*d)，其中d是操作数。然而，所有 Hadoop 解决方案的一个关键技巧是转置矩阵，并且只处理列中的非零值。假设您的稀疏性是s=0.01，这会将运行时间减少到O(d*n*s*n*s)，即s*s. 因此，如果你的稀疏度是 100 分之一，那么理论上你的计算速度会快 10000 倍。

请注意，结果数据仍然是O(n*n)距离矩阵，所以严格来说问题仍然是二次的。

击败二次因子的方法是使用索引结构。已经提到了 kd-tree，但我不知道分类/离散数据和缺失值的版本。AFAICT 对此类数据的索引没有得到很好的研究。

于 2013-02-14T07:11:32.770 回答