Los árboles de clasificación sirven, como su propio nombre indica, para resolver problemas de clasificación.

El objetivo de cualquier problema de este tipo es la asignación de un objeto a una de las diversas categorías o clases especificadas.

La clasificación es una técnica muy útil y se extiende a muchísimos campos, como puede ser el reconocimiento de patrones.

Un árbol consiste esencialmente en un conjunto secuencial de condiciones y acciones que relacionan unos determinados factores con un resultado o decisión. Es un método de clasificación supervisada, lo que quiere decir que cuenta con datos ya clasificados a priori de los que extraerá el conocimiento.

En primer lugar el algoritmo analiza los datos proporcionados en busca de patrones y usa los resultados de este análisis para definir la secuencia y condiciones para la creación del modelo de clasificación.

En este post es repasaremos los principales conceptos teóricos y los traduciremos a Matlab, que cuenta con las herramientas necesarias para trabajar con árboles en su Statistics Toolbox. Espero que os sea útil.

¿Qué es un árbol de decisión?

Un árbol de decisión es una forma de representar el conocimiento obtenido en el proceso de aprendizaje inductivo. Se crea una partición del espacio a partir de un conjunto de prototipos y la estructura resultante es el árbol.

Los prototipos serán una serie de características o atributos, las variables explicativas:

Creamos la matriz “a” de atributos en Matlab. Definiremos la función attributes para recoger las características que queremos tener en cuenta en el árbol.

Si trabajamos con series financieras son ejemplos de atributos la volatilidad, la eficiencia del movimiento, etc.

Cada conjunto de ellos tiene asignada una respuesta o clase, lo que pretendemos explicar. Esta clasificación se ha asignado utilizando cierta información futura, por lo que podemos clasificar datos históricos, pero nos es imposible hacerlo con el dato actual:

En función del tipo de clase se distinguen árboles de clasificación, clase binaria, y árboles de regresión, clase continua. Nos centraremos en las clases binarias, que es condición para la función de Matlab que utilizaremos. Clases binarias son, por ejemplo, que el precio suba o baje, que el precio suba más que un determinado valor o no, que el mercado sea lateral o haya tendencia.

Etiquetamos estas clases como -1 y 1 de aquí en adelante. Definimos nuestra función classes con el vector de respuestas para cada dato de x:

¿Cómo es un árbol de decisión?

Un árbol está formado por nodos:

Nodos internos: cada nodo interior contiene una pregunta sobre un atributo concreto (node = <attribute, value>) y da lugar a dos hijos, uno por cada posible respuesta, clasificación o decisión. Las preguntas serán del tipo ¿a(i)>=j?

Nodos terminales (hojas): son los que están asignados a una única clase, aquellos en los que termina el árbol. La complejidad del árbol viene determina por su número de hojas.

¿Cómo se construye?

La construcción de un árbol es la fase de aprendizaje del método. Consiste en analizar el conjunto de prototipos disponibles, el conjunto de atributos, y obtener unas reglas lógicas que se ajustan a la clasificación conocida, a las clases que están asignadas a cada vector (a1,… as).

El proceso de construcción es recursivo:

1. Se analizan todas las posibles particiones (attribute, value) y se toma de todas ellas la que da lugar a una mejor separación.
2. Se aplica la separación óptima.
3. Se repite el paso 1 con los nodos hijos, únicamente con los que no sean hojas.

¿Todas las particiones?

Sí, todas. Para cada uno de los atributos se toman todos los valores de sus observaciones.

Las particiones se definen tomando como corte el punto medio entre cada dos de esos valores.

¿Cuál es la separación óptima?

La mejor separación es aquella que divide los datos en grupos en los que predomina una única clase (nodo hijo 1 -> -1 y nodo hijo 2 -> 1).

Se utilizan las llamadas medidas de impureza y, de todas las particiones posibles, elegiremos aquella que minimiza la impureza de los dos nodos hijos.

Comentaremos el índice de diversidad de Gini, aunque existen muchas otras medidas de impureza, entre las que también destacan la entropía y la ganancia de información.

La impureza se calcula como el producto de las probabilidades de pertenecer a una clase o a la otra.

Cuando estas probabilidades están muy igualadas significa que la separación no está en línea con la clasificación definida por el vector de clases. Cuanto más igualadas estén las probabilidades, mayor impureza y mayor índice de Gini.

El índice de Gini de un nodo aij=(attribute i, value j) se calcula sumando las impurezas de los nodos hijos:

Un nodo puro tiene índice de Gini 0.

De esta forma, queda establecida la prioridad de los atributos. Es posible que algunas de las características que habíamos elegido queden excluidas de la definición del árbol. Debemos interpretar este hecho como que el atributo es irrelevante, pues la decisión es independiente del valor que tome el mismo.

De igual manera, los atributos que quedan en los niveles inferiores también tienen menor relevancia.  

Analizando la estructura del árbol podemos determinar el interés de cada una de las variables explicativas que habíamos elegido. 

¿Cuándo un nodo es hoja?

Si el nodo contiene una única clase, entonces es puro y el proceso termina. Sin embargo, es habitual utilizar criterios adicionales de parada como, por ejemplo, que la cantidad de datos contenidos en el nodo ya sea demasiado pequeño, en cuyo caso el desarrollo de su clasificación no se considera relevante.

Además, no se admiten particiones si la impureza de los hijos no mejora la impureza del padre: si llegados a un nodo, cualquier separación posible da lugar a nodos hijos con un número demasiado pequeño de datos, tampoco se efectúa la partición.

¿Cómo se utiliza?

Una de las grandes ventajas de los árboles de decisión es que son muy intuitivos y fáciles de aplicar.

La aplicación del árbol se conoce como fase de clasificación y consiste en asignar la clase que corresponde a un patrón x, independiente del conjunto de aprendizaje.

Una vez creado es sencillísimo encontrar la clase desconocida de un nuevo dato x con características (a1,…. as). Basta con contestar las preguntas planteadas en cada nodo y seguir el camino impuesto por nuestro árbol, hasta encontrar un nodo hoja. Se predice la clase c de x como la clase mayoritaria en la hoja a la que pertenece x.

El porcentaje de datos con clase mayoritaria en la hoja de x se entiende como la probabilidad de acierto de la asignación.

El resultado del modelo de clasificación proporcionado por el árbol no es únicamente una decisión, sino también la seguridad de la misma, pues conocemos las probabilidades de cada una de las posibles alternativas:

Podéis encontrar una aplicación práctica aquí: Clasificando el mercado mediante árboles de decisión.

Read this post in English!