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.