Fermín Pitol, Blog de Inteligencia Artificial en Español: 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]: