如何计算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,这是用户兴趣的良好表现.

相似功能

无论是余弦距离或杰卡德相似性是适合你的情况.

为给定用户查找类似用户

Kd Tree方法

首先构造kd树,然后对于任何给定用户,您可以为该用户启动查询,kd-tree能够基于相似性函数返回k-nearest-neighbor.C++中的良好实施是在这里.

locality-sensitive-hashing 途径

您将用户哈希到不同的存储桶.类似用户更有可能被一起散列.因此,对于类似的用户搜索,您只比较同一个存储桶中的用户.请查看此示例:如何理解位置敏感哈希？

clustering 途径

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

collaborative-filtering 做法.

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