Wählen Teilmenge von Spalten, die ein Kriterium in R minimieren

Question

Ich habe eine spärliches binären data.frame, die wie diese

set.seed(123) 
dat <- as.data.frame(matrix(rep(round(runif(40,0,0.9),0),5),ncol = 20)) 

# > dat 
# V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 V13 V14 V15 V16 V17 V18 V19 V20 
# 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 
# 2 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 
# 3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 
# 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
# 5 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 
# 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
# 7 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 
# 8 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 
# 9 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 
# 10 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 

I, die die Anzahl der Nullen erhalten minimieren Nötige zu finden, die 3 Spalten aussehen, wenn ich rowSums auf den Teilnehmer anrufen Säulen.

Beispiel:

# > rowSums(dat[,1:3]) 
# [1] 2 2 2 3 2 2 0 2 0 1 
# 
# > rowSums(dat[,2:4]) 
# [1] 3 2 3 3 1 2 1 1 0 1 

hier, wenn ich rowSums auf den ersten 3 Spalten nennen erhalte ich 2 Nullen, während, wenn ich rowSums auf Spalten nennen 2:4 ich nur eine 0 bekommen, so würde die zweite Lösung bevorzugt werden .

Natürlich, ich brauche nicht die Spalten nebeneinander zu sein, wenn ich rowSums anwenden, so dass ich alle möglichen Kombinationen erforschen müssen (zB: Ich rowSums auch den Fall ov V1+V5+V17, zu prüfen, wollen .. .), und wenn es mehrere "optimale" Lösungen gibt, ist es in Ordnung für mich, nur einen von ihnen zu behalten.

Beachten Sie, dass meine echte data.frame 220.000 Zeilen x 200 Spalten ist, also brauche ich einen effizienten Ansatz in Bezug auf Zeit/Speicherverbrauch.

Answer 1

Dies ist die naheliegendste Lösung, obwohl wahrscheinlich nicht sehr gut skalieren:

which.min(combn(dat,3L,function(x) sum(rowSums(x)==0))); 
## [1] 2 

Der Ausgangswert von 2 kann als ein Kombinationsindex gedacht werden. Sie können die Spalten erhalten, die von combn() auf dem gesamten Spaltenindex läuft zu dieser Kombination gehört Satz des Eingabeobjekts und Indizierung darauf hin, dass bestimmte Kombination von Indizes:

cis <- combn(seq_along(dat),3L)[,2L]; 
cis; 
## [1] 1 2 4 

Und dann die Spaltennamen bekommen ist einfach:

names(dat)[cis]; 
## [1] "V1" "V2" "V4" 

Sie die Anzahl der Nullen in der Lösung erhalten können wie folgt:

sum(rowSums(dat[,cis])==0); 
## [1] 1 

---

Ich habe eine viel schnellere Lösung in Rcpp geschrieben.

Um die Funktion generischer zu machen, habe ich es geschrieben, um eine logische Matrix anstelle eines dat.frame zu nehmen, mit dem Design, die Spaltenkombination mit den wenigsten wahrheitsgetreuen Zeilen zu finden. In diesem Fall können Sie das Argument als dat==0 berechnen. Ich habe auch die Anzahl der Spalten in der Kombination als zweiten Parameter r parametrisiert, die für Ihren Fall 3 sein wird.

library(Rcpp); 
Sys.setenv('PKG_CXXFLAGS'='-std=c++11'); 

cppFunction(' 
    IntegerVector findColumnComboWithMinimumAllTrue(LogicalMatrix M,int r) { 
     std::vector<int> rzFull(M.nrow()); std::iota(rzFull.begin(),rzFull.end(),0); 
     std::vector<int> rzErase; 
     std::vector<std::vector<int>> rzs(M.ncol(),std::vector<int>(M.nrow())); 
     std::vector<std::vector<int>*> rzps(M.ncol()); 
     std::vector<int>* rzp = &rzFull; 
     std::vector<int> com(r); 
     int bestAllTrueCount = M.nrow()+1; 
     std::vector<int> bestCom(r); 
     int pmax0 = M.ncol()-r; 
     int p = 0; 
     while (true) { 
      rzErase.clear(); 
      for (int rzi = 0; rzi < rzp->size(); ++rzi) 
       if (!M((*rzp)[rzi],com[p])) rzErase.push_back(rzi); 
      if (p+1==r) { 
       if (rzp->size()-rzErase.size() < bestAllTrueCount) { 
        bestAllTrueCount = rzp->size()-rzErase.size(); 
        bestCom = com; 
       } 
       if (com[p]==pmax0+p) { 
        do { 
         --p; 
        } while (p >= 0 && com[p]==pmax0+p); 
        if (p==-1) break; 
        ++com[p]; 
        rzp = p==0 ? &rzFull : rzps[p-1]; 
       } else { 
        ++com[p]; 
       } 
      } else { 
       if (rzErase.empty()) { 
        rzps[p] = rzp; 
       } else { 
        rzs[p].clear(); 
        int rzi = -1; 
        for (int ei = 0; ei < rzErase.size(); ++ei) 
         for (++rzi; rzi < rzErase[ei]; ++rzi) 
          rzs[p].push_back((*rzp)[rzi]); 
        for (++rzi; rzi < rzp->size(); ++rzi) 
         rzs[p].push_back((*rzp)[rzi]); 
        rzp = rzps[p] = &rzs[p]; 
       } 
       ++p; 
       com[p] = com[p-1]+1; 
      } 
     } 
     IntegerVector res(bestCom.size()); 
     for (int i = 0; i < res.size(); ++i) 
      res[i] = bestCom[i]+1; 
     return res; 
    } 
'); 

Hier ist eine Demo auf Ihrem Beispiel Eingabe:

set.seed(123L); 
dat <- as.data.frame(matrix(rep(round(runif(40,0,0.9),0),5),ncol=20L)); 
findColumnComboWithMinimumAllTrue(dat==0,3L); 
## [1] 1 2 4 

Und hier ist ein Full-Size-Test, der fast 10 Minuten auf meinem System nimmt:

set.seed(1L); NR <- 220e3L; NC <- 200L; 
dat <- as.data.frame(matrix(sample(0:1,NR*NC,T),NR,NC)); 
system.time({ findColumnComboWithMinimumAllTrue(dat==0,3L); }); 
## user system elapsed 
## 555.641 0.328 556.401 
res; 
## [1] 28 64 89