Las losowy

Las losowy, losowy las decyzyjny – metoda zespołowa uczenia maszynowego dla klasyfikacji, regresji i innych zadań, która polega na konstruowaniu wielu drzew decyzyjnych w czasie uczenia i generowaniu klasy, która jest dominantą klas (klasyfikacja) lub przewidywaną średnią (regresja) poszczególnych drzew. Losowe lasy decyzyjne poprawiają tendencję drzew decyzyjnych do nadmiernego dopasowywania się do zestawu treningowegoSzablon:Odn. Pierwszy algorytm losowych lasów decyzyjnych został stworzony przez Tin Kam Ho przy użyciu metody losowej podprzestrzeni, która w formule Ho jest sposobem na implementację podejścia „dyskryminacji stochastycznej” do klasyfikacji zaproponowanej przez Eugene’a Kleinberga.

Rozszerzenie algorytmu zostało opracowane przez Leo Breimana i Adele Cutler, którzy zarejestrowali „Random Forests” jako znak towarowy (stan na 2019, należący do Minitab, Inc.). Rozszerzenie łączy pomysł baggingu (agregacji bootstrapowej) Breimana i losowy wybór cech, wprowadzony po raz pierwszy przez Ho, a później niezależnie przez Amita i Gemana w celu skonstruowania zbioru drzew decyzyjnych o kontrolowanej wariancji.

Algorytm

Wstęp: metoda drzew decyzyjnych

Drzewa decyzyjne są popularną metodą dla różnych zadań uczenia maszynowego. Uczenie się drzew „przychodzi najbliżej spełnienia wymogów służących jako standardowa procedura eksploracji danych”, mówią Hastie i inni, „ponieważ jest niezmienne pod względem skalowania i różnych innych przekształceń wartości cech, jest odporne na włączenie nieistotnych cech i tworzy modele kontrolowane. Jednak rzadko są one dokładne”Szablon:Odn.

W szczególności drzewa, które są bardzo głębokie, mają tendencję do uczenia się wysoce nieregularnych wzorów: dopasowują się nadmiernie do zestawów treningowych, to znaczy mają niskie obciążenie, ale bardzo dużą wariancję. Losowe lasy są sposobem uśredniania wielu głębokich drzew decyzyjnych, wyszkolonych na różnych częściach tego samego zestawu treningowego, w celu zmniejszenia wariancjiSzablon:Odn. Odbywa się to kosztem niewielkiego wzrostu obciążenia i pewnej utraty interpretowalności, ale generalnie znacznie zwiększa wydajność w ostatecznym modelu.

Agregacja bootstrapa

Algorytm szkoleniowy dla lasów losowych stosuje ogólną technikę agregacji bootstrapa dla uczących się drzew. Biorąc pod uwagę zestaw treningowy Szablon:Mvar = Szablon:Mvar,..., Szablon:Mvar z odpowiedziami Szablon:Mvar = Szablon:Mvar,..., Szablon:Mvar, wielokrotna agregacja (razy B) wybiera losową próbę z wymianą zestawu treningowego i dopasowuje do niej drzewa:

Dla Szablon:Mvar = 1,..., Szablon:Mvar:

1. Próba, z wymianą, Szablon:Mvar przykładów szkoleniowych z Szablon:Mvar, Szablon:Mvar ; nazwijmy je Szablon:Mvar, Szablon:Mvar.
2. Trenuj drzewo klasyfikacyjne lub regresyjne Szablon:Mvar na Szablon:Mvar, Szablon:Mvar.

Po szkoleniu prognozy dla niewidocznych próbek Szablon:Mvar mogą być wykonane przez uśrednienie prognoz ze wszystkich poszczególnych drzew regresji na Szablon:Mvar:

$\hat{f}=\frac{1}{B}\sum _{b=1}^B{f}_b(x^{\prime })$

lub biorąc głos większości w przypadku drzew klasyfikacyjnych.

Ta procedura prowadzi do lepszej wydajności modelu, gdyż zmniejsza wariancję modelu bez zwiększania obciążenia. Oznacza to, że podczas gdy przewidywania pojedynczego drzewa są bardzo wrażliwe na szum w zestawie treningowym, średnia wielu drzew nie jest taka, tak długo, jak długo drzewa nie są skorelowane. Wyszkolenie wielu drzew na pojedynczym zbiorze treningowym dawałoby silnie skorelowane drzewa (lub nawet to samo drzewo wiele razy, jeśli algorytm treningowy jest deterministyczny); bootstrap jest sposobem na od-korelowanie drzew poprzez pokazanie im różnych zestawów treningowych.

Ponadto oszacowanie niepewności predykcji może być wykonane jako odchylenie standardowe przewidywań ze wszystkich poszczególnych drzew regresji na Szablon:Mvar:

$\sigma =\sqrt{\frac{\sum _{b=1}^B(f_b(x^{\prime })-\hat{f}{)}^2}{B-1}}.$

Liczba próbek / drzew, Szablon:Mvar, jest parametrem bezpłatnym. Zazwyczaj używa się od kilkuset do kilku tysięcy drzew, w zależności od wielkości i charakteru zestawu treningowego. Optymalną liczbę drzew Szablon:Mvar można znaleźć za pomocą walidacji krzyżowej: średni błąd predykcji na każdej próbce treningowej Szablon:Mvar, używając tylko drzew, które nie miały Szablon:Mvar w próbce bootstrap. Błąd treningowy i testowy mają tendencję do wyrównywania się po dopasowaniu pewnej liczby drzew.

Od agregacji bootstrapa po lasy losowe

