无需替换的最近邻向量匹配
Nearest neighbour vector matching without replacement
我想在 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 更具说明性的示例和术语，我正在寻找匹配的全局最优值，而不是局部最优值（first/greedy 匹配项）。例如，如果 X= c(3,7) 和 Y= c(1,4,12)，我想获得曼哈顿距离为 5 的 Z= c(1, 4)。我不想要 first/greedy 匹配，这将是 Z= c(4, 12)--这将通过找到 3 的最接近匹配以及随后的 7 的最接近匹配来获得。
蛮力
如果您可以假设大多数输入的大小都很小，那么最简单的方法就是扩展所有可能的搜索组合 space。
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
如果您有一个大搜索 space (Y)，但输入的维数较低 (X)，您可以修剪搜索 space 以帮助限制组合的数量。例如，您可以安全地排除 Y 中的所有点，这些点至少不是 X 中点的第 k 个最近邻点，其中 k是X.
的维度
算法方法
如果你确实有一个大搜索 space 并且修剪不足以减少问题，或者如果你将重复计算它并且它成为一个明显的瓶颈，你会想要诉诸到更复杂的方法。在我的脑海中，我认为 the A* algorithm 似乎很适合这个问题。对于可接受的启发式函数，可以使用 X 中每个点与其在 Y 中最近邻点的距离之和。在每次迭代中，将 X 中的一个点分配给它最近的邻居，然后在删除该点及其受让人的情况下沿着树向下移动。如果 X 中给定的 x 有多个最近的邻居（例如，x = 2 和 Y 包含 1 和 3），则必须在搜索中包括这两个选项 space.
这将达到全局最优，因为可证明 属性 给定任何 X 和 Y，对于所有全局最优，至少有一个 x在 X 中被分配给它在 Y 中最近的邻居。因此，所描述的树将包含所有可能的全局最优值，并且由于 A* 是一个 breadth-first 搜索，因此可以保证找到其中一个。
如果您需要走这条路，可能也值得在 cs.stackexchange.com 上询问，因为可能有更合适的算法。
这是一个优化问题。您需要的是使用匈牙利算法，它完全符合您的要求。
正如 Amol 所指出的，这正是 hungarian algorithm 的目的：找到最佳配对，同时最小化全局成本。您需要做的就是指定一个 cost 矩阵，我在这里将其作为点之间的 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 创建
我想在 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 更具说明性的示例和术语，我正在寻找匹配的全局最优值，而不是局部最优值（first/greedy 匹配项）。例如，如果 X= c(3,7) 和 Y= c(1,4,12)，我想获得曼哈顿距离为 5 的 Z= c(1, 4)。我不想要 first/greedy 匹配，这将是 Z= c(4, 12)--这将通过找到 3 的最接近匹配以及随后的 7 的最接近匹配来获得。
蛮力
如果您可以假设大多数输入的大小都很小，那么最简单的方法就是扩展所有可能的搜索组合 space。
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
如果您有一个大搜索 space (Y)，但输入的维数较低 (X)，您可以修剪搜索 space 以帮助限制组合的数量。例如，您可以安全地排除 Y 中的所有点，这些点至少不是 X 中点的第 k 个最近邻点，其中 k是X.
算法方法
如果你确实有一个大搜索 space 并且修剪不足以减少问题，或者如果你将重复计算它并且它成为一个明显的瓶颈，你会想要诉诸到更复杂的方法。在我的脑海中，我认为 the A* algorithm 似乎很适合这个问题。对于可接受的启发式函数，可以使用 X 中每个点与其在 Y 中最近邻点的距离之和。在每次迭代中，将 X 中的一个点分配给它最近的邻居，然后在删除该点及其受让人的情况下沿着树向下移动。如果 X 中给定的 x 有多个最近的邻居（例如，x = 2 和 Y 包含 1 和 3），则必须在搜索中包括这两个选项 space.
这将达到全局最优，因为可证明 属性 给定任何 X 和 Y，对于所有全局最优，至少有一个 x在 X 中被分配给它在 Y 中最近的邻居。因此，所描述的树将包含所有可能的全局最优值，并且由于 A* 是一个 breadth-first 搜索，因此可以保证找到其中一个。
如果您需要走这条路，可能也值得在 cs.stackexchange.com 上询问，因为可能有更合适的算法。
这是一个优化问题。您需要的是使用匈牙利算法，它完全符合您的要求。
正如 Amol 所指出的，这正是 hungarian algorithm 的目的：找到最佳配对，同时最小化全局成本。您需要做的就是指定一个 cost 矩阵，我在这里将其作为点之间的 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 创建