Metoda náhodného lesa

Metoda náhodného lesa je algoritmus strojového  učení navržený Leo Breimanem [ 1] [2] a Adele Cutler, která spočívá ve využití výboru (souboru) rozhodovacích stromů . Algoritmus kombinuje dvě hlavní myšlenky: Breimanovu metodu pytlování a metodu náhodného podprostoru .navrhl Tin Kam Ho. Algoritmus se používá pro klasifikační, regresní a shlukovací problémy. Hlavní myšlenkou je použití velkého souboru rozhodovacích stromů , z nichž každý sám o sobě poskytuje velmi nízkou kvalitu klasifikace, ale vzhledem k jejich velkému počtu je výsledek dobrý.

Algoritmus učení klasifikátoru

Nechť se trénovací množina skládá z N vzorků, rozměr prostoru příznaků je M a parametr m (obvykle v klasifikačních úlohách ) je uveden jako neúplný počet příznaků pro učení.

Nejběžnější způsob, jak postavit souborové stromy - pytlování ( angl.  bagging , zkratka pro eng.  bootstrap aggregation)  - se provádí následovně:

  1. Vygenerujme náhodný opakovaný podvzorek velikosti z trénovacího vzorku. Některé vzorky do ní spadnou dvakrát nebo vícekrát, přičemž v průměru (u velkých přibližně , kde  je základ přirozeného logaritmu ) vzorky nejsou v sadě zahrnuty nebo nejsou vybrány ( anglicky out-of-bag ). 
  2. Postavme rozhodovací strom , který klasifikuje vzorky tohoto podvzorku, a v průběhu vytváření dalšího uzlu stromu vybereme sadu prvků, na jejichž základě se rozdělení provádí (ne ze všech M prvků , ale pouze z m náhodně vybraných). Výběr nejlepších z těchto m vlastností lze provést různými způsoby. Původní Breimanova metoda používá Giniho kritérium , které se také používá v algoritmu rozhodovacího stromu CART . V některých implementacích algoritmu se místo toho používá kritérium informačního zisku . [3]
  3. Strom se buduje až do úplného vyčerpání dílčího vzorkování a nepodléhá procesu prořezávání ( angl.  pruning  - odřezávání větví), na rozdíl od rozhodovacích stromů algoritmů jako CART nebo C4.5 .

Klasifikace objektů se provádí hlasováním: každý strom komise přiřadí klasifikovaný objekt do jedné ze tříd a třída, která má největší počet stromů, pro které se hlasovalo, vyhrává.

Optimální počet stromů se volí tak, aby se minimalizovala chyba klasifikátoru na zkušebním vzorku. Pokud chybí, je odhad chyby minimalizován na vzorcích, které nejsou součástí sady.

Hodnocení důležitosti proměnných

Náhodné lesy získané výše popsanými metodami lze přirozeně použít k hodnocení důležitosti proměnných v regresních a klasifikačních problémech . Následující způsob takového odhadu popsal Breiman.

Prvním krokem při hodnocení důležitosti proměnné v trénovací sadě  je natrénovat na této množině náhodný les. Během procesu sestavování modelu je u každého prvku cvičné sady zaznamenána tzv. chyba out-of-bag .(chyba nevybraných položek). Potom se pro každou entitu tato chyba zprůměruje pro celou náhodnou doménovou strukturu.

Aby bylo možné vyhodnotit důležitost parametru -th po trénování, jsou hodnoty -th parametru smíchány pro všechny záznamy trénovací sady a znovu se vypočítá chyba out-of-bag. Důležitost parametru se odhaduje zprůměrováním rozdílu v chybovosti out-of-bag u všech stromů před a po smíchání hodnot. V tomto případě jsou hodnoty takových chyb normalizovány na standardní odchylku .

Vzorové parametry, které produkují větší hodnoty, jsou pro trénovací sadu považovány za důležitější. Metoda má potenciální nevýhodu – u kategoriálních proměnných s velkým počtem hodnot má metoda tendenci takové proměnné považovat za důležitější. Částečné smíchání hodnot v tomto případě může snížit vliv tohoto efektu. [4] [5] Ze skupin korelovaných parametrů, jejichž důležitost se ukazuje jako stejná, se vybírají menší skupiny. [6]

Výhody

Nevýhody

Použití ve vědeckých pracích

Algoritmus se používá ve vědeckých pracích, například pro hodnocení kvality článků na Wikipedii [7] [8] [9] .

Poznámky

  1. ↑ Breiman, Leo . Náhodné lesy   // Strojové učení : deník. - 2001. - Sv. 45 , č. 1 . - str. 5-32 . - doi : 10.1023/A:1010933404324 .  (anglicky)  (Datum přístupu: 7. června 2009)
  2. ↑ Popis algoritmu na webu Lea Breimana Archivováno 22. června 2008.  (anglicky)  (Datum přístupu: 7. června 2009)
  3. ↑ Popis postupu vytváření stromu používaného v Apache Mahout Archivováno 13. května 2012 na Wayback Machine  ( přístup  7. června 2009)
  4. ↑ Deng, H.; Ranger, G.; Tuv, E. (2011). Míry zkreslení důležitosti pro vícehodnotové atributy a řešení . Sborník příspěvků z 21. mezinárodní konference o umělých neuronových sítích (ICANN). str. 293-300.
  5. ↑ Altmann A., Tolosi L., Sander O., Lengauer T. Význam permutace: míra důležitosti opravené funkce  (anglicky)  // Bioinformatics : journal. - 2010. - doi : 10.1093/bioinformatics/btq134 .
  6. ↑ Tolosi L., Lengauer T. Klasifikace s korelovanými rysy: nespolehlivost hodnocení prvků a řešení.  (anglicky)  // Bioinformatika: časopis. - 2011. - doi : 10.1093/bioinformatics/btr300 .
  7. ↑ Węcel K., Lewoniewski W. Modeling the Quality of Attributes in Wikipedia Infoboxes  //  Lecture Notes in Business Information Processing: journal. - 2015. - 2. prosince ( sv. 228 ). - S. 308-320 . - doi : 10.1007/978-3-319-26762-3_27 .
  8. ↑ Lewoniewski W., Węcel K., Abramowicz W. Kvalita a význam článků Wikipedie v různých jazycích  //  Informační a softwarové technologie. ICIST 2016. Komunikace v počítačové a informační vědě: časopis. - 2016. - 22. září ( sv. 639 ). - S. 613-624 . - doi : 10.1007/978-3-319-46254-7_50 .
  9. ↑ Warncke-Wang M., Cosley D., Riedl J. Řekněte mi více: Akční model kvality pro wikipedii  //  WikiSym '13 Proceedings of the 9th International Symposium on Open Collaboration: journal. - 2013. - doi : 10.1145/2491055.2491063 .

Literatura

Odkazy

Implementace