R получить комбинацию строк по группе, используя data.table (для ввода в igraph) - PullRequest
Новая
       18

R получить комбинацию строк по группе, используя data.table (для ввода в igraph)

0 голосов
/ 06 июня 2018

У меня есть data.table, как это: 

dt<-data.table(group=(c(rep("A", 4), rep("B", 3), rep("C", 2))),
       individual=c("Ava", "Bill", "Claire", "Daniel", "Evelyn", "Francis", "Grant", "Helen", "Ig"))

Я хотел бы изменить что-то вроде этого: 

dt2<-data.table(group=(c(rep("A", 6), rep("B", 3), rep("C", 1))), edge1=c("Ava", "Ava", "Ava", "Bill", "Bill", "Claire", "Evelyn", "Evelyn", "Francis", "Helen"), edge2=c("Bill", "Claire", "Daniel", "Claire", "Daniel", "Daniel", "Francis", "Grant", "Grant", "Ig"))

По сути, каждая строка второй таблицы занимает "aСочетание двух индивидов по группам »в первой таблице.Вся идея состоит в том, чтобы вводить данные в igraph для анализа сети.Если есть какие-либо лучшие решения для этой цели, они более чем приветствуются.

Ответы [ 2 ]

0 голосов
/ 06 июня 2018

Вы можете достичь этого с помощью CJ: 

dt[, CJ(edge1 = individual, edge2 = individual), by = group][edge1 < edge2]
#     group   edge1   edge2
#  1:     A     Ava    Bill
#  2:     A     Ava  Claire
#  3:     A     Ava  Daniel
#  4:     A    Bill  Claire
#  5:     A    Bill  Daniel
#  6:     A  Claire  Daniel
#  7:     B  Evelyn Francis
#  8:     B  Evelyn   Grant
#  9:     B Francis   Grant
# 10:     C   Helen      Ig
Обсуждение

Как отмечает MichaelChirico, для этого потребуется больше памяти.Для группы размером n CJ создаст n ^ 2 строки, а combn создаст n (n-1) / 2 строки.Отношение составляет n ^ 2 / (n (n-1) / 2) = 2n / (n-1) ~ 2.

Для подхода, который более эффективен как по памяти, так и по скорости, см. fast_combn в ответе MiclaelChirico.

Редактировать

Добавлена ​​реализация Rcpp combn путем перечисления: 

library(Rcpp)
cppFunction(
    'List combnCpp(CharacterVector x) {
    const int n = x.size();
    x.sort();
    CharacterVector combn1 = CharacterVector(n*(n-1)/2);
    CharacterVector combn2 = CharacterVector(n*(n-1)/2);
    int idx = 0;
    for(int i = 0; i < n - 1; i++) {
        for(int j = i + 1; j < n; j++){
            combn1[idx] = x[i];
            combn2[idx] = x[j];
            idx++;
        }
    }
    return List::create(_["V1"] = combn1, _["V2"] = combn2);
}')

combnCpp = dt[ , combnCpp(individual), by = group]

Вот тест с использованием кода @ MichaelChirico: 

library(data.table)
max_g = 1e3
set.seed(123)
dt = data.table(
    group = rep(LETTERS, sample(max_g, 26, TRUE))
)
dt[ , individual := as.character(.I)]

library(gRbase)
library(microbenchmark)
microbenchmark(
    times = 10L,
    cpp_combn = dt[ , combnCpp(individual), by = group],
    gRbase = dt[ , transpose(combnPrim(individual, 2, simplify = FALSE)), by = group],
    CJ = dt[ , CJ(edge1 = individual, edge2 = individual), by = group][edge1 < edge2],
    fast_combn = dt[ , {
        edge1 = rep(1:.N, (.N:1) - 1L)
        i = 2L:(.N * (.N - 1L) / 2L + 1L)
        o = cumsum(c(0, (.N-2L):1))
        edge2 = i - o[edge1]
        .(edge1 = edge1, edge2 = edge2)
    }, by = group]
)
# Unit: milliseconds
#        expr       min        lq      mean    median        uq       max neval
#   cpp_combn  247.6795  284.3614  324.2149  305.1760  347.1372  499.9442    10
#      gRbase 1115.0338 1299.2865 1341.3890 1339.3950 1378.6571 1517.2534    10
#          CJ 1455.2715 1481.8725 1630.0190 1616.7780 1754.3922 1879.5768    10
#  fast_combn  128.5774  153.4234  215.5325  166.7491  319.1567  363.3657    10

combnCpp по-прежнему примерно в 2 раза медленнее, чем fast_combn, что может быть связано с тем, что combnCpp выполняет перечисление, а fast_combn выполняет вычисления.Возможным улучшением для combnCpp будет вычисление индексов, как это делает fast_combn вместо перечисления.

0 голосов
/ 06 июня 2018

Спасибо @ mt1022, который помогает подчеркнуть, что реализация combn в base R очень медленная (она реализована в R).Таким образом, мы можем использовать подходы из этого Q & A о ускорении combn, чтобы сделать этот подход более эффективным.Мне не удалось установить gRbase на мою машину, поэтому я взял код из comb2.int и включил его в свой подход: 

dt[ , {
  edge1 = rep(1:.N, (.N:1) - 1L)
  i = 2L:(.N * (.N - 1L) / 2L + 1L)
  o = cumsum(c(0, (.N-2L):1))
  edge2 = i - o[edge1]
  .(edge1 = edge1, edge2 = edge2)
}, by = group]

Это существенно ускоряет процесс при увеличении скоростиверсия набора данных OP: 

max_g = 1e3
dt = data.table(
  group = rep(LETTERS, sample(max_g, 26, TRUE))
)
dt[ , individual := as.character(.I)]

library(microbenchmark)
microbenchmark(
  times = 10L,
  combn = dt[ , transpose(combn(individual, 2, simplify = FALSE)), by = group],
  cj = dt[ , CJ(edge1 = individual, edge2 = individual), by = group
           ][edge1 < edge2],
  fast_combn = dt[ , {
    edge1 = rep(1:.N, (.N:1) - 1L)
    i = 2L:(.N * (.N - 1L) / 2L + 1L)
    o = cumsum(c(0, (.N-2L):1))
    edge2 = i - o[edge1]
    .(edge1 = edge1, edge2 = edge2)
  }, by = group]
)
# Unit: milliseconds
#        expr       min        lq     mean    median        uq       max neval
#       combn 3075.8078 3247.8300 3905.831 3482.9950 4289.8168 6180.1138    10
#          cj 2495.1798 2549.1552 3830.492 4014.6591 4959.2004 5239.7905    10
#  fast_combn  180.1348  217.9098  294.235  284.8854  329.5982  493.4744    10

То есть, хотя исходный подход combn и предложенный с CJ основаны на принципах «шея и шея» в зависимости от характеристик данных, этот подход далеко илучше работать с большими данными.

Оригинальный подход с помощью combn

Мы можем использовать combn примерно так: 

dt2 = dt[ , transpose(combn(individual, 2, simplify = FALSE)), by = group]

По умолчанию combn вернет матрицу 2 x n, где n = choose(.N, 2) и .N - размер каждой группы.

simplify = FALSE вместо этого вернет длину - n list кортежей;transpose преобразует это в длину - 2 list из n -кортежей (эффективно).

Затем исправьте имена: 

setnames(dt2, c('V1', 'V2'), c('edge1', 'edge2'))
...