在大型数据集上按组拆分和 expand.grid

Question

我有一个以下格式的 df 并尝试获取一个包含每组所有成对组合的数据框

df<-structure(list(id = c(209044052, 209044061, 209044061, 209044061,209044062, 209044062, 209044062, 209044182, 209044183, 209044295), group = c(2365686, 387969, 388978, 2365686, 387969, 388978, 2365686, 2278460, 2278460, 654238)), .Names = c("id", "group"), row.names = c(NA, -10L), class = "data.frame")

虽然 do.call(rbind, lapply(split(df, df$group), function(i) expand.grid(i$id, i$id))) 适用于小型数据框，但我运行遇到了我的大数据（约 1200 万个观测值和约 150 万组）的时间问题。

经过一些测试，我发现拆分命令似乎是瓶颈，expand.grid 也可能不是最快的解决方案。

发现 expand.grid Use outer instead of expand.grid 的一些改进这里还有一些更快的拆分替代方案 Improving performance of split() function in R? 但很难将它们与分组放在一起。

输出应该类似于

  Var1      Var2
209044061 209044061
209044062 209044061
209044061 209044062
209044062 209044062
209044061 209044061
209044062 209044061
209044061 209044062
209044062 209044062
209044295 209044295
209044182 209044182
209044183 209044182
....

另外，我想排除同一对的重复，自引用（例如 209044061 209044061 以上）并且只保留一个组合，如果它们的顺序不同（例如 [=16= 以上） ]和209044062 209044061)（没有重复的组合）。尝试 library(gtools) 使用“combinations()”但无法确定这是否会进一步减慢计算速度。

Answer 1

一种可能的解决方案是使用 data.table 和 combinat 包：

library(data.table)
setDT(df)[order(id), data.table(combinat::combn2(unique(id))), by = group]

     group        V1        V2
1: 2365686 209044052 209044061
2: 2365686 209044052 209044062
3: 2365686 209044061 209044062
4:  387969 209044061 209044062
5:  388978 209044061 209044062
6: 2278460 209044182 209044183

order(id) 在这里使用只是为了方便更好地检查结果，但可以在生产代码中跳过。

将 `combn2()` 替换为非相等连接

还有另一种方法，其中对 combn2() 的调用被非 equi 连接替换：

mdf <- setDT(df)[order(id), unique(id), by = group]
mdf[mdf, on = .(group, V1 < V1), .(group, x.V1, i.V1), nomatch = 0L,
    allow.cartesian = TRUE]

     group        V1        V2
1: 2365686 209044052 209044061
2: 2365686 209044052 209044062
3: 2365686 209044061 209044062
4:  387969 209044061 209044062
5:  388978 209044061 209044062
6: 2278460 209044182 209044183

请注意，非等连接要求数据排序。

基准

第二种方法好像快多了

# create benchmark data
nr <- 1.2e5L # number of rows
rg <- 8L # number of ids within each group
ng <- nr / rg # number of groups
set.seed(1L)
df2 <- data.table(
  id = sample.int(rg, nr, TRUE),
  group = sample.int(ng, nr, TRUE)
)

#benchmark code
microbenchmark::microbenchmark(
  combn2 = df2[order(group, id), data.table((combinat::combn2(unique(id)))), by = group],
  nej = {
    mdf <- df2[order(group, id), unique(id), by = group]
    mdf[mdf, on = .(group, V1 < V1), .(group, x.V1, i.V1), nomatch = 0L,
        allow.cartesian = TRUE]},
  times = 1L)

对于 120000 行和 14994 个组，时间是：

Unit: milliseconds
   expr        min         lq       mean     median         uq        max neval
 combn2 10259.1115 10259.1115 10259.1115 10259.1115 10259.1115 10259.1115     1
    nej   137.3228   137.3228   137.3228   137.3228   137.3228   137.3228     1

警告

正如指出的那样，每个 group 的 id 的数量在内存消耗和速度方面至关重要。组合数为O(n²)，正好是n * (n-1) / 2 或 choose(n, 2L) 如果 n 是 id 的数量。

最大组的大小可以通过

找到

df2[, uniqueN(id), by = group][, max(V1)]

最终结果的总行数可以通过

提前计算出来

df2[, uniqueN(id), by = group][, sum(choose(V1, 2L))]

在大型数据集上按组拆分和 expand.grid

split and expand.grid by group on large data set

expand

split

r

将 combn2() 替换为 非相等连接

基准

警告

将 `combn2()` 替换为非相等连接