Temps de calcul aléatoire de la forêt en R

49

J'utilise le package party en R avec 10 000 lignes et 34 fonctionnalités, et certaines fonctionnalités factorielles comportent plus de 300 niveaux. Le temps de calcul est trop long. (Cela a pris 3 heures jusqu'à présent et ce n'est pas fini.)

Je veux savoir quels éléments ont un effet important sur le temps de calcul d'une forêt aléatoire. Est-ce qu'il y a des facteurs avec trop de niveaux? Existe-t-il des méthodes optimisées pour améliorer le temps de calcul RF?

Chenghao Liu
la source

Réponses:

65

La complexité globale de RF est quelque chose comme ; Si vous souhaitez accélérer vos calculs, vous pouvez essayer les solutions suivantes:ntreemtry(# objects)log(# objects)

  1. Utilisez randomForestau lieu de party, ou encore mieux, rangerou Rborist(même si les deux ne sont pas encore testés au combat).
  2. Ne pas utiliser de formule, c’est-à-dire appeler randomForest(predictors,decision)au lieu de randomForest(decision~.,data=input).
  3. Utilisez l' do.traceargument pour voir l'erreur OOB en temps réel. De cette façon, vous pouvez détecter que vous pouvez baisser ntree.
  4. Sur les facteurs; RF (et toutes les méthodes arborescentes) essaient de trouver un sous-ensemble optimal de niveaux en explorant possibilités (# de niveaux-1) ; à cette fin, il est assez naïf de savoir que ce facteur peut vous donner tant d’informations - sans compter que randomForest ne mange pas de facteurs ayant plus de 32 niveaux. Peut-être pouvez-vous simplement le traiter comme un ordre (et donc comme une variable numérique normale pour RF) ou le regrouper dans certains groupes, en divisant cet attribut en plusieurs?2(# of levels-1)
  5. Vérifiez si votre ordinateur n’est pas à court de RAM et utilise l’espace de permutation. Si oui, achetez un ordinateur plus grand.
  6. Enfin, vous pouvez extraire un sous-ensemble d'objets aléatoire et effectuer des expériences initiales à ce sujet.
Rétablir Monica
la source
2
Merci, j'ai beaucoup appris de votre réponse et j'ai fait un test comme vous l'avez dit, d'ailleurs, pourquoi la deuxième suggestion fonctionne-t-elle?
Chenghao Liu
4
Les formules @ChenghaoLiu ont été conçues pour les cadres de modèles de liner petits mais complexes. Elles sont donc inefficaces lorsque la copie de l'ensemble devient coûteuse.
1
Pourquoi l'appel à randomForest (prédicteurs, décision) réduit-il le temps d'exécution?
JenSCDC
mtry
1
@AndyBlankertz L'interprétation des formules dans randomForest semble conduire à la copie de la totalité de l'entrée.
12

RandomForest étant un ensemble de paniers indépendants formés sur un sous-ensemble aléatoire de fonctionnalités et d'enregistrements, il se prête à la parallélisation. La combine()fonction du paquetage randomForest assemblera des forêts formées indépendamment. Voici un exemple de jouet. La réponse de @mpq stipule que vous ne devez pas utiliser la notation de formule, mais plutôt une structure de données / matrice de variables et un vecteur de résultats. Je les ai levées sans vergogne des docs.

library("doMC")
library("randomForest")
data(iris)

registerDoMC(4) #number of cores on the machine
darkAndScaryForest <- foreach(y=seq(10), .combine=combine ) %dopar% {
   set.seed(y) # not really needed
   rf <- randomForest(Species ~ ., iris, ntree=50, norm.votes=FALSE)
}

J'ai passé la fonction de combinaison randomForest au paramètre .combine portant le même nom (qui contrôle la fonction sur la sortie de la boucle. L'inconvénient est que vous n'obtenez aucun taux d'erreur OOB ou une importance plus tragiquement variable.

Modifier:

Après avoir relu le post, je me rends compte que je ne parle pas du problème des facteurs 34+. Une réponse totalement non réfléchie pourrait être de les représenter sous forme de variables binaires. C’est-à-dire que chaque colonne est codée avec un facteur de niveau 0/1 pour sa présence ou non. En effectuant des sélections variables sur des facteurs sans importance et en les supprimant, vous pouvez éviter que votre espace ne devienne trop grand.

Jdennison
la source
Bienvenue sur le site, @jdennison. Cela semble être une contribution vraiment intéressante (bien que je ne sache vraiment pas beaucoup de choses sur les RF et rien sur l'informatique parallèle). Une note, l'ordre des réponses peut fluctuer dans le temps, il est donc préférable de ne pas faire référence à "la réponse ci-dessus", mais plutôt à "la réponse de \ @ untel" à la place.
gung - Réintégrer Monica
Désolé de vous répondre tardivement.J'ai lu votre blog, excellent travail
Chenghao Liu le
3

Je suggérerais quelques liens:

1) Réduire le nombre de niveaux d’une variable facteur est un lien vers une question stackoverflowpermettant de traiter un problème similaire lors de l’utilisation du randomForestprogiciel. En particulier, il s'agit d'utiliser uniquement les niveaux les plus fréquents et d'attribuer un nouveau niveau à tous les autres niveaux moins fréquents.

L'idée est venue d'ici: le KDD Cup Slow Challenge 2009 . Les données de ce concours comportaient de nombreux facteurs et de nombreux niveaux et expliquaient certaines des méthodes utilisées pour réduire les données de 50 000 lignes à 15 000 colonnes afin qu'elles puissent être exécutées sur un ordinateur portable à 2 cœurs / 2 Go de RAM.

Ma dernière suggestion consisterait à examiner le problème, comme indiqué ci-dessus, en exécutant le problème en parallèle sur une instance Amazon EC2 à processeur élevé.

screechOwl
la source
Il n'y a pas 2) . Vous devez fournir la partie importante de la page au lieu de vous fier entièrement au lien.
AL
J'aime la façon dont ces instances EC fonctionnent. Waouh ils sont gentils. Je pense que le matériel virtualisé est meilleur que la réalité.
EngrStudent - Réintégrer Monica le
2

Je ne peux pas parler de la vitesse de certains algorithmes dans R, mais ce qui cause un long temps de calcul devrait être évident. Pour chaque arbre de chaque branche, CART cherche la meilleure division binaire. Ainsi, pour chacune des 34 entités, ce sont les fractionnements donnés par chacun des niveaux des variables qui sont le plus pris en compte. Multipliez le temps d'exécution pour chaque scission dans un arbre par le nombre de branches dans l'arbre, puis multipliez-le par le nombre d'arbres dans la forêt et vous aurez une longue durée. Qui sait? Peut-être que même avec un ordinateur rapide, cela pourrait prendre des années?

Je pense que la meilleure façon d’accélérer les choses est de regrouper certains niveaux afin que chaque variable soit réduite à peut-être 3 à 5 niveaux au lieu de 300. Bien sûr, cela dépend de la capacité de le faire sans perdre d’importantes pertes. informations dans vos données.

Après cela, vous pourriez peut-être vérifier s'il existe un algorithme intelligent qui peut accélérer le temps de recherche pour la division au niveau de chaque nœud de chaque arborescence. il se peut que, dans un arbre particulier, la recherche fractionnée répète une recherche déjà effectuée pour un arbre précédent. Donc, si vous pouvez sauvegarder les solutions des décisions précédentes et identifier quand vous répétez, peut-être que cette stratégie pourrait économiser un peu de temps de calcul.

Michael Chernick
la source
Encore une fois, je suis tout à fait d’accord avec vous. Et j’essaie de réduire le nombre de niveaux avec une fausse méthode factice.Par exemple, je remplace un prédicteur par 600 niveaux avec 4 prédicteurs (en tant que 600 <5 ^ 4). Après cette transformation, je peut exécuter un algorithme de forêt aléatoire.Cependant, le résultat RMSE est étrange, je vais ouvrir deux autres questions sur la façon de réduire le niveau de facteur facteur et quelle est la relation entre le facteur RMS CV 10 fois et le score RMSE du jeu de tests?
Chenghao Liu