PDF de programación - Aprendizaje inductivo - Aprendizaje Automático y Data Mining

Aprendizaje Automático y Data Mining

Bloque II
APRENDIZAJE INDUCTIVO

1

Índice

n Conceptos básicos.

n Concepto, instancia, atributo, clase.

n Árboles de decisión.

n Estructura.
n Generación automática.

n Otros modelos.
n Criterios de selección de modelos.

n Selección de modelos.
n Selección de algoritmos.
n Resumen.

2

CONCEPTOS BÁSICOS

3

Objetivo

n El objetivo es general un modelo

(general) a partir de ejemplos
(específicos).

n El conjunto de ejemplos usado se llama

conjunto de entrenamiento.

n Cuatro elementos fundamentales:

conceptos, instancias, atributos y clases.

4

Definiciones

n Concepto: el modelo a inferir a
partir de los ejemplos (también
llamado hipótesis).

n Instancia: cada uno de los ejemplos.
n Atributo: cada una de las medidas

de un ejemplo.

n Clase: el atributo que debe ser
deducido a partir de los demás.

5

Ejemplo

Ejemplo: modelado de la probabilidad de fallo de una

máquina.

n Clases: la máquina fallará / la máquina no fallará.
n Atributos: conjunto de medidas:

n Temperatura.
n Nivel de vibraciones.
n Horas de funcionamiento.
n Meses desde la última revisión.

n Instancias: ejemplos pasados (situaciones conocidas).
n Concepto: relación entre las medidas y la probabilidad de

fallo:
n SI nivel_vibraciones = alto Y temperatura = alta ENTONCES

fallará.

6

Atributos

n Múltiples tipos de atributos:
n Real: puede tomar cualquier valor dentro

de un cierto rango.
n ej. temperatura como un número real

(grados).

n Discreto: toma valores discretos

ordenados.
n ej. temperatura como {alta, media, baja}.
n Categórico: toma valores discretos no

ordenados.
n ej. color como {azul, rojo, amarillo}.

7

Conceptos

n Los conceptos se pueden expresar de

diversas formas:
n Árboles de decisión
n Listas de reglas
n Redes neuronales
n Modelos bayesianos o probabilísticos
n Etc.

n Los árboles de decisión son uno de los

modelos más usados en aprendizaje
automático.

8

ÁRBOLES DE DECISIÓN

9

Árboles de decisión (I)

n Ejemplo: modelado de la probabilidad de fallo de una

máquina.

nivel vibración

ALTO

temperatura

BAJO

no fallará

ALTA

fallará

BAJA

horas funcionam.

<1000

no fallará

>1000

meses revisión

< 1 MES

no fallará

> 1 MES

fallará

10

Árboles de decisión (II)

n Representan funciones lógicas (if-then).
n Compuestos de nodos y ramas.
n Nodos internos = atributos (medidas).
n Nodos hoja = clases.
n Nodo raíz = nodo superior del árbol.

n Objetivo en aprendizaje automático:

inferir un árbol de decisión a partir de un
conjunto de instancias o ejemplos.

11

Árboles de decisión (III)

n Ejemplo de conjunto de entrenamiento:

Temperatura

Nivel de

vibraciones

Horas de

funcionamiento

ALTA

BAJA

ALTA

ALTA

BAJA

BAJA

ALTA

ALTO

BAJO

BAJO

BAJO

ALTO

ALTO

ALTO

< 1000

< 1000

>1000

< 1000

< 1000

>1000

< 1000

Meses desde

revisión
> 1 MES

Probabilidad

de fallo
fallará

< 1 MES

> 1 MES

> 1 MES

> 1 MES

> 1 MES

< 1 MES

no fallará

no fallará

no fallará

no fallará

fallará

fallará

12

Árboles de decisión (IV)

n Múltiples formas de inferir el árbol:

n Trivial: se crea una ruta del árbol por cada

instancia de entrenamiento.
• Árboles excesivamente grandes.
• No funcionan bien con instancias nuevas.

n Optimo: el árbol más pequeño posible

compatible con todas las instancias.
• Inviable computacionalmente.

n Pseudo-optimo (heurístico): selección del

atributo en cada nivel del árbol en función de la
calidad de la división que produce.
• Los principales programas de generación de árboles
utilizan procedimientos similares (C4.5, CART, etc).

13

Árboles de decisión (V)

Crearemos un árbol a partir de los ejemplos de

entrenamiento anteriores.

n ¿Qué atributo elegir para el primer nodo?

ATRIBUTO

VALORES

CLASE

fallará

no fallará

Temperatura

Nivel de
vibraciones

defuncionamien

Horas

to

Meses desde

revisión

Alto
Bajo
Alto
Bajo

< 1000
>1000

> 1 mes
< 1 mes

2
1
3
0

2
1

2
1

2
2
1
3

3
1

3
1

14

Árboles de decisión (VI)

n Árbol construido hasta el momento:

nivel vibración

ALTO

?

BAJO

no fallará

No fallará (1 instancia)
fallará (3 instancias)

no fallará (3 instancias)

fallará (0 instancias)

n ¿Qué atributo se debe usar en el siguiente nivel

del árbol (rama izquierda)?

15

Árboles de decisión (VII)

Sólo aquellos ejemplos de entrenamiento que llegan al nodo se utilizan
para elegir el nuevo atributo:

ATRIBUTO

VALORES

CLASE

fallará

No fallará

Temperatura

Horas de

funcionamiento

Meses desde

revisión

Alta

BAja

< 1000

>1000

> 1 mes

< 1 mes

2

1

2

1

2

1

0

1

1

0

1

0

16

Árboles de decisión (VIII)

n Árbol construido hasta el momento:

nivel vibración

ALTO

temperatura

ALTA

fallará

(0,2)

BAJA

?

(1,1)

BAJO

no fallará

(3,0)

n ¿Qué atributo se debe usar en el siguiente nivel

del árbol (rama dereecha)?

17

Árboles de decisión (IX)

De nuevo, sólo aquellos ejemplos de entrenamiento que llegan al nodo
se utilizan para elegir el nuevo atributo:

ATRIBUTO

VALORES

CLASE

fails

works

Horas de

funcionamiento

Meses desde

revisión

< 1000

>1000

> 1 mes

< 1 mes

0

1

1

0

1

0

1

0

18

Árboles de decisión (X)

n Árbol obtenido finalmente:

nivel vibración

ALTO

temperatura

BAJA

horas funcion.

<1000

no fallará

(1,0)

BAJO

no fallará

(3,0)

>1000

fallará

(0,1)

ALTA

fallará

(0,2)

… muy similar al árbol original, utilizando sólo 7

ejemplos de entrenamiento!

19

OTROS MODELOS

20

Otros modelos

n Los árboles de decisión son sólo uno de los

posibles modelos.

n En los próximos apartados se explican otras

posibilidades.

n Dependiendo de la aplicación, se deberá elegir

un modelo u otro.

n A continuación se indican algunos criterios para

elegir modelos.

21

CRITERIOS DE SELECCIÓN

22

Criterios para elegir un modelo

n Dos decisiones fundamentales:

n El tipo de modelo (árboles de decisión, redes

neuronales, modelos probabilísticos, etc).

n El algoritmo usado para construir o ajustar el

modelo a partir de las instancias de
entrenamiento.
• Por ejemplo, hay múltiples formas de construir un
árbol de decisión a partir de ejemplos; algo similar
sucede con las redes neuronales o el resto de
modelos.

23

Selección del modelo (I)

1. Capacidad de representación

n Capacidad de expresar múltiples conceptos

diferentes.

n Relacionado con el tipo de fronteras de

decisión que se pueden crear.

