R:如何从向量/数据帧列表中识别最小代表性向量/行集

Question

我有一个向量列表，每个向量都包含一些元素。我想确定具有最大独特元素覆盖率的最少数量的向量。例如，如果向量表示为二进制数据帧中的行，唯一元素在列中，如下所示:

    >df<- data.frame(a=c(1,0,0,0,0),b=c(1,1,1,1,0),c=c(1,0,1,1,1),d=c(0,0,0,1,1),e=c(0,0,0,1,1), f=c(0,0,0,0,1))
    > df
        a b c d e f
      1 1 1 1 0 0 0
      2 0 1 0 0 0 0
      3 0 1 1 0 0 0
      4 0 1 1 1 1 0
      5 0 0 1 1 1 1

假设向量是从 1 到 5 的行，并且它们包含元素 a 到 f 的不同组合。我想获得覆盖尽可能多元素的最小代表向量或行。在这个例子中，最小代表(最大简约)向量是第 1 行和第 5 行。有没有办法从统计上做到这一点？我尝试在双向聚类热图中可视化数据集以手动识别最小组合。然而，是否有一种统计方法可以处理这个问题并能够提供一些选择性能的数字度量？

另一个例子来说明我的问题。给定以下向量:

    > vec.1 <- c("a", "c", "d")
    > vec.2 <- c("a", "b", "c", "d")
    > vec.3 <- c("b","e")
    > vec.4 <- c("b", "c", "d", "g")
    > vec.5 <- c("f","g")

最小组合是 2,3 和 5，因为它们涵盖了从 a 到 g 的所有元素，重叠最少。在较大的数据集中，可能有多个答案，但是，组合中的向量数量越少越好。谢谢。

Answer 1

一种解决方案是计算行之间的“重叠”并提取具有最大重叠的行对，如下所示:

m <- apply(df, 1, function(x) apply(df, 1, function(y) sum(x | y)))
which(m == max(m), arr.ind = TRUE)

结果输出是:

     row col
[1,]   5   1
[2,]   1   5

您可以选择任一组合(因为第 1 行与第 5 行以及第 5 行与第 1 行相同)。

虽然这个方法使用了 n^2 个操作。不确定是否有更有效的包/算法来找到最大汉明距离行对，这似乎是您想要的。