post list
QuantDare
categories
artificial intelligence

Random forest: many is better than one

xristica

artificial intelligence

Non-parametric Estimation

T. Fuertes

artificial intelligence

Classification trees in MATLAB

xristica

artificial intelligence

Applying Genetic Algorithms to define a Trading System

aparra

artificial intelligence

Graph theory: connections in the market

T. Fuertes

artificial intelligence

Data Cleansing & Data Transformation

psanchezcri

artificial intelligence

Learning with kernels: an introductory approach

ogonzalez

artificial intelligence

SVM versus a monkey. Make your bets.

P. López

artificial intelligence

Clustering: “Two’s company, three’s a crowd”

libesa

artificial intelligence

Euro Stoxx Strategy with Machine Learning

fjrodriguez2

artificial intelligence

Visualizing Fixed Income ETFs with T-SNE

j3

artificial intelligence

Hierarchical clustering, using it to invest

T. Fuertes

artificial intelligence

Markov Switching Regimes say… bear or bullish?

mplanaslasa

artificial intelligence

“K-Means never fails”, they said…

fjrodriguez2

artificial intelligence

What is the difference between Bagging and Boosting?

xristica

artificial intelligence

Outliers: Looking For A Needle In A Haystack

T. Fuertes

artificial intelligence

Machine Learning: A Brief Breakdown

libesa

artificial intelligence

Stock classification with ISOMAP

j3

artificial intelligence

Sir Bayes: all but not naïve!

mplanaslasa

artificial intelligence

Returns clustering with k-Means algorithm

psanchezcri

artificial intelligence

Confusion matrix & MCC statistic

mplanaslasa

artificial intelligence

Reproducing the S&P500 by clustering

fuzzyperson

artificial intelligence

Random forest vs Simple tree

xristica

artificial intelligence

Clasificando el mercado mediante árboles de decisión

xristica

artificial intelligence

Redes Neuronales II

alarije

artificial intelligence

Análisis de Componentes Principales

j3

artificial intelligence

Vecinos cercanos en una serie temporal

xristica

artificial intelligence

Redes Neuronales

alarije

artificial intelligence

Caso Práctico: Multidimensional Scaling

rcobo

artificial intelligence

Árboles de clasificación en Matlab

xristica

18/08/2014

1
Árboles de clasificación en Matlab

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:

nn (3)

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.

mat1

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:

nn (8)

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:

mat2

¿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.

viewtree

mat3

¿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.

mat4

¿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:

treeform

Un nodo puro tiene índice de Gini 0.

mat5

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.

mat6

¿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.

mat7

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:

mat8

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

Tweet about this on TwitterShare on LinkedInShare on FacebookShare on Google+Email this to someone

add a comment

[…] Teoría y herramientas… podéis encontrarlas aquí: Árboles de clasificación en Matlab […]

wpDiscuz