PDF de programación - Técnicas de inteligencia artificial - Aprendizaje: Arboles de Decisión

Técnicas de inteligencia artificial


Aprendizaje:

Arboles de Decisión

Indice

 Árboles de decisión

 Planteamiento del problema
 Ejemplo: Concesión de créditos
 Entropía y Ganancia de Información

 Algoritmo ID3

 Algoritmo recursivo
 Aplicación al ejemplo
 Consideración de atributos numéricos
 Atributos con un gran número de valores

Árboles de decisión

 Características:

 Estructura para clasificación de

vectores de atributos.

 Establece en qué orden testar los

atributos para conseguir la
clasificación del vector de
entrada.

 Para componer dicho orden se

eligen primero aquellos atributos
que mejor ganancia de
información prometen a efectos
de descubrir la clase del vector de
entrada.

 Es interesante aprenderlos a

partir de un conjunto de vectores

Ejemplo “Concesión de créditos”

no
sí

 Aprendizaje:

 ¿Por qué atributo comenzar primero?
 Esquema voraz: Elegir uno y filtrar recursivamente.

Entropía

 Definición:

 Medida del grado de incertidumbre

asociado a una distribución de
probabilidad.

 En una distribución uniforme, todos
los valores son igualmente probables
Pi = 1/N y por tanto la entropía es
máxima, lo cual indica máxima
incertidumbre.

 Por el contrario, en una distribución

≠

pico en la que Pi = 1 y Pj=0, para
todo j i la entropía es mínima lo
cual indica mínima incertidumbre o
sea máxima información.

si

no

-0.5log2(0.5) – 0.5log2(0.5) = 1

si

-1.0log2(1.0) – 0.0log2(0.0) = 0

Entropía condicionada

 Definición:

 Entropía de la distribución de Y

condicionada a X.

 Una entropía condicionada menor

que E(Y) indica que el conocimiento
de X mejora la información que se
dispone sobre X

E(Y | X) = Σj Prob( X= vj) E(Y | X = vj)
E(Y | X = vj)

Prob(X = vj)

vj

Math
History

CS

0.5
0.25
0.25

1
0
0

E(Y|X) = 0.5*1 + 0.25*0 + 0.25*0

X

Math
History

CS
Math
Math
CS

History
Math

Y
Yes
No
Yes
No
No
Yes
No
Yes

E(Y) = 1

E(Y|X) = 0.5

Ganancia de información

 Definición:

IG(Y | X) = E(Y) – E(Y | X)

 Medida de cuanto ayuda el

conocer el valor de una
variable aleatoria X para
conocer el verdadero valor de
otra Y.

 En nuestro caso, X es un

atributo de un ejemplo dado
mientras que Y es la clase a la
que pertenece el ejemplo.

 Una alta ganancia implica que
el atributo X permite reducir
la incertidumbre de la
clasificación del ejemplo de
entrada.

X

Math
History

CS
Math
Math
CS

History
Math

E(Y) = 1

Y
Yes
No
Yes
No
No
Yes
No
Yes

E(Y|X) = 0.5
IG(Y | X) = 1 – 0.5 = 0.5

Algoritmo recursivo

Aplicación al ejemplo

 Entropía inicial:
 Aplicando la ecuación de

entropía a los datos de
entrada del ejemplo
tenemos:
E(S)= -0.4log2(0.4)-
0.6log2(0.6)= 0.971

 Para cada atributo

(Antigüedad, Moroso,
Ingresos, Fijo), calculamos la
ganancia de información que
obtenemos al seleccionar
cada uno de ellos

Prob(S<1)=0.3,Prob(S1-5)=0.4,Prob(S>5)=0.3
E(S<1) = -2/3log2(2/3)–1/3log2(1/3)= 0.9183
E(S1-5)= -1/4log2(1/4)-3/4log2(3/4)= 0.811
E(S>5) = -1/3log2(1/3)-2/3log2(2/3)= 0.9183

E(S<1)*0.3 = 0.2755
E(S1-5)*0.4 = 0.3244
E(S>5)*0.3 = 0.2755
H(Conceder | Antigüedad) =
0.2755 + 0.3244 + 0.2755 = 0.8754
Ganancia = 0.971 – 0.8754 = 0.09

Aplicación al ejemplo

Extensiones del algoritmo

 Extensiones:

 Atributos numéricos: ID3 sólo trabaja con atributos discretos. Si se

usan atributos continuos hay que descomponerlos en rangos. Para ello
se ordenan los ejemplos según el valor y se toman como puntos límite los
puntos medios de aquellos en que se cambie de clase.

 Atributos con gran número de valores. Se forman grupos pequeños de

825 950 1150

ejemplos que pueden ser homogéneos por casualidad. Debe introducirse
un elemento corrector que penalice atributos con un elevado número de
valores (ganancia normalizada):

 Sobre-entrenamiento. Comprobación de capacidad de generalización.

Bibliografía

 Escolano et al. Inteligencia Artificial. Thomson-

Paraninfo 2003. Capítulo 4.

 Mitchel, Machine Learning. McGraw Hill,

Computer Science Series. 1997

 Cover, Thomas, Information Theory. Wiley &

Sons, New York 1991