PDF de programación - Métodos de aprendizaje inductivo - Aprendizaje Automático y Data Mining

Aprendizaje Automático y Data Mining

Bloque III
MÉTODOS DE
APRENDIZAJE INDUCTIVO

1

Índice

n Lazy
n Eager

n Clasificación de métodos:

n Árboles de decisión.
n Listas de reglas.
n Aprendizaje Bayesiano.
n Redes neuronales

2

CLASIFICACIÓN DE MÉTODOS

3

Clasificación de métodos (I)

n Los métodos de aprendizaje inductivo se

clasifican en dos grupos:
n Lazy: no construyen un modelo; todo el

‘trabajo’ se pospone hasta el momento de
clasificar una nueva instancia (todo el
procesamiento se hace on-line).
Ejemplo: vecino más cercano.

n Eager: construyen un modelo; parte del

‘trabajo’ se realiza off-line, nada más recopilar
todos los ejemplos de entrenamiento.
Ejemplos: árboles de decisión, redes neuronales, etc.

4

Clasificación de métodos (II)

n Algoritmos que estudiaremos:

LAZY

Vecino más

cercano

EAGER

Árboles de

decisión

Listas de reglas

Métodos

bayesianos

Redes neuronales

5

VECINO MÁS CERCANO

6

Vecino más cercano (I)

n Método lazy: no se crea modelo.

n Entrenamiento (off-line): simplemente

se guardan todas las instancias.

n Clasificación (on-line): una nueva

instancia se clasifica en función de la
clase de las instancias almacenadas
más cercanas.
• La distancia entre dos instancias (entre dos

ejemplos) se calcula a partir del valor de
sus atributos.

7

Vecino más cercano (II)

n Método básico: sólo un vecino (1-NN).

temp.

Instancias de entrenamiento:

Clase 1
Clase 2
Clase 3

Nueva instancia:

(debe ser clasificada)

vibración

8

Vecino más cercano (III)

n Class assigned = class of closest element.

temp.

Instancias de entrenamiento:

Clase 1
Clase 2
Clase 3

Nueva instancia:

(debe ser clasificada)

vibración

9

Vecino más cercano (IV)

n Más de un vecino (k-NN o k vecinos).

temp.

Instancias de entrenamiento:

Clase 1
Clase 2
Clase 3

Nueva instancia:

(debe ser clasificada)

vibración

10

Vecino más cercano (V)

n Clase elegida = clase mayoritaria en las k

instancias más cercanas (ejemplo con k = 4).

temp.

Instancias de entrenamiento:

Clase 1
Clase 2
Clase 3

Nueva instancia:

(debe ser clasificada)

vibración

11

Vecino más cercano (VI)

n Procedimiento para la clasificación de una

nueva instancia:

1. Se mide la distancia entre la instancia a clasificar y
todas las instancias de entrenamiento almacenadas.
•
Las distancias se miden en el espacio de los atributos.
• Tantas dimensiones como número de atributos.
• Distancia euclídea. Ejemplo con n atributos:
(

)2

+

=

+

+

)

2

)

2

