PRÁCTICA 2. CIENCIA COGNITIVA 2005

Aprendizaje inductivo. Arboles de decisión. ID3.

En esta práctica se trabajará con una variante del algoritmo de aprendizaje de árboles de 
decisión ID3 de Quinlan, desarrollado por Andrew Colin. Esta variante trata con 
atributos con valores reales y, a partir de un conjunto de ejemplos clasificados, induce 
árboles binarios donde los nodos suponen el test sobre los atributos:

if  (atributo > umbral)  then … else if …else …

La implementación consta de tres archivos: id3.c, id3.h, proto.h. Para compilarlo debe 
introducirse la opción de linkado de la librería matemática, ej:

gcc –o id3 id3.c –lm

También se proporcionan los archivos sample-spam.dat y sample-spam.tag. En el 
primero por cada línea aparecen un ejemplo clasificado como spam o no spam. El 
segundo indica que para cada ejemplo los atributos son: (1) número de caracteres en el 
mensaje, (2) presencia (valor 1) o ausencia (valor 0) del string “http”en mayúsculas o 
minúsculas en el mensaje,  (3) presencia (valor 1) o ausencia (valor 0) del string “click” 
en mayúsculas o minúsculas en el mensaje, (4) presencia (valor 1) o ausencia (valor 0) 
del string “free” een mayúsculas o minúsculas en el mensaje, (5) el número de letras 
mayúsculas en el mensaje, (6) el número de caracters dólar ($) en el mensaje, (7) el 
número de caracteres de exclamación (!) en el mensaje. El último valor en cada línea es 
el valor de clasificación del ejemplo: 0 no spam, 1 spam.

En esta práctica se realizarán las siguientes tareas:

1. Aplicar el inductor sobre los ejemplos de muestra:

id3 sample-spam

y dibujar el árbol inducido.

2. Construir espera-restaurante.dat y espera-restaurante.tag con los ejemplos del tema de 
aprendizaje inductivo de árboles de decisión del texto de Russell y Norvig vistos en 
clase. Aplicar el inductor sobre estos ejemplos y dibujar el árbol inducido. Compararlo 
con el obtenido en el texto y comentar las diferencias.

3. A partir del árbol inducido en 1 construir el clasificador, es decir, un programa que 
ante la presencia de un nuevo mensaje nos diga si es o no spam. Lo ideal sería un 
programa que reconociese cualquier árbol inducido por el inductor de Andrew Colin y 
construyese el clasificador. En esta práctica basta que transformeis en código la 
expresión producida por el inductor. 
Por tanto este clasificador tomará como entrada un archivo de ejemplos con el formato 
.dat pero donde el último valor en cada línea es 2 (con el significado de ejemplo sin 
clasificar) en lugar 1 (spam) o 0 (no-spam), y la salidad del inductor obtenida 
anterioremente, para producir una copia del archivo de ejemplos con todos los ejemplos 
clasificados (1 ó 0 en el último valor de cada línea). Si el clasificador fuese genérico 
debiera tomar como entrada también el archivo con formato .tag para poder leer la 
expresión producida por el inductor.

4. Probar el clasificador con los ejemplos del conjunto de entrenamiento sample-
spam.dat. El clasificador debe clasificar correctamente todos los ejemplos del conjunto 
de entrenamiento.

5. Se suministran también los archivos SpamTestSet y NonSpamTestSet que contienen 
ejemplos de mensajes spam y no spam, y que usaremos para evaluar el clasificador. 
Para ello es necesario procesar estos archivos de texto para producir los archivos 
correspondientes en formato .dat. Una vez obtenida la representación de los mensajes 
con este formato, deben pasarse al clasificador y el software de evaluación debe 
producir el % de clasificaciones correctas para cada categoría y el % de clasificaciones 
correctas total.

6. En el conjunto original de entrenamiento cambiar la clasificación de 1, 4 y 10 
ejemplos. Para cada caso obtener el árbol inducido, el clasificador y evaluarlo sobre 
SpamTestSet y NonSpamTestSet. ¿Cuáles son las conclusiones de este experimento?

Debe construirse una breve memoria con las descripción de los ejercicios, resultados y 
conclusiones de cada apartado que se entregará en las horas de prácticas los días 23 y 25 
de mayo de 2005. No se aceptarán entregas de prácticas fuera de plazo.