有效地找到与给定向量的前K个余弦相似向量

Question

问题：

假设我有一组大约1,000,000个简短文档D（每个文档不超过50个单词），并且我想让用户提供来自同一组D的文档，并从D中获得前K个相似的文档。

我的方法：

我的第一种方法是通过应用简单的tf-idf预处理D组，然后在每个文档都有非常稀疏的矢量之后，使用基于余弦相似度的简单最近邻算法。然后，在查询时间，仅使用我的静态最近邻居表（其大小为1,000,000 x K），而无需进行任何进一步的计算。

应用tf-idf之后，我得到的向量大小约为200,000，这意味着我现在有一个非常稀疏的表（可以使用稀疏向量将其有效地存储在内存中），大小为1,000,000 x 200,000。但是，计算最近的邻居模型花了我超过一天的时间，但还没有完成。我试图通过应用HashingTF来降低向量维，该方法利用了hasing技巧，因此我可以将维设置为常数（在我的情况下，我使用2 ^ 13表示不干扰的哈希），但仍然得到相同的结果表现不佳。

一些技术信息：

我将Spark 2.0用于tf-idf计算，并对收集的数据使用sklearn NearestNeighbours。

有没有更有效的方法实现这一目标？

提前致谢。

编辑：

我有一个想法去尝试LSH基于近似度算法像所描述的火花实现这里，但无法找到一个支持“余弦”相似性度量。

Answer 1

该算法对训练实例和向量维度之间的关系有一些要求，但您可以尝试DIMSUM。

您可以在此处找到该论文。