induccion1

Vista previa del material en texto

Jesús García Herrero 
TÉCNICAS DE INDUCCIÓN-I 
 
En esta clase se presentan los principios de los algoritmos básicos de inducción de modelos 
lógicos a partir de datos para aprendizaje de modelos predictivos. Se revisan los algoritmos 
más importantes, comenzando por el ID3, y la medida de la entropía de la información en la 
que se sustenta para construir árboles de decisión 
El planteamiento de este tipo de algoritmos es heurístico, no es posible evaluar todas las 
posibles configuraciones porque nos encontraríamos con dificultades de escalabilidad al 
número de datos y dimensiones de estos datos. Por tanto, es una búsqueda heurística basada 
en esta medida de la información que permite obtener buenos resultados y escalabilidad a 
conjuntos de datos grandes. 
El algoritmo se ilustra en ejemplos sencillos, presentando las características y limitaciones de 
esta estrategia. 
Inducción de Clasificadores 
Reglas y Árboles de Clasificación 
Jesús García Herrero 
Universidad Carlos III de Madrid 
Árboles de clasificación 
Árboles de decisión. ID3 
• Obtener reglas o relaciones que permitan 
clasificar a partir de los atributos 
• Ej. de entrada: 
Ejemplo Sitio de
acceso: A1
1ª cantidad
gastada: A2
Vivienda:
A3
Última
compra: A4
Clase
1 1 0 2 Libro Bueno
2 1 0 1 Disco Malo
3 1 2 0 Libro Bueno
4 0 2 1 Libro Bueno
5 1 1 1 Libro Malo
6 2 2 1 Libro Malo
Árboles de clasificación 
Clasificación “1R” 
• Medio rudimentario de una sola regla 
• Selección de atributo de mínimo error total 
Atributo Reglas Errores Errores totales 
A1 0  Bueno 0/1 2/6 
1  Bueno (?) 2/4 
2  Malo 0/1 
A2 0  Malo (?) 1/2 2/6 
1  Malo 0/1 
2  Bueno 1/3 
A3 0  Bueno 0/1 3/6 
1  Bueno (?) 3/4 
2  Bueno 0/1 
A4 Libro  Bueno 2/5 2/6 
Disco  Malo 0/1 
 
Árboles de clasificación 
Medida de orden. Entropía 
• Seleccionar el atributo que mejor separe (ordene) los 
ejemplos de acuerdo a las clases. “Divide y 
vencerás” 
• La entropía es una medida de como está ordenado el 
universo 
• La teoría de la información (basada en la entropía) 
calcula el número de bits (información, preguntas 
sobre atributos) que hace falta suministrar para 
conocer la clase a la que pertenece un ejemplo 
Árboles de clasificación 
Medida de la información 
• Entropía: propuesta por Shannon en su Teoría de la 
Información (1948) 
• Dado un conjunto de eventos A= {A1, A2,..., AN}, con 
probabilidades {p1, p2,..., pN}, información en un 
mensaje acerca de estos sucesos: 
– Información en el conocimiento de un suceso Ai (bits) 
 
 
– Información media de A (bits) 
 



