Random forest

Random forest (o random forests) també coneguts en castellà com a '"Boscos Aleatoris"' és una combinació d'arbres predictors en el qual cada arbre depèn dels valors d'un vector aleatori provat independentment i amb la mateixa distribució per a cadascun d'aquests. És una modificació substancial de bagging que construeix una llarga col·lecció d'arbres no correlacionats fent una mitjana de tots els seus valors.[1][2]

L'algorisme per induir un random forest va ser desenvolupat per Leo Breiman[3] i Adele Cutler i Random forests és la seva marca de fàbrica. El terme apareix en la primera proposta de Random decision forests, formulada per Tin Kam Ho de Bell Labs el 1995. El mètode combina la idea de bagging de Breiman i la selecció aleatòria d'atributs, introduïda independentment per Ho, Amit i Geman, per construir una col·lecció d'arbres de decisió amb variació controlada.[4][5]

La selecció d'un subconjunt aleatori d'atributs és un exemple del mètode random subspace, el que, segons la formulació de Ho, és una manera de dur a terme la discriminació estocàstica proposada per Eugenio Kleinberg.[6]

En molts problemes el rendiment de l'algorisme random forest és molt similar a la del boosting, i és més simple d'entrenar i ajustar. Com a conseqüència, el Random forest és popular i àmpliament utilitzat per milions de programadors i enginyers en la programació d'aprenentage automàtic.

Definició de Random forestsModifica

La idea essencial del bagging és fer una mitjana de molts models sorollosos però aproximadament imparcials, i per tant reduir la variació. Els arbres són els candidats ideals pel bagging, atès que ells poden registrar estructures d'interacció complexa en les dades, i si creixen suficientment profund, tenen relativament baixa parcialitat.

Cada arbre és construït usant el següent algorisme:

  1. Sigui N el nombre de casos de prova, M és el nombre de variables en el classificador.
  2. Sigui m el nombre de variables d'entrada a ser usat per determinar la decisió en un node donat; m ha de ser molt menor que M
  3. Triar un conjunt d'entrenament per a aquest arbre i usar la resta dels casos de prova per estimar l'error.
  4. Per a cada node de l'arbre, triar aleatòriament m variables en les quals basar la decisió. Calcular la millor partició del conjunt d'entrenament a partir de les m variables.

Per a la predicció d'un nou cas, és empès cap avall per l'arbre. Després se li assigna l'etiqueta del node terminal on acaba. Aquest procés és iterat per tots els arbres en l'assemblat, i l'etiqueta que obtingui la major quantitat d'incidències és reportada com la predicció.

Característiques i avantatgesModifica

Els avantatges del random forests són:[7]

  • Ser un dels algorismes d'aprenentatge més precisos que hi ha disponible. Per a un set de dades prou gran produeix un classificador molt precís.
  • Córrer eficientment en bases de dades grans.
  • Manejar centenars de variables d'entrada sense excloure cap.
  • Donar estimacions de quines variables són importants en la classificació.[1][2]
  • Tenir un mètode eficaç per estimar dades perdudes i mantenir l'exactitud quan una gran proporció de les dades està perduda.
  • Computar els prototips que donen informació sobre la relació entre les variables i la classificació.
  • Computar les proximitats entre els parells de casos que poden usar-se en els grups, localitzant valors atípics, o (ascendint) donant vistes interessants de les dades.
  • Oferir un mètode experimental per detectar les interaccions de les variables.

DesavantatgesModifica

  • S'ha observat que els algorismes de Random forests sobreajusten en certs grups de dades amb tasques de classificació/regressió sorolloses.[8]
  • A diferència dels arbres de decisió, la classificació feta per random forests és difícil d'interpretar.[9]
  • Per a les dades que inclouen variables categòriques amb diferent nombre de nivells, el random forests es parcialitza a favor d'aquests atributs amb més nivells. Per tant, la posició que marca la variable no és fiable per a aquest tipus de dades. Mètodes com les permutacions parcials s'han usat per resoldre el problema[10]
  • Si les dades contenen grups d'atributs correlacionats amb similar rellevància per al rendiment, llavors els grups més petits estan afavorits sobre els grups més grans.[11]

VisualitzacióModifica

 
Dades d'entrenament.
 
Visualització de Random Forest després de l'entrenament.
 
Model de regressió logística després d'entrenament.

Per formar una visualització intuïtiva de l'espai-model representat per un random forests, es va crear un set de dades que consisteix en 200 punts aleatoris (100 punts verds i 100 punts vermells). Els punts verds eren obtinguts a partir d'una distribució Gaussiana amb un centroide en (0,1), i els punts vermells eren obtinguts d'una distribució de Gaussiana amb un centroide en (1,0). En tots dos casos, la variació era circular amb un radi mitjà d'1.

El model del random forest, consistent de 50 arbres entrenats usant aquestes dades. La puresa del color indica la porció dels 50 arbres que van votar d'acord. Un over-fit (sobre ajust) significatiu pot ser observat en la visualització de Random Forest després de l'entrenament.

En contrast, es presenta la visualització d'un model de regressió logístic (menys propens al sobre ajustament), que també va ser entrenat usant aquestes mateixes dades.

Vegeu tambéModifica

ReferènciesModifica

  1. 1,0 1,1 Piryonesi, S. Madeh; El-Diraby, Tamer E. «Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems» (en anglès). Journal of Transportation Engineering, Part B: Pavements, 146, 2, 2020-06, pàg. 04020022. DOI: 10.1061/JPEODX.0000175. ISSN: 2573-5438 [Consulta: 7 agost 2020].
  2. 2,0 2,1 Hastie, Trevor.; Friedman, J. H. (Jerome H.). The elements of statistical learning : data mining, inference, and prediction : with 200 full-color illustrations. Springer, 2001. ISBN 0-387-95284-5. OCLC 46809224. 
  3. Breiman, Leo «Random Forests». Machine Learning, 45, 1, 2001, pàg. 5–32. DOI: 10.1023/A:1010933404324.
  4. Ho, Tin Kam «The Random Subspace Method for Constructing Decision Forests». IEEE Transactions on Pattern Analysis and Machine Intelligence, 20, 8, 1998, pàg. 832–844. DOI: 10.1109/34.709601.
  5. Amit, Yali; Geman, Donald «Shape quantization and recognition with randomized trees». Neural Computation, 9, 7, 1997, pàg. 1545–1588. DOI: 10.1162/neco.1997.9.7.1545. Arxivat 2018-02-05 a Wayback Machine.
  6. Kleinberg, Eugene «An Overtraining-Resistant Stochastic Modeling Method for Pattern Recognition». Annals of Statistics, 24, 6, 1996, pàg. 2319–2349. DOI: 10.1214/aos/1032181157. Arxivat 2011-07-19 a Wayback Machine.
  7. [1]
  8. Segal, Mark R. Machine Learning Benchmarks and Random Forest Regression. Center for Bioinformatics & Molecular Biostatistics, abril 14 de 2004. 
  9. Berthold, Michael R. Guide to Intelligent Data Analysis. Springer London, 2010. 
  10. Altmann A, Tolosi L, Sander O, Lengauer T «Permutation importance:a corrected feature importance measure». Bioinformatics, 2010. DOI: 10.1093/bioinformatics/btq134.
  11. Tolosi L, Lengauer T «Classification with correlated features: unreliability of feature ranking and solutions.». Bioinformatics, 2011. DOI: 10.1093/bioinformatics/btr300.

Implementació ComercialModifica

  • [2] Random Forests.

Implementacions Open sourceModifica