Найти повторяющиеся группы в r data.table

Question

Мне нужно идентифицировать и дедуплицировать группы записей в таблице данных r (но я полагаю, что проблема будет одинаковой на любом языке программирования), структурированной следующим образом:

Группы идентифицируются по значениям в var1 и var2, и они являются дубликатами, если они имеют одинаковый размер и содержат одинаковые значения в var2 и var3 (значения в var3 - это те, которые определены большими группами по var1 и var2 имеют общее).

Таким образом, в примере 2 красные группы являются дубликатами, но пара (красный, синий) и пара (красный, коричневый) не являются.

Мое решение состоит в том, чтобы переместить таблицу в широкий формат

, а затем выполнить unique(dt[,var1:=NULL]) и перенести обратно в длинный формат (мне не понадобится var1 больше на этом этапе).

Проблема в том, что моя реальная таблица содержит 165 391 868 записей, и это не одноразовая задача, а еженедельная с таблицами аналогичного размера и ограниченным временем выполнения.

я пробовал spl разбивает таблицу на куски, добавляет их, а затем выполняет дедупликацию, но первая транспонирование теперь выполняется более 2 часов!

Есть ли альтернативное и быстрое решение? Большое спасибо!

Код для создания примера таблицы:

dt <- data.table(
var1=c(
    "value1_1",
    "value1_1",
    "value1_1",
    "value1_2",
    "value1_2",
    "value1_2",
    "value1_2",
    "value1_3",
    "value1_3",
    "value1_3",
    "value1_4",
    "value1_4",
    "value1_4",
    "value1_5",
    "value1_5",
    "value1_5",
    "value1_5"),
var2=c(
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1",
    "value2_1"),
var1=c(
    "value3_1",
    "value3_2",
    "value3_3",
    "value3_2",
    "value3_4",
    "value3_5",
    "value3_6",
    "value3_1",
    "value3_2",
    "value3_3",
    "value3_1",
    "value3_2",
    "value3_4",
    "value3_1",
    "value3_2",
    "value3_3",
    "value3_5"))

Answer 1

Вот еще 2 варианта:

1) Свертывание var3 в одно значение для объединения

lu <- dt[, paste(var3, collapse=""), .(var1, var2)]

samegrp <- lu[lu, on=.(V1)][
    var1!=i.var1 & var2==i.var2, 
    .(var1=c(var11, var12), g=.GRP),
    .(var11=pmin(var1, i.var1), var12=pmax(var1, i.var1), var2)]

dt[samegrp, on=.(var1, var2), g := g]

вывод:

        var1     var2     var3  g
 1: value1_1 value2_1 value3_1  1
 2: value1_1 value2_1 value3_2  1
 3: value1_1 value2_1 value3_3  1
 4: value1_2 value2_1 value3_2 NA
 5: value1_2 value2_1 value3_4 NA
 6: value1_2 value2_1 value3_5 NA
 7: value1_2 value2_1 value3_6 NA
 8: value1_3 value2_1 value3_1  1
 9: value1_3 value2_1 value3_2  1
10: value1_3 value2_1 value3_3  1
11: value1_4 value2_1 value3_1 NA
12: value1_4 value2_1 value3_2 NA
13: value1_4 value2_1 value3_4 NA
14: value1_5 value2_1 value3_1 NA
15: value1_5 value2_1 value3_2 NA
16: value1_5 value2_1 value3_3 NA
17: value1_5 value2_1 value3_5 NA

2) Соответствие count:

setkey(dt, var1, var2, var3)
count <- dt[, .N, .(var1, var2)]

matches <- dt[dt, on=.(var2, var3), allow.cartesian=TRUE, nomatch=0L][
    var1!=i.var1,
    .(N=.N / 2, g=.GRP),
    .(var11=pmin(i.var1, var1), var12=pmax(i.var1, var1), var2)]

matches[count, on=.(var11=var1, var2, N), nomatch=0L][
    count, on=.(var12=var1, var2, N), nomatch=0L]

output:

      var11    var12     var2 N g
1: value1_1 value1_3 value2_1 3 1

2-й метод требует больше памяти и, следовательно, может быть медленнее. Но фактическая производительность действительно зависит от характеристик фактического набора данных. Например, типы данных столбцов, количество уникальных пар var1 и var2, количество уникальных значений var3, et c.

Answer 2

Это работает, но я понятия не имею о его эффективности (честно говоря, это, вероятно, медленнее, но это другой подход). Я построил функцию мультифильтрации для другого проекта, и мне пришло в голову использовать ее здесь. Multifilter разбивает фрейм данных на список фреймов данных в соответствии с уникальными комбинациями переменных, найденными в любых столбцах, которые вы ему предоставляете. Затем мы проверяем дубликаты var 3 и удаляем их. Наконец набор данных восстановлен.

multifilter <- function(data,filterorder){  
  newdata <- list(data)
  for(i in rev(filterorder)){
    newdata <- unlist(lapply(sort(unique(data[,i])), function(x) lapply(newdata, function(y) y[y[,i]==x,])),recursive=F)
  }
  return(newdata[sapply(newdata,nrow)>=1])
}


filtereddt <- multifilter(dt,c("var1","var2"))
filtereddt <- filtereddt[-duplicated(lapply(filtereddt, function(x) x[,3]))]
filtereddt <- do.call(rbind, filtereddt)[,-1]

вывод:

> filtereddt
       var2     var3
4  value2_1 value3_2
5  value2_1 value3_4
6  value2_1 value3_5
7  value2_1 value3_6
8  value2_1 value3_1
9  value2_1 value3_2
10 value2_1 value3_3
11 value2_2 value3_1
12 value2_2 value3_2
13 value2_2 value3_4
14 value2_1 value3_1
15 value2_1 value3_2
16 value2_1 value3_3
17 value2_1 value3_5

Answer 3

Я думаю, что у меня есть решение, но дайте мне знать, если оно не сработает, и у меня будет еще один треск.

Я только что отредактировал в ответ на ваш комментарий, добавив var2 в столбец id

Сначала создайте столбец для групп, основанных на var1 и var2

dt[,group:=paste0(var1, var2)]

Затем создайте идентификатор на основе var3 и размера

dt[,id:=paste0(paste(sort(var3), collapse=""), var2, .N), by=group]

Затем укажите каждая группа с номером в зависимости от того, первый ли это, второй, третий и т. д. c раз вы видели группу с таким идентификатором

dt[,groupN:=as.numeric(factor(group)), by=id]

Затем сохраняйте только первый раз, когда вы видите каждую группу

dt[groupN==1]