Losowy las - Random forest

Część serii na
Uczenie maszynowe i eksploracja danych
Problemy Klasyfikacja Grupowanie Regresja Wykrywanie anomalii Czyszczenie danych AutoML Zasady stowarzyszenia Nauka wzmacniania Prognoza strukturalna Inżynieria funkcji Nauka funkcji Nauka online Nauka częściowo nadzorowana Nauka nienadzorowana Nauka rangi Indukcja gramatyczna
Uczenie nadzorowane ( klasyfikacja  • regresja ) Drzewa decyzyjne Zespoły Parcianka Wzmacnianie Losowy las k -NN Regresja liniowa Naiwny Bayes Sztuczne sieci neuronowe Regresja logistyczna Perceptron Maszyna wektorów trafności (RVM) Maszyna wektorów pomocniczych (SVM)
Grupowanie BRZOZOWY LECZYĆ Hierarchiczny k -oznacza Oczekiwanie – maksymalizacja (EM) DBSCAN OPTYKA Średnia zmiana
Redukcja wymiarowości Analiza czynników CCA ICA LDA NMF PCA PGD t-SNE
Prognoza strukturalna Modele graficzne Sieć Bayesa Warunkowe pole losowe Ukryty Markow
Wykrywanie anomalii k -NN Lokalny czynnik odstający
Sztuczna sieć neuronowa Autokoder Obliczenia kognitywne Głęboka nauka DeepDream Perceptron wielowarstwowy RNN LSTM GRU ESN Ograniczona maszyna Boltzmanna GAN SOM Konwolucyjna sieć neuronowa U-Net Transformator Wzrastająca sieć neuronowa Memtranzystor Elektrochemiczna pamięć RAM (ECRAM)
Nauka wzmacniania Q-learning SARSA Różnica czasowa (TD)
Teoria Kompromis między odchyleniami a wariancją Teoria uczenia się komputerowego Minimalizacja ryzyka empirycznego Nauka Occam Nauka PAC Nauka statystyczna Teoria VC
Miejsca uczenia maszynowego NeuroIPS ICML ML JMLR ArXiv:cs.LG
Powiązane artykuły Słowniczek sztucznej inteligencji Lista zbiorów danych do badań nad uczeniem maszynowym Zarys uczenia maszynowego
v T mi

Losowe lasy lub losowe lasy decyzyjne to zespołowa metoda uczenia się klasyfikacji , regresji i innych zadań, która działa poprzez konstruowanie wielu drzew decyzyjnych w czasie szkolenia. W przypadku zadań klasyfikacyjnych wynikiem losowego lasu jest klasa wybrana przez większość drzew. W przypadku zadań regresji zwracana jest średnia lub średnia predykcji poszczególnych drzew. Losowe lasy decyzyjne korygują nawyk drzew decyzyjnych do nadmiernego dopasowania do zestawu treningowego . Lasy losowe generalnie przewyższają drzewa decyzyjne , ale ich dokładność jest niższa niż w przypadku drzew ze wzmocnieniem gradientowym. Jednak cechy danych mogą wpływać na ich wydajność.

Pierwszy algorytm losowych lasów decyzyjnych został stworzony w 1995 roku przez Tin Kam Ho przy użyciu metody podprzestrzeni losowej , która w ujęciu Ho jest sposobem implementacji podejścia „dyskryminacji stochastycznej” do klasyfikacji zaproponowanej przez Eugene'a Kleinberga.

Rozszerzenie algorytmu zostało opracowane przez Leo Breimana i Adele Cutler , którzy w 2006 roku zarejestrowali „Random Forests” jako znak towarowy (od 2019 roku należący do firmy Minitab, Inc. ). Rozszerzenie łączy w sobie ideę „ baggingu” Breimana i losowy dobór funkcji, wprowadzony najpierw przez Ho, a później niezależnie przez Amita i Gemana w celu skonstruowania kolekcji drzew decyzyjnych o kontrolowanej wariancji.

Lasy losowe są często używane jako modele „czarnej skrzynki” w firmach, ponieważ generują rozsądne prognozy dla szerokiego zakresu danych, wymagając niewielkiej konfiguracji.

Historia

