r - 如果行具有相似的元素，则保留较短的行

Question

我有一个数据框，如下所示。

dataframe

复制数据:

x <- data.frame(cluster=c(1,2,3,4,5),
                groups=c('20000127 20000128',
                         '20000127 20000128 20000134',
                         '20000129 20000130 20000131 20000132',
                         '20000133 20000134 20000135 20000136',
                         '20000128 20000133 20000134 20000135 20000136'),
                chr=c(17,26,35,35,44), stringsAsFactors=FALSE)

我试图想出一种方法来分析具有相似元素的任何组的“组”列，并删除计数较高的行。

例如，
元素 20000128 出现在第 1,2 和 5 行中。由于第 1 行的字符数较少，我想删除第 2 行和第 5 行。感谢您的帮助!

理想情况下，最终结果应该只有集群 1、3、4。每个元素应该只出现一次。 (字符数最少的簇)

Answer 1

探索这个问题很有趣。我了解到这是 set cover problem 的变体并且是 NP Complete .

这将有助于了解您的问题的范围。如果我们谈论的是 10 个集群，我们可以使用蛮力。如果是数千个集群，我们将不得不使用近似值。

我了解到有一个 R 实现 greedy algorithm在 RcppGreedySetCover包裹。

首先，我们需要转换为两列长格式。我们可以使用 dplyr .

library(tidyverse)
longx <- x %>% 
    mutate(splitgroups = strsplit(as.character(groups), " ")) %>%
    unnest(splitgroups) %>% select(cluster, splitgroups)

然后我们可以使用 greedySetCover来近似覆盖所有元素的最小集合。

library(RcppGreedySetCover)
greedySetCover(longx)
#100% covered by 3 sets.
#    cluster splitgroups
# 1:       2    20000127
# 2:       3    20000129
# 3:       3    20000130
# 4:       3    20000131
# 5:       3    20000132
# 6:       5    20000128
# 7:       5    20000133
# 8:       5    20000134
# 9:       5    20000135
#10:       5    20000136

这表明 2,3 和 5 的集合涵盖了所有内容。但这并不能完全回答您的问题，因为正如您所知，有一组较短的集群。

然而，我们了解到，最小集合是 3 个集群。现在我们可以测试 3 个集群的所有组合。

set.size <- length(unique(greedySetCover(longx)$cluster))
binary.matrix <- table(longx)
combinations <- combn(unique(x$cluster),set.size)

total.lengths <- apply(combinations,2,function(x){
  if(sum(as.logical(colSums(binary.matrix[x,]))) == ncol(binary.matrix))
    {sum(rowSums(binary.matrix[x,]))} 
  else {NA}})

min.length <- min(total.lengths,na.rm = TRUE)
min.set <- combinations[,which(total.lengths == min.length)]
x[min.set,]
#  cluster                              groups chr
#1       1                   20000127 20000128  17
#3       3 20000129 20000130 20000131 20000132  35
#4       4 20000133 20000134 20000135 20000136  35

数据

x <- data.frame(cluster=c(1,2,3,4,5),
                groups=c('20000127 20000128',
                         '20000127 20000128 20000134',
                         '20000129 20000130 20000131 20000132',
                         '20000133 20000134 20000135 20000136',
                         '20000128 20000133 20000134 20000135 20000136'),
                chr=c(17,26,35,35,44), stringsAsFactors=FALSE)