在數據框中查找/創建候選密鑰

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

儘管我不完全清楚以這種方式推動尋找關鍵的動機，但我認爲在確定哪些特徵組合可以唯一識別人羣中的個體時可能很有趣。

正如您所指出的那樣，詳盡的搜索可能會非常昂貴，因爲您需要檢查的變量可能存在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數據集，此運行在大約半秒，並返回1276個不同之處在於可以用作鍵的列的組合;沒有一列可以用作關鍵字，但有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窮舉的辦法50X快）上，並返回

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" 

當然，這仍然會表現不佳，如果唯一有效的按鍵都很大，或者如果沒有有效的密鑰，因爲我們還需要詳盡通過該變量的所有子集檢查：大小2的9個鍵案件。