Aprendizaje en Árboles de Aprendizaje en Árboles de DecisiónDecisión

Semana 2, Clase 3Semana 2, Clase 3Gabriela OchoaGabriela Ochoa

ContenidoContenido Características de los Arboles de Características de los Arboles de

DecisiónDecisión Problemas adecuados Problemas adecuados RepresentaciónRepresentación Entropía y Ganancia de InformaciónEntropía y Ganancia de Información Búsqueda en el espacio de HipotesisBúsqueda en el espacio de Hipotesis

Árboles de DecisiónÁrboles de Decisión Robustos a datos ruidosos, con erroresRobustos a datos ruidosos, con errores Capaz de aprender expresiones Capaz de aprender expresiones

disyuntivasdisyuntivas Método para aproximar funciones Método para aproximar funciones

objetivos con valores discretos objetivos con valores discretos ( booleanas, o mas)( booleanas, o mas)

Método mas utilizado y practico para Método mas utilizado y practico para inferencia inductivainferencia inductiva

Problemas Adecuados para Problemas Adecuados para Árboles de Decisión Árboles de Decisión

Instancias son representadas por pares Instancias son representadas por pares atributo-valoratributo-valor Instancias descritas por un conjunto fijo de Instancias descritas por un conjunto fijo de

atributos (Ej.., temperatura) y sus valores (Ej.., atributos (Ej.., temperatura) y sus valores (Ej.., hot). hot).

Preferiblemente un numero pequeño de Preferiblemente un numero pequeño de posibles valores (Ej., hot, mild, cold). posibles valores (Ej., hot, mild, cold).

Extensiones al algoritmo básico permiten Extensiones al algoritmo básico permiten manejar atributos con valores reales (Ej., a manejar atributos con valores reales (Ej., a floating point temperatura). floating point temperatura).

Función objetivo tiene valores de salida Función objetivo tiene valores de salida discretosdiscretos Caso mas sencillo, función booleanaCaso mas sencillo, función booleana Puede extenderse para aprender funciones Puede extenderse para aprender funciones

con mas de dos valores de salidacon mas de dos valores de salida Se requieren descripciones disyuntivasSe requieren descripciones disyuntivas Datos de entrenamiento pueden tener Datos de entrenamiento pueden tener

erroreserrores Errores en el valor o ausencia de algún Errores en el valor o ausencia de algún

atributoatributo Errores en la clasificaciónErrores en la clasificación

Representación Árboles de Representación Árboles de DecisiónDecisión

Ordenamiento de preguntas, que determina la Ordenamiento de preguntas, que determina la pregunta o test adecuado para cada pasopregunta o test adecuado para cada paso

Representan una disyunción de conjunciones de Representan una disyunción de conjunciones de restricciones sobre valores de los atributos restricciones sobre valores de los atributos

Clasifican instancias recorriendo el árbol hacia abajo Clasifican instancias recorriendo el árbol hacia abajo de la raíz a las hojasde la raíz a las hojas

La hoja provee la clasificación de la instanciaLa hoja provee la clasificación de la instancia Cada Nodo representa una pregunta sobre cada Cada Nodo representa una pregunta sobre cada

atributo. atributo. Las ramas descendentes de un nodo atributo Las ramas descendentes de un nodo atributo

corresponden a los valores de dicho atributocorresponden a los valores de dicho atributo

Arbol se construye a partir de Arbol se construye a partir de los Datos de Entrenamientolos Datos de Entrenamiento

Datos Árbol de Decisión

Reglas de Decisión

Predicciones en datos no observados

Algoritmo Básico ID3Algoritmo Básico ID3 Construye árboles top-downConstruye árboles top-down Pregunta: Cual atributo debe ser chequeado en la Pregunta: Cual atributo debe ser chequeado en la

raíz del árbol?raíz del árbol? El “mejor” atributo es seleccionado y colocado El “mejor” atributo es seleccionado y colocado

como test en la raizcomo test en la raiz Se crea una rama para cada valor del atributoSe crea una rama para cada valor del atributo Se repite el proceso utilizando ejemplos de Se repite el proceso utilizando ejemplos de

entrenamiento asociados con cada rama para entrenamiento asociados con cada rama para seleccionar mejor atributo en cada pasoseleccionar mejor atributo en cada paso

Algoritmo Greedy, sin backtrackingAlgoritmo Greedy, sin backtracking

Como seleccionar el mejor Como seleccionar el mejor atributo?atributo?

Medida para evaluar que tan bueno es un Medida para evaluar que tan bueno es un atributo. Propiedad estadistica: atributo. Propiedad estadistica: information gaininformation gain

Mide que tan bien un atributo dado separa Mide que tan bien un atributo dado separa a los ejemplos de entrenamientoa los ejemplos de entrenamiento

EntropíaEntropía: medida de teoria de la : medida de teoria de la informacion, caracteriza la (im)pureza u informacion, caracteriza la (im)pureza u homogeneidad en una colección arbitraria homogeneidad en una colección arbitraria de ejemplosde ejemplos

Ejemplo Calculo de EntropíaEjemplo Calculo de Entropía SS colección de 14 ejemplos de un concepto colección de 14 ejemplos de un concepto

booleano, 9 ejemplos + y 5 – [9+,5-]booleano, 9 ejemplos + y 5 – [9+,5-]E([9+,5-])E([9+,5-]) = -(9/14)log(9/14) - (5/14)log(5/14)= 0.940 = -(9/14)log(9/14) - (5/14)log(5/14)= 0.940

La entropía es = 0 si todos los miembros de S La entropía es = 0 si todos los miembros de S pertenecen a la misma clase. Si p+ = 1, p- = 0, pertenecen a la misma clase. Si p+ = 1, p- = 0, E(S)E(S) = -1*log(1) – 0*log(0) = -1*0 – 0*log(0) = 0 = -1*log(1) – 0*log(0) = -1*0 – 0*log(0) = 0

La entropía es = 1 cuando S contiene el mismo La entropía es = 1 cuando S contiene el mismo numero de ejemplos positivos y negativos. Si p+ numero de ejemplos positivos y negativos. Si p+ = 1/2, p- = 1/2, = 1/2, p- = 1/2, E(S)E(S) = -1/2*log(1/2) – 1/2*log(1/2) = -1/2*log(1/2) – 1/2*log(1/2) = -1/2*-1 – 1/2*-1 = 1= -1/2*-1 – 1/2*-1 = 1

Búsqueda en el espacio de Búsqueda en el espacio de HipótesisHipótesis

En cada paso del algoritmo mantiene un En cada paso del algoritmo mantiene un solo árbol o hipótesis (diferente al solo árbol o hipótesis (diferente al algoritmo del capitulo dos que mantiene algoritmo del capitulo dos que mantiene un conjunto)un conjunto)

ID3ID3: Busca en el espacio de posibles : Busca en el espacio de posibles árboles de decisión desde el mas simple árboles de decisión desde el mas simple hacia incrementalmente mas complejos, hacia incrementalmente mas complejos, guiado por la heurística de la ganancia de guiado por la heurística de la ganancia de informacióninformación