Wie reagieren Zufallswälder nicht auf Ausreißer?

33

In einigen Quellen, einschließlich dieser , habe ich gelesen , dass Random Forests unempfindlich gegenüber Ausreißern sind (wie es beispielsweise bei Logistic Regression und anderen ML-Methoden der Fall ist).

Zwei Teile der Intuition sagen mir jedoch etwas anderes:

  1. Bei jeder Erstellung eines Entscheidungsbaums müssen alle Punkte klassifiziert werden. Dies bedeutet, dass auch Ausreißer klassifiziert werden und sich somit auf die Entscheidungsbäume auswirken, in denen sie beim Boosten ausgewählt wurden.

  2. Bootstrapping ist ein Teil dessen, wie ein RandomForest Subsampling durchführt. Bootstrapping ist anfällig für Ausreißer.

Gibt es eine Möglichkeit, meine Intuition über die Empfindlichkeit gegenüber Ausreißern mit Quellen in Einklang zu bringen, die nicht übereinstimmen?

Hunle
quelle
Die Antwort unten ist sehr gut. Die intuitive Antwort lautet, dass ein Entscheidungsbaum für Teilungen funktioniert und Teilungen nicht für Ausreißer empfindlich sind: Eine Teilung muss nur irgendwo zwischen zwei Gruppen von Punkten liegen, um sie zu teilen.
Wayne
Ich nehme an, wenn das so min_samples_leaf_nodeist 1, dann könnte es anfällig für Ausreißer sein.
Hunle
yes min_samples und bootstrap sample können den Einfluss von 1b-Ausreißern in der RF-Regression vollständig entfernen
Soren Havelund Welling
Einige Statistiker erhalten einen Tunnelblick auf die Lieferanten, den man vorhersagen und verstehen kann. Schätzen Sie die Ausreißer als "bekannte Unbekannte" und fragen Sie sich, ob Ihr Geschäftsmodell für sie fragil ist. Einige Ausreißer sind von Grund auf unvorhersehbar, aber ihre Auswirkungen sind sehr real ... eine Umschreibung von N. Talebs 'Black Swan'
Soren Havelund Welling

Antworten:

21

Ihre Intuition ist richtig. Diese Antwort zeigt sie nur an einem Beispiel.

Es ist in der Tat ein weit verbreitetes Missverständnis, dass CART / RF Ausreißern gegenüber robust sind.

Um die mangelnde Robustheit von HF gegenüber einzelnen Ausreißern zu veranschaulichen, können wir den in der obigen Antwort von Soren Havelund Welling verwendeten Code (leicht) modifizieren, um zu zeigen, dass ein einzelner y-Ausreißer ausreicht, um das angepasste HF-Modell vollständig zu beeinflussen. Wenn wir zum Beispiel den mittleren Vorhersagefehler der nicht kontaminierten Beobachtungen als Funktion der Entfernung zwischen dem Ausreißer und dem Rest der Daten berechnen, können wir sehen (Bild unten), dass ein einzelner Ausreißer eingeführt wird (indem eine der ursprünglichen Beobachtungen ersetzt wird durch einen beliebigen Wert im 'y'-Raum) genügt, um die Vorhersagen des RF-Modells beliebig weit von den Werten zu entfernen, die sie hätten, wenn sie mit den ursprünglichen (nicht kontaminierten) Daten berechnet worden wären:

 library(forestFloor)
library(randomForest)
library(rgl)
set.seed(1)

X = data.frame(replicate(2,runif(2000)-.5))
y = -sqrt((X[,1])^4+(X[,2])^4)
X[1,]=c(0,0);
y2<-y
rg<-randomForest(X,y)   #RF model fitted without the outlier
outlier<-rel_prediction_error<-rep(NA,10)

