Las losowy

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Las losowy (Random forest) lub losowy las decyzyjny (Random decision forest) 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 (klasyfikacja) lub przewidywaną średnią (regresja) poszczególnych drzew[1][2]. Losowe lasy decyzyjne poprawiają tendencję drzew decyzyjnych do nadmiernego dopasowywania się do zestawu treningowego[3] s.587–588. Pierwszy algorytm losowych lasów decyzyjnych został stworzony przez Tina Kam Ho[1] przy użyciu metody losowej podprzestrzeni[2], która w formule Ho jest sposobem na implementację podejścia „dyskryminacji stochastycznej” do klasyfikacji zaproponowanej przez Eugene'a Kleinberga[4][5][6].

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

Algorytm[edytuj | edytuj kod]

Eliminacje: uczenie się drzewa decyzyjnego[edytuj | edytuj kod]

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 ”[3] 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[3]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.

Agregacja bootstrapa[edytuj | edytuj kod]

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

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

Po szkoleniu prognozy dla niewidocznych próbek x' mogą być wykonane przez uśrednienie prognoz ze wszystkich poszczególnych drzew regresji na 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' :

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[12]. Błąd treningowy i testowy mają tendencję do wyrównywania się po dopasowaniu pewnej liczby drzew.

Od agregacji bootstrapa po losowe lasy[edytuj | edytuj kod]

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[13].

Zazwyczaj w problemie klasyfikacji, z p cechami p (zaokrąglone w dół) cech jest użyte w każdym podziale[3] 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[3]s: 592. W praktyce najlepsze wartości dla tych parametrów będą zależeć od problemu i powinny być traktowane jako parametry strojenia[3] : 592.

ExtraTrees[edytuj | edytuj kod]

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 do klasyfikacji i dla regresji, gdzie to liczba funkcji w modelu[14].

Właściwości[edytuj | edytuj kod]

Znaczenie zmiennych[edytuj | edytuj kod]

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[7] i została zaimplementowana w R w pakiecie randomForest[8].

Pierwszy krok w mierzeniu zmiennego znaczenia w zbiorze danych 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 -tej cechy po treningu, wartości -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 -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.[15].

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[16][17] i rosnące nieobciążone drzewa[18][19] 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[20].

Lasy losowe w pracach naukowych[edytuj | edytuj kod]

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[21][22][23].

Implementacje open source[edytuj | edytuj kod]

  • 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.
  • Pomarańczowy pakiet do eksploracji danych obejmuje przypadkowego ucznia lasu i może wizualizować wyszkolonego lasu.
  • 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ż[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  1. a b c https://web.archive.org/web/20160417030218/http://ect.bell-labs.com/who/tkh/publications/papers/odt.pdf
  2. a b Tin Kam Ho, The random subspace method for constructing decision forests, „IEEE Transactions on Pattern Analysis and Machine Intelligence”, 20 (8), 1998, s. 832 - 844, DOI10.1109/34.709601.
  3. a b c d e f Trevor Hastie, Robert Tibshirani, Jerome Friedman: The Elements of Statistical Learning. Wyd. 2. Springer, 2008. ISBN 0-387-95284-5.
  4. E.M. Kleinberg, Stochastic discrimination, „Annals of Mathematics and Artificial Intelligence”, 1 (1–4), 1990, s. 207–239, DOI10.1007/BF01531079.
  5. E.M. Kleinberg, An overtraining-resistant stochastic modeling method for pattern recognition, „Ann. Statist.”, 24 (6), 1996, s. 2319--2349, DOI10.1214/aos/1032181157, MR1425956.
  6. E.M. Kleinberg, On the algorithmic implementation of stochastic discrimination, „IEEE Transactions on Pattern Analysis and Machine Intelligence”, 22 (5), 2000, s. 473 - 490, DOI10.1109/34.857004.
  7. a b Leo Breiman, Random Forests, „Machine Learning”, 45 (1), 2001, s. 5–32, DOI10.1023/A:1010933404324.
  8. a b randomForest.pdf.
  9. U.S. trademark registration number 3185828, registered 2006/12/19.
  10. RANDOM FORESTS Trademark of Health Care Productivity, Inc. - Registration Number 3185828 - Serial Number 78642027 :: Justia Trademarks.
  11. Yali Amit, Donald Geman, Shape Quantization and Recognition with Randomized Trees, „Neural Computation”, 9 (7), 1997, s. 1545-1588, DOI10.1162/neco.1997.9.7.1545.
  12. Introduction to Statistical Learning.
  13. Tin Kam Ho, A Data Complexity Analysis of Comparative Advantages of Decision Forest Constructors, „Pattern Analysis & Applications”, 5 (2), 2002, s. 102–112, DOI10.1007/s100440200009.
  14. Pierre Geurts, Damien Ernst, Louis Wehenkel, Extremely randomized trees, „Machine Learning”, 63 (1), 2006, s. 3–42, DOI10.1007/s10994-006-6226-1.
  15. Publikacja w otwartym dostępie – możesz ją bezpłatnie przeczytać Ruoqing Zhu, Donglin Zeng, Michael R. Kosorok, Reinforcement Learning Trees, „Journal of the American Statistical Association”, 110 (512), 2015, s. 1770-1784, DOI10.1080/01621459.2015.1036994, PMID26903687, PMCIDPMC4760114.
  16. H. Deng, G. Runger, E. Tuv, Bias of importance measures for multi-valued attributes and solutions, „Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN)”, 2011, s. 293–300.
  17. André Altmann i inni, Permutation importance: a corrected feature importance measure, „Bioinformatics”, 26 (10), 2010, s. 1340–1347, DOI10.1093/bioinformatics/btq134, PMID20385727.
  18. Carolin Strobl, Anne-Laure Boulesteix, Thomas Augustin, Unbiased split selection for classification trees based on the Gini Index, „Computational Statistics & Data Analysis”, 52 (1), 2007, s. 483-501, DOI10.1016/j.csda.2006.12.030.
  19. Amichai Painsky, Saharon Rosset, Cross-Validated Variable Selection in Tree-Based Methods Improves Predictive Performance, „IEEE Transactions on Pattern Analysis and Machine Intelligence”, 39 (11), 2017, s. 2142 - 2153, DOI10.1109/tpami.2016.2636831, PMID28114007, arXiv:1512.03444.
  20. Laura Toloşi, Thomas Lengauer, Classification with correlated features: unreliability of feature ranking and solutions, „Bioinformatics”, 27 (14), 2011, s. 1986–1994, DOI10.1093/bioinformatics/btr300, PMID21576180.
  21. Krzysztof Węcel, Włodzimierz Lewoniewski, Modelling the Quality of Attributes in Wikipedia Infoboxes, BIS 2015: Business Information Systems Workshops, 2015, s. 308-320, DOI10.1007/978-3-319-26762-3_27, ISBN 978-3-319-26761-6.
  22. Włodzimierz Lewoniewski, Krzysztof Węcel, Witold Abramowicz, Quality and Importance of Wikipedia Articles in Different Languages, ICIST 2016: Information and Software Technologies, 2016, s. 613-624, DOI10.1007/978-3-319-46254-7_50, ISBN 978-3-319-46253-0.
  23. Morten Warncke-Wang, Dan Cosley, John Riedl, Tell me more: an actionable quality model for Wikipedia, Hong Kong, China: WikiSym '13 Proceedings of the 9th International Symposium on Open Collaboration, 5 sierpnia 2013, DOI10.1145/2491055.2491063, ISBN 978-1-4503-1852-5, Article No. 8.