Arbres de decisió

• Introducció
• Què és un arbre de decisió?
  • Funcionament
• Diversos arbres possibles
• Construcció d’un arbre de decisió
  • Pas 1. Escollir la característica de l’arrel
  • Pas 2. Dividir el subarbre esquerre
  • Pas 3. Dividir el subarbre dret
  • Decisions clau en l’aprenentatge d’arbres de decisió
    • 1. Quina característica escollir en cada node?
    • 2. Quan aturar la divisió?
  • Reflexió final
• Entropia i puresa
  • Definició intuïtiva
  • Exemples addicionals
  • Fórmula general de l’entropia
  • Criteri de Gini
• Divisió d’un node
  • Exemple: reconèixer gats vs. no gats
  • Comparació de splits
  • Notació
  • Procés de construcció
• Algorisme de l’arbre de decisió
  • Paràmetres i intuïcions
  • Predicció amb l’arbre
• Codificació *One-Hot
  • Característica amb tres valors
  • Implementació *One-Hot
  • Aplicació a altres models
• Característiques contínues
  • Criteri de divisió
  • Exemple pas a pas
    • Prova amb llindar t=8
    • Prova amb llindar t=9
    • Prova amb llindar t=13
  • Estratègia general
  • Conclusió
• Arbres de decisió per a regressió
  • Exemple introductori
  • Fulles d’un arbre de regressió
  • Com escollir els talls (splits)
  • Reducció de variància
  • Procés complet de construcció
• Conjunts d’arbres de decisió (Tree Ensembles)
  • Exemple intuïtiu
  • Avantatge d’un ensemble d’arbres
  • Exemple de votació
  • Intuïció
  • Mostreig amb reposició
    • Demostració amb fitxes de colors
    • Aplicació al Tree Ensemble
  • Algorisme Random Forest
    • Generació d’un conjunt d’arbres
    • Predicció amb l’ensemble
    • Millora: Random Forest
  • Algorisme XGBoost
    • Com funciona XGBoost
• Ús de Xarxes Neuronals i Arbres de Decisions
  • Arbres de decisions i conjunts d’arbres
  • Xarxes neuronals

Introducció

Per entendre com funcionen els arbres de decisió, farem servir un exemple senzill:
Suposeu que gestioneu un centre d’adopció de gats i que, donades algunes característiques d’un animal, voleu entrenar un classificador que decideixi ràpidament si es tracta d’un gat o no.

Disposem de 10 exemples d’entrenament. Per a cada animal tenim les característiques següents:

• Forma de les orelles (punxegudes o caigudes)
• Forma de la cara (rodona o no rodona)
• Bigotis (present o absent)
• Etiqueta: és gat (1) o no és gat (0)

Exemple:

• El primer animal té orelles punxegudes, cara rodona, bigotis presents → és un gat.
• El segon té orelles caigudes, cara no rodona, bigotis presents → també és un gat.
• I així successivament fins a completar els 10 exemples (5 gats i 5 gossos).

Formalment:

• Les entrades X són les tres columnes de característiques.
• La sortida Y és la columna final que indica si és gat o no.

Com que Y∈0,1, es tracta d’un problema de classificació binària.
En aquest exemple, cada característica X1,X2,X3 només pot prendre dos valors possibles (categòrics). Més endavant veurem com treballar amb característiques multivaluades o fins i tot contínues.

Què és un arbre de decisió?

Un arbre de decisió és un model que, després d’entrenar-se amb dades, pren la forma d’una estructura jeràrquica anomenada arbre.

• Cada oval dins l’arbre és un node de decisió.
• El node arrel (a dalt de tot) és el punt de partida per classificar qualsevol exemple.
• Les fulles (caixes rectangulars a baix) representen les prediccions finals.

Funcionament

Si entra un nou exemple (p. ex., animal amb orelles punxegudes, cara rodona i bigotis presents), el procés és:

1. Comencem al node arrel, que pot preguntar: “Quina és la forma de les orelles?”.
2. Segons la resposta (punxegudes/caigudes), anem cap a l’esquerra o cap a la dreta.
3. Al següent node, potser es pregunta: “La cara és rodona?”.
4. Continuem baixant per l’arbre fins arribar a una fulla, que dona la predicció: “És un gat”.

👉 Encara que sembli estrany que les “arrels” siguin a dalt i les “fulles” a baix, penseu-ho com una planta penjant d’interior.

Diversos arbres possibles

Un mateix conjunt de dades pot donar lloc a molts arbres diferents.
Per exemple, podem tenir:

• Un arbre que primer mira les orelles i després els bigotis.
• Un altre que primer mira la cara i després les orelles.
• Altres variants amb criteris diferents.

Cadascun d’aquests arbres pot tenir un rendiment millor o pitjor sobre el conjunt d’entrenament, validació o test. La tasca de l’algoritme d’aprenentatge és trobar, entre tots els arbres possibles, un que generalitzi bé: és a dir, que tingui bon rendiment no només amb les dades vistes, sinó també amb noves dades.

Resumint:

• Els arbres de decisió permeten classificar exemples a partir d’un procés seqüencial de preguntes sobre les característiques.
• Cada node representa una decisió basada en una característica.
• Cada fulla representa una predicció final.
• Podem construir molts arbres diferents amb el mateix conjunt de dades; el repte és trobar-ne un que funcioni bé en general.

Construcció d’un arbre de decisió

El procés de construir un arbre de decisió a partir d’un conjunt d’entrenament es pot entendre en diversos passos. Vegem-ne el funcionament amb un exemple senzill de 10 mostres de gats i gossos.

