我有一个数据框,包含两个向量的元素之间的所有可能组合,对于每个组合,我有一个相应的分数。我试图找到一种有效的方法来找到具有唯一元素的唯一对的子集(即,来自一个向量的元素只能在所有对中找到一次),这使得对应于每个组合的得分之和最大化。作为示例数据,请考虑这个df
:
df = data.frame(Var1 = c("A", "B", "C"), Var2 = c("A", "C", "D"))
df = expand.grid(df$Var1, df$Var2)
df$score = c(1, 0.5, 2, 1, 0.5, 0.5, 1, 2, 1)
> df
Var1 Var2 score
1 A A 1.0
2 B A 0.5
3 C A 2.0
4 A C 1.0
5 B C 0.5
6 C C 0.5
7 A D 1.0
8 B D 2.0
9 C D 1.0
>
预期结果将是:
A C 1
B D 2
C A 2
请注意,两个向量的元素之间可能存在重叠,但每个向量的每个元素应该只出现一次。此外,对A A 1
是允许的,并且是可能的,但这将使得生成C A 2
对不可能增加score
的总和。作为尝试,我使用了这个带有dplyr
功能的衬垫
df <- df %>% group_by(Var1) %>% slice(which.max(score)) %>% as.data.frame()
产生:
> df
Var1 Var2 score
1 A A 1
2 B D 2
3 C A 2
这是足够接近..但重复第二个向量的A
。你有什么建议吗?先感谢您!
好吧,我最终找到了基于在Hungarian algorithm R包的solve_LSAP
函数中实现的clue
的解决方案。为了让它工作,将你的df
转换成如下矩阵:
df = matrix(sapply(df$score, function(x) x), nrow=length(unique(df$Var1)), ncol=length(unique(df$Var2)), dimnames = list(unique(df$Var1), unique(df$Var2)))
并应用该功能
df.res = solve_LSAP(df, maximum = T)
> df.res
Optimal assignment:
1 => 2, 2 => 3, 3 => 1
然后取回实际的节点或名称
df.res = cbind(rownames(df), colnames(df)[df.res])
> df.res
[,1] [,2]
[1,] "A" "C"
[2,] "B" "D"
[3,] "C" "A"
>
Tadayalam!