Klasyfikator Random Forest

Jedno drzewo, za dużo pamięci

Drzewo decyzyjne uczy się rekurencyjnie dzieląc przestrzeń cech: w każdym węźle wybiera cechę i próg, które najbardziej redukują zanieczyszczenie (impurity) w dwóch wynikowych grupach, zwykle mierzone za pomocą entropii lub współczynnika Giniego. Jeśli rosnąć wystarczająco głęboko, drzewo może wyryć granicę tak precyzyjną, że każdy przykład treningowy kończy się w swoim własnym liściu – idealna dokładność uczenia i model, który zasadniczo zapamiętał zbiór danych. To klasyczny tryb awarii drzewa decyzyjnego: niski błąd (bias), bardzo wysoka zmienność (variance). Zmiana zbioru treningowego nieznacznie może całkowicie zmienić strukturę głębokiego drzewa, co oznacza, że jego przewidywania na nowych danych drastycznie zależą od tego, które przykłady przypadkowo znajdowały się w próbce treningowej.

Bagging: redukcja szumów poprzez uśrednianie

Pomysł Leona Breimana z 1996 roku dotyczący bootstrap aggregatingu (bagging) jest zaskakująco prosty: losowo wyciągnij N wierszy z powtórzeniem z zbioru treningowego (próbka bootstrapowa), wytrenuj na nich pełne, nieprzerobione drzewo i powtórz to setki razy. Ponieważ każde drzewo widzi nieco inny fragment danych, jego indywidualne błędy są do pewnego niezależne od błędów innych drzew. Uśrednianie prognoz z wielu modeli o wysokiej wariancji, ale niskim błędem, eliminuje dużą część tej wariancji, prawie nie dotykając błędu, co jest tym, czego pojedyncze drzewo nie może zrobić samodzielnie. Breiman jeszcze bardziej uściślił to w swoim artykule z 2001 roku „Losowe Lasery”, dodając drugi składnik, który nadaje metodzie jej nazw.

Losowa selekcja cech: rozdzielanie drzew

Sam bagging ma słabość: jeśli jedno cecha jest naprawdę silnym predyktorem, prawie każde drzewo bootstrapowe wybierze je w pobliżu korzenia, co prowadzi do strukturalnie podobnych drzew i korelujących błędów – średnia ocenianie skorelowanych modeli usuwa znacznie mniej wariancji niż średnia niezależnych. Las losowy rozwiązuje to, ograniczając na każdym pojedynczym podziale kandydatów do cech do losowego podzbioru – zwykle pierwiastek z całkowitej liczby cech dla klasyfikacji lub jego trzeciej części dla regresji. To wymusza różne drzewa w różnych ścieżkach nawet przy szkoleniu na podobnych danych, dekorelując ensemble i pozwalając etapowi średnienia wykonać znacznie więcej pracy.

// growing a random forest of T trees over p features
for t in 1..T:
    sample_t = bootstrap_sample(training_data)     // N rows, drawn with replacement
    tree_t   = grow_tree(sample_t):
        at each node:
            candidates = random_subset_of_features(size = sqrt(p))
            split      = best_split(candidates)     // minimize Gini impurity
            recurse until max_depth or min_leaf_size
    forest.add(tree_t)

predict(x):
    votes = [tree.predict(x) for tree in forest]
    return majority_vote(votes)                     // average(votes) for regression

demo na żywo · powiązana symulacja● LIVE

Błąd poza torem (OOB): zestawy walidacyjne zbudowane wewnątrz

Próbkowanie N wierszy z powtórzeniem z N wierszy powoduje pominięcie, średnio około 1/e ≈ 36,8% oryginalnych wierszy dla danego próbkowania bootstrapowego — te wiersze po prostu nie zostały wybrane. Ponieważ każdy drzewo nigdy nie widziało swoich "zewnętrznych, poza-lasem" wierszy podczas treningu, przewidywanie ich tylko z podzbiorem drzew, które je wykluczały, daje uczciwą, niezobowiązaną ocenę błędu testowego, bez konieczności dzielenia oddzielnie zbioru walidacyjnego lub przeprowadzania krzyżowej walidacji. Ten błąd OOB jest jednym z najbardziej praktycznych udogodnień lasów losowych: pochodzi zasadniczo za darmo z procesu treningowego.

