inducción de Árboles de decisión -...

Inducción de Árboles de Decisión

ID3, C4.5

Inducción de árboles de decisión 2

Contenido

1. Representación mediante árboles de decisión

2. Algoritmo básico: divide y vencerás

3. Heurística para la selección de atributos

4. Espacio de búsqueda y bias inductivo

5. Sobreajuste

6. Mejoras a ID3

7. Poda de árboles: C4.5

8. Interpretación geométrica aprendizaje con árboles

9. Conclusiones y ejemplos de aplicación

Inducción de árboles de decisión 3

1. Representación mediante árboles de decisión

Descripción de instancias: pares atributo/valor

Árbol de decisión

Nodos no terminales: test

Arcos: valores

Nodos terminales: clase de decisión

Clasificación instancias no vistas

Recorrer árbol de decisión

Inducción de árboles de decisión 4

Árbol de decisiónConcepto: “Riesgo en la concesión de crédito”

Ingresos

Alto

0 a 2 2 a 5 más de 5

Historia Historia

Deuda Alto Moderado Bajo Moderado Bajo

Desconocida MalaBuena DesconocidaMala Buena

Alto Moderado

Alta Baja

Inducción de árboles de decisión 5

Espacio de hipótesis

Si clase de decisión binaria Cada árbol de decisión representa una

función booleana

Espacio de hipótesis: Conjunto de todos los árboles de decisión o

de todas las funciones booleanas

Tamaño espacio de hipótesis Suponiendo atributos binarios

n atributos

|H|= 22n funciones booleanas distintas

Inducción de árboles de decisión 6

Tarea inducción de árboles de decisión

Dados

Descripción de Instancias, X, (atributos, valores)

Descripción de las Hipótesis, H (espacio de árboles de decisión)

Concepto objetivo, c : X {0,1}

Ejemplos positivos y negativos, D, pares (<x, c(x)>)

Determinar

Hipótesis h de H / h(x) = c(x) para todo xde X

Datos para aplicaciones de concesión de créditos

Nº Riesgo Historia Deuda Avales Ingresos

1 alto mala alta no 0 a 2M

2 alto desconocida alta no 2 a 5M

3 moderado desconocida baja no 2 a 5M

4 alto desconocida baja no 0 a 2M

5 bajo desconocida baja no más de 5M

6 bajo desconocida baja adecuados más de 5M

7 alto mala baja no 0 a 2M

8 moderado mala baja adecuados más de 5M

9 bajo buena baja no más de 5M

10 bajo buena alta adecuados más de 5M

11 alto buena alta no 0 a 2M

12 moderado buena alta no 2 a 5M

13 bajo buena alta no más de 5M

14 alto mala alta no 2 a 5M

7Inducción de árboles de decisión

Árbol de decisión

Historia

DeudaDeuda Avales

DesconocidaMala Buena

Alto Avales

No AdecuadosAlta Baja

Alto Moderado Avales Bajo

Alta Baja

Ingresos Bajo

No Adecuados

Ingresos Bajo

No Adecuados

Alto Moderado Bajo Alto Moderado Bajo

0 a 2 0 a 22 a 5 2 a 5más de 5 más de 5

8Inducción de árboles de decisión

Inducción de árboles de decisión 9

Árbol de decisión “más simple”

Ingresos

Alto

0 a 2 2 a 5 más de 5

Historia Historia

Deuda Alto Moderado Bajo Moderado Bajo

Desconocida MalaBuena DesconocidaMala Buena

Alto Moderado

Alta Baja

2. Algoritmo básico: divide y vencerásInducción analítica (top-down) de árboles de decisión

PROCEDIMIENTO Inducir_Arbol(Ejemplos, Atributos)

BEGIN

SI todos los elementos de Ejemplos pertenecen a la misma clase

ENTONCES devolver un nodo hoja con la clase;

SINO SI Atributos está vacío

ENTONCES devolver nodo hoja con disyunción de clases de Ejemplos;

SINO SI Ejemplos está vacío

