Szybka regresja liniowa odporna na wartości odstające

50

Mam do czynienia z danymi liniowymi z wartościami odstającymi, z których niektóre są o 5 standardowych odchyleń od szacowanej linii regresji. Szukam techniki regresji liniowej, która zmniejsza wpływ tych punktów.

Jak dotąd oszacowałem linię regresji ze wszystkimi danymi, a następnie odrzuciłem punkt danych z bardzo dużymi kwadratowymi resztkami (powiedzmy 10%) i powtórzyłem regresję bez tych punktów.

W literaturze istnieje wiele możliwych podejść: najmniej przycięte kwadraty, regresja kwantylowa, estymatory m itp. Naprawdę nie wiem, które podejście powinienem wypróbować, dlatego szukam sugestii. Dla mnie ważne jest to, że wybrana metoda powinna być szybka, ponieważ solidna regresja będzie obliczana na każdym etapie procedury optymalizacji. Wielkie dzięki!

regression linear-model outliers robust fused-lasso Matteo Fasiolo
źródło

2

Metodą, o której nie wspomniałeś, jest użycie błędów o nieznanych stopniach swobody. Może to jednak nie być tak szybkie, jak potrzebujesz.

t

$t$

@ Procrastinator: (Łatwo wyobrazić sobie konfigurację wartości odstających, gdzie) nie będzie to działać.

user603,

@ user603 Tak jest w przypadku każdej metody, nie ma Panacei;). Po prostu wskazałem inną metodę. +1 do twojej odpowiedzi.

3

@ Procrastinator: Zgadzam się, że wszystkie metody zawiodą w przypadku pewnego stopnia zanieczyszczenia . „Niepowodzenie” w tym kontekście można zdefiniować ilościowo i empirycznie. Chodzi jednak o to, by nadal faworyzować metody, które zawiodą tylko przy wyższych poziomach zanieczyszczenia.

user603

4

Ponieważ robi się to wielokrotnie podczas procedury optymalizacji, być może dane w regresji (ewentualnie) zmieniają się powoli. Sugeruje to algorytm dostosowany do twojej sytuacji: zacznij od pewnej formy solidnej regresji, ale podczas robienia małych kroków podczas optymalizacji, po prostu załóż w następnym kroku, że każda poprzednia wartość odstająca pozostanie wartością odstającą. Użyj OLS na danych, a następnie sprawdź, czy przypuszczalne wartości odstające są nadal odległe. Jeśli nie, uruchom ponownie za pomocą solidnej procedury, ale jeśli tak - co może się zdarzyć często - zaoszczędzisz dużo obliczeń.

whuber

55

Jeśli dane zawierają jedną wartość odstającą, można je wiarygodnie znaleźć przy użyciu zaproponowanego przez Ciebie podejścia (bez iteracji). Formalne podejście do tego jest

Cook, R. Dennis (1979). Wpływowe obserwacje w regresji liniowej . Journal of the American Statistics Association (American Statistics Association) 74 (365): 169–174.

W celu znalezienia więcej niż jednej wartości odstającej od wielu lat wiodącą metodą była tak zwana rodzina metod szacowaniaJest to dość szeroka rodzina estymatorów, która obejmuje estymator regresji Hubera, regresję L1 Koenkera, a także podejście zaproponowane przez Procastinator w jego komentarzu do twojego pytania. The estymatory o wypukłym funkcji mają tę zaletę, że mają o tej samej złożoności numerycznej jako stałego oszacowania regresji. Dużą wadą jest to, że mogą niezawodnie znaleźć wartości odstające, tylko jeśli: $M$ $M$ $M$ $\rho$

stopień zanieczyszczenia próbki jest mniejszy niż gdzie jest liczbą zmiennych projektowych, $\frac{1}{1+p}$ $p$
lub jeśli wartości odstające nie są odległe w przestrzeni projektowej (Ellis i Morgenthaler (1992)).

Możesz znaleźć dobrą implementację oszacowań regresji ( ) w pakiecie ( ) . $M$ $l_1$ robustbasequantregR

Jeśli Twoje dane zawierają więcej niż odstająca potencjalnie również zależna od przestrzeni projektowej, wówczas znalezienie ich sprowadza się do rozwiązania problemu kombinatorycznego (równoważnie rozwiązanie estymatora z ponownym funkcja decending / non-wypukła ). $\lfloor\frac{n}{p+1}\rfloor$ $M$ $\rho$

