多分类算法各组间个体最大交集求解技术问询

问题背景 #

现有多个可将个体分为A、B、C、D四类的算法，示例数据集如下：

# 示例数据集
df_orig <- tibble(
  Individuals = c(1, 2, 3, 4, 5, 6, 7),
  Algorithm_1 = c("A", "B", "A", "C", "A", "A", "D"),
  Algorithm_2 = c("B", "C", "B", "D", "C", "A", "D"),
  Algorithm_3 = c("C", "D", "D", "B", "D", "B", "A"),
  Algorithm_4 = c("D", "B", "C", "A", "B", "A", "A")
)

各组分类仅存在模糊重叠，需求为：找出跨算法的类间个体最大交集，输出最优匹配表格形式。

已尝试方法及问题 #

• 使用集合论方法Reduce(intersect())，但嵌套在dplyr::结构中返回numeric(0)，未得到有效结果
• 采用相关分析方法，仅能获取两两算法的分类相关性，无法得到多类跨算法的最优个体集合

解决方案 #

通过枚举所有跨算法类组合、计算组合个体交集的方式，筛选出交集最大的匹配组合，具体实现代码如下：

步骤1：加载依赖包并处理数据 #

library(tidyverse)

# 提取每个算法的「类-个体列表」映射
class_individuals <- df_orig %>%
  pivot_longer(cols = starts_with("Algorithm_"), names_to = "Algorithm", values_to = "Class") %>%
  group_by(Algorithm, Class) %>%
  summarise(Individuals = list(Individuals), .groups = "drop")

步骤2：生成所有跨算法类组合 #

# 生成每个算法选一个类的所有可能组合
class_combinations <- expand.grid(
  Algorithm_1 = unique(df_orig$Algorithm_1),
  Algorithm_2 = unique(df_orig$Algorithm_2),
  Algorithm_3 = unique(df_orig$Algorithm_3),
  Algorithm_4 = unique(df_orig$Algorithm_4)
)

步骤3：计算交集并筛选最优匹配 #

# 计算每个组合的个体交集及大小
result <- class_combinations %>%
  rowwise() %>%
  mutate(
    # 获取对应算法类的个体列表
    list1 = filter(class_individuals, Algorithm == "Algorithm_1", Class == Algorithm_1)$Individuals[[1]],
    list2 = filter(class_individuals, Algorithm == "Algorithm_2", Class == Algorithm_2)$Individuals[[1]],
    list3 = filter(class_individuals, Algorithm == "Algorithm_3", Class == Algorithm_3)$Individuals[[1]],
    list4 = filter(class_individuals, Algorithm == "Algorithm_4", Class == Algorithm_4)$Individuals[[1]],
    # 计算四组个体的交集
    intersection = list(Reduce(intersect, list(list1, list2, list3, list4))),
    # 记录交集个体数量
    intersection_size = length(intersection[[1]])
  ) %>%
  ungroup() %>%
  arrange(desc(intersection_size))

# 筛选出交集最大的最优匹配
optimal_matches <- result %>%
  select(Algorithm_1, Algorithm_2, Algorithm_3, Algorithm_4, intersection_size, intersection) %>%
  filter(intersection_size == max(intersection_size))

# 查看最优匹配结果
print(optimal_matches)

结果说明 #

运行上述代码后，optimal_matches会输出所有跨算法类组合中个体交集最大的匹配项，包括对应算法的类、交集大小及具体个体列表，完全满足需求。

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