Construção de listas de
decisão
• Os tópicos anteriores tratam de indução
de conceitos que podem ser descritos
usando uma única região de decisão
• Neste tópico se tratará da indução de
descrições disjuntivas (v)
Múltiplas regiões
Peso
+ +
-
+ +
-
+
+
+
Altura
Construção de listas de
decisão
Construção de listas de
decisão
• Forma normal disjuntiva FND
– combina um conjunto de descrições
D1,D2,..Dn em uma disjunção {D1vD2v..Dn }
– as vezes mais de uma classe "match"uma
instância
• criar descrições mutualmente exclusivas
• precedência, lista ordenada
A tarefa de indução disjuntiva
• Dado: Um conjunto de instâncias de
treinamento, cada uma com sua classe
associada
• Encontrar: Uma descrição disjuntiva que,
corretamente classifique instâncias não
observadas
• Ao menos para algumas
representações, o espaço de FND é
parcialmente ordenado (G->S), mas o
Aprendizado não-incremental
Dividir e Conquistar (NDC)
• Tarefa de discriminar entre duas classes
– construir a FND de uma classe e usar a outra
como default. Tecnicamente o resultado é
uma lista de decisão.
NDC
• Entrada:
• Pset, conjunto de instâncias +
• Nset, conjunto de instâncias • FND uma disjunção de uma descrição de uma
única região
• Saída: Uma disjunção de uma única região
• Nivel-Top chamada: NDC(Pset,Nset,{})
• Procedimento NDC(Pset,Nset,FND)
• Se Pset esta vazio Então retorne FND
• CC Encontre uma região D que cobra algumas
instâncias em Pset e não em Nset, FND=FND+D,
NDC usando HSG
Peso
Pes
o
+
+
+
+
-
-
+
+
Altura
-
+
+
Altura
-
MDC
• NDC é projetado para inducir
expressões para uma única classe
• MDC utiliza NDC como bloco de
construção para mais de duas classes
MDC
• Entrada: Cset é conjunto dos nomes das
classes, Iset é o conjunto das instâncias de
treinamento.
• Saída: uma lista de decisão
• Procedimento MDC(Cset,Iset)
• Rule-set = {}
• Para cada Classe em Cset,
– Pset = {i Iset e i  Classe}, Nset = {i Iset e i
 Classe}, FND = NDC(Pset,Nset,{}).
– Para cada termo D em FND, Rule-set =Ruleset + Se D então Classe
Indução Incremental usando
Dividir para conquistar (IDC)
• Utiliza ideias de Hill Climbing
• Guarda uma única hipoteses em
memoria (um conjunto de termos lógicos
disjuntivo)
• Guarda as k últimas instâncias de
treinamento, para avaliar as hipoteses
• Revisa suas hipoteses somente quando
realiza um erro de classificação
Revisões em IDC
 Erro de classificação de uma instância
positiva, generalizar a hipoteses
– modificar um termo da FND; remover um teste
booleano, nominal ou características
numericas, Aumentar o tamanho do retangulo
ou mudanças nos pesos
– Como a hipoteses pode ter multiples termos,
IDC deve aplicar generalização a cada um
deles
– Outra alternativa envolve em adicionar um
Revisões em IDC
• Erro de classificação de uma instância
negativa, especializar a hipoteses
• modificar cada termo da FND que case
com a instância; adicionar um teste
booleano, nominal ou características
numericas, diminuir o tamanho do
retangulo ou mudanças nos pesos
• Outra alternativa envolve em eliminar um
termo
Algoritmo IDC
Função de Avaliação
• Incluir uma medida da simplicidade da
expresão e de precisão
• simplicidade 1/t , t número de termos
• precisão a = (Pc + N~c)/k
• F = a + 1/t ou F = (1-w)a + w 1/t , w entre
0e1
Comportamento de IDC
+
+
1/1+1/1=
2
2/2+1/1=
2
+
3/4+1/1=7/
4
+
4/4+1/2=3/
2
V
-
2/3+1/1=5/
3
+
4/4+1/2=3/
2
V
Problemas
• Métodos que utilizam "Hill Climbing"
possuem baixos requisitos de memoria e
processamento
• Eles consideram somente uma
hipoteses
• Sensibilidade a ordem das instâncias de
treinamento, maior número de casos
para convergência
• Pode não converger e em ambiente com
Indução de listas de decisão
por excepção NEX
• O método dividir e conquistar constrõe a
lista de forma top-down, adicionando o
primeiro termo na lista e logo o
segundo...
• Pode-se operar na direção oposta, NEX
inicializa sua lista criando uma classe
default, baseado na classe mais
frequente
• Em cada iteração, NEX aplica sua lista
NEX
• Nex seleciona a classe mais comun
neste conjunto,
• chama uma subrutina para inducir a
descrição mais específica que cobre os
membros desclassificados desta classe,
e
• adiciona a regra na frente da lista de
decisão
• Continua-se desta forma até que a lista
Fronteiras criadas por NEX
Pes
o
Pes
o
+
+
+
-
+
_
+
_
+
_
_ +
+
+
_
+
Altura
-
_
+
_
_ +
+
_
+
+
_
+
Altura
Algoritmo NEX
Indução de disjunções
competitivas
• NDC, utiliza uma tecnica competitiva
simples, para criar um conjunto inicial de
descrições
• NDC utiliza isto para classificar o
conjunto.
• O algoritmo remove os casos
problematicos e os coloca em "pseudo
classes"
• NDC produz um novo conjunto de
Algoritmo NDC
NDC e protótipos
Pes
o
Pes
o
- -
- -
- - + +
- - + +
+ +
+
+
+ +
+
+
Altura
Altura
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
teinamento
Aprendizado K-Nearest Neighbor
• O método IBL mas basico é o algoritmo knearest 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 instâ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
Exercicios
Indução de Conceitos
Competitivos
Indução de Conceitos
Competitivos
• Protótipos
• Tarefa
– dado um conjunto de instâncias preclassificadas
– 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
Peso
Peso
C
B
A
B
Altura
A
D
Altura
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
Peso
++
-
+
--
Altura
Pesos de atributos iguais
++
-
+
--
Altura
Altura 0.93 e peso 0.68
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