El algoritmo de aprendizaje

• Un árbol de decisión puede aprenderse inductivamente a partir de un conjunto de ejemplos

  Un ejemplo se describe con los valores de los atributos y el valor del predicado objetivo. El valor del predicado objetivo es la clasificación del ejemplo. El ejemplo es positivo o negativo según su clasificación. El conjunto de ejemplos se llama conjunto de entrenamientos

  La idea clave del algoritmo de aprendizaje es encontrar el atributo más importante. El significado de más importante es que es el más significativo con respecto a la clasificación de los ejemplos

  Patrons es un atributo bastante importante ya que si el valor es None o Some, produce ejemplos para los que ya hay una respuesta definitiva (Si/No), es decir, clasifica todos los ejemplos como positivos o negativos. Type es un atributo pobre porque produce cuatro salidas y en cada una hay ejemplos positivos y negativos

• Realmente Patrons es el atributo más importante. Una vez elegido, cada salida (hay 3) es un nuevo problema de aprendizaje de un árbol de decisión con menos ejemplos y 1 atributo menos (procedimiento recursivo). Hay que considerar cuatro casos:
  • Si hay ejemplos positivos y negativos hay que elegir el mejor atributo (Teoría de la Información) para dividirlos. En la figura se elige el atributo Hungry para dividir los ejemplos restantes
  • Si todos los ejemplos son positivos (o todos negativos) no queda nada por hacer. Se puede responder Si o No
  • Si no quedan ejemplos (no ha sido observado ese ejemplo) se devuelve un valor por defecto para el predicado objetivo o el valor mayoritario en la clasificación del nodo padre
  • No quedan atributos pero quedan ejemplos positivos y negativos. Problema: son ejemplos con la misma descripción y distinta clasificación. Puede ser debido a ruido en los datos (datos incorrectos), a que los atributos no den suficiente información para describir la situación o a que el dominio es no determinístico. Una primera aproximación puede ser devolver el valor mayoritario de esos ejemplos
• Obsérvese el árbol inducido por el ejemplo
  • Se aprende de los ejemplos. Por eso no aparecen atributos como Raining o Reservation ya que se pueden clasificar todos los ejemplos sin ellos
  • Pueden detectarse regularidades no sospechadas en los datos (Esperar en un Thai los fines de semana)
  • Discútase el ejemplo de una espera de 0-10 minutos y el restaurante lleno
• La curva de aprendizaje muestra que al aumentar el conjunto de entrenamiento aumenta el porcentaje de acierto en el conjunto de test. Esto es un indicador de que realmente el algoritmo está aprendiendo el patrón de los datos
• Consideraciones a tener en cuente en los sistemas reales
  • En el caso de ruido en los datos, debe evitarse que el algoritmo encuentre regularidades que realmente no existen en los datos (cuestión similar a la de la significancia estadística)
  • Falta de datos. En muchos dominios no todos los valores de los atributos se conocerán en todos los ejemplos
  • Atributos con muchos valores. Se requiere modificar la medida de la importancia del atributo. Considerar un atributo RestaurantName: clasificaría cada ejemplo en una clase y tendría la máxima importancia. Sin embargo es irrelevante
  • Atributos con valores continuos. Discretización. Véase el ejemplos del atributo Price. El interés está en encontrar que rangos de discretización dan más información al proceso de clasificación
• Aplicaciones industriales (J.R. Quinlan ) C4.5 versión industrial de ID3