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.