W ciągu ostatnich 20 lat (a zwłaszcza ostatnich 10) opracowano dużą liczbę szybkich i niezawodnych algorytmów wykrywania wartości odstających, aby w przybliżeniu rozwiązać ten problem kombinatoryczny. Są one obecnie szeroko implementowane w najpopularniejszych pakietach statystycznych (R, Matlab, SAS, STATA, ...).

Niemniej jednak złożoność numeryczna znalezienia wartości odstających przy tych podejściach jest zazwyczaj rzędu . Większość algorytmów można zastosować w praktyce dla wartości w wieku dojrzewania. Zazwyczaj algorytmy te są liniowe w (liczbie obserwacji), więc liczba obserwacji nie stanowi problemu. Dużą zaletą jest to, że większość tych algorytmów jest żenująco równoległa. Niedawno zaproponowano wiele podejść zaprojektowanych specjalnie dla danych o wyższych wymiarach. $O(2^p)$ $p$ $n$

Biorąc pod uwagę, że nie podałeś w swoim pytaniu, wymienię niektóre odniesienia dla sprawy . Oto kilka artykułów, które wyjaśniają to bardziej szczegółowo w tej serii artykułów przeglądowych: $p$ $p<20$

Rousseeuw, PJ i van Zomeren BC (1990). Demaskowanie wielowymiarowych wartości odstających i punktów dźwigni . Journal of the American Statistics Association , t. 85, nr 411, s. 633–639.

Rousseeuw, PJ i Van Driessen, K. (2006). Obliczanie regresji LTS dla dużych zestawów danych . Archiwum Data Mining i Discovery, tom 12, wydanie 1, strony 29–45.

Hubert, M., Rousseeuw, PJ i Van Aelst, S. (2008). Odporne na awarie metody wielowymiarowe . Nauka statystyczna , tom. 23, nr 1, 92–119

Ellis SP i Morgenthaler S. (1992). Dźwignia i podział w regresji L1. Journal of the American Statistics Association , t. 87, nr 417, str. 143–148

Najnowszy podręcznik dotyczący problemu identyfikacji wartości odstających to:

Maronna RA, Martin RD i Yohai VJ (2006). Solidne statystyki: teoria i metody . Wiley, Nowy Jork.

Te (i wiele innych odmian tych) metod są implementowane (między innymi) w pakiecie.robustbase R

użytkownik603
źródło

4

To świetna odpowiedź!

Peter Flom - Przywróć Monikę

Bardzo dziękuję użytkownikowi 603! W moim problemie i nie ma wartości odstających w przestrzeni projektowej (ponieważ zmienne objaśniające są symulowane z rozkładu normalnego). Więc może spróbuję z m-estymatorem? W każdym razie wszystkie inne podane przez ciebie referencje będą bardzo przydatne, gdy zacznę pracować nad bardziej złożonymi aplikacjami ( >> 10) mojego algorytmu.

p < 10

$p < 10$

p

$p$

Matteo Fasiolo,

2

@Jugurtha: W takim przypadku (brak wartości odstającej w przestrzeni projektowej i ) estymatory są rzeczywiście preferowanym rozwiązaniem. Rozważ funkcję „lmrob..M..fit” w pakiecie robustbase, funkcję „rlm” w pakiecie MASS lub regresję l1 w pakiecie quantreg. W kilku przypadkach nadal prowadziłbym regresję LTS i porównywał wyniki, ponieważ mogą one wytrzymać więcej wartości odstających. Zrobiłbym to tylko w celu sprawdzenia, czy stopień zanieczyszczenia nie jest wyższy niż podejrzewasz.

p < 10

$p<10$

M

$M$

user603,

1

„Dużą zaletą jest to, że większość tych algorytmów jest żenująco równoległa”. Lubię to sformułowanie. ;)

Mateen Ulhaq

1

@ Mateen, cóż, w końcu jest to termin sztuki . :)

JM nie jest statystykiem

19

