从一组文档中找到最相似的文档（最近邻居）

Question

我有80,000份关于众多主题的文件。我想要做的是为每篇文章提供链接，推荐其他类似的文章（例如前5篇相关文章），这些文章与用户当前阅读的文章相似。如果不需要，我对分类文件并不感兴趣，只是相似性或相关性。理想情况下，我希望输出一个 80,000 x 80,000 的矩阵，其中包含所有文档及其与数据集中其他文档的距离（或者可能是相关性/相似性）。

我目前在使用 NLTK 处理文档内容并获取 ngrams，但是不确定应该采取什么方法来计算文档之间的相似度。

我了解到可以使用 tf-idf 和余弦相似度，但由于预计有大量的主题，因此可能会有很多唯一的标记，因此将两个非常长的向量相乘可能不是一个好方法，而且80,000个文档可能需要进行大量的向量相乘。（不过，必须仅需要执行一次，因此这仍然是一个选项）。

是否有更好的方法来获取文件之间的距离，而无需创建ngrams的庞大向量？斯皮尔曼相关性？还是采取更低技术的方法，例如获取前k-grams中的前ngrams并查找具有相同ngrams的其他文件，会更合适？我只是觉得如果需要将可能包含10,000个元素的向量乘以320万次（算术序列的总和从79,999 + 79,998 ...到1），那肯定是最暴力的方法。

欢迎提供建议或指导阅读资料。

- fohx

Answer 1

你应该学习哈希机制，以计算文档之间的相似性。典型的哈希函数旨在最小化冲突映射，将近似重复的内容映射到非常不同的哈希键。在加密哈希函数中，如果数据改变了一个位，哈希键将被更改为完全不同的键。

相似性哈希的目标是创建一个相似性哈希函数。基于哈希的技术用于检测近似重复内容的设计与加密哈希算法的相反。非常相似的文档映射到非常相似的哈希键，甚至映射到相同的键。键的按位汉明距离的差异是相似性的一种度量。

计算哈希键后，可以对键进行排序，将近似重复内容的检测速度从O(n2)提高到O(nlog(n))。可以通过分析训练数据的准确性来定义和调整阈值。

Simhash、Minhash和Local sensitive hashing是三种基于哈希的方法的实现。你可以通过谷歌搜索获取更多信息。有很多与此主题相关的研究论文...

- Sampath Liyanage

Answer 2

对于 K=5，您基本上想返回特定文档的K个最近邻居吗？在这种情况下，您应该使用K-Nearest Neighbors算法。Scikit-Learn有一些很好的文本导入和规范化例程（tfidf），然后实现KNN就很容易了。

启发式方法基本上只是从文档中的所有单词创建归一化的单词计数向量，然后比较向量之间的距离。我肯定会交换几个不同的距离度量：例如欧几里得距离 vs. 曼哈顿距离 vs. 余弦相似度。这些向量并不是真正的“长”，它们只是位于高维空间中。因此，您可以通过PCA或您喜欢的算法进行一些降维来解决您写的唯一单词问题。

在另一个软件包中执行此操作可能同样容易，但是Scikit learn的文档非常出色，使您能够快速而全面地学习。

- AN6U5

---

谢谢！我会研究一下的！从之前了解kNN算法的阅读中，似乎在找到距离后，下一步总是对数据点进行分类，所以我很困惑是否只能用它来寻找距离。 - fohx