Árbol de decisión (modelo de clasificación ID3)

Modelo de clasificación también conocido como ID3 que significa "inducción mediante árboles de decisión" que fue desarrollado por J. Ross Quinlan, capaz de tomar decisiones con gran precisión. Sistema de aprendizaje supervisado que aplica la estrategia "divide y vencerás" para hacer la clasificación, implementando métodos y técnicas para la realización de procesos inteligentes, representando así el conocimiento y el aprendizaje, con el propósito de automatizar tareas.

En la actualidad es ya común oír que la palabra “inteligente”, o algún sinónimo de esta, se aplique a máquinas, sistemas, procesos y hasta a productos de uso doméstico, dados a conocer en todo el mundo, y cuyo origen se debe al surgimiento de la Inteligencia Artificial y de los Sistemas Expertos. La Inteligencia Artificial es una rama de las ciencias computacionales que trata de modelar el comportamiento humano por medio de la creación de sistemas que sean capaces de imitar la comprensión humana y que también sean capaces de aprender y reconocer. Entre las aplicaciones más comunes de esta ciencia podemos mencionar a las computadoras, los cajeros automáticos, los circuitos cerrados, los medicamentos, etc., los cuales son considerados "inteligentes" por el hecho tener mecanismos o procesos que se activan automáticamente.

Hasta la fecha la inteligencia no se ha podido definir con exactitud, pero se puede decir que es la facultad de entender o conocer, así pues podemos entonces suponer que los procesos o productos inteligentes son capaces de "entender" con que cuentan y que son capaces de lograr, es decir cómo reaccionan ante los estímulos provenientes de su medio con base en la información que perciben. Como ejemplo podemos mencionar un limpiaparabrisas de un auto que se activa automáticamente al percibir las primeras gotas de la lluvia; este proceso toma como entrada de información las gotas de la lluvia y en consecuencia toma la "decisión" de activar el limpiaparabrisas.

A todo esto podemos decir que el ser humano ha puesto parte de su conocimiento a estos procesos o productos con el fin de automatizar tareas de uso frecuente. Por naturaleza el ser humano siempre se ha dedicado a buscar nuevas y mejores formas de vida, ya sea para ahorrar tiempo, dinero, esfuerzo o simplemente para hacer más cómoda su vida; avocándose a la investigación y procurando mejores alternativas de solución a sus problemas, implementando métodos y técnicas desarrollados por él mismo para la realización de procesos inteligentes, representando así el conocimiento y el aprendizaje, con el propósito de automatizar sus tareas.

Filosofía

Así, es J. Ross Quinlan quién primero presentó el "descubrimiento de reglas por inducción desde un gran número de ejemplos" y posteriormente desarrolló el modelo ID3 que significa “inducción mediante árboles de decisión”, que también es conocido como árboles de decisión.

El ID3 permite determinar el árbol de decisión mínimo, para un conjunto de objetos. Este árbol permite que la información se mantenga en forma organizada y entendible para cualquier persona, además hace uso de una secuencia de preguntas, donde cada una de las preguntas es evaluada con el propósito de obtener la mejor respuesta posible.

Este modelo es un algoritmo de aprendizaje inductivo, es decir, busca establecer leyes o principios generales sobre la base de la observación de varios o todos los componentes de un conjunto o clase. Aplica la estrategia “divide y vencerás” para hacer la clasificación de los objetos y asociarlos a una clase, tomando en cuenta los valores de los atributos de los objetos. Un árbol de decisión toma como entradas objetos o situaciones que se caracterizan mediante un conjunto de propiedades.

El árbol proporciona como salida una “decisión” que puede ser si o no, para las funciones booleanas, aunque también es posible representar funciones con un mayor rango de salidas.

Representación de un Árbol de decisión

La salida del algoritmo ID3 se representa como un grafo en forma de árbol, cuyos componentes son:

Representación de un árbol de decisión

• Un nodo principal llamado raíz en la parte superior, de este nodo parten líneas hacia otros nodos inferiores, que a su vez, pueden hacer las veces de nodo raíz.
• Nodos terminales, como su nombre lo indica, son nodos donde termina el flujo y que ya no son raíz de ningún otro nodo. Estos nodos terminales deben contener una

respuesta, o sea, la clasificación a que pertenece el objeto que ha conducido hasta él.

• Los demás nodos representan preguntas con respecto al valor de uno de los atributos.
• Las líneas representan las posibles respuestas que los atributos pueden tomar.

Cada objeto se representa con una lista de valores el atributo y su valor, la cual constituye una descripción conjuntiva de ese objeto. El objeto debe ser etiquetado con la clase a la que pertenece.