En el següent arbre s’ha afegit el nombre d’animals que coincideixen amb el criteri de decisió (entre parèntesis):

Pas 1. Escollir la característica de l’arrel

El primer pas és decidir quina característica utilitzarem al node arrel (el node superior de l’arbre).

Mitjançant un algoritme (que veurem més endavant), suposem que escollim la forma de les orelles.

• Els 5 exemples amb orelles punxegudes van al subarbre esquerre.
• Els 5 exemples amb orelles caigudes van al subarbre dret.

Pas 2. Dividir el subarbre esquerre

Ara ens fixem només en les 5 mostres amb orelles punxegudes. Hem de decidir una nova característica per dividir.

Imaginem que escollim la forma de la cara.

• 4 mostres tenen cara rodona → baixen a l’esquerra.
• 1 mostra té cara no rodona → baixa a la dreta.

Com que les 4 mostres amb cara rodona són totes gats, aquest node es converteix en un node fulla que preveu “gat”.

El node de la dreta conté un gos (100%), així que també es crea un node fulla que preveu “no gat”.

Pas 3. Dividir el subarbre dret

Passem al subarbre dret (les 5 mostres amb orelles caigudes). Aquí hi ha 1 gat i 4 gossos.

Suposem que escollim la característica bigotis.

• Si hi ha bigotis → queda 1 gat (100%).
• Si no hi ha bigotis → queden 4 gossos (100%).

Tots dos nodes són purs (conté només una classe), de manera que es converteixen en fulles: “gat” i “no gat”.

Decisions clau en l’aprenentatge d’arbres de decisió

Durant el procés hem de prendre diverses decisions importants:

1. Quina característica escollir en cada node?

En cada node amb una barreja de gats i gossos, l’algoritme ha de decidir quina característica és millor per dividir:

• forma de les orelles,
• forma de la cara,
• bigotis, etc.

La idea és maximitzar la puresa de les divisions.

Per exemple, si tinguéssim la característica fictícia “té ADN de gat”, dividir per ella produiria subconjunts totalment purs (100% gats a l’esquerra i 0% gats a la dreta).

En general, triem la característica que produeix subconjunts més homogenis.

2. Quan aturar la divisió?

No podem dividir indefinidament. Els criteris típics per aturar la divisió són:

• Puresa total: si un node conté només una classe (100% gats o 100% gossos), es crea una fulla.
• Profunditat màxima: limitem l’arbre a una profunditat determinada.
  • La profunditat d’un node és el nombre de salts des de l’arrel.
  • Exemple: si imposem una profunditat màxima de 2, cap node pot arribar a profunditat 3.
• Mida mínima del node: si un node té molt poques mostres (p. ex. només 3), es prefereix no dividir més.
• Guany de puresa insuficient: si la millora en puresa (o reducció d’impuresa) és molt petita, no val la pena dividir.

Aquests criteris ajuden a reduir el risc de sobreajustament i a mantenir l’arbre manejable.

Reflexió final

Els arbres de decisió poden semblar complicats perquè, amb els anys, molts investigadors han anat afegint refinaments:

• nous criteris de divisió,
• límits de profunditat,
• criteris de parada alternatius, etc.

Però, en essència, només hi ha dues preguntes clau:

1. Quina característica faig servir per dividir?
2. Quan em paro de dividir?

Amb aquestes regles, més una bona mesura de puresa (com l’entropia), podem construir arbres de decisió efectius.

Entropia i puresa

A continuació veurem una manera de mesurar la puresa d’un conjunt d’exemples.

• Si tots els exemples són de la mateixa classe (per exemple, tots gats), aleshores el conjunt és molt pur.
• Si tots els exemples són de la classe contrària (per exemple, tots no gats o gossos), també és molt pur.
• Però, què passa quan hi ha una barreja? Com quantifiquem la puresa d’un conjunt?

Per fer-ho, introduïm el concepte d’entropia, una mesura de la impuresa d’un conjunt de dades.

Definició intuïtiva

Suposem un conjunt de 6 exemples amb 3 gats i 3 gossos.

Definim:

p1=fracció d’exemples que són gats (classe 1)

En aquest cas:

p1=36=0.5

La funció d’entropia es denota habitualment com:

On:

• L’eix horitzontal representa p1 (la fracció de gats).
• L’eix vertical mostra el valor de l’entropia.

En aquest exemple (p1=0.5), obtenim:

H(0.5)=1

El valor màxim d’impuresa.
Això té sentit, perquè un conjunt 50%-50% és el més desordenat possible.

En canvi:

• Si tots els exemples són gats (p1=1) o tots no gats (p1=0), aleshores:

H(0)=H(1)=0

El conjunt és completament pur.

Exemples addicionals

• 5 gats i 1 gos:
  p1=56≈0.83,H(p1)≈0.65

• 6 gats:
  p1=1,H(1)=0

• 2 gats i 4 gossos:
  p1=26=0.33,H(p1)≈0.92

• 0 gats i 6 gossos:
  p1=0,H(0)=0

Fórmula general de l’entropia

Recordem:

p1=fracció de gats,p0=1−p1=fracció de no gats

L’entropia es defineix com:

H(p1)=−p1log2(p1)−p0log2(p0)

O equivalentment:

H(p1)=−p1log2(p1)−(1−p1)log2(1−p1)

• Es fa servir el logaritme en base 2 per tal que el valor màxim sigui exactament 1.

• Si p1=0 o p0=0, per convenció definim: 0log(0)=0

  així el càlcul és consistent.