(

(

(
x,xd

1

2

)

x
11

x

21

x
12

x

22

...

x
1

n

x

2

n

2. Se eligen las k instancias más próximas.
3. Se asigna como clase la clase mayoritaria entre las k

instancias.

n Gran coste computacional on-line.

12

-
-
-
Vecino más cercano (VII)

n Es necesaria la normalización de atributos.
n Ejemplo: préstamo bancario.

n Datos de entrenamiento:

Nº ejemplo

1
2
3
4

Salario
100.000
90.000
15.000
20.000

Edad

Devuelve préstamo

55
30
60
25

SI
NO
SI
NO

Aparentemente, sólo importa la edad.
Buscamos la clase de una nueva instancia (nuevo cliente del banco):

Salario = 25.000
Edad = 65

… de acuerdo con la edad, la clase debe ser SI (devuelve préstamo)

13

Vecino más cercano (VIII)

n
n
n

Una representación gráfica confirma que sólo importa la edad.
El vecino más cercano es el ejemplo 3 (1-NN).
La clase de la nueva instancia debe ser SI (devuelve prestamo):

salario

100.000

(2)

80.000

60.000

40.000

20.000

(4)

(1)

(3)

20

30

40

50

60

70

edad

Instancias de entrenamiento:

NO (no paga)
SI (paga)

Nueva instancia:

(debe ser clasificada)

14

Vecino más cercano (IX)

n

Si realizamos el cálculo numérico:

=
=
=
=

d

1

d

d

d

2

3

4

75000

65000

10000
2

5000

2

2

+
+
+
+

2

2

10

2

35
2

10
2

40

=
=
=
=

75000

,
00067

65000

,
00942

10000

,
00125

5000

,
1599

n … el ejemplo más cercano es el #4!
n … la clase debería ser NO (no devuelve el préstamo)!

15

Vecino más cercano (X)

n

n

¿Dónde se encuentra el problema?
n

LOS ATRIBUTOS HAN DE SER NORMALIZADOS.
En otro caso, los atributos con mayor valor absoluto
siempre prevalecen sobre los demás.
Por eso parece que sólo importa el salario.

n

n
Posibles normalizaciones:
n

Todos los atributos normalizados a media cero y varianza
unidad.

x
i

=

xˆ

i

m-
s

i

i

n

Todos los atributos normalizados al rango 0 - 1.

=

xˆ
i

x
i
max
i

min
i
min
i

16

-
-
Vecino más cercano. Resumen (I)

1. Capacidad de representación:

n Muy elevada, fronteras de decisión complejas (superficies

de Voronoi).

temp.

Instancias de entrenamiento:

Clase 1
Clase 2
Clase 3
Clase 4

vibración

17

Vecino más cercano. Resumen (II)

2.

3.

4.

5.

Legibilidad:
n Ninguna, no se crea modelo.
Tiempo de cómputo on-line:
n

Lento, es necesario calcular distancias a todos los ejemplos
de entrenamiento.

Tiempo de cómputo off-line:
n

Rápido, sólo el tiempo necesario para almacenar todas las
instancias de entrenamiento.

Parámetros a ajustar:
n

Sólo el número de vecinos (k-NN).

6. Robustez ante instancias de entrenamiento ruidosas:
1-NN no es robusto; k-NN es más robusto a medida que
aumenta k.

n

7. Sobreajuste (overfitting):

n

Es difícil que ocurra; más difícil cuanto mayor es k.

18

ÁRBOLES DE DECISIÓN

19

Árboles de decisión (I)

Funcionamiento básico ya estudiado.

n
n Método Eager: crea un modelo.
n

Estudiaremos dos algoritmos:
ID3 para atributos discretos.
n
C4.5 para atributos continuos y discretos.

n
Creación del árbol: selección de atributos comenzando
en el nodo raíz.
El criterio para elegir los atributos en ID3 y C4.5 es el
‘incremento de información’ o ‘information gain’.
Information gain = reducción de entropía como
consecuencia de realizar una división de los datos.

n

n

n

20

Árboles de decisión (II)

n

Algoritmo ID3.
n

Entropía de un nodo del árbol:

-=

E

k

=
1

i

r
i

log

2

( )
r
i

n

n

ri = porcentaje de instancias pertenecientes a la clase i.
k = número de clases.

•
•
Entropía = falta de homogeneidad.
Entropía mínima: todas las instancias pertenecen a la
misma clase:
E
log

-=

( ) 0
=
1

2

1

n

Entropía máxima: todas las clases representadas por igual.

-=

E

k

1
k

log

2

1
k

=

log

2

( )
k

=
=
k
2

1

21

ł


Ł



Árboles de decisión (III)

n

Algoritmo ID3.
n Ganancia de información como resultado de dividir un nodo:

=

IG

E

0

NP

=
1

i

n
i E
n
0

i

•
•

•
•
•

E0 = entropía del nodo antes de la división.
Ei = entropía de cada partición (fórmula general para dos o más
particiones).
NP = número de particiones.
ni = número de instancias pertenecientes a la partición i.
n0 = número total de instancias del nodo.

n Hay ganancia de información cuando la división envía

n

instancias con clases distintas a los distintos nodos.
El atributo que permite obtener la mayor ganancia de
información es el seleccionado para dividir el nodo.
• Criterio similar al utilizado para construir el árbol de decisión a

mano en apartados anteriores.

22



ł



Ł


-
Árboles de decisión (IV)

n

Algoritmo C4.5.
n

Principal diferencia con ID3: permite usar tanto atributos
discretos como atributos continuos.
Problema: es necesario elegir tanto un atributo como un
umbral para realizar la división de un nodo.

n

Temperatura > 26

Temperatura > 42

Temperatura > 35

SI

NO

SI

NO

SI

NO

¿qué umbral produce la mejor división?

23

Árboles de decisión (V)

n

Algoritmo C4.5.
n No es necesario probar todos los posibles umbrales (serían

infinitas posibilidades, dado que los atributos son valores
reales).
Los únicos umbrales razonables son aquellos que se
encuentran en la frontera entre dos clases, de acuerdo con
los ejemplos de entrenamiento.
Se oredenan los atributos, y los umbrales candidatos son
aquellos que quedan en el punto medio entre dos clases.
Ejemplo:

n

n

n

Temp.

Clase

25

NF

34

NF

42

F

42

F

51

F

54

NF

66

F

67

NF

72

NF

75

NF

38

52.5

60

66.5

n

Se calcula la ganancia de información para cada atributo y
para cada umbral y se eligen atributo y umbral óptimos.

24

Árboles de decisión (VI)

n

Algoritmo C4.5: poda de los árboles.
n

ID3 nunca produce árboles demasiado grandes, pero C4.5 sí
(puede repetir atributos en el árbol).

n Un árbol demasiado grande puede producir sobreajuste.
n
n

Es necesario podar los árboles (pruning).
Se realiza un test estadístico que indica si el árbol podado
funcionará previsiblemente mejor o peor que el árbol sin
podar.
• Se considera el peor caso posible (peor situación posible dentro

•

del rango previsible).
El rango es mayor o menor en función de un parámetro (nivel de
confianza) que es ajustable.

n Hay dos posibles tipos de poda:

• Reemplazo de un subárbol (un subárbol se sustituye por una

hoja).
Elevación de un subárbol (un subárbol se eleva en el árbol
principal).

•

n

Se muestra un ejemplo:

25

Árboles de decisión (VII)

f1

f2

f3

Elevación
subárbol

A

B

C

f4

Reemplazo
subárbol

D

E

f1

f1

f2

f4

A+B

f3

A

B

D*

E*

C

f4

D

E

26

Árboles de decisión. Resumen (I)

1. Capacidad de representación:

n No muy elevada, las superficies de decisión son siempre

perpendiculares a los ejes:

temp.

95

fallará

50

no fall.

fallará

no fall.

fallará

70

120

vibración

vibr. > 120 ?

no

temp. > 95 ?

si

F

no

vibr. > 70 ?

no

NF

si

temp. > 50 ?

no

NF

si

F

si

F

27

Árboles de decisión. Resumen (II)

Legibilidad:
n Muy alta. Uno de los mejores modelos en este sentido.
Tiempo de cómputo on-line:
n Muy rápido, clasificar un nuevo ejemplo es tan sencillo como

recorrer el árbol hasta alcanzar un nodo hoja.

Rápido, tanto ID3 como C4.5 son algoritmos simples.

Tiempo de cómputo off-line:
n
Parámetros a ajustar:
n

Fundamentalmente el nivel de confianza para la poda. Fácil
de ajustar: el valor por defecto (25%) da buenos resultados.

2.

3.

4.

5.

6. Robustez ante instancias de entr