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
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
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}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.
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
Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.
Abrir referência DOICopiado.