Aprendizado Baseado em
Instâncias (IBL)
Aprendizado Baseado em Instâncias
• Ideia central: guardar todos os exemplos de
treinamento {xi,f(xi)};
• Vizinho mais próximo:
– classificar xq, encontrar o exemplo de treinamento mais
próximo xn, estime
– f(xq) <= f(xn)
• K-Vizinho mais próximos:
– classificar xq, encontrar os k exemplo de treinamento
mais próximos, estime f(xq)
– o valor mais frequente no caso discreto
– a media no caso continuo
• K-Vizinho mais próximos:
– classificar xq, encontrar os k exemplo de
treinamento mais próximos, estime f(xq)
– o valor mais frequente no caso discreto
– a media no caso continuo
K-Vizinho mais próximos
• Algoritmo de treinamento
– para cada exemplo de treinamento <x,f(x)>, adicione o
exemplo a lista de exemplos de treinamento
• Algoritmo de Classificação
– dada uma instância xq a ser classificada
– Sejam x1,…xk as k instâncias mais similares a xq no
conjunto de treinamento.
^
k
f ( xq)  arg max  δ(v,f(xi ))
i1
v V
quando (a,b)= 1 se a=b e (a,b)= 0 caso contrario
Vizinho mais próximo
• Seu uso é indicado quando:
– as instâncias podem ser representadas como
pontos que mapeiam o espaço euclidiano;
– as instâncias têm menos de 20 atributos
– existem muitos exemplos no conjunto de
treinamento
Vantagens
– O aprendizado é muito rápido
– Pode aprender conceitos complexos
– Não perde informação
• Desvantagens
– Tempo de classificação lento
– Sensivel a atributos irrelevantes
Vizinho mais próximo
• O vizinho mais próximo de uma instância é definido em
termos da distância Euclidiana
• A distância entre xi xj é:
d ( xi, xj)   (ar( xi)  ar( xj))2
n
r 1
•
ar(x) denota o rth attribute da instância.
Nearest Neighbor com Distância Ponderada
• Um refinamento obvio do algoritmo é
atribuir pesos a cada k-vizinho de acordo a
sua distância a instância a classificar xq.
Observações
• A introdução de pesos no algoritmo o faz um
método altamente efetivo para varios problemas
práticos
• Robusto a dados com ruído e efetivo com grandes
bases de treinamento
• É altamente sensivel ao conjunto de atributos
– árvores de decisão é capaz de descartar os atributos
irrelevantes
Regressão Localmente Ponderada
• Esta abordagem usa exemplos de
treinamento ponderados por sua distância
para formar uma aproximação explicita a f
– função linear, quadratica, rede neural ou
alguma outra função.
Problemas de Dimensionalidade
• Imagine instâncias descritas por 20 atributos
mais somente 2 são relevantes
• Abordagens: “Stretch”, são atribuidos pesos
aos atributos, os pesos são escolhidos de
forma a minimizar os erros de predição
– escolha aleatoriamente casos e estime pesos
para predição acurada
– repita 1 com diferentes casos para obter pesos
mais confiaveis
Problemas de Recuperação
• Indexação eficiente de memória
• Kd-Tree
– as instâncias são guardadas nas folhas da
árvore, com as instâncias vizinhas nos nó mais
pertos.
Raciocinio Baseado em Casos
O que é RBC
• Solucionar um problema novo lembrando
uma situação similar previa, reutilizando
conhecimento e informação de tal situação.
• Utilizada em todas as áreas:
– médica
– financiera
Raciocinio Baseado em Casos
• Instâncias ou casos podem ser representados
por descrições simbolicas mais complexas.
• Requer uma medida de similaridade
diferente a distância euclidiana
• Os casos recuperados podem ser
combinados para formar a solução do
problema novo, baseado em raciocinio
baseado em conhecimento.
Aprendizado lazy
•
•
•
•
•
não generaliza a função de classificação
aproximação local
treinamento rápido
classificação lenta
k-NN considera todos os atributos