Schnelle lineare Regression, robust gegenüber Ausreißern

50

Ich habe es mit linearen Daten mit Ausreißern zu tun, von denen einige um mehr als 5 Standardabweichungen von der geschätzten Regressionslinie abweichen. Ich suche nach einer linearen Regressionstechnik, die den Einfluss dieser Punkte verringert.

Bisher habe ich die Regressionsgerade mit allen Daten geschätzt, dann den Datenpunkt mit sehr großen quadratischen Residuen (sagen wir die oberen 10%) verworfen und die Regression ohne diese Punkte wiederholt.

In der Literatur gibt es viele mögliche Ansätze: am wenigsten zugeschnittene Quadrate, Quantilregression, m-Schätzer usw. Ich weiß wirklich nicht, welchen Ansatz ich versuchen soll, also suche ich nach Vorschlägen. Für mich ist wichtig, dass die gewählte Methode schnell ist, da die robuste Regression bei jedem Schritt einer Optimierungsroutine berechnet wird. Danke vielmals!

regression linear-model outliers robust fused-lasso Matteo Fasiolo
quelle

2

Ein Verfahren , dass Sie nicht erwähnt , ist die Verwendung von Student- Fehler mit unbekannten Freiheitsgraden. Dies ist jedoch möglicherweise nicht so schnell, wie Sie es benötigen.

t

$t$

@Procrastinator: (Man kann sich leicht eine Konfiguration von Ausreißern vorstellen, bei der dies nicht funktioniert.)

user603

@ user603 Das stimmt für jede Methode, es gibt kein Allheilmittel;). Ich habe nur eine andere Methode aufgezeigt. +1 auf deine Antwort.

3

@Procrastinator: Ich bin damit einverstanden, dass alle Methoden für eine gewisse Kontaminationsrate fehlschlagen . Und "Misserfolg" kann in diesem Zusammenhang quantitativ und empirisch definiert werden. Die Idee ist jedoch, immer noch die Methoden zu bevorzugen, die nur bei höheren Kontaminationsraten scheitern.

user603

4

Da dies während einer Optimierungsroutine wiederholt durchgeführt wird, ändern sich die Daten in der Regression (möglicherweise) langsam. Dies deutet auf einen Algorithmus hin, der an Ihre Situation angepasst ist: Beginnen Sie mit einer stabilen Regression. Wenn Sie jedoch während der Optimierung kleine Schritte ausführen, gehen Sie im nächsten Schritt einfach davon aus, dass jeder vorherige Ausreißer ein Ausreißer bleibt. Verwenden Sie OLS für die Daten und prüfen Sie dann, ob die mutmaßlichen Ausreißer noch ausreißen. Wenn nicht, starten Sie mit der robusten Prozedur neu. Wenn dies jedoch der Fall ist - was häufig vorkommt -, haben Sie eine Menge Berechnungen eingespart.

Whuber

55

Wenn Ihre Daten einen einzelnen Ausreißer enthalten, können sie mit dem von Ihnen vorgeschlagenen Ansatz zuverlässig gefunden werden (allerdings ohne die Iterationen). Ein formeller Ansatz hierfür ist

Cook, R. Dennis (1979). Einflussreiche Beobachtungen in der linearen Regression . Journal of the American Statistical Association (Amerikanische statistische Vereinigung) 74 (365): 169–174.

Um mehr als einen Ausreißer über viele Jahre hinweg zu finden, war die führende Methode die sogenannte Bestimations - Ansatzfamilie. Dies ist eine ziemlich breite Familie von Schätzern, zu denen Hubers Schätzer der Regression, Koenkers L1-Regression sowie der von Procastinator in seinem Kommentar zu Ihrer Frage vorgeschlagene Ansatz gehören. Die Schätzer mit konvexen Funktionen haben den Vorteil, dass sie in etwa die gleiche numerische Komplexität haben wie eine reguläre Regressionsschätzung. Der große Nachteil ist, dass sie die Ausreißer nur zuverlässig finden können, wenn: $M$ $M$ $M$ $\rho$

Die Kontaminationsrate Ihrer Probe ist kleiner als wobei die Anzahl der Entwurfsvariablen ist. $\frac{1}{1+p}$ $p$
oder wenn sich die Ausreißer nicht im Entwurfsraum befinden (Ellis und Morgenthaler (1992)).

Eine gute Implementierung von ( ) Regressionsschätzungen finden Sie im ( ) -Paket. $M$ $l_1$ robustbasequantregR

Wenn Ihre Daten mehr als Ausreißer enthalten, die möglicherweise auch außerhalb des Entwurfsbereichs liegen, dann bedeutet das Auffinden, dass ein kombinatorisches Problem gelöst wird (entsprechend der Lösung eines Schätzers mit neuem absteigende / nicht konvexe Funktion). $\lfloor\frac{n}{p+1}\rfloor$ $M$ $\rho$

In den letzten 20 Jahren (und insbesondere in den letzten 10 Jahren) wurde eine Vielzahl schneller und zuverlässiger Ausreißererkennungsalgorithmen entwickelt, um dieses kombinatorische Problem näherungsweise zu lösen. Diese sind mittlerweile in den gängigsten Statistikpaketen (R, Matlab, SAS, STATA, ...) weit verbreitet.

Die numerische Komplexität der Ermittlung von Ausreißern mit diesen Ansätzen liegt jedoch typischerweise in der Größenordnung von . Die meisten Algorithmen können in der Praxis für Werte von im mittleren Teenageralter verwendet werden. In der Regel sind diese Algorithmen in (Anzahl der Beobachtungen) linear, sodass die Anzahl der Beobachtungen kein Problem darstellt. Ein großer Vorteil ist, dass die meisten dieser Algorithmen peinlich parallel sind. In jüngerer Zeit wurden viele Ansätze speziell für höherdimensionale Daten vorgeschlagen. $O(2^p)$ $p$ $n$

Da Sie in Ihrer Frage nicht angegeben haben , werde ich einige Referenzen für den Fall . Im Folgenden finden Sie einige Artikel, die dies in dieser Reihe von Übersichtsartikeln näher erläutern: $p$ $p<20$

Rousseeuw, PJ und van Zomeren BC (1990). Demaskierung multivariater Ausreißer und Hebelpunkte . Journal of the American Statistical Association , Bd. 85, Nr. 411, S. 633-639.

Rousseeuw, PJ und Van Driessen, K. (2006). Berechnen der LTS-Regression für große Datenmengen . Archiv für Data Mining und Knowledge Discovery, Band 12, Ausgabe 1, Seiten 29 - 45.

Hubert, M., Rousseeuw, PJ und Van Aelst, S. (2008). Robuste multivariate Methoden mit hoher Ausfallrate . Statistical Science , Vol. 1, 92–119

Ellis SP und Morgenthaler S. (1992). Hebelwirkung und Zusammenbruch der L1-Regression. Journal of the American Statistical Association , Bd. 87, Nr. 417, S. 143-148

Ein aktuelles Nachschlagewerk zum Problem der Ausreißeridentifikation ist:

Maronna RA, Martin RD und Yohai VJ (2006). Robuste Statistik: Theorie und Methoden . Wiley, New York.

Diese (und viele andere Variationen dieser) Methoden sind (unter anderem) im Paket implementiert.robustbase R

user603
quelle

4

Das ist eine großartige Antwort!

Peter Flom - Wiedereinsetzung von Monica

Vielen Dank user603! In meinem Problem und es gibt keine Ausreißer im Entwurfsraum (weil die erklärenden Variablen von einer Normalverteilung simuliert werden). Also kann ich es vielleicht mit dem m-estimator versuchen? In jedem Fall werden alle anderen Referenzen, die Sie mir gegeben haben, sehr nützlich sein, sobald ich anfange, an komplexeren Anwendungen ( >> 10) meines Algorithmus zu arbeiten.

p < 10

$p < 10$

p

$p$

Matteo Fasiolo

2

@Jugurtha: In diesem Fall (kein Ausreißer im Entwurfsraum und ) sind Schätzer in der Tat die bevorzugte Lösung. Betrachten Sie die Funktion 'lmrob..M..fit' im Paket robustbase, die Funktion 'rlm' im Paket MASS oder die Regression l1 im Paket quantreg. In einigen Fällen würde ich auch noch die LTS-Regression durchführen und die Ergebnisse vergleichen, da sie mehr Ausreißern standhalten können. Ich würde dies nur tun, um zu überprüfen, ob die Kontaminationsrate nicht höher ist, als Sie vermuten.

p < 10

$p<10$

M

$M$

user603

1

"Ein großer Vorteil ist, dass die meisten dieser Algorithmen peinlich parallel sind." Ich mag den Wortlaut. ;)

Mateen Ulhaq

1

@Mateen, na ja, das ist doch der Begriff der Kunst . :)

JM ist kein Statistiker

19

Für die einfache Regression (single x) gibt es für die Theil-Sen-Linie etwas zu sagen, was die Robustheit gegenüber y-Ausreißern und einflussreichen Punkten sowie die im Allgemeinen gute Effizienz (im Normalfall) im Vergleich zu LS für die Steigung betrifft. Der Durchschlagspunkt für die Steigung liegt bei fast 30%; Solange der Abschnitt (es gibt eine Vielzahl möglicher Abschnitte, die von Menschen verwendet wurden) keine geringere Aufschlüsselung aufweist, kommt das gesamte Verfahren mit einem beträchtlichen Kontaminationsanteil recht gut zurecht.