for(i in 1:10){
    y2[1]=100*i+2
    rf=randomForest(X,y2)   #RF model fitted with the outlier
    rel_prediction_error[i]<-mean(abs(rf$predict[-1]-y2[-1]))/mean(abs(rg$predict[-1]-y[-1]))
    outlier[i]<-y2[1]
}
plot(outlier,rel_prediction_error,type='l',ylab="Mean prediction error (on the uncontaminated observations) \\\ relative to the fit on clean data",xlab="Distance of the outlier")

Bildbeschreibung hier eingeben

Wie weit? Im obigen Beispiel hat der einzelne Ausreißer die Anpassung so stark geändert, dass der mittlere Vorhersagefehler (bei nicht kontaminierten Beobachtungen) jetzt 1-2 Größenordnungen größer ist als er gewesen wäre, wenn das Modell an die nicht kontaminierten Daten angepasst worden wäre.

Es ist also nicht wahr, dass ein einzelner Ausreißer die HF-Anpassung nicht beeinflussen kann.

Wie ich an anderer Stelle erwähne, ist es außerdem viel schwieriger, mit Ausreißern umzugehen, wenn möglicherweise mehrere von ihnen vorhanden sind (obwohl sie nicht unbedingt einen großen Teil der Daten enthalten müssen, damit ihre Auswirkungen sichtbar werden). Kontaminierte Daten können natürlich mehrere Ausreißer enthalten. Um die Auswirkung mehrerer Ausreißer auf die RF-Anpassung zu messen, vergleichen Sie die Darstellung auf der linken Seite, die von der RF auf den nicht kontaminierten Daten erhalten wurde, mit der Darstellung auf der rechten Seite, die durch willkürliche Verschiebung von 5% der Antwortwerte erhalten wurde (der Code befindet sich unter der Antwort). .

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

Schließlich muss im Zusammenhang mit der Regression darauf hingewiesen werden, dass sich Ausreißer sowohl im Entwurfs- als auch im Antwortbereich von der Masse der Daten abheben können (1). Im spezifischen RF-Kontext beeinflussen Ausreißer beim Design die Schätzung der Hyperparameter. Dieser zweite Effekt ist jedoch deutlicher, wenn die Anzahl der Dimensionen groß ist.

Was wir hier beobachten, ist ein besonderer Fall eines allgemeineren Ergebnisses. Die extreme Empfindlichkeit multivariater Datenanpassungsmethoden, die auf konvexen Verlustfunktionen basieren, gegenüber Ausreißern wurde viele Male wiederentdeckt. Siehe (2) für eine Illustration im spezifischen Kontext von ML-Methoden.

Bearbeiten.

t

s=argmaxs[pLvar(tL(s))+pRvar(tR(s))]

tLtRstLtRspLtLpR=1-pLtR. Dann kann man Regressionsbäumen (und damit RFs) "y" -Raum-Robustheit verleihen, indem die in der ursprünglichen Definition verwendete Varianzfunktion durch eine robuste Alternative ersetzt wird. Dies ist im Wesentlichen der in (4) verwendete Ansatz, bei dem die Varianz durch einen robusten M-Schätzer der Skala ersetzt wird.

  • (1) Demaskierung multivariater Ausreißer und Hebelpunkte. Peter J. Rousseeuw und Bert C. van Zomeren Journal der American Statistical Association Vol. 85, Nr. 411 (September 1990), S. 633-639
  • (2) Zufälliges Klassifizierungsrauschen besiegt alle konvexen potentiellen Booster. Philip M. Long und Rocco A. Servedio (2008). http://dl.acm.org/citation.cfm?id=1390233
  • (3) C. Becker und U. Gather (1999). Der Maskierungs-Breakdown-Point der Regeln zur Identifizierung multivariater Ausreißer.
  • (4) G. Galimberti, M. Pillati & G. Soffritti (2007). Robuste Regressionsbäume basierend auf M-Schätzern. Statistica, LXVII, 173–190.

    library(forestFloor)
    library(randomForest)
    library(rgl)
    set.seed(1)

    X<-data.frame(replicate(2,runif(2000)-.5))
    y<--sqrt((X[,1])^4+(X[,2])^4)
    Col<-fcol(X,1:2) #make colour pallete by x1 and x2
    #insert outlier2 and colour it black
    y2<-y;Col2<-Col
    y2[1:100]<-rnorm(100,200,1);    #outliers
    Col[1:100]="#000000FF" #black

    #plot training set
    plot3d(X[,1],X[,2],y,col=Col)
    rf=randomForest(X,y)    #RF on clean data
    rg=randomForest(X,y2)   #RF on contaminated data
    vec.plot(rg,X,1:2,col=Col,grid.lines=200)
    mean(abs(rf$predict[-c(1:100)]-y[-c(1:100)]))
    mean(abs(rg$predict[-c(1:100)]-y2[-c(1:100)]))