• L’entropia s’assembla a la funció de pèrdua logística, i hi ha una justificació matemàtica darrere d’aquesta similitud (tot i que no ens hi endinsarem en aquest curs).

• El punt clau és que l’entropia mesura el desordre del conjunt:

  • 0 = pur (tots de la mateixa classe).
  • 1 = màxim d’impuresa (50%-50%).

Existeixen altres funcions similars a l’entropia, com el criteri de Gini.

Criteri de Gini

El criteri de Gini (o impuresa de Gini) és una alternativa popular a l’entropia per mesurar la impuresa d’un conjunt de dades. La fórmula de Gini és:

Gini(p1)=p1(1−p1)+p0(1−p0)=2p1(1−p1)

on p1 és la fracció d’exemples de la classe positiva (gats) i p0=1−p1 és la fracció de la classe negativa (gossos).

Comparació entre Gini i Entropia:

Exemples numèrics:

• Conjunt 50%-50% (p1=0.5):

  • Gini: 2×0.5×0.5=0.5
  • Entropia: −0.5log2(0.5)−0.5log2(0.5)=1.0

• Conjunt 83%-17% (p1=5/6≈0.83):

  • Gini: 2×0.83×0.17≈0.28
  • Entropia: −0.83log2(0.83)−0.17log2(0.17)≈0.65

• Conjunt pur (p1=1 o p1=0):

  • Gini: 0
  • Entropia: 0

Principals diferències:

1. Eficiència computacional: Gini és més ràpid de calcular perquè no usa logaritmes.
2. Escala: L’entropia oscil·la entre 0 i 1, mentre que Gini oscil·la entre 0 i 0.5.
3. Sensibilitat: L’entropia penalitza més les divisions desbalancejades que Gini, ja que és més “curva” al voltant de p1=0.5.
4. Ús pràctic: En la majoria d’aplicacions, ambdues mesures donen resultats similars. Gini és més comú en CART (Classification and Regression Trees), mentre que l’entropia s’usa més sovint en ID3 i C4.5.

En resum, tant Gini com entropia mesuren el mateix concepte (impuresa), però amb escales i càlculs lleugerament diferents. A la pràctica, la diferència de rendiment entre usar un o l’altre sol ser petita.

Divisió d’un node

Quan construïm un arbre de decisió, la manera de decidir quina característica utilitzar per dividir un node es basa en quina elecció de característica redueix més l’entropia. També es pot veure com reduir la impuresa o maximitzar la puresa.

En l’aprenentatge amb arbres de decisió, la reducció d’entropia es coneix com a guany d’informació (information gain).

En aquest apartat veurem com calcular el guany d’informació i, per tant, com triar quines característiques usar per dividir cada node de l’arbre.

Exemple: reconèixer gats vs. no gats

Suposem que volem decidir quina característica usar al node arrel de l’arbre que estem construint.

Aplicarem la fórmula d’entropia:

H(P)=−P1log2P1−P0log2P0

1. Forma de l’orella

   Si dividim per la característica forma de l’orella, tindríem:

   • Esquerra: 5 exemples, 4 són gats → P1=4/5
   • Dreta: 5 exemples, 1 és gat → P1=1/5

   Entropies:

   H(4/5)≈0.72,H(1/5)≈0.72

2. Forma de la cara

   Si dividim per forma de la cara:

   • Esquerra: 7 exemples, 4 gats → P1=4/7
   • Dreta: 3 exemples, 1 gat → P1=1/3

   Entropies:

   H(4/7)≈0.99,H(1/3)≈0.92

   La impuresa sembla molt més alta comparada amb la divisió per forma de l’orella.

3. Bigotis

   Dividint per la característica bigotis:

   • Esquerra: P1=3/4
   • Dreta: P1=2/6

   Entropies:

   H(3/4)≈0.81,H(2/6)≈0.92

Comparació de splits

En lloc de comparar només els valors d’entropia, és útil fer una mitjana ponderada, ja que:

• Un node amb molts exemples i alta entropia és pitjor que un node amb pocs exemples i alta entropia.
• La mitjana ponderada combina la importància segons la quantitat d’exemples en cada subnode.

Càlcul de la mitjana ponderada:

Si wleft és la fracció d’exemples a l’esquerra i wright a la dreta, llavors:

Hponderada=wleftH(Pleft1)+wrightH(Pright1)

Exemples:

• Forma d’orella: 5/10⋅H(0.8)+5/10⋅H(0.2)
• Forma de cara: 7/10⋅H(0.57)+3/10⋅H(0.33)
• Bigotis: 4/10⋅H(0.75)+6/10⋅H(0.33)

I triaríem el split amb l’entropia ponderada més baixa. Però per seguir la convenció dels arbres de decisió, calculem la reducció d’entropia respecte al node original, no només l’entropia ponderada:

IG=H(Proot)−(wleftH(Pleft1)+wrightH(Pright1))

• Node arrel: Proot1=5/10=0.5 → H(Proot)=1
• Forma d’orella: IG=0.28
• Forma de cara: IG=0.03
• Bigotis: IG=0.12

El guany d’informació mesura la reducció d’entropia obtinguda amb la divisió. Triem la característica amb el guany més gran.

Nota: Aquesta mesura també s’utilitza com a criteri d’aturada. Si el guany és molt petit, no té sentit continuar dividint, ja que només augmentaríem la mida de l’arbre i el risc d’overfitting.

Notació

Per a qualsevol node:

• wleft i wright són les fraccions d’exemples que van a cada subnode.
• Pleft1 i Pright1 són les fraccions d’exemples positius a cada subnode.
• Proot1 és la fracció d’exemples positius al node arrel.

Fórmula general del guany d’informació:

