Zufällige Gesamtstrukturberechnungszeit in R

48

Ich verwende das Party- Paket in R mit 10.000 Zeilen und 34 Features, und einige Factor-Features haben mehr als 300 Levels. Die Rechenzeit ist zu lang. (Es hat bis jetzt 3 Stunden gedauert und ist noch nicht fertig.)

Ich möchte wissen, welche Elemente einen großen Einfluss auf die Rechenzeit einer zufälligen Gesamtstruktur haben. Gibt es Faktoren mit zu vielen Ebenen? Gibt es optimierte Methoden zur Verbesserung der RF-Rechenzeit?

Chenghao Liu
quelle

Antworten:

64

Die Gesamtkomplexität von RF ist ; Wenn Sie Ihre Berechnungen beschleunigen möchten, können Sie Folgendes versuchen:ntreemtry(# objects)log(# objects)

  1. Verwenden Sie randomForestanstelle von partyoder, noch besser, rangeroder Rborist(obwohl beide noch nicht kampferprobt sind).
  2. Verwenden Sie keine Formel, dh rufen Sie randomForest(predictors,decision)statt randomForest(decision~.,data=input).
  3. Verwenden Sie das do.traceArgument, um den OOB-Fehler in Echtzeit anzuzeigen. Auf diese Weise können Sie feststellen, dass Sie senken können ntree.
  4. Über Faktoren; RF (und alle Baummethoden) versuchen, eine optimale Untergruppe von Ebenen zu finden, um Möglichkeiten zu durchsuchen; zu diesem Zweck ist es ziemlich naiv, dass dieser Faktor so viele Informationen liefert - ganz zu schweigen davon, dass randomForest keine Faktoren mit mehr als 32 Levels frisst. Vielleicht können Sie es einfach als eine geordnete behandeln (und damit einer normalen numerischen Variablen für RF entsprechen) oder es in einige Gruppen gruppieren und dieses eine Attribut in mehrere aufteilen?2(# of levels-1)
  5. Überprüfen Sie, ob der Arbeitsspeicher Ihres Computers nicht voll ist und Swap Space verwendet. Wenn ja, kaufen Sie einen größeren Computer.
  6. Schließlich können Sie eine zufällige Teilmenge von Objekten extrahieren und erste Experimente dazu durchführen.
Setzen Sie Monica wieder ein
quelle
2
Vielen Dank, ich lerne viel aus Ihrer Antwort und habe einen Test gemacht, wie Sie sagten, außerdem, warum der zweite Vorschlag funktioniert?
Chenghao Liu
4
@ChenghaoLiu Formeln wurden für kleine, aber komplexe Rahmenmodelle entwickelt und sind daher ineffizient, wenn das Kopieren des Satzes teuer wird.
1
Warum reduziert das Aufrufen von randomForest (Prädiktoren, Entscheidung) die Laufzeit?
JenSCDC
Was ist ? mtry
jkabrg
1
@AndyBlankertz Formelinterpretation in randomForest scheint zum Kopieren der gesamten Eingabe zu führen.
12

Da randomForest eine Sammlung unabhängiger Wagen ist, die auf einer zufälligen Untergruppe von Features und Datensätzen basieren, eignet es sich für die Parallelisierung. Die combine()Funktion im randomForest-Paket setzt unabhängig trainierte Wälder zusammen. Hier ist ein Spielzeugbeispiel. In der Antwort von @mpq heißt es, dass Sie nicht die Formelnotation verwenden sollten, sondern einen Datenrahmen / eine Variablenmatrix und einen Ergebnisvektor übergeben sollten. Ich habe sie schamlos aus den Unterlagen geholt.

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

Ich habe die randomForest-Kombinationsfunktion an den ähnlich benannten .combine-Parameter übergeben (der die Funktion am Ausgang der Schleife steuert).

Bearbeiten:

Nach dem erneuten Lesen des Beitrags stelle ich fest, dass ich nicht über das 34+ Faktor-Problem spreche. Eine völlig unüberlegte Antwort könnte darin bestehen, sie als binäre Variablen darzustellen. Das ist jeder Faktor eine Spalte, die mit einem 0/1-Level-Faktor bezüglich ihrer Anwesenheit / Nicht-Anwesenheit codiert ist. Indem Sie bei unwichtigen Faktoren eine variable Auswahl treffen und diese entfernen, können Sie verhindern, dass der Funktionsbereich zu groß wird.

jdennison
quelle
Willkommen auf der Site, @jdennison. Dies sieht nach einem wirklich netten Beitrag aus (obwohl ich nicht allzu viel über RFs und nichts über Parallel-Computing weiß). Eine Anmerkung: Die Reihenfolge der Antworten kann im Laufe der Zeit variieren. Verweisen Sie daher am besten nicht auf "die obige Antwort", sondern auf "die Antwort von \ @ so-and-so".
gung - Wiedereinsetzung von Monica
Entschuldigung für die späte Antwort. Ich habe Ihren Blog gelesen, tolle Arbeit
Chenghao Liu
3

Ich würde ein paar Links vorschlagen:

1) Shrink number of levels einer Faktorvariablen ist ein Link zu einer Frage, stackoverflowum sich mit einem ähnlichen Problem während der Verwendung des randomForestPakets zu befassen . Insbesondere werden nur die am häufigsten vorkommenden Ebenen verwendet und allen anderen, weniger häufig vorkommenden Ebenen eine neue Ebene zugewiesen.

Die Idee dazu kam von hier: 2009 KDD Cup Slow Challenge . Die Daten für diesen Wettbewerb hatten viele Faktoren mit vielen Ebenen und es werden einige der Methoden erläutert, mit denen die Daten von 50.000 Zeilen auf 15.000 Spalten reduziert wurden, um auf einem Laptop mit 2 Kernen und 2 GB RAM ausgeführt zu werden.

Mein letzter Vorschlag wäre, das oben vorgeschlagene Problem parallel auf einer Amazon EC2-Instanz mit hoher CPU-Auslastung auszuführen.

kreischeule
quelle
Es gibt keine 2) . Sie sollten den wichtigen Teil der Seite bereitstellen, anstatt sich ausschließlich auf den Link zu verlassen.
AL
Mir gefällt, wie diese EC-Instanzen ausgeführt werden. Wow sind sie nett. Ich denke, die virtualisierte Hardware ist besser als die echte.
EngrStudent
2

