clasificadores : Árboles de decisión, ID3

En esta entrada hablaré de mi clasificador preferido, este es el árbol de decisión, y ello es debido a que a diferencia de los demás clasificadores, los árboles de decisión nos entregan un modelo visual, es decir, algo que podemos entender sin ninguna ecuación, incluso sin conocer matemáticas,esto último es bueno, por que, a decir, podemos mostrar el modelo a otros departamentos, ellos lo entenderían y pueden seguirlo incluso sin un ordenador, amen de que es fácil implementarlo, no es costoso computacionalmente crear el modelo, además, es muy rápido al momento de ponerlo en el campo de acción.

A continuación muestro un ejemplo de un árbol de decisión[1]:

Dentro de las bondades con que cuentan estos algoritmos están:

• Determinan aquellos atributos que aportan información relevante al sistema
• Establece jerarquías de importancia entre los atributos
• Rápido clasificando nuevos elementos
• No tiene gran coste computacional la creación del modelo
• El modelo puede ser modificable o pulido por un experto una vez creado (como en las redes bayesianas)
• Entendible e interpretable fácilmente
• El modelo se puede entender como un conjunto de reglas si , no, entonces

Siendo sus desventajas

• Suele favorecer a aquellos atributos con muchos valores
• Débil contra información ruidosa o que genere conflictos en la base de datos
• Usualmente es necesario discretizar los atributos continuos
• Puede crear árboles muy grandes que intentan explicar incluso el ruido y las partes aisladas(outliers o casos raros que sin embargo son correctos)

A grandes rasgos este clasificador es especialmente útil cuando los ejemplos a partir de los que se desea aprender se puedan representar mediante atributos y valores, así como cuando se desea tener un modelo gráfico que clasifique la información, sin embargo, no resultan adecuados cuando la estructura de los ejemplos es variable, es decir, cuando no conocemos todos los valores posibles o límites máximos y mínimos de los atributos. También presentan inconvenientes con información incompleta.

Existen diversas y variadas formas de construirlos, la tendencia general es utilizar una fórmula que nos indique que atributo desplegar, como tal, las fórmulas mas utilizadas son las siguientes:

Entropia[2] : Describe la tendencia al orden en un sistema (también conocida como medida de incertidumbre). Básicamente determina en base a una situación, la probabilidad de que ocurra cada uno de los casos subsecuentes posibles.Va de 0 a 1, en donde 0 es el orden total y 1 el desorden total. Usualmente para los árboles de decisión suele utilizarse su forma binaria (al menos una forma de expresarla):

GINI[3]: Representa la medida de desigualdad de un sistema, una forma de medirlo es con la siguiente fórmula:

Y el algoritmo mas común es el siguiente[4]:

Pues bien, manos a la obra, vamos a crear un árbol de decisión utilizando la fórmula de entropia arriba descrita, y la  conocida base de datos de jugar golf:

Día	Temperatura	Humedad	Viento	Jugar
Soleado	caliente	alta	débil	no
Soleado	caliente	alta	fuerte	no
nublado	caliente	alta	débil	si
lluvioso	templada	alta	débil	si
lluvioso	fría	normal	débil	si
lluvioso	fría	normal	fuerte	no
nublado	fría	normal	fuerte	si
Soleado	templada	alta	débil	no
Soleado	fría	normal	débil	si
lluvioso	templada	normal	débil	si
Soleado	templada	normal	fuerte	si
nublado	templada	alta	fuerte	si
nublado	caliente	normal	débil	si
lluvioso	templada	alta	fuerte	no

Bien, la clase es “Jugar”, entonces comencemos a determinar cual será nuestro nodo raíz,para eso aplicaremos la formula de la entropia a cada uno de los atributos (día, temperatura, humedad, viento) y utilizaremos la siguiente fórmula que nos va a expresar nuestra ganancia de información:

Cabe mencionar que existen muchas fórmulas para calcular la ganancia de la información con respecto a la entropia, simplemente utilicé la mas sencilla.

Pues bien, al trabajo, comencemos con el atributo de día, entonces construimos la siguiente subtabla:

Día	Jugar (si)	Jugar (no)
soleado	2	3
nublado	4	0
lluvioso	3	2

Básicamente , esta tabla nos indica que el atributo día tiene tres estados (soleado, nublado y lluvioso)

y que cada uno de dichos estados aparece distribuido un número x de veces para cada valor de la clase, ejemplo : soleado aparece enlazado 2 veces a la clase “Jugar:Si” y 3 veces a la clase “jugar:No”.

Bien ahora calculemos la entropia para día(soleado=>si):

y para día(soleado => no):

entonces día(soleado) = 0.5287 + 0.44217 = 0.9709

Ahora debemos calcular los demás estados de día (nublado y lluvioso) de la misma manera y obtendremos la siguiente tabla:

