Warum verarbeitet Random Forest fehlende Werte in Prädiktoren nicht?

42

Was sind theoretische Gründe, um fehlende Werte nicht zu behandeln? Gradientenverstärkungsmaschinen und Regressionsbäume verarbeiten fehlende Werte. Warum macht Random Forest das nicht?

Fedorenko Kristina
quelle
3
Sie werden im partyR-Paket behandelt. Ein Blog-Artikel hier: exegetic.biz/blog/2013/05/…
Stéphane Laurent

Antworten:

34

Gradient Boosting Trees verwendet CART-Bäume (in einer Standardkonfiguration, wie sie von den Autoren vorgeschlagen wurde). CART-Bäume werden auch in zufälligen Wäldern verwendet. Was @ user777 sagte, ist wahr, dass RF-Bäume fehlende Werte entweder durch Imputation mit Durchschnitt, entweder durch groben Durchschnitt / Modus oder durch eine Mittelung / Modus basierend auf Ähnlichkeiten handhaben. Diese Methoden wurden von Breiman und Cutler vorgeschlagen und werden für HF verwendet. Dies ist eine Referenz von Autoren Fehlende Werte im Trainingssatz .

Es kann jedoch ein GBM oder RF mit anderen Arten von Entscheidungsbäumen erstellt werden. Der übliche Ersatz für CART ist C4.5, der von Quinlan vorgeschlagen wurde. In C4.5 werden die fehlenden Werte im Datensatz nicht ersetzt. Stattdessen berücksichtigt die berechnete Verunreinigungsfunktion die fehlenden Werte, indem die Verunreinigungsbewertung mit dem Verhältnis der fehlenden Werte bestraft wird. Beim Test wird die Bewertung in einem Knoten festgelegt, der einen Test mit fehlendem Wert hat. Die Vorhersage wird für jeden untergeordneten Knoten erstellt und später aggregiert (nach Gewichtung).

In vielen Implementierungen wird jetzt C4.5 anstelle von CART verwendet. Der Hauptgrund ist, teure Berechnungen zu vermeiden (CART hat strengere statistische Ansätze, die mehr Berechnungen erfordern), die Ergebnisse scheinen ähnlich zu sein, die resultierenden Bäume sind oft kleiner (da CART binär ist und C4.5 nicht). Ich weiß, dass Weka diesen Ansatz verwendet. Andere Bibliotheken kenne ich nicht, aber ich gehe davon aus, dass es sich nicht um eine Einzelsituation handelt. Wenn dies bei Ihrer GBM-Implementierung der Fall ist, wäre dies eine Antwort.

rapaio
quelle
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Prophet60091
Sie haben "Bestrafung der Verunreinigungsbewertung mit der Angabe fehlender Werte" angesprochen. Wie wirkt sich dies direkt auf die Auswahl der optimalen Dimensionswerte aus, die auf einer bestimmten Ebene / Verzweigung des Baums ausgewählt wurden?
Javadba
16

"Was sind [die] theoretischen Gründe [für RF], fehlende Werte nicht zu behandeln? Gradientenverstärkungsmaschinen, Regressionsbäume behandeln fehlende Werte. Warum macht Random Forest das nicht?"

RF tut Griff fehlende Werte, nur nicht in der gleichen Art und Weise , dass CART und andere ähnliche Entscheidungsbaum - Algorithmen tun. User777 beschreibt die beiden Methoden, die RF verwendet, um mit fehlenden Daten umzugehen (Median-Imputation und / oder approximationsbasiertes Maß), während Frank Harrell korrekt beschreibt, wie fehlende Werte in CART behandelt werden (Surrogat-Splits). Weitere Informationen finden Sie unter den Links zum Umgang mit fehlenden Daten für CART (oder FOSS-Cousin: RPART ) und RF .

Eine Antwort auf Ihre eigentliche Frage finden Sie , IMHO, in Ishwaran et al. 2008 mit dem Titel Random Survival Forests . Sie liefern die folgende plausible Erklärung, warum RF fehlende Daten nicht wie CART oder ähnliche Einzelentscheidungsbaumklassifizierer behandelt:

