Tema 12: Arboles de decisión

Razonamiento Automatico Curso 2000–2001

Tema 12: Arboles de decision

Jose A. Alonso Jimenez

Miguel A. Gutierrez Naranjo

Dpto. de Ciencias de la Computacion e Inteligencia Artificial

Universidad de Sevilla

RA 2000–01 CcIa Arboles de decision 12.1

¿Que es el Aprendizaje mediante arboles de decision?

• El aprendizaje mediante arboles de decision es un metodo de aproxi-macion de una funcion objetivo de valores discretos en el cual la funcionobjetivo es representada mediante un arbol de decision.

• Los arboles aprendidos tambien pueden representarse como un conjuntode reglas Si–entonces


Un ejemplo

Cielo Temperatura Humedad Viento Agua Forecast Hacer DeporteSoleado Templada Alta Debil Frıa Sigue igual NoSoleado Templada Normal Debil Frıa Sigue igual SıNublado Templada Normal Debil Frıa Sigue igual SıLluvioso Templada Normal Fuerte Templada Cambio NoLluvioso Templada Normal Debil Frıa Cambio Sı

• ¿Cuando hacemos deporte?

• ¿Podemos definir el concepto Hacer Deporte?


Un ejemplo de arbol de decision

Cielo

Nublado

Humedad

NormalAlta

No Si

Viento

Fuerte Debil

No Si

Si

LluviosoSoleado


El problema de la representacion

El arbol anterior corresponde a la hipotesis:

(Cielo = Soleado ∧Humedad = Normal)∨ (Cielo = Nublado)∨ (Cielo = Lluvioso ∧ V iento = Debil)

Representacion:

• Cada nodo que no sea una hoja representa un atributo.

• Las aristas que partan del nodo etiquetado con el atributo A estan etiquetadas con cadauno de los posibles valores del atributo A.

• Cada hoja corresponde a un valor de la clasificacion


Cuestiones sobre arboles de decision

x ¿Cuando usar arboles de decision?

u Podemos describir los ejemplos en terminos de pares atributo–valor

u La funcion 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 Diagnostico medico

u Analisis de riesgo en la concesion de creditos

u Elaboracion de horarios


Cuestiones sobre arboles de decision

x ¿Cual es el arbol de decision correcto?

u Navaja de Occam

u El mundo es inherentemente simple

u El arbol de decision mas pequeno consistente con la muestra es el que tiene mas

probabilidades de identificar objetos desconocidos de manera correcta

u Menor profundidad

u Menor numero de nodos

x ¿Como se puede construir el arbol de decision mas pequeno?

u Busqueda en escalada


Algoritmo basico (I)

• Arbol inicial: Arbol con un unico nodo, sin etiquetar, al que asignamoscomo 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 clasificacion,etiquetamos N con esa clasificacion.

∗ En otro caso ...


Algoritmo basico (II)

· Etiquetamos N con el mejor atributo A segun el conjunto deejemplos asignado.

· Para cada valor de A creamos una nueva arista descendente en elnodo N , y al final de cada una de esas nuevas aristas creamos unnuevo nodo sin etiquetar, N1, . . . , Nk.

· Separamos los ejemplos asignados al nodo N segun el valor quetomen para el atributo A y creamos nuevos conjuntos de ejemplospara N1, . . . , Nk.

•Hasta que todos los nodos estes etiquetados

¿Que atributo clasifica mejor?


Entr

opıa

(Definic

ion)

•Definic

ion:

Sea

P={p

1,p

2,.

..,p

n}u

na

dis

trib

uci

onde

pro

bab

ilidad

.Lla

mam

osentr

opıa

b-ar

iade

ladis

-tr

ibuci

onP

a

Hb(

p 1,p

2,.

..,p

n)

=−

i=n

∑ i=1

p ilo

g bp i

•La

funci

onde

entr

opıa

H2(p

,1−

p)=

plo

g 21 p

+(1−

p)lo

g 21

1−

p

esm

uy

com

un

ynos

refe

rim

osa

ella

com

ola

funci

onde

entr

opıa

yse

den

ota

por

H(p

).Su

grafi

caes

Entropy(S)

1.0

