Czy modele CART mogą być solidne?

Mój kolega z mojego biura powiedział mi dzisiaj: „Modele drzew nie są dobre, ponieważ przyłapują ich ekstremalne obserwacje”.

Wyszukiwanie tutaj zaowocowało tym wątkiem, który zasadniczo obsługuje roszczenie.

Co prowadzi mnie do pytania - w jakiej sytuacji model CART może być solidny i jak to pokazano?

— Tal Galili
źródło

Odpowiedzi:

Nie, nie w obecnej formie. Problem polega na tym, że funkcji wypukłych ubytków nie można uczynić odpornymi na zanieczyszczenie wartościami odstającymi (jest to dobrze znany fakt od lat 70., ale wciąż jest odnawiany okresowo, patrz na przykład ten artykuł z niedawnym ponownym odkryciem):

http://www.cs.columbia.edu/~rocco/Public/mlj9.pdf

Teraz, w przypadku drzew regresyjnych, można zastosować fakt, że CART używa marginesów (lub alternatywnie projekcji jednowymiarowych): można pomyśleć o wersji CART, w której kryterium sd jest zastąpione bardziej solidnym odpowiednikiem (MAD lub jeszcze lepszym, Estymator Qn).

Edytować:

Ostatnio natknąłem się na starszy artykuł wdrażający sugerowane powyżej podejście (używając solidnego estymatora skali M zamiast MAD). Zapewni to solidność wartościom „y” wartości CART / RF (ale nie wartościom odstającym zlokalizowanym w przestrzeni projektowej, co wpłynie na oszacowania hiper-parametrów modelu). Patrz:

Galimberti, G., Pillati, M., i Soffritti, G. (2007). Solidne drzewa regresji oparte na estymatorach M. Statistica, LXVII, 173–190.

— użytkownik603
źródło

Dziękuję kwak. Ten artykuł wydaje się mówić o metodach ulepszania. Czy przedstawione przez nich wyniki odnoszą się do prostego przypadku klasyfikatora modelu CART? (na pierwszy rzut oka to tak brzmi, ale nie przeczytałem wystarczająco dużo artykułu, aby naprawdę wiedzieć)

— Tal Galili

Przedstawiony przez nich wynik ma zastosowanie do dowolnej funkcji wypukłej utraty i był początkowo omawiany przez Tukeya. Podsumowując, miara rozprzestrzeniania się (Gini lub entropia) stosowana do kwantyfikacji jakości węzła jest wrażliwa na zanieczyszczenie przez wartości odstające (tj. Obserwacje, które są źle oznaczone w zbiorze danych). Ten problem dotyczy zarówno etapu budowy, jak i etapu ogłuszania. Zanieczyszczenie zestawu danych przez obserwację niewłaściwie przypisaną etykietą zwykle powoduje, że powstałe drzewo jest o wiele za złożone (można to dość łatwo sprawdzić samodzielnie).

— user603

Dziękuję Kwak! I czy nie ma solidnej funkcji utraty?

— Tal Galili,

brak funkcji wypukłej utraty. Zobacz artykuł „Szybki algorytm dla estymatora minimalnej determinanty kowariancji”, aby zapoznać się z przykładem tego, co można zrobić z niewypukłymi funkcjami strat (chociaż nie jest to związane z klasyfikacją, artykuł jest wart przeczytania).

— user603

@Tal CART jest równoważny wzmocnieniu „klasyfikatora przestawnego” (kryterium, które znajduje się w każdym węźle drzewa, jak niektóre większe atrybuty niż coś lub pewna wartość atrybutu w zestawie czegoś).

Możesz rozważyć użycie worków lub losowych lasów Breimana . Jednym z dobrych odniesień jest Breiman „Bagging Predictors” (1996). Również streszczone w Clifton Sutton's „Drzewa klasyfikacji i regresji, workowanie i wzmacnianie” w Handbook of Statistics.

Możesz także zobaczyć dyskusję Andy Liaw i Matthew Wiener R News na temat pakietu randomForest.

— Shane
źródło

Nie zepsuć przyjęcia, ale jak losowy las ma zapewniać odporność na zanieczyszczenia przez wartości odstające jest tajemnicą.

— user603

@kwak To wciąż dobra odpowiedź; drzewa w RF nie widzą całego zestawu, więc wiele z nich nie zostanie zanieczyszczonych. Jeszcze lepiej - śledzenie, w którym liście wykonują skrzynki OOB, może być wykorzystane do znalezienia źle oznakowanych obiektów i ich wyeliminowania. (Jak pamiętam teraz, wspomniano o tym w artykule Breimana o RF).

Problem polega na tym, że wartości odstające sprawią, że niektóre „złe” (tj. Zanieczyszczone) drzewa będą wyglądać lepiej niż dobre (niezanieczyszczone). Nazywa się to efektem maskowania i można go łatwo powielić przy użyciu danych symulowanych. Problem pojawia się, ponieważ kryterium stosowane do oceny drzew nie jest samo w sobie odporne na wartości odstające. Wiem, że zaczynam brzmieć jak fundamentalistyczny mułła, ale jeśli każde narzędzie, którego używasz, nie jest solidne, możesz wykazać, że twoja procedura jest wrażliwa (na takim czy innym poziomie) na wartości odstające (a zatem nie na solidne).

— user603,

Jeśli sprawdzisz pakiet „gbm” w R (uogólnione zwiększenie gradientu), to „wzmocnienie” używa funkcji strat, które niekoniecznie oznaczają błąd kwadratowy. Pokazuje to argument „dystrybucji” funkcji „gbm ()”. Zatem opracowanie drzewa poprzez wzmocnienie będzie odporne na wartości odstające, podobnie jak w przypadku działania estymatorów M.

Możesz zacząć tutaj .

Innym podejściem byłoby zbudowanie drzewa w zwykły sposób (partycje oparte na SSE), ale przycinanie drzewa za pomocą walidacji krzyżowej z solidną miarą dopasowania. Myślę, że xpred w rpart da sprawdzone predykcyjnie predykatory (dla wielu różnych złożoności drzew), które możesz następnie zastosować własną miarę błędu, taką jak średnia wartość bezwzględna.

— AlaskaRon
źródło