Быстрый способ группировки переменных на основе прямого и косвенного сходства в нескольких столбцах

У меня относительно большой набор данных (1 750 000 строк, 5 столбцов), который содержит записи с уникальными значениями идентификаторов (первый столбец), описанные по четырем критериям (4 других столбца). Небольшой пример будет:

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

Все стало еще хуже, потому что я могу найти эти записи с дублированными описаниями прямо и косвенно. Поэтому сейчас я делаю эту операцию в два этапа.

ШАГ 1 - Построение дублированных идентификаторов на основе прямых дубликатов

Эта операция приводит к следующему, с уникальным дублированным идентификатором, определенным как "new.id":

Обратите внимание, что записи "b3" и "c7" дублируются косвенно через "a1" (все остальные примеры являются прямыми дубликатами, которые должны оставаться неизменными). Вот почему нам нужен следующий шаг.

ШАГ 2 - Обновление дублированных идентификаторов на основе косвенных дубликатов

Обратите внимание, что теперь первые три записи ("a1", "b3", "c7") сгруппированы под более широким дублированным идентификатором, который содержит как прямые, так и косвенные записи.

Все работает хорошо, но мой код ужасно медленный. Потребовалось 2 полных дня, чтобы запустить половину набора данных (~ 800,0000). Я мог бы распараллелить цикл на разные ядра, но все равно это заняло бы часы. И я почти уверен, что мог бы использовать функции data.table лучше, возможно, используя set в цикле. Я потратил часы сегодня, пытаясь реализовать те же самые коды, используя data.table, но я новичок в его синтаксисе, и мне действительно трудно здесь. Любые предложения о том, как я мог бы оптимизировать этот код?

Примечание. Самая медленная часть кода - это цикл, а внутри цикла самый неэффективный шаг - это grepl() шаблонов внутри data.table. Кажется, что установка "ключа" для data.table может ускорить процесс, но я не изменил время, необходимое для выполнения grepl() в моем случае.

Ответы

Ответ 1

Вы можете подходить к этому как к проблеме сети. Здесь я использую функции из пакета igraph. Основные шаги:

melt данные в длинный формат.
Используйте graph_from_data_frame для создания графа, где столбцы "id" и "value" обрабатываются как список ребер.
Используйте components чтобы получить связанные компоненты графа, то есть, какие "идентификаторы" связаны через их критерии, прямо или косвенно.
Выберите элемент membership чтобы получить "идентификатор кластера, которому принадлежит каждая вершина".
Присоединиться к членству к исходным данным.
Объединение идентификатора, сгруппированного по принадлежности к кластеру.

library(igraph)

# melt data to long format, remove NA values
d <- melt(dt, id.vars = "id", na.rm = TRUE)

# convert to graph
g <- graph_from_data_frame(d[ , .(id, value)])

# get components and their named membership id 
mem <- components(g)$membership

# add membership id to original data
dt[.(names(mem)), on = .(id), mem := mem] 

# for groups of length one, set 'mem' to NA
dt[dt[, .I[.N == 1], by = mem]$V1, mem := NA]

При желании объедините 'id' по столбцу 'mem' (для non- NA 'mem') (IMHO, это только усложняет дальнейшие манипуляции с данными;)). Во всяком случае, здесь мы идем:

dt[!is.na(mem), id2 := paste(id, collapse = "|"), by = mem]

#     id   s1   s2 s3   s4  mem      id2
#  1: a1    a    d  f    h    1 a1|b3|c7
#  2: b3    b    d  g    i    1 a1|b3|c7
#  3: c7    c    e  f    j    1 a1|b3|c7
#  4: d5    l    k  l    m    2    d5|e3
#  5: e3    l    k  l    m    2    d5|e3
#  6: f4    o    o  s    o    3 f4|g2|h1
#  7: g2    o    o  r    o    3 f4|g2|h1
#  8: h1    o    o  u    o    3 f4|g2|h1
#  9: i9 <NA> <NA>  w <NA>   NA     <NA>
# 10: j6 <NA> <NA>  z <NA>   NA     <NA>

Базовый график графика в этом небольшом примере, просто для иллюстрации связанных компонентов:

plot(g, edge.arrow.size = 0.5, edge.arrow.width = 0.8, vertex.label.cex = 2, edge.curved = FALSE)

Ответ 2

Я думаю, что этот рекурсивный подход делает то, что вы хотите. По сути, он выполняет самостоятельное соединение для каждого столбца, по одному за раз, и, если сопоставляется более одной строки (т.е. Строк, отличных от рассматриваемой строки), он сохраняет все уникальные идентификаторы из совпадения. Это позволяет избежать использования строк с NA, используя вторичные индексы. Хитрость в том, что мы делаем рекурсию дважды, один раз с id s, и снова, но с вновь созданными new_id s.

dt[, new_id := .(list(character()))]

get_ids <- function(matched_ids, new_id) {
  if (length(matched_ids) > 1L) {
    list(unique(
      c(new_id[[1L]], unlist(matched_ids))
    ))
  } else {
    new_id
  }
}

find_recursively <- function(dt, cols, pass) {
  if (length(cols) == 0L) return(invisible())

  current <- cols[1L]
  next_cols <- cols[-1L]

  next_dt <- switch(
    pass,

    first = dt[!list(NA_character_),
               new_id := dt[.SD, .(get_ids(x.id, i.new_id)), on = current, by = .EACHI]$V1,
               on = current],

    second = dt[!list(NA_character_),
                new_id := dt[.SD, .(get_ids(x.new_id, i.new_id)), on = current, by = .EACHI]$V1,
                on = current]
  )

  find_recursively(next_dt, next_cols, pass)
}

find_recursively(dt, paste0("s", 1:4), "first")
find_recursively(dt, paste0("s", 1:4), "second")

dt[, new_id := sapply(new_id, function(nid) {
  ids <- unlist(nid)
  if (length(ids) == 0L) {
    NA_character_
  } else {
    paste(ids, collapse = "|")
  }
})]

print(dt)
    id   s1   s2 s3   s4   new_id
 1: a1    a    d  f    h a1|b3|c7
 2: b3    b    d  g    i a1|b3|c7
 3: c7    c    e  f    j a1|c7|b3
 4: d5    l    k  l    m    d5|e3
 5: e3    l    k  l    m    d5|e3
 6: f4    o    o  s    o f4|g2|h1
 7: g2    o    o  r    o f4|g2|h1
 8: h1    o    o  u    o f4|g2|h1
 9: i9 <NA> <NA>  w <NA>     <NA>
10: j6 <NA> <NA>  z <NA>     <NA>

Объединение использует эту идиому.