Ogólna metoda losowych lasów decyzyjnych została po raz pierwszy zaproponowana przez Ho w 1995 roku. Ho ustalił, że lasy drzew rozszczepionych ukośnymi hiperpłaszczyznami mogą zyskać dokładność w miarę wzrostu bez cierpienia z powodu przetrenowania, o ile lasy są losowo ograniczone do wrażliwości tylko na wybrane wymiary funkcji . Kolejna praca w tym samym kierunku wykazała, że ​​inne metody podziału zachowują się podobnie, o ile są losowo zmuszane do niewrażliwości na niektóre wymiary cech. Zauważ, że ta obserwacja bardziej złożonego klasyfikatora (większego lasu) staje się bardziej dokładna niemal monotonicznie, stoi w ostrym kontraście z powszechnym przekonaniem, że złożoność klasyfikatora może wzrosnąć tylko do pewnego poziomu dokładności, zanim zostanie zraniona przez nadmierne dopasowanie. Wyjaśnienie odporności metody leśnej na przetrenowanie można znaleźć w teorii dyskryminacji stochastycznej Kleinberga.

Na wczesny rozwój koncepcji lasów losowych Breimana wpłynęła praca Amita i Gemana, którzy wprowadzili ideę przeszukiwania losowego podzbioru dostępnych decyzji podczas dzielenia węzła w kontekście uprawy pojedynczego drzewa . Idea losowego wyboru podprzestrzeni z Ho miała również wpływ na projektowanie losowych lasów. W tej metodzie rośnie las drzew, a zmienność między drzewami jest wprowadzana przez rzutowanie danych uczących na losowo wybraną podprzestrzeń przed dopasowaniem każdego drzewa lub każdego węzła. Wreszcie, pomysł optymalizacji z randomizacją węzłów, w której decyzja w każdym węźle jest wybierana przez procedurę randomizowaną, a nie optymalizację deterministyczną, został po raz pierwszy wprowadzony przez Diettericha.

Prawidłowego wprowadzenia lasów losowych dokonał w artykule Leo Breiman . W artykule opisano metodę budowania lasu nieskorelowanych drzew przy użyciu procedury typu CART , połączonej z randomizowaną optymalizacją węzłów i baggingiem . Ponadto niniejsza praca łączy w sobie kilka składników, niektóre wcześniej znane, a niektóre nowatorskie, które stanowią podstawę współczesnej praktyki lasów losowych, w szczególności:

1. Używanie błędu braku opakowania jako oszacowania błędu uogólnienia .
2. Mierzenie zmiennego znaczenia poprzez permutacje.

Raport oferuje również pierwszy wynik teoretyczny dla lasów losowych w postaci powiązania błędu uogólnienia, który zależy od siły drzew w lesie i ich korelacji .

Algorytm

Wstępy: nauka drzewa decyzyjnego

Drzewa decyzyjne to popularna metoda wykonywania różnych zadań uczenia maszynowego. Nauka drzewa „jest najbliżej spełnienia wymagań, aby służyć jako standardowa procedura eksploracji danych”, mówią Hastie i in. , „ponieważ jest niezmienna przy skalowaniu i różnych innych przekształceniach wartości cech, jest odporna na włączanie nieistotnych cech i tworzy możliwe do sprawdzenia modele. Jednak rzadko są one dokładne”.

W szczególności drzewa, które są uprawiane bardzo głęboko, mają tendencję do uczenia się wysoce nieregularnych wzorców: przesadzają ze swoimi zestawami treningowymi, tj. mają niską stronniczość, ale bardzo wysoką wariancję . Lasy losowe to sposób uśredniania wielu głębokich drzew decyzyjnych, wytrenowanych na różnych częściach tego samego zestawu szkoleniowego, w celu zmniejszenia wariancji. Dzieje się to kosztem niewielkiego wzrostu błędu systematycznego i pewnej utraty możliwości interpretacji, ale generalnie znacznie poprawia wydajność końcowego modelu.

Lasy są jak połączenie wysiłków algorytmu drzewa decyzyjnego. Praca zespołowa wielu drzew poprawia wydajność pojedynczego drzewa losowego. Choć nie do końca podobne, lasy dają efekty walidacji krzyżowej K-krotnej.

Parcianka

Algorytm uczący dla losowych lasów stosuje ogólną technikę agregacji bootstrap lub baggingu do uczących się drzew. Biorąc pod uwagę zestaw szkoleniowy X = x ₁ , ..., x _n z odpowiedziami Y = Y ₁ , ..., Y _n wielokrotnie pakowania ( B razy) wybiera losowo próbki zastępując zbioru treningowego i pasuje do tych drzew próbki:

Dla b = 1, ..., B :

1. Próbka, z zastąpieniem, n przykładów uczących z X , Y ; nazwijmy je X _b , Y _b .
2. Wytrenuj drzewo klasyfikacji lub regresji f _b na X _b , Y _b .

Po treningu, prognozy dla niewidzianych próbek x' można wykonać uśredniając prognozy ze wszystkich indywidualnych drzew regresji na x' :

${\ Displaystyle {\ kapelusz {f}} = {\ Frac {1} {B}} \ suma _ {b = 1} ^ {B} f_ {b} (x')}$

lub poprzez oddanie większości głosów w przypadku drzew klasyfikacyjnych.

Ta procedura ładowania początkowego prowadzi do lepszej wydajności modelu, ponieważ zmniejsza wariancję modelu bez zwiększania błędu systematycznego. Oznacza to, że podczas gdy predykcje pojedynczego drzewa są bardzo wrażliwe na hałas w jego zbiorze treningowym, średnia wielu drzew nie jest taka, o ile drzewa nie są skorelowane. Proste uczenie wielu drzew na jednym zbiorze uczącym dałoby silnie skorelowane drzewa (lub nawet to samo drzewo wiele razy, jeśli algorytm uczący jest deterministyczny); Próbkowanie bootstrap to sposób na dekorowanie drzew poprzez pokazywanie im różnych zestawów treningowych.

Dodatkowo oszacowanie niepewności predykcji można wykonać jako odchylenie standardowe predykcji ze wszystkich poszczególnych drzew regresji na x' :

${\ Displaystyle \ sigma = {\ sqrt {\ Frac {\ suma _ {b = 1} ^ {B} (f_ {b} (x ') - {\ kapelusz {f}}) ^ {2}} {B -1}}}.}$

Liczba próbek/drzew, B , jest parametrem swobodnym. Zazwyczaj używa się od kilkuset do kilku tysięcy drzew, w zależności od wielkości i charakteru zbioru treningowego. Optymalną liczbę drzew B można znaleźć za pomocą walidacji krzyżowej lub obserwując błąd out-of-bag : średni błąd predykcji na każdej próbie treningowej x _i , używając tylko drzew, które nie miały x _i w swojej próbie bootstrap . Błąd treningu i testu ma tendencję do wyrównywania się po dopasowaniu pewnej liczby drzew.

Od workowania po losowe lasy

Powyższa procedura opisuje oryginalny algorytm workowania drzew. Lasy losowe obejmują również inny rodzaj schematu pakowania: wykorzystują zmodyfikowany algorytm uczenia drzewa, który wybiera losowy podzbiór cech przy każdym podziale kandydatów w procesie uczenia . Proces ten jest czasami nazywany „bagażowaniem cech”. Powodem tego jest korelacja drzew w zwykłej próbie bootstrap: jeśli jedna lub kilka cech jest bardzo silnymi predyktorami zmiennej odpowiedzi (wyjście docelowe), cechy te zostaną wybrane w wielu drzewach B , powodując je skorelowane. Analizę wpływu workowania i losowej projekcji podprzestrzennej na wzrost dokładności w różnych warunkach podaje Ho.

Zazwyczaj w przypadku problemu klasyfikacji z cechami p , w każdym podziale używane są cechy √ p (zaokrąglone w dół). W przypadku problemów z regresją wynalazcy zalecają p/3 (zaokrąglone w dół) z minimalną wielkością węzła wynoszącą 5 jako wartość domyślną. W praktyce najlepsze wartości tych parametrów będą zależeć od problemu i należy je traktować jako parametry strojenia.

DodatkoweDrzewa

Dodanie kolejnego kroku randomizacji daje niezwykle randomizowane drzewa , czyli ExtraTrees. Chociaż podobne do zwykłych lasów losowych, ponieważ są zbiorem pojedynczych drzew, istnieją dwie główne różnice: po pierwsze, każde drzewo jest trenowane przy użyciu całej próbki uczącej (zamiast próbki początkowej), a po drugie, dzielenie odgórne w uczący się na drzewie jest losowany. 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. Wartość ta jest wybierana z rozkładu równomiernego w zakresie empirycznym cechy (w zbiorze uczącym drzewa). Następnie ze wszystkich losowo wygenerowanych podziałów do podziału węzła wybierany jest podział, który daje najwyższy wynik. 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 dotyczą klasyfikacji i regresji, gdzie jest liczbą elementów w modelu. ${\displaystyle {\sqrt {p}}}$${\displaystyle p}$${\displaystyle p}$

Nieruchomości

Zmienna ważność

Lasy losowe można wykorzystać do oceny ważności zmiennych w problemie regresji lub klasyfikacji w naturalny sposób. Poniższa technika została opisana w oryginalnym artykule Breimana i jest zaimplementowana w pakiecie R randomForest .

Pierwszym krokiem w mierzeniu ważności zmiennej w zbiorze danych jest dopasowanie losowego lasu do danych. Podczas procesu dopasowywania błąd braku worka 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 podczas treningu nie jest używane pakowanie). ${\ Displaystyle {\ mathcal {D}} _ {n} = \ {(X_ {i}, Y_ {i}) \} _ {i = 1} ^ {n}}$

Aby zmierzyć ważność -tej cechy po uczeniu, wartości -tej cechy są permutowane wśród danych uczących i ponownie obliczany jest błąd braku torby na tym zaburzonym zestawie danych. Wynik ważności dla -tej cechy jest obliczany przez uśrednienie różnicy błędu braku torby przed i po permutacji dla wszystkich drzew. Wynik jest znormalizowany przez odchylenie standardowe tych różnic. ${\ Displaystyle j}$${\ Displaystyle j}$${\ Displaystyle j}$

Cechy, które dają duże wartości tego wyniku, są klasyfikowane jako ważniejsze niż cechy, które dają małe wartości. Statystyczną definicję miary ważności zmiennej podali i przeanalizowali Zhu i in.

Ten sposób określania ważności zmiennej ma pewne wady. W przypadku danych zawierających zmienne kategorialne o różnej liczbie poziomów losowe lasy są stronnicze na korzyść tych atrybutów o większej liczbie poziomów. Do rozwiązania problemu można zastosować takie metody, jak częściowe permutacje i hodowanie bezstronnych drzew. Jeśli dane zawierają grupy skorelowanych cech o podobnym znaczeniu dla wyników, mniejsze grupy są uprzywilejowane w stosunku do większych grup.

Relacje z najbliższymi sąsiadami

Związek między losowymi lasami a algorytmem k -najbliższego sąsiada ( k -NN) został wskazany przez Lin i Jeona w 2002 roku. Okazuje się, że oba mogą być postrzegane jako tzw. ważone schematy sąsiedztwa . Są to modele zbudowane ze zbioru uczącego, które przewidują nowe punkty x' , patrząc na „sąsiedztwo” punktu, sformalizowane przez funkcję wagi W : ${\ Displaystyle \ {(x_ {i}, y_ {i}) \} _ {i = 1} ^ {n}}$${\displaystyle {\kapelusz {y}}}$

${\ Displaystyle {\ kapelusz {y}} = \ suma _ {i = 1} ^ {n} W (x_ {i}, x ') \ y_ {i}.}$

Oto nieujemna waga i 'tego punktu treningowego względem nowego punktu x' w tym samym drzewie. Dla dowolnego konkretnego x' wagi punktów muszą sumować się do jednego. Funkcje wagowe podano w następujący sposób: ${\ Displaystyle W (x_ {i}, x')}$${\displaystyle x_{i}}$

• W k -NN wagami są, jeśli x _i jest jednym z k punktów najbliższych x' , a zero w przeciwnym razie.${\ Displaystyle W (x_ {i}, x ') = {\ Frac {1} {k}}}$
• W drzewie, jeśli x _i jest jednym z k' punktów w tym samym liściu co x' , a zero w przeciwnym wypadku.${\ Displaystyle W (x_ {i}, x ') = {\ Frac {1} {k'}}}$

Ponieważ las uśrednia przewidywania zbioru m drzew z indywidualnymi funkcjami wag , jego przewidywania są ${\ Displaystyle W_ {j}}$

${\ Displaystyle {\ kapelusz {y}} = {\ Frac {1} {m}} \ suma _ {j = 1} ^ {m} \ suma _ {i = 1} ^ {n} W_ {j} ( x_{i},x')\,y_{i}=\sum _{i=1}^{n}\left({\frac {1}{m}}\sum _{j=1}^{ m}W_{j}(x_{i},x')\right)\,y_{i}.}$

To pokazuje, że cały las jest znowu ważonym schematem sąsiedztwa, z wagami, które są średnią wagą poszczególnych drzew. W tej interpretacji sąsiadami x' są punkty dzielące ten sam liść w dowolnym drzewie . W ten sposób sąsiedztwo x' zależy w złożony sposób od struktury drzew, a więc od struktury zbioru uczącego. Lin i Jeon pokazują, że kształt sąsiedztwa wykorzystywanego przez losowy las dostosowuje się do lokalnego znaczenia każdej cechy. ${\displaystyle x_{i}}$${\ Displaystyle j}$

Nauka nienadzorowana z losowymi lasami

W ramach ich konstrukcji losowe predyktory lasu w naturalny sposób prowadzą do miary rozbieżności między obserwacjami. Można również zdefiniować miary niepodobieństwa losowego lasu między danymi nieoznakowanymi: chodzi o skonstruowanie losowego predyktora lasu, który odróżnia „zaobserwowane” dane od odpowiednio wygenerowanych danych syntetycznych. Obserwowane dane są oryginalnymi danymi nieoznakowanymi, a dane syntetyczne pochodzą z rozkładu referencyjnego. Losowa odmienność lasu może być atrakcyjna, ponieważ bardzo dobrze radzi sobie z mieszanymi typami zmiennych, jest niezmienna w przypadku monotonicznych przekształceń zmiennych wejściowych i jest odporna na obserwacje odległe. Losowa odmienność lasów z łatwością radzi sobie z dużą liczbą zmiennych półciągłych ze względu na swój wewnętrzny dobór zmiennych; na przykład losowa odmienność lasu „Addcl 1” waży udział każdej zmiennej w zależności od stopnia jej zależności od innych zmiennych. Losowa odmienność lasów jest wykorzystywana w różnych zastosowaniach, np. do znajdowania skupisk pacjentów na podstawie danych z markerów tkankowych.

Warianty

Zamiast drzew decyzyjnych zaproponowano i oceniono modele liniowe jako podstawowe estymatory w lasach losowych, w szczególności wielomianową regresję logistyczną i naiwne klasyfikatory Bayesa . W przypadkach, gdy relacja między predyktorami a zmienną docelową jest liniowa, podstawowi uczący się mogą mieć równie wysoką dokładność jak uczący się zespołowo.

Losowy las jądra

W uczeniu maszynowym losowe lasy jądra ustanawiają połączenie między losowymi lasami a metodami jądra . Nieznacznie modyfikując ich definicję, losowe lasy można przepisać jako metody jądra , które są bardziej zrozumiałe i łatwiejsze do analizy.

Historia

Leo Breiman był pierwszą osobą, która zauważyła związek między losowymi metodami lasu i jądra . Zwrócił uwagę, że losowe lasy, które są hodowane przy użyciu iid losowych wektorów w konstrukcji drzewa, są równoważne z jądrem działającym na prawdziwym marginesie. Lin i Jeon ustalili połączenie między losowymi lasami a adaptacyjnym najbliższym sąsiadem, co oznacza, że ​​losowe lasy mogą być postrzegane jako adaptacyjne szacunki jądra. Davies i Ghahramani zaproponowali Random Forest Kernel i pokazali, że może empirycznie przewyższać najnowocześniejsze metody jądra. Scornet najpierw zdefiniował szacunki KeRF i podał wyraźny związek między szacunkami KeRF a losowym lasem. Podał także wyraźne wyrażenia dla jądra oparte na wyśrodkowanym losowym lesie i jednolitym losowym lesie, dwóch uproszczonych modelach lasu losowego. Nazwał te dwa KeRF Centered KeRF i Uniform KeRF i udowodnił górne granice ich współczynników spójności.

Notacje i definicje

Eliminacje: Lasy centralne

Las wyśrodkowany to uproszczony model oryginalnego lasu losowego Breimana, który jednolicie wybiera atrybut spośród wszystkich atrybutów i dokonuje podziałów w środku komórki wzdłuż wcześniej wybranego atrybutu. Algorytm zatrzymuje się po zbudowaniu w pełni binarnego drzewa poziomów , gdzie jest parametrem algorytmu. ${\displaystyle k}$${\ Displaystyle k \ w \ mathbb {N}}$

Jednolity las

Jednolity las to kolejny uproszczony model oryginalnego losowego lasu Breimana, który jednolicie wybiera cechę spośród wszystkich cech i dokonuje podziałów w punkcie równomiernie narysowanym z boku komórki, wzdłuż wstępnie wybranej cechy.

Od losowego lasu do KeRF

Biorąc próbkę szkolenia z -valued niezależnych zmiennych losowych rozproszonych jako niezależnego parę prototypowych , gdzie . Dążymy do przewidzenia odpowiedzi związanej ze zmienną losową poprzez oszacowanie funkcji regresji . Las regresji losowej to zespół losowych drzew regresji. Oznacz wartość przewidywaną w punkcie przez -te drzewo, gdzie są niezależne zmienne losowe, rozłożone jako ogólna zmienna losowa , niezależnie od próbki . Ta zmienna losowa może być wykorzystana do opisania losowości wywołanej podziałem węzłów i procedury próbkowania dla konstrukcji drzewa. Drzewa są łączone w celu utworzenia skończonego oszacowania lasu . W przypadku drzew regresji mamy , gdzie jest komórką zawierającą , zaprojektowaną z losowością i zbiorem danych oraz . ${\ Displaystyle {\ mathcal {D}} _ {n} = \ {(\ mathbf {X} _ {i}, Y_ {i}) \} _ {i = 1} ^ {n}}$${\ Displaystyle [0,1] ^ {p} \ razy \ mathbb {R}}$${\ Displaystyle (\ mathbf {X}, Y)}$${\ Displaystyle \ operatorname {E} [Y ^ {2}] <\ infty}$${\ Displaystyle Y}$${\ Displaystyle \ mathbf {X} }$${\ Displaystyle m (\ mathbf {x} ) = \ operatorname {E} [Y \ mid \ mathbf {X} = \ mathbf {x}]}$${\ Displaystyle M}$${\ Displaystyle m_ {n} (\ mathbf {x} , \ mathbf {\ Theta} _ {j})}$${\displaystyle \mathbf {x}}$${\ Displaystyle j}$${\ Displaystyle \ mathbf {\ Theta} _ {1} \ ldots \ mathbf {\ Theta} _ {M}}$${\displaystyle \mathbf {\theta}}$${\ Displaystyle {\ Mathcal {D}} _ {n}}$${\ Displaystyle m_ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ {M}) = {\ Frac {1} {M}} \ suma _ {j = 1}^{M}m_{n}(\mathbf {x} ,\Theta _{j})}$${\ Displaystyle m_ {n} = \ suma _ {i = 1} ^ {n} {\ Frac {Y_ {i} \ mathbf {1} _ {\ mathbf {X} _ {i} \ w A_ {n} (\mathbf {x} ,\Theta _{j})}}{N_{n}(\mathbf {x} ,\Theta _{j})}}}$${\ Displaystyle A_ {n} (\ mathbf {x}, \ Theta _ {j})}$${\displaystyle \mathbf {x}}$${\ Displaystyle \ Theta _ {j}}$${\ Displaystyle {\ Mathcal {D}} _ {n}}$${\ Displaystyle N_ {n} (\ mathbf {x}, \ Theta _ {j}) = \ suma _ {i = 1} ^ {n} \ mathbf {1} _ {\ mathbf {X} _ {i} \w A_{n}(\mathbf {x} ,\Theta _{j})}}$

W ten sposób losowe oszacowania lasu spełniają dla wszystkich , . Las regresji losowej ma dwa poziomy uśredniania, najpierw dla próbek w docelowej komórce drzewa, a następnie dla wszystkich drzew. W związku z tym wkład obserwacji znajdujących się w komórkach o dużej gęstości punktów danych jest mniejszy niż w przypadku obserwacji należących do mniej zaludnionych komórek. Aby ulepszyć metody losowego lasu i skompensować błędne oszacowanie, Scornet zdefiniował KeRF przez ${\ Displaystyle \ mathbf {x} \ w [0,1] ^ {d}}$${\ Displaystyle m_ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ {M}) = {\ Frac {1} {M}} \ suma _ {j = 1}^{M}\left(\sum _{i=1}^{n}{\frac {Y_{i}\mathbf {1} _{\mathbf {X} _{i}\in A_{n }(\mathbf {x} ,\Theta _{j})}}{N_{n}(\mathbf {x} ,\Theta _{j})}}\right)}$

${\ Displaystyle {\ tylda {m}} _ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ {M}) = {\ Frac {1} {\ suma _{j=1}^{M}N_{n}(\mathbf {x} ,\Theta _{j})}}\sum _{j=1}^{M}\sum _{i=1} ^{n}Y_{i}\mathbf {1} _{\mathbf {X} _{i}\in A_{n}(\mathbf {x} ,\Theta _{j})},}$