ENTONCES devolver un nodo hoja etiquetado “desconocido”;

SINO BEGIN

seleccionar un atributo A como raíz del árbol actual;

eliminar A de Atributos;

PARA CADA valor V de A,

BEGIN

crear una rama del árbol etiquetada con V;

sea particion_V elementos de Ejemplos con valor V en atributo A;

colocar rama V resultado de Inducir_Arbol(particion_V, Atributos);

END;

END;

END 10Inducción de árboles de decisión

Inducción de árboles de decisión 11

3. Heurística para la selección de atributos

¿Atributo más útil para la clasificación?

Elegir atributo cuyo conocimiento aporte mayor información desde la perspectiva de clasificación

Quinlan, ID3 y sucesores: heurística basada en teoría de información

Inducción de árboles de decisión 12

Selección de atributos

¿Qué atributo es mejor?

atributo A atributo B

6+, 4- 6+, 4-

5+, 1- 1+, 3- 3+, 1- 3+, 3-

Inducción de árboles de decisión 13

Fundamentos teoría información

Universo mensajes

M={m1, m2... ...mn}

con probabilidad p(mi), i=1,2... ...n

Información que aporta la recepción de un mensaje

I(M)=-i=1

np(mi)log2(p(mi))

Inducción de árboles de decisión 14

Heurística teoría información

Considerar la clasificación obtenida por un árbol como un mensaje

Estimar el contenido de información a priori, I(D) contenido de información de un mensaje que proporciona la

clasificación de un ejemplo del conjunto de entrenamiento, D, sin conocer el valor de sus atributos

Estimar el contenido de información a posteriori, o resto, Resto(A)

Como antes, pero una vez conocido el valor del atributo A

Seleccionar el atributo A que maximice la ganancia de información Ganancia(D, A) = I(D) – Resto(A)

Inducción de árboles de decisión 15

Información a priori

I(D)

Estimar la probabilidad de cada clase por la frecuencia de aparición en D

Inducción de árboles de decisión 16

Información a posteriori

Resto(A)

Estimar la información promediando la estima para cada posible valor

Conocemos atributo A, con K posibles valores

K particiones de D, según valor de A

Di: partición i-esima conjunto D

Resto(A)= i=1

k|Di|/|D| I(Di)

Datos para aplicaciones de concesión de créditos

Nº Riesgo Historia Deuda Avales Ingresos

1 alto mala alta no 0 a 2M

2 alto desconocida alta no 2 a 5M

3 moderado desconocida baja no 2 a 5M

4 alto desconocida baja no 0 a 2M

5 bajo desconocida baja no más de 5M

6 bajo desconocida baja adecuados más de 5M

7 alto mala baja no 0 a 2M

8 moderado mala baja adecuados más de 5M

9 bajo buena baja no más de 5M

10 bajo buena alta adecuados más de 5M

11 alto buena alta no 0 a 2M

12 moderado buena alta no 2 a 5M

13 bajo buena alta no más de 5M

14 alto mala alta no 2 a 5M

17Inducción de árboles de decisión

Inducción de árboles de decisión 18

Evaluación de la GANANCIA sobre el ejemplo

I(D) = - 6/14log2(6/14) - 3/14log2(3/14) - 5/14log2(5/14)

= - 6/14 *(-1.222) -3/14*(-2.222) -5/14*(-1.485)

= 1.531 bits

GANANCIA(D, Ingresos)= I(D) - Resto(Ingresos)

Resto(Ingresos)

C1={1, 4, 7, 11} C2={2, 3, 12, 14} C3={5, 6, 8, 9, 10, 13}

Resto(Ingresos) = 4/14*I(C1 ) + 4/14*I(C2) + 6/14*I(C3) =

= 4/14*0 + 4/14*1 + 6/14*0.650 =

= 0.564 bits

GANANCIA(D, Ingresos) = 0.967 bits

GANANCIA(D, Historia) =0.266 bits

GANANCIA(D, Deuda) = 0.581 bits

GANANCIA(D, Avales) = 0.756 bits

riesgo alto moderado bajo

frecuencias 6/14 3/14 5/14

Inducción de árboles de decisión 19

4. Espacio de búsqueda y bias inductivo

Espacio de hipótesis:

Conjunto de todos los árboles de decisión o de todas las funciones booleanas

Tamaño espacio de hipótesis

Suponiendo atributos binarios

n atributos

|H|= 22n funciones booleanas distintas

ID3 realiza una búsqueda voraz, escalada, en la dirección de los árboles más simples a los más complejos

Inducción de árboles de decisión 20

Bias BPA-ID3

BPA-ID3:

Primero en anchura, partiendo de árbol vacío, incrementando profundidad

Encuentra árbol de menor profundidad consistente con D

Bias BPA-ID3

Preferir el árbol de menor profundidad.

Inducción de árboles de decisión 21

Bias ID3

ID3: aproximación eficiente a BPA-ID3

Búsqueda heurística voraz, escalada

No garantiza árbol de menor profundidad

Tiende a encontrar árboles sencillos

Aproximación al bias inductivo de ID3

Preferir árboles de menor profundidad. Preferir árboles que sitúan atributos que aportan más información cerca de la raíz

Bias restrictivos /de preferencia

Algoritmo de eliminación de candidatos

Espacio de hipótesis incompleto (por el lenguaje de representación de hipótesis elejido)

Busqueda exhaustiva en el espacio de hipótesis

ID3

Espacio de hipótesis completo

Búsqueda heurística (incompleta): la heurística de selección de atributos impone un orden en la búsqueda de hipótesis

Inducción de árboles de decisión 22

Inducción de árboles de decisión 23

¿Por qué preferir árboles de menor profundidad?

Navaja de Occam: preferir hipótesis más simples que explique los datos

Árbol de decisión hipótesis más simple: árbol de menor profundidad

Justificación adicional Es razonable esperar que las hipótesis más simples

generalicen mejor (clasifique mejor los ejemplos no vistos) pues es razonable esperar que contengan menos atributos irrelevantes

!Validación experimental! (¿más simple = más pequeña?)

Inducción de árboles de decisión 24

5. Sobreajuste

No siempre es una buena estrategia hacer crecer el árbol hasta que clasifique correctamente todos los ejemplo de entrenamiento

Ruido en los ejemplos

¡Podemos aprender el ruido!

Pocos ejemplos

Escasa descripción del concepto objetivo

En ambos casos, mala generalización

Inducción de árboles de decisión 25

Errores

Error de resubstitución, er(h)

Error que comete una hipótesis sobre el conjunto de entrenamiento

= |ejemplos de D mal clasificados|/|D|

Error verdadero o error, eD(h)

Error que comete la hipótesis sobre todo el espacio de instancias X, gobernado por la distribución de probabilidad D

Inducción de árboles de decisión 26

Definición de sobreajuste

Dado un espacio de hipótesis H, una hipótesis h H sobreajusta el conjunto de entrenamiento sii h’ H tal que

er(h) < er(h´)

eD(h) > eD(h’)

Inducción de árboles de decisión 27

Impacto del sobreajuste

Aplicación: aprendizaje del tipo de diabetes de los pacientes

Inducción de árboles de decisión 28

Ejemplo sobreajuste

Nº Riesgo Historia Deuda Avales Ingresos

1 alto mala alta no 0 a 2M

2 alto desconocida alta no 2 a 5M

3 moderado desconocida baja no 2 a 5M

4 alto desconocida baja no 0 a 2M

5 bajo desconocida baja no más de 5M

6 bajo desconocida baja adecuados más de 5M

7 alto mala baja no 0 a 2M

8 moderado mala baja adecuados más de 5M

9 bajo buena baja no más de 5M

10 bajo buena alta adecuados más de 5M

11 alto buena alta no 0 a 2M

12 moderado buena alta no 2 a 5M

13 bajo buena alta no más de 5M

14 alto mala alta no 2 a 5M

Inducción de árboles de decisión 29

