algorithm - 如何计算facebook中两个用户的相似度？

Question

我正在做一个关于数据挖掘的项目。我的公司给了我 600 万个 Facebook 的虚拟客户信息。我被指派找出任何两个用户之间的相似性。谁能给我一些如何处理大型社区数据的想法？提前致谢 ：）

问题：我使用状态信息和主题标签信息（主题标签是用户突出显示的那些词）作为衡量两个不同用户之间相似度的两个标准。由于用户数量众多，尤其是每个用户可能有数百万个标签和状态。谁能告诉我快速计算两个用户之间相似度的好方法？我曾尝试使用 TF-IDF 来计算两个不同用户之间的相似度，但似乎不可行。谁能有一个非常超级的算法或好主意，可以让我快速找到用户之间的所有相似之处？

例如：

user A's hashtag = `{cat, bull, cow, chicken, duck}`
user B's hashtag =`{cat, chicken, cloth}` 
user C's hashtag = `{lenovo, Hp, Sony}`

显然，C 和 A 没有关系，所以不必计算相似度来浪费时间，我们可以先过滤掉所有不相关的用户，然后再计算相似度。事实上，超过 90% 的总用户与特定用户无关。如何以hashtag为标准，快速找到A的潜在相似用户群？这是一个好主意吗？还是我们直接计算 A 和所有其他用户的相对相似度？哪种算法将是解决该问题的最快和定制算法？

Answer 1

用户向量表示

使用您定义的内容是可以的。您还可以包括 facebook likes，这是用户兴趣的良好代表。

相似函数

余弦距离或Jaccard相似度都适合您的情况。

为给予用户寻找相似用户

Kd 树方法

您首先构建 kd 树，然后对于任何给定用户，您可以为该用户启动查询，kd-tree 能够根据相似度函数返回您的 k-最近邻。c++ 中的一个很好的实现是here。

locality-sensitive-hashing方法

您将用户散列到不同的存储桶。相似的用户有更高的概率被散列在一起。因此，对于相似用户搜索，您只需比较同一存储桶中的用户。检查此示例：如何理解局部敏感散列？

clustering方法

尝试像k-means这样的聚类算法。这可能是您将用户分组到少量集群中的第一步，然后您可以O(n^2)在组中的所有用户对之间进行比较。

collaborative-filtering方法。

将这些喜欢或主题标签视为用户喜欢的项目。然后，您可以尝试协同过滤方法。对于数百万用户，您可能希望使用一些基于 map-reduce 的实现，例如mahout。