6 - md - classificação knn-convertido

Prévia do material em texto

Objetivos
●
●
Aprender conceitos básicos sobre classificação 
de dados
Conhecer o método de classificação dos k-
vizinhos mais próximos
Classificação
●
●
É a tarefa de atribuir objetos em categorias pré-
definidas
Engloba muitas aplicações distintas:
–
–
–
– Detecção de mensagens de spam em e-mails 
Diagnóstico de doenças
Classificação de imagens
...
Classificação
Exemplos
Tarefa Conjunto de atributos, x Classe, y
Categorização Características extraídas Spam ou não-spam
de e-mails do cabeçalho e do corpo
do e-mail
Identificação de Características extraídas a Células malignas ou
células partir de exame de benignas
tumorais ressonância magnética
Classificação
● Formalmente:
– Dados de entrada: um conjunto de instâncias, 
cada uma representada por uma tupla (x,y)
●
● x denota os atributos 
y denota a classe
–
–
Se y é discreto → Classificação 
Se y é contínuo → Regressão
Classificação
● Um modelo de classificação é útil para:
– Modelagem descritiva: serve como ferramenta explicativa para distinguir 
objetos de classesdiferentes
● Exemplos:
– quais características (x) definem um mamífero?
– Quais características (x) definem um cliente que recebeu crédito bancário?
– Modelagem preditiva: modelo é utilizado para prever a classe de novos
registros
● Exemplos:
– tendo as características de um animal, como determinar a classe (y) à qual o animal 
pertence (e.g. mamífero ou réptil)?
– Tendo as características de um cliente (renda, estado civil, tempo no emprego atual), como 
determinar a classe (y) do cliente (se é interessante ou não o banco fornecer crédito)?
Processo de classificação
Processo de classificação
Modelo
Algoritmo de 
aprendizagem
Dados de treinamento
Dados de teste
Aprende 
modelo
Usa 
modelo
Critérios de comparação de 
classificadores
●
●
●
●
●
Acurácia: capacidade de classificar corretamente novas 
instâncias
Rapidez: mede o tempo gasto na classificação de dados
Robustez: habilidade de classificar corretamente mesmo 
na presença de ruídos e valores desconhecidos
Escalabilidade: eficiência de um classificador ou método 
em grandes volumes de dados
Interpretabilidade: facilidade de um usuário entender ou 
compreender as regras produzidas pelo classificador
Avaliação do desempenho
●
●
É baseada na contagem de instâncias de teste previstas 
corretamente e incorretamente pelomodelo
Contagens são baseadas em uma tabela chamada Matriz de 
Confusão
●
●
Acurácia = porcentagem das tuplas de teste que são 
corretamente classificadas
Erro = 1 –Acurácia
Outras medidas de 
desempenho
● Exemplo:
–
–
–
–
– C1: “tem câncer” (4pacientes)
C2: “não tem câncer” (500 pacientes)
Método classificou corretamente 454 pacientes que não tem câncer 
Não acertou nenhum dos que tem câncer
Acurácia = 90%
● Mesmo com acurácia alta, esse classificador é bom?
k-vizinhos mais próximos (kNN)
●
●
Tipo de aprendizado denominado Lazy Learning
Ideia: “If it walks like a duck, quacks like a duck, and 
looks like a duck, then it’s probably a duck”
Instâncias 
treinamento
Instância 
de Teste
Calcula 
Distância
Escolha as k 
instâncias mais 
“próximas”
k-vizinhos mais próximos (kNN)
● kNN atribui uma classe ao objeto de interesse considerando 
a classe mais frequente entre seus k objetos mais próximos
● Informalmente, o algoritmo pode ser descrito nos passos a 
seguir:
–
–
– Armazene a base dados de treinamento (atributos e 
classe) na memória
Para cada novo objeto, calcule a proximidade dele com os 
objetos da base de treinamento
Classifique o novo objeto na classe mais frequente dos 
seus k vizinhos mais próximos
Método kNN
●
●
●
Dados: BD de m tuplas de treinamento classificadas (a1, …, an, c);
Escolher o parâmetro K = número de vizinhos mais próximos
Considere uma tupla X = (x1, …, xn) não classificada (ou seja, pertencente 
aos dados de teste)
1) Atributos são normalizados: p.ex., atributo a1
2)Calcula distância euclidiana entre X e todas as tuplas da base 
treinamento
3)Ordena as distâncias e determina os k vizinhos mais próximos da tupla 
X, isto é, as k tuplas com menor distância a X
4)A classe de X será a classe que aparecer com maior frequência 
(quantidade maior) dentre ask-tuplas
Exemplo kNN
●
●
●
A instância de teste (círculo
verde) deve ser classificada
como um quadrado azul ou
tr iângulo vermelho?
Se k = 3 (círculo linha sólida), a 
instância será classificada como 
tr iângulo vermelho, porque há 2 
triângulos e apenas 1 quadrado 
dentro desse círculo.
Se k = 5 (círculo linha tracejada), 
a instância será classificada 
como quadrado azul, pois tem-
se 3 quadrados e 2 triângulos 
dentro desse círculo
Exercício
● Dada a base de dados a seguir, classifique os 
novos objetos usando o método kNN
Considerações kNN
●
●
●
●
É preciso estar atento comas etapas de pré-processamento 
e as medidas de proximidade escolhidas
A etapa de teste (isto é, classificar uma nova instância) pode 
ser um pouco mais lenta que a de outros algoritmos
kNN considera informações locais para realizar a 
classificação, o que pode ser uma limitação em bases de 
dados com muito ruído
kNN pode produzir fronteiras de decisão de forma 
arbitrária devido à representação mais flexível do modelo