Download Inducción de Árboles de Decisión

Inducción de Árboles de
Decisión
ID3, C4.5
Contenido
1.
2.
3.
4.
5.
6.
7.
8.
9.
Representación mediante árboles de decisión
Algoritmo básico: divide y vencerás
Heurística para la selección de atributos
Espacio de búsqueda y bias inductivo
Sobreajuste
Mejoras a ID3
Poda de árboles: C4.5
Interpretación geométrica aprendizaje con
árboles
Conclusiones y ejemplos de aplicación
Inducción de árboles de decisión
2
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
3
Árbol de decisión
Concepto: “Riesgo en la concesión de crédito”
Ingresos
0a2
2a5
Alto
Historia
Desconocida
Deuda
Alta
Alto
más de 5
Mala
Alto
Historia
Buena
Desconocida
Mala
Buena
Moderado
Bajo
Moderado
Bajo
Baja
Moderado
Inducción de árboles de decisión
4
Espacio de hipótesis

Si clase de decisión binaria


Espacio de hipótesis:


Cada árbol de decisión representa una
función booleana
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
n
2
|H|= 2 funciones booleanas distintas
Inducción de árboles de decisión
5
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 x
de X
Inducción de árboles de decisión
6
Datos para aplicaciones de
concesión de créditos
Nº
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Riesgo
alto
alto
moderado
alto
bajo
bajo
alto
moderado
bajo
bajo
alto
moderado
bajo
alto
Historia
mala
desconocida
desconocida
desconocida
desconocida
desconocida
mala
mala
buena
buena
buena
buena
buena
mala
Deuda
alta
alta
baja
baja
baja
baja
baja
baja
baja
alta
alta
alta
alta
alta
Avales
no
no
no
no
no
adecuados
no
adecuados
no
adecuados
no
no
no
no
Ingresos
0 a 2M
2 a 5M
2 a 5M
0 a 2M
más de 5M
más de 5M
0 a 2M
más de 5M
más de 5M
más de 5M
0 a 2M
2 a 5M
más de 5M
2 a 5M
Inducción de árboles de decisión
7
Árbol de decisión
Historia
Desconocida
Buena
Mala
Deuda
Avales
Alta
Baja
No
Alto
Avales
Alto
No
Deuda
Moderado
Adecuados
Ingresos
0a2
2a5
Alto
Moderado
Bajo
Ingresos
0a2
Alto
Baja
Avales
No
Bajo
más de 5
Alta
Adecuados
2a5
Moderado
Bajo
Adecuados
Bajo
más de 5
Bajo
Inducción de árboles de decisión
8
Árbol de decisión “más simple”
Ingresos
0a2
2a5
Alto
Historia
Desconocida
Deuda
Alta
Alto
más de 5
Mala
Alto
Historia
Buena
Desconocida
Mala
Buena
Moderado
Bajo
Moderado
Bajo
Baja
Moderado
Inducción de árboles de decisión
9
2. Algoritmo básico: divide y vencerás
Inducció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
Inducción de árboles de decisión 10
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
11
Selección de atributos

¿Qué atributo es mejor?
6+, 4-
6+, 4-
atributo A
5+, 1-
1+, 3-
atributo B
3+, 1-
3+, 3-
Inducción de árboles de decisión
12
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
n
I(M)=- i=1 p(mi)log2(p(mi))
Inducción de árboles de decisión
13
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)


Estimar el contenido de información a posteriori, o
resto, Resto(A)


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
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
14
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
15
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=1k |Di|/|D| I(Di)
Inducción de árboles de decisión
16
Datos para aplicaciones de
concesión de créditos
Nº
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Riesgo
alto
alto
moderado
alto
bajo
bajo
alto
moderado
bajo
bajo
alto
moderado
bajo
alto
Historia
mala
desconocida
desconocida
desconocida
desconocida
desconocida
mala
mala
buena
buena
buena
buena
buena
mala
Deuda
alta
alta
baja
baja
baja
baja
baja
baja
baja
alta
alta
alta
alta
alta
Avales
no
no
no
no
no
adecuados
no
adecuados
no
adecuados
no
no
no
no
Ingresos
0 a 2M
2 a 5M
2 a 5M
0 a 2M
más de 5M
más de 5M
0 a 2M
más de 5M
más de 5M
más de 5M
0 a 2M
2 a 5M
más de 5M
2 a 5M
Inducción de árboles de decisión
17
Evaluación de la GANANCIA
sobre el ejemplo
I(D)
riesgo
alto
moderado
bajo
frecuencias
6/14
3/14
5/14
= - 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,
GANANCIA(D,
GANANCIA(D,
GANANCIA(D,
Ingresos) = 0.967 bits
Historia) =0.266 bits
Deuda) = 0.581 bits
Avales) = 0.756 bits
Inducción de árboles de decisión
18
4. Espacio de búsqueda y bias
inductivo

Espacio de hipótesis:


Tamaño espacio de hipótesis




Conjunto de todos los árboles de decisión o de todas
las funciones booleanas
Suponiendo atributos binarios
n atributos
n
|H|= 22 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
19
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
20
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
Inducción de árboles de decisión
21
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
¿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
23
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
24
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
25
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
26
Impacto del sobreajuste

Aplicación: aprendizaje del tipo de diabetes de
los pacientes
Inducción de árboles de decisión
27
Ejemplo sobreajuste
Nº
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Riesgo
alto
alto
moderado
alto
bajo
bajo
alto
moderado
bajo
bajo
alto
moderado
bajo
alto
Historia
mala
desconocida
desconocida
desconocida
desconocida
desconocida
mala
mala
buena
buena
buena
buena
buena
mala
Deuda
alta
alta
baja
baja
baja
baja
baja
baja
baja
alta
alta
alta
alta
alta
Avales
no
no
no
no
no
adecuados
no
adecuados
no
adecuados
no
no
no
no
Ingresos
0 a 2M
2 a 5M
2 a 5M
0 a 2M
más de 5M
más de 5M
0 a 2M
más de 5M
más de 5M
más de 5M
0 a 2M
2 a 5M
más de 5M
2 a 5M
Inducción de árboles de decisión
28
Ejemplo sobreajuste
Ingresos
0a2
2a5
Alto
Historia
Desconocida
Deuda
Alta
Alto
más de 5
Mala
Alto
Historia
Buena
Desconocida
Mala
Buena
Moderado
Bajo
Moderado
Bajo
Baja
Moderado
Inducción de árboles de decisión
29
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
15 bajo
Historia
mala
Deuda
alta
Avales
Ingresos
adecuados 0 a 2M
Inducción de árboles de decisión
30
Ejemplo sobreajuste
Ingresos
0a2
2a5
Avales
Adecuados
Bajo
No
Alto
Historia
Desconocida
Deuda
Alta
Alto
más de 5
Alto
Mala
Historia
Buena
Moderado
Desconocida
Bajo
Mala
Buena
Moderado
Bajo
Baja
Moderado
Inducción de árboles de decisión
31
Motivos sobreajuste


Ruido en los datos
Presencia de regularidades no
relevantes en D


Pocos datos
Numerosos atributos
Inducción de árboles de decisión
32
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
33
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
34
Discretización atributos
continuos




40 48 60 72 80 90
Clase
+
+
-
-
-
+
Selección de umbral, C: máxima ganancia
Candidatos: valores adyacentes con distinta clase


Presión
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
35
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
36
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
37
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
38
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=1k |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)
Inducción de árboles de decisión
39
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
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
41
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
42
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
43
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
44
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
45
Efecto de la poda mediante
entrenamiento y validación
Inducción de árboles de decisión
46
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
47
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
48
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
49
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
Inducción de árboles de decisión
50
Votación congreso:
árbol sin podar
Inducción de árboles de decisión
51
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
52
Votación congreso: árbol podado
Inducción de árboles de decisión
53
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
54
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
55
Ejemplo interpretación
geométrica (II)

Concepto objetivo: suponer recta pendiente no
nula
C`
C
Inducción de árboles de decisión
56
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
57
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
58
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
59
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
60
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
61
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
Inducción de árboles de decisión
62