无需替换的最近邻向量匹配

Question

我希望在R语言中实现以下功能：对于向量X中的每个元素，我想要找到向量Y中最近的邻居，使得每个X-Y匹配对应的绝对差的总和最小。向量Y的长度至少与向量X相同。

注意：我希望在不进行替换的情况下完成这个任务。例如，给定以下向量：

X= c(3, 6)
Y= c(1, 2, 4, 10),

我希望获得Z = c（2,4），因为将3匹配到2，将6匹配到4，比将3匹配到4，将6匹配到10创建了更小的总距离。

*这是我第一次在stack上提出问题，所以提前道歉如果我有任何错误。

更新：使用@merv更具说明性的示例和术语，我正在寻找匹配的全局最优解，而不是局部最优解（第一个/贪心匹配）。例如，如果X = c（3,7）并且Y = c（1,4,12），我想获得Z = c（1,4），其曼哈顿距离为5。我不想要第一个/贪婪的匹配，这将是Z = c（4,12） - 这将通过找到3的最接近匹配，随后找到7的最接近匹配来获得。

- txinferno

---

尝试使用Y[findInterval(X, Y)] - akrun

@akrun的解决方案非常好，但你也可以使用：Y[sapply(X, function(x) which.min(abs(Y - x)))] - pogibas

因为没有替代品。如果有Y元素的替代品，那么c(11, 11)就可以工作了。 - txinferno

你能否更新你的问题，提供完整的输入和期望的输出示例？ - pogibas

已更新问题，以解决@merv的疑问。 - txinferno

Answer 1

暴力破解

如果您可以假设大多数输入的大小都很小，则最简单的方法是扩展搜索空间的所有可能组合。

uniqueNearestNeighbor <- function (X, Y) {
  zs <- combn(Y, length(X))
  dists <- apply(zs, 2, function (z) sum(abs(X - z)))
  return(zs[,which.min(dists)])
}

请注意，这假定您的向量都已排序。

> uniqueNearestNeighbor(c(3, 7), c(1, 4, 12))
[1] 1 4

如果您有一个大的搜索空间（Y），但输入维度较低（X），您可以剪枝搜索空间，以帮助限制组合数量。例如，您可以安全地排除所有不是至少是X中某个点的第k近邻的Y中的点，其中k是X的维度。

算法方法

如果您确实有一个大的搜索空间，并且剪枝不足以简化问题，或者如果您将重复计算它并且它成为明显的瓶颈，则需要采用更复杂的方法。我认为A*算法似乎是适合这个问题的。对于一个可接受的启发式函数，可以使用X中每个点到其在Y中最近邻居的距离之和。在每次迭代中，将X中的一个点分配给其最近邻居，然后使用该点和其被分配的点删除树。如果X中的给定x具有多个最近邻居（例如，x = 2，Y包含1和3），则必须在搜索空间中包含两个选项。

这将到达全局最优解，因为对于任何X和Y，对于所有全局最优解，至少有一个X分配给其在Y中的最近邻居。因此，所描述的树将包含所有可能的全局最优解，并且由于A*是广度优先搜索，其中一个解决方案得到保证。

如果您需要采用这种方法，也许值得在cs.stackexchange.com上提问，因为可能会有更适合的算法。

- merv

---

感谢@merv的周到回复。我也相信暴力破解是正确的方法：我使用了optmatch包的pairmatch功能，我怀疑它在幕后正是按照您所描述的方式进行操作。 - txinferno

Answer 2

这是一个优化问题。你需要使用匈牙利算法，它正好做你想要的事情。

- Amol Deshmukh

Answer 3

正如Amol所指出的那样，这正是匈牙利算法的目标：在最小化全局成本的同时找到最优配对。你需要做的就是指定一个成本矩阵，我在这里将其视为点之间的L1/L2距离。

复制OP的第二个示例，使用RcppHungarian，可以得到相同的解决方案Z= c(1, 4)和相同的最小成本5：

library(RcppHungarian)

X= c(3,7)
Y= c(1,4,12)
D <- outer(X, Y, function(x, y) abs(x-y))

out <- HungarianSolver(D)
out
#> $cost
#> [1] 5
#> 
#> $pairs
#>      [,1] [,2]
#> [1,]    1    1
#> [2,]    2    2
Y[out$pairs[,2]]
#> [1] 1 4

^{由reprex package (v2.0.1)于2021年11月23日创建}

- Matifou