Regressió d'arbre de decisió des de zero: teoria i pràctica

Inici » Pitó » Regressió d'arbre de decisió des de zero: teoria i pràctica

La regressió d'arbre de decisió des de zero és un dels exercicis més reveladors que podeu fer si voleu entendre realment com pensen els models basats en arbres i per què són tan populars en l'aprenentatge automàtic. En lloc de tractar l'arbre com una misteriosa caixa negra, veureu com es tria cada divisió, com es mesura la impuresa i com es produeixen prediccions numèriques a les fulles, tant per a problemes de regressió com de classificació.

En aquesta guia, repassarem les idees bàsiques que hi ha darrere dels arbres de decisió, les funcions de cost que utilitzen, com busquen les millors divisions i com codificar un arbre bàsic que admeti tant la regressió com la classificació, utilitzant només conceptes fonamentals com ara bucles, condicions i estadístiques simples. Al llarg del camí, compararem els arbres de regressió i els de classificació, connectarem la teoria amb implementacions pràctiques en eines com Python i R (per exemple, amb rpart i tree) i situarem breument els arbres de decisió dins de conjunts més grans com ara els boscos aleatoris.

Què és un arbre de decisió i per què és tan intuïtiu?

Un arbre de decisió és essencialment un flux de preguntes de sí/no (o regles simples) que et guia des d'una decisió arrel fins a una predicció final en un node fulla. En un entorn típic d'aprenentatge supervisat, l'objectiu és predir una variable objectiu Y utilitzant múltiples predictors (característiques, covariables), i l'arbre aprèn una seqüència de preguntes com ara "el pes és ≤ 103?" o "el país és a {EUA, Regne Unit, CA}?" que divideix gradualment les dades en grups més homogenis.

Per tenir una mica d'intuïció, imagineu-vos que voleu predir si algú és obes utilitzant només l'alçada i el pes, i teniu un conjunt de dades etiquetat que us indica qui és obès i qui no. Un arbre podria descobrir una regla com ara "si el pes és > 100 kg, prediu obesitat", però aquesta regla no serà perfecta: algunes persones per sobre dels 100 kg no seran obeses, i algunes per sota d'aquest llindar sí que ho seran. L'arbre continua afegint més preguntes (subdivisions), per exemple sobre l'alçada o un llindar de pes refinat, per "afinar" aquestes prediccions aproximades inicials.

Cada node intern de l'arbre correspon a una regla de decisió, cada branca correspon a un resultat d'aquesta regla i cada node fulla correspon a una regió de l'espai de característiques on les prediccions són constants. En la classificació, una fulla retorna una etiqueta de classe (o una distribució de probabilitat sobre les etiquetes); en la regressió, una fulla normalment retorna la mitjana dels valors objectiu que cauen en aquesta regió.

Un dels principals punts forts dels arbres de decisió és que gestionen tant la regressió com la classificació de manera natural, són fàcils d'interpretar i funcionen amb predictors quantitatius i qualitatius (categòrics) sense necessitat d'un processament previ pesat. No cal assumir cap distribució específica per a les característiques o el destí, cosa que fa que els arbres siguin molt atractius en escenaris del món real on sovint es violen les suposicions lineals clàssiques.

Classificació vs. arbres de regressió

Tot i que l'estructura dels arbres de classificació i de regressió és la mateixa, la naturalesa de la variable de resposta Y i la funció de cost utilitzada per a la divisió difereixen entre aquests dos tipus. Quan Y és quantitatiu (per exemple, vendes, esperança de vida, consum de combustible), parlem d'un arbre de regressió; quan Y és qualitatiu o categòric (per exemple, va sobreviure vs. no va sobreviure, obès vs. no obès), parlem d'un arbre de classificació.

En un arbre de regressió, l'objectiu habitual és dividir l'espai de característiques en regions on la resposta es pot aproximar mitjançant una constant, sovint la mitjana de les observacions en aquesta regió. Les regles de decisió típiques tenen la forma "és x_k ≤ c?”, on x_k és una de les covariables i c és un llindar; aquestes regles divideixen repetidament l'espai en hiperrectangles, i tots els punts del mateix hiperrectangle comparteixen el mateix valor predit ŷ.

