从向量列表中找到最接近的向量 | Python

Question

如果给你一个包含 10 个向量的列表，称为 A，代表不同的组。然后你有一个向量 v1,v2,...,vn 的时间序列，每个向量也是一个向量。我想知道如果定义一些距离度量，是否有办法在 A 中为每个 v1、v2、...、vn 找到 "closest" 向量？

除了遍历和比较所有条目之外，还有什么快速的方法可以做到这一点吗？

编辑：不，我不是在问如何做 k-means 或类似的东西。

Answer 1

如果你定义了一个指标，你可以在min函数中使用它：

closest = min(A, key=distance)

Answer 2

可以使用spatial KDtree in scipy。它使用快速树算法来识别任意维度向量的邻近点。

编辑：抱歉，如果您正在寻找 arbitrary distance metrics，树状结构可能仍然是一个选项。

这是一个例子：

>>> from scipy import spatial
>>> A = [[0,1,2,3,4], [4,3,2,1,0], [2,5,3,7,1], [1,0,1,0,1]]
>>> tree = spatial.KDTree(A)

这将使用 A 中的所有点设置 KDTree，允许您在其中执行快速空间搜索。这样的查询需要一个向量，并且 return 是 A 中最近的邻居：

>>> tree.query([0.5,0.5,0.5,0.5,0.5])
(1.1180339887498949, 3)

第一个return值是最近邻居的距离，第二个是它在A中的位置，这样你就可以像这样获得它：

>>> A[ tree.query([0.5,0.5,0.5,0.5,0.5])[1] ]
[1, 0, 1, 0, 1]

Answer 3

所以一些示例代码是：

# build a KD-tree to compare to some array of vectors 'centall'
tree = scipy.spatial.KDTree(centall) 
print 'shape of tree is ', tree.data.shape

# loop through different regions and identify any clusters that belong to a different region
[d1, i1] = tree.query(group1)
[d2, i2] = tree.query(group2)

这个returns变量d和i。 d 存储最近的距离 i returns 发生这种情况的索引

希望对您有所帮助。

从向量列表中找到最接近的向量 | Python

Find Closest Vector from a List of Vectors | Python

python

vector

distance