多数值列容差范围内高效分组行的实现方案问询

针对你提出的多维度容差分组需求，我整理了几种可靠的实现方法，既能满足双指标容差+传递性分组的核心要求，也能解决你之前用igraph时遇到的错误分组问题（比如Row20、21、22被错误归组的情况）。

先明确你的核心规则 #

我们的分组逻辑要严格遵循：

• 按Name独立分组，A的组和B的组完全不交叉
• 同一组内的所有行，必须通过连续的符合双容差的行对连接（传递性）：即如果行A和行B符合容差，行B和行C符合容差，那A、B、C同组；若行A和B不符合，B和C不符合，哪怕A和C直接符合，也不能同组
• 双容差标准：|Time1_i - Time1_j| ≤ 2 且 |Time2_i - Time2_j| ≤ 0.05

你的输入数据（方便复现） #

input <- data.frame(
  Row_number = 1:22,
  Name = c(rep("A",6), rep("B",4), rep("A",12)),
  Time1 = c(1236, 1236, 1235, 1237, 1287, 1288, 570, 1092, 1092, 1092, 1236, 1237, 1238, 2000, 2001, 2003, 1500, 1502, 1504, 3000, 3002, 3004),
  Time2 = c(2.315, 2.317, 2.314, 3.012, 4.360, 4.358, 2.602, 2.603, 2.605, 2.610, 2.320, 2.360, 2.400, 5.000, 5.010, 5.015, 6.000, 6.050, 6.100, 1.000, 10.000, 1.040)
)

方案1：修正后的igraph连通分量方法（推荐，兼顾准确性和效率） #

你之前的igraph方法出错，大概率是因为先按单指标粗分组再处理另一指标，破坏了双指标同时满足的传递性。正确的做法是：在每个Name子集中，把每一行看作节点，只有当两行同时满足双容差时才连边，然后所有连通的节点就是一个组。

代码实现 #

library(igraph)
library(dplyr)

# 定义容差参数
tol_time1 <- 2
tol_time2 <- 0.05

# 分组处理
result <- input %>%
  group_by(Name) %>%
  group_modify(function(sub_df, name_grp) {
    n_rows <- nrow(sub_df)
    # 生成邻接矩阵：判断每对行是否同时符合双容差
    adj_matrix <- outer(1:n_rows, 1:n_rows, function(i, j) {
      abs(sub_df$Time1[i] - sub_df$Time1[j]) <= tol_time1 & 
        abs(sub_df$Time2[i] - sub_df$Time2[j]) <= tol_time2
    })
    # 构建无向图，提取连通分量
    graph <- graph_from_adjacency_matrix(adj_matrix, mode = "undirected", diag = FALSE)
    cluster_id <- components(graph)$membership
    # 生成组名
    sub_df$Group_Name <- paste0(name_grp$Name, "_", cluster_id)
    return(sub_df)
  }) %>%
  ungroup() %>%
  # 按组名和行号排序，和你的示例输出对齐
  arrange(Group_Name, Row_number)

# 验证Row20-22的分组（正确应该是三个独立组）
result %>% filter(Row_number %in% 20:22)

输出结果（Row20-22部分） #

# A tibble: 3 × 5
  Row_number Name  Time1 Time2 Group_Name
       <int> <chr> <dbl> <dbl> <chr>     
1         20 A      3000  1    A_6       
2         21 A      3002 10    A_7       
3         22 A      3004  1.04 A_8       

完全符合你的预期，不会错误关联这三行。

方案2：DBSCAN密度聚类（适合超大数据量） #

如果你的数据量很大（比如10万行以上），生成全量邻接矩阵会占用过多内存，这时候可以用密度聚类算法DBSCAN，把双容差转化为密度判断的规则。

代码实现 #

library(dbscan)
library(dplyr)

tol_time1 <- 2
tol_time2 <- 0.05

# 自定义距离函数：只有同时满足双容差的行对，距离为0；否则为1（表示不连通）
custom_distance <- function(df) {
  n <- nrow(df)
  # 向量化优化，避免双重循环（比循环快很多）
  time1_diff <- outer(df$Time1, df$Time1, "-") %>% abs()
  time2_diff <- outer(df$Time2, df$Time2, "-") %>% abs()
  dist_mat <- matrix(0, n, n)
  dist_mat[time1_diff > tol_time1 | time2_diff > tol_time2] <- 1
  return(as.dist(dist_mat))
}

# 分组处理
result_dbscan <- input %>%
  group_by(Name) %>%
  group_modify(function(sub_df, name_grp) {
    # 用DBSCAN，minPts=1表示只要连通就归为一组（等价于连通分量）
    cluster <- dbscan(custom_distance(sub_df), eps = 0.5, minPts = 1)
    sub_df$Group_Name <- paste0(name_grp$Name, "_", cluster$cluster)
    return(sub_df)
  }) %>%
  ungroup() %>%
  arrange(Group_Name, Row_number)

这个方法的优势是：向量化计算距离矩阵，比双重循环快，而且DBSCAN的底层实现更高效，适合大数据场景。

方案3：贪心逐行合并法（适合小数据，逻辑直观） #

如果你的数据量很小，也可以用最直观的贪心逻辑：逐行检查当前行是否能和已有的某个组合并（只要当前行和组内任意一行符合双容差，就合并），不能合并就新建组。

代码实现 #

library(dplyr)

tol_time1 <- 2
tol_time2 <- 0.05

result_greedy <- input %>%
  group_by(Name) %>%
  group_modify(function(sub_df, name_grp) {
    sub_df$Group_Name <- NA_character_
    current_cluster <- 1
    # 初始化第一行的组
    sub_df$Group_Name[1] <- paste0(name_grp$Name, "_", current_cluster)
    
    for (i in 2:nrow(sub_df)) {
      matched <- FALSE
      # 遍历已有的所有组
      for (grp in unique(sub_df$Group_Name[1:(i-1)])) {
        # 取当前组的所有行
        grp_rows <- sub_df[1:(i-1), ][sub_df$Group_Name[1:(i-1)] == grp, ]
        # 检查当前行是否和组内任意一行符合双容差
        if (any(abs(grp_rows$Time1 - sub_df$Time1[i]) <= tol_time1 & 
                abs(grp_rows$Time2 - sub_df$Time2[i]) <= tol_time2)) {
          sub_df$Group_Name[i] <- grp
          matched <- TRUE
          break
        }
      }
      # 没有匹配的组，新建一个
      if (!matched) {
        current_cluster <- current_cluster + 1
        sub_df$Group_Name[i] <- paste0(name_grp$Name, "_", current_cluster)
      }
    }
    return(sub_df)
  }) %>%
  ungroup() %>%
  arrange(Group_Name, Row_number)

这个方法逻辑最容易理解，但因为是双重循环，数据量大时效率会很低，适合小数据集调试用。

内容来源于stack exchange