5. Características del algoritmo ID3 y Fuentes de mejora

• El espacio de hipótesis es completo, la función objetivo está incluida en él.
• Selecciona una única hipótesis:
• No es capaz de determinar todos los árboles compatibles con los ejemplos de entrenamiento.
• No se puede proponer ejemplos que reduzcan el espacio de búsqueda.
• No hay vuelta atrás:
• Encuentra un óptimo local que puede no ser el óptimo global (hill-climbing).
• En cada paso utiliza información estadística de todos los ejemplos en lugar de considerar los ejemplos uno a uno:
• Permite ruido en los datos de entrenamiento.
• Por la ganancia de información, tiene tendencia a elegir atributos con muchos valores.
• De todos los árboles compatibles con los ejemplos de entrenamiento ¿Cuál elige ID3?
• ID3 prefiere árboles cortos frente a largos, con los atributos que producen una mayor ganancia de información cerca de la raíz.

Fuentes de mejora de ID3

• Cuándo parar en la construcción del árbol
• Uso de atributos continuos
• Otras medidas de selección de atributos
• Atributos con coste diferente
• Ejemplos incompletos

4. Ejemplo

Dados los siguientes datos:

Calculamos entropía del conjunto:

H(S) = Entropia(S)=4/15 log (15/4) + 8/15 log(15/8) + 3/15 log (15/3) = 0.4384

Ahora elegimos el atributo test con máxima ganacia de información:

Género:

H(S,gender=F)=3/9 log(9/3) + 6/9 log (9/6) =0.2764

H(S,gender=M)=1/6 log(6/1) + 2/6 log (6/2) + 3/6 log(6/3)= 0.4392

por tanto la ganancia de información del género será:

Gain(S,gender) = 0.4384 – 9/15·0.2764 – 6/15·0.4392 = 0.09688

Altura: El algoritmo ID3 tiene como precondición que los datos sean discretos y como la altura es un valor continuo vamos a acotarlo en intervalos:

1: (0,1.6], 2: (1.6,1.7], 3: (1.7,1.8], 4: (1.8,1.9], 5: (1.9,2.0], 6: (2.0,∞)





H(S,height=1)=2/2 log(2/2)=0

H(S,heigth=2)=2/2 log(2/2)=0

H(S,height=3)=3/3 log(3/3)=0

H(S,height=4)=4/4 log(4/4)=0
H(S,height=5)=1/2 log 2 + 1/2 log 2 = 0.301
H(S,height=6)=2/2 log (2/2)=0

Gain(S,height) =0.4384 – 2/15 · 0.301 = 0.3983

Por lo tanto como la ganancia de información del atributo "altura" es mayor que la ganancia de información del atributo "género" se clasificará en base a la "altura"



3. Esquema del algoritmo ID3

Pasos del algoritmo ID3:

1. Seleccionar el atributo A que maximice la ganancia G(S,A)

2. Crear un nodo para ese atributo con tantos sucesores como valores tenga

3. Introducir los ejemplos en los sucesores según el valor que tenga el atributo A

4. Por cada sucesor:

           Si sólo hay ejemplos de una clase, Ck

           Entonces etiquetarlo con Ck

           Si no llamar a ID3 con un conjunto de ejemplos formado por los ejemplos de ese

           nodo, eliminando la columna del atributo A

 Termina cuando todos los datos del nodo son de la misma clase y la entropía es cero

Donde encontrar y aplicar ID3:

El algoritmo ID3 puede encontrarse en muchas herramientas de minería de datos como Weka y Keel, por ejemplo.

La manera de usar el algoritmo ID3 en Weka sería como se muestra en la imagen:

Y un ejemplo de árbol que genera:

2. Entropía y Ganancia de Información

ID3 elige el atributo test con máxima ganancia de información. Está basada en la entropía que se utiliza como una medida de la cantidad de incertidumbre o sorpresa en un conjunto de datos.

¿Qué es la entropía?

Dados:
  - Un problema con dos clases (positiva y negativa)
  - S, el conjunto de ejemplos.

Entropia(S)= ∑i =1 hasta k     pi ⋅ log2 (1 / pi )

con k clases

¿Qué es la ganacia de información?

Es la diferencia entre la cantidad de información que se necesita para hacer una clasificación antes de hacer la división y después.

Se calcula determinando la diferencia entre la entropía del conjunto de datos de partida y la suma ponderada de las entropías una vez dividido el conjunto de ejemplos.





1. En qué consiste el algoritmo ID3

ID3 o Induction Decision Trees fue desarrollado por J. Ross Quinlan en 1983 y tiene como objetivo construir un árbol de decisión que explique cada instancia de la secuencia de entrada de la manera más compacta posible a partir de una tabla de inducción.

El algoritmo se aplica sobre una serie de ejemplos y cada uno de ellos deberá estar conformado por una serie de tuplas de valores, denominados atributos, donde uno de esos atributos es el objetivo. Este objetivo será de tipo binario, ocurre el suceso o no ocurre.

Si necesita información adicional a este blog puede encontrarla aquí .