在R中选取共享至少5年数据的最大站点数量

核心思路 #

要找到最大的站点子集，使得这些站点共同拥有至少5个采样年份，本质是寻找一组年份（≥5个），覆盖这组年份的站点数最多，对应的站点就是目标集合。

步骤1：预处理数据（可选但推荐） #

先过滤掉本身采样年份不足5的站点——这类站点不可能和其他站点共享5年数据，直接排除能减少后续计算量：

library(tidyverse)

set.seed(123)
# 生成示例数据
DF <- tibble(
  Sites = 1:100,
  NYears = rbinom(100, 40, .2)
) %>%
  rowwise() %>%
  mutate(Years = list(sample(1982:2021, NYears))) %>%
  unnest(Years) %>%
  select(-NYears)

# 过滤掉年份数<5的站点
filtered_DF <- DF %>%
  group_by(Sites) %>%
  filter(n() >= 5) %>%
  ungroup()

步骤2：全局最优解法（适用于中小规模站点） #

通过枚举覆盖数靠前的年份组合，找到覆盖站点数最多的5年组合，对应的站点就是最优集合：

# 存储每个站点的采样年份集合
site_year_sets <- filtered_DF %>%
  group_by(Sites) %>%
  summarise(year_set = list(unique(Years)), .groups = "drop")

# 取覆盖站点数最多的前20个年份（减少组合枚举量）
top_years <- filtered_DF %>%
  count(Years, name = "site_count") %>%
  arrange(desc(site_count)) %>%
  slice(1:20) %>%
  pull(Years)

# 生成所有5年组合
year_combinations <- combn(top_years, 5, simplify = FALSE)

# 计算每个组合对应的有效站点数
combination_results <- map_dfr(year_combinations, function(years) {
  valid_sites <- site_year_sets %>%
    filter(map_lgl(year_set, ~all(years %in% .x))) %>%
    nrow()
  tibble(shared_years = list(years), site_count = valid_sites)
})

# 找到最优组合
best_result <- combination_results %>%
  arrange(desc(site_count)) %>%
  slice(1)

# 提取选中的站点
selected_sites <- site_year_sets %>%
  filter(map_lgl(year_set, ~all(best_result$shared_years[[1]] %in% .x))) %>%
  pull(Sites)

# 输出结果
cat("选中站点数：", length(selected_sites), "\n")
cat("共享年份：", paste(best_result$shared_years[[1]], collapse = ", "), "\n")

步骤3：贪心高效解法（适用于大规模站点） #

如果站点数量极大（如上万），枚举所有组合效率太低，用贪心算法快速得到近似最优解：

greedy_select <- function(df, min_years = 5) {
  # 第一步：选覆盖最多的年份
  year_counts <- df %>% count(Years, name = "site_count") %>% arrange(desc(site_count))
  selected_years <- c(year_counts$Years[1])
  valid_sites <- df %>% filter(Years == selected_years[1]) %>% pull(Sites)
  
  # 逐步添加年份，直到凑够5个
  while(length(selected_years) < min_years) {
    # 统计当前有效站点中各年份的覆盖数
    current_counts <- df %>%
      filter(Sites %in% valid_sites) %>%
      count(Years, name = "site_count") %>%
      arrange(desc(site_count))
    next_year <- current_counts$Years[1]
    selected_years <- c(selected_years, next_year)
    # 更新有效站点（必须包含所有已选年份）
    valid_sites <- df %>%
      filter(Sites %in% valid_sites, Years == next_year) %>%
      pull(Sites)
    if(length(valid_sites) == 0) break
  }
  list(shared_years = selected_years, selected_sites = valid_sites)
}

# 运行贪心算法
greedy_out <- greedy_select(filtered_DF, min_years = 5)
cat("贪心算法选中站点数：", length(greedy_out$selected_sites), "\n")
cat("共享年份：", paste(greedy_out$shared_years, collapse = ", "), "\n")

注意事项 #

• 全局最优解法能找到真正的最大站点集合，但计算量随年份数指数增长，仅适合中小规模数据集。
• 贪心算法效率极高，结果接近最优，适合大规模数据集。
• 如果需要共享年份数多于5，只需调整代码中的min_years参数即可。

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