W przypadku prostej regresji (pojedynczy x) można powiedzieć coś o linii Theil-Sen pod względem odporności na odchylenia Y i wpływowych punktów, a także ogólnie dobrej wydajności (normalnej) w porównaniu do LS dla zbocza. Punkt przebicia stoku wynosi prawie 30%; o ile przechwytywanie (istnieje wiele możliwych przechwyceń, z których ludzie korzystali) nie ma mniejszego podziału, cała procedura dość dobrze radzi sobie ze znaczną częścią zanieczyszczenia.

Jego prędkość może brzmieć tak, jakby była zła - mediana wygląda na nawet z medianą - ale pamiętam, że można to zrobić szybciej jeśli prędkość naprawdę stanowi problem ( , myślę) $\binom{n}{2}$ $O(n^2)$ $O(n)$ $O(n \log n)$

Edycja: użytkownik603 poprosił o przewagę regresji Theil nad regresją L1. Odpowiedź to inna rzecz, o której wspomniałem - wpływowe punkty:

Theil_vs_L1

Czerwona linia to dopasowanie (od funkcji w pakiecie). Kolor zielony pasuje do stoku Theil. Wystarczy jedna literówka w wartości x - jak pisanie 533 zamiast 53 - i takie rzeczy mogą się zdarzyć. Dlatego dopasowanie nie jest odporne na pojedynczą literówkę w przestrzeni $L_1$ rqquantreg $L_1$

Glen_b
źródło

można go rzeczywiście obliczyć w czasie . Czy mógłbyś , jaką przewagę (w pojedynczym przypadku x) ma estymator TS nad, powiedzmy, regresją ?

n \log n

$n\log n$

l_{1}

$l_1$

user603 10.03.13

1

@ user603 Zobacz edycję.

Glen_b 10.03.13

(+1) dzięki za edycję. Ważne jest, aby zwrócić uwagę na tę funkcję.

user603 11.03.13

1

A jaka jest przewaga nad oszacowaniem MM, takim jak lmrob () z pakietu robustbase pakietu R, a nawet {nie trzeba niczego instalować oprócz „base R”} rlm (*, ... method = "MM") z pakietu MASS? Mają one pełny punkt podziału (~ 50%) i prawdopodobnie są jeszcze bardziej wydajne w normalnych warunkach.

Martin Mächler

1

@ MartinMächler Wygląda na to, że spierasz się z roszczeniem, którego tam nie złożyłem. Jeśli chciałbyś znaleźć odpowiedź, która zawiera także porównanie innych solidnych estymatorów o wysokim poziomie awarii, szczególnie takich, które są mniej więcej tak łatwe do zrozumienia dla kogoś na poziomie PO, chętnie je przeczytam.

Glen_b

12

Czy spojrzałeś na RANSAC (Wikipedia) ?

Powinno to być dobre w obliczaniu rozsądnego modelu liniowego, nawet gdy występuje dużo wartości odstających i szumu, ponieważ opiera się on na założeniu, że tylko część danych faktycznie należy do mechanizmu.

Anony-Mus
źródło

tak, ale dodanie prostego etapu zmiany wagi daje estymator (LTS), który jest równie solidny i o wiele bardziej stabilny i statystycznie wydajny. Dlaczego nie

user603

1

Znalazłem najlepszą regresję błędów za pomocą . Możesz także użyć iteracyjnie i ponownie zważyć próbki, które nie są zbyt spójne z rozwiązaniem. Podstawową ideą jest rozszerzenie modelu o błędy: gdzie jest nieznanym wektorem błędów. Teraz wykonujesz regresję na . Co ciekawe, możesz oczywiście użyć do tego „skondensowanego lassa”, kiedy możesz z góry oszacować pewność swoich pomiarów i umieścić to jako ważenie w i rozwiązać nowe, nieco inne zadanie $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$

Więcej informacji można znaleźć tutaj: http://statweb.stanford.edu/~candes/papers/GrossErrorsSmallErrors.pdf

mojovski
źródło

czy próbowałeś tego na przykładzie Glen_b (jeśli dodasz drugą wartość odstającą obok miejsca, w którym umieścił swoją) lub ja opublikowałem?

user603

@ user603 nie, właśnie zastosowałem to w bardziej praktycznych przypadkach do modelowania 3D z obrazów z kamery. Tam bardzo pomogło. Jednak wyciągnięto z tego lekcję: jeśli masz wiele możliwości wyeliminowania wartości odstających, skorzystaj z nich.

mojovski

Szybka regresja liniowa odporna na wartości odstające

Odpowiedzi: