Introducció
Els arbres de decisió (DT) són un mètode d'aprenentatge supervisat no paramètric utilitzat per a la classificació i la regressió. L'objectiu és crear un model que predigui el valor d'una variable objectiu aprenent regles de decisió senzilles inferides de les característiques de les dades.
Entropia
L'objectiu de l'entrenament és trobar les millors divisions en els nodes per tal de trobar l'arbre més òptim. Les divisions es fan utilitzant alguns criteris com ara: Entropia.
Hi ha moltes definicions d'entropia com ara:
-
L'entropia correspon a la quantitat d'informació continguda en una font d'informació.
-
L'entropia també es pot veure com l'aleatorietat o la mesura de la sorpresa en un conjunt.
-
L'entropia és una mètrica que mesura la impredictibilitat o impuresa del sistema.
En els arbres de decisió, considerarem l'entropia com la mesura de la puresa dins d'un node. L'objectiu del model d'arbre de decisió és reduir l'entropia dels nodes a cada divisió:
Per tant, volem maximitzar la diferència entre l'entropia del node pare i l'entropia dels nodes fills. Aquesta diferència s'anomena Guany d'informació.
L'entropia $H$ d'un conjunt $X$ es formula matemàticament de la següent manera:
$$ H(X) = - \sum\limits_{x \in X} p(x) \log p(x) $$
Guany d'informació
El guany d'informació és la diferència entre l'entropia del node pare i la suma ponderada de les entropies dels nodes infantils, i per tant es pot formular de la següent manera:
$$IG(Y, X) = H(Y) - \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x)$$
$$= H(Y) - \sum_{x \in unique(X)} \frac{X.count(x)}{len(X)} \times H(Y[X == x])$$
on:
-
$H(.)$ és l'entropia.
-
$Y$ és la població abans de la divisió, representa el node pare.
-
$X$ és la variable que volem utilitzar per a la divisió.
-
$x$ és un valor únic de X.
-
$Y[X==x]$ és una llista dividida amb només valors de $x$.
prenguem un exemple adequat:
Calcularem el guany d'informació quan dividim el node pare utilitzant els valors de X:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
\
Primer, calculem l'entropia del node pare:
$$ H(parent) = - P(Y=Blue) \times \log P(Y=Blue) - P(Y=Yellow) \times \log P(Y=Yellow) $$
$$ = - \frac{11}{21} \times \log(\frac{11}{21}) - \frac{10}{21} \times \log(\frac{10}{21}) = 0.3 $$
\
Aleshores, calcularem la probabilitat interna de cada node fill després de la divisió utilitzant els valors únics de X:
$$ unique(X) = [Circle, Square] $$
$$ \sum_{x \in unique(X)} P(x|X) \times H(Y | X = x) = P(Square|X) \times H(Y | X = Square) $$
$$ + P(Circle|X) \times H(Y | X = Circle) $$
$$ = \frac{9}{21} \times H(Y | X = Square) + \frac{12}{21} \times H(Y | X = Circle) $$
Com ara:
-
$H(Y | X = Quadrat)$ : representa l'entropia del primer node fill.
-
$H(Y | X = Cercle)$ : representa l'entropia del segon node fill.
\
Comencem amb el primer node fill:
$$ H(Y | X = Square) = - P(Y=Blue | X = Square) \times \log P(Y=Blue| X = Square) $$
$$ - P(Y=Yellow| X = Square) \times \log P(Y=Yellow| X = Square) $$
$$ = - \frac{7}{9} \times \log\frac{7}{9} - \frac{2}{9} \times \log\frac{2}{9} = 0.23 $$
\
I després el segon node fill:
$$ H(Y | X = Circle) = - P(Y=Blue | X = Circle) \times \log P(Y=Blue| X = Circle) $$
$$ - P(Y=Yellow| X = Circle) \times \log P(Y=Yellow| X = Circle) $$
$$ = - \frac{4}{12} \times \log\frac{4}{12} - \frac{8}{12} \times \log\frac{8}{12} = 0.28 $$
\
Finalment, substituïm les entropies a la fórmula de guany d'informació:
$$IG(parent, X) = H(parent) - \sum_{x \in unique(X)} P(x|X) \times H(parent | X = x)$$
$$ = 0.3 - \frac{9}{21} \times 0.23 - \frac{12}{21} \times 0.28 = 0.041 $$
\
\
Com s'ha dit abans, l'objectiu d'una divisió de nodes és maximitzar el guany d'informació i, per tant, minimitzar l'entropia en el node fill resultant. Per fer-ho, hem d'intentar dividir el node amb diferents conjunts d'entrades $ X_1, X_2, \ldots, Xn $ i només mantenim la divisió que maximitza el guany d'informació:
$$ X^{*} = \underset{X_i}{\operatorname{argmax}} IG(Y, X_i) $$
Quan s'ha de deixar de dividir
La divisió de nodes en els arbres de decisió és recursiva, per tant ha d'haver un criteri que puguem utilitzar per aturar la divisió. Aquests són alguns dels criteris més implementats:
-
Quan el node és pur: H(node) = 0. No té sentit dividir el node més.
-
Nombre màxim de profunditat: Podem establir una profunditat màxima que pot assolir el model, vol dir que encara que el node no sigui pur el desdoblament s'atura.
-
Nombre mínim de mostres per node: També podem establir un nombre mínim de $N$ de mostres per node. Si el nombre de mostres per node és igual a $N$, deixem de dividir encara que el node no sigui pur.
Al final de l'entrenament (la divisió), cada node que es basa en el final de l'arbre de decisió s'anomena "Fulla", perquè no és una arrel de cap subarbre. Cada fulla representarà el rendiment de la classe amb més mostres.
Conclusió
L'arbre de decisions és un dels algorismes d'aprenentatge automàtic més famosos per la seva eficiència, fons intuïtiu i implementació senzilla. Aquest algorisme es pot utilitzar encara més amb variables numèriques independents (arbre de decisió gaussià), i també es pot estendre per resoldre tasques de regressió.
