2组点之间的成对匹配

Question

我需要一种方法来确定两组点之间成对拟合的最佳组合，以便最小化聚类对之间的总体距离。它似乎可能适合 k-means（如果 max/min 簇大小约束为 2 是可能的，则使用 'n' 对）但我不知道任何可以在 2 组之间聚集的函数。有谁知道合适的功能或替代聚类方法？

作为起点，它看起来像以下几组点的解决方案：

set1 <- data.frame(id=c('A','B','C'), x = c(3,4,7), y = c(4,2,6))
set2 <- data.frame(id=c('X','Y','Z'), x = c(2,5,8), y = c(5,6,7))

... 是 AX、BY、CZ：

Answer 1

这不是聚类分析。这与在您的数据集中查找结构组件无关。

相反，您要查找的是两个数据集的 JOIN。

如果允许每个点映射到另一个数据集中的多个点，那么它就是最近邻连接。否则，我不知道该怎么称呼它，但我知道解决它的算法：

Hungarian algorithm，也称为Kuhn–Munkres算法或Munkres分配算法。最简单的解释如下：

您有 n 个生产者
您有 m 个消费者，可能有 m != n，但最好假设 m=n。
您想最大化您的利润，例如最大限度地减少将产品从生产者运送到消费者的运输成本

所以你构建了一个运输成本矩阵，列出了每对生产者和消费者的成本。然后可以使用匈牙利算法来找到最佳映射。（其中可能涉及并不总是选择最近的邻居。）

Answer 2

除了@Anoiny-Mousse 的回答之外，这个适用于我的 R 实现：

require(clue)
dist_mat = fields::rdist(set1[,2:3], set2[,2:3])
soln = solve_LSAP(dist_mat)
data.frame(set1 = set1$id, set2 = set2$id[soln])
  set1 set2
1    A    X
2    B    Y
3    C    Z

2组点之间的成对匹配

Pairwise matching between 2 sets of points

r

cluster-analysis