计算数百万份文档之间的相似度指标

Question

我有数百万个文档（接近1亿），每个文档都有诸如skills、hobbies、certification和{}等字段。我想找出每个文档之间的相似性以及分数。在

下面是一个数据示例。在

skills  hobbies        certification    education
Java    fishing        PMP              MS
Python  reading novel  SCM              BS
C#      video game     PMP              B.Tech.
C++     fishing        PMP              MS

所以我想要的是第一行和所有其他行之间的相似性，第二行和所有其他行之间的相似性，等等。所以，每个文档都应该与其他文档进行比较。得到相似度得分。在

我的目的是查询我的数据库以获取基于技能的人员。除此之外，我现在想要的人即使不具备技能，但在某种程度上与具有特定技能的人相匹配。例如，如果我想为具有JAVA技能的人获取数据，那么第一行将出现，最后一行将再次出现，因为它与第一行基于相似性得分相同。在

挑战：我的主要挑战是计算每个文档相对于其他文档的相似性分数，如下面的伪代码所示。我怎样才能更快？对于这个伪代码有什么不同的方法吗？或者有没有其他的计算（硬件/算法）方法可以更快地完成这个任务？在

^{pr2}$

Answer 1

我想你想要的是某种聚类算法。您可以将数据的每一行看作多维空间中的一个点。然后你想寻找附近的其他“点”。并不是所有的数据维度都能产生良好的聚类，因此您需要分析数据中哪些维度对生成集群非常重要，并通过映射到较低维度的数据来降低查找类似记录的复杂性。scikit-learn提供了一些用于维度分析和聚类的良好例程，以及一些帮助您决定将哪些例程应用于数据的最佳文档。对于实际的分析，我认为您最好购买AWS或googleappengine的云计算时间。我相信两者都可以让您访问节点上可用的Anaconda（包括scikit learn）的Hadoop集群。关于这些主题（集群、云计算）的详细说明都超出了简单的答案。当你陷入困境时，再问一个问题。在

Answer 2

对于1亿个文档，您需要500000亿个比较。不，在Python中不能这样做。在

最可行的解决方案（除了使用超级计算机之外）是计算C/C++中的相似性得分。在

1. 阅读整个数据库并列举每项技能、爱好、认证和教育。这个操作需要一个线性时间，假设您的索引查找是“智能”的，并且需要固定的时间。在
< L>创建一个C/C++ ^ {CD1}}，包含四个数字字段：技能、爱好、认证和教育。在
2. 运行一个嵌套循环，从所有其他的struct字段中减去每个{}，并使用位级算法来评估相似度。在
3. 如有必要，将结果保存到一个文件中，并可供Python程序使用。在

Answer 3

一种加快速度的方法是确保你不会同时计算相似度。您当前的伪代码将比较i和{}和j与{}。不要在整个文档中迭代j，而是迭代document[i+1:]，即只在i之后的条目。这将使您对compute_similarity的调用减少一半。在

最适合这种比较的数据结构是邻接矩阵。这将是一个n * n矩阵（n是数据集中的成员数），其中matrix[i][j]是成员{}和{}之间的相似性。您可以完全填充这个矩阵，同时只需对j进行半次迭代，只需同时为matrix[i][j]和{}分配一个对compute_similarity的调用。在

除此之外，我想不出任何加快此过程的方法；您至少需要对compute_similarity进行n * (n - 1) / 2调用。把它想象成握手问题；如果每个成员都必须与每个其他成员（握手）至少比较一次，那么下限是n * (n - 1) / 2。但我欢迎其他人的意见！在