Como posso obter algumas das combinações possíveis em R?

8

Às vezes, quero fazer um teste exato examinando todas as combinações possíveis dos dados para criar uma distribuição empírica com a qual posso testar minhas diferenças observadas entre as médias. Para encontrar as combinações possíveis, eu normalmente usaria a função combn. A função escolher pode me mostrar quantas combinações possíveis existem. É muito fácil que o número de combinações seja tão grande que não seja possível armazenar o resultado da função combn, por exemplo, combn (28,14) requer um vetor de 2,1 Gb. Por isso, tentei escrever um objeto que seguisse a mesma lógica da função combn para fornecer os valores de uma "pilha" imaginária, uma de cada vez. No entanto, esse método (como eu instanciei) é facilmente 50 vezes mais lento que o combn em tamanhos razoáveis ​​de combinação,

Existe um algoritmo melhor para fazer esse tipo de coisa do que o algoritmo usado no combn? Especificamente, existe uma maneira de gerar e puxar a enésima combinação possível sem calcular todas as combinações anteriores?

r nonparametric combinatorics russellpierce
fonte
Alguém já reparou que o número de perguntas que deveriam estar no StackOverflow R subiu aqui recentemente?
John
1
Por que não fazer amostragem aleatória?
4
@ John: Se você se sente assim, discuta o problema em meta.stats.stackexchange.com/questions/248/… , não precisa ser irritante.
russellpierce
@mbq: a amostragem aleatória fornecerá rapidamente uma aproximação razoável, especialmente com dados bem comportados. No entanto, especifiquei que meu objetivo era um teste exato.
russellpierce
@drknexus É por isso que foi um comentário, não uma resposta.

Respostas:

6

Se você deseja trocar a velocidade de processamento pela memória (o que eu acho que você faz), sugiro o seguinte algoritmo:

  • Configure um loop de 1 a N Escolha K, indexado por i
  • Cada i pode ser considerado um índice para uma decodificação combinada , como tal
  • Use a combinação para executar sua estatística de teste, armazene o resultado, descarte a combinação
  • Repetir

Isso fornecerá a você todas as combinações possíveis de N Choose K sem precisar criá-las explicitamente. Eu tenho código para fazer isso em R, se você quiser (você pode me enviar um e-mail no ponto de ponto m fredrickson no símbolo gmail dot com).

Mark M. Fredrickson
fonte
1
Aqui está um post com o código e algumas ilustrações: markmfredrickson.com/thoughts/2010-08-06-combinadics-in-r.html
Mark M. Fredrickson
Estou aceitando esta resposta porque ela resolve (o que eu acho) é o mais difícil dos problemas que eu estava procurando por uma solução - escolher uma combinação específica sem calcular os valores anteriores. Infelizmente, ainda é muito lento. Talvez, como mencionado aqui e em outros lugares, uma pesquisa binária ajude a acelerar as coisas. Talvez a melhor abordagem seja ter um thread gerando as combinações passo a passo, como na resposta do mbq, e outro thread os lendo e testando-os.
russellpierce
1

Gerar combinações é bem fácil, veja, por exemplo, isso ; escreva esse código em R e processe cada combinação no momento em que aparecer.


fonte
Mas isso vai lidar com combinações muito grandes?
precisa saber é o seguinte
@csgillespie Bem, acredito que sim - funciona in situ , portanto, apenas uma combinação é armazenada na memória de cada vez, e os resultados da simulação também podem ser agregados para eliminar a necessidade de armazená-los. Obviamente, isso funcionará terrivelmente longo, mas pesquisas exaustivas geralmente funcionam. Para velocidade, poderia ser escrito em C, mas junto com a parte da simulação, que provavelmente é muito mais lenta que uma etapa do gerador.
2
Isso parece quase idêntico ao modo como a função combn de R já está fazendo as coisas. Eu escrevi uma versão do combn que remove combinações da pilha, uma de cada vez, e como o mbq diz, porque está armazenando apenas uma combinação na memória por vez, pode lidar com combinações muito grandes. O problema de fazê-lo em R é que fazer uma abordagem passo a passo em uma função geralmente envolve a leitura das variáveis ​​de estado na função, manipulá-las e armazená-las de volta para o global - o que parece apenas diminuir a velocidade / tudo / baixa.
russellpierce