Poprzednia

ⓘ Las losowy




                                     

ⓘ Las losowy

Las losowy lub losowy las decyzyjny jest metodą zespołową 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 lub przewidywaną średnią poszczególnych drzew. Losowe lasy decyzyjne poprawiają tendencję drzew decyzyjnych do nadmiernego dopasowywania się do zestawu treningowego s.587–588. Pierwszy algorytm losowych lasów decyzyjnych został stworzony przez Tina 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 Eugenea Kleinberga.

Rozszerzenie algorytmu zostało opracowane przez Leo Breimana i Adele Cutler, którzy zarejestrowali "Random Forests” jako znak towarowy. Rozszerzenie łączy pomysł "baggingu agregacji bootstrapa” Breimana i losowy wybór funkcji, wprowadzony po raz pierwszy przez Ho, a później niezależnie przez Amita i Gemana w celu skonstruowania zbioru drzew decyzyjnych o kontrolowanej wariancji.

                                     

1.1. Algorytm Eliminacje: uczenie się drzewa decyzyjnego

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 in., "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 ” s. 352.

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, tj. 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 wariancji s: 587–588. Odbywa się to kosztem niewielkiego wzrostu obciążenia i pewnej utraty interpretowalności, ale generalnie znacznie zwiększa wydajność w ostatecznym modelu.

                                     

1.2. Algorytm 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 X = x 1., x n z odpowiedziami Y = y 1., y n, wielokrotna agregacja razy B wybiera losową próbę z wymianą zestawu treningowego i dopasowuje do niej drzewa:

Dla b = 1., B:
  • Trenuj drzewo klasyfikacyjne lub regresyjne f b na X b, Y b.
  • Próba, z wymianą, n przykładów szkoleniowych z X, Y ; nazwijmy je X b, Y b.

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

f ^ = 1 B ∑ b = 1 B f b x ′ {\displaystyle {\hat {f}}={\frac {1}{B}}\sum _{b=1}^{B}f_{b}x}

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

Ta procedura prowadzi do lepszej wydajności modelu, ponieważ 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 x:

σ = ∑ b = 1 B f b x ′ − f ^) 2 B − 1. {\displaystyle \sigma ={\sqrt {\frac {\sum _{b=1}^{B}f_{b}x-{\hat {f}})^{2}}{B-1}}}.}

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

                                     

1.3. Algorytm Od agregacji bootstrapa po losowe lasy

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 B, 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 p cechami √ p zaokrąglone w dół cech jest użyte w każdym podziale s: 592. W przypadku problemów z regresją twórcy zalecają p/3 zaokrąglone w dół z minimalnym rozmiarem węzła 5 jako domyślnym s: 592. W praktyce najlepsze wartości dla tych parametrów będą zależeć od problemu i powinny być traktowane jako parametry strojenia: 592.



                                     

1.4. Algorytm 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 na podstawie np. 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 n {\displaystyle {\sqrt {n}}} do klasyfikacji i n {\displaystyle n} dla regresji, gdzie n {\displaystyle n} to liczba funkcji w modelu.

                                     

2.1. 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.

Pierwszy krok w mierzeniu zmiennego znaczenia w zbiorze danych D n = { X i, Y i } i = 1 n {\displaystyle {\mathcal {D}}_{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 {\displaystyle j} -tej cechy po treningu, wartości j {\displaystyle 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 {\displaystyle 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.

                                     

3. Lasy losowe w pracach naukowych

Algorytm jest często wykorzystywany w pracach naukowych ze względu na jego zalety. Na przykład można go wykorzystać do oceny jakości artykułów Wikipedii.

                                     

4. Implementacje open source

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