1

data.frame私はこのようなスパースバイナリを持っています

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

これらの列を呼び出すときに取得されるゼロの数を最小限に抑える 3 つの列を見つける必要がありrowSumsます。

例： 

 # > 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

ここrowSumsで、最初の 3 列を呼び出すと 2 つのゼロを取得しますがrowSums、列を呼び出すと2:41 つしか取得しない0ため、2 番目のソリューションが優先されます。

もちろん、 を適用するときに列が隣り合っている必要はないので、考えられるすべての組み合わせを調べる必要があります (例: ov の場合も考慮しrowSumsたい...)。複数の「最適な」ソリューションがありますが、そのうちの 1 つだけを保持してもかまいません。rowSumsV1+V5+V17

私の実数data.frameは 220.000 行 x 200 列であるため、消費される時間/メモリに関して効率的なアプローチが必要であることに注意してください。

4

1 に答える 1

3

これは最も明白な解決策ですが、あまりうまくスケーリングできない可能性があります。

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

2 の出力値は、組み合わせインデックスと考えることができます。その組み合わせに属する列を取得するにcombn()は、入力オブジェクトの完全な列インデックス セットに対して実行し、その特定のインデックスの組み合わせにインデックスを付けます。

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

そして、列名を取得するのは簡単です:

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

次のように、ソリューション内のゼロの数を取得できます。

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

Rcpp ではるかに高速なソリューションを作成しました。

関数をより一般的なものにするために、data.frame ではなく論理行列を使用するように記述し、すべて真の行が最も少ない列の組み合わせを見つけるように設計しました。したがって、あなたの場合、引数を として計算できますdat==0。また、組み合わせの列数を 2 番目のパラメーターとしてパラメーター化しましたr。この場合は 3 になります。

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;
    }
');

入力例のデモは次のとおりです。

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

そして、これはフルサイズのテストで、私のシステムではほぼ 10 分かかります。

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
于 2016-07-08T10:15:43.767 に答える