Árboles de Decisión

Los árboles de decisión son un modelo de Inteligencia Artificial de clasificación que usa Aprendizaje supervisado. Tienen nodos de decisión (que intentan clasificar un ejemplo) y nodos hoja (que aplican una clase).

El árbol se construye particionando el conjunto de entrenamiento con tal de encontrar subconjuntos disjuntos lo más puros posibles (aquellos cuyos ejemplos son de la misma clase). Los caminos generados en el árbol son mutuamente excluyentes y exhaustivos.

El $(X / Y)$ debajo de cada clase representa que $X$ de cada $Y$ ejemplos del conjunto de entrenamiento que llegan a ese nodo hoja tienen la clase del nodo hoja. Indica la pureza del subconjunto. Esto se puede relacionar al Modelo de Reglas de Asociación, donde $X$ representa el conteo de soporte y $X / Y$ representa la confianza. Por lo general sucede que $X < Y$ .

Un árbol de decisión puede convertirse en un conjunto de reglas si-entonces. El problema es que no se pueden encontrar todas las reglas, por lo que solo se obtienen un subconjunto de todas las reglas posibles.

Se pueden crear muchos árboles de decisión a partir del mismo dataset. La cuestión es encontrar el que tenga mejor precisión y sea más fácil de entender. Siempre es conveniente el árbol de decisión que sea más útil para el usuario.

Existen muchos algoritmos para construir árboles de decisión. El más representativo es el C4.5 de Quinlan. Este algoritmo asume que los datos son discretos. Es recursivo. En términos simples, siendo $D$ un conjunto de ejemplos, $A$ un conjunto de atributos, y $T$ un nodo actual:

Si $D$ es puro o $A = \emptyset$ , hacer $T$ un nodo hoja etiquetado con la clase $c_{j}$ más común en $D$ .
Sino, evaluar la impureza de $D$ ( $p_{0}$ ) y la impureza que cada atributo de $A$ contribuye ( $p_{1}$ ) para elegir el atributo $A_{g}$ que da la mayor reducción de impureza según $p_{0} - p_{1}$ . Si $A_{g}$ reduce la impureza por encima de un threshold, entonces $T$ será un nodo de decisión sobre $A_{g}$ con una rama por cada valor distinto de $A_{g}$ y se debe particionar $D$ en un subconjunto disyunto por cada valor distinto de $A_{g}$ para hacer la llamada recursiva $decisionTree (D_{j}, A - {A_{g}}, T_{j})$ .

Algorithm decisionTree (D, A, T) if D contains only training examples of the same class c_{j} \in C then make T a leaf node labeled with class c_{j}; elseif A = \emptyset then make T a leaf node labeled with c_{j}, the most frequent class in D else p_{0} \leftarrow impurityEval-1 (D); for each A_{i} \in A (= {A_{1}, A_{2}, \dots, A_{k}}) do p_{i} \leftarrow impurityEval-2 (A_{i}, D); endfor Select A_{g} \in {A_{1}, A_{2}, \dots, A_{k}} that gives the biggest impurity reduction, computed using p_{0} - p_{i}; if p_{0} - p_{g} < t h r es h o l d then make T a leaf node labeled with c_{j}, the most frequent class in D; else Make T a decision node on A_{g}; Let the possible values of A_{g} be v_{1}, v_{2}, \dots, v_{m} . Partition D into m disjoint subsets D_{1}, D_{2}, \dots, D_{m} based on the m values of A_{g} . for each D_{j} \in {D_{1}, D_{2}, \dots, D_{m}} do if D_{j} \neq = \emptyset then create a branch (edge) node T_{j} for v_{j} as a child node of T; decisionTree (D_{j}, A - {A_{g}}, T_{j}) endif endfor endif endif endif

El éxito de la construcción del árbol depende de la evaluación de la pureza. Dos de las funciones de impureza más utilizadas son la ganancia de información y la tasa de ganancia de información. Ambas están basadas en la entropía:

$entropy (D) = - \sum_{j = 1}^{∣ C ∣} P r (c_{j}) lo g_{2} P r (c_{j})$

Usando entropía:

impurityEval-1 (D) : entropy (D) impurityEval-2 (D, A_{i}) : entropy_{A_{i}} (D) gain (D, A_{i}) gainRatio (D, A_{i}) = - j = 1 \sum ∣ C ∣ P r (c_{j}) lo g_{2} P r (c_{j}) = - j = 1 \sum v \frac{∣ D _{j} ∣}{∣ D ∣} \times entropy (D_{j}) = entropy (D) - entropy_{A_{i}} (D) = \frac{gain ( D , A _{i} )}{- \sum _{j = 1}^{s} ( \frac{∣ D _{j} ∣}{∣ D ∣} \times lo g _{2} \frac{∣ D _{j} ∣}{∣ D ∣} )}

La ganancia de información es buena medida siempre que no haya un atributo con muchos valores distintos en proporciones muy distintas, ya que es sensible a valores “sobre-representados”. En esos casos conviene usar la tasa de ganancia de información.

Cambiar la función de impureza puede afectar los árboles generados.

El algoritmo C4.5 puede operar con atributos continuos si éstos son particionados en intervalos, considerando a cada intervalo como un valor discreto. También se requieren algunas otras modificaciones al algoritmo, ya que un mismo atributo continuo podría aparecer varias veces en el mismo árbol si es que en cada nodo decisión se crean nuevos intervalos, particionando aún más al espacio de datos. Desde el punto de vista geométrico un árbol de decisión construido con atributos continuos representa un particionamiento del espacio de datos.

💾 Apuntes de ISI

Explorador

Árboles de Decisión

Vista Gráfica