Finding/creating 数据框中的候选键

Question

我正在寻找一种方法来确定 data.frame 中的候选键。

举个简单的例子，如果我有一个data.frame:

df <- data.frame(Col1 = c("A", "A", "B", "B", "C", "C"), Col2 = c(1, 2, 1, 2, 1, 2))

那么很明显，Col1 或 Col2 不是单独唯一标识每一行的键，但 Col1+Col2 的串联是。

通过比较 length(unique(df$column)) == nrow(df).

可以找到可以用作键的单个列

但是如果我的 data.frame 包含很多列并且没有任何一列是键，那么可能是两列的串联。

问题是，我怎样才能找出哪两个可以解决问题？哪三个？等。我意识到这可能是一个指数增长的穷举搜索，但我想知道是否有更好的方法。

我已经编写了代码来至少搜索所有可能的 2 列组合，但它非常麻烦。

Answer 1

虽然我不完全清楚是什么促使以这种方式找到密钥，但我认为确定哪些特征组合可以唯一地识别群体中的个体可能会很有趣。

正如您所指出的，详尽搜索可能非常昂贵，因为您需要检查 k 个变量的 2^k 个可能子集。尽管如此，它仍然易于编码并提供运行时基准：

all.keys <- function(dat) {
  combos <- tail(expand.grid(sapply(dat, function(x) c(F, T), simplify=FALSE)), -1)
  nunique <- unlist(apply(combos, 1, function(x) nrow(unique(dat[,x,drop=FALSE]))))
  combos[nunique == nrow(dat),]
}

对于 11 列的 mtcars 数据集，运行时间约为半秒，returns 1,276 种不同的列组合可用作键；没有单个列可以用作键，但可以使用 9 对列。

dim(all.keys(mtcars))
# [1] 1276   11
head(all.keys(mtcars))
#     mpg   cyl  disp    hp  drat   wt  qsec    vs    am  gear  carb
# 34 TRUE FALSE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE
# 36 TRUE  TRUE FALSE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE
# 38 TRUE FALSE  TRUE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE
# 40 TRUE  TRUE  TRUE FALSE FALSE TRUE FALSE FALSE FALSE FALSE FALSE
# 42 TRUE FALSE FALSE  TRUE FALSE TRUE FALSE FALSE FALSE FALSE FALSE
# 44 TRUE  TRUE FALSE  TRUE FALSE TRUE FALSE FALSE FALSE FALSE FALSE
table(rowSums(all.keys(mtcars)))
#   2   3   4   5   6   7   8   9  10  11 
#   9  52 148 266 322 266 148  53  11   1

对于包含许多列的数据集，尝试有效地计算所有可能的键可能是无望的，因为有效键的数量可能会随着变量的数量呈指数增长。我们可能有机会有效地找到尽可能小的密钥大小（在本例中为大小为 2 的密钥）。一种直接的方法是遍历密钥大小并在找到该大小的有效密钥后停止：

small.keys <- function(dat) {
  for (size in 1:ncol(dat)) {
    keys <- combn(names(dat), size)
    nunique <- apply(keys, 2, function(x) nrow(unique(dat[,x,drop=FALSE])))
    if (sum(nunique == nrow(dat)) > 0) {
      return(t(keys[,nunique == nrow(dat)]))
    }
  }
  return(NULL)
}

这在我的计算机上运行不到 10 毫秒（比 mtcars 的详尽方法快 50 倍）并且 returns 9 个大小为 2 的键：

small.keys(mtcars)
#       [,1]   [,2]  
#  [1,] "mpg"  "wt"  
#  [2,] "mpg"  "qsec"
#  [3,] "cyl"  "qsec"
#  [4,] "disp" "qsec"
#  [5,] "hp"   "qsec"
#  [6,] "drat" "qsec"
#  [7,] "wt"   "qsec"
#  [8,] "qsec" "am"  
#  [9,] "qsec" "carb"

当然，如果唯一的有效键很大或没有有效键，这仍然会表现不佳，因为在这种情况下我们仍然需要详尽地检查所有变量子集。

Finding/creating 数据框中的候选键

Finding/creating candidate key(s) in a data frame

r

key