K-Nearest Neighbors (KNN)

Escrito por Michael Queiroz Cardoso

Esta aula faz parte do Guia da Teoria do Departamento de Inteligência Artificial do NOIC. Para acompanhar bem o conteúdo, é importante já saber o que são features, target e dados de treino. Esses conceitos aparecem na nossa Introdução ao Machine Learning.

Imagine que precisamos classificar uma fruta que nunca vimos. Em vez de criar várias regras sobre cor, peso e tamanho, podemos compará-la com frutas já conhecidas. Se a maioria das frutas parecidas for uma maçã, essa será uma boa previsão. O KNN transforma justamente essa ideia em um algoritmo.

1. O que é KNN?

KNN significa K-Nearest Neighbors, ou K Vizinhos Mais Próximos. É um algoritmo de aprendizado supervisionado que prevê a resposta de um novo exemplo observando os exemplos de treino mais próximos dele.

O valor de k indica quantos vizinhos entram na decisão. Se usamos k = 3, por exemplo, o algoritmo consulta os três exemplos mais próximos.

  • Classificação: cada vizinho vota em uma classe e vence a mais votada.
  • Regressão: a previsão costuma ser a média dos valores dos vizinhos.

Ao contrário de uma regressão linear ou de uma rede neural, o KNN não ajusta uma equação durante o treinamento. Ele guarda os dados e faz a maior parte do trabalho quando recebe um novo exemplo. Por isso, é conhecido como um método baseado em instâncias.

Isso faz com que o “treinamento” seja muito simples: em essência, precisamos armazenar os exemplos. O custo aparece depois, na hora da previsão, quando o algoritmo precisa comparar o novo ponto com os dados conhecidos. Em conjuntos pequenos isso raramente é um problema, mas a diferença fica importante quando a base cresce muito.

Também vale perceber uma ideia central do modelo: o KNN parte da hipótese de que pontos próximos tendem a ter respostas parecidas. Se essa hipótese fizer sentido para o problema, o método pode funcionar surpreendentemente bem mesmo sendo simples.

Não confunda: KNN e K-Means são algoritmos diferentes. KNN utiliza respostas conhecidas e faz previsões; K-Means procura grupos em dados sem rótulos.

2. Como o algoritmo funciona?

Para prever a resposta de um ponto novo, o KNN segue quatro etapas:

  • Calcula a distância entre o novo ponto e cada exemplo de treino;
  • Ordena os exemplos da menor para a maior distância;
  • Seleciona os k primeiros;
  • Combina as respostas desses vizinhos.

A medida mais comum é a distância Euclidiana. Para dois pontos com d features, ela é dada por:

d(𝐱,𝐳)=∑j=1d(xj−zj)2d(\mathbf{x},\mathbf{z})=\sqrt{\sum_{j=1}^{d}(x_j-z_j)^2}

Em duas dimensões, essa expressão é apenas o Teorema de Pitágoras. Também existem outras medidas, como a distância Manhattan, que soma as diferenças absolutas entre as coordenadas. A escolha depende do tipo de dado e deve ser validada no problema real.

A métrica escolhida define, na prática, o que significa ser “parecido”. A distância Euclidiana mede o caminho direto entre dois pontos; a Manhattan mede quanto precisaríamos percorrer seguindo cada eixo separadamente. Em alguns conjuntos elas produzem os mesmos vizinhos, mas isso não é garantido. Por esse motivo, a métrica também pode ser tratada como uma escolha do modelo e comparada durante a validação.

3. Um exemplo calculado à mão

Na figura abaixo, temos seis pontos divididos entre as classes Azul e Laranja. Queremos classificar o ponto Q = (4, 3) usando distância Euclidiana e k = 3.

Os pontos azuis são A = (1, 1), B = (2, 3) e C = (3, 2). Os pontos laranjas são D = (5, 3), E = (6, 5) e F = (7, 7). Assim, o exemplo pode ser conferido mesmo sem depender da figura.

Figura 1. Os três vizinhos mais próximos de Q são D, C e B.

Veja o KNN em ação:

Use o gráfico abaixo para mover o ponto Q, alterar o valor de k e comparar as distâncias Euclidiana e Manhattan. Observe que uma pequena mudança pode trocar os vizinhos e, com isso, a previsão.

Classe Azul Classe Laranja Novo ponto Q
Previsão:

Arraste os controles ou clique no gráfico para mover Q. Círculos representam a classe Azul; losangos, a classe Laranja.

Um bom teste é colocar Q perto da região entre as duas classes e variar os controles. Longe da fronteira, a decisão costuma permanecer estável. Perto dela, trocar a posição de Q, a distância ou o número de vizinhos pode alterar o resultado.

As três menores distâncias são:

  • D, da classe Laranja: distância 1;
  • C, da classe Azul: distância √2 ≈ 1,41;
  • B, da classe Azul: distância 2.