która jest równa średniej z opadania komórek znajdujących się w lesie. Jeśli zdefiniujemy funkcję połączenia skończonego lasu jako , tj. proporcję komórek dzielonych między i , to prawie na pewno mamy , który definiuje KeRF. ${\ Displaystyle Y_ {i}}$${\displaystyle \mathbf {x}}$${\ Displaystyle M}$${\ Displaystyle K_ {M, n} (\ mathbf {x}, \ mathbf {z}) = {\ Frac {1} {M}} \ suma _ {j = 1} ^ {M} \ mathbf {1} _{\mathbf {z} \in A_{n}(\mathbf {x} ,\Theta _{j})}}$${\displaystyle \mathbf {x}}$${\displaystyle \mathbf {z}}$${\ Displaystyle {\ tylda {m}} _ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ {M}) = {\ Frac {\ suma _ {i =1}^{n}Y_{i}K_{M,n}(\mathbf {x} ,\mathbf {x} _{i})}{\sum _{\ell =1}^{n}K_ {M,n}(\mathbf {x} ,\mathbf {x} _{\ell })}}}$

Wyśrodkowany KeRF

Konstrukcja Centered KeRF poziomu jest taka sama jak dla wyśrodkowanego lasu, z wyjątkiem tego, że przewidywania są dokonywane przez odpowiednią funkcję jądra lub funkcję połączenia ${\displaystyle k}$${\ Displaystyle {\ tylda {m}} _ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ {M})}$