IG=H(Proot1)−(wleftH(Pleft1)+wrightH(Pright1))

Amb això, podem calcular el guany d’informació per qualsevol característica i escollir la que maximitza la puresa dels subnodes.

Procés de construcció

1. Per a cada node, calcular el guany d’informació de totes les característiques possibles.
2. Escollir la característica amb el guany més alt.
3. Dividir el node segons aquesta característica.
4. Repetir el procés per als subnodes fins que es compleixi algun criteri d’aturada (p. ex., guany molt baix, node pur o nombre mínim d’exemples).

D’aquesta manera construïm un arbre de decisió que maximitza la puresa dels subnodes i redueix l’entropia global.

Algorisme de l’arbre de decisió

El criteri de guany d’informació ens permet decidir quina característica escollir per dividir un node.

Aquest concepte s’aplica repetidament per construir un arbre de decisió complet amb múltiples nodes. A continuació es mostra el procés global de construcció d’un arbre de decisió:

1. Comencem amb tots els exemples d’entrenament al node arrel.
2. Calculem el guany d’informació per totes les característiques possibles i escollim aquell que maximitza el guany d’informació.
3. Un cop escollit la característica, dividim el conjunt de dades en dos subconjunts segons el valor de la característica i creem les branques esquerra i dreta de l’arbre.
4. Els exemples d’entrenament s’envien a la branca corresponent segons el valor de la característica.

Això crea la primera divisió al node arrel. Després, repetim el procés de divisió a les branques esquerra i dreta, i així successivament, fins que es compleixi algun dels criteris d’aturada:

• El node conté només exemples d’una classe (entropia H=0).
• La divisió del node faria que l’arbre excedís la profunditat màxima establerta.
• El guany d’informació d’una nova divisió és menor que un llindar mínim.
• El nombre d’exemples en el node és inferior a un llindar mínim.

Repetim el procés fins que es compleixi un o més d’aquests criteris.

Exemple pràctic: suposem que tenim un conjunt d’exemples amb tres característiques: orella, bigotis i forma_cara.

1. Tots els exemples comencen al node arrel.
2. Calculant el guany d’informació per cada característica, decidim que forma d’orella és la característica que millor divideix els exemples.
3. Creem branques esquerra i dreta segons orella = punxeguda o orella = caiguda.
4. Ens fixem en la sub-branca esquerra, que té 5 exemples.
5. El criteri de divisió indica que hem de continuar fins que tots els exemples del node pertanyin a una única classe.
6. Calculant el guany d’informació per cada característica restant, trobem que forma_cara té el guany més alt. Dividim aquesta branca segons forma_cara.

• Branca esquerra: tots els exemples són gats → creem un node fulla que prediu gat.
• Branca dreta: tots els exemples són gossos → creem un node fulla que prediu no gat.

El mateix procés s’aplica a la sub-branca dreta del node arrel amb els seus 5 exemples, triant la característica que maximitza el guany d’informació (bigotis en aquest cas), i creant els nodes fulla corresponents.

El procés mostra un algorisme recursiu:

Per construir l’arbre de decisió complet, construïm sub-arbres més petits per a les branques esquerra i dreta, i després els combinem.

Paràmetres i intuïcions

• Profunditat màxima: com més gran, més complex serà l’arbre, similar a entrenar un polinomi d’alt grau o una xarxa neuronal gran. Permet aprendre funcions més complexes, però augmenta el risc de sobreajustament.
• Guany d’informació mínim: si una nova divisió aporta poc guany d’informació, podem parar.
• Nombre mínim d’exemples per node: evita crear nodes fulla amb massa pocs exemples.

En la pràctica, moltes biblioteques open-source proporcionen valors per defecte raonables, i fins i tot mètodes automàtics per triar aquests paràmetres.

Predicció amb l’arbre

Per fer una predicció:

1. Prenem un nou exemple.
2. Comencem al node arrel i seguim les decisions de les branques.
3. Quan arribem a un node fulla, obtenim la predicció final.

Codificació One-Hot

En l’exemple que hem vist fins ara, cadascuna de les característiques (features) només podia prendre dos possibles valors.
Per exemple:

• La forma de les orelles era punxeguda o caiguda.
• La forma de la cara era rodona o no rodona.
• Els bigotis podien estar presents o absents.

Però, què passa quan tenim característiques que poden prendre més de dos valors discrets?
En aquest cas, podem utilitzar una tècnica anomenada one-hot encoding.

Característica amb tres valors

Suposem que al nostre conjunt d’entrenament per a l’aplicació del centre d’adopció d’animals, la característica de la forma de les orelles ja no té només dues opcions (punxeguda i caiguda), sinó que pot ser també ovalada.

Així doncs, aquesta característica continua sent categòrica, però ara pot prendre tres valors possibles.

Si féssim servir directament aquest atribut per construir un arbre de decisió, quan dividíssim el conjunt de dades segons la forma de les orelles, acabaríem generant tres subconjunts i, per tant, tres branques.

Però hi ha una manera diferent i més flexible de representar aquests valors: la codificació one-hot.

Implementació One-Hot

En lloc d’utilitzar una sola característica “forma d’orelles” amb tres possibles valors, crearem tres noves característiques binàries:

• Té orelles punxegudes?
• Té orelles caigudes?
• Té orelles ovalades?

Cada nova característica només pot prendre els valors 0 o 1.

Per exemple:

• Si abans dèiem “aquest animal té orelles punxegudes”, ara direm:
  • punxegudes = 1, caigudes = 0, ovalades = 0.