La idea básica del ID3 es de determinar, para un conjunto de ejemplos dados, el atributo más importante, o sea, aquel que posea el mayor poder discriminatorio para dicho conjunto; este atributo es usado para la clasificación de la lista de objetos, basados en los valores asociados con él mismo. Después de haber hecho la primera prueba de atributo, esta arrojará un resultado, el cual es en sí mismo un nuevo problema de aprendizaje de árbol de decisión, con la diferencia que contará con menos ejemplos y un atributo menos, por lo que, cada atributo que se selecciona se descarta para la siguiente prueba.

En este proceso de división se pueden presentar algunos casos especiales:

• Si existen objetos con clases diferentes, entonces para separarlos, se selecciona el que tenga la mayor información.
• Si los objetos restantes son todos de una sola clase, entonces los objetos se clasifican con esa clase.
• Si no quedan atributos, pero si objetos con sus respectivas clases, entonces hay problemas. Quiere decir que la descripción de estos objetos es exactamente la misma hasta ese punto, pero su clasificación es distinta. En este caso se dice que hay ambigüedad en los datos. También sucede cuando los atributos no proporcionan la suficiente información para describir completamente la situación.

Fundamentos

El algoritmo ID3 se apoya en técnicas matemáticas y probabilísticas; introduce el concepto de entropía, la cual es una medida de incertidumbre o de desorden, y es usado para ayudar a decidir qué atributo debe ser el siguiente en seleccionarse. En general, un atributo que puede ayudar a discriminar más objetos, tiende a reducir más la entropía, y por tal motivo, debe ser seleccionado como un nodo de prueba o de selección para la siguiente subdivisión.

Para calcular la entropía de n clases se utiliza la fórmula:

${\text{Entropia}}(S)=\sum _{i=1}^{n}-p_{i}\log _{2}p_{i}$

Donde:

S: es una colección de objetos

P_i : es la probabilidad de los posibles valores

i: las posibles respuestas de los objetos

Para una muestra homogénea la entropía es igual a 0, y por el contrario si la distribución de objetos que pertenecen a una clase es la misma, entonces la entropía es igual a 1, o sea es la máxima incertidumbre.

Si en el cálculo de la entropía se presentara una proporción 0.0, entonces se tomará la expresión 0 log₂ 0 como igual a 0.

También se introduce el concepto de ganancia de información, esta es una medida de discriminación, un indicador del siguiente atributo a ser seleccionado para continuar con el proceso de división, discriminando el atributo seleccionado entre los demás atributos aún no clasificados, y se calcula utilizando la fórmula:

${\text{Gan Inf}}(S,A)={\text{Entropia}}(S)-\sum _{v\in V(A)}{\frac {\vert Sv\vert }{\vert S\vert }}{\text{Entropia}}(Sv)$

Donde:

S : es una colección de objetos

A : son los atributos de los objetos

V(A) : Conjunto de valores que A puede tomar

Ross Quinlan define el esquema del algoritmo ID3, el cual adopta los siguientes:

1. Calcular la entropía para todas las clases.
2. Seleccionar el mejor atributo basado en la reducción de la entropía.
3. Iterar hasta que todos los objetos sean clasificados.

Diversos problemas pueden ser modelados y resueltos eficientemente con el uso de los árboles de decisión, para ello dichos problemas deben satisfacer las

siguientes características:

• La descripción de los objetos debe efectuarse en términos de parejas, el atributo y su valor.
• Cada salida debe ser distinta, es decir, los nodos terminales deben contener una respuesta única.
• Debe haber alternativas entre 2 o más cosas, para hacer posible la clasificación.
• El entrenamiento debe estar libre de errores, o sea, el problema a clasificar debe contener la información correcta, para que el resultado sea eficiente.
• El entrenamiento debe contener información suficiente para poder hacer la clasificación.

Cabe mencionar que este modelo permite predecir qué actividad tomar sobre la base de la información que se tiene, además posee una gran exactitud en su aplicación. Para ejemplificar este modelo, presentaremos una tabla de registros y su correspondiente solución en el árbol de decisión.

Clasificación de objetos mediante árboles de decisión mínimos

Alumno	ATRIBUTO			Nota
	Punt. y asist.	Participación	Aprovechamiento
1	No asiste	Media	Excelente	Exento
2	Asiste	Alta	Bueno	Exento
3	No asiste	Media	Bueno	Final
4	No asiste	Baja	Bueno	Final
5	Asiste	Alta	Regular	Final
6	Asiste	Baja	Deficiente	Extraordinario
7	No asiste	Media	Regular	Extraordinario

La rama del árbol más larga puede tener a lo mucho n preguntas, donde n es el número de atributos.

Se obtiene la ganancia de información de cada atributo:

