Metoda forestieră aleatorie

Metoda pădurii aleatoare este un algoritm de  învățare automată propus de Leo Breiman [1] [2] și Adele Cutler, care constă în folosirea unui comitet (ansamblu) de arbori de decizie . Algoritmul combină două idei principale: metoda de însăcire Breiman și metoda subspațială aleatorie .propus de Tin Kam Ho. Algoritmul este utilizat pentru probleme de clasificare, regresie și clustering. Ideea principală este să folosiți un ansamblu mare de arbori de decizie , fiecare dintre acestea oferind în sine o calitate foarte scăzută a clasificării, dar datorită numărului lor mare, rezultatul este bun.

Algoritm de învățare a clasificatorului

Fie setul de antrenament format din N eșantioane, dimensiunea spațiului de caracteristici este M și parametrul m (de obicei în problemele de clasificare ) este dat ca un număr incomplet de caracteristici pentru antrenament.

Cel mai obișnuit mod de a construi arbori de ansamblu - bagging ( eng.  bagging , scurt pentru eng.  bootstrap aggregation)  - se face după cum urmează:

  1. Să generăm un subeșantion repetat aleatoriu de dimensiune din eșantionul de antrenament. Unele eșantioane vor cădea în el de două sau mai multe ori, în timp ce, în medie (pentru mari aproximativ , unde  este baza logaritmului natural ), eșantioanele nu sunt incluse în set sau nu sunt selectate ( în engleză out-of-bag ). 
  2. Să construim un arbore de decizie care clasifică eșantioanele acestui subeșantion și, în cursul creării următorului nod al arborelui, vom alege un set de caracteristici pe baza căruia se face împărțirea (nu din toate caracteristicile M ). , dar numai din m alese aleatoriu). Alegerea celor mai bune dintre aceste m caracteristici se poate face în diferite moduri. Metoda originală a lui Breiman utilizează criteriul Gini , care este, de asemenea, utilizat în algoritmul arborelui de decizie CART . În unele implementări ale algoritmului, se folosește în schimb criteriul câștigului de informații . [3]
  3. Arborele este construit până când subeșantionarea este complet epuizată și nu este supus procedurii de tăiere ( eng.  pruning  - tăierea ramurilor), spre deosebire de arborii de decizie ai algoritmilor precum CART sau C4.5 .

Clasificarea obiectelor se realizează prin vot: fiecare arbore al comitetului atribuie obiectul care este clasificat uneia dintre clase, iar clasa care are cel mai mare număr de arbori votați câștigă.

Numărul optim de arbori este selectat astfel încât să se minimizeze eroarea de clasificare pe proba de testare. Dacă este absentă, estimarea erorii este minimizată pe eșantioanele care nu sunt incluse în set.

Evaluarea importanței variabilelor

Pădurile aleatorii obţinute prin metodele descrise mai sus pot fi folosite în mod natural pentru a evalua importanţa variabilelor în problemele de regresie şi clasificare . Următorul mod de estimare a fost descris de Breiman.

Primul pas în evaluarea importanței unei variabile într-un set de antrenament  este antrenamentul unei păduri aleatorii pe acel set. În timpul procesului de construire a modelului, este înregistrată o așa-numită eroare out-of-bag pentru fiecare element al setului de antrenament.(eroare articole neselectate). Apoi, pentru fiecare entitate, această eroare este mediată pe întreaga pădure aleatoare.

Pentru a evalua importanța parametrului --lea după antrenament, valorile parametrului --lea sunt amestecate pentru toate înregistrările setului de antrenament și se calculează din nou eroarea în afara sacului. Importanța parametrului este estimată prin medierea diferenței dintre ratele de eroare în afara sacului pentru toți arborii înainte și după amestecarea valorilor. În acest caz, valorile unor astfel de erori sunt normalizate la abaterea standard .

Parametrii eșantionului care produc valori mai mari sunt considerați mai importanți pentru setul de antrenament. Metoda are un dezavantaj potențial - pentru variabilele categorice cu un număr mare de valori, metoda tinde să considere astfel de variabile mai importante. Amestecarea parțială a valorilor în acest caz poate reduce influența acestui efect. [4] [5] Din grupurile de parametri corelați, a căror importanță se dovedește a fi aceeași, sunt selectate grupurile mai mici. [6]

Avantaje

Dezavantaje

Utilizare în lucrări științifice

Algoritmul este utilizat în lucrări științifice, de exemplu, pentru a evalua calitatea articolelor Wikipedia [7] [8] [9] .

Note

  1. ↑ Breiman, Leu . Păduri aleatorii   // Învățare automată : jurnal. - 2001. - Vol. 45 , nr. 1 . - P. 5-32 . - doi : 10.1023/A:1010933404324 .  (Engleză)  (Data accesării: 7 iunie 2009)
  2. ↑ Descrierea algoritmului pe site-ul lui Leo Breiman Arhivat 22 iunie 2008.  (Engleză)  (Data accesării: 7 iunie 2009)
  3. ↑ O descriere a procedurii de construire a copacilor folosită în Apache Mahout Arhivat 13 mai 2012 la Wayback Machine  ( accesat  la 7 iunie 2009)
  4. ↑ Deng, H.; Runger, G.; Tuv, E. (2011). Măsuri de părtinire a importanței pentru atribute și soluții cu mai multe valori . Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN). pp. 293-300.
  5. ↑ Altmann A., Tolosi L., Sander O., Lengauer T. Permutation importance:a corrected feature importance measure  (engleză)  // Bioinformatics : journal. - 2010. - doi : 10.1093/bioinformatics/btq134 .
  6. ↑ Tolosi L., Lengauer T. Clasificare cu caracteristici corelate: nefiabilitatea clasării caracteristicilor și soluțiilor.  (engleză)  // Bioinformatică: jurnal. - 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 decembrie ( vol. 228 ). - P. 308-320 . - doi : 10.1007/978-3-319-26762-3_27 .
  8. ↑ Lewoniewski W., Węcel K., Abramowicz W. Quality and Importance of Wikipedia Articles in Different Languages  ​​​​//  Information and Software Technologies. ICIST 2016. Communications in Computer and Information Science: jurnal. - 2016. - 22 septembrie ( vol. 639 ). - P. 613-624 . - doi : 10.1007/978-3-319-46254-7_50 .
  9. ↑ Warncke-Wang M., Cosley D., Riedl J. Spune-mi mai multe: Un model de calitate acționabil pentru wikipedia  //  WikiSym '13 Proceedings of the 9th International Symposium on Open Collaboration : journal. - 2013. - doi : 10.1145/2491055.2491063 .

Literatură

Link -uri

Implementări