查找多个列中是唯一的标识符组/组(Find unique set of identifiers/gr

我有标识符的两（可能更）列（通常为长字符串）数据。 有时这些不同，是拼写错误，或随时间而改变。 我想识别数据的唯一主题。 这需要识别其在一定程度上通过它们的ID连接箱子群组。

一个例子

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 。

该解决方案需要扩展到数百万的观察与唯一ID数以万计。 我已经使用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 ，这样做。

Answer 1:

Here is a recursive approach using 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]

data:

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"))

Answer 2:

使用的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)

# 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

文章来源: Find unique set of identifiers/groups among several columns