• Si té orelles ovalades:
  • punxegudes = 0, caigudes = 0, ovalades = 1.

En general, si una característica categòrica pot prendre k valors possibles, la substituirem per k característiques binàries.

xcategòric∈v1,v2,…,vk⇒x1,x2,…,xk,xi∈0,1

on exactament un dels xi val 1, i els altres valen 0.

Aquesta representació és la que rep el nom de one-hot encoding, perquè exactament una característica està “enfocada” (hot) amb el valor 1.

Amb aquesta transformació:

• Tornem al cas original on cada característica és binària (només 0 o 1).
• L’algorisme de construcció d’arbres de decisió pot aplicar-se sense cap modificació.

Però no només això: la tècnica és útil més enllà dels arbres de decisió.

Aplicació a altres models

Podem utilitzar el one-hot encoding per preparar dades d’entrada a altres models d’aprenentatge automàtic, com ara:

• Regressió logística
• Xarxes neuronals
• Regressió lineal

Per exemple:

• La característica “forma de cara” amb dos valors (rodona / no rodona) es pot codificar com:
  • rodona = 1
  • no rodona = 0
• La presència de bigotis:
  • present = 1
  • absent = 0

En el nostre cas, tenim:

• 3 característiques provinents de la forma de les orelles (punxegudes, caigudes, ovalades).
• 1 característica de la forma de la cara.
• 1 característica de la presència de bigotis.

En total, obtenim 5 característiques binàries, que poden alimentar perfectament una xarxa neuronal o una regressió logística per entrenar un classificador de gats.

Resumint:

• El one-hot encoding converteix una característica categòrica amb k valors possibles en k característiques binàries.
• És una representació universal que permet utilitzar aquestes dades amb arbres de decisió, regressió logística, xarxes neuronals, etc.
• És especialment útil perquè molts models només poden treballar amb valors numèrics.

Característiques contínues

Fins ara hem vist arbres de decisió que treballen amb característiques discretes, com ara forma de les orelles, forma de la cara o bigotis. Però, què passa si tenim una característica contínua, és a dir, que pot prendre qualsevol valor numèric?

Per entendre-ho, considerem un exemple: l’adopció de gats i gossos. Afegim una nova característica: el pes de l’animal (en lliures). De mitjana, els gats solen ser més lleugers que els gossos, tot i que alguns gats poden ser més pesats que alguns gossos. Així doncs, el pes és una característica útil per decidir si un animal és un gat o no.

Criteri de divisió

L’algoritme d’aprenentatge dels arbres de decisió funciona igual que abans: busca la partició que maximitza el guany d’informació. Ara, però, a més de les característiques discretes, també ha de considerar el pes.

La pregunta clau és: com dividir segons una característica contínua?

La idea és provar llindars (thresholds). Per exemple, dividir segons si

pes≤t

per a algun valor t. L’algoritme provarà diversos valors de t i escollirà el que maximitzi el guany d’informació.

Exemple pas a pas

Imaginem que tenim 10 animals, alguns gats i alguns gossos, representats en un gràfic:

Prova amb llindar t=8

Dividim entre animals amb pes ≤ 8 i pes > 8.

• A l’esquerra: 2 gats.
• A la dreta: 3 gats i 5 gossos.

El guany d’informació és:

IG=H(0.5)−(210H(1)+810H(38))≈0.24

on

H(p)=−plog2(p)−(1−p)log2(1−p)

és l’entropia.

Prova amb llindar t=9

• A l’esquerra: 4 gats.
• A la dreta: 1 gat i 5 gossos.

El guany d’informació és:

IG=H(0.5)−(410H(1)+610H(16))≈0.61

Aquest valor és molt millor que el 0.24 anterior.

Prova amb llindar t=13

El càlcul dona:

IG≈0.40

millor que el cas de t=8, però pitjor que t=9.

Estratègia general

En lloc de provar uns quants valors a l’atzar, l’algoritme segueix aquesta estratègia:

1. Ordena els exemples segons el valor de la característica contínua (en aquest cas, el pes).
2. Considera com a candidats els punts mitjans entre exemples consecutius.
3. Calcula el guany d’informació per a cadascun d’aquests llindars.
4. Escull el llindar que dona el guany d’informació més alt.

Així, si tenim m exemples, l’algoritme provarà m−1 possibles valors de llindar.

Conclusió

Quan treballem amb característiques contínues en arbres de decisió:

• Es proven diversos llindars t.
• Es calcula el guany d’informació per a cada possible divisió.
• Si aquest guany és superior al que es podria aconseguir amb altres característiques, l’arbre es divideix segons aquest llindar.

En el nostre exemple, el millor llindar era t=9, amb guany d’informació 0.61. Això fa que la partició sigui molt més informativa que altres opcions.

Arbres de decisió per a regressió

Fins ara només hem parlat dels arbres de decisió com a algoritmes de classificació. A continuació els generalitzarem per fer regressió, és a dir, per predir un valor numèric.

Exemple introductori

Suposem que volem predir el pes d’un animal (Y) a partir de certes característiques (X) com ara la forma de les orelles o de la cara.
A diferència de l’exemple de classificació (on l’objectiu era saber si era gat o no gat), aquí l’objectiu és predir un número.

Per això diem que és un problema de regressió.

Fulles d’un arbre de regressió

Imaginem un arbre on la arrel separa segons la forma de les orelles, i els subarbres es tornen a dividir per la forma de la cara.

• En cada fulla no hi ha una categoria (gat o no gat), sinó un conjunt de valors numèrics (els pesos dels animals d’entrenament que hi han arribat).
• La predicció de l’arbre en aquella fulla serà la mitjana d’aquests pesos.