"Obwohl das Aufteilen von Ersatzbäumen für Bäume gut funktioniert, ist die Methode möglicherweise nicht für Wälder geeignet. Die Geschwindigkeit ist ein Problem. Das Auffinden einer Aufteilung von Ersatzbäumen ist rechenintensiv und kann unmöglich werden, wenn eine große Anzahl von Bäumen gezüchtet wird, insbesondere für vollständig gesättigte Bäume, die von verwendet werden Darüber hinaus sind Ersatzaufteilungen in einem Gesamtstrukturparadigma möglicherweise nicht einmal von Bedeutung. RF wählt beim Aufteilen eines Knotens Variablen nach dem Zufallsprinzip aus, sodass Variablen innerhalb eines Knotens möglicherweise nicht korreliert sind und eine sinnvolle Ersatzaufteilung möglicherweise nicht besteht Durch die Ersatzaufteilung wird die Interpretation einer Variablen geändert, was sich auf Kennzahlen wie [Variablenbedeutung] auswirkt.

Aus diesen Gründen ist für RF eine andere Strategie erforderlich. "

Dies ist eine Ausnahme, aber für mich stellt dies diejenigen in Frage, die behaupten, dass RF ein Ensemble von CART-Modellen verwendet. Ich habe diese Behauptung in vielen Artikeln gesehen, aber ich habe noch nie solche Aussagen gesehen, die auf einen maßgeblichen Text in RF bezogen sind. Zum einen werden die Bäume in einem RF ohne Beschneiden gezüchtet , was normalerweise nicht der Standardansatz beim Erstellen eines CART-Modells ist. Ein weiterer Grund wäre der, auf den Sie in Ihrer Frage anspielen: CART und andere Ensembles von Entscheidungsbäumen behandeln fehlende Werte, während [das Original] RF dies nicht tut, zumindest nicht intern wie CART.

In Anbetracht dieser Einschränkungen könnte man sagen, dass RF ein Ensemble von CART-ähnlichen Entscheidungsbäumen verwendet (dh eine Reihe von unbeschnittenen Bäumen, die maximal gewachsen sind, ohne die Fähigkeit, fehlende Daten durch Ersatzaufteilung zu verarbeiten). Vielleicht ist dies einer dieser pünktlichen semantischen Unterschiede, aber ich halte es für erwähnenswert.


BEARBEITEN : In meiner Randnotiz, die nichts mit der tatsächlich gestellten Frage zu tun hat, stellte ich fest, dass "ich noch nie solche Aussagen gesehen habe, die auf einen maßgeblichen Text in RF bezogen waren". Es hat sich herausgestellt, dass Breiman DID ausdrücklich angibt, dass im ursprünglichen RF-Algorithmus CART-Entscheidungsbäume verwendet werden:

"Die einfachste zufällige Gesamtstruktur mit zufälligen Merkmalen wird durch zufälliges Auswählen einer kleinen Gruppe von Eingabevariablen an jedem Knoten gebildet. Wachsen Sie den Baum mithilfe der CART-Methodik auf die maximale Größe und schneiden Sie ihn nicht ab." [Meine Betonung]

Quelle: S.9 von Random Forests. Breiman (2001)

Ich stehe jedoch immer noch (wenn auch etwas prekärer) auf dem Gedanken, dass dies CART-ähnliche Entscheidungsbäume sind, da sie ohne Bereinigung erstellt werden, während ein CART normalerweise nie in dieser Konfiguration ausgeführt wird, da es mit ziemlicher Sicherheit zu einer Überanpassung Ihrer Daten führt ( daher in erster Linie das Beschneiden).

Prophet60091
quelle
11

Zufällige Gesamtstruktur verarbeitet fehlende Daten auf zwei verschiedene Arten:

1) Ohne Anrechnung fehlender Daten, aber Rückschluss. 2) Eingabe der Daten. Die unterstellten Daten werden dann zur Schlussfolgerung herangezogen.

Beide Methoden sind in meinem R-Paket randomForestSRC implementiert (gemeinsam mit Udaya Kogalur geschrieben). Erstens ist es wichtig, sich daran zu erinnern, dass die herkömmlichen Methoden für fehlende Daten, die von einzelnen Bäumen (CART und dergleichen) verwendet werden, nicht angewendet werden, da zufällige Gesamtstrukturen eine zufällige Featureauswahl verwenden. Dieser Punkt wurde in Ishwaran et al. (2008), "Random Survival Forests", Annals of Applied Statistics , 2 , 3 , und schön von einem der Kommentatoren artikuliert.

