如何在两个数组中找到最接近的元素？

Question

我有两个numpy数组,比如X=[x1,x2,x3,x4], y=[y1,y2,y3,y4].其中三个元素很接近,第四个元素可能接近或不接近.

喜欢:

X   [ 84.04467948  52.42447842  39.13555678  21.99846595]
y   [ 78.86529444  52.42447842  38.74910101  21.99846595]

或者它可以是:

X   [ 84.04467948  60  52.42447842  39.13555678]
y   [ 78.86529444  52.42447842  38.74910101  21.99846595]

我想定义一个函数来查找两个数组中的相应索引,如第一种情况:

• y[0]对应X[0],
• y[1]对应X[1],
• y[2]对应X[2],
• y[3] 相当于 X[3]

在第二种情况下:

• y[0]对应X[0],
• y[1]对应X[2],
• y[2] 相当于 X[3]
• 并y[3]对应于X[1].

我不能写一个完全解决问题的功能,请帮忙.

Answer 1

您可以首先预先计算距离矩阵，如本答案所示：

import numpy as np

X = np.array([84.04467948,60.,52.42447842,39.13555678])
Y = np.array([78.86529444,52.42447842,38.74910101,21.99846595])

dist = np.abs(X[:, np.newaxis] - Y)

现在您可以计算沿一个轴的最小值（我选择对应于为每个1找到最接近的元素）：YX

potentialClosest = dist.argmin(axis=1)

这仍然可能包含重复项（在您的情况下为 2）。要检查这一点，您可以使用以下命令找到Y出现在中的所有索引：potentialClosestnp.unique

closestFound, closestCounts = np.unique(potentialClosest, return_counts=True)

现在您可以通过检查 if 来检查重复项closestFound.shape[0] == X.shape[0]。如果是这样，那么您就是黄金，potentialClosest并将包含您的合作伙伴的每一个元素X。但在你的情况 2 中，一个元素会出现两次，因此closestFound只会有X.shape[0]-1elements 而closestCounts不会只包含1s 而是包含 1 2。对于所有具有 count 的元素，1已经找到了合作伙伴。对于有计数的两个候选者2，虽然你必须选择较近的一个，但距离较大的那个的伙伴将是Y不在其中的一个元素closestFound。这可以通过以下方式找到：

missingPartnerIndex = np.where(
        np.in1d(np.arange(Y.shape[0]), closestFound)==False
        )[0][0]

您可以在循环中进行匹配（尽管使用 可能有一些更好的方法numpy）。这个解决方案相当丑陋但有效。非常感谢任何改进建议：

partners = np.empty_like(X, dtype=int)
nonClosePartnerFound = False
for i in np.arange(X.shape[0]):
    if closestCounts[closestFound==potentialClosest[i]][0]==1:
        # A unique partner was found
        partners[i] = potentialClosest[i]
    else:
        # Partner is not unique
        if nonClosePartnerFound:
            partners[i] = potentialClosest[i]
        else:
            if np.argmin(dist[:, potentialClosest[i]]) == i:
                partners[i] = potentialClosest[i]
            else:
                partners[i] = missingPartnerIndex
                nonClosePartnerFound = True
print(partners)

仅当只有一对不接近时，此答案才有效。如果不是这种情况，您将必须定义如何为多个非封闭元素找到正确的伙伴。遗憾的是，它既不是一个非常通用的解决方案，也不是一个非常好的解决方案，但希望您会发现它是一个有用的起点。

Answer 2

似乎最好的方法是对两个数组进行预排序 (n log(n))，然后对两个数组执行类似合并的遍历。它肯定比您在评论中指出的 n n 快。