Véletlenszerű erdő módszer

A véletlen erdő módszer Leo Breiman [1] [2] és Adele Cutler által javasolt gépi tanulási  algoritmus ., amely döntési fákból álló bizottság (együttes) használatából áll . Az algoritmus két fő ötletet egyesít: a Breiman zsákolási módszert és a véletlen altér módszerét .javasolta Tin Kam Ho. Az algoritmust osztályozási, regressziós és klaszterezési problémák esetén használják. A fő ötlet az, hogy nagy számú döntési fát használjunk , amelyek mindegyike önmagában nagyon alacsony minőségű osztályozást ad, de nagy számuk miatt az eredmény jó.

Osztályozó tanulási algoritmus

Legyen a tanító halmaz N mintából, a jellemzőtér dimenziója M , és az m paraméter (általában osztályozási feladatokban ) a tanuláshoz hiányos jellemzőszámként adható meg.

Az együttes fák felépítésének legáltalánosabb módja - a zsákolás ( eng.  bagging , az eng.  bootstrap aggregation rövidítése)  - a következőképpen történik:

  1. Generáljunk egy véletlenszerűen ismétlődő méretű részmintát a betanítási mintából. Egyes minták kétszer vagy többször is beleesnek, míg átlagosan (nagyon körülbelül , ahol  a természetes logaritmus alapja ) a minták nem szerepelnek a halmazban, vagy nincsenek kiválasztva ( angolul out-of-bag ). 
  2. Készítsünk egy döntési fát , amely osztályozza ennek a részmintának a mintáit, és a fa következő csomópontjának létrehozása során kiválasztunk egy olyan tulajdonsághalmazt, amely alapján a felosztás történik (nem minden M jellemzőből , de csak a m ​​véletlenszerűen kiválasztottak közül). Ezen m jellemzők közül a legjobbak kiválasztása többféleképpen történhet. Breiman eredeti módszere a Gini-kritériumot használja, amelyet a CART döntési fa algoritmusában is használnak . Az algoritmus egyes megvalósításaiban ehelyett az információszerzési kritériumot használják . [3]
  3. A fát addig építik, amíg az almintavétel teljesen ki nem merül, és nem vetik alá metszési eljárásnak ( eng.  pruning  - ágak levágása), ellentétben az olyan algoritmusok döntési fáival, mint a CART vagy a C4.5 .

Az objektumok besorolása szavazással történik: a bizottság minden fája a besorolandó objektumot valamelyik osztályba rendeli, és az az osztály nyer, amelyikre a legtöbb fa szavazott.

A fák optimális számát úgy választjuk meg, hogy az osztályozó hibája minimális legyen a vizsgálati mintán. Ha hiányzik, a hibabecslés minimálisra csökken a készletben nem szereplő mintákon.

A változók fontosságának felmérése

A fent leírt módszerekkel nyert véletlenszerű erdők természetesen felhasználhatók a változók fontosságának értékelésére a regressziós és osztályozási problémákban . Az ilyen becslések következő módját írta le Breiman.

Az első lépés egy változó fontosságának értékeléséhez egy gyakorlóhalmazban  az, hogy egy véletlenszerű erdőt képezzünk ezen a halmazon. A modellépítés során a képzési halmaz minden eleméhez egy úgynevezett out-of-bag hiba kerül rögzítésre.(nem kiválasztott tételek hiba). Ezután minden entitásnál ezt a hibát a rendszer a teljes véletlenszerű erdőre átlagolja.

A -edik paraméter fontosságának értékelése érdekében a betanítás után a -edik paraméter értékeit összekeverik a betanítási halmaz összes rekordjához, és újra kiszámítják az out-of-bag hibát. A paraméter fontosságát úgy becsüljük meg, hogy az értékek keverése előtt és után az összes fa esetében az out-of-bag hibaarányok különbségét átlagoljuk. Ebben az esetben az ilyen hibák értékeit a szórásra normalizálják .

Azok a mintaparaméterek, amelyek nagyobb értékeket produkálnak, fontosabbnak tekinthetők a képzési készlet számára. A módszernek van egy lehetséges hátránya - a nagyszámú kategorikus változók esetében a módszer hajlamos az ilyen változókat fontosabbnak tekinteni. Az értékek részleges keverése ebben az esetben csökkentheti ennek a hatásnak a hatását. [4] [5] A korrelált paraméterek csoportjai közül, amelyek fontossága azonosnak bizonyul, a kisebb csoportokat választjuk ki. [6]

Előnyök

Hátrányok

Használata tudományos közleményekben

Az algoritmust tudományos közleményekben használják, például a Wikipédia -cikkek minőségének értékelésére [7] [8] [9] .

Jegyzetek

  1. Breiman, Leo . Véletlenszerű erdők   // Gépi tanulás : folyóirat. - 2001. - Vol. 45 , sz. 1 . - 5-32 . o . - doi : 10.1023/A:1010933404324 .  (angol)  (Hozzáférés dátuma: 2009. június 7.)
  2. Algoritmus leírása Leo Breiman honlapján Archiválva : 2008. június 22.  (angol)  (Hozzáférés dátuma: 2009. június 7.)
  3. Az Apache Mahoutban használt faépítési eljárás leírása archiválva 2012. május 13-án a Wayback Machine -nél  ( Hozzáférés  : 2009. június 7.)
  4. Deng, H.; Runger, G.; Tuv, E. (2011). A többértékű attribútumok és megoldások fontossági torzítása . A 21. International Conference on Artificial Neural Networks (ICANN) anyaga. pp. 293-300.
  5. Altmann A., Tolosi L., Sander O., Lengauer T. Permutációs fontosság: a korrigált jellemző fontossági mértéke  (angol)  // Bioinformatika : folyóirat. - 2010. - doi : 10.1093/bioinformatika/btq134 .
  6. Tolosi L., Lengauer T. Osztályozás korrelált jellemzőkkel: a jellemzők rangsorolásának és megoldásainak megbízhatatlansága.  (angol)  // Bioinformatika: folyóirat. - 2011. - doi : 10.1093/bioinformatika/btr300 .
  7. Węcel K., Lewoniewski W. Az attribútumok minőségének modellezése a Wikipédia információs dobozaiban  //  Lecture Notes in Business Information Processing : folyóirat. - 2015. - december 2. ( 228. köt. ). - P. 308-320 . - doi : 10.1007/978-3-319-26762-3_27 .
  8. Lewoniewski W., Węcel K., Abramowicz W. A Wikipédia-cikkek minősége és jelentősége különböző nyelveken  //  Információs és szoftvertechnológiák. ICIST 2016. Communications in Computer and Information Science: folyóirat. - 2016. - szeptember 22. ( 639. köt. ). - P. 613-624 . - doi : 10.1007/978-3-319-46254-7_50 .
  9. Warncke-Wang M., Cosley D., Riedl J. Mondjon el többet: Egy használható minőségi modell a wikipédiához  //  WikiSym '13 Proceedings of the 9th International Symposium on Open Collaboration : Journal. - 2013. - doi : 10.1145/2491055.2491063 .

Irodalom

Linkek

Megvalósítások