user603
quelle
Danke für deine ausführliche Antwort. Befinden sich mehrere Ausreißer im selben hochdimensionalen Raum, stellt sich die Frage, nach welchen Kriterien wir einen „Ausreißer“ nennen sollen. In diesem Fall frage ich mich, welche Hyperparameter festgelegt werden können, damit ich a priori Kriterien für einen Ausreißer festlegen kann.
Hunle
1
Ich habe meine früheren Kommentare zu meiner Antwort hinzugefügt. Ich hoffe, dass es Ihre Frage jetzt besser beantwortet!
user603
1
Vielen Dank. Was ist pund sin der Formel?
Hunle
1
Warum sind kombinierte Ausreißer (1a + 2) schlecht? In Ihrem Beispiel passte das RF-Modell perfekt zur Datenstruktur, 99,99% OOB MSE. Die Modellstruktur des mittleren Landes zwischen den beiden Clustern ist ziemlich grob und eher ein Produkt des Modells als der Daten. In diesem unbekannten Bereich sollten sich jedoch keine Schlussfolgerungen und / oder Vorhersagen befinden, sodass dies keine Rolle spielt. Absolute Robustheit gegenüber Ausreißern ist unumgänglich, um seltene, aber möglicherweise wichtige mögliche Ereignisse zu ignorieren. Die meisten ML-Algen würden standardmäßig einen Mittelweg zwischen Robustheit und "Flexibilität" einnehmen, können aber zur Erhöhung der Robustheit optimiert werden.
Soren Havelund Welling
1
@ user603 Nichts zur technischen Diskussion hinzuzufügen, außer diesem Heart of Darkness war mein Lieblingsbuch als Kind, mit Franz Kafkas The Trial an zweiter Stelle (es wäre vielleicht das erste gewesen, wenn es fertig und vielleicht in Englisch geschrieben worden wäre - dann wieder, vielleicht passte es, dass es nicht fertig war). Ich habe nicht wirklich vom Ausreißer-Standpunkt aus darüber nachgedacht, außer dass ich Heart of Darkness und The Trials als (gute) Ausreißer im Meer von BS betrachtete die ähnliche Analyse auf.
Mark L. Stone
11

Ausreißer 1a: Dieser Ausreißer weist einen oder mehrere extreme Merkmalswerte auf und ist von jeder anderen Stichprobe entfernt. Der Ausreißer beeinflusst die anfänglichen Teilungen der Bäume wie jede andere Stichprobe, also keinen starken Einfluss. Es hat eine geringe Nähe zu anderen Stichproben und definiert die Modellstruktur nur in einem entfernten Teil des Merkmalsbereichs. Während der Vorhersage sind die meisten neuen Stichproben wahrscheinlich nicht mit diesem Ausreißer vergleichbar und landen selten im selben Endknoten. Außerdem betrachten Entscheidungsbäume Merkmale als ordinal (Rangfolge). Der Wert ist entweder kleiner / gleich oder größer als der Unterbrechungspunkt, daher spielt es keine Rolle, ob ein Merkmalswert ein extremer Ausreißer ist.

