Dlaczego Random Forest nie obsługuje brakujących wartości w predyktorach?

42

Jakie są teoretyczne powody, aby nie obsługiwać brakujących wartości? Maszyny zwiększające gradient, drzewa regresji radzą sobie z brakującymi wartościami. Dlaczego Random Forest tego nie robi?

Fedorenko Kristina
źródło
3
Są one obsługiwane w partypakiecie R. Jeden artykuł na blogu tutaj: exegetic.biz/blog/2013/05/…
Stéphane Laurent,

Odpowiedzi:

34

Gradient Boosting Trees wykorzystuje drzewa CART (w standardowej konfiguracji, jak zaproponowali autorzy). Drzewa CART są również używane w losowych lasach. To, co powiedział @ user777, jest prawdą, że drzewa RF radzą sobie z brakującymi wartościami albo przez imputację ze średnią, albo przez przybliżoną średnią / tryb, albo przez uśrednienie / tryb oparty na przybliżeniach. Metody te zostały zaproponowane przez Breimana i Cutlera i są stosowane w RF. Jest to odniesienie od autorów Brakujące wartości w zestawie treningowym .

Można jednak zbudować GBM lub RF z innymi typami drzew decyzyjnych. Zwykłym zamiennikiem CART jest C4.5 zaproponowany przez Quinlan. W C4.5 brakujące wartości nie są zastępowane w zestawie danych. Zamiast tego obliczona funkcja zanieczyszczenia bierze pod uwagę brakujące wartości poprzez karanie wyniku zanieczyszczenia stosunkiem brakujących wartości. Podczas testu zestaw oceny w węźle, który ma test z brakującą wartością, prognoza jest budowana dla każdego węzła potomnego i agregowana później (poprzez ważenie).

Teraz w wielu implementacjach zamiast CART używana jest C4.5. Głównym powodem jest uniknięcie kosztownych obliczeń (CART ma bardziej rygorystyczne podejście statystyczne, które wymagają więcej obliczeń), wyniki wydają się podobne, a drzewa wynikowe są często mniejsze (ponieważ CART jest binarny, a C4.5 nie). Wiem, że Weka stosuje to podejście. Nie znam innych bibliotek, ale spodziewam się, że nie będzie to szczególna sytuacja. Jeśli tak jest w przypadku implementacji GBM, to byłaby to odpowiedź.

rapaio
źródło
Daj nam kontynuować tę dyskusję w czacie .
Prophet60091,
Dotknąłeś „karania wyniku nieczystości racją brakujących wartości”. Jak to bezpośrednio wpływa na wybór optymalnych wartości wymiarów wybranych na określonym poziomie / gałęzi drzewa?
javadba
16

„Jakie są teoretyczne powody, dla których RF nie obsługuje brakujących wartości? Maszyny zwiększające gradient, drzewa regresji obsługują brakujące wartości. Dlaczego Random Forest tego nie robi?”

RF ma wartości uchwytu brakuje, tylko nie w ten sam sposób, że wózek i inne podobne algorytmy drzewo decyzja zrobienia. User777 poprawnie opisuje dwie metody stosowane przez RF do obsługi brakujących danych (mediana imputacji i / lub miary bliskości), podczas gdy Frank Harrell poprawnie opisuje, jak obsługiwane są brakujące wartości w CART (podziały zastępcze). Aby uzyskać więcej informacji, zobacz łącza do obsługi brakujących danych dla CART (lub jego kuzyna FOSS: RPART ) i RF .

Odpowiedź na twoje aktualne pytanie jest wyraźnie omówiona, IMHO, w pracy Ishwaran i wsp. Z 2008 r. Zatytułowanej Random Survival Forests . Podają następujące prawdopodobne wyjaśnienie, dlaczego RF nie obsługuje brakujących danych w taki sam sposób, jak CART lub podobne klasyfikatory drzewa pojedynczej decyzji:

„Chociaż podział surogatów działa dobrze na drzewa, metoda może nie być odpowiednia dla lasów. Szybkość jest jednym z problemów. Znalezienie podziału surogatów jest intensywne obliczeniowo i może stać się niemożliwe przy uprawie dużej liczby drzew, szczególnie w przypadku drzew w pełni nasyconych używanych przez lasy. Ponadto podziały zastępcze mogą nawet nie mieć znaczenia w paradygmacie leśnym. RF losowo wybiera zmienne podczas podziału węzła i jako takie zmienne w węźle mogą być nieskorelowane, a rozsądny podział zastępczy może nie istnieć. Innym problemem jest to, że podział zastępczy zmienia interpretację zmiennej, co wpływa na miary takie jak [Znaczenie zmiennej].

Z tych powodów dla RF wymagana jest inna strategia. ”

To jest na bok, ale dla mnie podważa to tych, którzy twierdzą, że RF używa zestawu modeli CART. Widziałem to twierdzenie w wielu artykułach, ale nigdy nie widziałem, aby takie oświadczenia pochodziły z jakiegokolwiek wiarygodnego tekstu w RF. Po pierwsze, drzewa w RF są uprawiane bez przycinania , co zwykle nie jest standardowym podejściem przy budowie modelu CART. Innym powodem może być ten, na który powołujesz się w swoim pytaniu: CART i inne zestawy drzew decyzyjnych obsługują brakujące wartości, podczas gdy [oryginalne] RF nie, przynajmniej wewnętrznie tak jak CART.

Mając na uwadze powyższe zastrzeżenia, myślę, że można powiedzieć, że RF wykorzystuje zestaw drzew decyzyjnych podobnych do CART (tj. Wiązka nie przycinanych drzew, wyhodowanych w maksymalnym stopniu, bez możliwości obsługi brakujących danych poprzez dzielenie zastępcze). Być może jest to jedna z tych punktowych różnic semantycznych, ale myślę, że warto ją zauważyć.


EDYCJA : W mojej notatce dodatkowej, która nie ma związku z faktycznie zadanym pytaniem, stwierdziłem, że „nigdy nie widziałem, aby takie oświadczenia pochodziły od jakiegokolwiek wiarygodnego tekstu w RF”. Okazuje się, że Breiman DID wyraźnie stwierdza, że ​​drzewa decyzyjne CART są używane w oryginalnym algorytmie RF:

„Najprostszy losowy las z losowymi funkcjami jest tworzony przez losowe wybranie w każdym węźle małej grupy zmiennych wejściowych do podziału. Wyhoduj drzewo przy użyciu metodologii CART do maksymalnego rozmiaru i nie przycinaj”. [Mój nacisk]

Źródło: s. 9 Losowych lasów. Breiman (2001)

Nadal jednak stoję (choć bardziej niepewnie) na przekonaniu, że są to drzewa decyzyjne podobne do CART , ponieważ są uprawiane bez przycinania, podczas gdy CART zwykle nie jest uruchamiany w tej konfiguracji, ponieważ prawie na pewno nadmiernie przewyższa twoje dane ( stąd przede wszystkim przycinanie).

Prophet60091
źródło
11

Losowy las obsługuje brakujące dane i istnieją dwa różne sposoby:

1) Bez przypisywania brakujących danych, ale zapewnianie wnioskowania. 2) Zapisywanie danych. Dane przypisane są następnie wykorzystywane do wnioskowania.

Obie metody są zaimplementowane w moim pakiecie R randomForestSRC (napisany wspólnie z Udaya Kogalur). Po pierwsze, należy pamiętać, że ponieważ losowe lasy stosują losowy wybór funkcji, tradycyjne metody brakujących danych stosowane przez pojedyncze drzewa (CART i tym podobne) nie mają zastosowania. Ten punkt został poruszony w Ishwaran i in. (2008), „Random Survival Forests”, Annals of Applied Statistics , 2 , 3 i ładnie artykułowane przez jednego z komentatorów.

Metoda (1) to metoda „imputacji w locie” (OTFI). Przed podzieleniem węzła brakujące dane dla zmiennej są przypisywane losowym losowaniem wartości z brakujących danych w torbie. Celem tych przypisanych danych jest umożliwienie przypisania obserwacji do węzłów potomnych w przypadku, gdy węzeł zostanie podzielony na zmienną z brakującymi danymi. Dane przypisane nie są jednak wykorzystywane do obliczania statystyki podziału, która wykorzystuje tylko brakujące dane. Po podziale węzłów dane przypisane są resetowane do brakujących, a proces jest powtarzany aż do osiągnięcia węzłów końcowych. OTFI zachowuje integralność danych „poza torbą”, dlatego wartości wydajności, takie jak zmienne znaczenie (VIMP) pozostają bezstronne. Algorytm OTFI został opisany w Ishwaran i in. (2008) i zaimplementowany w wycofanym pakiecie randomSurvivalForest,

Metoda (2) jest implementowana za pomocą funkcji „impute” w randomForestSRC. Dostępne są nienadzorowane, randomizowane i wielowymiarowe metody podziału dla przypisywania danych. Na przykład podział wielowymiarowy uogólnia bardzo skuteczną metodę imputacji missForest ( Stekhoven i Bühlmann (2012), „MissForest - nieparametryczna imputacja wartości brakujących dla danych mieszanych”, Bioinformatics , 28 , 1 ). Wywołanie funkcji imputacji z brakującymi danymi zwróci imputowaną ramkę danych, którą można dopasować za pomocą podstawowej funkcji lasu „rfsrc”.

Szczegółowe porównanie różnych algorytmów brakujących danych w lesie zaimplementowanych przy użyciu „impute” zostało opisane w najnowszym artykule Fei Tanga „Algorytmy losowych brakujących danych w lesie”, 2017 . Polecam przejrzenie plików pomocy „rfsrc” i „impute” z randomForestSRC, aby uzyskać więcej informacji na temat imputacji i OTFI.

