Wikipedia

Las losowy

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 lub przewidywaną średnią poszczególnych drzew

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[1][2]. Losowe lasy decyzyjne poprawiają tendencję drzew decyzyjnych do nadmiernego dopasowywania się do zestawu treningowego[3]. Pierwszy algorytm losowych lasów decyzyjnych został stworzony przez Tin 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, należący do Minitab, Inc.)[10]. Rozszerzenie łączy pomysł baggingu (agregacji bootstrapa) Breimana i losowy wybór cech, 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

Wstęp: metoda drzew decyzyjnych edytuj

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

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

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, 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 x':

 

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

Od agregacji bootstrapa po lasy losowe edytuj

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

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

ExtraTrees edytuj

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

Właściwości edytuj

Znaczenie zmiennych edytuj

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

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

Lasy losowe w pracach naukowych edytuj

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[23][24][25].

Implementacje open source edytuj

  • 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ż edytuj

Przypisy edytuj

  1. ↑ a b c Wayback Machine [online], ect.bell-labs.com [dostęp 2019-11-25] [zarchiwizowane z adresu 2016-04-17].
  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, DOI: 10.1109/34.709601 [dostęp 2019-05-25] [zarchiwizowane z adresu 2016-03-04].
  3. ↑ a b Hastie, Tibshirani i Friedman 2008 ↓, s. 587, 588.
  4. ↑ E.M. Kleinberg, Stochastic discrimination, „Annals of Mathematics and Artificial Intelligence”, 1 (1–4), 1990, s. 207–239, DOI: 10.1007/BF01531079 [dostęp 2019-05-25] [zarchiwizowane z adresu 2018-01-18].
  5. ↑ E.M. Kleinberg, An overtraining-resistant stochastic modeling method for pattern recognition, „Ann. Statist.”, 24 (6), 1996, s. 2319–2349, DOI: 10.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, DOI: 10.1109/34.857004 [dostęp 2019-05-25] [zarchiwizowane z adresu 2018-01-18].
  7. ↑ a b Leo Breiman, Random Forests, „Machine Learning”, 45 (1), 2001, s. 5–32, DOI: 10.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, DOI: 10.1162/neco.1997.9.7.1545 [dostęp 2019-05-25] [zarchiwizowane z adresu 2018-02-05].
  12. ↑ Hastie, Tibshirani i Friedman 2008 ↓, s. 352.
  13. ↑ Introduction to Statistical Learning.
  14. ↑ Tin Kam Ho, A Data Complexity Analysis of Comparative Advantages of Decision Forest Constructors, „Pattern Analysis & Applications”, 5 (2), 2002, s. 102–112, DOI: 10.1007/s100440200009 [dostęp 2019-05-25] [zarchiwizowane z adresu 2016-04-17].
  15. ↑ a b c Hastie, Tibshirani i Friedman 2008 ↓, s. 592.
  16. ↑ Pierre Geurts, Damien Ernst, Louis Wehenkel, Extremely randomized trees, „Machine Learning”, 63 (1), 2006, s. 3–42, DOI: 10.1007/s10994-006-6226-1.
  17. ↑ Ruoqing Zhu, Donglin Zeng, Michael R. Kosorok, Reinforcement Learning Trees, „Journal of the American Statistical Association”, 110 (512), 2015, s. 1770–1784, DOI: 10.1080/01621459.2015.1036994, PMID: 26903687, PMCID: PMC4760114.
  18. ↑ 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.
  19. ↑ André Altmann i inni, Permutation importance: a corrected feature importance measure, „Bioinformatics”, 26 (10), 2010, s. 1340–1347, DOI: 10.1093/bioinformatics/btq134, PMID: 20385727 [zarchiwizowane z adresu 2013-04-15].
  20. ↑ 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, DOI: 10.1016/j.csda.2006.12.030.
  21. ↑ 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, DOI: 10.1109/tpami.2016.2636831, PMID: 28114007, arXiv:1512.03444.
  22. ↑ Laura Toloşi, Thomas Lengauer, Classification with correlated features: unreliability of feature ranking and solutions, „Bioinformatics”, 27 (14), 2011, s. 1986–1994, DOI: 10.1093/bioinformatics/btr300, PMID: 21576180 [zarchiwizowane z adresu 2013-04-15].
  23. ↑ Krzysztof Węcel, Włodzimierz Lewoniewski, Modelling the Quality of Attributes in Wikipedia Infoboxes, BIS 2015: Business Information Systems Workshops, 2015, s. 308–320, DOI: 10.1007/978-3-319-26762-3_27, ISBN 978-3-319-26761-6.
  24. ↑ 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, DOI: 10.1007/978-3-319-46254-7_50, ISBN 978-3-319-46253-0.
  25. ↑ 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, DOI: 10.1145/2491055.2491063, ISBN 978-1-4503-1852-5, Article No. 8.

Bibliografia edytuj

Źródło: „https://pl.wikipedia.org/w/index.php?title=Las_losowy&oldid=71498859”