0.5 0.

00.

51.

0p +

RA

2000

–01

CcI a

Arb

oles

de

dec

isio

n12

.10

Entropıa

•D es un conjunto de entrenamiento

• P y N son, respectivamente, la cantidad de ejemplos positivos y negativosen D

• T es el numero total de ejemplos de D

• La entropıa de esta distribucion es:

u Formula: I(P, N) = H2(P/T, N/T ) =

{0, si N ∗ P = 0;

−PT

log2PT

− NT

log2NT

, si N ∗ P 6= 0.

u Ejemplo: I(9, 9) = − 918

log2918

− 918

log2918

= 1

(El termino entropıa fue usado por primera vez por Clausius en 1864 e introducido en la teorıa de lainformacion por Shannon en 1948)


Otr

oeje

mplo

Dıa

Cie

loTem

per

atura

Hum

edad

Vie

nto

Juga

rte

nis

D1

Sol

eado

Alt

aA

lta

Deb

ilN

o

D2

Sol

eado

Alt

aA

lta

Fuer

teN

o

D3

Llu

vios

oA

lta

Alt

aD

ebil

Sı

D4

Llu

vios

oM

edia

Alt

aD

ebil

Sı

D5

Llu

vios

oFrı

aN

orm

alD

ebil

Sı

D6

Llu

vios

oFrı

aN

orm

alFuer

teN

o

D7

Llu

vios

oFrı

aN

orm

alFuer

teSı

D8

Sol

eado

Med

iaA

lta

Deb

ilN

o

D9

Sol

eado

Frı

aN

orm

alD

ebil

Sı

D10

Llu

vios

oM

edia

Nor

mal

Deb

ilSı

D11

Sol

eado

Med

iaN

orm

alFuer

teSı

D12

Llu

vios

oM

edia

Alt

aFuer

teSı

D13

Llu

vios

oA

lta

Nor

mal

Deb

ilSı

D14

Llu

vios

oM

edia

Alt

aFuer

teN

o

Ent

ropia

([9+

,5-])=

-(9/

14)l

og2(9

/14)

-(5/

14)l

og2(5

/14)

=0’

940

RA

2000

–01

CcI a

Arb

oles

de

dec

isio

n12

.12

Ganancia de informacion

Ganancia(D,A)= Estimacion de la reduccion de la entropıa en el conjuntode entrenamiento D si tomamos el atributo A y clasificamos segun 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 elatributo A toman el valor v


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 Debil y Fuerte

• La distribucion de ejemplos positivos y negativos segun los valores deV iento son

Positivos NegativosDebil 6 2Fuerte 3 3


Otro ejemplo

La Ganancia de informacion que obtenemos si clasificamos los 14 ejemplossegun el atributo V iento es:

Ganancia(S,A)

= Entropia(S) − ∑v∈V alores(A)

|Sv||S|Entropia(Sv)

= Entropia(S) − 814Entropia(SDebil) − 6

14Entropia(SFuerte)

= 0′940 − 8140

′811 − 6141

′00

= 0.048


Seleccion del mejor atributo (I)

Which attribute is the best classifier?

High Normal

Humidity

[3+,4-] [6+,1-]

Wind

Weak Strong

[6+,2-] [3+,3-]

= .940 - (7/14).985 - (7/14).592 = .151

= .940 - (8/14).811 - (6/14)1.0 = .048

Gain (S, Humidity ) Gain (S, )Wind

=0.940E =0.940E

=0.811E=0.592E=0.985E =1.00E

[9+,5-]S:[9+,5-]S:

Humedad proporciona mayor ganacia de informacion que Viento


Sele

ccio

ndelm

ejo

ratr

ibuto

(II)

Con

sider

emos

elej

emplo

ante

rior

con

14ej

emplo

s

Gan

anci

a(S,C

ielo

)=

0’24

6G

anan

cia(

S,H

um

edad

)=

0’15

1G

anan

cia(

S,V

ient

o)=

0’04

8G

anan

cia(

S,T

emper

atura

)=

0’02

9

•Ela

trib

uto

con

elqu

ete

nem

osm

ayor

Gan

anci

ade

info

rmac

ion

esCie

lo

•Lueg

o,se

lecc

ionam

osCie

loco

mo

atri

buto

de

dec

isio

npar

ael

nod

ora

ız

•Par

aca

da

uno

de

sus

pos

ible

sva

lore

s(S

olea

do,

Llu

vios

o,Llu

vios

o)cr

eam

osuna

ram

a

•Cla

sific

amos

los

ejem

plo

sse

gun

los

valo

res

de

Cie

lo

•En

las

ram

asen

las

que

los

ejem

plo

sno

este

nper

fect

amen

tecl

asifi

cados

,it

eram

osel

pro

ceso

RA

2000

–01

CcI a

Arb

oles

de

dec

isio

n12

.17

Sele

ccio

ndelm

ejo

ratr

ibuto

(III

)

Tra

sel

pri

mer

pas

o,ob

tenem

osun

arbol

de

dec

isio

npa

rcia

l

Out

look

Sunn

yO

verc

ast

Rai

n

[9+

,5−

]

{D1,

D2,

D8,

D9,

D11

}{D

3,D

7,D

12,D

13}

{D4,

D5,

D6,

D10

,D14

}

[2+

,3−

][4

+,0

−]

[3+

,2−

]

Yes

{D1,

D2,

...,

D14

}

??

Whi

ch a

ttri

bute

sho

uld

be te

sted

her

e?

S sun

ny=

{D

1,D

2,D

8,D

9,D

11}

Gai

n (S

sunn

y, H

umid

ity)

sunn

yG

ain

(S

, Tem

pera

ture

)=

.97

0 −

(2/

5) 0

.0 −

(2/

5) 1

.0 −

(1/

5) 0

.0 =

.57

0

Gai

n (S

sunn

y, W

ind)

= .

970

− (

2/5)

1.0

− (

3/5)

.918

= .

019

= .

970

− (

3/5)

0.0

− (

2/5)

0.0

= .

970

RA

2000

–01

CcI a

Arb

oles

de

dec

isio

n12

.18

Espacio de hipotesis

• El aprendizaje mediante arboles de decision es un metodo de aproxi-macion de una funcion objetivo de valores discretos en el cual la funcionobjetivo es representada mediante un arbol de decision.

• Podemos pensar este proceso como un proceso de busqueda de un arbolque clasifique correctamente nuestros ejemplos.

• Espacio de hipotesis: Todos los posibles arboles de decision.

•Metodo: Escalada (hill-climbing), empezando por el arbol vacıo.

• Funcion de evaluacion que guıa la busqueda: Ganancia de informacion


Comentarios (I)

• El espacio de hipotesis es completo: Cualquier funcion finita que tomevalores discretos puede ser representada como un arbol de decision.

• En cada eleccion consideramos una unica hipotesis, a diferencia del al-goritmo de Eliminacion de Candidatos, que considerabamos si-multaneamente todas las hipotesis consistentes con los ejemplos.


Comentarios (II)

• No permite retroceso, por lo que podemos obtener optimos locales enlugar de optimos globales

• Considera en cada paso gran cantidad de ejemplos, en contraste con otrosmetodos, por ejemplo Eliminacion de candidatos que consideranlos ejemplos uno a uno. Esto supone mayor robustez frente al ruido.


Sesgo de restriccion y sesgo preferencial (I)

Consideremos la busqueda en el espacio de hipotesis en el algoritmo dearboles de decision y el algoritmo de Eliminacion de Candidatos

• ID3 busca de manera incompleta en un espacio de busqueda completo.El sesgo es consecuencia unicamente del metodo de busqueda. El espaciode hipotesis no introduce ningun sesgo. Llamamos a este tipo de sesgopreferencial, ya que se debe a la preferencia de unas hipotesis sobre otras.


Sesgo de restriccion y sesgo preferencial (II)

• El algoritmo de Eliminacion de Candidatos busca en un espaciode busqueda incompleto de manera completa (i.e. devuelve todas lashipotesis del espacio consistentes con el conjunto de entrenamiento). Eneste caso el sesgo depende unicamente de la potencia expresiva en la rep-resentacion de las hipotesis. Llamamos a este sesgo sesgo de restricciono sesgo del lenguaje.


Sistemas TDIDP

x Los sistemas basados en arboles de decision forman una familia llamadaTDIDT (Top–Down Induction of Decision Tree)

x Representantes de TDIDT:

u ID3 [Quinlan, 1986]

u C4.5 [Quinlan, 93]

x Quinlan, J. R. C4.5: Programs for Machine Learning (Morgan Kauf-mann, 1993)


Otr

os

tem

as

de

est

udio

(I)

•Sobre

aju

ste

(overfi

ttin

g)

–D

efinic

ion:

Dad

oun

espac

iode

hip

otes

isH

,una

hip

otes

ish∈

Hse

dic

equ

eso

brea

-ju

sta

un

conju

nto

de

entr

enam

ient

oC

siex

is-

teal

guna

hip

otes

isal

tern

ativ

ah′∈

Hta

lqu

eh

clas

ifica

mej

orqu

eh′ l

osel

emen

tos

del

conju

nto

de

entr

enam

ient

o,per

oh′ c

lasi

fica

mej

orqu

eh

elco

nju

nto

com

ple

tode

pos

ible

sin

stan

cias

.

–E

xces

ode

ruid

o

–C

onju

nto

de

entr

enam

ient

odem

asia

do

peq

uen

o

•Poda

(pru

nnin

g)

–D

efinic

ion:

Pod

arun

nod

ode

un

arbol

de

dec

isio

nco

nsi

ste

enel

imin

arun

subar

bol

ani-

dad

oen

ese

nod

otr

ansf

orm

andol

oen

una

hoja

yas

ignan

dol

ela

clas

ifica

cion

mas

com

un

de

los

ejem

plo

sde

entr

enam

ient

oco

nsi

der

a-dos

enes

enod

o

RA

2000

–01

CcI a

Arb

oles

de

dec

isio

n12

.25

Otr

os

tem

as

de

est

udio

(II)

•Atr

ibuto

sde

valo

res

conti

nuos

•Medid

as

alt

ern

ati

vas

en

lase

lecc

ion

de

atr

ibuto

s

•Atr

ibuto

sco

nvalo

res

perd

idos

•Atr

ibuto

sco

npeso

sdifere

nte

s

RA

2000

–01

CcI a

Arb

oles

de

dec

isio

n12

.26

Ejemplo de datosEjemplo Accion Autor Tema Longitud Sitio

e1 saltar conocido nuevo largo casae2 leer desconocido nuevo corto trabajoe3 saltar desconocido viejo largo trabajoe4 saltar conocido viejo largo casae5 leer conocido nuevo corto casae6 saltar conocido viejo largo trabajoe7 saltar desconocido viejo corto trabajoe8 leer desconocido nuevo corto trabajoe9 saltar conocido viejo largo casae10 saltar conocido nuevo largo trabajoe11 saltar desconocido viejo corto casae12 saltar conocido nuevo largo trabajoe13 leer conocido viejo corto casae14 leer conocido nuevo corto trabajoe15 leer conocido nuevo corto casae16 leer conocido viejo corto trabajoe17 leer conocido nuevo corto casae18 leer desconocido nuevo corto trabajo


Arbol de decision

trama

autor

longitud

cortolargo

saltar

nuevo viejo

leer

conocido desconocido

leer saltar


Busqueda del arbol de decision

x Informacion tras la division por un Atributo:I = N1∗I1+N2∗I2

N1+N2, donde

• N1 = numero de ejemplos en la clase 1

• N2 = numero de ejemplos en la clase 2

• I1 = cantidad de informacion en los ejemplos de la clase 1

• I2 = cantidad de informacion en los ejemplos de la clase 2


Algoritmo ID3

x Sesion

?- [’aprende_ad.pl’,’aprende_ad_e1.pl’].Yes

?- aprende_ad(accion,[e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12,e13,e14,e15,e16,e17,e18],

[autor,tema,longitud,sitio],AD).

AD = si(longitud=largo, saltar,si(tema=nuevo, leer,

si(autor=desconocido, saltar,leer)))

Yes


Algoritmo ID3

x Representacion del problema aprende ad e1.pl

u val(Objeto,Atributo,Valor) se verifica si el valor del Atributo del Objeto es Valor

val(e1,accion,saltar).val(e1,autor,conocido).val(e1,tema,nuevo).val(e1,longitud,largo).val(e1,sitio,casa ).

..........................

val(e18,accion,leer).val(e18,autor,desconocido).val(e18,tema,nuevo).val(e18,longitud,corto).val(e18,sitio,trabajo).


Algoritmo ID3

x Algoritmo de aprendizaje de arboles de decision

u aprende ad(+Objetivo,+Ejemplos,+Atributos,-AD) se verifica si AD es el arbol de de-

cision inducido para el Objetivo a partir de la lista de Ejemplos y Atributos

aprende_ad(Objetivo, Ejemplos, _ , Val) :-coinciden_todos_ejemplos(Objetivo, Ejemplos, Val).

aprende_ad(Objetivo, Ejemplos, Atributos, si(Atr=ValPos,APos,ANeg)) :-not(coinciden_todos_ejemplos(Objetivo, Ejemplos, _)),selecciona_division(Objetivo, Ejemplos, Atributos, Atr, Resto_Atr),divide(Ejemplos, Atr, ValPos, Positivos, Negativos),aprende_ad(Objetivo, Positivos, Resto_Atr, APos),aprende_ad(Objetivo, Negativos, Resto_Atr, ANeg).


Algoritmo ID3

x Seleccion del mejor atributo para dividir

u selecciona division(+Objetivo,+Ejemplos,+Atributos, -Atrib,-Restantes atrib) se

verifica si Atributo es el mejor elemento de la lista de Atributos para determinar el

Objetivo a partir de los Ejemplos (es decir, la informacion resultante del Objetivo

en los Ejemplos usando como division el Atributo es mınima), y Restantes atributos

es la lista de los restantes Atributos. Falla si para ningun atributo se gana en

informacion.

selecciona_division(Objetivo, Ejemplos, [A|R], Atributo, Resto_Atr) :-informacion_division(Objetivo,Ejemplos,A,I),selecciona_max_ganancia_informacion(Objetivo,Ejemplos,R,A,I,

Atributo,[],Resto_Atr).


Algoritmo ID3

u informacion(+Objetivo,+Ejemplos,-I) se verifica si I es la cantidad de informacion

en los Ejemplos respecto del Objetivo; es decir,

I =

{0, si N ∗ P = 0;

−PT

log2PT

− NT

log2NT

, si N ∗ P 6= 0.

informacion(Objetivo,Ejemplos,I) :-cuenta(Objetivo,_,Ejemplos,NP,NN),( (NP=0 ; NN=0) -> I=0

;NT is NP + NN,I is - NP/NT * log2(NP/NT) - NN/NT * log2(NN/NT)).


Algoritmo ID3

u selecciona max ganancia informacion(+Objetivo, +Ejemplos, +Atributos,

+Mejor atributo actual, +Mejor info actual, -Atributo, +Atributos analizados,

-Resto atributos) se verifica si Atributo es el elemento de Atributos tal la infor-

macion resultante del Objetivo en los Ejemplos usando como division el Atributo es

mınima

selecciona_max_ganancia_informacion(_,_,[],MejorA,_,MejorA, A_analizados, A_analizados).

selecciona_max_ganancia_informacion(Objetivo, Ejs, [A|R], MejorA, MejorI,Atributo, A_analizados, Resto_Atr) :-

informacion_division(Objetivo,Ejs,A,Informacion),( Informacion > MejorI

-> selecciona_max_ganancia_informacion(Objetivo,Ejs,R,MejorA,MejorI,Atributo,[A|A_analizados],Resto_Atr)

; selecciona_max_ganancia_informacion(Objetivo,Ejs,R,A,Informacion,Atributo,[MejorA|A_analizados],Resto_Atr)

).


Bibliografıa

•Mitchell, T. M. Machine Learning

– Texto: McGraw–Hill, 1997. Capıtulo III.

– Web:

http://www.cs.cmu.edu/~tom/mlbook.html

• Poole D., et. al Computational Intelligence. A Logical ApproachOxford University Press, 1998.


Documents

Tema 12: Arboles de decisión