Ejemplo sobreajuste

Ingresos

Alto

0 a 2 2 a 5 más de 5

Historia Historia

Deuda Alto Moderado Bajo Moderado Bajo

Desconocida MalaBuena DesconocidaMala Buena

Alto Moderado

Alta Baja

Inducción de árboles de decisión 30

Ejemplo sobreajuste

Imaginar que añadimos un ejemplo etiquetado erróneamente como Riesgo=bajo (en vez de alto) al conjunto inicial de entrenamiento

Nº Riesgo Historia Deuda Avales Ingresos

15 bajo mala alta adecuados 0 a 2M

Inducción de árboles de decisión 31

Ejemplo sobreajuste

Ingresos

0 a 2 2 a 5 más de 5

Historia Historia

DeudaAlto Moderado Bajo Moderado Bajo

Desconocida MalaBuena DesconocidaMala Buena

Alto Moderado

Alta Baja

Avales

AdecuadosNo

Bajo Alto

Inducción de árboles de decisión 32

Motivos sobreajuste

Ruido en los datos

Presencia de regularidades no relevantes en D

Pocos datos

Numerosos atributos

Inducción de árboles de decisión 33

6. Mejoras a ID3

Dificultades en la inducción de árboles

Atributos con valores continuos

Atributos con valores desconocidos

Atributos con numerosos valores

Sobreajuste

Inducción de árboles de decisión 34

Atributos con valores continuos

Se puede discretizar dinámicamente, empleando la misma heurística utilizada para la selección de atributos

Reemplazar los atributos continuos por atributos booleanos que se crean dinámicamente, introduciendo umbrales C

A continuo

A<c , T si a A < C

Inducción de árboles de decisión 35

Discretización atributos continuos

Presión 40 48 60 72 80 90

Clase + + - - - +

Selección de umbral, C: máxima ganancia

Candidatos: valores adyacentes con distinta clase 54=(48+60)/2, 85=(80+90)/2

Para el ejemplo A>54

El nuevo atributo compite con los restantes

Una vez seleccionado, son posibles discretizaciones posteriores En el ejemplo, solo A>85

Inducción de árboles de decisión 36

Atributos con valores desconocidos

En muchos dominios, es frecuente no disponer de los valores de algún(os) atributo(s) para todos los ejemplos

Solución: estimar el valor del atributo en base a los ejemplos para los cuales el atributo tiene valores conocidos

Alternativas Valor más común en nodo actual

Valor más común en nodo actual entre ejemplos de su misma clase

Asignar probabilidades a partir de las frecuencias en nodo actual

Inducción de árboles de decisión 37

Aproximación probabilística

Modificación construcción Generalizar cardinalidad a suma de

probabilidades de pertenencia a la partición

Modificar definición Ganancia(D,A) = F * (I(D)-Resto(A)), siendo F el porcentaje de ejemplos con valor conocido para el atributo A

Si se selecciona el atributo, asignar probabilidades a las ramas

Clasificación Examinar todas las ramas para atributos con

valor desconocido, obteniendose valor más probable (sumando prob. nodos hoja alcanzados)

Inducción de árboles de decisión 38

Atributos con numerosos valores

La heurística de la ganancia favorece la selección de atributos con muchos valores generan muchas particiones con pocos ejemplos de pocas clases

Consecuencia: conocer el valor del atributo tiende a maximizar la ganancia

Ejemplo patológico: añadir atributo DNI al ejemplo de concesión de créditos

El atributo DNI proporciona la máxima ganancia de información: predice perfectamente el riesgo de los ejemplos de D Genera un árbol con un único test y profundidad 1, con un nodo

hoja por cada ejemplo Capacidad de generalización nula

Inducción de árboles de decisión 39

Razón de ganancia

¿Estimación de la información generada al dividir D en k particiones?

Atributo A con k posibles valores

Información media de un mensaje que indique el valor del atributo A de un ejemplo:

IDivisión(D, A)= -i=1

k|Di|/|D| * log2(|Di|/|D| )

