Upload
fai
View
62
Download
2
Embed Size (px)
DESCRIPTION
Aprendizaje en Árboles de Decisión. Semana 2, Clase 3 Gabriela Ochoa. Contenido. Características de los Arboles de Decisión Problemas adecuados Representación Entropía y Ganancia de Información Búsqueda en el espacio de Hipotesis. Árboles de Decisión. - PowerPoint PPT Presentation
Citation preview
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