Variable	Ganancia de información (Variable)
Puntualidad y asistencia	1.56-[4/7(1.5)+3/7(1.58)] = 0.025
Participación	1.56-[2/7(1.0)+3/7(1.58)+2/7(1.0)] = 0.311
Aprovechamiento	1.56-[1/7(0)+2/7(1.0)+3/7(0.92)+1/7(0) = 0.880

De donde:

• Información de las clases: I(C) = 1.56

${\begin{array}{l}{\text{Clase}}{\begin{cases}{\text{Exento}}&=2/7\\{\text{Final}}&=3/7\\{\text{Extraordinario}}&=2/7\\\end{cases}}\\I(2/7,3/7,2/7)=-2/7\log _{2}2/7-3/7\log _{2}3/7-2/7\log _{2}2/7=1.56\end{array}}$

• Puntualidad y Asistencia = {No asiste, Asiste}

PyA = No asiste

${\begin{array}{l}{\text{No Asiste}}{\begin{cases}{\text{Exento}}&=1/4\\{\text{Final}}&=2/4\\{\text{Extraordinario}}&=1/4\end{cases}}\\I({\text{Py A}}={\text{No Asiste}})=I(1/4,2/4,1/4)\\\qquad =-1/4\log _{2}1/4-2/4\log _{2}2/4-1/4\log _{2}1/4=1.50\end{array}}$

PyA = Asiste

${\begin{array}{l}{\text{Asiste}}{\begin{cases}{\text{Exento}}&=1/3\\{\text{Final}}&=1/3\\{\text{Extraordinario}}&=1/3\end{cases}}\\I({\text{Py A}}={\text{Asiste}})=I(1/3,1/3,1/3)\\\qquad =-1/3\log _{2}1/3-1/3\log _{2}1/3-1/3\log _{2}1/3=1.58\end{array}}$

• Participación = {Baja, Media, Alta}

Participación = Baja

${\begin{array}{l}{\text{Baja}}{\begin{cases}{\text{Exento}}&=0/2\\{\text{Final}}&=1/2\\{\text{Extraordinario}}&=1/2\end{cases}}\\I({\text{Part}}={\text{Baja}})=I(0/2,1/2,1/2)\\\qquad =-0/2\log _{2}0/2-1/2\log _{2}1/2-1/2\log _{2}1/2=1.0\end{array}}$

Participación = Media

${\begin{array}{l}{\text{Media}}{\begin{cases}{\text{Exento}}&=1/3\\{\text{Final}}&=1/3\\{\text{Extraordinario}}&=1/3\end{cases}}\\I({\text{Part.}}={\text{Media}})=I(1/3,1/,1/3)\\\qquad =-1/3\log _{2}1/3-1/3\log _{2}1/3-1/3\log _{2}1/3=1.58\end{array}}$

Participación = Alta

${\begin{array}{l}{\text{Alta}}{\begin{cases}{\text{Exento}}&=1/2\\{\text{Final}}&=1/2\\{\text{Extraordinario}}&=0/2\end{cases}}\\I({\text{Part}}={\text{Alta}})=I(1/2,1/2,0/2)\\\qquad =-1/2\log _{2}1/2-1/2\log _{2}1/2-0/2\log _{2}0/2=1.0\end{array}}$

• Aprovechamiento = {Deficiente, Regular, Bueno, Excelente}

Aprovechamiento = Deficiente

${\begin{array}{l}{\text{Deficiente}}{\begin{cases}{\text{Exento}}&=0/1\\{\text{Final}}&=0/1\\{\text{Extraordinario}}&=1/1\end{cases}}\\I({\text{Aprovech.}}={\text{Deficiente}})=I(0/1,0/1,1/1)\\\qquad =-0/1\log 0/1-0/1\log _{2}0/1-1/1\log _{2}1/1=0.0\end{array}}$

Aprovechamiento = Regular

${\begin{array}{l}{\text{Regular}}{\begin{cases}{\text{Exento}}&=0/2\\{\text{Final}}&=1/2\\{\text{Extraordinario}}&=1/2\end{cases}}\\I({\text{Aprovech}}={\text{Regular}})=I(0/2,1/2,1/2)\\\qquad =-0/2\log _{2}0/2-1/2\log _{2}1/2-1/2\log _{2}1/2=1.0\end{array}}$

Aprovechamiento = Bueno

${\begin{array}{l}{\text{Bueno}}{\begin{cases}{\text{Exento}}&=1/3\\{\text{Final}}&=2/3\\{\text{Extraordinario}}&=0/3\end{cases}}\\I({\text{Aprovech.}}={\text{Bueno}})=I(1/3,2/3,0/3)\\\qquad =-1/3\log _{2}1/3-2/3\log _{2}2/3-0/3\log _{2}0/3=0.92\end{array}}$

Aprovechamiento = Excelente

${\begin{array}{l}{\text{Excelente}}{\begin{cases}{\text{Exento}}&=1/1\\{\text{Final}}&=0/1\\{\text{Extraordinario}}&=0/1\end{cases}}\\I({\text{Aprovech.}}={\text{Excelente}})=I(1/1,0/1,0/1)\\\qquad =-1/1\log _{2}1/1-0/1\log _{2}0/1-0/1\log _{2}0/1=0.0\end{array}}$

Tomando todos estos datos y calculando la ganancia de información de todos los atributos, nos damos cuenta que el atributo "Aprovechamiento" es el mejor atributo, dado que posee la mayor ganancia de información, de tal manera que se selecciona como un nodo de prueba. Quedando el árbol de la siguiente manera:

Como los valores de "Bueno" y "Regular" todavía no llegan a una respuesta, se necesita realizar de nuevo el cálculo para ellos, pero ahora solo tomando los atributos "Puntualidad y Asistencia" y "Participación", discriminando al atributo "Aprovechamiento" porque ya ha sido tomado como prueba.

Entonces para "Aprovechamiento = Bueno" se tiene:

Variable	Ganancia de información (Variable)
Puntualidad y asistencia	0.92-[2/3(0)+1/3(0)] = 0.92
Participación	0.92-[1/3(0)+1/3(0)+1/3(0)] = 0.92

• Información de la clase: I(C) = 0.92

${\begin{array}{l}{\text{Bueno}}{\begin{cases}{\text{Exento}}&=1/3\\{\text{Final}}&=2/3\end{cases}}\\I(1/3,2/3)=-1/3\log _{2}1/3-2/3\log _{2}2/3=0.92\end{array}}$

• Puntualidad y Asistencia = {No asiste, Asiste}

PyA = No asiste

${\begin{array}{l}{\text{Py A}}={\text{No asiste}}\\{\text{No Asiste}}={\begin{cases}{\text{Exento}}&=0/2\\{\text{Final}}&=2/2\end{cases}}\\I({\text{Py A}}={\text{No Asiste}})=I(0/2,2/2)\\\qquad =-0/2\log _{2}0/2-2/2\log _{2}2/2=0.0\end{array}}$

PyA = Asiste

${\begin{array}{l}{\text{Py A}}={\text{Asiste}}\\{\text{Asiste}}{\begin{cases}{\text{Exento}}&=1/1\\{\text{Final}}&=0/1\end{cases}}\\I({\text{Py A}}={\text{Asiste}})=I(1/1,0/1)\\\qquad =1/1\log _{2}1/1-0/1\log _{2}0/1=0.0\end{array}}$

• Participación = {Alta, Media, Baja}

Participación = Baja

${\begin{array}{l}{\text{Baja}}{\begin{cases}{\text{Exento}}&=0/1\\{\text{Final}}&=1/1\end{cases}}\\I({\text{Part.}}={\text{Baja}})=I(0/1,1/1)\\\qquad =-0/1\log _{2}0/1-1/1\log _{2}1/1=0.0\end{array}}$

Participación = Media

${\begin{array}{l}{\text{Media}}{\begin{cases}{\text{Exento}}&=0/1\\{\text{Final}}&=1/1\end{cases}}\\I({\text{Part.}}={\text{Media}})=I(0/1,1/1)\\\qquad =-0/1\log _{2}0/1-1/1\log _{2}1/1=0.0\end{array}}$

Participación = Alta

${\begin{array}{l}{\text{Alta}}{\begin{cases}{\text{Exento}}&=1/1\\{\text{Final}}&=0/1\end{cases}}\\I({\text{Part.}}={\text{Alta}})=I(1/1,0/1)\\\qquad =-1/1\log _{2}1/1-0/1\log _{2}0/1=0.0\end{array}}$

Observando los resultados obtenidos, vemos que la ganancia de información de los 2 atributos “Puntualidad y Asistencia” y “Participación” es 0.0 para ambos casos, por tal motivo la selección del nodo pregunta puede ser cualquiera de ellos.

Observamos, haciendo una rápida revisión para “Aprovechamiento = Regular”, que también toma los mismos datos, por lo que, por convención tomamos el atributo “Puntualidad y Asistencia” como nodo pregunta.

Hasta ahí donde concluye el árbol de decisión, quedando de la siguiente manera:

Bibliografía

Bibliografía utilizada

• INTELIGENCIA ARTIFICIAL: UN ENFOQUE PRACTICO Russell
• GRAN DICCIONARIO ENCICLOPÉDICO ILUSTRADO, Selecciones del Reader’s Digest

Enlaces externos

• Wikimedia Commons alberga una galería multimedia sobre Árbol de decisión.
• https://web.archive.org/web/19990428103011/http://www.pvv.unit.no/%7Ehgs/project/report/node36.html
• https://web.archive.org/web/19990218034308/http://ai.bpa.arizona.edu/papers/mlir93/subsection3_7_1.html
• http://www.cis.temple.edu/~ingargio/cis587/readings/id3-C45.html

• Datos: Q6173756