Ausreißer 1b: Für die Klassifizierung kann eine einzelne Stichprobe als Ausreißer angesehen werden, wenn sie in die Mitte vieler Stichproben einer anderen Klasse eingebettet ist. Ich habe bereits beschrieben, wie ein Standard-HF-Modell von dieser einen Stichprobe einer ungeraden Klasse beeinflusst wird, jedoch nur sehr nahe an der Stichprobe.

Ausreißer 2: Dieser Ausreißer hat einen extremen Zielwert, der möglicherweise um ein Vielfaches höher ist als alle anderen Werte, aber die Merkmalswerte sind normal. Ein 0,631-Bruchteil der Bäume wird mit dieser Stichprobe einen Endknoten haben. Die Modellstruktur wird lokal in der Nähe des Ausreißers beeinflusst. Beachten Sie, dass die Modellstruktur hauptsächlich parallel zur Feature-Achse beeinflusst wird, da Knoten einheitlich aufgeteilt werden.

y=(x14+x24)12x1x2

Bildbeschreibung hier eingeben

library(forestFloor)
library(randomForest)
library(rgl)
set.seed(1)

X = data.frame(replicate(2,runif(2000)-.5))
y = -sqrt((X[,1])^4+(X[,2])^4)^1
Col = fcol(X,1:2) #make colour pallete by x1 and x2
#insert outlier2 and colour it black
X[1,] = c(0,0);y[1]=2 ;Col[1] = "#000000FF" #black

#plot training set
plot3d(X[,1],X[,2],y,col=Col)

rf = randomForest(X,y)
vec.plot(rf,X,1:2,col=Col,grid.lines = 400)

BEARBEITEN: Kommentar an User603

Ja, bei extremen Ausreißern auf der Zielskala sollte eine Transformation der Zielskala in Betracht gezogen werden, bevor RF ausgeführt wird. Ich habe unten eine robustModel () -Funktion hinzugefügt, die randomForest optimiert. Eine andere Lösung wäre, die Transformation vor dem Training zu protokollieren.

.
##---code by user603
library(forestFloor)
library(randomForest)
library(rgl)
set.seed(1)

X<-data.frame(replicate(2,runif(2000)-.5))
y<--sqrt((X[,1])^4+(X[,2])^4)
Col<-fcol(X,1:2) #make colour pallete by x1 and x2

#insert outlier2 and colour it black
y2<-y;Col2<-Col
y2[1:100]<-rnorm(100,200,1);    #outliers
Col2[1:100]="#000000FF" #black
##---

#function to make models robust
robustModel = function(model,keep.outliers=TRUE) {
  f = function(X,y,lim=c(0.1,.9),keep.outliers="dummy",...) {
  limits = quantile(y,lim)
  if(keep.outliers) {#keep but reduce outliers
  y[limits[1]>y] = limits[1] #lower limit
  y[limits[2]<y] = limits[2] #upper limit
  } else {#completely remove outliers
    thrashThese = mapply("||",limits[1]>y,limits[2]>y)
    y = y[thrashThese]
    X = X[thrashThese,]
  }
  obj = model(x=X,y=y,...)
  class(obj) = c("robustMod",class(obj))
  return(obj)
  }
  formals(f)$keep.outliers = keep.outliers
  return(f)
}

robustRF = robustModel(randomForest) #make RF robust
rh = robustRF(X,y2,sampsize=250)     #train robustRF
vec.plot(rh,X,1:2,col=Col2)          #plot model surface
mean(abs(rh$predict[-c(1:100)]-y2[-c(1:100)]))

Bildbeschreibung hier eingeben