Powyższa procedura opisuje oryginalny algorytm agregacji bootstrapa dla drzew. Losowe lasy różnią się tylko jednym sposobem od tego ogólnego schematu: używają zmodyfikowanego algorytmu uczenia się drzewa, który wybiera w każdym podziale kandydata w procesie uczenia się losowy podzbiór cech. Ten proces jest czasami nazywany „agregacją bootstrapa funkcji”. Powodem tego jest korelacja drzew w zwykłej próbce bootstrapu: jeśli jedna lub kilka cech jest bardzo silnymi predyktorami dla zmiennej odpowiedzi (wynik docelowy), funkcje te zostaną wybrane w wielu drzewach Szablon:Mvar, powodując ich skorelowanie. Analiza sposobu, w jaki bagging i losowa projekcja podprzestrzeni przyczyniają się do zwiększenia dokładności w różnych warunkach, jest podana przez Ho.

Zazwyczaj w problemie klasyfikacji, z Szablon:Mvar cechami √Szablon:Mvar (zaokrąglone w dół) cech jest użyte w każdym podzialeSzablon:Odn. W przypadku problemów z regresją twórcy zalecają Szablon:Mvar (zaokrąglone w dół) z minimalnym rozmiarem węzła 5 jako domyślnymSzablon:Odn. W praktyce najlepsze wartości dla tych parametrów będą zależeć od problemu i powinny być traktowane jako parametry strojeniaSzablon:Odn.

ExtraTrees

Dodanie jednego kolejnego kroku randomizacji daje wyjątkowo losowe drzewa lub ExtraTrees. Chociaż są podobne do zwykłych lasów losowych, ponieważ stanowią zbiór pojedynczych drzew, istnieją dwie główne różnice: po pierwsze, każde drzewo jest szkolone przy użyciu całej próbki uczenia się (a nie próbki początkowej), a po drugie, rozdzielanie odgórne uczącego się drzewa jest losowe. Zamiast obliczać lokalnie optymalny punkt odcięcia dla każdej rozważanej cechy (przykładowo na podstawie wzmocnienia informacji lub zanieczyszczenia Giniego), wybierany jest losowy punkt odcięcia. Ta wartość jest wybierana z jednolitego rozkładu w zakresie empirycznym elementu (w zestawie treningowym drzewa). Następnie, spośród wszystkich losowo wygenerowanych podziałów, podział, który daje najwyższy wynik, jest wybierany do podziału węzła. Podobnie jak w przypadku zwykłych lasów losowych, można określić liczbę losowo wybranych cech, które należy uwzględnić w każdym węźle. Domyślne wartości tego parametru to $\sqrt{n}$ do klasyfikacji i $n$ dla regresji, gdzie $n$ to liczba funkcji w modelu.

Właściwości

Znaczenie zmiennych

Losowe lasy można wykorzystać do rankingu znaczenia zmiennych w problemie regresji lub klasyfikacji w naturalny sposób. Poniższa technika została opisana w oryginalnym artykule Breimana i została zaimplementowana w R w pakiecie randomForest.

Pierwszym krokiem w mierzeniu zmiennego znaczenia w zbiorze danych ${𝒟}_n=\{(X_i,Y_i){\}}_{i=1}^n$ jest dopasowanie losowego lasu do danych. Podczas procesu dopasowania bagging dla każdego punktu danych jest rejestrowany i uśredniany w lesie (błędy w niezależnym zestawie testowym mogą zostać zastąpione, jeśli workowanie nie jest używane podczas treningu).

Aby zmierzyć znaczenie $j$ -tej cechy po treningu, wartości $j$ -tej cechy są permutowane wśród danych treningowych, a błąd tego baggingu jest ponownie obliczany na tym zaburzonym zbiorze danych. Wynik ważności dla $j$-tą cechę oblicza się uśredniając różnicę błędu braku baggingu przed i po permutacji na wszystkich drzewach. Wynik jest znormalizowany przez odchylenie standardowe tych różnic.

Cechy, które dają duże wartości dla tego wyniku, są klasyfikowane jako ważniejsze niż cechy, które generują małe wartości. Statystyczna definicja miary zmiennej ważności została podana i przeanalizowana przez Zhu i in.

Ta metoda określania znaczenia cech ma pewne wady. W przypadku danych, w tym zmiennych kategorycznych o różnej liczbie poziomów, losowe lasy sprzyjają tym atrybutom z większą liczbą poziomów. Metody takie jak częściowe permutacje i rosnące nieobciążone drzewa mogą być wykorzystane do rozwiązania problemu. Jeśli dane zawierają grupy skorelowanych cech o podobnym znaczeniu dla danych wyjściowych, mniejsze grupy są faworyzowane w stosunku do większych grup.

Lasy losowe w pracach naukowych

Algorytm jest często stosowany w pracach naukowych ze względu na jego zalety. Można go też użyć do oceny jakości artykułów Wikipedii.

Implementacje open source

• Oryginał RF Breimana i Cutlera napisany w Fortran 77.
• ALGLIB zawiera modyfikację losowego lasu w C #, C ++, Pascal, VBA.
• party Implementacja oparta na drzewach wnioskowania warunkowego w R.
• randomForest do klasyfikacji i regresji w R.
• Implementacja Pythona z przykładami w scikit-learn.
• Implementacja Matlab.
• Oprogramowanie SQP wykorzystuje losowy algorytm lasu do przewidywania jakości pytań ankietowych, w zależności od formalnych i językowych charakterystyk pytania.
• Weka RandomForest w bibliotece Java i GUI.
• ranger Implementacja losowego lasu C ++ do klasyfikacji, regresji, prawdopodobieństwa i przeżycia. Zawiera interfejs dla R.

Zobacz też

• algorytm losowy
• statystyka nieparametryczna

Bibliografia

• Szablon:Cytuj książkę