求满足对象值覆盖要求的样本选择算法及R实现

问题概述 #

你需要从105个样本中选出最少数量的样本，确保每个(对象, 特征)组合的三个取值（0、1、2）在选中样本中各自出现至少3次。这是集合覆盖问题的变种（NP难问题），因此采用贪心算法获取近似最优解，该算法实现简单、效率高，适合大规模数据场景。

算法核心逻辑 #

1. 需求拆解：将问题拆解为每个(对象, 特征, 取值)组合需要出现至少3次，总共有i*j*3个需求（250个对象×12个特征×3个取值）。
2. 贪心迭代：每轮计算所有样本的贡献（即加入该样本后能新增多少个满足的需求），选择贡献最大的样本加入集合，更新需求满足状态，直到所有需求都达成。

R语言实现 #

1. 数据预处理（修正示例代码的格式问题） #

library(dplyr)

set.seed(1234)

i = 250 # 对象数量
j = 12 # 每个对象的特征数量
k = 105 # 样本数量
values = c(0, 1, 2)

# 生成对象-特征对应表
dat <- data.frame("object" = rep(1:i, each = j)) %>% 
  mutate(features = paste(object, 1:j, sep = "_"))

# 生成样本列并合并到主数据框
sample_cols <- sapply(X = paste0("sample", 1:k), 
                      FUN = function(x) {sample(x = values, size = nrow(dat), replace = TRUE)}, 
                      simplify = FALSE)
dat <- cbind(dat, bind_cols(sample_cols))

2. 初始化需求跟踪表 #

创建数据框跟踪每个(对象, 特征, 取值)组合的出现次数及满足状态：

requirement_df <- expand.grid(
  object = unique(dat$object),
  feature = unique(dat$features),
  value = values,
  current_count = 0,
  satisfied = FALSE # 是否已满足≥3次的要求
)

# 将样本列转为矩阵，提升取值效率
sample_matrix <- as.matrix(dat[, paste0("sample", 1:k)])
rownames(sample_matrix) <- dat$features

3. 贪心算法主循环 #

selected_samples <- c()

# 循环直到所有需求都满足
while(sum(requirement_df$satisfied) < nrow(requirement_df)) {
  # 计算每个样本的贡献：加入后能新增多少个满足的需求
  sample_contributions <- sapply(colnames(sample_matrix), function(sample_col) {
    sample_vals <- sample_matrix[, sample_col]
    temp_df <- requirement_df %>%
      left_join(dat %>% select(object, features) %>% rename(feature = features), by = c("object", "feature")) %>%
      mutate(sample_val = sample_vals[match(feature, rownames(sample_matrix))]) %>%
      filter(!satisfied) %>% # 只关注未满足的需求
      mutate(new_count = current_count + (sample_val == value)) %>%
      mutate(will_satisfy = new_count >= 3)
    
    sum(temp_df$will_satisfy)
  })
  
  # 选择贡献最大的样本（若有多个，取第一个）
  best_sample <- names(which.max(sample_contributions))
  selected_samples <- c(selected_samples, best_sample)
  
  # 更新需求跟踪表的计数和满足状态
  sample_vals <- sample_matrix[, best_sample]
  obj_feature_vals <- dat %>%
    select(object, features) %>%
    mutate(sample_val = sample_vals) %>%
    rename(feature = features)
  
  requirement_df <- requirement_df %>%
    left_join(obj_feature_vals, by = c("object", "feature")) %>%
    mutate(current_count = current_count + (sample_val == value)) %>%
    mutate(satisfied = current_count >= 3) %>%
    select(-sample_val)
}

# 输出结果
cat("最少需要的样本数量：", length(selected_samples), "\n")
cat("选中的样本列表：", paste(selected_samples, collapse = ", "), "\n")

4. 结果验证 #

运行以下代码确认所有需求都已满足：

verify_df <- requirement_df %>%
  group_by(object, feature) %>%
  summarise(
    count_0 = current_count[value == 0],
    count_1 = current_count[value == 1],
    count_2 = current_count[value == 2],
    all_satisfied = all(count_0 >=3, count_1 >=3, count_2 >=3)
  )

# 检查是否所有对象-特征组合都符合要求
all(verify_df$all_satisfied)

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