寻找最近向量的算法

Question

5

我有一组向量。对于这组向量中的一个向量，我想找到最接近它的子集。有哪个算法可以做到这一点？

- joel

1

你的向量代表的是“点”还是“方向”？我问这个问题是因为一些答案中提到的余弦距离度量会对向量进行归一化处理，这可能不符合你的需求，如果你正在寻找欧几里得（或其他闵可夫斯基范数）距离的话。如果是这种情况，你需要使用传统的最近邻算法，如kd树、k均值聚类等。 - tzaman

3个回答

3

使用余弦相似度（http://en.wikipedia.org/wiki/Cosine_similarity）来比较向量，然后进行排序。

- excepeiont32

+1 我本来只想提到标量积，没有考虑向量长度。谢谢你帮我避免了被嘲笑的尴尬情况 ;) - Mads Elvheim

我们不知道他想要什么距离。 - fa.

2

如果您的问题涉及大量数据：

我在ddj.com上发布了一篇相关算法，可以找到给定点最近的线：

您需要修改此算法，例如将给定向量转换为多个点。这将大大减少可能的匹配数量。然后必须对每个可能的匹配进行精确匹配检查，方法如下：

- RED SOFT ADAIR

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nick Fortescue · Accepted Answer

这类算法被称为最近邻或K最近邻。

除了余弦相似度，如果向量的方向很重要，则会起作用。如果向量表示空间中的位置，则任何表示空间中距离的度量都可行。

例如欧几里得距离：取每个维度差的平方和的平方根。这将为每个向量提供一个距离，然后按此距离对向量集进行升序排序。

这个过程的时间复杂度为O（N）。如果速度太慢，您可能需要查看一些常见的K最近邻算法。