En un arbre de classificació, les divisions encara són "característica ≤ llindar?" o "categoria del conjunt S?", però la qualitat d'una divisió es mesura per la puresa dels nodes fills resultants en termes d'etiquetes de classe. La predicció de fulles sol ser la classe majoritària dins d'aquest node, i el model intenta crear fulles que s'acostin el màxim possible a contenir només una classe.

Malgrat aquestes diferències en el tipus de destinació, des d'una perspectiva de codificació podeu implementar una única estructura d'arbre genèrica i simplement connectar diferents mesures d'impuresa o pèrdua segons si esteu fent una regressió o una classificació. Més tard, quan calculem el guany d'informació, veureu que les fórmules de classificació (basada en l'entropia) i de regressió (basada en la variància) són paral·leles en esperit.

Funcions d'impuresa i cost en arbres de decisió

Al cor de qualsevol algorisme d'arbre de decisió hi ha una funció de cost que avalua la capacitat d'una divisió particular per separar les dades en grups significatius. Aquesta funció de cost s'expressa en termes d'impuresa: un node es considera pur si totes les seves mostres pertanyen a la mateixa classe (per a la classificació) o tenen gairebé el mateix valor numèric (per a la regressió).

Sempre que seleccioneu una divisió candidata en una característica, l'algoritme examina els nodes fills que produeix i pregunta: "quina barreja hi ha entre les etiquetes (o valors) de cada fill?" Una bona divisió és aquella que produeix nodes fills que són molt menys impurs que el pare, la qual cosa significa que les dades dins de cada fill són més homogènies respecte a l'objectiu.

En els arbres de classificació, la impuresa se sol mesurar mitjançant criteris com l'índex de Gini o l'entropia, que capturen la probabilitat que una observació escollida aleatòriament en aquest node es classifiqui incorrectament si simplement prediguéssim la classe majoritària. En els arbres de regressió, la impuresa es mesura habitualment amb l'error quadràtic o la variància, que reflecteix com de dispersos estan els valors objectiu dins del node.

Índex de Gini: mesura de la impuresa en arbres de classificació

L'índex de Gini és una de les mesures d'impureses més utilitzades per als arbres de classificació perquè és fàcil de calcular i funciona bé a la pràctica. Conceptualment, mesura la probabilitat que una observació seleccionada aleatòriament del node es classifiqui incorrectament si la seva etiqueta es predigui segons la distribució d'etiquetes en aquest node.

Si un node conté classes amb probabilitats P₁, P₂, … , P_n, l'índex de Gini es calcula com a Gini = 1 − Σ (P_i)². Quan un node és perfectament pur (totes les observacions pertanyen a la mateixa classe), una de les probabilitats és 1 i la resta són 0, de manera que la suma dels quadrats és 1 i l'índex de Gini és 0, cosa que indica puresa total.

D'altra banda, l'índex de Gini arriba al seu màxim quan les classes es barregen uniformement dins del node, per exemple en un problema binari amb P₁ = P₂ = 0.5, que dóna Gini = 1 − (0.5² + 0.5²) = 0.5. En aquesta situació, predir la classe majoritària és el pitjor que es pot aconseguir per a aquesta distribució perquè el node conté la meitat de cada classe.

Quan implementeu Gini en codi, normalment agafeu el vector d'etiquetes per al node, calculeu la freqüència de cada classe, convertiu les freqüències en probabilitats i després apliqueu la fórmula 1 − Σ p². Si feu això per a múltiples divisions candidates, podeu comparar quina divisió produeix fills amb una impuresa de Gini mitjana ponderada més baixa, que és exactament el que l'arbre necessita per decidir la millor partició.

Entropia: una altra visió de la impuresa de classificació

L'entropia és una mesura d'impuresa alternativa àmpliament utilitzada en la teoria de la informació i en els primers algoritmes d'arbre com ID3 i C4.5, i captura la quantitat d'aleatorietat o incertesa en la distribució de classes del node. Mentre que Gini se centra en la probabilitat de classificació errònia, l'entropia quantifica la "sorpresa" associada a l'observació d'una classe particular quan la distribució és mixta.

Donades les probabilitats de classe p₁,…, pàg_c per a un node S, la seva entropia es defineix com E(S) = − Σ p_i log₂(p_i). Si el node és pur, una de les probabilitats és 1 i totes les altres són 0, cosa que fa que la suma sigui zero (perquè log₂(1) = 0), de manera que l'entropia és 0, cosa que indica que no hi ha incertesa.

Quan el node conté una distribució uniforme de classes, l'entropia es maximitza; per a un problema binari amb p₁ = pàg₂ = 0.5, l'entropia és d'1 bit, que és el valor més alt possible per a dues classes. Aquest valor correspon a la incertesa màxima, és a dir, que el node és tan impur com pot ser sota aquesta distribució.

Tot i que el coeficient de Gini i l'entropia utilitzen fórmules diferents i tenen rangs numèrics diferents (Gini entre 0 i 0.5 per a dues classes, entropia entre 0 i 1), ambdues mesuren essencialment el mateix concepte, de manera que normalment condueixen a arbres molt similars a la pràctica. Quan calculeu tots dos al mateix node, trobareu que un índex de Gini alt correspon a una entropia alta i viceversa, motiu pel qual moltes biblioteques us permeten triar qualsevol dels dos sense canviar dràsticament el rendiment.

Obtenció d'informació i elecció de les millors divisions

Per triar la millor divisió entre molts candidats, l'algoritme d'arbre utilitza una mètrica anomenada Guany d'informació, que mesura quanta impuresa disminueix quan dividim un node en els seus fills. Intuïtivament, una divisió té un guany d'informació elevat si els fills són molt més purs que el pare, és a dir, que la regla ha separat correctament les dades en grups més significatius.

Per als arbres de classificació que utilitzen entropia, el guany d'informació d'una divisió es defineix com a IG_{classificació} = E(pare) − Σ (|S_nen| / |S_pare|) · E(S_nen). Primer calculeu l'entropia del node pare i després resteu l'entropia mitjana ponderada dels nodes fills, on els pesos són les seves mides relatives.

Per als arbres de regressió, un concepte anàleg utilitza la variància o l'error quadràtic mitjà com a mesura d'impuresa, donant IG_regressió = Var(pare) − Σ (|S_nen| / |S_pare|) · Var(S_nen). En aquest context, una bona divisió és aquella que redueix substancialment la variabilitat dels valors objectiu dins de cada nen.

L'algoritme d'entrenament d'arbre avalua aquest guany d'informació per a cada possible divisió candidata en cada característica, i després tria la divisió amb el guany més alt, sempre que superi un llindar mínim per evitar crear millores petites i inútils. Aquest procés es repeteix recursivament a cada node fill fins que s'assoleixen alguns criteris d'aturada.

Com buscar la millor divisió per a cada característica

Trobar la millor divisió en una sola característica depèn de si la característica és numèrica o categòrica, però la idea subjacent és sempre la mateixa: enumerar les particions candidates i calcular el seu guany d'informació. Per a les característiques numèriques, una partició es defineix mitjançant un llindar; per a les característiques categòriques, es defineix agrupant els nivells en subconjunts.

Per a un predictor numèric, l'estratègia habitual és examinar tots els valors únics que la característica pren al node actual, ordenar-los i després considerar els llindars candidats entre valors consecutius. Per a cada llindar candidat c, creeu dos grups (x ≤ c i x > c), calculeu la impuresa de cada grup i després calculeu el guany d'informació; el llindar que produeix el guany més alt és la vostra millor divisió numèrica en aquesta característica.

Quan es tracta de predictors categòrics, l'espai de cerca és més complex perquè, en principi, qualsevol subconjunt de categories podria formar un costat de la divisió, amb el complement a l'altre costat. En una característica amb K categories, hi ha molts subconjunts possibles (2^K−1 − 1 particions no trivials), de manera que a la pràctica les implementacions sovint restringeixen aquesta cerca o utilitzen heurístiques, especialment quan K és gran.

Un cop hàgiu calculat la millor divisió per a cada característica, compareu els seus guanys d'informació i seleccioneu la característica i el llindar (o subconjunt de categories) corresponent al guany màxim. Aquesta divisió escollida esdevé la decisió al node actual i, aleshores, el procés d'entrenament es repeteix a cada fill amb el subconjunt d'observacions corresponent.

Control del creixement dels arbres amb hiperparàmetres

Si permeteu que un arbre de decisió creixi sense cap restricció, continuarà dividint-se fins que cada fulla sigui perfectament pura o contingui molt poques observacions, cosa que gairebé sempre condueix a un sobreajustament greu (sobreajustament vs infraajustament). Per evitar això, definiu una col·lecció d'hiperparàmetres que controlen la profunditat i la complexitat de l'arbre.

Un hiperparàmetre comú és max_depth, que limita el nombre màxim de nivells que l'arbre pot créixer des de l'arrel fins a qualsevol fulla. Si max_depth s'estableix a None (o a un nombre molt gran), l'arbre pot continuar creixent sempre que es compleixin altres restriccions; si és petit, l'arbre roman superficial i més interpretable, però podria ser insuficient.

Un altre hiperparàmetre clau és min_samples_split, que especifica el nombre mínim d'observacions que un node ha de contenir abans que es pugui dividir. Si un node té menys mostres que aquest llindar, es converteix en una fulla, cosa que evita que el model persegueixi el soroll en subconjunts de dades molt petits.

També podeu imposar un guany d'informació mínim (min_information_gain) de manera que l'algoritme només realitzi una divisió si produeix una millora significativa en la reducció d'impureses. Això evita crear branques innecessàries que gairebé no canvien les prediccions i simplement compliquen l'estructura de l'arbre.

Construir un arbre de decisió des de zero en codi

La implementació d'un arbre de decisió des de zero normalment gira al voltant d'un petit conjunt de funcions bàsiques que es criden recursivament. Mentre que biblioteques com scikit-learn o rpart fan tot això en secret, codificar aquests passos tu mateix fa que la lògica sigui molt més clara (lògica de programació) i et dóna control total sobre el comportament.

Primer, necessiteu una rutina que, donades les dades actuals en un node, avaluï cada característica i cada divisió candidata per trobar la que tingui el guany d'informació més alt. Aquesta funció retorna la característica escollida, la regla de divisió (llindar o subconjunt de categories), el valor de guany i la màscara booleana o els conjunts d'índexs que identifiquen quines mostres van a l'esquerra i quines a la dreta.

En segon lloc, necessiteu una funció de predicció per als nodes fulla que converteixi el conjunt de valors objectiu d'aquest node en una única predicció. Per a la regressió, aquesta és normalment la mitjana de y en aquest node; per a la classificació, normalment es pren la moda (la classe més freqüent), possiblement emmagatzemant també les probabilitats de classe si es volen resultats probabilístics.

En tercer lloc, creeu una funció d'entrenament recursiva que comprovi els criteris d'aturada, cerqui la millor divisió si està permesa i, a continuació, construeix nodes fills cridant-se a si mateixa als subconjunts esquerre i dret. Si no es compleixen les condicions de mida mínima de mostra, profunditat màxima o guany mínim, la funció atura la divisió i emmagatzema una predicció de fulles en lloc de més branques.

Com funciona la predicció en un arbre de decisió entrenat

Un cop que l'arbre ha estat entrenat i hagueu emmagatzemat totes les regles de divisió i les prediccions de fulles, fer una predicció per a una nova observació és simplement qüestió de caminar per l'arbre des de l'arrel fins a una fulla. A cada node intern, inspeccioneu la característica requerida i proveu si l'observació compleix la condició del node.

Si la regla de divisió és numèrica, comproveu si el valor de la característica és inferior o igual al llindar; si la regla de divisió és categòrica, comproveu si la categoria es troba en un subconjunt concret. Depenent del resultat, seguiu la branca adequada (per exemple, "sí" a l'esquerra, "no" a la dreta) i repetiu aquest procés al següent node.

Continueu descendint per l'arbre fins que arribeu a un node sense fills, que és una fulla que emmagatzema un valor de sortida constant o una etiqueta de classe. Per a un arbre de regressió, la predicció serà un nombre com ara una esperança de vida estimada o una eficiència de combustible; per a un arbre de classificació, la sortida serà una categoria prevista com ara "va sobreviure" o "no va sobreviure".

Si proveu aquest mètode amb les mateixes dades que heu utilitzat per a l'entrenament, sovint veureu una precisió força alta per a la classificació (per exemple, al voltant del 85% en alguns exemples simples d'obesitat o d'estil Titanic), però aquest rendiment podria disminuir amb dades no visibles si el vostre arbre és massa profund. Aquesta és precisament la raó per la qual és tan important controlar la profunditat i la mida dels arbres, i per la qual es van inventar conjunts com els boscos aleatoris per estabilitzar les prediccions dels arbres.

Treballar amb arbres de regressió a la pràctica

Els arbres de regressió són particularment útils quan la relació entre els predictors i la resposta és fortament no lineal i implica interaccions que són difícils de modelar amb la regressió lineal clàssica. En lloc d'intentar ajustar una única equació global, l'arbre divideix l'espai de característiques en regions i ajusta un model constant simple dins de cada regió.

A R, paquets populars com ara rpart i tree faciliten la construcció d'arbres de regressió amb una única crida a funció, especificant una fórmula com ara y ~ x1 + x2 + … + x11. Aquests paquets van ser influenciats per la metodologia CART original descrita per Breiman i els seus col·legues, i implementen moltes de les idees de divisió i poda estàndard en la modelització moderna basada en arbres.

Per exemple, podeu utilitzar el paquet rpart per modelar una resposta y basada en onze covariables x1 a x11, netejar les dades dels valors que falten i, a continuació, visualitzar l'arbre resultant amb funcions auxiliars com ara prp del paquet rpart.plot. Els nodes terminals mostren la y prevista per a cada regió, que podeu utilitzar directament per a noves observacions.

Donat un arbre de regressió entrenat, podeu introduir nous valors de covariables com ara x9 = 70, x2 = 100 o x9 = 60, x2 = 150 a la funció de predicció per obtenir valors estimats ŷ (per exemple, al voltant de 20 o 28 en un exemple de consum de combustible). Comparar aquestes prediccions amb els valors observats, per exemple mitjançant la correlació entre y i ŷ, us dóna una idea ràpida de com de bé l'arbre captura el patró subjacent, fins i tot quan el conjunt de dades és força petit.

D'arbres individuals a boscos aleatoris

Un únic arbre de decisió és potent però també notòriament sensible a les particularitats de les dades d'entrenament, cosa que pot conduir a una alta variància (biaix i variància) i sobreajustament. Per mitigar això, els boscos aleatoris construeixen molts arbres sobre mostres de dades bootstrappejades i agreguen les seves prediccions, produint un model més estable i normalment més precís.

En un bosc aleatori, cada arbre s'entrena sobre una mostra d'bootstrap, la qual cosa significa que s'extreu un nou conjunt de dades de la mateixa mida del conjunt d'entrenament original amb reemplaçament. Aquest procés de mostreig fa que cada arbre vegi un conjunt de dades lleugerament diferent, de manera que els seus errors estan menys correlacionats i es poden cancel·lar quan s'agreguen.

A més, els boscos aleatoris introdueixen aleatorietat en el procés de selecció de característiques considerant només un subconjunt aleatori de predictors a cada divisió en lloc de tots els predictors. Això redueix encara més la correlació entre els arbres, millora la diversitat del bosc i tendeix a reduir la variància sense augmentar massa el biaix.

La combinació de bootstrapping i agregació de prediccions es coneix com a bagging, i en boscos aleatoris també s'obté una estimació interna de l'error del model avaluant cada arbre en els punts de dades que no es van incloure a la seva mostra de bootstrap (les anomenades observacions fora de la bossa). Aquest error fora de la caixa proporciona una manera convenient d'avaluar el rendiment sense necessitat d'un conjunt de validació separat.

Tot i que aquest article se centra en la construcció d'un únic arbre des de zero, entendre com funciona aquest component bàsic facilita molt la comprensió de com conjunts com ara boscos aleatoris, augment de gradients i altres mètodes basats en arbres es basen en els mateixos principis per aconseguir resultats d'avantguarda en molts problemes aplicats.

En conjuntar-ho tot, la regressió d'arbre de decisió des de zero mostra com un conjunt simple de regles, funcions de cost i divisions recursives poden modelar relacions complexes, tant si es preveu un resultat binari com la supervivència, una etiqueta categòrica com l'obesitat o un objectiu numèric com l'esperança de vida o el consum de combustible, i aquesta comprensió profunda esdevé una base sòlida per utilitzar tècniques més avançades basades en arbres a la pràctica.