Skip to content
Voltar aos resultados

K-Nearest Neighbors

Proposto por
Cover, T.M. & Hart, P.E.
Ano
1967
Tipo
Instance-based (non-parametric) learning

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

K-Nearest Neighbors (KNN), formalizado por Cover e Hart em 1967, é um método não paramétrico e baseado em instâncias que classifica ou prevê uma nova observação examinando os k exemplos mais próximos nos dados de treinamento.

Para classificação, ele utiliza um voto majoritário entre esses vizinhos; para regressão, ele calcula a média de seus valores.

A intuição por trás do método

A ideia é simples: entradas similares tendem a ter saídas similares. Para rotular um novo ponto, o KNN encontra o punhado de exemplos de treinamento que estão mais próximos dele no espaço de características e deixa que eles decidam. Nenhuma equação é ajustada antecipadamente — os próprios dados de treinamento constituem o modelo, e uma previsão só é feita quando um novo ponto chega.

História

A classificação de padrões por vizinhos mais próximos recebeu sua base estatística formal por Thomas Cover e Peter Hart em seu artigo de 1967 na IEEE Transactions on Information Theory, que analisou a taxa de erro da regra do vizinho mais próximo. O KNN tornou-se um dos métodos de aprendizado baseados em instâncias mais antigos e duradouros e permanece um classificador de linha de base padrão.

Quando usar

Use o KNN para classificação ou previsão em dados tabulares com características contínuas, binárias ou ordinais e pelo menos cerca de 30 observações. Ele não assume nenhuma distribuição particular, mas exige que as características sejam normalizadas e que o número de características permaneça pequeno em relação ao tamanho da amostra (p muito menor que n é preferível). Em amostras pequenas ou de alta dimensionalidade, a maldição da dimensionalidade domina — as distâncias entre vizinhos tornam-se informativas — e um modelo paramétrico como regressão logística ou Naive Bayes é a melhor escolha.

Limitações e considerações

  • Sensível à escala das características; sem padronização, características de grande escala dominam a distância.
  • Degrada rapidamente em altas dimensões (maldição da dimensionalidade), onde as distâncias entre vizinhos perdem o significado.
  • Cada previsão requer a varredura de todo o conjunto de treinamento, o que é lento no tempo de previsão em grandes volumes de dados.
  • Requer pelo menos um tamanho de amostra moderado; em amostras pequenas, as distâncias dos vizinhos mais próximos não são significativas.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Conceitualmente simples e fácil de explicar: sem equação no tempo de treinamento, os dados são o modelo.
  • Não paramétrico — não faz suposições sobre a distribuição subjacente.
  • Lida naturalmente com problemas multiclasse e fronteiras de decisão complexas e não lineares.
  • Funciona tanto para classificação quanto para regressão com a mesma ideia básica.

Aplicações

  • Classificação de dados tabulares em duas ou mais categorias.
  • Previsão numérica (regressão) pela média dos exemplos mais próximos.
  • Uma linha de base simples e interpretável antes de tentar modelos mais complexos.
  • Reconhecimento de padrões onde a similaridade com exemplos conhecidos impulsiona a decisão.

Como funciona

Como funciona

1

Para uma nova observação, o KNN mede a distância até cada exemplo de treinamento, tipicamente usando a distância Euclidiana através das características. Como a distância é sensível à escala, as características devem ser padronizadas primeiro — caso contrário, uma variável medida em uma escala numérica grande dominaria o cálculo e distorceria quais vizinhos são considerados os mais próximos.

Fórmula
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}
2

Os k pontos de treinamento com as menores distâncias para a nova observação são selecionados como seus vizinhos. O valor de k controla o quão local é a decisão: um k pequeno segue os dados de perto, mas é sensível a ruídos, enquanto um k maior suaviza a fronteira. k deve ser escolhido por validação cruzada (por exemplo, o método do cotovelo) em vez de ser adivinhado.

3

Os vizinhos decidem a previsão: para classificação, o novo ponto assume a classe mais comum entre seus k vizinhos (um voto majoritário), e para regressão, ele assume a média de seus valores. Isso torna o método fácil de entender, mas cada previsão requer a varredura do conjunto de treinamento.

Fórmula
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}

Erros comuns

  • Omissão da padronização das características, de modo que uma variável de grande escala controla silenciosamente a distância.
  • Escolha de k manualmente em vez de selecioná-lo com validação cruzada.
  • Aplicação do KNN com muitas características e poucas observações, onde a razão dimensão/amostra o quebra.
  • Relato apenas de acurácia em vez de precisão, recall, F1 e uma matriz de confusão.

Perguntas frequentes

Como devo escolher o valor de k?

k deve ser selecionado com validação cruzada em vez de ser adivinhado — por exemplo, tentando uma faixa de valores e usando o método do cotovelo para encontrar onde o erro para de melhorar. Um k pequeno segue os dados de perto, mas é sensível a ruídos, enquanto um k maior suaviza a fronteira de decisão.

Por que devo padronizar as características?

O KNN decide quem é o 'mais próximo' usando a distância, que é sensível à escala. Se uma característica estiver em uma escala numérica muito maior do que as outras, ela domina a distância e distorce o conjunto de vizinhos. A padronização das características (por exemplo, com um StandardScaler) é necessária para que cada característica contribua de forma justa.

Por que o KNN tem dificuldades com muitas características?

Em espaços de alta dimensionalidade, todos os pontos ficam aproximadamente equidistantes — a maldição da dimensionalidade — de modo que os vizinhos 'mais próximos' não estão mais significativamente próximos. O desempenho do KNN cai rapidamente, e um modelo paramétrico como Naive Bayes ou regressão logística é geralmente preferível. Manter p muito menor que n ajuda.

Existe uma etapa de treinamento?

Não no sentido usual. O KNN é baseado em instâncias (preguiçoso): ele simplesmente armazena os dados de treinamento e faz todo o trabalho no tempo de previsão, quando calcula distâncias para encontrar os vizinhos mais próximos de um novo ponto.

Métodos relacionados

Fontes

  1. Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.

    Abrir referência DOI
    Copiado.