Exemple:
Si en una fulla arriben els pesos 7.2,7.6,10.2,8.4, l’arbre predirà

ˆy=7.2+7.6+10.2+8.44=8.35

Així, si un nou animal té orelles punxegudes i cara arrodonida, seguirà el camí corresponent de l’arbre i s’acabarà assignant el valor mitjà d’aquella fulla.

Com escollir els talls (splits)

En la classificació usàvem l’entropia o la informació guanyada per decidir quina característica era millor dividir.

En la regressió, el criteri és diferent:
volem reduir al màxim la variància dels valors de Y a cada subconjunt.

Intuïció de la Variància:

• La variància mesura com de dispersos estan els valors.
• Si tots els pesos d’una fulla són semblants, la variància és baixa (i la predicció serà més precisa).
• Si són molt diferents, la variància és alta (i la predicció serà menys fiable).

Exemple:

• Valors 7.2,9.2,10.2 → variància ≈ 1.47 (baixa).
• Valors 8.8,15,11,18,20 → variància ≈ 21.87 (alta).

Suposem que tenim Wleft i Wright, que són les proporcions d’exemples que van a esquerra i dreta.

La variància mitjana després del tall és:

Varmitjana=Wleft⋅Varleft+Wright⋅Varright

Aquest valor juga el mateix paper que l’entropia ponderada en classificació.

Reducció de variància

De manera similar a la informació guanyada, aquí mesurem la reducció de variància:

ΔVar=Vararrel−Varmitjana

• Vararrel: variància de tots els exemples a l’arrel.
• Varmitjana: variància ponderada després de dividir.

Exemple:

• Variància inicial de tots els exemples: 20.51.
• Després de dividir per forma d’orella, la variància mitjana és 11.67.
• Per tant, la reducció és:

ΔVar=20.51−11.67=8.84

Com més gran sigui la reducció de variància, millor és el tall.

Procés complet de construcció

1. A l’arrel, calculem la reducció de variància per a cada característica possible.
2. Triem la característica que produeix la reducció més gran.
3. Dividim el conjunt en dos subconjunts.
4. A cada subconjunt, repetim el mateix procés de manera recursiva.
5. Parem quan:
   • no queda cap millora significativa en la variància, o
   • hi ha massa pocs exemples, o
   • s’arriba a una profunditat límit.

Resumint:

• Un arbre de classificació busca reduir l’entropia (impuresa).
• Un arbre de regressió busca reduir la variància dels valors de sortida.
• Les prediccions en les fulles són la mitjana dels valors d’entrenament.
• El procés de creació de l’arbre és iteratiu i recursiu, buscant sempre la característica que millor redueixi la variància.

Amb aquest mètode, els arbres de decisió no només poden fer classificació, sinó també prediccions numèriques.

Conjunts d’arbres de decisió (Tree Ensembles)

Una de les debilitats d’utilitzar un únic arbre de decisió és que aquest pot ser molt sensible a petits canvis en les dades.

Per fer l’algoritme menys sensible, o més robust, una solució és no construir només un arbre, sinó molts arbres de decisió. A aquest conjunt d’arbres se l’anomena ensemble d’arbres (o conjunt d’arbres).

Exemple intuïtiu

En l’exemple que hem anat utilitzant, la millor característica per dividir les dades al node arrel va resultar ser la forma de les orelles, i això generava dos subconjunts de dades, sobre els quals després es construïen subarbres.

Però què passa si només un dels 10 exemples d’entrenament canvia una mica?
Imaginem que un gat que abans tenia:

• orelles punxegudes,
• cara rodona,
• bigotis absents,

ara es transforma en un gat amb:

• orelles caigudes,
• cara rodona,
• bigotis presents.

Només amb aquest petit canvi, la característica amb màxima informació per dividir les dades ja no seria la forma de les orelles, sinó la presència de bigotis.

Com a conseqüència:

• Els subconjunts de dades dels subarbres esquerre i dret serien completament diferents.
• En continuar el procés recursiu de construcció, es generarien arbres molt diferents.

Això mostra que petits canvis en les dades poden donar lloc a arbres de decisió totalment diferents. Per tant, un sol arbre no és gaire robust.

Avantatge d’un ensemble d’arbres

Per això, en lloc d’utilitzar un sol arbre, sovint obtenim millors resultats —prediccions més acurades— si entrenem molts arbres diferents i els fem votar.

Un ensemble d’arbres és simplement una col·lecció de múltiples arbres de decisió.

Per exemple, imaginem un ensemble de tres arbres. Cada arbre és una manera plausible de classificar si un animal és gat o no. Si tenim un nou exemple de prova, el procés seria així:

1. Passem aquest exemple pels tres arbres.
2. Cada arbre produeix una predicció (gat o no gat).
3. Finalment, fem una votació majoritària: el resultat final és la classe que tingui més vots.

Exemple de votació

Nou exemple de prova:

• orelles punxegudes,
• cara no rodona,
• bigotis presents.

Resultats:

• El primer arbre recorre les seves branques i decideix: gat.
• El segon arbre segueix un altre camí i decideix: no gat.
• El tercer arbre acaba concloent: gat.

La votació queda així:

• 2 vots: gat
• 1 vot: no gat

El resultat final de l’ensemble és gat, que en aquest cas és la classificació correcta.

Intuïció

La raó per utilitzar un ensemble és que, amb molts arbres votant, l’algoritme global és molt menys sensible al que faci un arbre individual.

Predicció final=MajorityVote{h1(x),h2(x),…,hn(x)}