Día	Jugar (si)	Jugar (no)	Total casos	Entropia jugar(si)	Entropia jugar(no)	Entropia
soleado	2	3	5	0.528771238	0.4421793565	0.9709505945
nublado	4	0	4	-0	0	0
lluvioso	3	2	5	0.4421793565	0.528771238	0.9709505945
					Ganancia	0.6935

Recordando que ganancia la obtenemos de (0.9709 + 0 + 0.97095)/14 en donde 14 es el número total de casos.

Bien entonces tenemos que el atributo de Día nos da una ganancia de 0.6935. Ahora solo nos resta calcular los demás atributos y obtendremos las siguientes tablas:

Temperatura	Jugar (si)	Jugar (no)	Total casos	Entropia jugar(si)	Entropia jugar(no)	Entropia
caliente	2	2	4	0.5	0.5	1
fría	3	1	4	0.3112781245	0.5	0.8112781245
templada	4	2	6	0.3899750005	0.5283208336	0.9182958341
					Ganancia	0.911063393

Humedad	Jugar (si)	Jugar (no)	Total casos	Entropia jugar(si)	Entropia jugar(no)	Entropia
alta	3	4	7	0.5238824663	0.4613456697	0.985228136
normal	6	1	7	0.1906220754	0.4010507032	0.5916727786
					Ganancia	0.788450457

Viento	Jugar (si)	Jugar (no)	Total casos	Entropia jugar(si)	Entropia jugar(no)	Entropia
no	6	2	8	0.3112781245	0.5	0.8112781245
si	3	3	6	0.5	0.5	1
					Ganancia	0.892158928

Y como podemos observar nuestro atributo ganador es “día” debido a que presentó el número mas pequeño y recordando en entropìa mientras mas cercano al cero sea mas tendencia al orden tenemos y es lo que buscamos, entonces ya podemos construir las primeras ramas del árbol y quedaría de la siguiente manera:

Ahora bien, como observamos en nublado la entropia marco 0, esto quiere decir que no necesitamos mas información, si el día es nublado se jugará sin importar los demás atributos y sus valores, sin embargo, no ocurre lo mismo para soleado y lluvioso, ahora deberemos determinar para cada estado del día (a excepción de nublado) cual sera el atributo que sigue.

Tomemos a soleado como nuestro punto a seguir, tenemos la siguiente subtabla:

Día	Temperatura	Humedad	Viento	Jugar
Soleado	caliente	alta	débil	no
Soleado	caliente	alta	fuerte	no
Soleado	templada	alta	débil	no
Soleado	fría	normal	débil	si
Soleado	templada	normal	fuerte	si

que es básicamente aquellos datos que correspondan a día=>soleado, ahora repetiremos los pasos, obviamente solo necesitamos calcular los atributos que no son día(temperatura, humedad y viento)

Tenemos entonces que para Temperatura =>caliente:

ahora computamos todos los valores de la clase y obtenemos la siguiente tabla:

Temperatura	Jugar (si)	Jugar (no)	Total casos	Entropia jugar(si)	Entropia jugar(no)	Entropia
caliente	0	2	2	0	0	0
templada	1	1	2	0.5	0.5	1
fría	1	0	1	0	0	0
					Ganancia	0.4

Y ahora haremos lo mismo para los demás atributos:

Humedad	Jugar (si)	Jugar (no)	Total casos	Entropia jugar(si)	Entropia jugar(no)	Entropia
alta	0	3	3	0	0	0
normal	2	0	2	0	0	0
					Ganancia	0

Viento	Jugar (si)	Jugar (no)	Total casos	Entropia jugar(si)	Entropia jugar(no)	Entropia
débil	1	2	3	0.5283208336	0.3899750005	0.9182958341
fuerte	1	1	2	0.5	0.5	1
					Ganancia	0.9509775

Y bueno, aquí tenemos un ganador claro, en este caso es Humedad, ya que su entropia es cero, es decir, es orden total, entonces ahora construimos una rama mas del árbol y no queda de la siguiente manera:

Una vez que terminamos soleado nos enfocaremos en la rama de día(lluvioso), como tal tenemos la siguiente subtabla:

Día	Temperatura	Humedad	Viento	Clase
lluvioso	templada	alta	débil	si
lluvioso	fría	normal	débil	si
lluvioso	fría	normal	fuerte	no
lluvioso	templada	normal	débil	si
lluvioso	templada	alta	fuerte	no

y al igual que en soleado calculamos la entropia para cada atributo, entonces obtendremos las siguientes tablas:

Temperatura	Jugar (si)	Jugar (no)	Total casos	Entropia jugar(si)	Entropia jugar(no)	Entropia
caliente	0	0	0	0	0	0
templada	2	1	3	0.3899750005	0.5283208336	0.9182958341
fría	1	1	2	0.5	0	0.5
					Ganancia	0.7509775

