Download Aprendizaje basado en instancias - Centro de Inteligencia Artificial

Universidad
de Oviedo
Centro de
Inteligencia Artificial
SISTEMAS INTELIGENTES
T8: Aprendizaje basado en
instancias
www.aic.uniovi.es/ssii
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Índice
•  Aprendizaje basado en instancias
•  Métricas
•  NN Vecino más próximo:
° 
Regiones de Voronoi
° 
El parámetro K
•  Problemas de los algoritmos basados en
instancias
•  Técnicas de reducción de instancias
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Universidad
de Oviedo
Centro de
Inteligencia Artificial
Aprendizaje basado en instancias (IBL)
•  Idea: en situaciones parecidas se toman decisiones
similares
•  Si tenemos que tomar una decisión, buscaremos en
nuestra memoria el caso que más se parece a la situación
actual y repetiremos la misma (acertada) acción
•  Aprendizaje: la clase de un nuevo ejemplo será la misma
que la del ejemplo más similar de entre los que
conocemos
•  Quizás es la técnica de aprendizaje más intuitiva y
sencilla. Ha generado multitud de algoritmos
•  Case Base Reasoning (CBR): instancias con
representaciones simbólicas
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Similitud y distancia
•  Un concepto recurrente en todos las técnicas de
aprendizaje (supervisado y no supervisado) es el
concepto de similitud
•  Motivo: objetos similares tendrán clases/grupos
similares
•  Problema: Es difícil que dos cosas sean exactamente
iguales
• 
Más similar : ¿Cómo se mide la similitud?
•  La distancia es la inversa de la similitud
•  Muchas técnicas basan su aprendizaje en los métodos
que miden la similitud (distancia)
•  Los algoritmos basados en instancias depende casi
totalmente del concepto de distancia
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Métricas (I)
•  Es el aspecto clave de estos sistemas
•  No existe el ajuste exacto, como en las reglas o
árboles
•  El sistema hereda las desviaciones de su
métrica
° 
° 
cada métrica proporciona su sesgo de aprendizaje
no existe una métrica que funcione bien en todos los
problemas
•  Más empleadas: euclídea, HVDM....
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Métricas (II)
d(x,y) es una métrica si y solo si cumple:
° 
° 
° 
d(x,y) >= 0
d(x,y) = d(y,x)
d(x,y) >= d(x,w) + d(w,y)
para todo par de ejemplos x e y
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Métricas (III)
•  Atributos numéricos
° 
n
n
2
∑ (xi − yi )
Distancia Euclídea:
2
∑ wi (xi − yi )
i =1
i =1
n
° 
Distancia de Manhattan:
∑x −y
i
i
i =1
° 
Distancia de Chebychev:
maxi =1.. n xi − yi
•  Atributos discretos:
° 
° 
Solapamiento (atr. discretos): Si tienen el mismo valor
la distancia es 0, sino 1
VDM
2
⎛ N a , x ,c N a , y ,c ⎞
⎟
vdma (x, y ) = ∑ ⎜
−
⎜
N a , y ⎟⎠
c =1 ⎝ N a , x
C
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
VDM
⎛ N a , x ,c N a , y ,c ⎞
⎟
vdma (x, y ) = ∑ ⎜
−
⎜
N a , y ⎟⎠
c =1 ⎝ N a , x
C
2
Color
Peso
Manzana
Rojo
10
NO
Verde
145
SI
Rojo
120
SI
Verde
118
SI
Naranja
130
NO
Naranja
155
NO
Verde
130
SI
Rojo
135
SI
Naranja
140
NO
⎛ N Color , Rojo, SI N Color ,Verde, SI
vdmColor (Rojo, Verde ) = ⎜
−
⎜ N
N Color ,Verde
⎝ Color , Rojo
2
⎞
⎟ +
⎟
⎠
⎛ N Color , Rojo, NO N Color ,Verde, NO ⎞
⎜
⎟
−
⎜ N
N Color ,Verde ⎟⎠
⎝ Color , Rojo
2
2
vdmColor (Rojo,Verde) = (0.66 − 1) + (0.33 − 0) = 0.218
2
2
vdmColor (Rojo, Naranja) = (0.66 − 0) + (0.33 − 1) = 0.871
2
2
vdmColor (Naranja,Verde) = (0 − 1) + (1 − 0) = 2
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
2
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Algoritmo del vecino más próximo (NN)
•  Algoritmo simple y efectivo
•  Función de aprendizaje: almacena todos los ejemplos de
entrenamiento (lazy learning)
•  Difieren el trabajo hasta el momento de la clasificación
•  Función de evaluación: por mínima distancia
d ( x, q ) =
2
(
)
x
−
q
∑ a a
a∈ A
•  Ejemplos no vistos: clase del ejemplo (UNO) almacenado
(vecino) más próximo
•  Las regiones que se forman con 1-NN se denominan regiones de
Voronoi
•  Múltiples versiones variando la métrica y el número de vecinos
considerados (k-NN)
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Ejemplo
Atributo 2
Atributo 1
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Regiones de Voronoi
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
El parámetro K (I)
Para clasificar un nuevo ejemplo x, observamos
los K ejemplos más próximos y asignamos a x la
clase más frecuente
k=1
k=6
x
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
El parámetro K (II)
•  Parámetro clave
•  Se suele elegir impar para deshacer los posibles
empates
•  Sirve para reducir la sensibilidad al ruido
•  Hace un poco más lento el proceso de
clasificación de nuevos casos. Para solucionarlo
se pueden indexar los ejemplos
•  Ejemplos:
° 
° 
si k es muy bajo: sistema sensible al ruido
si k es muy alto: las zonas más densas pueden
acaparar las menos densas
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Problemas de los NN s (I)
1.  Almacenan demasiadas instancias
° 
° 
° 
° 
Se incrementa el tiempo de respuesta
Aumenta la sensibilidad frente al ruido
Sobreajuste
Soluciones ininteligibles
Solución: Técnicas de reducción de
instancias
° 
° 
° 
Incrementales
Decrementales
Por lotes
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Problemas de los NN s (II)
2.  Atributos: igual importancia
Solución: técnicas de selección de
atributos
° 
° 
Eliminación de atributos irrelevantes
Ponderar la importancia de cada atributo
3.  Problemas derivados de la métrica
utilizada
Solución: seleccionar la métrica que
mejor se adapta a cada problema
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Técnicas de reducción de instancias
•  Objetivo: dado un conjunto de instancias S se busca un
subconjunto R que resuelva el problema como S (o mejor)
y con menos ejemplos
•  El mayor o menor acierto, en determinadas situaciones, no
es lo más importante
•  Ventajas:
° 
° 
° 
Se reduce el tiempo de respuesta. Fundamental en problemas
en tiempo real
Menor sensibilidad al ruido
Conocimiento más inteligible ¿?
•  Se pueden utilizar no sólo para producir clasificadores
° 
° 
Eliminación de ruido
Elección de prototipos
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Tipos de algoritmos de reducción
•  Incrementales: R inicialmente vacío, y se añaden
instancias de S que cumplan alguna condición
° 
° 
Problema: influye el orden de presentación. Barajado
Ventaja: se pueden añadir nuevas instancias después de
aprender
•  Decrementales: R=S y se van eliminando aquellas
instancias que verifiquen algún criterio
° 
° 
Problema: Mayor coste computacional
Ventaja: Consiguen mayor reducción
•  Por lotes: La decisión de eliminar/incluir una instancia
depende de un lote de ejemplos.
° 
° 
Problema: Tamaño de los lotes?
Ventaja: No toman decisiones sin partir de una información
suficiente
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
Algoritmos de reducción
•  Incrementales:
° 
° 
CNN: añaden los ejemplos de S mal clasificados con los que
llevamos seleccionados en R
IB2: igual que CNN salvo inicializaciones
•  Decrementales
° 
° 
RNN: borra las instancias de R que no provocan que se
clasifiquen mal otras instancias de S
ENN: borra las instancias de R que no coinciden con la clase
mayoritaria de sus k vecinos (RENN repetir ENN)
›  Filtro de ruido
° 
Familia DROP: Borra una instancia de R si los k más cercanos
a ella pueden clasificarse correctamente sin ella
•  Lotes:
° 
SNN: demasiada complejidad
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Universidad
de Oviedo
Centro de
Inteligencia Artificial
RENN Repited Edited NN rule
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Universidad
de Oviedo
Centro de
Inteligencia Artificial
DROP 1
Sistemas Inteligentes - T8: Aprendizaje basado en instancias
Centro de
Inteligencia Artificial
Universidad
de Oviedo
RISE [Domingos, 96]
•  Es un sistema de aprendizaje híbrido
•  Combina
° 
° 
reglas
instancias
•  Las reglas se inducen mediante la
generalización de instancias
•  Una instancia puede considerarse como la regla
más específica
•  Para clasificar un nuevo ejemplo, aplica la regla
(o instancia) que se encuentra más cerca
Sistemas Inteligentes - T8: Aprendizaje basado en instancias