${\ Displaystyle {\ zacząć {wyrównany} K_ {k} ^ {cc} (\ mathbf {x}, \ mathbf {z}) = \ suma _ {k_ {1}, \ ldots, k_ {d}, \ suma _{j=1}^{d}k_{j}=k}&{\frac {k!}{k_{1}!\cdots k_{d}!}}\left({\frac {1}{ d}}\right)^{k}\prod _{j=1}^{d}\mathbf {1} _{\lceil 2^{k_{j}}x_{j}\rceil =\lceil 2^ {k_{j}}z_{j}\rceil },\\&{\text{ dla wszystkich }}\mathbf {x} ,\mathbf {z} \in [0,1]^{d}.\end {wyrównany}}}$

Jednolity KeRF

Uniform KeRF jest budowany w taki sam sposób jak uniform forest, z tą różnicą, że prognozy są dokonywane przez , odpowiednią funkcję jądra lub funkcję połączenia ${\ Displaystyle {\ tylda {m}} _ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ {M})}$

${\ Displaystyle K_ {k} ^ {uf} (\ mathbf {0}, \ mathbf {x}) = \ suma _ {k_ {1}, \ ldots, k_ {d}, \ suma _ {j = 1} ^{d}k_{j}=k}{\frac {k!}{k_{1}!\ldots k_{d}!}}\left({\frac {1}{d}}\right)^ {k}\prod _{m=1}^{d}\left(1-|x_{m}|\sum _{j=0}^{k_{m}-1}{\frac {(-\ ln |x_{m}|)^{j}}{j!}}\right){\text{ dla wszystkich }}\mathbf {x} \in [0,1]^{d}.}$

