从矢量列表中查找最接近的矢量

从矢量列表中查找最接近的矢量|(Find Closest Vector from a List of Vectors | Python)

如果给出一个10个向量的列表，称为A代表不同的组。 然后你有一个时间序列的向量v1，v2，...，vn，每个向量也是一个向量。 如果你定义了一些距离度量，我想知道是否有一种方法可以在A中为每个v1，v2，...，vn找到“最接近”的矢量？

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

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

If you are given say a list of 10 vectors, called A that represent different groups. Then you have a time series of vectors v1,v2,...,vn, each being a vector as well. I was wondering if there was a way to find the "closest" vector in A for each v1,v2,...,vn if you define some distance metric?

Is there a quick way to do this besides for looping through and just comparing all entries?

Edit: No I am not asking how to do k-means or something like that.

最满意答案

您可以在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)

这设置了K中所有点的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]

You can use the spatial KDtree in scipy. It uses a fast tree algorithm to identify close by points for vectors of arbitrary dimension.

Edit: sorry, if you are looking for arbitrary distance metrics, a Tree like structure might still be an option.

Here is an example:

>>> 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)

This sets up the KDTree with all the points in A, allowing you to perform fast spatial searches within it. Such a query takes a vector and returns the closest neighbor in A for it:

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

The first return value is the distance of the closest neighbor and the second its position in A, such that you can obtain it for example like this:

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