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

Question

如果给你一个10个向量的列表，称为a，代表不同的组。然后你有一个时间序列的向量v1 v2，…，vn，它们都是向量。我想知道是否有一种方法可以找到a中每个v1,v2，…如果你定义一些距离度量?

除了循环和比较所有条目之外，有没有一种快速的方法来做到这一点?

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

Answer 1

您可以在scipy中使用空间KDtree。它使用快速树算法来识别任意维向量的近邻点。

编辑:抱歉，如果您正在寻找任意距离度量，树状结构可能仍然是一个选项。

下面是一个例子:

>>> 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，允许您在其中执行快速空间搜索。这样的查询接受一个向量，并返回它在a中最近的邻居:

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

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

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

Answer 2

如果您定义了一个度量，您可以在min函数中使用它:

closest = min(A, key=distance)

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)

返回变量d和i。D存储最近的距离I返回发生此操作的索引