Nieruchomości

Relacja między KeRF a losowym lasem

Prognozy podane przez KeRF i losowe lasy są bliskie, jeśli kontrolowana jest liczba punktów w każdej komórce:

Załóżmy, że istnieją takie sekwencje , że prawie na pewno ${\ Displaystyle (a_ {n}), (b_ {n})}$

${\ Displaystyle a_ {n} \ leq N_ {n} (\ mathbf {x}, \ Theta) \ leq b_ {n} {\ tekst {i}} a_ {n} \ leq {\ Frac {1} {M }}\sum _{m=1}^{M}N_{n}{\mathbf {x} ,\Theta _{m}}\leq b_{n}.}$

Wtedy prawie na pewno

${\ Displaystyle | m_ {M, n} (\ mathbf {x}) - {\ tylda {m}} _ {M, n} (\ mathbf {x}) | \ leq {\ Frac {b_ {n} - a_{n}}{a_{n}}}{\tylda {m}}_{M,n}(\mathbf {x} ).}$

Związek między nieskończonym KeRF a nieskończonym losowym lasem

Kiedy liczba drzew zbliża się do nieskończoności, mamy nieskończony losowy las i nieskończony KeRF. Ich szacunki są zbliżone, jeśli liczba obserwacji w każdej komórce jest ograniczona: ${\ Displaystyle M}$