Esta expresión proporciona la información generada al dividir D en k subconjuntos

Razón de Ganancia

RG(D, A)= Ganancia(D, A)/IDivision(D, A)

Comportamiento Razón de Ganancia

Penaliza atributos con numerosos valores y ejemplos distribuidos uniformemente

n valores, 1 ejemplo por valor: IDivisión= log2n

2 valores, n/2 ejemplos cada valor: IDivision= 1

Dificultad si algún |Di|~|D| : IDivisión 0

Inducción de árboles de decisión 40

Inducción de árboles de decisión 41

7. Poda de árboles: C4.5

ID3 tiende a general árboles complicados que sobreajustan los datos

Ejemplo patológico

10 atributos , valores binarios, probabilidad 0.5

clase binaria, SI probabilidad 0.25, NO probabilidad 0.75

N=1000, ET 500, EP 500

produce árbol con 119 nodos y tasa error 35%

un árbol, con una única hoja, NO, tendría un error esperado del 25%

Inducción de árboles de decisión 42

Simplificación de Árboles

Métodos de simplificación

prepoda: no subdividir ejemplos según algún criterio

inconveniente: no se sabe cual es el mejor criterio

poda: reemplazar subárboles por una hoja o una de sus ramas

mayor coste computacional, pero mejores resultados

Inducción de árboles de decisión 43

Métodos de poda basados en el error

Utilizan una estimación de la tasa de error de un árbol para realizar la poda

comenzando por las hojas, examinar los subárboles de los nodos no terminales

reemplazar cada subárbol por el nodo terminal o la rama que clasifique más casos, si esto mejora la tasa de error del subárbol

como la estimación del error de un árbol disminuye al disminuir la tasa de error de cada uno de sus subárboles, este proceso genera un árbol cuya estimación de la tasa de error es minimal respecto a las distintas formas de poda

Inducción de árboles de decisión 44

Métodos de poda basados en el error

Observar que la poda del árbol siempre incrementa la tasa de error del árbol calculada sobre los ejemplos de entrenamiento

Distintas familias de técnicas según el método de estimación de errores

Entrenamiento y validación

Métodos pesimistas

Inducción de árboles de decisión 45

Poda mediante entrenamiento y validación

Separar D en tres conjuntos disjuntos

T, conjunto de entrenamiento

V, conjunto de validación

P, conjunto para prueba (estimación del error)

Crear árbol con T, hasta valor mínimo er

Podar árbol hasta que la estimación de eD, según V, empeore

Inducción de árboles de decisión 46

Efecto de la poda mediante entrenamiento y validación

Inducción de árboles de decisión 47

Inconvenientes de la poda mediante entrenamiento y validación

Se precisa un número elevado de datos por la necesidad de usar tres conjuntos disjuntos

Alternativa: evitar el uso de V para guiar la poda

Método pesimista (Quinlan 87): se basan en reemplazar subárbol por hoja si una estimación pesimista del error en la hoja es mejor que la estimación pesimista del error del subárbol

Inducción de árboles de decisión 48

C4.5

Método de inducción de árboles basado en ID3

Mejoras para atributos continuos, desconocidos, con múltiples valores

Poda pesimista

Generación de reglas

Última versión: C4.8 (implementado en WEKA como J4.8)

Inducción de árboles de decisión 49

Estimación del error

Suponer que la observación de E errores en N ejemplos sigue un distribución binomial Experimento base: cometer un error al clasificar un

ejemplo Probabilidad: tasa de error del clasificador

Observación disponible: E errores cometidos al clasificar N ejemplos de entrenamiento

Fijado un nivel de confianza, c%, la distribución binomial proporciona el intervalo de confianza de la probabilidad del experimento base

Inducción de árboles de decisión 50

Estimación pesimista del error

Uc(E,N):extremo superior del intervalo de confianza

Estimar el error al clasificar instancia no vista por Uc(E,N) sobre el conjunto de entrenamiento

Suponer que cada hoja clasifica tantas instancias como ejemplos de entrenamiento Estimación error: N*Uc(E,N)

Estimación error subárbol: suma estimación ramas

Vo

tació

n c

on

greso

: árb

ol sin

po

dar

51Inducción de árboles de decisión

Inducción de árboles de decisión 52

Ejemplo poda

Suponer subárbol

education spending=no : democrat (6)

education spending=yes: democrat (9)

education spending=no: republican(1)

Estimación del error:

6*U25(0, 6)+9*U25(0,9)+1*U25(0,1)=3.273

6*0.206+9*0.143+1*0.750=3.273

Si reemplazamos el subárbol por una única hoja, etiquetada DEMOCRAT, se comete un único error y su estimación es:

16*U25(1,16)=16*0.175=2.512

Según este criterio, se realizaría la poda

Inducción de árboles de decisión 53

Votación congreso: árbol podado

Inducción de árboles de decisión 54

Interpretación geométrica del aprendizaje en árboles (I)

Descripción ejemplos: vector de características

Ejemplo: punto en espacio N-dimensional (N atributos)

Interpretación geométrica del aprendizaje: dividir el espacio en regiones etiquetadas con una sola clase

Clasificación ejemplos no vistos: según región en que se sitúen

En el caso de los árboles: hiperrectangulos

Inducción de árboles de decisión 55

Ejemplo interpretación geométrica (I)

Suponer dos atributos X, Y continuos, discretizados (X < C, Y < C`)

Cada test: hiperplano ortogonal al eje del atributo

C

C`

Inducción de árboles de decisión 56

Ejemplo interpretación geométrica (II)

Concepto objetivo: suponer recta pendiente no nula

C

C`

Inducción de árboles de decisión 57

Ejemplo interpretación geométrica (III)

Cuando no usar árboles Regiones con baja densidad de puntos: mucha holgura para

determinar fronteras Regiones con puntos de distintas clases: distribución probabilística

que no se representa bien con un árbol

C

C`

Inducción de árboles de decisión 58

Conclusiones

Método robusto y transportable a distintas tareas

Comparable a redes de neuronas, como clasificador Árboles: menor coste computacional, conocimiento

explicito

Redes: mayor precisión

Adecuados si Se buscan conceptos disyuntivos

Se requiere conocimiento explícito

Ruido (poda)

Inducción de árboles de decisión 59

Ejemplos de aplicación

Quinlan, 79, ID3, finales de ajedrez

1,4 millones posiciones, 49 atributos binarios: 715 configuraciones distintas Entrenamiento 20%, aleatorio

Tasa acierto: 84%

Induction of decision trees, Machine learning, 1, 81-106, 1986

Inducción de árboles de decisión 60

Ejemplos de aplicación

Soybean (semillas de soja)

R.S. Michalski and R.L. Chilausky, 1980

Diagnosis de enfermedades en las semillas de soja

19 clases (15 significativas)

35 atributos

307 Instancias

Tasa error 11% (C4.5)

J.W. Shavlik, R.J. Mooney, and G.G. Towell. Symbolic and neural learning algorithms: an experimental comparison, machine learning. Machine Learning, 6(2):111-- 143, 1991

Inducción de árboles de decisión 61

Ejemplos de aplicación

Quinlan, hipotiroides, principio 80

varios miles ejemplo

7 atributos continuos, 23 discretos

3-8 clases

Tasa error < 1%

Quinlan J. R. Comparing connectionist and symbolic learning methods. In: Rivest R. L. ed. Computational Learning Theory and Natural Learning Systems, vol.1, Cambridge, MA: MIT Press, 1994, pp.445-456

Inducción de árboles de decisión 62

Ejemplo actual

Console, Picardi, Theseider.

Temporal Decision Trees: Model-based Diagnosis of Dynamic Systems On-Board. Journal of Artificial Intelligence Research 19 (2003) 469-512

Árboles de decisión con restricciones temporales

Aplicación: Diagnosis on board para automóviles

Inducidos a partir de ejemplos generados mediante técnicas de diagnosis basada en modelos