如何在不重复ID的前提下筛选topic与index的最高value配对

需求说明 #

我有一个合并后的DataFrame（df），包含54个唯一的topic ID、54个唯一的index ID，共2916条观测数据，每条观测对应一个数值评分value。需要筛选出一个包含54条观测的子DataFrame，满足以下要求：

• 每个topic和index都仅出现一次（无重复）
• 选中的topic-index配对的value尽可能高

举个例子：样本数据中index 349同时出现在topic 33和topic 2的高value行里，需要把index 349分配给value更高的topic 33，topic 2则取次高对应的index 347。

样本数据 #

df <- structure(list(topic = c(33L, 2L, 33L, 2L, 33L, 13L, 33L, 2L, 
2L, 2L, 42L, 13L, 33L), index = c(349, 349, 363, 347, 342, 369, 
321, 366, 321, 363, 344, 370, 366), value = c(0.210311631079167, 
0.204938177956459, 0.201678820628508, 0.160801031631647, 0.160747075179686, 
0.154814646522019, 0.154102617910918, 0.137730410377001, 0.126294470150952, 
0.123695668664189, 0.110965846294849, 0.0999091218902647, 0.099824248465453
)), row.names = c(NA, -13L), class = c("tbl_df", "tbl", "data.frame"
))

期望输出 #

output <- structure(list(topic = c(33L, 2L, 13L, 42L), index = c(349, 347, 
369, 344), value = c(0.210311631079167, 0.160801031631647, 0.154814646522019, 
0.110965846294849)), row.names = c(NA, -4L), class = c("tbl_df", 
"tbl", "data.frame"))

当前问题代码 #

以下代码无法实现需求：

df2 <- df %>% group_by(topic, index) %>% arrange(-value) %>% filter(top_n(54))

解决方案 #

方法1：贪心算法（高效匹配，符合示例逻辑） #

核心思路：按value从高到低排序，依次选择未被占用的topic和index配对，直到凑够54条。

library(dplyr)

# 按value降序排序所有观测
sorted_df <- df %>% arrange(desc(value))

# 初始化空容器记录已选中的topic、index和结果
selected_topics <- c()
selected_indexes <- c()
result <- tibble()

# 遍历排序后的每一行
for (i in 1:nrow(sorted_df)) {
  current_topic <- sorted_df$topic[i]
  current_index <- sorted_df$index[i]
  
  # 如果当前topic和index都未被选中，就加入结果集
  if (!(current_topic %in% selected_topics) && !(current_index %in% selected_indexes)) {
    result <- bind_rows(result, sorted_df[i, ])
    selected_topics <- c(selected_topics, current_topic)
    selected_indexes <- c(selected_indexes, current_index)
    
    # 选够54条后终止循环
    if (nrow(result) == 54) break
  }
}

优势：计算速度快，逻辑简单直观，完全匹配示例中的分配规则。

方法2：线性规划（全局最优匹配） #

如果需要严格最大化所有选中配对的总value，可以用线性规划求解最优二分匹配问题，需要用到lpSolve包。

library(lpSolve)
library(dplyr)
library(tidyr)

# 将数据转换为成本矩阵（为适配lp的最小化需求，取value的负值）
cost_matrix <- df %>% 
  pivot_wider(names_from = index, values_from = value, values_fill = 0) %>%
  column_to_rownames("topic") %>%
  as.matrix()
cost_matrix <- -cost_matrix  # 转换为最小化问题

# 构建约束条件：每个topic必须选1个index，每个index只能被1个topic选中
row_constraints <- rep(1, nrow(cost_matrix))  # 每行（topic）和为1
col_constraints <- rep(1, ncol(cost_matrix))  # 每列（index）和为1

# 求解0-1线性规划
lp_result <- lp(
  direction = "min",
  objective.in = as.vector(cost_matrix),
  const.mat = rbind(
    # 行约束矩阵：每个topic对应一行，标记该topic的所有可能index
    t(model.matrix(~0 + rownames(cost_matrix))),
    # 列约束矩阵：每个index对应一行，标记所有可能的topic
    model.matrix(~0 + colnames(cost_matrix))
  ),
  const.dir = rep("=", length(row_constraints) + length(col_constraints)),
  const.rhs = c(row_constraints, col_constraints),
  all.bin = TRUE  # 变量为0或1，表示是否选中该配对
)

# 提取选中的配对并转换回原DataFrame格式
selected_pairs <- which(lp_result$solution == 1, arr.ind = TRUE)
result <- df %>%
  filter(
    topic == rownames(selected_pairs)[selected_pairs[,1]],
    index == colnames(selected_pairs)[selected_pairs[,2]]
  ) %>%
  arrange(topic)

优势：得到全局最优解（总value最大），适合需要严格最优结果的场景；54×54的规模计算完全可行。

内容的提问来源于stack exchange，提问作者DOR