miniatura|320.994x320.994px|Fig. 1 Exemple d'arbre de decisió simple Un arbre de decisió és una eina de suport a la presa de decisions que empra un model gràfic en forma d'arbre per expressar les decisions i les seves possibles conseqüències, incloent-hi les probabilitats de què succeeixin certs successos, els costos i les utilitats.
S'usa en àmbits tan diversos com intel·ligència artificial i l'economia. L'arbre és una manera d'especificar un algorisme que conté controls condicionals.
Propietats miniatura|Fig.2 Exemple d'arbre de decisió amb blocs Un arbre de decisió és una estructura similar a un diagrama de flux en què cada node intern representa una "prova" sobre un atribut (per exemple, si quan tirem una moneda aquesta sortirà cara o creu), cada branca representa el resultat de la prova i cada mode de fulla representa una etiqueta de classe (decisió presa després de calcular tots els atributs). Els camins d'arrel a fulla representen regles de classificació.
En l'anàlisi de decisions, un arbre de decisió i el diagrama d'influència estan estretament relacionats, ja que els utilitzem com a eina de suport visual i analític a la decisió, on es calculen els valors esperats (o la utilitat esperada) de les alternatives competidores.
Un arbre de decisió està format per 3 tipus de nodes:
Node de decisió: típicament representat per quadrats. Nodes casuals: típicament representat per cercles Node final: típicament representat per triangles. Els arbres de decisió s'usen habitualment en la investigació operativa i la gestió d'operacions. Si, a la pràctica, les decisions s'han de prendre en línia sense recordar-les sota coneixements incomplets, un arbre de decisions hauria d'anar paral·lel a un model de probabilitat com a model de millor elecció o algorisme de model de selecció en línia. Un altre ús dels arbres de decisió és com a mitjà descriptiu per calcular probabilitats condicionals.
Construcció d'un arbre de decisió Expliquem com es construeix un arbre de decisió. Per fer-ho, haurem d'explicar primer una sèrie de coses:
Elements miniatura|301x301px|Elements d'un arbre de decisió Els arbres de decisió estan formats per nodes, vectors de nombres, fletxes i etiquetes:
Cada node es pot definir com el moment en què s'ha de prendre una decisió entre diverses possibles, el que va fent que a mesura que augmenti el nombre de nodes augmenti el nombre de possibles finals als quals pot arribar un individu. Això fa que un arbre amb molts nodes sigui complicat de dibuixar a mà i d'analitzar a causa de l'existència de nombrosos camins que poden seguir. Els vectors de nombres serien la solució final a la qual s'arriba en funció de les diverses possibilitats que es tenen, donen les utilitats en cada solució. Les fletxes són les unions entre un node i un altre, i representen cada una de les accions realitzades. Les etiquetes es troben en cada node i cada fletxa i donen nom a cada acció.
Conceptes Quan parlem del desenvolupament d'arbres, utilitzarem sovint aquests conceptes:
Cost. Es refereix a dos conceptes diferents: # El cost de mesurament per a determinar el valor d'una determinada propietat (atribut) exhibit per l'objecte en qüestió. # El cost de classificació errònia quan es decideix que l'objecte pertany a la classe X quan la seva classe real és la Y. Sobreajust (Overfitting). Es produeix quan les dades d'entrenament són poques o tenen incoherències. En prendre un espai d'hipòtesis , es diu que una hipòtesi sobreajusta un conjunt d'entrenament si existeix alguna hipòtesi alternativa tal que classifica millor que els elements del conjunt entrenament, però classifica millor que el conjunt complet de possibles instàncies. Poda (Pruning). La poda consisteix en eliminar una branca d'un node transformant-lo en una fulla (terminal), assignant-li la classificació més comuna dels exemples d'entrenament considerats en aquell node. Validació encreuada. És el procés de construir un arbre amb la majoria de les dades i després utilitzar la part restant de les dades per a provar-ne la precisió de l'arbre.
Regles de decisió En els arbres de decisió s'han de complir una sèrie de regles de decisió:
Al començament del joc, es dona un node inicial que no és apuntat per cap fletxa, és l'únic del joc que amb aquesta característica. La resta de nodes del joc són apuntats per una única fletxa. D'aquí es dedueix que hi ha un únic camí per arribar del node inicial a cada un dels nodes del joc. No hi ha dues formes diferents d'arribar a la mateixa solució final, les decisions són excloents.
En els arbres de decisió les decisions que s'escullen són lineals, a mesura que vas seleccionant entre diverses opcions es van tancant altres, el que implica normalment que no hi ha marxa enrere. En general, les regles tenen una forma condicional:if condició 1 i condició 2 i condició 3 llavors resultatAquestes regles solen venir implícites en el conjunt de dades arran del qual es construeix l'arbre de decisions. Les regles de decisió es poden generar construint regles d'associació amb la variable objectiu de la dreta. També poden denotar relacions temporals o causals.K. Karimi and H.J. Hamilton (2011), "Generation and Interpretation of Temporal Decision Rules", International Journal of Computer Information Systems and Industrial Management Applications, Volume 3
Exemple miniatura|275x275px En aquest arbre de decisió podem observar com hi ha quatre possibles solucions finals. En ell es compleixen les regles anteriorment descrites (node inicial, una única fletxa per node i un únic camí per arribar a cada node final) i té tots els elements descrits (node, vector de nombres, fletxes i etiquetes). La imatge representa un arbre de decisió conformat per dos jugadors. La primera decisió l'ha de prendre la jugadora 1, qui deu decidir entre O1 i O2, ara haurà de ser la jugadora 2 qui decideix. Si la jugadora 1 ha decidit O1, l'altra jugadora haurà de decidir entre A1 i R1, A1 li produirà una utilitat de 2, i R1 de 0, a la vegada A1 li reportarà una utilitat de 8 a la jugadora 1 i R1 de 0. En canvi, si la jugadora 1 escull O2, la jugadora 2 haurà de triar entre A2 i R2, la primera opció li reportarà una utilitat de 5 a ella i a l'altra jugadora, R2 reportarà una utilitat de 0 a les dues. Amb els mètodes d'inducció existents adequats es podria resoldre aquest arbre de decisió sense molta complicació.
Exemple d'anàlisi L'anàlisi pot tenir en compte la funció de preferència o utilitat del qui el du a terme (per exemple, de l'empresa), per exemple: center|sense marc|329x329px La interpretació bàsica en aquest cas és que l'empresa prefereix el risc i els beneficis de B sota coeficients de preferència de risc realistes (superiors a 400 dòlars), en aquest rang d'aversió al risc, l'empresa hauria de modelar una tercera estratègia, "Ni A ni B".
Un altre exemple, utilitzat habitualment en cursos d'investigació operativa, és la distribució de socorristes a les platges (també conegut com l'exemple "Life's a Beach"). L'exemple descriu dues platges amb socorristes que es distribuiran a cada platja. Hi ha un pressupost màxim B que es pot distribuir entre les dues platges (en total), i mitjançant una taula de retorn marginal, els analistes poden decidir quants socorristes destinar a cada platja. +Socorristes a cada platjaOfegaments previnguts en total, platja #1Ofegaments previnguts en total, platja #2131204 En aquest exemple, un arbre de decisions pot ser dibuixat per a il·lustrar la llei de rendiments de decreixement a la platja #1. miniatura L'arbre de decisió il·lustra que quan els socorristes es distribueixen seqüencialment, col·locar primerament un socorrista a la platja #1 seria la millor opció si només hi hagués pressupost per a un socorrista. Però si hi ha pressupost per a dos socorristes, llavors col·locant-los als dos a la platja #2 previndran més ofegaments. center|sense marc|308x308px
Diagrama d'influència Molta de la informació en un arbre de decisió pot ser representada més compacte com a diagrama d'influència, focalitzant l'atenció en els problemes i relacions entre esdeveniments. center|miniatura|359x359px|El rectangle de l'esquerra representa la decisió, els ovals representen accions i el diamant el resultat.
Regla d'inducció Els arbres de decisió poden ser utilitzats com models generatius de regles d'inducció sobre dades empíriques. Un arbre de decisió optimal es pot definir com un arbre que considera la gran majoria de les dades, mentre minimitza el nombre de nivells (o preguntes). Hi ha diversos algorismes per generar aquests tipus d'arbres, com ID3/4/5, CLS, ASSISTANT, i CART.
Avantatges i inconvenients Entre les diferents eines de decisió, els arbres de decisió tenen varies avantatges:
Són fàcils d'entendre i de ser interpretats. Els resultats son valuosos fins i tot amb dades valuoses i pesades. Es pot extreure molt de coneixement expert que descriu algunes situacions (com poden ser alternatives, probabilitats i costos). Ajuda a determinar valors pitjors, millors i esperats per diferents escenaris. S'utilitza un model de caixa blanca, on es pot veure el procés en el qual el model ha arribat a un cert resultat però el procés no pot ser alterat. Es pot combinar amb altres tècniques de decisió. Es poden utilitzar més d'un arbre de decisió dins del mateix problema.
Els inconvenients dels arbres de decisió són:
Aquests són inestables, és a dir, al mínim canvi produït en les dades d'entrada poden generar un canvi en la estructura òptima de l'arbre. Molt sovint són poc acurats. Altres predictors donen millors resultats amb dades similars. Una manera de solucionar-ho, podria ser generar un bosc aleatori d'arbres de decisió, però la interpretació d'aquest és una mica més complicada. Per dades que continguin variables categòriques amb diferent nombre de nivells, la informació que guanya l'arbre de decisió és esbiaixada pels atributs amb nivells més alts. Els càlculs es poden tornar molt complexes, sobretot si hi ha molts valors desconeguts i/o hi ha molta dependència entre les dades.
Optimització d'un arbre de decisió Cal tenir en compte algunes coses a l'hora de millorar la precisió del classificador de l'arbre de decisió. A continuació es mostren algunes optimitzacions possibles a tenir en compte a l'hora d'assegurar-se que el model d'arbre de decisions produït fa la decisió o classificació correcta. S'ha de tenir en compte que aquestes coses no són les úniques coses a considerar.
Augment del nombre de nivells de l'arbre
L'exactitud de l'arbre de decisió pot canviar en funció de la profunditat de l'arbre de decisió. En molts casos, les fulles de l'arbre són nodes purs. Quan un node és pur, vol dir que totes les dades d'aquest node pertanyen a una sola classe. Per exemple, si les classes del conjunt de dades són Càncer i No-Càncer, un node fulla es consideraria pur quan totes les dades de mostra d'un node fulla només formen part d'una classe, ja sigui Càncer o No-Càncer. És important tenir en compte que un arbre més profund no sempre és millor l'hora d'optimitzar l'arbre de decisió. Un arbre més profund pot influir en el temps d'execució de manera negativa. Si s'utilitza un determinat algorisme de classificació, un arbre més profund podria significar que el temps d'execució d'aquest algorisme de classificació és significativament més lent. També hi ha la possibilitat que l'algoritme que construeix l'arbre de decisió sigui significativament més lent a mesura que l'arbre es fa més profund. Si l'algoritme utilitzat divideix els nodes purs, es podria experimentar una disminució de la precisió general del classificador d'arbres. Ocasionalment, aprofundir en l'arbre pot provocar una disminució de la precisió en general, per la qual cosa és molt important fer proves modificant la profunditat de l'arbre de decisió i seleccionant la profunditat que produeixi els millors resultats. Els següents punts mostren un breu resum, sent el nombre D la profunditat de l'arbre.