on hi(x) és la predicció de l’arbre i per l’exemple x.

Cada arbre té només un vot entre molts, i això fa que el sistema global sigui molt més robust.

Mostreig amb reposició

Per a construir un tree ensemble, necessitem una tècnica anomenada mostreig amb reposició (sampling with replacement). Vegem què significa això pas a pas.

Demostració amb fitxes de colors

Per il·lustrar com funciona el mostreig amb reposició, fem servir quatre fitxes de colors: vermell, groc, verd i blau. Suposem que tenim una bossa negra buida i hi tirem aquestes quatre fitxes.

Ara farem quatre mostrejos amb reposició:

1. Agitem la bossa sense mirar i en traiem una: surt verd.
2. Com que és amb reposició, tornem a posar la fitxa a la bossa i agitem de nou. Ara traiem una altra fitxa: surt groc.
3. Repetim el procés: surt blau, i tornem a reemplaçar-la.
4. Una altra vegada: surt blau de nou.

La seqüència obtinguda és:

Verd, Groc, Blau, Blau

Observa que ha aparegut blau dues vegades i que vermell no ha aparegut.

Si repetíssim aquest procés moltes vegades, podríem obtenir altres seqüències, com:

Vermell, Groc, Vermell, VerdoVerd, Verd, Blau, Vermell

El fet de reemplaçar la fitxa cada vegada és crucial, ja que sense reposició sempre obtindríem les mateixes quatre fitxes.

Aplicació al Tree Ensemble

Ara veiem com s’aplica això per construir un ensemble d’arbres:

1. Suposem que tenim un conjunt d’entrenament amb 10 exemples de gats i gossos.
2. Posem aquests 10 exemples en una bossa teòrica (no hi posem animals reals!).
3. Crearem un nou conjunt d’entrenament aleatori de la mateixa mida (10 exemples).

El procés és el següent:

• Treiem un exemple a l’atzar de la bossa.
• Tornem a posar-lo dins la bossa.
• Repetim aquest procés fins a obtenir 10 exemples.

Com que és amb reposició:

• Alguns exemples es poden repetir.
• Alguns exemples originals poden no aparèixer.

Això és normal i forma part del mostreig amb reposició.

Nou conjunt d’entrenament≈Conjunt originalperò amb variacions

Aquest mètode ens permet construir conjunts d’entrenament lleugerament diferents cada vegada, la qual cosa és la clau per construir un ensemble d’arbres.

En resum:

• El mostreig amb reposició permet generar múltiples conjunts d’entrenament aleatoris i lleugerament diferents.
• Cada arbre de l’ensemble s’entrena amb un conjunt diferent.
• Això ajuda a reduir la variància i fa que l’algorisme sigui més robust.

Algorisme Random Forest

Ara que tenim una manera d’utilitzar sampling amb reposició per crear nous conjunts d’entrenament que són similars però també una mica diferents del conjunt original, estem llestos per construir el nostre primer algorisme de conjunt d’arbres.

En particular, parlarem de l’algorisme Random Forest, un potent algorisme de conjunt d’arbres que funciona molt millor que utilitzar un únic arbre de decisió.

Generació d’un conjunt d’arbres

Si tenim un conjunt d’entrenament de mida M, llavors fem el següent per B=1…B (és a dir, B vegades):

1. Utilitzem sampling amb reposició per crear un nou conjunt d’entrenament de mida M.
   • Per exemple, si tenim 10 exemples, posarem aquests 10 exemples en una “bossa virtual” i en seleccionarem 10 amb reposició per generar un nou conjunt amb 10 exemples.
2. Entrenem un arbre de decisió amb aquest nou conjunt.

Observa que alguns exemples poden repetir-se, i això està bé.

Repetint aquest procediment, obtindrem arbres de decisió lleugerament diferents cada vegada. Si ho fem B vegades, obtindrem un conjunt d’arbres.

Un valor típic de B és al voltant de 100, tot i que algunes persones recomanen 64, 128, etc.

Predicció amb l’ensemble

Quan volem fer una predicció, cada arbre vota i el resultat final és el vot majoritari.
Augmentar B més enllà d’un cert punt no millora gaire el rendiment (més de 1000), i només augmenta el temps de càlcul.

Aquest procediment s’anomena sovint Bagged Decision Tree, ja que fa referència a posar els exemples en una bossa (de aquí el “B” majúscula).

Millora: Random Forest

Hi ha una modificació que millora encara més aquest algorisme i el transforma en Random Forest:

• Encara amb sampling amb reposició, sovint la mateixa característica s’escull al node arrel o nodes propers, generant arbres molt similars.
• Per augmentar la diversitat dels arbres, s’escull un subconjunt aleatori de K<N característiques a cada node en lloc de tots els N característiques disponibles.
• L’arbre tria la característica amb major guany d’informació dins d’aquest subconjunt.

K≈√Nper a conjunts grans característiques

Aquesta modificació fa que el Random Forest sigui més robust i precís que un arbre de decisió individual.

Intuïció:

• El procediment de sampling amb reposició ja explora moltes petites variacions del conjunt d’entrenament.
• Cada arbre veu una versió lleugerament diferent de les dades, i la predicció final és un mitjana de moltes exploracions, fent que petits canvis al conjunt d’entrenament no afectin gaire el resultat final.

Random Forest és un algorisme molt efectiu, però encara hi ha opcions més potents, com els Boosted Decision Trees.

Algorisme XGBoost

Al llarg dels anys, els investigadors en Machine Learning han proposat moltes maneres diferents de construir arbres de decisió i conjunts d’arbres de decisió.
Avui dia, el mètode més utilitzat per implementar conjunts d’arbres de decisió és un algorisme anomenat XGBoost.