Co może powiedzieć las o Twoich cechach

Ponieważ każdy podział rejestruje, jaką cechę użył i jak bardzo zmniejsza on nieczystość, las może ocenić cechy według średniego spadku nieczystości – sumując redukcję nieczystości każdej cechy na każdym podziale w każdym drzewie. Bardziej odporną alternatywą jest ważność permutacji: losowo przemieszaj wartość jednej cechy na wierszach poza zakłado terem i zmierz, jak bardzo spada dokładność OOB. Cecha, na którą las naprawdę polega, pogorszy dokładność znacznie, gdy zostanie zdezorganizowana; cecha, której ignoruje, prawie nie wpłynie. Żaden z tych metod nie wymaga ponownego trenowania modelu od początku.

Dostrojenie pokręteł

Liczba drzew w zasadzie wymienia czas obliczeniowy na bardziej gładką i stabilną krzywą błędu OOB – jak w przypadku metod boostingowych, dodawanie do lasu losowego więcej drzew nie prowadzi do przetrenowania, jedynie uśrednia więcej niezależnych szumów. Zmienność każdej indywidualnej drzewa, a tym samym ilość pracy, jaką wykonuje krok uśredniający, jest kontrolowana oddzielnie przez głębokość maksymalną i minimalną liczbę próbek na liście: drzewa o mniejszej głębokości z większymi liśćmi są indywidualnie mniej dokładne, ale bardziej stabilne, co może przesunąć punkt optymalny dla zbioru danych w zależności od jego szumu.

Frequently asked questions

Dlaczego lasy losowe nie nadmiernie dopasowują się (overfit) do danych, gdy dodaje się więcej drzew?

Dodawanie większej liczby drzew nigdy nie zwiększa wariancji średniej zbioru, a każde kolejne drzewo jest niezależnie próbkowane za pomocą bootstrapa, więc krzywa błędu lasu wypłaszcza się zamiast stawać się wyżniejsza, jak w przypadku pojedynczego drzewa, które nadmiernie dopasowuje się do danych wraz ze zwiększającą się głębokością. Dodatkowe drzewa generują jedynie koszty związane z czasem obliczeń; w przeciwieństwie do boostingu, lasy losowe nie iteracyjnie dopasowują się do błędów poprzedniego modelu, więc nie ma mechanizmu, który pozwalałby dodatkowym drzewom zapamiętywać szum.

Jakie jest różnica między baggingiem a lasem losowym?

Bagging trenuje każde drzewo na bootstrapowej próbce wierszy, ale pozwala każdemu podziałowi uwzględniać wszystkie dostępne cechy. W rezultacie, jeśli jedna cecha jest silnym predyktorem, większość drzew bagginowych wybiera ją blisko korzenia i kończy się korelacja między nimi, co ogranicza ilość redukcji wariancji przez uśrednianie. Las losowy dodaje drugiego warstwa losowości: podczas każdego podziału rozważa się tylko losowy podzbiór cech, zmuszając drzewa do różnych ścieżek i dekorlując je, dzięki czemu średnia wielu drzew redukuje wariancję jeszcze bardziej niż bagging.

Jak błąd OOB różni się od walidacji krzyżowej?

Obie metody szacują błąd poza próbą bez użycia oddzielnego zbioru testowego, ale walidacja krzyżowa k-fold retrenuje cały model k razy na różnych podzbiorach, podczas gdy błąd OOB jest darmowy i pochodzi z pojedynczego przebiegu treningowego: każdy wiersz oceniany jest tylko przez około jedną trzecią drzew, które nigdy nie widziały go w swojej próbce bootstrapowej, więc nie są potrzebne dodatkowe przebiegy treningowe.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację the simulation

Lasy Losowe: Mądrość Niezrównoważonej Grupy Drzew