Humedad	Jugar (si)	Jugar (no)	Total casos	Entropia jugar(si)	Entropia jugar(no)	Entropia
alta	1	1	2	0	0.5	0.5
normal	2	1	3	0.3899750005	0	0.3899750005
					Ganancia	0.433985

Viento	Jugar (si)	Jugar (no)	Total casos	Entropia jugar(si)	Entropia jugar(no)	Entropia
débil	3	0	3	-0	0	0
fuerte	0	2	2	0	-0	0
					Ganancia	0

Y ahora tenemos como claro ganador a viento, entonces podemos concluir nuestro árbol:

Como podemos observar el atributo de temperatura no es requerido en el modelo, eso significa que no aporta nada en términos de orden al modelo de clasificación y es aquí en donde se visualiza una de las grandes ventajas de este clasificador.

Como comente en un principio existen muchas formas de generar un árbol, inclusive existe métodos aposteriori que intentar brindarle una mayor calidad al modelo, un ejemplo es la poda, que intenta eliminar ramificaciones duplicadas,la siguiente imagen muestra un ejemplo de ello[5]:

Incluso existen algoritmos para meter ramificaciones con decisiones[5]:

Pero bueno es un tema realmente extenso, prometo abordar árboles mas complejos en futuras entregas, por lo pronto espero les haya gustado esta.

[1]http://si2008.wikispaces.com/%C3%81rboles+de+decisi%C3%B3n, consultado el 19/04/2014

[2]http://en.wikipedia.org/wiki/Entropy, consultado el 19/04/2014

[3]http://es.wikipedia.org/wiki/Coeficiente_de_Gini, consultado el 19/04/2014

[4]http://es.wikipedia.org/wiki/Algoritmo_ID3, consultado el 19/04/2014

[5]Addison Wesley,Introduction to data mining, Pang-Ning Tan

Clasificadores discriminantes, discriminante de Fisher

Bien, en esta entrada hablaré acerca de algunas de las técnicas de discriminantes que existen. Debo aclarar que este  es uno de los temas en donde se encuentra más teoría que práctica en la web, haciendo realmente en ocasiones difícil de entender la idea general (en la mayoría de los casos se encontraran con varias fórmulas sin un ejemplo concreto de su utilización u explicación de las variables que la forman). El motivo de esto, quiero suponer, es porque este tipo de clasificadores se basan en una idea en general, que es la de discriminar a las clases, más que a un algoritmo en particular.

La idea general de este tipo de clasificadores es, una vez teniendo conocimiento de nuestros datos, intentar crear un modelo que nos permita separar a nuestra clases, usualmente este modelo es una recta (discriminantes lineales), una curva (discriminantes no lineales) , un circulo (ídem) etc.

Por ejemplo supongamos que tenemos la gráfica de  dos dimensiones de alguna tabla de una base y que las mismas se ven de la siguiente manera:

Bien, si quisiéramos diferenciar a los círculos verdes de los azules, podríamos trazar un círculo y diríamos que todo lo que este dentro del círculo es azul y fuera del mismo es verde:

Claro, es un poco raro encontrarse con este tipo de distribuciones, usualmente nos encontraremos con datos de la siguiente manera (al menos cuando sigan una distribución Gaussiana):

Para este tipo de datos basta con trazar una línea (ese será nuestro modelo o discriminante) para diferenciar a nuestros datos:

Pero en la práctica, tendremos bases de datos con más de tres atributos, lo cual indica que no podremos visualizarlos en una gráfica y entonces no podremos colocar nuestro discriminante de forma manual, es aquí en donde entran los métodos desarrollados para este tipo de casos.

En esta entrada solo me basaré en los discriminantes más utilizados, los lineales(son los más utilizados por que sirven para discriminar poblaciones que siguen una Gaussiana).

Bien existen muchas técnicas para poder trazar una o varias líneas que nos puedan separar a nuestros datos, entre ellas tenemos algunos métodos que son parecidos al siguiente algoritmo:

Elegir un modelo aleatorio L

Para cada elemento “a” de una población ” A” hacer

                Si el modelo L NO clasifica bien al elemento “a” entonces

                               Modificar el modelo L para que pueda clasificar al elemento a

Termina Si

Termina Para

Salida el modelo L

Si, lo se, es un poco burdo el algoritmo, pero es la idea básica de cómo funcionan la mayoría de los métodos que se encontrarán, claro el problema principal está en modificar el modelo para que pueda clasificar bien a la entrada que se le está dando.

Pero los discriminantes lineales no son tan ciegos y existen varias técnicas que nos permiten escoger (algunas de ellas mediante modelos estadísticos)  la línea (o el plano si es que hablamos de más de dos atributos) con una simple fórmula, ejemplos de esto es el discriminante de Fisher y la máquina de soporte de vectores.

