Aprenentatge basat en arbres de decisió

L'aprenentatge basat en arbres de decisió és un mètode de modelatge predictiu utilitzat en l'estadística, la mineria de dades i l'aprenentatge automàtic. Consisteix en la selecció automàtica d'un arbre de decisió (com a model predictiu), que utilitza observacions de les variables independents (representades a les branques) per a deduir el valor de la variable dependent (representada en les fulles). Els arbres de decisió on la variable dependent és discreta s'anomenen arbres de classificació. En aquestes estructures, les fulles representen etiquetes de classe i les branques representen conjuncions de característiques que dirigeixen a les etiquetes corresponents. Els arbres de decisió on la variable dependent és contínua (típicament números reals) s'anomenen arbres de regressió. Els arbres de decisió són un dels models més populars en aprenentatge automàtic, gràcies a la seva intel·ligibilitat i simplicitat.

Dins l'anàlisi de decisió, un arbre de decisió pot ser utilitzat per representar processos de decisió de forma visual i explícita. En la mineria de dades, un arbre de decisió descriu les dades (però l'arbre de classificació resultant pot ser utilitzat per a la presa de decisions). Aquesta pàgina tracta arbres de decisió en el context de la mineria de dades.

General

Un arbre que mostra la supervivència de passatgers en el Titànic ("sibsp" és el número de cònjuges o germans a bord, de l'anglès "siblings and spouses"). Les figures sota les fulles mostren la probabilitat de supervivència i el percentatge d'observacions en la fulla. En resum: Les vostres possibilitats de supervivència eren bones si eres (i) una dona o (ii) un home menor de 9.5 anys amb estrictament menys de 3 germans.

L'aprenentatge basat en arbres de decisió és un mètode habitual en la mineria de dades. L'objectiu és crear un model que prediu el valor d'una variable dependent $y\in Y$ basada en diverses variables independents $x=(x_{1},\ldots x_{n})\in X$.

Un arbre de decisió és una representació senzilla per classificar exemples. Consisteix en un arbre on cada node intern (incloent l'arrel) és etiquetat amb una variable independent $x_{i}$, i les arestes que surten del node són etiquetades amb els diferents valors que aquesta variable pot prendre. El procés de decisió consisteix en començar a l'arrel i, basant-nos en el valor de les variables independents, anar prenent la branca corresponent. Per exemple, en la probabilitat de supervivència de passatgers del Titanic (vegeu la figura), el factor més important era el gènere del passatger, així que podem etiquetar l'arrel "gènere", amb dues arestes "home" i "dona". Si volem saber la probabilitat de supervivència d'un passatger concret, seguim la branca corresponent. Les fulles de l'arbre contenen el valor estimat de la variable independent. Seguint amb l'exemple, l'aresta "dona" correspon a una fulla, que indica una probabilitat de supervivència del 73%, mentre que si seguim l'aresta "home" l'arbre continua, amb un node etiquetat "edat", i arestes per a menors de 9.5 anys i majors de 9.5 anys, respectivament.

Típicament, l'arbre es construeix començant per l'arrel, on considerem el conjunt $X$ format per totes les variables independents. Basats en un seguit de regles (per exemple, comparant quin és el tall que obté el màxim poder predictiu, de tots els possibles), s'escull una variable independent i un criteri de subdivisió, obtenint el primer node de l'arbre i el primer conjunt d'arestes. Això subdivideix el conjunt original en dos o més subconjunts, cada un associat a una aresta. Aquest procés de subdivisió es repeteix per a cada subconjunt de forma recursiva, fins que tots els elements d'un subconjunt prenen el mateix valor, o es compleix algun altre criteri de parada (per exemple, una profunditat màxima de l'arbre o una variancia mínima de la variable dependent). Aquest procés és un exemple d'un algorisme voraç.

Tipus d'arbres de decisió

Un arbre que calcula la probabilitat de cifosi després d'una cirurgia espinal, donada l'edat del pacient i la vèrtebra en que l'operació es va iniciar. El mateix arbre és mostrat de tres formes diferents. Esquerra: Les fulles (en color) mostren la probabilitat de cifosi després de cirurgia espinal, i el percentatge de pacients en la fulla. Mig: Representació de l'arbre en perspectiva. Dreta: Vista aèrea. La probabilitat de cifosi després que la cirurgia és més alta en les àrees més fosques.

Els arbres de decisió utilitzats en minatge de dades es divideixen en dues categories:

• Arbre de classificació, si la variable dependent pren un nombre finit de valors (anomenants categories).
• Arbre de regressió, si la variable dependent pren valors continuus (típicament, nombres reals).

Ambdós mètodes s'agrupen sota el nom Arbres de Classificació i Regressió (CART, per les sigles angleses), introduït per Breiman et al. l'any 1984. Malgrat les similituds, hi ha diferències importants, com el procediment utilitzat per subdividir l'arbre.

Els arbres de decisió sovint s'utilitzen en mètodes de conjunt, on es creen varis arbres:

• "Boosted trees" consisteix en construir un conjunt d'arbres de forma seqüencial, posant èmfasi a cada pas en els exemples que han estat classificats erròniament en els passos anteriors. Un exemple típic és AdaBoost.
• "Bootstrap aggregated decision trees" construeix un conjunt d'arbres en paral·lel, entrenant cada un amb una mostra amb repetició de les dades d'entrenament, en comptes d'entrenar-los directament amb les dades originals. El resultat final s'obté per consens (resultat més votat).
• Bosc de rotació – on cada arbre de decisió és entrenat en un subconjunt aleatòri de les variables independents, a les que s'ha aplicat anàlisi de component principal (PCA).