Comment puis-je obtenir certaines de toutes les combinaisons possibles dans R?

Parfois, je veux faire un test exact en examinant toutes les combinaisons possibles des données pour construire une distribution empirique par rapport à laquelle je peux tester mes différences observées entre les moyennes. Pour trouver les combinaisons possibles, j'utilise généralement la fonction combn. La fonction Choose peut me montrer le nombre de combinaisons possibles. Il est très facile que le nombre de combinaisons devienne si grand qu'il n'est pas possible de stocker le résultat de la fonction combn, par exemple, combn (28,14) nécessite un vecteur de 2,1 Go. J'ai donc essayé d'écrire un objet qui passait par la même logique que la fonction combn afin de fournir les valeurs d'une "pile" imaginaire une à la fois. Cependant, cette méthode (comme je l'ai instanciée) est facilement 50 fois plus lente que combn à des tailles de combinaison raisonnables,

Existe-t-il un meilleur algorithme pour faire ce genre de chose que l'algorithme utilisé dans combn? Plus précisément, existe-t-il un moyen de générer et de tirer la Nème combinaison possible sans calculer par toutes les combinaisons précédentes?

r nonparametric combinatorics russellpierce
la source

Quelqu'un a-t-il remarqué que le nombre de questions qui devraient être dans StackOverflow R est monté en flèche récemment?

John

Pourquoi ne pas faire un échantillonnage aléatoire?

@John: Si vous pensez de cette façon, discutez du problème sur meta.stats.stackexchange.com/questions/248/… , pas besoin d'être sarcastique.

russellpierce

@mbq: L'échantillonnage aléatoire fournira rapidement une approximation raisonnable, en particulier avec des données bien comportées. Cependant, j'ai précisé que mon objectif était un test exact.

russellpierce

@drknexus C'est pourquoi c'était un commentaire et non une réponse.

Réponses:

Si vous souhaitez échanger la vitesse de traitement contre de la mémoire (ce que je pense que vous faites), je suggère l'algorithme suivant:

Configurer une boucle de 1 à N Choisissez K, indexé par i
Chaque i peut être considéré comme un index d'une combinaison , décodé comme tel
Utilisez la combinaison pour effectuer votre statistique de test, stockez le résultat, jetez la combinaison
Répéter

Cela vous donnera toutes les combinaisons N Choose K possibles sans avoir à les créer explicitement. J'ai du code pour le faire en R si vous le souhaitez (vous pouvez m'envoyer un mail à mark dot m period fredrickson at-symbol gmail dot com).

Mark M. Fredrickson
la source

Voici un article avec le code et quelques illustrations: markmfredrickson.com/oughtts/2010-08-06-combinadics-in-r.html

Mark M. Fredrickson

J'accepte cette réponse parce qu'elle résout (ce que je pense) est le plus difficile des problèmes auxquels je cherchais une solution - choisir une combinaison particulière sans calculer les valeurs précédentes. Malheureusement, c'est encore très lent. Peut-être que, comme mentionné ici et ailleurs, une recherche binaire aiderait à accélérer les choses. La meilleure approche est peut-être d'avoir un thread générant les combinaisons pas à pas comme dans la réponse de mbq et un autre thread les lisant et les testant.

russellpierce

La génération de combinaisons est assez simple, voyez par exemple ceci ; écrire ce code dans R, puis traiter chaque combinaison à un moment où elle apparaît.

la source

Mais cela fera-t-il face à de très grandes combinaisons?

csgillespie

@csgillespie Eh bien, je crois que oui - cela fonctionne in situ , donc une seule combinaison est stockée en mémoire à la fois, et les résultats de la simulation peuvent également être agrégés pour éliminer le besoin de les stocker. Bien sûr, cela fonctionnera terriblement longtemps, mais les recherches exhaustives le font généralement. Pour la vitesse, cela pourrait être écrit en C, mais avec la partie simulation, qui est probablement beaucoup plus lente qu'une étape de générateur.

Cela semble presque identique à la façon dont la fonction combn de R fait déjà les choses. J'ai écrit une version de combn qui prend les combinaisons de la pile une à la fois, et comme le dit mbq car il ne stocke qu'une seule combinaison en mémoire à la fois, il peut gérer de très grandes combinaisons. Le problème avec le faire dans R est que faire une approche pas à pas dans une fonction implique généralement de lire les variables d'état dans la fonction, de les manipuler, puis de les stocker de nouveau dans global - ce qui semble simplement tout ralentir / façon / vers le bas.

russellpierce