Methode (1) ist eine "on the fly Imputation" (OTFI) -Methode. Vor dem Aufteilen eines Knotens werden fehlende Daten für eine Variable durch zufälliges Zeichnen von Werten aus nicht fehlenden In-Bag-Daten berechnet. Der Zweck dieser unterstellten Daten besteht darin, die Zuordnung von Fällen zu Tochterknoten für den Fall zu ermöglichen, dass der Knoten auf eine Variable mit fehlenden Daten aufgeteilt wird. Imputierte Daten werden jedoch nicht zur Berechnung der Split-Statistik verwendet, bei der nur nicht fehlende Daten verwendet werden. Nach einem Knotensplit werden die unterstellten Daten auf "fehlend" zurückgesetzt und der Vorgang wiederholt, bis die Endknoten erreicht sind. OTFI bewahrt die Integrität von Out-of-Bag-Daten und daher bleiben Leistungswerte wie variable Wichtigkeit (VIMP) unvoreingenommen. Der OTFI-Algorithmus wurde von Ishwaran et al. (2008) beschrieben und im pensionierten randomSurvivalForest-Paket implementiert.

Methode (2) wird mit der Funktion "impute" in randomForestSRC implementiert. Es stehen unbeaufsichtigte, randomisierte und multivariate Aufteilungsmethoden für die Eingabe von Daten zur Verfügung. Zum Beispiel verallgemeinert die multivariate Aufteilung die sehr erfolgreiche missForest-Imputationsmethode ( Stekhoven & Bühlmann (2012), "MissForest - nichtparametrische Fehlwertimputation für gemischte Daten", Bioinformatics , 28 , 1 ). Wenn Sie die Impute-Funktion mit fehlenden Daten aufrufen, wird ein unterstellter Datenrahmen zurückgegeben, der mit der primären Gesamtstrukturfunktion "rfsrc" angepasst werden kann.

Ein detaillierter Vergleich der verschiedenen Algorithmen für fehlende Walddaten, die mit "impute" implementiert wurden, wurde in einem kürzlich erschienenen Artikel mit Fei Tang "Random forest missing data algorithms", 2017, beschrieben . Ich empfehle, die Hilfedateien von "rfsrc" und "impute" von randomForestSRC zu Rate zu ziehen, um weitere Informationen zu Imputation und OTFI zu erhalten.

Hemant Ishwaran
quelle
3
Willkommen auf unserer Webseite! Beachten Sie, dass Ihr Benutzername, Ihr Identicon und ein Link zu Ihrer Benutzerseite automatisch zu jedem von Ihnen verfassten Beitrag hinzugefügt werden, sodass Sie Ihre Beiträge nicht signieren müssen. Tatsächlich bevorzugen wir, dass Sie nicht.
Silverfish
1
Vielen Dank für eine interessante Antwort (+1). Ich habe mir erlaubt, für einige der zitierten Artikel vollständige Verweise und Links hinzuzufügen, konnte jedoch Tang & Ishwaran (2015), "Random Forest missing data algorithms", nicht finden. Wurde es schon veröffentlicht?
Scortchi - Wiedereinsetzung von Monica
9

Bei der rekursiven Partitionierung werden Ersatzteilungen verwendet, die auf nicht fehlenden Prädiktoren basieren, die mit dem Prädiktor korrelieren, der den fehlenden Wert für eine Beobachtung besitzt. Theoretisch erscheint es möglich, zufällige Wälder zu implementieren, die dieselbe Idee verwenden. Ich weiß nicht, ob zufällige Forest-Software dies getan hat.

Frank Harrell
quelle
7

Random Forest hat zwei Methoden, um mit fehlenden Werten umzugehen, so Leo Breiman und Adele Cutler, die es erfunden haben.

Der erste ist schnell und schmutzig: Er füllt nur den Medianwert für kontinuierliche Variablen oder den häufigsten nicht fehlenden Wert nach Klasse aus .