XGBoost és:

• Ràpid en execució.
• Fàcil d’utilitzar gràcies a les implementacions open source.
• Molt exitós en concursos de Machine Learning i en aplicacions comercials.

Com funciona XGBoost

XGBoost és una modificació de l’algorisme bàsic d’arbres de decisió que hem vist anteriorment, i millora el rendiment de manera significativa.

Recordem l’algorisme clàssic:

1. Tenim un conjunt d’entrenament de mida m.
2. Repetim B vegades:
   • Fem un sampling amb reemplaçament per crear un nou conjunt d’entrenament de mida m.
   • Entrenem un arbre de decisió amb aquest nou conjunt.

El primer arbre s’entrena normalment. Però a partir del segon arbre, fem un canvi clau: en lloc de seleccionar exemples amb la mateixa probabilitat (1m), donem més probabilitat als exemples mal classificats pels arbres anteriors.

A l’educació, existeix el concepte de pràctica deliberada. Per exemple, si estàs aprenent a tocar el piano:

• En lloc de repetir tota una peça de 5 minuts contínuament (costós en temps),
• Et concentres en les parts que encara no domines i les practiques fins que milloren.

XGBoost aplica la mateixa idea: cada arbre següent se centra més en els exemples que encara no es classifiquen correctament.

Procediment detallat:

1. Observem l’arbre que acabem de construir.
2. Tornem al conjunt d’entrenament original (no al generat amb sampling amb reemplaçament).
3. Recorrem tots els exemples i anotem quins són correctament classificats i quins no.
4. Quan generem el següent arbre:
   • Assignem més probabilitat a seleccionar els exemples que anteriorment es van classificar malament.
5. Repetim aquest procés B vegades.

El resultat és un conjunt d’arbres que aprèn progressivament a corregir els errors dels arbres anteriors.

Característiques principals de XGBoost:

• Extreme Gradient Boosting (XGBoost) és una implementació open source de boosting molt ràpida i eficient.
• Té criteris de divisió i parades predeterminats ben escollits.
• Inclou regularització incorporada per prevenir l’overfitting.
• En comptes de fer sampling amb reemplaçament, XGBoost assigna pesos diferents a cada exemple, millorant encara més l’eficiència.

Per usar XGBoost com a classificació:

import xgboost as xgb

model = xgb.XGBClassifier()

model.fit(X_train, y_train)
predictions = model.predict(X_test)

I si el que vols és fer regressió, només cal substituir el model per xgb.XGBRegressor().

Ús de Xarxes Neuronals i Arbres de Decisions

Tant les xarxes neuronals com els arbres de decisions, incloent conjunts d’arbres, són algoritmes d’aprenentatge molt potents i efectius. Però, quan hem de triar un o l’altre? Vegem els avantatges i desavantatges de cadascun.

Arbres de decisions i conjunts d’arbres

Els arbres de decisions i els seus ensembles sovint funcionen bé amb dades tabulars, també conegudes com a dades estructurades.
Si el teu dataset sembla un gran full de càlcul, els arbres de decisions són una opció interessant.

Per exemple, en l’aplicació de predicció de preus d’habitatges, teníem un dataset amb característiques com:

• mida de la casa
• nombre d’habitacions
• nombre de pisos
• antiguitat de l’habitatge

Aquest tipus de dades pot contenir característiques categòriques o continues, i poden ser utilitzades tant per classificació (preveure categories) com per regressió (preveure un valor numèric). Tot això són tasques on els arbres de decisions poden funcionar molt bé.

No es recomana usar arbres de decisions ni ensembles amb dades no estructurades com imatges, vídeo, àudio o text, ja que no estan pensades per emmagatzemar-se en format de full de càlcul.

Per aquestes tasques, les xarxes neuronals solen ser més adequades.

Avantatges:

1. Entrenament ràpid:
   Els arbres de decisions, especialment els ensembles, són relativament ràpids d’entrenar. Això és important perquè, en el cicle iteratiu del desenvolupament de machine learning, un model ràpid permet iterar més vegades i millorar el rendiment amb més eficàcia.

2. Interpretabilitat:
   Els arbres petits poden ser comprensibles per humans. Per exemple, un arbre amb unes quantes desenes de nodes pot ser visualitzat per entendre com pren decisions.
   Nota: La interpretabilitat disminueix amb ensembles grans, com els 100 arbres amb centenars de nodes cadascun, on calen tècniques de visualització especials.

Recomanacions:

• Per a la majoria d’aplicacions, utilitza XGBoost, que és un potent ensemble d’arbres.
• Desavantatge: un ensemble és més car computacionalment que un arbre individual.
• Si tens un pressupost molt limitat, pots optar per un arbre individual.

Xarxes neuronals

Les xarxes neuronals funcionen bé tant amb dades estructurades com no estructurades, i fins i tot amb dades mixtes.

• En dades tabulars, poden ser competitives amb els arbres de decisions.
• En dades no estructurades (imatges, vídeo, àudio, text), les xarxes neuronals són l’opció preferida.

Desavantatges:

• Entrenament lent: Una xarxa gran pot trigar molt a entrenar.

Avantatges addicionals:

1. Aprenentatge per transferència:
   Permet fer pre-entrenament en datasets grans i després ajustar-se a datasets petits, millorant significativament el rendiment.

2. Sistemes de múltiples models:
   És més senzill entrenar diverses xarxes neuronals conjuntament utilitzant gradient descent, cosa que no és possible amb arbres de decisions, que s’entrenen un a un.