INF 1771 Inteligência Artificial  
Aula 14 K-Nearest Neighbor (KNN)  
Edirlei Soares de Lima  
<elima@inf.puc-rio.br>  
Formas de Aprendizado  
Aprendizado Supervisionado  
Árvores de decisão.  
K-Nearest Neighbor (KNN).  
Support Vector Machines (SVM).  
Redes Neurais.  
Aprendizado Não Supervisionado  
Aprendizado Por Reforço  
Aprendizado Supervisionado  
Observa-se alguns pares de exemplos de  
entrada e saída, de forma a aprender uma  
função que mapeia a entrada para a  
saída.  
Damos ao sistema a resposta correta  
durante o processo de treinamento.  
É eficiente pois o sistema pode trabalhar  
diretamente com informações corretas.  
K-Nearest Neighbor  
É um dos algoritmos de classificação mais simples.  
Usado para classificar objetos com base em  
exemplos de treinamento que estão mais próximos  
no espaço de características.  
?
K-Nearest Neighbor  
Para utilizar o KNN é necessário:  
(
1) Um conjunto de exemplos de  
treinamento.  
(
a distância entre os exemplos de  
treinamento.  
2) Definir uma métrica para calcular  
?
(
vizinhos mais próximos que serão  
considerados pelo algoritmo).  
3) Definir o valor de K (o número de  
K-Nearest Neighbor  
Classificar um exemplo desconhecido  
com o algoritmo KNN consiste em:  
(
desconhecido e o outros exemplos do  
conjunto de treinamento.  
1) Calcular a distância entre o exemplo  
?
(
2) Identificar os K vizinhos mais próximos.  
3) Utilizar o rotulo da classe dos vizinhos  
(
mais próximos para determinar o rótulo de  
classe do exemplo desconhecido (votação  
majoritária).  
Espaço de Caracteristicas  
2,20  
2,00  
1,80  
1,60  
1,40  
1,20  
1,10  
Altura  
2
0 40 60  
70 90 110 130 150  
Peso  
K-Nearest Neighbor  
Calculando a distancia entre dois pontos:  
Existem varias formas diferentes de calcular essa  
distancia. A mais simples é a distancia euclidiana:  
n
2
d(p,q) =  
(pi qi )  
i=1  
É importante normalizar os dados.  
Outras formas de mediar a distancia:  
Distância de Mahalanobis.  
Distância de Minkowsky.  
Hamming Distance.  
...  
K-Nearest Neighbor  
Determinando a classe do exemplo  
desconhecido a partir da de lista de vizinhos  
mais próximos:  
Considera-se o voto majoritário entre os rótulos de  
classe dos K vizinhos mais próximos.  
Como escolher o valor de K?  
K-Nearest Neighbor  
K = 1  
Pertence a classe de quadrados.  
K = 3  
Pertence a classe de triângulos.  
?
K = 7  
Pertence a classe de quadrados.  
K-Nearest Neighbor  
Como escolher o valor de K?  
Se K for muito pequeno, a classificação fica  
sensível a pontos de ruído.  
Se k é muito grande, a vizinhança pode incluir  
elementos de outras classes.  
Além disso, é necessário sempre escolher um  
valor ímpar para K, assim se evita empates  
na votação.  
K-Nearest Neighbor  
A precisão da classificação utilizando o algoritmo  
KNN depende fortemente do modelo de dados.  
Na maioria das vezes os atributos precisam ser  
normalizados para evitar que as medidas de  
distância sejam dominado por um único atributo.  
Exemplos:  
Altura de uma pessoa pode variar de 1,20 a 2,10.  
Peso de uma pessoa pode variar de 40 kg a 150 kg.  
O salário de uma pessoa podem variar de R$ 800 a R$  
2
0.000.  
K-Nearest Neighbor  
Vantagens:  
Técnica simples e facilmente implementada.  
Bastante flexível.  
Em alguns casos apresenta ótimos resultados.  
Desvantagens:  
Classificar um exemplo desconhecido pode ser um processo  
computacionalmente complexo. Requer um calculo de distancia  
para cada exemplo de treinamento.  
Pode consumir muito tempo quando o conjunto de treinamento é muito grande.  
A precisão da classificação pode ser severamente degradada  
pela presença de ruído ou características irrelevantes.