Die zweite Methode füllt fehlende Werte aus, führt dann RF aus und berechnet für fehlende kontinuierliche Werte den approximationsgewichteten Durchschnitt der fehlenden Werte. Dann wird dieser Vorgang mehrmals wiederholt. Dann wird das Modell ein letztes Mal unter Verwendung des RF-imputierten Datensatzes trainiert.

Setzen Sie Monica wieder ein
quelle
Vielen Dank für Ihre Antwort! Beide Methoden ersetzen jedoch fehlende Werte. In GBM- oder Regressionsbäumen ersetzen fehlende Werte jedoch nichts. Was ist in diesem Sinne der theoretische Unterschied zwischen beispielsweise GBM und RF?
Fedorenko Kristina
Ich bin kein Experte für GBM, aber der RF-Umgang mit fehlenden Werten scheint auf der Idee der Imputation zu beruhen ( en.wikipedia.org/wiki/Imputation_(statistics) Ergebnisse können aufgrund von Fehlzeiten verzerrt sein. Die Imputation versucht, diese fehlenden Werte wiederherzustellen und die Verzerrung zu verringern.
Setzen Sie Monica
2

Anstatt Medianwerte usw. zu verwenden, würde ich dringend empfehlen, sich das missRanger- Paket (das derzeit auf Github entwickelt wird) oder das R-Paket missForest anzusehen. In beiden Paketen werden zufällige Gesamtstrukturen verwendet, um Ihre Daten zunächst mithilfe einer Methode zuzuweisen, die der Mehrfachzuweisung über verkettete Gleichungen (MICE) ähnelt. Dies wäre die geeignete Imputationsmethode, da sie eng mit Ihrem tatsächlichen Analysemodell übereinstimmt. Sie können dann alle Ihre Daten verwenden, ohne sich wegen fehlender Beobachtungen Gedanken über das Löschen einzelner Zeilen machen zu müssen. Darüber hinaus sind die unterstellten Werte weitaus realistischer als die Auswahl von Medianwerten oder Modi.

Sie können nur einen ausgefüllten, kalkulatorischen Datensatz für Ihre Analysen verwenden. Die Unsicherheit über fehlende Werte lässt sich jedoch am besten einschließen, indem Sie mehrere Durchläufe dieser Imputationsmethoden ausführen und dann Ihr Modell für jeden der resultierenden Datensätze (dh mehrere) schätzen Imputation) und kombinieren Sie dann die Schätzungen nach Rubins Regeln (siehe R-Paket mitools).

Robert Kubinec
quelle
0

Für CART können Sie den Ansatz für fehlende Attribute (MIA) anwenden. Das heißt, für kategoriale Prädiktoren fehlt der Code als separate Kategorie. Für numerische Prädiktoren erstellen Sie zwei neue Variablen für jede Variable mit Fehlstellen: eine, bei der Sie Fehlstellen als -Inf und eine, bei der Sie Fehlstellen als + Inf codieren. Anschließend wenden Sie wie gewohnt eine zufällige Gesamtstrukturfunktion auf Ihre Daten an.

Vorteile von MIA: 1) Rechnerisch günstig, 2) liefert keine Mehrfachdatensätze und damit Modelle, wie dies bei der Mehrfachzurechnung der Fall ist (die Literatur zur Zurechnung fehlender Daten stimmt im Allgemeinen überein, dass ein einziger Zurechnungsdatensatz nicht ausreicht), 3) nicht erforderlich Sie können eine statistische Methode und / oder ein statistisches Modell für die Eingabe der Daten auswählen.

Funktionen ctree()und cforest()from package partykit ermöglichen das Anwenden von MIA, indem sie ctree_control(MIA = TRUE)an ihre controlArgumente übergeben werden.

Das RuleFit-Programm von Jerome Friedman verwendet offenbar MIA zur Behebung von Fehlern (siehe https://statweb.stanford.edu/~jhf/r-rulefit/rulefit3/RuleFit_help.html#xmiss) .

Eine Beschreibung des MIA-Ansatzes findet sich in Twala et al. (2008):

Twala, BETH, Jones, MC und Hand, DJ (2008). Gute Methoden, um mit fehlenden Daten in Entscheidungsbäumen umzugehen. Pattern Recognition Letters, 29 (7), 950-956.

Marjolein Fokkema
quelle