Hemant Ishwaran
źródło
3
Witamy na naszej stronie! Pamiętaj, że twoja nazwa użytkownika, identyfikator oraz link do strony użytkownika są automatycznie dodawane do każdego posta, więc nie musisz podpisywać swoich postów. W rzeczywistości wolimy, żebyś tego nie robił.
Silverfish,
1
Dzięki za ciekawą odpowiedź (+1). Pozwoliłem sobie na dodanie pełnych referencji i linków do kilku cytowanych artykułów, ale nie mogłem znaleźć Tanga i Ishwaran (2015), „Losowych algorytmów brakujących danych w lesie”. Czy zostało już opublikowane?
Scortchi - Przywróć Monikę
9

Partycjonowanie rekurencyjne wykorzystuje podziały zastępcze oparte na brakujących predyktorach, które są skorelowane z predyktorem posiadającym brakującą wartość dla obserwacji. Teoretycznie wydaje się możliwe wdrożenie losowych lasów, które wykorzystują ten sam pomysł. Nie wiem, czy zrobiło to jakieś przypadkowe oprogramowanie leśne.

Frank Harrell
źródło
7

Według Leo Breimana i Adele Cutler, która go wynalazła, Losowy Las ma dwie metody postępowania z brakującymi wartościami.

Pierwszy jest szybki i brudny: po prostu wypełnia wartość mediany dla zmiennych ciągłych lub najczęściej brakującą wartość według klasy .

Druga metoda wypełnia brakujące wartości, następnie uruchamia RF, a następnie dla brakujących wartości ciągłych RF oblicza średnią ważoną z bliskich brakujących wartości. Następnie proces ten powtarza się kilka razy. Następnie model jest trenowany po raz ostatni przy użyciu zestawu danych przypisanych do RF.

Przywróć Monikę
źródło
Dziękuję za Twoją odpowiedź! Ale obie te metody zastępują brakujące wartości. Ale w drzewach GBM lub regresyjnych brakujące wartości niczego nie zastępują. Jaka jest teoretyczna różnica między np. GBM a RF w tym sensie?
Fedorenko Kristina
Nie jestem ekspertem od GBM, ale obsługa RF brakujących wartości wydaje się być zakorzeniona w idei imputacji, en.wikipedia.org/wiki/Imputation_(statistics) W przypadkach, gdy brakujące wartości nie są losowo wybierane wyniki mogą być stronnicze z powodu braków. Imputacja próbuje odzyskać brakujące wartości i zmniejszyć błąd systematyczny.
Przywróć Monikę
2

Zamiast korzystać z wartości mediany itp., Zdecydowanie polecam przyjrzenie się pakietowi missRanger (obecnie w fazie rozwoju na Github) lub pakietowi missForest). Oba te pakiety wykorzystują losowe lasy, aby najpierw przypisać dane przy użyciu metody podobnej do wielokrotnej imputacji za pomocą równań łańcuchowych (MICE). Byłaby to właściwa metoda imputacji, ponieważ ściśle odpowiada twojemu rzeczywistemu modelowi analizy. Następnie możesz wykorzystać wszystkie swoje dane bez martwienia się o upuszczenie poszczególnych wierszy z powodu brakujących obserwacji. Ponadto przypisane wartości będą znacznie bardziej realistyczne niż zwykłe wybieranie median lub trybów.

Do analiz można użyć tylko jednego wypełnionego przypisanego zestawu danych, ale najlepszym sposobem na uwzględnienie niepewności w odniesieniu do brakujących wartości jest uruchomienie wielu serii tych metod imputacji, a następnie oszacowanie modelu na każdym z wynikowych zestawów danych (tj. Wielu imputacja), a następnie połącz oszacowania za pomocą reguł Rubina (patrz pakiet R mitools).

Robert Kubinec
źródło
0

W przypadku CART możesz zastosować metodę brakujących atrybutów (MIA). Oznacza to, że dla predyktorów jakościowych brakuje kodu jako oddzielnej kategorii. Dla predyktorów numerycznych tworzysz dwie nowe zmienne dla każdej zmiennej z brakami: jedną, w której kodujesz braki jako -Inf, a drugą, gdzie kodujesz braki jako + Inf. Następnie stosuje się do danych losową funkcję lasu.

Zalety MIA: 1) obliczeniowo taniej, 2) nie daje wielu zestawów danych, a tym samym modeli, podobnie jak wielokrotne imputacje (literatura imputacji brakujących danych ogólnie zgadza się, że jeden przypisany zestaw danych nie jest wystarczający), 3) nie wymaga wybrać metodę statystyczną i / lub model przypisywania danych.

Funkcje ctree()i cforest()z pakietu partykit pozwalają na zastosowanie MIA poprzez przekazanie ctree_control(MIA = TRUE)ich controlargumentów.

Wygląda na to, że program RuleFit Jerome'a ​​Friedmana wykorzystuje MIA do radzenia sobie z brakami, patrz https://statweb.stanford.edu/~jhf/r-rulefit/rulefit3/RuleFit_help.html#xmiss .

Opis podejścia MIA można znaleźć w Twala i in. (2008):

Twala, BETH, Jones, MC i Hand, DJ (2008). Dobre metody radzenia sobie z brakującymi danymi w drzewach decyzyjnych. Listy rozpoznające wzór, 29 (7), 950-956.

Marjolein Fokkema
źródło