Tema 12: Arboles de decisión

Tema 12: Arboles de decisión - Page 1
Tema 12: Arboles de decisión - Page 2
Tema 12: Arboles de decisión - Page 3
Tema 12: Arboles de decisión - Page 4
Tema 12: Arboles 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 36

Tema 12: Arboles de decisi´ on


Documentos relacionados


Tema 12: Arboles de decisión Transcripciones

Razonamiento Automático Curso 2000–2001
Tema 12: Arboles de decisión
José A. Alonso Jiménez
Miguel A. Gutiérrez Naranjo
Dpto. de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla
RA 2000–01 CcIa Arboles de decisión 12.1
¿Qué es el Aprendizaje mediante árboles de decisión?
• El aprendizaje mediante árboles de decisión es un método de aproxi-
mación de una función objetivo de valores discretos en el cual la función
objetivo es representada mediante un árbol de decisión.
• Los árboles aprendidos también pueden representarse como un conjunto
de reglas Si–entonces
RA 2000–01 CcIa Arboles de decisión 12.2
Un ejemplo
Cielo Temperatura Humedad Viento Agua Forecast Hacer Deporte
Soleado Templada Alta Débil Fŕıa Sigue igual No
Soleado Templada Normal Débil Fŕıa Sigue igual Śı
Nublado Templada Normal Débil Fŕıa Sigue igual Śı
Lluvioso Templada Normal Fuerte Templada Cambio No
Lluvioso Templada Normal Débil Fŕıa Cambio Śı
• ¿Cuándo hacemos deporte?
• ¿Podemos definir el concepto Hacer Deporte?
RA 2000–01 CcIa Arboles de decisión 12.3
Un ejemplo de árbol de decisión
  Cielo
