我正在寻找为我正在开发的网站上的用户生成“邻居”（具有相似品味的人）的技术；类似于 last.fm 的工作方式。
目前，我有一个可以发挥作用的用户兼容功能。它根据 1) 对相似项目的评分 2) 对项目的相似评分对用户进行排名。该函数的权重为第 2 点，如果我在生成“邻居”时仅使用这些因素之一，这将是最重要的。
我的一个想法是只计算每个用户组合的兼容性，并选择评价最高的用户作为用户的邻居。这样做的缺点是随着用户数量的增加，这个过程可能需要很长时间。对于仅 1000 个用户，它需要 1000C2 (0.5 * 1000 * 999 = = 499 500) 次调用兼容性功能，这对服务器来说也可能非常繁重。
所以我正在寻找关于如何最好地实现这样的系统的任何建议、文章链接等。
在《编程集体智能》一书中
http://oreilly.com/catalog/9780596529321
第 2 章“做出推荐”很好地概述了根据用户之间的相似性向人们推荐物品的方法。您可以使用相似度算法找到您正在寻找的“邻居”。该章节可在此处的谷歌图书搜索中找到：http:
//books.google.com/books ?id=fEsZ3Ey-Hq4C&printsec=frontcover
您需要的是一种聚类算法，它会自动将相似的用户分组在一起。您面临的第一个困难是大多数聚类算法期望它们聚类的项目被表示为欧几里得空间中的点。在您的情况下，您没有点的坐标。相反，您可以计算它们之间的“相似性”函数的值。
这里的一个很好的可能性是使用光谱聚类，这正是你所拥有的：相似矩阵。缺点是您仍然需要为每对点计算兼容性函数，即算法为 O(n^2)。
如果您绝对需要比 O(n^2) 更快的算法，那么您可以尝试一种称为dissimilarity spaces的方法。这个想法很简单。您反转您的兼容性函数（例如，通过取其倒数）将其转换为差异或距离的度量。然后，您将每个项目（在您的情况下为用户）与一组原型项目进行比较，并将结果距离视为空间中的坐标。例如，如果您有 100 个原型，那么每个用户将由 100 个元素的向量表示，即由 100 维空间中的一个点表示。然后您可以使用任何标准的聚类算法，例如K-means。
现在的问题是你如何选择原型，你需要多少。已经尝试了各种启发式方法，但是，这里有一篇论文它认为随机选择原型可能就足够了。它显示了使用 100 或 200 个随机选择的原型的实验产生了良好的结果。在您的情况下，如果您有 1000 个用户，并且您选择其中的 200 个作为原型，那么您需要评估您的兼容性函数 200,000 次，这比比较每一对用户提高了 2.5 倍。然而，真正的优势在于，对于 1,000,000 名用户，200 个原型仍然足够，并且您需要进行 200,000,000 次比较，而不是 500,000,000,000 次改进 2500 倍。您得到的是 O(n) 算法，即比 O(n^2) 好，尽管常数因子可能很大。
请务必查看Collaborative Filtering。许多推荐系统使用协同过滤来向用户推荐项目。他们通过寻找“邻居”然后推荐你的邻居评价很高但你没有评价的项目来做到这一点。你可以去寻找邻居，谁知道呢，也许你将来会想要推荐。
GroupLens是明尼苏达大学的一个研究实验室，研究协同过滤技术。他们有大量已发表的研究以及一些示例数据集。
Netflix 奖是一项旨在确定谁能最有效地解决此类问题的竞赛。按照他们的排行榜上的链接。一些竞争对手分享了他们的解决方案。
至于计算成本低廉的解决方案，您可以试试这个：
这种方法不会那么准确，但速度很快。
干杯。
如果您将其视为构建/批处理问题而不是实时查询，则可以大大减轻对性能的担忧。
可以静态计算该图，然后进行潜在更新，例如每小时、每天等，然后生成边和存储优化以用于运行时查询，例如每个用户的前 10 个相似用户。
+1 也适用于编程集体智能 - 它提供的信息非常丰富 - 希望它不是（或者我曾经是！）面向 Python，但仍然很好。
这个问题似乎是“分类问题”。是的，有很多解决方案和方法。
要开始探索，请检查： http ://en.wikipedia.org/wiki/Statistical_classification
您听说过kohonen 网络吗？
它是一种自组织学习算法，将相似的变量聚集到相似的槽中。尽管大多数网站（如我链接到的网站）都将网络显示为二维，但很少涉及将算法扩展到多维超立方体。
使用这样的数据结构，查找和存储具有相似品味的邻居是微不足道的，因为相似的用户应该被存储到相似的位置（几乎就像一个反向哈希码）。
这将您的问题减少为找到将定义相似性的变量并在可能的枚举值之间建立距离的问题之一，例如古典和声学是接近的，而死亡金属和雷鬼是相当遥远的（至少在我看来）
顺便说一句，为了找到好的划分变量，最好的算法是决策树。更靠近根的节点将是建立“紧密度”的最重要变量。
看来您需要阅读有关聚类算法的信息。一般的想法是，每次将它们分成相似点的集群时，不要将每个点与每个其他点进行比较。那么邻域可能是同一个簇中的所有点。聚类的数量/大小通常是聚类算法的参数。
你可以在 Google 关于集群计算和 mapreduce的系列中找到关于集群的视频。