1

我有一个长数字表，其中 7 列是键，4 列是要查找的值。

实际上，我已经渲染了一个具有不同距离和透视角度的对象，并计算了它的轮廓的 Hu 矩。但这对问题并不重要，只是一个想象的样本。

所以，当我有 7 个值时，我需要扫描一个表，在这 7 个列中找到最接近的值并提取相应的 4 个值。

因此，要考虑的任务方面如下：

1）数字有错误

2）函数域的尺度与函数值的尺度不同；即7维空间中点的“距离”应该取决于这4个值，它如何影响

3）搜索应该很快

所以问题如下：是不是有一些算法可以有效地解决这个任务，即对那 7 列执行一些索引，但是这样做不像传统数据库那样，而是考虑到上面的一点。

4

2 回答 2

2

如果我正确理解了这个问题，您可以考虑使用scipy.cluster.vq（矢量量化）：

假设您的 7 个数字列如下所示（我们称之为数组code_book）：

import scipy.cluster.vq as vq
import scipy.spatial as spatial
import numpy as np
np.random.seed(2013)
np.set_printoptions(precision=2)
code_book = np.random.random((3,7))
print(code_book)
# [[ 0.68  0.96  0.27  0.6   0.63  0.24  0.7 ]
#  [ 0.84  0.6   0.59  0.87  0.7   0.08  0.33]
#  [ 0.08  0.17  0.67  0.43  0.52  0.79  0.11]]

假设相关的 4 列值如下所示：

values = np.arange(12).reshape(3,4)
print(values)
# [[ 0  1  2  3]
#  [ 4  5  6  7]
#  [ 8  9 10 11]]

最后，假设我们对 7 列值有一些“观察”，如下所示：

observations = np.random.random((5,7))
print(observations)
# [[ 0.49  0.39  0.41  0.49  0.9   0.89  0.1 ]
#  [ 0.27  0.96  0.16  0.17  0.72  0.43  0.64]
#  [ 0.93  0.54  0.99  0.62  0.63  0.81  0.36]
#  [ 0.17  0.45  0.84  0.02  0.95  0.51  0.26]
#  [ 0.51  0.8   0.2   0.9   0.41  0.34  0.36]]

要找到最接近每个观察值的 7 值行code_book，可以使用vq.vq：

index, dist = vq.vq(observations, code_book)
print(index)
# [2 0 1 2 0]

索引值指的是code_book. 但是，如果 中的行以values与 相同的方式排序code_book，我们可以使用“查找”关联值values[index]：

print(values[index])
# [[ 8  9 10 11]
#  [ 0  1  2  3]
#  [ 4  5  6  7]
#  [ 8  9 10 11]
#  [ 0  1  2  3]]

以上假设您将所有观察结果排列在一个数组中。因此，要查找所有索引，您只需要一次调用vq.vq.

但是，如果您一次获得一个观测值，并且需要code_book在继续下一个观测值之前找到最近的行，那么vq.vq每次调用都会效率低下。相反，生成一个 KDTree一次，然后在树中找到最近的邻居：

tree = spatial.KDTree(code_book)
for observation in observations:
    distances, indices = tree.query(observation)
    print(indices)
    # 2
    # 0
    # 1
    # 2
    # 0

code_book请注意，与简单的穷举搜索相比，您的( N)中的点数必须大于数据的维度（例如N >> 2**7），以便 KDTree 更快。

使用vq.vqorKDTree.query可能会也可能不会比穷举搜索更快，具体取决于数据的大小（code_book和observations）。要找出哪个更快，请务必对这些与使用timeit的详尽搜索进行基准测试。

于 2013-06-17T13:23:13.240 回答
1

我不知道我是否理解你的问题，但我会尝试给出答案。

对于表中的每一行 K 计算您的键与该行中的键的距离：

( (X1-K1)^2 + (X2-K2)^2 + (X3-K3)^2 + (X4-K4)^2 + (X5-K5)^2 + (X6-K6)^2 + ( X7-K7)^2)^0.5

其中 {X1,X2,X3,X4,X5,X6,X7} 是键，{K1,K2,K3,K4,K5,K6,K7} 是第 K 行的键

您可以在计算距离时使键的一个因素或多或少与其他因素相乘，例如，您可以将上面公式中的(X1-K1)^2替换为5*(X1-K1)^2以使其更有影响力。

并将距离存储在一个变量中，在第二个变量中存储行号

对以下行执行相同操作，如果新距离低于您存储的距离，则替换距离和行号。

当您检查了表中的所有行时，您使用的第二个变量将显示离键最近的行

这是一些伪代码：

int Row= 0
float Key[7] #suppose it is already filled with some values
float ClosestDistance= +infinity 
int ClosestRow= 0
while Row<NumberOfRows{
    NewDistance= Distance(Key,Table[Row][0:7])#suppose Distance is a function that outputs the distance and Table is the table you want to control Table[Row= NumberOfRows][Column= 7+4]
    if NewDistance<ClosestDistance{
        ClosestDistance= NewDistance
        ClosestRow= Row}
    increase row by 1}

ValueFound= Table[ClosestRow][7:11]#this should be the value you were looking for

我知道这并不快，但这是我能做的最好的，希望它有所帮助。

PS我没有考虑测量误差，我知道。

于 2013-06-17T13:45:20.260 回答