Un ejemplo desarrollado de ID3

Buscando por internet podemos encontrar algunos ejemplos sobre el ID3. Si los seguimos podemos entender mucho mejor su funcionamiento. En primer lugar vamos a incluir el pseudocódigo de este, de manera que podamos estudiarlo de manera teórica:

Si todos los ejemplos de E pertenecen a una misma clase C, entonces
   arbol1 <-- nodo etiquetado con C
SiNo
   Si a = f, entonces
      C <-- clase mayoritaria de los ejemplos de E
      arbol1 <-- nodo etiquetado con C
   SiNo
      A <-- mejor atributo de a
      arbol1 <-- nodo etiquetado con A
      Para cada v perteneciente a los valores de A, hacer
         EAv <-- los ejemplos de E que tienen el valor v para el atributo A
         Si EAv = f, entonces
            arbol2 <-- nodo etiquetado con la clase mayoritaria en E
         SiNo
            arbol2 <-- ID3(EAv , a-{A})
         arbol1 <-- añadir a arbol1 el arbol2, a través de una rama etiquetada con v
Devolver arbol1

A continuación vamos a desarrollar un ejemplo del ID3, con el objetivo de entender como funciona y como obtiene el árbol.

Teniendo estos datos como originales, trataremos de obtener un árbol que nos permita clasificar a los pacientes para administrarle el tratamiento o no. El primer paso sería elegir el atributo con máxima ganancia. Para ello, observamos la ganancia de cada uno de los atributos de la siguiente manera: Obtenemos la entropía de cada atributo para cada característica, obteniendo el log 2 del número de sujetos que poseen ese atributo, entre el número de los que no lo tienen. Posteriormente, estas entropías, las multiplicamos por el número de elementos totales que tiene cada característica, como se lleva a cabo a continuación:

                                   

G(S,"Presión Arterial")=0.940−(5/14)⋅0.971−(4/14)⋅0 −(5/14)⋅0.971=0.246

G(S,"Gota")=0.940−(7/14)⋅0.985 − (7 /14) ⋅ 0.592 = 0.151

G(S,"Urea en Sangre")=0.940 −(4/14)⋅1−(6/14)⋅0.918 −(4/14)⋅ 0.811 = 0.029

G(S,"Hipotiroidismo")=0.940 −(6/14)⋅1  − (8/14)⋅0.811 = 0.048

Una vez terminado este primer paso, nos quedamos con el atributo que más ganancia tenga; en este caso, se trataría de la presión arterial, por lo tanto, obtendríamos ya una parte del árbol, como se muestra a continuación:

Si seguimos realizando la ganancia a partir de la imagen anterior, obtenemos el siguiente árbol, con el que finalizaríamos el ejemplo:

Ross Quinlan: El inventor del ID3

John Ross Quinlan es un ingeniero informático, investigador especializado de ciencias de la computación en la minería de datos y la teoría de la decisión. Ha contribuido ampliamente al desarrollo de algoritmos de árboles de decisión, incluyendo la invención de los algoritmos de clasificación C4.5, ID3 y C5.0. Actualmente trabaja para la compañía Research RuleQuest, que  él mismo fundó en 1997. Ha publicado gran número de publicaciones, que podremos consultar a continuación. Su página web es: http://www.rulequest.com/Personal/

Publicaciones

• (1979). Discovering Rules by Induction from Large Collections of Examples. Expert Systems in the Micro-electronic Age, pp. 168-201. Edinburgh University Press (Introducing ID3)
• (1982). Semi-Autonomous Acquisition of Pattern-Based Knowledge. Introductory Readings in Expert Systems, pp. 192-207. Gordon & Breach, New York. ISBN 0677163509.
• (1983, 1985). Learning efficient classification procedures and their application to chess end games. Machine Learning: An Artificial Intelligence Approach 
• (1986). Induction of Decision Trees. Machine Learning 1, 1, 81-106
• (1986). The Effect of Noise on Concept Learning. Machine Learning: An Artificial Intelligence Approach, Vol. 2 
• (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann
• (1993). Improved use of continuous attributes in c4.5. Journal of Artificial Intelligence Research, 4:77-90
• Ron Kohavi (1999). Decision Tree Discovery.

Pseudocódigo y algunas herramientas de Minería de Datos...

El siguiente fragmento de pseudocódigo podría representar el funcionamiento general del algoritmo:

Podemos observar que el árbol va construyéndose recursivamente, siendo las líneas de código señaladas en rojo las que construyen los nodos hoja.

En el siguiente diagrama de flujo podemos apreciar la manera de trabajar de ID3:

Son numerosas las herramientas de minería de datos que incorporan ID3 para su utilización, algunas de ellas:

• RapidMiner http://rapid-i.com/content/view/181/190/
• KNIME http://www.knime.org/
• Weka http://www.cs.waikato.ac.nz/~ml/weka/
• KEEL http://www.keel.es/

En esta imagen podemos apreciar su disponibilidad en Keel, incluso incorporando un discretizador específico para este algoritmo:

La siguiente imagen corresponde a la herramienta software Weka:

Algoritmo de clasificación: ID3

(J. Ross Quinlan, 1983)

Se trata de un algoritmo de aprendizaje y clasificación que tiene como objetivo la construcción de un árbol de decisión que explique cada una de las instancias de la secuencia de entrada. En cada momento escogerá el mejor atributo atendiendo a una heurística, determinará las variables relevantes para la resolución del problema y establecerá la secuencia dentro del árbol de decisión.

Procurará encontrarse el árbol más sencillo que separe los ejemplos, es recursivo, no utiliza "backtracking" (vuelta atrás) y hace uso de la entropía y de la ganancia. El árbol de decisión estará formado por:

1. Nodos: Nombres de los atributos.
2. Ramas: Posibles valores del atributo asociado al nodo.
3. Hojas: Conjuntos clasificados de ejemplos, ya etiquetados con el nombre de una clase.

El algoritmo funciona, en general, de la siguiente manera:

• Comienza tomando el conjunto inicial S de ejemplos como nodo raíz.
• En cada iteración, el algoritmo, itera sobre los atributos no usados del conjunto y calcula su entropía , H(S) (o su ganancia G(S), según la alternativa que se decida utilizar).
• Se selecciona entonces el atributo con menor entropía (o mayor ganancia), haciendo una división del conjunto S, produciendo subconjuntos.
• El algoritmo se llama recursivamente en cada uno de los subconjuntos obtenidos. Cuando todos los elementos de un subconjunto pertenecen a la misma clase, el algoritmo deja de iterar y este subconjunto pasará a ser una hoja del árbol etiquetándose con el nombre de la clase a la que pertenecen todos sus elementos.
• El algoritmo termina cuando todos los subconjuntos están clasificados.

*Entropía: Medida de la incertidumbre de un sistema, ante una situación, probabilidad de que ocurra cada una de las posibilidades.

Donde,

S: Conjunto de datos para el que se está calculando la entropía.

X: Conjunto de clases de S.

p(x): Proporción del número de elementos de la clase x respecto al número de elementos de S.

Cuando H(S)=0, el conjunto está clasificado, todos sus elementos pertenecen a la misma clase.

*Ganancia: Diferencia entre la entropía de un nodo y la de uno de sus descendientes. Es otra heurística para la selección del mejor atributo en cada nodo.

Donde,

H(S): Entropía del conjunto S.

T: Subconjuntos creados de separar el conjunto S por el atributo A.

p(t): Proporción del número de elementos en T respecto al número de elementos de S.

H(t): Entropía del subconjunto t.