Bien enfocaremos nuestra energía en el discriminante de Fisher.

Este discriminante es muy poderoso, se usa entre otras cosas en imágenes, sistemas de información médica y un sin fin de cosas. Utiliza información de variables estadísticas para poder trazar el modelo que nos servirá para discriminar nuestras clases. Su regla de clasificación es la siguiente:

Clasifica al grupo 1 si:

W'X() < W'((VectorMediasClase1 + VectorMediasClase2) / 2  )

En donde:

• W= Sw^-1  (VectorMediasClase1  -  VectorMediasClase2);
• W’ = transpuesta de W
• Sw = ((n1 -1) / n1 + n2 -2) S1 +  ((n1 -1) / n1 + n2 -2  ) S2
• S1 , S2 = Matriz de covarianzas para la clase 1 y la clase 2
•  n1,n2 = cantidad de elementos de la clase 1 y cantidad de elementos de la clase 2

Cabe mencionar que a Sw se le conoce como matriz de intra-grupos combinada

Pues bien manos a la obra. 

Para el ejemplo clasificaré a la base de datos iris, en particular clasificaré las clases versicolor y setosa. Primero debo de obtener su vector de medias para cada uno, esta base de datos cuenta con  4 atributos, entonces los vectores de medias quedan de la siguiente manera:

VectorMedias Setosa

5.0059999999999993

3.4180000000000006

1.464

0.24399999999999991

  

VectorMediasVersicolor

5.936

2.7700000000000005

4.26

1.3259999999999998

Ahora obtendremos la matriz de covarianzas para setosa (S1):

0.12424898	0.10029796	0.01613878	0.01054694
0.10029796	0.14517959	0.01168163	0.01143673
0.01613878	0.01168163	0.03010612	0.00569796
0.01054694	0.01143673	0.00569796	0.01149388

Y para versicolor (S2):

0.12424898	0.10029796	0.01613878	0.01054694
0.10029796	0.14517959	0.01168163	0.01143673
0.01613878	0.01168163	0.03010612	0.00569796
0.01054694	0.01143673	0.00569796	0.01149388

Ahora computamos Sw:

Sw = ((50 -1) / 50 + 50 -2) S1 +  ((50 -1) / 50 + 50 -2  ) S2

Sw = 

0.12424898	0.10029796	0.01613878	0.01054694
0.10029796	0.14517959	0.01168163	0.01143673
0.01613878	0.01168163	0.03010612	0.00569796
0.01054694	0.01143673	0.00569796	0.01149388

Vamos por W:

W =

 

-2.8464883

-18.4136903

21.2317579

32.5898589

W’=

-2.8464883

-18.4136903

21.2317579

32.5898589

 

¡Uf! ya casi, ahora que ya tenemos todas las partes, es hora de ensamblar nuestro modelo :

Modelo = W' ((VectorMediasClase1 + VectorMediasClase2) / 2  ) =

Modelo = 42.462542

Y Listo tenemos nuestro modelo ahora, ya podemos clasificar nuevas entradas tomando en cuenta lo siguiente:

• Si W’X() (en donde X() es la entrada a clasificar) > 42.462542 entonces está por encima de la línea (plano etc.)
  Si W’X() (en donde X() es la entrada a clasificar) < 42.462542 entonces está por debajo de la línea (plano etc.)

Saber que clase está arriba y que clase está por debajo no es nada difícil, basta con proporcionar un  dato del conjunto con el cual se creó el modelo y determinar cuál es arriba y cual abajo, en este caso versicolor está encima y setosa se ubica debajo de nuestro plano.

Tomemos como ejemplo la siguiente entrada:

Sepal length	Sepal width	Petal length	Petal width
7	3.8	1.7	0.4

Ahora computamos:

W’X(7 , 3.8, 1.7, 0.4) = -40.767

Entonces decimos que la entrada pertenece a setosa ya que  ser menor -40.767 < 42.46 se encuentra por debajo de la linea.

Hasta aquí todo excelente, pero ¿Qué pasa si tengo más de 2 clases?, bueno pues es cuestión de crear más líneas, por ejemplo, si tenemos 3 clases, crearemos dos planos, primero detectamos en el modelo que explique la clase que se ubica en el fondo, si resulta ser de dicha clase bueno allí paramos, pero si no, entonces ahora computamos el segundo modelo y determinamos su clase, es decir, modelo1 explica las clases 1 y 2, modelo2 explica las clases 2 y 3. Dada una entrada, con el modelo1 checamos a que clase pertenece, si pertenece a la clase uno , allí termina, si no, entonces aplicamos el modelo2 para determinar si es clase 2 o clase 3.

A continuación muestro una imagen que muestra lo que acabo de comentar, cabe aclarar que solo grafiqué tres parámetros de las clases de la base de datos iris, y dibujé los planos que representan al modelo creado: