O algoritmo dos k-vizinhos mais próximos (k-NN) é um método de aprendizado não paramétrico, baseado em instâncias, usado para classificação e regressão. Em ambos os casos, a entrada consiste nos k exemplos de treinamento mais próximos em um espaço de características. A saída depende se o k-NN é usado para classificação ou regressão: na classificação, a saída é uma associação a uma classe, determinada por votação majoritária entre os k vizinhos mais próximos; na regressão, a saída é a média (ou média ponderada) dos valores dos k vizinhos mais próximos. O k-NN é um tipo de aprendizado preguiçoso, onde a função é apenas aproximada localmente, e todo o cálculo é adiado até a avaliação da função. Por depender de cálculos de distância, o algoritmo é sensível à estrutura local dos dados e à escolha da métrica de distância.
O algoritmo foi desenvolvido pela primeira vez em 1951 por Evelyn Fix e Joseph Hodges na Escola de Medicina da Aviação da Força Aérea dos EUA, originalmente como uma técnica de classificação não paramétrica. Foi posteriormente expandido e formalizado por Thomas Cover e Peter Hart em 1967, que estabeleceram seus limites de erro assintóticos. Desde então, o k-NN se tornou uma ferramenta fundamental em aprendizado de máquina, reconhecimento de padrões e mineração de dados, frequentemente usado como referência para modelos mais complexos.
Como Funciona
Dado um ponto de consulta, o algoritmo calcula a distância (tipicamente euclidiana, de Manhattan ou de Minkowski) para cada exemplo de treinamento. Em seguida, seleciona os k exemplos de treinamento com as menores distâncias. Para classificação, o rótulo previsto é o mais frequente entre esses k vizinhos. Para regressão, o valor previsto é a média dos valores alvo dos vizinhos. A escolha de k é crítica: um k pequeno (por exemplo, 1) leva a alta variância e sensibilidade a ruído, enquanto um k grande pode suavizar padrões locais, aumentando o viés. A prática comum é selecionar k por validação cruzada, frequentemente usando valores ímpares para classificação binária a fim de evitar empates.
O algoritmo também requer uma métrica de distância. A distância euclidiana é padrão para características contínuas, mas para dados de alta dimensão ou categóricos, outras métricas como distância de Hamming ou similaridade de cosseno podem ser usadas. A escala de características (por exemplo, normalização ou padronização) é essencial porque características com intervalos maiores dominam o cálculo de distância.
Propriedades e Variantes
O k-NN é não paramétrico, o que significa que não faz suposições fortes sobre a distribuição subjacente dos dados. Também é baseado em instâncias, armazenando todo o conjunto de treinamento e usando-o diretamente no momento da previsão. Isso torna o treinamento trivial (essencialmente apenas armazenar dados), mas a previsão computacionalmente cara, com complexidade de tempo O(nd) por consulta, onde n é o número de amostras de treinamento e d é o número de características.
Várias variantes abordam essas limitações. O k-NN ponderado atribui maior influência aos vizinhos mais próximos, frequentemente usando pesos de distância inversa. A regressão localmente ponderada ajusta um modelo linear dentro da vizinhança. Para grandes conjuntos de dados, técnicas de busca aproximada de vizinhos mais próximos, como árvores k-d, árvores de bola ou hashing sensível à localidade, reduzem o custo de busca. Em altas dimensões, a maldição da dimensionalidade degrada o desempenho, pois as distâncias se tornam menos discriminativas; redução de dimensionalidade ou seleção de características é frequentemente aplicada.
Aplicações
O algoritmo é amplamente usado em campos como visão computacional para classificação de imagens, processamento de linguagem natural para categorização de texto e bioinformática para análise de expressão gênica. Aparece em sistemas de recomendação, onde encontra usuários ou itens com preferências semelhantes. Em finanças, é usado para pontuação de crédito e detecção de fraude. Sua simplicidade e interpretabilidade o tornam uma primeira escolha comum para análise exploratória e como referência contra modelos mais complexos como redes neurais.
Pontos Fortes e Limitações
Os principais pontos fortes do k-NN são sua simplicidade, facilidade de implementação e eficácia em conjuntos de dados pequenos a médios com dimensionalidade baixa a moderada. Não requer fase de treinamento, tornando-o adequado para aprendizado incremental. No entanto, suas limitações incluem alto uso de memória (armazenando todos os dados de treinamento), tempo de previsão lento, sensibilidade a características irrelevantes e ruído, e desempenho ruim em espaços de alta dimensão. Também assume que todas as características são igualmente importantes, o que raramente é verdade na prática.
Relação com Outros Métodos
O k-NN é frequentemente comparado a outros métodos não paramétricos como árvores de decisão e máquinas de vetores de suporte. É uma técnica fundamental em aprendizado de máquina e é frequentemente ensinada junto com currículos de inteligência artificial. Seus princípios sustentam métodos mais avançados, como técnicas de aumento de dados que geram vizinhos sintéticos, e é usado em aprendizado curricular como uma forma de ordenar exemplos de treinamento por dificuldade. Na prática moderna, o k-NN às vezes é usado como camada final em modelos de aprendizado profundo para aprendizado de métricas, onde embeddings aprendidos são comparados usando busca de vizinhos mais próximos.
Ver Também
Referências
- Cover, T., & Hart, P. (1967). Nearest neighbor pattern classification. IEEE Transactions on Information Theory.
- Fix, E., & Hodges, J. L. (1951). Discriminatory analysis, nonparametric discrimination: consistency properties. USAF School of Aviation Medicine.
- Altman, N. S. (1992). An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician.