next up previous contents
Next: 7.3 Selección de las Up: 7. Arboles de Clasificación Previous: 7.1 Introducción

   
7.2 Construcción del árbol de clasificación

La construcción del árbol de decisión constrituye la fase de aprendizaje. Entre los mecanismos de aprendizaje constituye el más complejo de los estudiados hasta ahora. Las líneas generales para su construcción pueden resumirse en los siguientes puntos, de acuerdo a un esquema recursivo:

1.
El avance está basado en la partición de un nodo de acuerdo a alguna regla, normalmente evaluando una condición sobre el valor de alguna variable:
Los prototipos que verifican la condición se asignan a uno de los dos nodos hijo (normalmente el izquierdo) y los restantes, al otro.
Cuando un nodo se particiona, pasa a ser un nodo intermedio.

2.
El caso base o condición de parada tiene como objetivo detener el proceso de partición de nodos. Cuando se verifica la condición de parada en un nodo, éste es un nodo hoja.

Los prototipos asociados a un nodo hoja constituyen un agrupamiento homogéneo, por lo que al nodo se le asigna una etiqueta.

En ocasiones, se poda el árbol resultante utilizando alguna regla de poda.

En este esquema quedan muchos conceptos por determinar:

1.
¿De qué forma se hacen las particiones y se selecciona la mejor de entre las posibles en cada momento?, concretamente,

1.1
¿Cómo se formulan las preguntas?, o de otra manera, ¿De qué tipo son las condiciones a evaluar para formar una partición?
1.2
¿Qué criterio se adopta para seleccionar la mejor partición?

2.
¿Cual es el criterio para determinar que un nodo es homogéneo?, o de otra manera, ¿Cúando se debe declarar un nodo como terminal, o por el contrario, continuar su división?

3.
¿Cómo asignar una etiqueta a un nodo terminal?

Las respuestas a estas preguntas se encuentran en las secciones siguientes, donde utilizaremos la metodología de CART para concretarlas. Antes, mostraremos un ejemplo detallado del proceso de construcción de un árbol de decisión mediante CART.

 



Ejemplo  

En este ejemplo mostramos el proceso que podría seguirse para construir un árbol de decisión a partir de un conjunto de prototipos pertenecientes a tres clases y con patrones de dimensión 25 con valores no categóricos. El conjunto de aprendizaje consta de N = 300 prototipos de manera que Ni = 100, i = 1, 2, 3.

1.
Construcción del nodo raiz.

Inicialmente se asignan todos los prototipos a la raíz (figura 82) de manera que éste contiene 100 prototipos de cada clase. De manera informal podemos adelantar que esta situación, en la que todas las clases están igualmente representadas, corresponde a la situación de máxima impureza: ninguna clase ``domina'' sobre las otras.


  
Figura 82: Nodo raiz del árbol
\begin{figure}
\centerline{
\psfig{figure=figures_3/const_1.eps,height=0.8cm}}
\end{figure}



2.
Partir el nodo raiz.

Se trata de seleccionar la mejor partición del nodo raiz entre todas las posibles. Este proceso puede descomponerse en tres pasos:

2.1.
Examinar todas las particiones de la forma ¿X1 < C? donde:

min (X1) $\displaystyle \leq$ C $\displaystyle \leq$ max (X1)

Por ejemplo, sea C = 1.1. Los prototipos para los que se verifica que X1 < 1.1 van al nodo izquierdo, y los otros, al derecho (figura 83.A).

Una vez examinadas todas las particiones para la variable X1, se considera la mejor partición asociada a esta variable. Por ejemplo, sea ésta ¿ X1 < 10.7?.

2.2.
Repetir el proceso anterior para X2, X3,..., X25

2.3.
Seleccionar la mejor partición entre las mejores de X1,..., X25

Por ejemplo, si la mejor partición se consigue para la variable X8 y la partición es la asociada a la condición ¿X8 < 3.2?, el árbol resultante se muestra en la figura 83.B.


  
Figura 83: Particiones asociadas a: A) ¿X1 < 1.1? B) ¿X8 < 3.2?
\begin{figure}
\centerline{
\psfig{figure=figures_3/const_2y3.eps,height=3cm}}
\end{figure}

Si comparamos los árboles de decisión de la figura 83 observamos que el primero (A), aún siendo más puro que el de la figura 82, las proporciones de las clases en cada nodo no son determinantes, en el sentido de que ninguna destaca claramente sobre las otras. En el segundo (B) estas proporciones son más determinantes, haciendo que: a) la clase 3 esté muy por debajo de las clases 1 y 2 en el nodo izquierdo y b) que la clase 3 sea dominate en el nodo derecho.



3.
Repetir el paso 2 para los nodos hijo.

Por ejemplo, sea ¿ X3 < - 0.8? la mejor partición para el nodo izquierdo y ¿ X1 < 17.9? la mejor para el derecho. En la figura 84 mostramos el árbol resultante de estas particiones. Se han numerado los nodos para facilitar la discusión posterior.


  
Figura 84: Árbol resultante de partir el árbol de la figura 83.B
\begin{figure}
\centerline{
\psfig{figure=figures_3/const_4.eps,height=4cm}}
\end{figure}

Estas particiones hacen que los nodos 4 y 5 diferencien claramente las clases 2 y 3, respectivamente, mientras que en los nodos 6 y 7 se diferencian las clases 2 y 3, respectivamente.

Observar que las particiones efectuadas han ido ``definiendo'' una clase mayoritaria en cada nodo resultante, o expresado de otra manera, han ido aumentando la pureza de los nodos asociados a cada partición. Este proceso de división puede continuar para cada uno de los 4 nodos que hemos obtenido o, para cada caso, plantearse si debemos detenernos.

4.
¿Parada?

Establecer el criterio de parada para obtener un buen árbol de decisión no es sencillo. No obstante, hasta que estudiemos la manera adecuada de hacerlo estableceremos un criterio sencillo basado en la pureza del nodo. Uno muy simple puede ser el siguiente: un nodo se declarará terminal, y en consecuencia no se dividirá si la clase dominante tiene más del 60% de los prototipos asociados a ese nodo.

En este ejemplo, y considerando el árbol de la figura 84, si N(t) es el número total de prototipos asociados al nodo t y Ni(t) es el número de prototipos de clase i asociados al nodo t,

En este caso, se detendría la división de los nodos 4, 5 y 7, mientras que el nodo 6 continuaría su división como indicamos en los pasos 2 y 3. El resultado de la división de este nodo se muestra en la figura 85.

Podemos plantearnos si era necesaria la división de los nodos 1, 2 y 3. Procedemos como para los nodos 4, 5, 6 y 7.

Así, hicimos bien al dividir estos nodos.


  
Figura 85: Árbol resultante al declarar los nodos 4, 5 y 7 como hojas.
\begin{figure}
\centerline{
\psfig{figure=figures_3/const_5.eps,height=4cm}}
\end{figure}

Finalmente, si el resultado de partir el nodo 6 es el mostrado en la figura 86.A, es fácil comprobar que los nodos 6.1 y 6.2 no requieren más particiones (figura 86.B).


  
Figura 86: A) Árbol resultante de partir el nodo 6 del árbol de la figura 85. B) Árbol final
\begin{figure}
\centerline{
\psfig{figure=figures_3/const_6.eps,height=5.5cm}}
\end{figure}



next up previous contents
Next: 7.3 Selección de las Up: 7. Arboles de Clasificación Previous: 7.1 Introducción

2000-11-30