Die Geschwindigkeit mag sich schlecht anhören - der Median von Steigungen scheint selbst mit einem Median - aber ich erinnere mich, dass es schneller geht wenn Geschwindigkeit wirklich ein Problem ist ( , glaube ich) $\binom{n}{2}$ $O(n^2)$ $O(n)$ $O(n \log n)$

Edit: user603 hat um einen Vorteil der Theil-Regression gegenüber der L1-Regression gebeten. Die Antwort ist die andere Sache, die ich erwähnt habe - einflussreiche Punkte:

Theil_vs_L1

Die rote Linie ist die Anpassung (aus der Funktion im Paket). Das Grün passt zu einem Theil-Hang. Alles, was es braucht, ist ein Tippfehler im x-Wert - wie die Eingabe von 533 anstelle von 53 - und so etwas kann passieren. Daher ist die Anpassung für einen einzelnen Tippfehler im x-Raum nicht robust. $L_1$ rqquantreg $L_1$

Glen_b
quelle

es kann in der Tat in der Zeit berechnet werden . Könnten Sie näher erläutern, welchen Vorteil der TS-Schätzer (im Einzelfall x) gegenüber der Regression hat?

n \log n

$n\log n$

l_{1}

$l_1$

user603

1

@ user603 Siehe Bearbeiten.

Glen_b

(+1) Danke für die Bearbeitung. Es ist wichtig, auf dieses Merkmal hinzuweisen.

user603

1

Und was ist der Vorteil gegenüber einer MM-Schätzung wie lmrob () aus dem R-Paket robustbase oder sogar rlm (*, ... method = "MM") aus dem Paket MASS? Diese haben einen vollen Durchschlagspunkt (~ 50%) und sind im Normalfall wahrscheinlich noch effizienter.

Martin Mächler

1

@ MartinMächler Es scheint, als würden Sie gegen eine Behauptung argumentieren, die ich dort nicht gemacht habe. Wenn Sie eine Antwort verfassen möchten, die auch einen Vergleich anderer zuverlässiger Schätzer enthält, insbesondere solcher, die für jemanden auf der Ebene des OP ungefähr so einfach zu verstehen sind, würde ich mich darauf freuen, sie zu lesen.

Glen_b

12

Haben Sie sich RANSAC (Wikipedia) angesehen ?

Auf diese Weise sollte ein vernünftiges lineares Modell berechnet werden können, auch wenn es viele Ausreißer und Rauschen gibt, da davon ausgegangen wird, dass nur ein Teil der Daten tatsächlich zum Mechanismus gehört.

Anony-Mousse
quelle

ja aber Hinzufügen einer einfachen Wiedergewichtungsschritt ergibt ein Schätzer (LTS) , die ebenso robust ist und so viel stabiler und statistisch effizient. Warum nicht?

user603

1

Ich fand die bestrafte Fehlerregression am besten. Sie können es auch iterativ verwenden und Proben neu gewichten, die mit der Lösung nicht sehr konsistent sind. Die Grundidee ist, Ihr Modell mit Fehlern zu erweitern: wobei der unbekannte Fehlervektor ist. Nun führen Sie die Regression für . Interessanterweise können Sie hierfür natürlich "Fused Lasso" verwenden, wenn Sie die Sicherheit Ihrer Messungen im Voraus abschätzen und diese als Gewichtung in und die neue geringfügig andere Aufgabe lösen können $l_1$

y = A x + e

$y=Ax+e$

e

$e$

∥ y - A x - e ∥_{2}^{2} + λ ∥ e ∥_{1}

$\parallel y-Ax-e \parallel_2^2+ \lambda \parallel e \parallel_1$

W = d i a g (w_{i})

$W=diag(w_i)$

∥ y - A x - e ∥_{2}^{2} + λ ∥ W e ∥_{1}

$\parallel y-Ax-e \parallel_2^2 + \lambda \parallel W e \parallel_1$

Weitere Informationen finden Sie hier: http://statweb.stanford.edu/~candes/papers/GrossErrorsSmallErrors.pdf

mojovski
quelle

hast du das am beispiel glen_b probiert (wenn du einen zweiten ausreißer neben dem platzierst den er hat) oder hab ich gepostet?

user603

@ user603 nein, ich habe dies gerade auf praktischere Fälle für die 3D-Modellierung von Kamerabildern angewendet. Da hat es sehr geholfen. Die Lektion lautet jedoch: Wenn Sie mehrere Möglichkeiten haben, Ihre Ausreißer zu eliminieren, verwenden Sie diese.

Mojovski

Schnelle lineare Regression, robust gegenüber Ausreißern

Antworten: