Slumpmässig skogsmetod

Random forest-metoden är en maskininlärningsalgoritm som  föreslagits av Leo Breiman [1] [2] och Adele Cutler, som består i att använda en kommitté (ensemble) av beslutsträd . Algoritmen kombinerar två huvudidéer: Breiman bagging- metoden och den slumpmässiga subspace-metoden .föreslagit av Tin Kam Ho. Algoritmen används för klassificering, regression och klustringsproblem. Huvudtanken är att använda en stor ensemble av beslutsträd , som var och en i sig ger en mycket låg klassificeringskvalitet, men på grund av deras stora antal blir resultatet bra.

Inlärningsalgoritm för klassificerare

Låt träningsuppsättningen bestå av N sampel, dimensionen av funktionsutrymmet är M och parametern m (vanligtvis i klassificeringsproblem ) ges som ett ofullständigt antal funktioner för inlärning.

Det vanligaste sättet att bygga ensembleträd - bagging ( eng.  bagging , förkortning för eng.  bootstrap aggregation)  - görs på följande sätt:

  1. Låt oss generera ett slumpmässigt upprepat delprov av storlek från träningsprovet. Vissa prover kommer att falla in i det två eller flera gånger, medan i genomsnitt (för stora ungefär , var  är basen för den naturliga logaritmen ) prover inte ingår i uppsättningen eller inte är valda ( engelska out-of-bag ). 
  2. Låt oss bygga ett beslutsträd som klassificerar proverna av detta delprov, och under loppet av att skapa nästa nod i trädet kommer vi att välja en uppsättning funktioner på basis av vilka uppdelningen görs (inte från alla M funktioner , men endast från m slumpmässigt utvalda). Valet av det bästa av dessa m funktioner kan göras på olika sätt. Breimans ursprungliga metod använder Gini-kriteriet , som också används i CART- beslutsträdsalgoritmen . I vissa implementeringar av algoritmen används istället informationsvinstkriteriet . [3]
  3. Trädet byggs tills delprovtagningen är helt uttömd och utsätts inte för beskärningsproceduren ( eng.  beskärning  - skära av grenar), i motsats till beslutsträden för algoritmer som CART eller C4.5 .

Klassificeringen av objekt utförs genom omröstning: varje träd i kommittén tilldelar objektet som klassificeras till en av klasserna, och den klass som har det största antalet röstade träd vinner.

Det optimala antalet träd väljs på ett sådant sätt att klassificeringsfelet på testprovet minimeras. Om den saknas minimeras feluppskattningen på prover som inte ingår i uppsättningen.

Bedöma betydelsen av variabler

Slumpmässiga skogar som erhållits med ovan beskrivna metoder kan naturligtvis användas för att utvärdera betydelsen av variabler i regressions- och klassificeringsproblem . Följande sätt för sådan uppskattning beskrevs av Breiman.

Det första steget i att utvärdera betydelsen av en variabel i en träningsuppsättning  är att träna en slumpmässig skog på den uppsättningen. Under modellbyggnadsprocessen registreras ett så kallat out-of-bag-fel för varje element i träningssetet.(fel om ovalda objekt). Sedan, för varje entitet, beräknas medelvärdet av detta fel över hela den slumpmässiga skogen.

För att utvärdera vikten av den -th parametern efter träning, blandas värdena för den -th parametern för alla poster i träningsuppsättningen och out-of-bag-felet beräknas igen. Vikten av parametern uppskattas genom att medelvärdet av skillnaden i out-of-bag felfrekvens över alla träd före och efter blandning av värdena. I det här fallet är värdena för sådana fel normaliserade till standardavvikelsen .

Exempelparametrar som ger större värden anses vara viktigare för träningsuppsättningen. Metoden har en potentiell nackdel - för kategoriska variabler med ett stort antal värden tenderar metoden att betrakta sådana variabler som viktigare. Partiell blandning av värden i detta fall kan minska påverkan av denna effekt. [4] [5] Från grupperna av korrelerade parametrar, vars betydelse visar sig vara densamma, väljs de mindre grupperna. [6]

Fördelar

Nackdelar

Användning i vetenskapliga artiklar

Algoritmen används i vetenskapliga artiklar, till exempel för att utvärdera kvaliteten på Wikipedia- artiklar [7] [8] [9] .

Anteckningar

  1. ↑ Breiman, Leo . Random Forests   // Machine Learning : journal. - 2001. - Vol. 45 , nr. 1 . - S. 5-32 . - doi : 10.1023/A:1010933404324 .  (engelska)  (åtkomstdatum: 7 juni 2009)
  2. ↑ Algoritmbeskrivning på Leo Breimans hemsida Arkiverad 22 juni 2008.  (engelska)  (åtkomstdatum: 7 juni 2009)
  3. ↑ En beskrivning av trädbyggnadsproceduren som används i Apache Mahout Arkiverad 13 maj 2012 på Wayback Machine  ( Åtkomst  7 juni 2009)
  4. ↑ Deng, H.; Runger, G.; Tuv, E. (2011). Bias av betydelse för attribut och lösningar med flera värden . Handlingar från den 21:a internationella konferensen om artificiella neurala nätverk (ICANN). pp. 293-300.
  5. ↑ Altmann A., Tolosi L., Sander O., Lengauer T. Permutation essential:a corrected feature important measure  (engelska)  // Bioinformatics: journal. - 2010. - doi : 10.1093/bioinformatics/btq134 .
  6. ↑ Tolosi L., Lengauer T. Klassificering med korrelerade egenskaper: opålitlighet i funktionsrankning och lösningar.  (engelska)  // Bioinformatik: tidskrift. - 2011. - doi : 10.1093/bioinformatics/btr300 .
  7. ↑ Węcel K., Lewoniewski W. Modellering av kvaliteten på attribut i Wikipedia infoboxar  //  Föreläsningsanteckningar i affärsinformationsbehandling: journal. - 2015. - 2 december ( vol. 228 ). - S. 308-320 . - doi : 10.1007/978-3-319-26762-3_27 .
  8. ↑ Lewoniewski W., Węcel K., Abramowicz W. Kvalitet och betydelse för Wikipedia-artiklar på olika språk  //  Informations- och mjukvaruteknik. ICIST 2016. Communications in Computer and Information Science: tidskrift. - 2016. - 22 september ( vol. 639 ). - s. 613-624 . - doi : 10.1007/978-3-319-46254-7_50 .
  9. ↑ Warncke-Wang M., Cosley D., Riedl J. Tell me more: An actionable quality model for wikipedia  //  WikiSym '13 Proceedings of the 9th International Symposium on Open Collaboration : journal. - 2013. - doi : 10.1145/2491055.2491063 .

Litteratur

Länkar

Genomföranden