Classificadores Lazy
Aprendem a partir de seus vizinhos
AULA 9
DATA MINING
Sandra de Amo
História




Método introduzido nos anos 50.
Muito dispendioso computacionalmente.
Só ganhou popularidade a partir dos anos 60,
como o aumento da capacidadecomputacional
dos computadores.
Muito usado na área de Reconhecimento de
Padrões.
Descrição do Método KNN






Dados: Banco de Dados de m tuplas classificadas (a1,...,an,C)
Uma tupla X = (x1,...,xn) não classificada
Os valores dos atributos são normalizados.
Valor normalizado = (v.real - MinA)/(MaxA – MinA)
Calcula-se a distância de X a cada uma das tuplas do banco
de dados.
Pega-se as k tuplas do banco de dados mais próximas de X.
A classe de X é a classe que aparece com mais frequência
entre as k tuplas mais próximas de X.
Diferentes valores de K
K=1
K=2
K=3
Algumas questões

Como calcular a distância entre duas tuplas ?


Para atributos contínuos : distância Euclidiana
d(x,y) = √ Σni=1 (xi – yi)2
Para atributos categóricos
Se xi = yi então xi – yi = 0
Se xi e yi são distintos: xi – yi = 1

Como lidar com valores incompletos (ausentes) ao calcular a
distância entre duas tuplas X e Y ?



Se xi e yi são ausentes: xi – yi = 1
Se xi é ausente e yi não: xi – yi = max { |1 – yi|, |0 – yi| }
Como determinar o melhor valor de K (=número de vizinhos)
?
Obtido repetindo-se os experimentos.
Vantagens e Desvantagens

Performance




Não constrói um modelo de classificação.
Processo de classificação de uma tupla é lento.
Classificadores Eager gastam tempo para construir o
modelo. O processo de classificação de uma tupla é
rápido.
Sensível a ruídos


KNN faz predição baseando-se em informações locais à
tupla sendo classificada.
Arvores de decisão, redes neurais e bayesianas encontram
modelo global que se leva em conta todo o banco de
dados de treinamento.
Exemplo
Compra-computador
ID
IDADE
RENDA
ESTUDANTE
CREDITO
CLASSE
1
≤ 30
Alta
Não
Bom
Não
2
≤ 30
Alta
Sim
Bom
Não
3
31...40
Alta
Não
Bom
Sim
4
> 40
Média
Não
Bom
Sim
5
> 40
Baixa
Sim
Bom
Sim
6
> 40
Baixa
Sim
Excelente
Não
7
31...40
Baixa
Sim
Excelente
Sim
8
≤ 30
Média
Não
Bom
Não
9
≤ 30
Baixa
Sim
Bom
Sim
10
> 40
Média
Sim
Bom
Sim
11
≤ 30
Média
Sim
Excelente
Sim
12
31...40
Média
Não
Excelente
Sim
13
31...40
Alta
Sim
Bom
Sim
14
> 40
Média
Não
Excelente
Não
X = (≤ 30, Média,Sim,Bom)
Exemplo
Distância
VALOR
d(X,1)
1,41
d(X,2)
1
d(X,3)
1,73
d(X,4)
1,41
d(X,5)
1,41
d(X,6)
1,73
d(X,7)
1,73
d(X,8)
1
d(X,9)
1
d(X,10)
1
d(X,11)
1
d(X,12)
1,73
d(X,13)
1,41
d(X,14)
1,73
Exemplo


K=5
Os 5 vizinhos mais próximos são

X1 = ( ≤ 30
X2 = (≤ 30
X3 = ( ≤ 30
X4 = ( > 40
X5 = (≤ 30

Logo, X é classificada na classe = Sim




Alta
Média
Baixa
Média
Média
Sim
Não
Sim
Sim
Sim
Bom)
Bom)
Bom)
Bom)
Exc. )
Classe = Não
Classe = Não
Classe = Sim
Classe = Sim
Clase = Sim
Acurácia de
Classificadores
Como medir ?
Holdout

Método Holdout





Considera-se um banco de dados de amostras
Divide-se em 2 partes : D1 e D2
D1 é 2 vezes maior do que D2
Acurácia= número de tuplas de D2 bem classificadas
dividido pelo total de tuplas de D2
Subamostragem Randômica



Variação do método Holdout
Método Holdout é repetido k vezes
Acurácia geral = média das acurácias em cada rodada
Cross-Validation

Validação Cruzada (k-fold Cross-validation)






Dados iniciais são particionados em k partes D1,..., Dk de tamanhos
aproximados
Treinamento e testes são executados k vezes.
Em cada iteração i (i=1...k) Di é escolhido para teste e o restante das
partições são utilizadas como treinamento.
Cada tupla de amostra é utilizada o mesmo número de vezes como
tupla de treinamento e uma única vez como tupla de teste.
Acurácia de um classificador = número total de tuplas bem
classificadas nas k iterações dividido pelo total de tuplas no banco de
dados original.
Acurácia de um preditor = Soma dos erros dividido nas k iterações
dividido pelo total de tuplas no banco de dados original.
Variantes do Cross-validation

Leave-one-out




Caso especial de k-fold cross validation
Cada Di tem um único elemento
Em cada iteração somente 1 tupla é utilizada para teste.
Cross-validation estratificada


As “folhas” D1, ... , Dk são tais que a distribuição das
classes em cada folha é aproximadamente igual à
distribuição nos dados iniciais.
Ex: se em D a proporção de tuplas das classes C1 e C2 é
de 2 para 1 então esta proporção é mantida em cada
“folha” Di.
Bootstrap

A cada vez que uma tupla é selecionada para
participar do grupo de treinamento, ela volta
novamente para o banco inicial, podendo ser
novamente selecionada na próxima vez.

Bancos de treinamento e testes podem conter
tuplas repetidas.
.632 Bootstrap




Banco de dados original com d tuplas
Os sorteios de tuplas são realizados d vezes.
Ao final de d sorteios temos um banco D1 de
treinamento (boostrap sample) e um banco D2
de testes.
A amostra de treinamento D1 tem exatamente
d elementos.
.632 Bootstrap


É bem provável que alguma tupla t do banco original
ocorre repetida em D1.
Qual a probabilidade de uma tupla não estar no
banco de treinamento D1 no final dos d sorteios ?






(1 – 1/d)d
lim (1 – 1/d)d = 1/e (para d  infinito)
e = 2.718
1/e = 0,368
36,8% das tuplas não são escolhidas: formam o conj. D2
63,2% das tuplas são escolhidas: formam o boostrap D1
Acurácia medida com o Boostrap





Repete-se o processo de amostragem k vezes
Em cada vez construimos D1 e D2 e medimos a acurácia do
classificador (ou preditor) M
Acc(Mi)test-set = acurácia de M calculada na iteração i, com
D2 como teste e D1 como treinamento
Acc(Mi)train-set = acurácia de M calculada na iteração i, com
dados originais como teste e D1 como treinamento.
Acurácia(M) =
k
Σ (0.632*Acc(Mi)test-set + 0.368*Acc(Mi)train-set )
i=1