algorithm - 具有任意度量的最快 k 最近邻？

Question

这个问题的难点在于“任意度量”。如果您不知道那是什么，那只是测量点之间距离的方法。 (在“真实”世界中，一维距离只是两点之间差异的绝对大小)。

准备就绪。我试图找到具有这些属性的快速 k 最近邻算法:

• 适用于任意指标
• 比较容易实现
• 针对查找一组点到另一组点的距离进行了优化

维基百科给出了算法和方法的列表，但没有具体实现。

更新:度量是余弦相似度，它不满足三角形不等式。但是，我似乎可以使用“角度相似度”(根据维基百科)。

更新:用例是自然语言处理。 “向量”是给定单词的“上下文”，由二进制属性表示(例如:文档的标题)。因此，虽然可能只有几个属性(现在我只使用 3 个)，但每个向量都有任意大的维度(在标题示例中，数据库中的每个标题都对应于向量中的一个维度)。

更新:出于好奇，我正在实现这个算法:

http://josquin.cs.depaul.edu/~mramezani/papers/IEEEIS.pdf

更新:该算法需要从大约 100 个点中找到大约 12 个点的最近邻居。平均维度可能会很大，比如 50，(我真的还不知道)。是的，我感兴趣的是算法，而不是图书馆。是的，估计可能已经足够好了。

Answer 1

我建议您使用当前流行的局部敏感哈希 (LSH)。它降低了高维数据的维度，但我不确定你的维度是否适合该算法。参见维基百科 page了解更多。

您可以使用自己的指标，但通常您可以在许多算法中这样做。希望这会有所帮助。

你可以选择 RKD 树，一片森林，但现在这可能太多了。