Найти уникальный набор идентификаторов / групп среди нескольких столбцов - PullRequest
Новая
       16

Найти уникальный набор идентификаторов / групп среди нескольких столбцов

1 голос
/ 11 июня 2019

У меня есть данные с двумя (потенциально более) столбцами идентификаторов (обычно это длинные строки). Они иногда отличаются, опечатки или меняются с течением времени. Я хочу идентифицировать уникальные предметы в данных. Это требует идентификации групп дел, которые связаны через их идентификаторы на некотором уровне.

Пример 

df <- data.frame(ida = c("A", "B", "C", "C", "D", "E"),
                 idb = c(1, 1, 3, 4, 4, 7),
                 trueid = c("id1", "id1", "id2", "id2", "id2", "id3"))

> df
  ida idb trueid
1   A   1    id1
2   B   1    id1
3   C   3    id2
4   C   4    id2
5   D   4    id2
6   E   7    id3

Идентификаторы для id1: "A", "B", 1, для id2 "C", "D", 3, 4 и для id3 "E", 7.

Я не знаю trueid, но нужно найти его, используя информацию из столбцов ida и idb.

Решение должно масштабироваться до миллионов наблюдений с десятками тысяч уникальных идентификаторов. Я уже использую data.table.

Расширение : существует другой сценарий, в котором имеется более двух столбцов, и некоторые столбцы могут быть информативными для других, т. Е. Иметь одинаковые идентификаторы. Я не знаю, какие столбцы являются информативными для каких. Я думаю, что тип можно игнорировать, хотя все столбцы являются строками или могут быть безопасно преобразованы.

Еще один пример для этого: 

df <- data.frame(ida = c("A", "B", "C", "C", "D", "E"),
                 idb = c("1", "2", "3", "4", "4", "7"),
                 idc = c("1", "1", "2", "3", "4", "5"),
                 idd = c("1", "A", "2", "3", "4", "5"),
                 trueid = c("id1", "id1", "id1", "id1", "id1", "id2"))

> df
  ida idb idc idd trueid
1   A   1   1   1    id1
2   B   2   1   A    id1
3   C   3   2   2    id1
4   C   4   3   3    id1
5   D   4   4   4    id1
6   E   7   5   5    id2

Редактировать: Как отметил комментатор, это по сути проблема клики нахождения полных подграфов в графе. Прочитав немного больше, я понимаю, что эту проблему можно решить с помощью library(igraph). Я оставляю вопрос открытым, так как предпочел бы решение, основанное на base, data.table или dplyr. Я не могу легко установить пакеты на сервере, который я использую, установка igraph требует большого количества волокиты и задержек.

Edit2: Для тех, кто читает это и сталкивается с подобной проблемой: zx8754 ответ с использованием igraph значительно (на несколько порядков) быстрее для больших (смоделированных) данных с большим количеством групп. Если у вас есть возможность использовать igraph, сделайте это.

Ответы [ 2 ]

4 голосов
/ 12 июня 2019

Использование igraph : 

# example input, I removed "trueid" column
df <- data.frame(ida = c("A", "B", "C", "C", "D", "E"),
                 idb = c("1", "2", "3", "4", "4", "7"),
                 idc = c("1", "1", "2", "3", "4", "5"),
                 idd = c("1", "A", "2", "3", "4", "5"))
#trueid = c("id1", "id1", "id1", "id1", "id1", "id2")

library(igraph)

# set up connections
# Improved version suggested by @thelatemail in the comments
x <- cbind(df[ 1 ], unlist(df[ -1 ]))

# original clumsy version (do not use)
# x <- unique(do.call(rbind, lapply(1:(ncol(df) - 1), function(i) setNames(df[, c(i, i + 1) ], c("from", "to")))))

# convert to graph object
g <- graph_from_data_frame(x)        

# plot if you wish to visualise
plot(g)

enter image description here

# this is the solution, add membership ids to original input dataframe
merge(df, data.frame(grp = clusters(g)$membership),
      by.x = "ida", by.y = 0)
#   ida idb idc idd grp
# 1   A   1   1   1   1
# 2   B   2   1   A   1
# 3   C   3   2   2   1
# 4   C   4   3   3   1
# 5   D   4   4   4   1
# 6   E   7   5   5   2
1 голос
/ 12 июня 2019

Вот рекурсивный подход с использованием data.table: 

#convert into a long format for easier processing
mDT <- melt(DT[, rn := .I], id.var="rn", variable.name="V", value.name="ID")[,
    tid := NA_integer_]

#the recursive function
link <- function(ids, label) {
    #identify the rows in DT containing ids and extract the IDs
    newids <- mDT[mDT[.(ID=ids), on=.(ID), .(rn=rn)], on=.(rn), allow.cartesian=TRUE,
        unique(ID)]

    #update those rows to the same group
    mDT[mDT[.(ID=ids), on=.(ID), .(rn=rn)], on=.(rn), tid := label]

    if (length(setdiff(newids, ids)) > 0L) {
        #call the recursive function if there are new ids
        link(newids, label)
    }
}

#get the first id that is not labelled yet
id <- mDT[is.na(tid), ID[1L]]
grp <- 1L
while(!is.na(id)) {
    #use recursive function to link them up
    link(id, grp)

    #repeat for next id that is not part of any group yet
    id <- mDT[is.na(tid), ID[1L]]
    grp <- grp + 1L
}

#update original DT with tid
DT[mDT, on=.(rn), tid := tid]

данные: 

library(data.table)
DT <- data.table(ida = c("A", "B", "C", "C", "D", "E"),
    idb = c("1", "2", "3", "4", "4", "7"),
    idc = c("1", "1", "2", "3", "4", "5"),
    idd = c("1", "A", "2", "3", "4", "5"))
...