Aprendizado Baseado em Instancias
Introdução• Em contraste aos métodos de aprendizado que
constroem uma descrição explicita genérica da função alvo.
• Os métodos baseados em instâncias guardam os exemplos de treinamento
• A generalização é posposta até que uma nova instância deva ser classificada
• Cada vez que uma nova instância é encontrada, seus relacionamentos com os exemplos previamente guardados é examinado para atribuir um valor de função alvo.
IBL
• IBL, instance based learning• Inclui os métodos de vizinho mais
próximo, raciocínio baseado em casos• IBL é um método chamado lazy• IBL é utilizado em funções alvo com
valores discreto ou valores reais.
IBL
• IBL pode utilizar uma representação simbólica mais complexa para as instâncias -> Raciocínio baseado em Casos.
• O custo de classificar uma nova instância é alto
• Indexação eficiente dos exemplos de treinamento
Aprendizado K-Nearest Neighbor
• O método IBL mas basico é o algoritmo k-nearest neighbor
• Este algoritmo assume que todas as instâncias correspondem a um ponto no espaço n-dimensional Rn
• O vizinho mais próximo de uma instância é definido em termos da distância euclidiana.
Distância Euclidiana
• Seja a instância descrita por– (a1(x),a2(x),.........an(x))
• A distância entre 2 instâncias Xi e Xj– d(Xi,Xj)=(∑r=1,n (ar(Xi)-ar(Xj))2)1/2
Esta abordagem é apropriada tanto para funções alvo discretas ou reais.
Algoritmo para funções Alvo Discretas
• Neste caso o valor f(xq) retornado é o f(xq) mais freqüente entre os k vizinhos de f(xq).
• Algoritmo– Fase de treinamento: para cada exemplo de
treinamento (x,f(x)), adicione o exemplo a lista de exemplos.
Classificação
• Dado uma instância Xq a ser classificada• Sejam X1...Xk as instâncias de treinamento
mais próximas de Xq • Retorne
– F(Xq) <- argmax )=(∑i=1,k α(r,f(Xi))• Onde α(a,b)=1 se a=b• Caso contrario α(a,b)=0
Numero de vizinhos
1 vizinho classifica como +5 vizinhos classificam como -
Regressão
• Classificação no caso de valores reais
• f(Xq) =(∑i=1,k,f(Xi))/k
Algoritmo Nearest Neighbor Distâncias Ponderadas
• Um refinamento obvio do algoritmo é atribuir pesos a cada k-vizinho de acordo a sua distância a instância a classificar Xq
• Ex: valores discretos– F(Xq) <- argmax )=(∑i=1,kwi α(r,f(Xi))– Voto de acordo com a distância– Wi = 1/ d(Xq,Xi)2
– Se Xi= Xq -> f(Xq) = f(Xi)
Continuo
• f(Xq) =(∑i=1,k,wi f(Xi))/ ∑i=1,k,wi – Normalizar os pesos– K = todas as instâncias ou constante
• Obs: A introdução de pesos no algoritmo o faz um método altamente efetivo para vários problemas práticos
• É robusto a dados com ruído e efetivo com grandes bases de treinamento
• É sensível ao conjunto de atributos
Regressão Localmente Ponderada
• Esta abordagem usa exemplos de treinamento ponderado por sua distância para formar uma aproximação a f.
• Ex: podemos usar uma função linear, quadrática, rede neural ou alguma outra função.
• Dada uma instância a classificar Xq, a abordagem constrõe uma aproximação f usando os vizinhos de Xq.
• Esta aproximação é utilizada para calcular f(Xq)
Regressão Linear
• f(X) = w0 + w1 a1(x)+ .....+ wnan(x)
• E = ½ ∑i=1,k,( f(X) – fe(x))2
• ∆W=ŋ ∑i=1,k,( f(X) – fe(x)) an(x)
Problemas de Dimensionalidade
• Imagine instâncias descritas por 20 atributos, mais somente 2 são relevantes
• Problemas de recuperação, kd-tree, as instâncias são guardadas nas folhas da arvore, com as instâncias vizinhas no no perto dele. Os nos internos da arvore ordenam a nova instância e a classificam testando seus atributos.
Comentarios IHC
• Baixos requisitos de memoria e processamento
• Uma hipoteses• Sensibilidade a ordem no treinamento,
maior quantidade de instâncias de treinamento para converger
• Menos sensitivo a ruido
Indução de Conceitos Competitivos
Indução de Conceitos Competitivos
• Protótipos• Tarefa– dado um conjunto de instâncias pre-
classificadas– encontrar uma descrição intencional– um conjunto de protótipos
Indução de Conceitos Competitivos
• Esquemas competitivos não podem ser representados isoladamente
• A extensão de um conceito depende de sua descrição e da dos outros
• O operador típico é o calculo da media das instâncias de treinamento.
• A descrição especifica a tendência central das instâncias
Aprendizado baseado em Instâncias
• Guardam instâncias específicas ao invés de uma descrição abstrata
• Protótipos– conjunção de pares atributos valor
Protótipos
A
B
Peso
Altura Altura
Peso
A D
B C
Protótipos
• Usar protótipos para classificação é um processo de três passos:
– Dada uma instância I, – calcula-se sua distância a cada protótipo
• distância euclidiana, • distância de hamming
– Usa-se o resultado para classificar a instância, o protótipo mais perto
Método média das Instâncias
• Realizar a média das instâncias para encontrar o protótipo de cada classe
• Para determinar o valor pi de um atributo para um protótipo (numérico)
– pi= 1/n xij (j=1,n)
Método incremental
• Ao encontrar uma instância de uma classe nova, guarde esta instância como protótipo
• Quando observar uma instância de uma classe conhecida, recalcule o protótipo
– para cada atributo i pi= (xi-pi)/n+1
– para atributos nominais, escolha o valor mais frequente
Método média das Instâncias
• Em termos de eficiência e elegância é um dos melhores
• pouca expressão representacional• linhas de fronteiras
Método dos Pesos
• Um dos problemas do método anterior é tratar todos os atributos de forma equivalente
• Se os atributos tem escalas diferentes– normalizar
• Alguns atributos tem maior importância
Relevância dos atributos
- -
Peso
Altura
+
+ + -
Pesos de atributos iguais Altura 0.93 e peso 0.68
- -
Peso
Altura
+
+ + -
Métrica de distância
i wi (pi-xi)2
• wi ?
• wi = 1 - 1/n( (k=1,c) j=1,nk pki - xji)• n = número total de instâncias de
treinamento• nk = número de instâncias para a
classe c
Modelos Estatisticos
Naive Bayes
Naive Bayes
• 2 presupostos– todos os atributos são igualmente importantes– independencia estatistica (dado o valor da
classe)• A independencia nunca é verdadeira• Na pratica o esquema trabalha bem.
Probabilidades para a base Weather
5/14
5No
9/14
9Yes
Play
3/52/5
32No
3/96/9
36
Yes
TrueFalse
TrueFalse
Windy
1/54/5
14NoYesNoYesNoYes
6/93/9
63
NormalHigh
NormalHigh
Humidity
1/52/52/5122
3/94/92/9342
Cool2/53/9RainyMildHotCoolMildHot
Temperature
0/54/9Overcast3/52/9Sunny23Rainy04Overcast32Sunny
Outlook
NoTrueHighMildRainyYesFalseNormalHotOvercastYesTrueHighMildOvercastYesTrueNormalMildSunnyYesFalseNormalMildRainyYesFalseNormalCoolSunnyNoFalseHighMildSunnyYesTrueNormalCoolOvercastNoTrueNormalCoolRainyYesFalseNormalCoolRainyYesFalseHighMildRainyYesFalseHighHot Overcast NoTrueHigh Hot SunnyNoFalseHighHotSunnyPlayWindyHumidityTempOutlook
5/14
5No
9/14
9Yes
Play
3/52/5
32No
3/96/9
36
Yes
TrueFalse
TrueFalse
Windy
1/54/5
14NoYesNoYesNoYes
6/93/9
63
NormalHigh
NormalHigh
Humidity
1/52/52/5122
3/94/92/9342
Cool2/53/9RainyMildHotCoolMildHot
Temperature
0/54/9Overcast3/52/9Sunny23Rainy04Overcast32Sunny
Outlook
?TrueHighCoolSunnyPlayWindyHumidityTemp.Outlook Um novo dia:
Probabilidade de cada classePara “yes” = 2/9 3/9 3/9 3/9 9/14 = 0.0053Para “no” = 3/5 1/5 4/5 3/5 5/14 = 0.0206
Normalizando entre 0 e 1::P(“yes”) = 0.0053 / (0.0053 + 0.0206) = 0.205P(“no”) = 0.0206 / (0.0053 + 0.0206) = 0.795
Probabilidades para a base Weather
Regra de BayesA Probabilidade de um evento H dada a evidência E:
A proobabilidade de H a priori : Pr[H] A probabilidade de um evento antes de ver a
evidênciaA probabilidade a posteriori de H:Pr[H|E]
A probabilidade de um evento após conhecer a evidência
Thomas BayesNascido: 1702 em London, EnglandMorto: 1761 em Tunbridge Wells, Kent, England
Pr [H∣E ]= Pr [E∣H ]Pr [H ]Pr [E ]
Naive Bayes para Classificação
• Aprendizado: Qual é a probabilidade de uma classe dada uma instância??– Evidência E = Instância– Evento H = valor da classe para a instância
• Os atributos são independentes
Pr[H|E]= Pr[E1|H]Pr[E2|H]...Pr[En|H]Pr[E] Pr[E]
Exemplo
?TrueHighCoolSunnyPlayWindyHumidit
yTemp.Outlook Evidência E
Probabilidade daclasse “yes”
Pr [yes∣E ]=Pr [Outlook=Sunny ∣yes ]
×Pr [Humidity=High ∣yes ]×Pr [Windy=True ∣yes ]
×Pr [yes ]Pr [E ]
=
29 ×3
9 ×39 × 3
9× 914
Pr [E ]
×Pr [Temperature=Cool∣yes ]×Pr [Humidity=High ∣yes ]×Pr [Windy=True ∣yes ]
×Pr [yes ]Pr [E ]
=
29 ×3
9 ×39 × 3
9× 914
Pr [E ]
Discusão
• Naive Bayes trabalha muito bem mesmo quando existe dependência entre atributos.
• Adicionando muitos atributos redundantes causará problemas