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.