Załóżmy, że istnieją takie sekwencje , że prawie na pewno ${\ Displaystyle (\ varepsilon _ {n}), (a_ {n}), (b_ {n})}$

• ${\ Displaystyle \ operatorname {E} [N_ {n} (\ mathbf {x}, \ Theta)] \ geq 1,}$
• ${\ Displaystyle \ operatorname {P} [a_ {n} \ leq N_ {n} (\ mathbf {x}, \ Theta) \ leq b_ {n} \ mid {\ mathcal {D}} _ {n}] \ geq 1-\varepsilon _{n}/2,}$
• ${\ Displaystyle \ operatorname {P} [a_ {n} \ leq \ operatorname {E} _ {\ Theta} [N_ {n} (\ mathbf {x}, \ Theta)] \ leq b_ {n} \ mid { \mathcal {D}}_{n}]\geq 1-\varepsilon _{n}/2,}$

Wtedy prawie na pewno

${\ Displaystyle | m_ {\ infty, n} (\ mathbf {x}) - {\ tylda {m}} _ {\ infty, n} (\ mathbf {x}) | \ leq {\ Frac {b_ {n }-a_{n}}{a_{n}}}{\tilde {m}}_{\infty ,n}(\mathbf {x} )+n\varepsilon _{n}\left(\max _{ 1\leq i\leq n}Y_{i}\right).}$