A classe Azul recebe dois votos e a Laranja recebe um. Logo, o KNN classifica Q como Azul.

Se estivéssemos fazendo regressão, não haveria votação. Suponha que os três imóveis mais próximos custem R$ 300 mil, R$ 320 mil e R$ 340 mil. A previsão seria a média:

y^=300+320+3403=320 mil reais\hat{y}=\frac{300+320+340}{3}=320\text{ mil reais}

4. Como escolher o valor de k?

O valor de k controla o quanto o modelo reage aos detalhes dos dados. Com k = 1, uma única amostra ruidosa pode mudar a previsão. Com um valor muito alto, vizinhos distantes começam a participar e padrões locais podem desaparecer.

Uma forma intuitiva de pensar nisso é imaginar o tamanho da “vizinhança” consultada pelo algoritmo. Valores pequenos de k dão muita importância ao que acontece imediatamente ao redor do ponto. Valores maiores buscam uma espécie de consenso em uma região mais ampla. O objetivo é encontrar um meio-termo: nem reagir a cada exceção do conjunto de treino, nem suavizar tanto a ponto de ignorar estruturas úteis.

Figura 2. Valores pequenos de k geram fronteiras mais irregulares; valores grandes deixam a decisão mais suave.

Explore a fronteira de decisão

Arraste o controle de k no gráfico interativo. O fundo mostra a classe prevista em cada região do plano.

Classe Azul Classe Laranja

Não existe um valor de k que seja sempre o melhor. Na prática, testamos algumas opções usando validação cruzada. O conjunto de teste deve ficar separado para a avaliação final, e não para escolher o modelo.

Em classificação binária, usar um valor ímpar reduz a chance de empate na votação. Ainda assim, é importante definir como o algoritmo deve agir caso duas classes recebam o mesmo número de votos.

Também podemos dar mais importância aos vizinhos que estão realmente próximos. No Scikit-learn, por exemplo, weights="distance" faz com que vizinhos mais próximos tenham maior influência na decisão. Essa configuração também deve ser avaliada durante a validação.

5. A importância da escala

Como o KNN depende diretamente de distâncias, a escala das features importa bastante. Imagine um conjunto de dados com idade, variando de 15 a 80 anos, e renda anual, variando de 10.000 a 500.000 reais. Sem nenhum tratamento, a renda terá uma influência muito maior na distância simplesmente porque seus valores numéricos são maiores.

Figura 3. Depois da padronização, as duas features passam a contribuir de maneira mais equilibrada para a distância.

Uma solução comum é a padronização. O StandardScaler, por exemplo, transforma cada feature levando em consideração sua média e seu desvio-padrão:

z=x−μσz=\frac{x-\mu}{\sigma}

O scaler deve ser ajustado somente com os dados de treino. Se utilizarmos informações do conjunto de teste nessa etapa, ocorre o chamado vazamento de dados: o modelo acaba tendo acesso a informações que deveria conhecer apenas no momento da avaliação.

Padronizar também não significa que todas as features passam a ser igualmente úteis. Uma variável irrelevante ainda pode atrapalhar o KNN. A padronização apenas evita que uma feature domine a distância simplesmente porque seus números são maiores.

6. Quando o KNN é uma boa escolha?

O KNN costuma funcionar bem em conjuntos pequenos ou médios, principalmente quando exemplos parecidos realmente tendem a ter respostas parecidas. Também é um ótimo modelo de referência: é simples de entender e consegue representar relações não lineares.

Por outro lado, o algoritmo precisa guardar os dados de treino e pode ficar lento quando o conjunto cresce muito. Features irrelevantes também prejudicam o resultado, pois entram diretamente no cálculo das distâncias.

Outro problema aparece quando temos muitas features. Em espaços com muitas dimensões, as distâncias entre os pontos tendem a se tornar menos informativas e a ideia de “vizinho próximo” perde parte de seu significado. Esse fenômeno é conhecido como maldição da dimensionalidade.

7. Conclusão

O KNN parte de uma ideia bastante simples: procurar exemplos semelhantes antes de tomar uma decisão. Para utilizá-lo bem, porém, precisamos escolher uma distância coerente, tratar a escala das features e selecionar o valor de k de forma adequada.

Apesar da simplicidade, estudar o KNN permite entender vários conceitos fundamentais de Machine Learning. É um ótimo ponto de partida antes de avançar para modelos mais sofisticados.

Referências

  1. COVER, T. M.; HART, P. E. Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 1967.
  2. SCIKIT-LEARN DEVELOPERS. Nearest Neighbors — User Guide
  3. SCIKIT-LEARN DEVELOPERS. StandardScaler — Documentation
  4. JAMES, G.; WITTEN, D.; HASTIE, T.; TIBSHIRANI, R. An Introduction to Statistical Learning. 2. ed. Springer, 2021.