1 Aprendizaje en Árboles de DecisiónSemana 2, Clase 3 Gabriela Ochoa

2 Contenido Características de los Arboles de DecisiónProblemas adecuados Representación Entropía y Ganancia de Información Búsqueda en el espacio de Hipotesis

3 Árboles de Decisión Robustos a datos ruidosos, con erroresCapaz de aprender expresiones disyuntivas Método para aproximar funciones objetivos con valores discretos ( booleanas, o mas) Método mas utilizado y practico para inferencia inductiva

4 Problemas Adecuados para Árboles de DecisiónInstancias son representadas por pares atributo-valor Instancias descritas por un conjunto fijo de atributos (Ej.., temperatura) y sus valores (Ej.., hot). Preferiblemente un numero pequeño de posibles valores (Ej., hot, mild, cold). Extensiones al algoritmo básico permiten manejar atributos con valores reales (Ej., a floating point temperatura).

5 Función objetivo tiene valores de salida discretosCaso mas sencillo, función booleana Puede extenderse para aprender funciones con mas de dos valores de salida Se requieren descripciones disyuntivas Datos de entrenamiento pueden tener errores Errores en el valor o ausencia de algún atributo Errores en la clasificación

6 Representación Árboles de DecisiónOrdenamiento de preguntas, que determina la pregunta o test adecuado para cada paso Representan una disyunción de conjunciones de restricciones sobre valores de los atributos Clasifican instancias recorriendo el árbol hacia abajo de la raíz a las hojas La hoja provee la clasificación de la instancia Cada Nodo representa una pregunta sobre cada atributo. Las ramas descendentes de un nodo atributo corresponden a los valores de dicho atributo

7 Arbol se construye a partir de los Datos de EntrenamientoÁrbol de Decisión Predicciones en datos no observados Reglas de Decisión

8 Algoritmo Básico ID3 Construye árboles top-downPregunta: Cual atributo debe ser chequeado en la raíz del árbol? El “mejor” atributo es seleccionado y colocado como test en la raiz Se crea una rama para cada valor del atributo Se repite el proceso utilizando ejemplos de entrenamiento asociados con cada rama para seleccionar mejor atributo en cada paso Algoritmo Greedy, sin backtracking

9 Como seleccionar el mejor atributo?Medida para evaluar que tan bueno es un atributo. Propiedad estadistica: information gain Mide que tan bien un atributo dado separa a los ejemplos de entrenamiento Entropía: medida de teoria de la informacion, caracteriza la (im)pureza u homogeneidad en una colección arbitraria de ejemplos

10 Ejemplo Calculo de EntropíaS colección de 14 ejemplos de un concepto booleano, 9 ejemplos + y 5 – [9+,5-] E([9+,5-]) = -(9/14)log(9/14) - (5/14)log(5/14)= 0.940 La entropía es = 0 si todos los miembros de S pertenecen a la misma clase. Si p+ = 1, p- = 0, E(S) = -1*log(1) – 0*log(0) = -1*0 – 0*log(0) = 0 La entropía es = 1 cuando S contiene el mismo numero de ejemplos positivos y negativos. Si p+ = 1/2, p- = 1/2, E(S) = -1/2*log(1/2) – 1/2*log(1/2) = -1/2*-1 – 1/2*-1 = 1

11 Búsqueda en el espacio de HipótesisEn cada paso del algoritmo mantiene un solo árbol o hipótesis (diferente al algoritmo del capitulo dos que mantiene un conjunto) ID3: Busca en el espacio de posibles árboles de decisión desde el mas simple hacia incrementalmente mas complejos, guiado por la heurística de la ganancia de información