Ver el código de «Á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:

[[Archivo:Representa.arbol.decision.PNG|thumb|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:

:<math>\text{Entropia}(S)=\sum_{i=1}^n-p_i\log_2 p_i</math>

Donde: 

''S'': es una colección de objetos

''P<sub>i</sub>'' : 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<sub>2</sub> 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:

:<math>\text{Gan Inf}(S,A)=\text{Entropia}(S)-\sum_{v\in V(A)} \frac{\vert Sv \vert}{\vert S \vert} \text{Entropia}(Sv)</math>

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:

# Calcular la entropía para todas las clases.
# Seleccionar el mejor atributo basado en la reducción de la entropía.
# 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''

{| class="wikitable" align=left
| rowspan=2 | '''Alumno''' 
| colspan="3" align="center"| '''ATRIBUTO''' 
| rowspan=2 align="center"| '''Nota'''
|-
| '''Punt. y asist.''' || '''Participación''' || '''Aprovechamiento''' 
|-
| align="center"| 1 || align="center"| No asiste || align="center"| Media || align="center"| Excelente|| align="center"| Exento  
|-
| align="center"| 2 || align="center"| Asiste || align="center"| Alta || align="center"| Bueno || align="center"| Exento
|-
| align="center"| 3 || align="center"| No asiste || align="center"| Media || align="center"| Bueno|| align="center"| Final  
|-
| align="center"| 4 || align="center"| No asiste || align="center"| Baja || align="center"| Bueno|| align="center"| Final  
|-
| align="center"| 5 || align="center"| Asiste || align="center"| Alta || align="center"| Regular || align="center"| Final
|-
| align="center"| 6 || align="center"| Asiste || align="center"| Baja || align="center"| Deficiente|| align="center"| Extraordinario  
|-
| align="center"| 7 || align="center"| No asiste || align="center"| Media || align="center"| Regular || align="center"| 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:

{| class="wikitable"
! Variable
! Ganancia de información (Variable)
|-
|align="center"| Puntualidad y asistencia||1.56-[4/7(1.5)+3/7(1.58)] = 0.025
|-
|align="center"| Participación||1.56-[2/7(1.0)+3/7(1.58)+2/7(1.0)] = 0.311
|-
|align="center"| 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

:<math>\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}</math>

* '''Puntualidad y Asistencia''' = {No asiste, Asiste}

PyA = No asiste

:<math>\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}</math>

PyA = Asiste

:<math>\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}</math>

* '''Participación''' = {Baja, Media, Alta}

Participación = Baja

:<math>\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}</math>

Participación = Media

:<math>\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}</math>

Participación = Alta

:<math>\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}</math>

* '''Aprovechamiento''' = {Deficiente, Regular, Bueno, Excelente}

Aprovechamiento = Deficiente

:<math>\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}</math>

Aprovechamiento = Regular

:<math>\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}</math>

Aprovechamiento = Bueno

:<math>\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}</math>

Aprovechamiento = Excelente

:<math>\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}</math>

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:

[[Archivo:Arbol2.PNG|frameless|350px]]

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

{| class="wikitable"
! Variable
! Ganancia de información (Variable)
|-
|align="center"| Puntualidad y asistencia||0.92-[2/3(0)+1/3(0)] = 0.92
|-
|align="center"| Participación||0.92-[1/3(0)+1/3(0)+1/3(0)] = 0.92
|}

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

:<math>\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}</math>

* '''Puntualidad y Asistencia =''' {No asiste, Asiste}

PyA = No asiste

:<math>\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}</math>

PyA = Asiste

:<math>\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}</math>

* '''Participación =''' {Alta, Media, Baja}

Participación = Baja

:<math>\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}</math>

Participación = Media

:<math>\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}</math>

Participación = Alta

:<math>\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}</math>

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:

[[Archivo:Arbol3.PNG|frameless|350px]]

== Bibliografía ==

'''Bibliografía utilizada'''

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

== Enlaces externos ==
{{commons|Árbol de decisión (modelo de clasificación ID3)}}
* 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

{{Control de autoridades}}
[[Categoría:Teoría de la decisión]]