Nublado
Humedad
NormalAlta
No Si
Viento  
Fuerte Debil
No Si
Si
LluviosoSoleado
RA 2000–01 CcIa Arboles de decisión 12.4
El problema de la representación
El árbol anterior corresponde a la hipótesis:
(Cielo = Soleado ∧Humedad = Normal)
∨ (Cielo = Nublado)
∨ (Cielo = Lluvioso ∧ V iento = Debil)
Representación:
• Cada nodo que no sea una hoja representa un atributo.
• Las aristas que partan del nodo etiquetado con el atributo A están etiquetadas con cada
uno de los posibles valores del atributo A.
• Cada hoja corresponde a un valor de la clasificación
RA 2000–01 CcIa Arboles de decisión 12.5
Cuestiones sobre árboles de decisión
x ¿Cuándo usar árboles de decisión?
u Podemos describir los ejemplos en términos de pares atributo–valor
u La función objetivo toma valores discretos
u Posibilidad de ruido en el conjunto de entrenamiento
u Pueden no conocerse los valores de algunos atributos en los ejemplos del conjunto
de entrenamiento
x Ejemplos:
u Diagnóstico médico
u Análisis de riesgo en la concesión de créditos
u Elaboración de horarios
RA 2000–01 CcIa Arboles de decisión 12.6
Cuestiones sobre árboles de decisión
x ¿Cuál es el árbol de decisión correcto?
u Navaja de Occam
u El mundo es inherentemente simple
u El árbol de decisión más pequeño consistente con la muestra es el que tiene más
probabilidades de identificar objetos desconocidos de manera correcta
u Menor profundidad
u Menor número de nodos
x ¿Cómo se puede construir el árbol de decisión más pequeño?
u Búsqueda en escalada
RA 2000–01 CcIa Arboles de decisión 12.7
Algoritmo básico (I)
• Árbol inicial: Árbol con un único nodo, sin etiquetar, al que asignamos
como conjunto de ejemplos todo el conjunto de entrenamiento.
• Bucle principal:
– Consideramos el primer nodo, N , sin etiquetar
∗ Si los ejemplos asignados N tienen todos la misma clasificación,
etiquetamos N con esa clasificación.
∗ En otro caso ...
RA 2000–01 CcIa Arboles de decisión 12.8
Algoritmo básico (II)
· Etiquetamos N con el mejor atributo A según el conjunto de
ejemplos asignado.
· Para cada valor de A creamos una nueva arista descendente en el
nodo N , y al final de cada una de esas nuevas aristas creamos un
nuevo nodo sin etiquetar, N1, . . . , Nk.
· Separamos los ejemplos asignados al nodo N según el valor que
tomen para el atributo A y creamos nuevos conjuntos de ejemplos
para N1, . . . , Nk.
•Hasta que todos los nodos estés etiquetados
¿Qué atributo clasifica mejor?
RA 2000–01 CcIa Arboles de decisión 12.9
E
n
tr
o
ṕ
ıa
(D
e
fi
n
ic
ió
n
)
•D
e
fi
n
ic
ió
n
:
S
ea
P
=
{p
1
,p
2
,.
..
,p
n
}u
n
a
d
is
tr
ib
u
ci
ón
d
e
p
ro
b
ab
ili
d
ad
.
L
la
m
am
os
e
n
tr
o
ṕ
ıa
b-
ar
ia
d
e
la
d
is
-
tr
ib
u
ci
ón
P
a
H
b(
p 1
,p
2
,.
..
,p
n
)
=
−
i=
n
∑ i=
1
p i
lo
g b
p i
•L
a
fu
n
ci
ón
d
e
en
tr
oṕ
ıa
H
2
(p
,1
−
p)
=
p
lo
g 2
1 p
+
(1
−
p)
lo
g 2
1
1
−
p
es
m
u
y
co
m
ú
n
y
n
os
re
fe
ri
m
os
a
el
la
co
m
o
la
fu
n
ci
ón
d
e
en
tr
oṕ
ıa
y
se
d
en
ot
a
p
or
H
(p
).
S
u
gr
áfi
ca
es
Entropy(S)
1.
0
0.
5 0.
0
0.
5
1.
0
p +
R
A
20
00
–0
1
C
c
I a
A
rb
ol
es
d
e
d
ec
is
ió
n
12
.1
0
Entroṕıa
•D es un conjunto de entrenamiento
• P y N son, respectivamente, la cantidad de ejemplos positivos y negativos
en D
• T es el número total de ejemplos de D
• La entroṕıa de esta distribución es:
u Fórmula: I(P, N) = H2(P/T, N/T ) =
{
0, si N ∗ P = 0;
−P
T
log2
P
T
− N
T
log2
N
T
, si N ∗ P 6= 0.
u Ejemplo: I(9, 9) = − 9
18
log2
9
18
− 9
18
log2
9
18
= 1
(El término entroṕıa fue usado por primera vez por Clausius en 1864 e introducido en la teoŕıa de la
información por Shannon en 1948)
RA 2000–01 CcIa Arboles de decisión 12.11
O
tr
o
e
je
m
p
lo
D
ı́a
C
ie
lo
T
em
p
er
at
u
ra
H
u
m
ed
ad
V
ie
nt
o
Ju
ga
r
te
n
is
D
1
S
ol
ea
d
o
A
lt
a
A
lt
a
D
éb
il
N
o
D
2
S
ol
ea
d
o
A
lt
a
A
lt
a
F
u
er
te
N
o
D
3
L
lu
vi
os
o
A
lt
a
A
lt
a
D
éb
il
Ś
ı
D
4
L
lu
vi
os
o
M
ed
ia
A
lt
a
D
éb
il
Ś
ı
D
5
L
lu
vi
os
o
F
ŕı
a
N
or
m
al
D
éb
il
Ś
ı
D
6
L
lu
vi
os
o
F
ŕı
a
N
or
m
al
F
u
er
te
N
o
D
7
L
lu
vi
os
o
F
ŕı
a
N
or
m
al
F
u
er
te
Ś
ı
D
8
S
ol
ea
d
o
M
ed
ia
A
lt
a
D
éb
il
N
o
D
9
S
ol
ea
d
o
F
ŕı
a
N
or
m
al
D
éb
il
Ś
ı
D
10
L
lu
vi
os
o
M
ed
ia
N
or
m
al
D
éb
il
Ś
ı
D
11
S
ol
ea
d
o
M
ed
ia
N
or
m
al
F
u
er
te
Ś
ı
D
12
L
lu
vi
os
o
M
ed
ia
A
lt
a
F
u
er
te
Ś
ı
D
13
L
lu
vi
os
o
A
lt
a
N
or
m
al
D
éb
il
Ś
ı
D
14
L
lu
vi
os
o
M
ed
ia
A
lt
a
F
u
er
te
N
o
E
nt
ro
p
ia
([
9+
,5
-]
)=
-(
9/
14
)l
og
2
(9
/1
4)
-(
5/
14
)l
og
2
(5
/1
4)
=
0’
94
0
R
A
20
00
–0
1
C
c
I a
A
rb
ol
es
d
e
d
ec
is
ió
n
12
.1
2
Ganancia de información
Ganancia(D,A)= Estimación de la reducción de la entroṕıa en el conjunto
de entrenamiento D si tomamos el atributo A y clasificamos según sus valores
Ganancia(S, A) ≡ Entropia(S) −
∑
v∈V alores(A)
|Sv|
|S| Entropia(Sv)
donde
• Valores(A) es el conjunto de valores del atributo A
• Sv es el subconjunto de S formado por aquellas instancias que en el
atributo A toman el valor v
RA 2000–01 CcIa Arboles de decisión 12.13
Otro ejemplo
Supongamos que S es un conjunto de entrenamiento con 14 ejemplos
• 9 ejemplos positivos y 5 negativos ([9+,5-])
• Unos de los atributos, V iento, puede tomar los valores Débil y Fuerte
• La distribución de ejemplos positivos y negativos según los valores de
V iento son
Positivos Negativos
Débil 6 2
Fuerte 3 3
RA 2000–01 CcIa Arboles de decisión 12.14

© 2016 - 2017 Docmia. Todos los derechos reservados.