Spójność wyników

Załóżmy, że , gdzie jest wyśrodkowanym szumem Gaussa, niezależnym od , ze skończoną wariancją . Ponadto jest równomiernie rozmieszczony na i jest Lipschitz . Scornet udowodnił górne granice współczynników spójności dla wyśrodkowanego KeRF i jednorodnego KeRF. ${\ Displaystyle Y = m (\ mathbf {X} ) + \ varepsilon }$${\displaystyle \varepsilon}$${\ Displaystyle \ mathbf {X} }$${\displaystyle \sigma ^{2}<\infty}$${\ Displaystyle \ mathbf {X} }$${\ Displaystyle [0,1] ^ {d}}$${\ Displaystyle m}$

Spójność wyśrodkowanego KeRF

Zapewniając i , istnieje stała taka, że ​​dla wszystkich , . ${\displaystyle k\rightarrow \infty}$${\displaystyle n/2^{k}\rightarrow \infty}$${\displaystyle C_{1}>0}$${\ Displaystyle n}$${\ Displaystyle \ mathbb {E} [{\ tylda {m}} _ {n} ^ {cc} (\ mathbf {X}) -m (\ mathbf {X})] ^ {2} \ równoważnik C_ {1 }n^{-1/(3+d\log 2)}(\log n)^{2}}$

Spójność jednolitego KeRF

Zapewniając i , istnieje stała taka, że ​​, . ${\displaystyle k\rightarrow \infty}$${\displaystyle n/2^{k}\rightarrow \infty}$${\displaystyle C>0}$${\ Displaystyle \ mathbb {E} [{\ tylda {m}} _ {n} ^ {uf} (\ mathbf {X}) -m (\ mathbf {X})] ^ {2} \ Leq Cn ^ { -2/(6+3d\log 2)}(\log n)^{2}}$

Niedogodności

Chociaż losowe lasy często osiągają wyższą dokładność niż pojedyncze drzewo decyzyjne, poświęcają one wewnętrzną interpretację obecną w drzewach decyzyjnych. Drzewa decyzyjne należą do dość małej rodziny modeli uczenia maszynowego, które można łatwo zinterpretować wraz z modelami liniowymi, modelami opartymi na regułach i modelami opartymi na uwadze . Ta interpretowalność jest jedną z najbardziej pożądanych cech drzew decyzyjnych. Pozwala programistom potwierdzić, że model nauczył się realistycznych informacji z danych i pozwala użytkownikom końcowym mieć zaufanie i zaufanie do decyzji podejmowanych przez model. Na przykład podążanie ścieżką, którą podąża drzewo decyzyjne, aby podjąć decyzję, jest dość trywialne, ale podążanie ścieżkami dziesiątek lub setek drzew jest znacznie trudniejsze. Aby osiągnąć zarówno wydajność, jak i interpretację, niektóre techniki kompresji modelu umożliwiają przekształcenie losowego lasu w minimalne drzewo decyzyjne „narodzonego na nowo”, które wiernie odtwarza tę samą funkcję decyzyjną. Jeśli ustalono, że atrybuty predykcyjne są liniowo skorelowane ze zmienną docelową, użycie losowego lasu może nie zwiększyć dokładności podstawowego ucznia. Ponadto w przypadku problemów z wieloma zmiennymi kategorialnymi losowy las może nie być w stanie zwiększyć dokładności podstawowego ucznia.

Zobacz też

• Wzmacnianie
• Nauka drzewa decyzyjnego
• Nauka zespołowa
• Wzmocnienie gradientu
• Statystyki nieparametryczne
• Algorytm randomizowany

Bibliografia

Dalsza lektura

Scholia ma profil tematyczny dla Random forest .

Zewnętrzne linki

• Opis klasyfikatora Losowe Lasy (strona Leo Breimana)
• Liaw, Andy & Wiener, Matthew „Klasyfikacja i regresja przez randomForest” R News (2002) tom. 2/3 os. 18 (Omówienie wykorzystania pakietu losowego lasu dla R )