Aprendizaje de árboles de decisión Aprendizaje de árboles de decisión

Aprendizaje de árboles de decisión Aprendizaje de árboles de decisión - Page 1
Aprendizaje de árboles de decisión Aprendizaje de árboles de decisión - Page 2
Aprendizaje de árboles de decisión Aprendizaje de árboles de decisión - Page 3
Aprendizaje de árboles de decisión Aprendizaje de árboles de decisión - Page 4
Aprendizaje de árboles de decisión Aprendizaje de árboles de decisión - Page 5

Esto es sólo una vista previa del documento.

Descargar el documento original para ver más páginas

Descargar

1 de 19

Aprendizaje de árboles de decisión Aprendizaje de árboles de decisión


Documentos relacionados


Microsoft PowerPoint - decision.ppt [Modo de compatibilidad] Transcripciones

1
Aprendizaje de árboles de decisión
José M. Sempere
Departamento de Sistemas Informáticos y Computación
Universidad Politécnica de Valencia
Aprendizaje de árboles de decisión
1. Introducción. Definición y algoritmos de aprendizaje.
2. Conceptos básicos de teoría de la información
3 El algoritmo ID3.   
4. Extensiones hacia el algoritmo C4.5
5. Una versión incremental del ID3: El algoritmo ID5R
Bibliografía
• T. Mitchell. Machine Learning. Ed. McGraw-Hill. 1997.
• B Sierra Aprendizaje Automático Ed Pearson- Prentice Hall 2006. .  . .  . .
• J.R. Quinlan. C 4.5: programs for machine learning.  Ed. Morgan Kaufmann. 1993.
2
Un árbol de decisión es una representación de una función
multievaluada
f: A 1  A 2  ...  A n  B
A 1
l(A 1 j)
A 2
oprel(A 1.v,v1) opre .v,v
B .v2B .v1
A n
oprel(A j.v,vk) = {A j.v = vk, 
A j.v  vk 
A j.v  vk 
A j.v  vk,
... }
oprel(A n.v,v1) oprel(A n.v,vh)
Ejemplo: Árbol de decisión para “¿ Administrar fármaco F ?”
Presión arterial ?
BajaMedia
Í Sí
Alta
Azúcar en sangre ?
Alto
ndice de colesterol ?
Alergia a antibióticos ? SíNo
Bajo
Sí
Alto Bajo
Sí No
Otras alergias ? Sí
SíNo
NoSí
3
Los árboles de decisión son adecuados cuando ...
• Las instancias del concepto son representadas por pares
atributo-valor
• La función objetivo tiene valores de salida discretos
• Las descripciones del objeto son disyuntivas
• El conjunto de aprendizaje tiene errores
• El conjunto de aprendizaje  es incompleto 
Algunos algoritmos para el aprendizaje 
de árboles de decisión
• Hoveland y Hunt (1950): Concept Learning Systems (CLS)
• Breiman, Friendman, Olshen y Stone (1984): Método CART
• J.R. Quinlan (1973, 1986): Método ID3
• J.R. Quinlan (1994): Método C4.5
• G.V. Kass (1980): Método CHAID
• Otras mejoras del C4.5: J4.8, C5.0
• J. Schlimmer y D. Fisher (1986): ID4 e ID4R
• P. Utgoff (1990): ID5 e ID5R
4
 
Un algoritmo genérico para el aprendizaje de 
árboles de decisión 
Entrada: Un conjunto de ejemplos de aprendizaje (tuplas supervisadas) E
Salida: Un árbol de decisión T
Método:
Crear una raiz para el árbol.
si todos los ejemplos pertenecen a la clase Cj
entonces return (raiz,Cj)
sino
Seleccionar un atributo X con valores x1, x2, …, xM
Particionar E de acuerdo con los valores del atributo E1, E2, …, EM
Construir árboles de decisión para cada partición T1, T2, …, TM
return (raiz(T T T )) 1, 2, …, M
finMétodo T1
X = x2
X = xMX = x1
T2 TM
raiz
Conceptos básicos de la teoría de la información (I)
Teoría de la probabilidad
Variables independientes
p(x,y)=p(x)p(y)
Probabilidad condicional y conjunta
p(x,y)=p(x|y)p(y)
p(x,y)=p(y|x)p(x)
)(
)()|()|(
yp
xpxypyxp 
Teorema de Bayes ( regla de Bayes )
5
Conceptos básicos de la teoría de la información (II)



n
i
ii xXpxXpXH
1
2 )(log )()(
Entropía H(x)

x
yxpyxpyXH )|(log )|()|( 2

y x
yxpyxpypYXH )|(log )|()()|( 2
Teorema (1) H(X Y)  H(X) + H(Y)
p(x)0.5
. ,    
(2) H(X,Y) = H(X) + H(Y) sii X e Y son independientes
Teorema. H(X,Y) = H(Y) + H(X |Y) = H(X) + H(Y | X)
Corolario (1) H(X | Y)  H(X)
(2) H(X | Y) = H(X) sii X e Y son independientes.
El algoritmo de aprendizaje de árboles de decisión ID3
J.R Quinlan (1986)
• Búsqueda voraz top-down
• Basado en un criterio estadístico 
• Selección de atributos mediante el Principio de ganancia de información
S: conjunto de ejemplos clasificados en C clases
A: Atributo de los ejemplos
S Ej l l t ib t A ti l l
)(
||
||
)(),(
)(
SS v
AValoresv
Entropía
S
SEntropíaASGanancia V


v: emp os que en e  a r u o  enen e  va or v
6
 
Algoritmo ID3(Ejemplos, Atributo_salida, Atributos)
Ejemplos: Ejemplos de aprendizaje.
Atributo_salida: Atributo a predecir por el árbol.
Atributos: Lista de atributos a comprobar por el árbol.
(1) Crear una raiz para el árbol.
(2) Si todos los ejemplos son positivos Return(raiz,+)
(3) Si t d l j l ti R t ( i )o os os e emp os son nega vos e urn ra z,-
(4) Si Atributos=Return(raiz,l)
( l es el máximo valor común de Atributo_salida en Ejemplos )
Si ninguna de las anteriores condiciones se cumple 
Begin
(1) Seleccionar el atributo A con mayor Ganancia(Ejemplos,A)
(2) El atributo de decisión para raiz es A
(3) Para cada posible valor vi de A
(3.1) Añadir una rama a raiz con el test A=vi
(3.2) Ejemplos_vi es el subconjunto de Ejemplos con valor vi para A
(3.3) Si Ejemplos_vi=
entonces añadir un nodo (n,l) a partir de la rama creada. 
(l es el máximo valor común de Atributo_salida en Ejemplos).
sino añadir a la rama creada el subárbol
ID3(Ejemplos_vi, Atributo_salida, Atributos-{A})
End
Return(raiz)
Paciente Presión 
arterial
Azúcar en 
sangre
Índice de 
colesterol
Alergia a 
antibióticos
Otras 
alergias
Administrar 
fármaco F
1 Alta Alto Alto No No Sí
2 Alta Alto Alto Sí No Sí
3 Baja Alto Bajo No No Sí
Un ejemplo: ¿Administrar fármaco F?
4 Media Alto Alto No Sí No
5 Media Bajo Alto Sí Sí No
6 Baja Bajo Alto Sí Sí Sí
7 Alta Bajo Alto Sí No Sí
8 Alta Bajo Bajo No Sí Sí
9 Alta Alto Bajo Sí Sí No
10 Baja Bajo Alto Sí Sí Sí
11 Media Bajo Bajo Sí Sí Sí
12 Alta Bajo Alto Sí Sí No
13 Baja Alto Alto Sí Sí Sí
14 Baja Alto Bajo No No Sí
7
Cálculo de entropías y ganancia de la información respecto del 
atributo Presión arterial
863121.0
14
4log
14
4 - 
14
10log
14
10-  log  )( 222
1
 

i
c
i
i ppSEntropía
2244 0.918296
6
log
6
 - 
6
log
6
-   )( 22 AltaPASEntropía
0 
5
5log
5
5-   )( 2 BajaPASEntropía
0.918296
3
1log
3
1 - 
3
2log
3
2-   )( 22 MediaPASEntropía
0.2727880.918296
14
3  0
14
5918296.0
14
6 0.863121  ),( PASGanancia
Cálculo de entropías y ganancia de la información respecto del 
atributo Azúcar en sangre
863121.0
14
4log
14
4 - 
14
10log
14
10-  log  )( 222
1


i
c
i
i ppSEntropía
863121.0
7
2log
7
2 - 
7
5log
7
5-   )( 22 AltoASSEntropía
863121.0
7
2log
7
2 - 
7
5log
7
5-   )( 22 BajoASSEntropía
00.863121
14
7863121.0
14
7 0.863121  ),( ASSGanancia
8
Cálculo de entropías y ganancia de la información respecto del 
atributo Índice de colesterol
863121.0
14
4log
14
4 - 
14
10log
14
10-  log  )( 222
1


i
c
i
i ppSEntropía
918296.0
9
3log
9
3 - 
9
6log
9
6-   )( 22 AltoICSEntropía
721928.0
5
1log
5
1 - 
5
4log
5
4-   )( 22 BajoICSEntropía
0.01495640.721928
14
5918296.0
14
9 0.863121  ),( ICSGanancia
Cálculo de entropías y ganancia de la información respecto del 
atributo Alergia a antibióticos
863121.0
14
4log
14
4 - 
14
10log
14
10-  log  )( 222
1


i
c
i
i ppSEntropía
918296.0
9
3log
9
3 - 
9
6log
9
6-   )( 22 SIAASEntropía
721928.0
5
1log
5
1 - 
5
4log
5
4-   )( 22 NOAASEntropía
0149564.00.721928
14
5918296.0
14
9 0.863121  ),( AASGanancia
9
Cálculo de entropías y ganancia de la información respecto del 
atributo Otras alergias
863121.0
14
4log
14
4 - 
14
10log
14
10-  log  )( 222
1


i
c
i
i ppSEntropía
991076.0
9
4log
9
4 - 
9
5log
9
5-   )( 22 SIOASEntropía
0 
5
5log
5
5-   )( 2 NOOASEntropía
226001.00
14
5991076.0
14
9 0.863121  ),( OASGanancia
Selección del mejor atributo que explica las decisiones
Ganancia(S,PA) = 0.272788
Ganancia(S,AS) = 0
Ganancia(S,IC) = 0.0149564
Ganancia(S,AA) = 0.0149564
Ganancia(S,OA) = 0.226001
10
Presión arterial ?
BajaMediaAlta
Paciente Presión 
arterial
Azúcar en 
sangre
Índice de 
colesterol
Alergia a 
antibióticos
Otras 
alergias
Administrar 
fármaco F
1 Alta Alto Alto No No Sí
2 Alta Alto Alto Sí No Sí
3 Baja Alto Bajo No No Sí
4 Media Alto Alto No Sí No
5 Media Bajo Alto Sí Sí No
6 Baja Bajo Alto Sí Sí Sí
7 Alta Bajo Alto Sí No Sí
8 Alta Bajo Bajo No Sí Sí
9 Alta Alto Bajo Sí Sí No
10 Baja Bajo Alto Sí Sí Sí
11 Media Bajo Bajo Sí Sí Sí
12 Alta Bajo Alto Sí Sí No
13 Baja Alto Alto Sí Sí Sí
14 Baja Alto Bajo No No Sí
11
Tabla de datos para calcular el  subárbol  de   PA=Alta
Paciente Azúcar en 
sangre
Índice de 
colesterol
Alergia a 
antibióticos
Otras 
alergias
Administrar 
fármaco F
1 Alto Alto No No Sí
2 Alto Alto Sí No Sí
7 Bajo Alto Sí No Sí
8 Bajo Bajo No Sí Sí
9 Alto Bajo Sí Sí No
12 Bajo Alto Sí Sí No
Características del ID3
Espacio de hipótesis completo
Hipótesis única en cada momento de tiempo      
No se realiza “backtracking” 
Búsqueda no incremental
Principio de “la navaja de Occam” (MDL)
Saturación sobre los datos (“overfitting”)
12
Hacia el algoritmo de aprendizaje de árboles de decisión C4.5
El problema de la saturación (“overfitting”)
Dado un  espacio de  hipótesis H, una hipótesis h  H diremos que
satura un conjunto de aprendizaje si existe otra hipótesis h’ tal que
h tiene menor error  que h’ sobre  el conjunto de aprendizaje, pero
h’ ti h b l di t ib ió t t l d i t i ene  menor error que  so re a s r uc n  o a  e ns anc as
de aprendizaje.
Posible solución (C4.5)
Utilizad un conjunto de aprendizaje A y un conjunto de validación V.
1. Inferir el árbol con el conjunto A
2. Establecer todas las posibles podas del árbol (convirtiendo los caminos 
desde la raíz en reglas de decisión y eliminando precondiciones)
3 Para cada poda medir el error respecto del conjunto V.          
4. Ordenad los mejores resultados y aplicadlos en la fase de test.
Si (PA=Media)  (IC=alto)
entonces NO administrar F
Si (PA=Media)
entonces NO administrar F
Si (IC=alto)
entonces NO administrar F
Hacia el algoritmo de aprendizaje de árboles de decisión C4.5
Evaluación de atributos continuos
Cómo incorporar atributos continuos en las fases de aprendizaje y de test: 
Dada una variable x de carácter continuo, estableced los intervalos adecuados 
en sus valores para proporcionar variables discretas
0 10 20 30 40 50Temperatura
T c T> cc
Problema: ¿ Cómo seleccionar el (los) valor(es) de c ?
Posible solución: Seleccionad aquellos valores que mayor ganancia de 
información proporcionen
13
Hacia el algoritmo de aprendizaje de árboles de decisión C4.5
Incorporación de otras medidas para la selección de atributos
Problema: La medida Ganancia favorece aquellas variables con mayor número
de posibles valores
Posible solución
||
||log
||
||),( 2
1 S
S
S
SASmationSplitInfor i
c
i
i


Dados S (un conjunto de ejemplos de aprendizaje) y A (un atributo de los
ejemplos que puede tomar c posibles valores) definimos … 
SplitInformation(S,A) denota la entropía de S con respecto a los valores de A
),(
),(),(
ASmationSplitInfor
ASGananciaASanciaRatiodeGan 
El RatiodeGanacia(S,A) favorece aquellos atributos que, en igualdad de Ganacia,
separen los datos en menos clases.
Hacia el algoritmo de aprendizaje de árboles de decisión C4.5
Manejo de ejemplos incompletos (atributos no evaluados)
Problema: Dado un conjunto de ejemplos ¿ qué hacer cuando algunos atributos
no tienen valor ?
Posibles soluciones
(1) Estimar el valor desconocido como el valor mayoritario que aparece en el
el resto de ejemplos
(2) Asignar a cada posible valor una probabilidad (frecuencia) de acuerdo con
el resto de ejemplos. A continuación repartir el ejemplo en cada uno de sus
valores de acuerdo con la probabilidad y hacer el cálculo de la Ganancia
En el caso de la clasificación, los casos con valores desconocidos se clasifican
de acuerdo con la mayor probabilidad que proporcione el árbol.
14
Hacia el algoritmo de aprendizaje de árboles de decisión C4.5
Introduciendo costes en los atributos
Problema: ¿ Todos los atributos son igual de valiosos al hacer una clasificación ?
Posible solución
)(
),(2
ACoste
ASGanancia
 
Incorporar el coste de evaluar cada atributo a la hora de estimar el
mejor de todos ellos. Algunas medidas pueden ser las siguientes
w
ASGanancia
ACoste )1)((
12 ),(


w es una constante entre 0 y 1 que evalúa la
importancia del Coste frente a la Ganancia
Una versión incremental del algoritmo ID3: ID5R
(para versiones dicotómicas en la decisión)
Nueva información en los nodos de decisión
Sea A el conjunto de atributos presentes en los ejemplos.
Sea ai el i-ésimo atributo de un ejemplo      
Sea Vi el conjunto de valores posibles para ai
Sea vij el valor j-esimo del atributo ai
Definimos la función E



iV
ijij npI
np
aE )()(
p = número de ejemplos positivos
n = número de ejemplos negativos
pij = número de ejemplos positivos con valor vij
 j
ijiji np1
,        
nij= número de ejemplos negativos con valor vij














caso otroen     loglog
0  si                                                             0
0  si                                                             0
),(
yx
y
yx
y
yx
x
yx
x
y
x
yxI

© 2016 - 2017 Docmia. Todos los derechos reservados.