n Frontera de decisión: frontera entre clases

distintas de acuerdo con el modelo.

n Las fronteras de decisión que crea cada

modelo (árboles de deisión, redes neuronales,
etc.) son diferentes.

24

Selección del modelo (II)

n Ejemplo con sólo dos atributos:

temp.

95

fallará

50

no fall.

fallará

no fall.

fallará

70

120

vibración

Árboles de decisión: fronteras
perpendiculares a los ejes.

vibr. > 120 ?

no

temp. > 95 ?

si

F

no

vibr. > 70 ?

no

NF

si

temp. > 50 ?

no

NF

si

F

si

F

25

Selección del modelo (III)

n Ejemplo con sólo dos atributos :

temp.

fallará

95

50

no fall.

fallará

fallará

no fall.

70

120

vibración

Redes neuronales (NN): fronteras no
lineales:

• Mayor capacidad de representación.
• Permiten representar conceptos más
complejos que los árboles de
decisión.
• Se estudiarán más adelante.

26

Selección del modelo (IV)

2. Legibilidad:

n Capacidad de ser leido e interpretado por un humano.
n Árboles de decisión: fáciles de entender e intepretar: los

niveles altos del árbol indican los atributos más importantes.

n Redes neuronales: difíciles (o imposibles) de interpretar:
múltiples conexiones entre neuronas con pesos diferentes.

n Un modelo legible puede ofrecer información sobre el

problema que se estudia (ej. indicar qué atributos afectan a
la probabilidad de fallo de una máquina, y cómo).

n Un modelo no legible sólo puede ser usado como un

clasifcador (ej. Permite predecir si una máquina fallará o no
aplicando el modelo).

27

Selección del modelo (V)

3. Tiempo de cómputo on-line:

n Tiempo necesario para clasificar una nueva

instancia:
• Árboles de decisión: tiempo necesario para recorrer

el árbol, evaluando las funciones lógicas de cada
nodo.

• Métodos probabilísticos: tiempo necesario para

calcular probabilidades o funciones de densidad de
probabilidad.

• Redes neuronales: tiempo necesario para realizar las
operaciones (sumas, productos, sigmoides) incluidas
en la red.

• Etc.

28

Selección del modelo (VI)

Importancia del tiempo de cómputo on-

line:
n Este tiempo se consume cada vez que se debe

clasificar una nueva instancia.

n Algunas aplicaciones requieren clasificar miles

de instancias.
• Ejemplo: clasificación de cada uno de los pixels de

una imagen aerea como tierra de cultivo, río,
carretera, edificios, etc.

• Es necesario clasificar millones de pixels.
• El tiempo de cómputo es muy importante.

29

Selección del algoritmo (I)

1. Tiempo de cómputo off-line.

n Tiempo necesario para construir o ajustar el modelo a

partir de los ejemplos de entrenamiento.

• Árboles de decisión: tiempo necesario para elegr la

estructura del árbol y los atributos a situar en cada uno de
los nodos.

• Redes neuronales: tiempo necesario para ajustar los
pesos de las conexiones (se estudiará más adelante).

• Etc.

n Ejemplo: un árbol de decisión se puede generar

utilizando diferentes algoritmos. El tiempo empleado
por cada algoritmo puede ser diferente.

30

Selección del algoritmo (II)

Importancia del tiempo de cómputo off-line.

n Sólo se consume una vez, cuando se han

recopilado todos los ejemplos de
entrenamiento y se genera el modelo con
ellos.

n Dependiendo de la aplicación, no es un

problema que el tiempo de cómputo on-line
sea elevado (es aceptable tener un ordenador
procesando durante un día entero para
obtener el resultado).

31

Selección del algoritmo (III)

2. Dificultad de ajuste de parámetros.

n Algoritmo ideal: no dispone de parámetros

para ajustar o es muy poco sensible a la
modificación de los parámetros: es fácil
generar e