Soren Havelund Welling
quelle
Sie schreiben "keine andere Vorhersage wird beeinflusst". Wenn Sie Ihren einzelnen Ausreißer verschieben, um zu setzen, werden y[1]=200Sie sehen, dass er allein den Vorhersagefehler auf den nicht kontaminierten Beobachtungen veranlasst , um einen Faktor 20 zu springen!
user603
@ user603 Richtig, in solchen Fällen kann die Zielskala vor der Übergabe an RF monoton transformiert werden. Ich habe meiner Antwort ein 'robustModel: macht Modelle robust' hinzugefügt ..... natürlich bleibt es unmöglich, solche zufälligen Zielausreißer (Typ 2) vorherzusagen, aber die verbleibende Modellstruktur muss nicht leiden
Soren Havelund Welling
Die Protokolltransformation ist im Allgemeinen keine Lösung für Ausreißer (sie verbirgt lediglich das Problem). Die von Ihnen vorgeschlagene Stabilisierung der Hochfrequenz ist im Wesentlichen der in Galimberti, G., Pillati, M. und Soffritti, G. vertretene Ansatz (siehe meine Antwort). Der Hauptunterschied besteht darin, dass Ihr "robustModel" -Ansatz einen maximalen Ausfallpunkt von 25% im Antwortbereich hat (er kann 25% oder beliebige "y" -Ausreißer aushalten), während ihr BDP 50% beträgt. Beachten Sie, dass keiner der beiden Ansätze ist robust für Ausreißer im Designbereich
user603
8

Es ist nicht der Random Forest-Algorithmus selbst, der für Ausreißer robust ist, sondern der grundlegende Lernstoff, auf dem er basiert: der Entscheidungsbaum . Entscheidungsbäume isolieren atypische Beobachtungen in kleine Blätter (dh kleine Teilräume des ursprünglichen Raums). Darüber hinaus sind Entscheidungsbäume lokale Modelle. Im Gegensatz zur linearen Regression, bei der die gleiche Gleichung für den gesamten Raum gilt, wird jedem Unterraum (dh jedem Blatt) lokal ein sehr einfaches Modell angepasst.

  • Bei der Regression handelt es sich im Allgemeinen um ein Regressionsmodell sehr niedriger Ordnung (normalerweise nur der Durchschnitt der Beobachtungen im Blatt).
  • Bei der Klassifizierung handelt es sich um eine Mehrheitswahl.

Aus diesem Grund wirken sich Extremwerte beispielsweise für die Regression nicht auf das gesamte Modell aus, da sie lokal gemittelt werden. Die Anpassung an die anderen Werte ist also nicht betroffen.

Tatsächlich überträgt sich diese wünschenswerte Eigenschaft auf andere baumartige Strukturen wie Dendogramme. Hierarchisches Clustering wird beispielsweise seit langem für die Datenbereinigung verwendet, da es abweichende Beobachtungen automatisch in kleine Cluster aufteilt. Siehe zum Beispiel Loureiro et al. (2004). Ausreißererkennung mithilfe von Clustering-Methoden: eine Datenbereinigungsanwendung .

Kurz gesagt, RF erbt seine Unempfindlichkeit gegenüber Ausreißern durch rekursive Partitionierung und lokale Modellanpassung .

Beachten Sie, dass Entscheidungsbäume eine geringe Verzerrung aufweisen, aber Modelle mit hoher Varianz: Ihre Struktur kann sich bei einer kleinen Änderung des Trainingssatzes ändern (Entfernen oder Hinzufügen einiger Beobachtungen). Dies sollte jedoch nicht mit der Empfindlichkeit gegenüber Ausreißern verwechselt werden, dies ist eine andere Sache.

Antoine
quelle
Wie Sie vorschlagen, habe ich tatsächlich überlegt, eine Clustering-Methode zur Erkennung von Ausreißern zu verwenden. Aber dann bin ich mir nicht sicher, wo ich das Clustering anwenden soll. Sollte es auf labeledoder unlabeledDaten angewendet werden? Und wie könnte diese Clusterbildung für heterogene Daten erreicht werden, die sowohl kategoriale als auch numerische Merkmale enthalten?
Hunle