r - 最近邻向量匹配无替换

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 产生的总距离更小。

*这是我的第一个堆栈问题，因此对于我在提出问题时犯的任何错误，提前道歉。

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

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 )，则可以修剪搜索空间以帮助限制组合数量。例如，您可以安全地排除 Y 中的所有点。至少不是 X 中某个点的第 k 个最近邻居，其中 k 是 X 的维度.

算法方法

如果您确实有很大的搜索空间并且修剪不足以减轻问题，或者如果您将重复计算它并且它成为一个明显的瓶颈，您将需要求助于更复杂的方法。在我的头顶，我想 the A* algorithm似乎它很适合这个问题。对于可接受的启发式函数，可以使用 X 中每个点的距离之和。到其在 Y 中的最近邻居.在每次迭代中，在 X 中分配一个点到它最近的邻居，然后沿着树向下移动，该点并删除其受让人。如果给定 x在 X有多个最近的邻居(例如，x = 2 和 Y 包含 1 和 3)，必须在搜索空间中包含这两个选项。

由于给定任何 X 的可证明性质，这将达到全局最优。和 Y ，对于所有全局最优，至少有一个 x在 X被分配给它在 Y 中的最近邻居.因此，所描述的树将包含所有可能的全局最优值，并且因为 A* 是广度优先搜索，保证找到其中一个。

如果您需要走这条路，也许也值得在 cs.stackexchange.com 上询问，因为可能有更合适的算法。