Ich kann nicht mit der Geschwindigkeit bestimmter Algorithmen in R sprechen, aber es sollte offensichtlich sein, was zu langer Rechenzeit führt. Für jeden Baum in jedem Zweig sucht CART nach der besten binären Aufteilung. Für jedes der 34 Features werden die durch die einzelnen Ebenen der Variablen gegebenen Aufteilungen am häufigsten betrachtet. Multiplizieren Sie die Laufzeit für jede Teilung in einem Baum mit der Anzahl der Zweige im Baum und multiplizieren Sie diese dann mit der Anzahl der Bäume im Wald, und Sie haben eine lange Laufzeit. Wer weiß? Vielleicht kann es sogar mit einem schnellen Computer Jahre dauern, bis dies erledigt ist?

Ich denke, die beste Möglichkeit, die Dinge zu beschleunigen, besteht darin, einige der Ebenen so zusammenzufassen, dass jede Variable nur noch 3 bis 5 statt bis zu 300 Ebenen enthält Informationen in Ihren Daten.

Danach könnten Sie vielleicht nachsehen, ob es einen cleveren Algorithmus gibt, der die Suchzeit für das Teilen an jedem Knoten der einzelnen Bäume beschleunigen kann. es könnte sein, dass die geteilte Suche an einem bestimmten Baum eine Wiederholung einer Suche ist, die bereits für einen vorherigen Baum durchgeführt wurde. Wenn Sie also die Lösungen der vorherigen Teilungsentscheidungen speichern und feststellen können, wann Sie sie wiederholen, kann diese Strategie möglicherweise ein wenig Rechenzeit einsparen.

Michael Chernick
quelle
Nochmals vielen Dank, ich stimme Ihnen voll und ganz zu. Und ich versuche, die Anzahl der Ebenen mit einer gefälschten Dummy-Methode zu reduzieren. Zum Beispiel ersetze ich einen Prädiktor mit 600 Ebenen durch 4 Prädiktoren (als 600 <5 ^ 4) Zufallswald-Algorithmus kann ausgeführt werden. Das RMSE-Ergebnis ist jedoch seltsam. Ich möchte zwei weitere Fragen dazu stellen, wie das Faktor-Feature reduziert werden kann und in welcher Beziehung das 10-fache CV-RMSE zum RMSE-Score des Testsets steht.
Chenghao Liu