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

Imágen de pdf Técnicas de inteligencia artificial - Aprendizaje: Arboles de Decisión

Técnicas de inteligencia artificial - Aprendizaje: Arboles de Decisióngráfica de visualizaciones

Publicado el 11 de Julio del 2017
569 visualizaciones desde el 11 de Julio del 2017
387,8 KB
12 paginas
Creado hace 10a (19/04/2011)
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


 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
  • Links de descarga
http://lwp-l.com/pdf5298

Comentarios de: Técnicas de inteligencia artificial - Aprendizaje: Arboles de Decisión (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad