Tilfældig skovmetode

Den tilfældige skovmetode er en maskinlæringsalgoritme  foreslået af Leo Breiman [ 1] [2] og Adele Cutler, som består i at bruge et udvalg (ensemble) af beslutningstræer . Algoritmen kombinerer to hovedideer: Breiman- bagging - metoden og random subspace-metoden .foreslået af Tin Kam Ho. Algoritmen bruges til klassificering, regression og klyngeproblemer. Hovedideen er at bruge et stort ensemble af beslutningstræer , som hver i sig selv giver en meget lav kvalitet af klassificering, men på grund af deres store antal er resultatet godt.

Klassificeringsindlæringsalgoritme

Lad træningssættet bestå af N prøver, dimensionen af ​​trækrummet er M , og parameteren m (normalt i klassifikationsproblemer ) er givet som et ufuldstændigt antal træk til læring.

Den mest almindelige måde at bygge ensembletræer på - bagging ( eng.  bagging , forkortelse for eng.  bootstrap aggregation)  - udføres som følger:

  1. Lad os generere en tilfældig gentaget delprøve af størrelse fra træningsprøven. Nogle prøver vil falde ind i det to eller flere gange, mens prøver i gennemsnit (for store ca , hvor  er bunden af ​​den naturlige logaritme ) ikke er inkluderet i sættet eller ikke er valgt ( engelsk out-of-bag ). 
  2. Lad os bygge et beslutningstræ, der klassificerer prøverne af denne delprøve, og i løbet af oprettelsen af ​​den næste knude i træet, vil vi vælge et sæt funktioner, som opdelingen foretages på grundlag af (ikke fra alle M funktioner , men kun fra m tilfældigt udvalgte). Valget af det bedste af disse m funktioner kan gøres på forskellige måder. Breimans oprindelige metode bruger Gini-kriteriet , som også bruges i CART -beslutningstræalgoritmen . I nogle implementeringer af algoritmen bruges informationsforstærkningskriteriet i stedet for . [3]
  3. Træet bygges, indtil delprøvetagningen er fuldstændig opbrugt og er ikke udsat for beskæringsproceduren ( eng.  pruning  - afskæring af grene), i modsætning til beslutningstræerne for algoritmer som CART eller C4.5 .

Klassificeringen af ​​objekter udføres ved afstemning: hvert træ i komiteen tildeler objektet, der klassificeres, til en af ​​klasserne, og den klasse, der har det største antal træer, der er stemt på, vinder.

Det optimale antal træer vælges på en sådan måde, at klassificeringsfejlen på testprøven minimeres. Hvis den er fraværende, minimeres fejlestimatet på prøver, der ikke er inkluderet i sættet.

Vurdering af betydningen af ​​variabler

Tilfældige skove opnået ved de ovenfor beskrevne metoder kan naturligvis bruges til at vurdere betydningen af ​​variable i regressions- og klassifikationsproblemer . Den følgende måde at foretage en sådan vurdering blev beskrevet af Breiman.

Det første trin i at evaluere vigtigheden af ​​en variabel i et træningssæt  er at træne en tilfældig skov på det sæt. Under modelbygningsprocessen registreres en såkaldt out-of-bag-fejl for hvert element i træningssættet.(fejl fra umarkerede elementer). Derefter beregnes gennemsnittet af denne fejl for hver enhed over hele den tilfældige skov.

For at evaluere vigtigheden af ​​den -th parameter efter træning, blandes værdierne af den -th parameter for alle registreringer af træningssættet, og out-of-bag-fejlen beregnes igen. Vigtigheden af ​​parameteren er estimeret ved at tage et gennemsnit af forskellen i out-of-bag fejlrater over alle træer før og efter blanding af værdierne. I dette tilfælde normaliseres værdierne af sådanne fejl til standardafvigelsen .

Prøveparametre, der producerer større værdier, anses for at være vigtigere for træningssættet. Metoden har en potentiel ulempe - for kategoriske variable med et stort antal værdier har metoden en tendens til at betragte sådanne variable som vigtigere. Delvis blanding af værdier i dette tilfælde kan reducere indflydelsen af ​​denne effekt. [4] [5] Fra grupperne af korrelerede parametre, hvis betydning viser sig at være den samme, udvælges de mindre grupper. [6]

Fordele

Ulemper

Brug i videnskabelige artikler

Algoritmen bruges i videnskabelige artikler, for eksempel til at evaluere kvaliteten af ​​Wikipedia- artikler [7] [8] [9] .

Noter

  1. ↑ Breiman, Leo . Tilfældige skove   // ​​Machine Learning : journal. - 2001. - Bd. 45 , nr. 1 . - S. 5-32 . - doi : 10.1023/A:1010933404324 .  (engelsk)  (dato for adgang: 7. juni 2009)
  2. ↑ Algoritmebeskrivelse på Leo Breimans hjemmeside Arkiveret 22. juni 2008.  (engelsk)  (dato for adgang: 7. juni 2009)
  3. ↑ En beskrivelse af træbygningsproceduren brugt i Apache Mahout Arkiveret 13. maj 2012 på Wayback Machine  ( Åbnet  7. juni 2009)
  4. ↑ Deng, H.; Runger, G.; Tuv, E. (2011). Bias af vigtige mål for attributter og løsninger med flere værdier . Proceedings of the 21st International Conference on Artificial Neurale Networks (ICANN). pp. 293-300.
  5. ↑ Altmann A., Tolosi L., Sander O., Lengauer T. Permutation important:a corrected feature important measure  (engelsk)  // Bioinformatics : journal. - 2010. - doi : 10.1093/bioinformatics/btq134 .
  6. ↑ Tolosi L., Lengauer T. Klassifikation med korrelerede funktioner: upålidelighed af funktionsrangering og løsninger.  (engelsk)  // Bioinformatik: tidsskrift. - 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. december ( bind 228 ). - S. 308-320 . - doi : 10.1007/978-3-319-26762-3_27 .
  8. ↑ Lewoniewski W., Węcel K., Abramowicz W. Kvalitet og betydning af Wikipedia-artikler på forskellige sprog  //  Informations- og softwareteknologier. ICIST 2016. Communications in Computer and Information Science: tidsskrift. - 2016. - 22. september ( bind 639 ). - s. 613-624 . - doi : 10.1007/978-3-319-46254-7_50 .
  9. ↑ Warncke-Wang M., Cosley D., Riedl J. Fortæl mig mere: En brugbar kvalitetsmodel for wikipedia  //  WikiSym '13 Proceedings of the 9th International Symposium on Open Collaboration : journal. - 2013. - doi : 10.1145/2491055.2491063 .

Litteratur

Links

Implementeringer