N
1i
i2i
N
1i
ii )p(logp)A(Ip)A(I
)p(log
p
1
log)A(I i2
i
2i 






Árboles de clasificación 
Medida de la información 
• Ej.: A= {A1, A2, A3, A4}, {1/4, 1/4, 1/4, 1/4} 
 
 
 
• A= {A1, A2, A3, A4}, {1/5, 1/5, 1/5, 2/5} 
 
 
 
 
Máxima entropía con sucesos equi-probables 
bits2
4
1
log
4
1
4
1
log
4
1
4
1
log
4
1
4
1
log
4
1
)A(I
bits2
4
1
log)A(I
2222
2i
































bits92.1
5
2
log
5
2
5
1
log
5
1
5
1
log
5
1
5
1
log
5
1
)A(I
;bits32.1
5
2
log)A(I
;bits32.2
5
1
log)A(I)A(I)A(I
2222
24
2321







































Árboles de clasificación 
Aplicación a la clasificación 
Medida de lo que se gana tras usar un atributo Ai 
– Información antes de utilizar atributos: 
 clases: {C1,…, CM}; instancias: {n1,…, nM} 
 
 
 
– Tras utilizar atributo Ai 
 
 







M
1c
c
2
c
n
n
log
n
n
I
)()(
log;)(
1
2
)(
1
ii
M
k ij
ijk
ij
ijk
ij
Anv
j
ij
ij
i
AIIAG
n
n
n
n
II
n
n
AI
i

 

Árboles de clasificación 
Ejemplo 
 
 
A3 (zona vivienda)? 
0 1 2 
ejemplo3(B) ejemplo2(M) 
ejemplo4(B) 
ejemplo5(M) 
ejemplo6(M) 
ejemplo1(B) 
Ejemplo Sitio de
acceso: A1
1ª cantidad
gastada: A2
Vivienda:
A3
Última
compra: A4
Clase
1 1 0 2 Libro Bueno
2 1 0 1 Disco Malo
3 1 2 0 Libro Bueno
4 0 2 1 Libro Bueno
5 1 1 1 Libro Malo
6 2 2 1 Libro Malo
Árboles de clasificación 
Ejemplo 
bit1
6
3
log
6
3
6
3
log
6
3
I 22 












0
1
0
log
1
0
1
1
log
1
1
n
n
log
n
n
I
bits81.0
4
3
log
4
3
4
1
log
4
1
n
n
log
n
n
I
0
1
0
log
1
0
1
1
log
1
1
n
n
log
n
n
I
22
2
1k 32
k32
2
12
k12
10
22
2
1k 31
k31
2
11
k11
11
22
2
1k 30
k30
2
10
k10
10









32313032
32
31
31
30
30
3
1j
j1
j1
3 I
6
1
I
6
4
I
6
1
I
n
n
I
n
n
I
n
n
I
n
n
)A(I 

bits46.0)A(II)A(G;54.0)A(I 333 
Árboles de clasificación 
Algoritmo ID3 (Quinlan 93) 
1. Seleccionar el atributo Ai que maximice la ganancia G(Ai) 
2. Crear un nodo para ese atributo con tantos sucesores como 
valores tenga 
3. Introducir los ejemplos en los sucesores según el valor que 
tenga el atributo Ai 
4. Por cada sucesor: 
Si sólo hay ejemplos de una clase, Ck 
Entonces etiquetarlo con Ck 
Si no, llamar al ID3 con una tabla formada por los ejemplos de 
ese nodo, eliminando la columna del atributo Ai 
 
 
Árboles de clasificación 
Ejemplo 
 
 
Ejemplo Sitio de
acceso: A1
1ª cantidad
gastada: A2
Vivienda:
A3
Última
compra: A4
Clase
1 1 0 2 Libro Bueno
2 1 0 1 Disco Malo
3 1 2 0 Libro Bueno
4 0 2 1 Libro Bueno
5 1 1 1 Libro Malo
6 2 2 1 Libro Malo
19,1)(;81.0
6
5
6
1
)(
46,1)(;54.0
6
1
6
4
6
1
)(
21,1)(;79.0
6
3
6
1
6
2
)(
34,1)(;66.0
6
1
6
4
6
1
)(
44144
33231303
22221202
11211101




AGIIAI
AGIIIAI
AGIIIAI
AGIIIAI
LibroDisco
Árboles de clasificación 
Ejemplo 
 
 
A3 (zona vivienda)? 
B B 
0 1 2 
ejemplo3(B) ejemplo2(M) 
ejemplo4(B) 
ejemplo5(M) 
ejemplo6(M) 
ejemplo1(B) 
Ejemplo Sitio de
acceso: A1
1ª cantidad
gastada: A2
Vivienda:
A3
Última
compra: A4
Clase
1 1 0 2 Libro Bueno
2 1 0 1 Disco Malo
3 1 2 0 Libro Bueno
4 0 2 1 Libro Bueno
5 1 1 1 Libro Malo
6 2 2 1 Libro Malo
Árboles de clasificación 
Ejemplo 
 
 
Ejemplo Sitio de
acceso: A1
1ª cantidad
gastada: A2
Última
compra: A4
Clase
2 1 0 Disco Malo
4 0 2 Libro Bueno
5 1 1 Libro Malo
6 2 2 Libro Malo
77,1)(;23.0
4
3
4
1
)(
5,1)(;5.0
4
2
4
1
4
1
)(
2)(;0
4
1
4
2
4
1
)(
4444
22221202
11211101



AGIIAI
AGIIIAI
AGIIIAI
LibroDisco
Árboles de clasificación 
Ejemplo 
 
 
A3 (zona vivienda)? 
B B 
0 1 2 
ejemplo3(B) ejemplo1(B) 
A1 (sitio de acceso)? 
M B 
0 1 2 
ejemplo4(B) ejemplo6(M) ejemplo2(M) 
ejemplo5(M) 
M 
Árboles de clasificación 
Estrategia del ID3 
 
 
M 
M 
B M 
Zona vivienda? 
S
it
io
 d
e 
ac
ce
so
? 
B 
B 
0 1 2 
0 
1 
2 
Árboles de clasificación 
Estrategia del ID3 
 
 
M 
M 
B M 
Zona vivienda? 
S
it
io
 d
e 
ac
ce
so
? 
B 
B 
0 1 2 
0 
1 
2 
Árboles de clasificación 
Estrategia del ID3 
 
 
M 
M 
B M 
Zona vivienda? 
S
it
io
 d
e 
ac
ce
so
? 
B 
B 
0 1 2 
0 
1 
2 
Árboles de clasificación 
Ejemplo con frontera diagonal 
 
 
A1? 
A
2
? 
1 2 3 
5 
1 
2 
3 
4 
4 
Árboles de clasificación 
Ejemplo con frontera diagonal 
 
 
A1? 
A
2
? 
1 2 3 
5 
1 
2 
3 
4 
4 
Árboles de clasificación 
Ejemplo con frontera diagonal 
 
 
A1? 
A
2
? 
1 2 3 
5 
1 
2 
3 
4 
4 
Árboles de clasificación 
Ejemplo con frontera diagonal 
 
 
A1? 
A
2
? 
1 2 3 
5 
1 
2 
3 
4 
4 
Árboles de clasificación 
Ejemplo con frontera diagonal 
 
 
A1? 
A
2
? 
1 2 3 
5 
1 
2 
3 
4 
4 
Árboles de clasificación 
A2 = 1: 0 
A2 = 2 
| A1 = 1: 1 
| A1 = 2: 0 
| A1 = 3: 0 
| A1 = 4: 0 
A2 = 3 
| A1 = 1: 1 
| A1 = 2: 1 
| A1 = 3: 0 
| A1 = 4: 0 
A2 = 4 
| A1 = 1: 1 
| A1 = 2: 1 
| A1 = 3: 1 
| A1 = 4: 0 
A2 = 5: 1 
 
Salida ID3 
Árboles de clasificación 
Transformación de atributos 
 
 
A1-A2?-4 -3 -2 2 0 1 3 -1 
Árboles de clasificación 
Dif = -4: 1 
Dif = -3: 1 
Dif = -2: 1 
Dif = -1: 1 
Dif = 0: 0 
Dif = 1: 0 
Dif = 2: 0 
Dif = 3: 0 
Salida ID3