K-Nearest Neighbors (k-NN) é um algoritmo de aprendizado supervisionado não paramétrico usado tanto para classificação quanto para regressão. Na classificação, um novo ponto de dados recebe a classe mais comum entre seus k vizinhos mais próximos no espaço de características, determinada por uma métrica de distância. Na regressão, a saída é a média (ou média ponderada) dos valores desses vizinhos. O algoritmo é baseado em instâncias, o que significa que ele armazena todo o conjunto de dados de treinamento e realiza cálculos apenas quando uma previsão é necessária, adiando toda a generalização até o momento da consulta.
O método foi desenvolvido pela primeira vez por Evelyn Fix e Joseph Hodges em 1951 e posteriormente expandido por Thomas Cover. É um dos algoritmos de aprendizado de máquina mais simples, mas pode alcançar precisão competitiva em muitos domínios, especialmente quando a fronteira de decisão é irregular. Seu desempenho depende fortemente da escolha de k, da métrica de distância e da escala das características.
Desenvolvimento Histórico
As origens do k-NN remontam a 1951, quando Evelyn Fix e Joseph Hodges, trabalhando na Escola de Medicina da Força Aérea dos EUA, introduziram um método de classificação não paramétrico baseado em vizinhos mais próximos. Seu trabalho foi motivado pela necessidade de classificar observações sem assumir uma distribuição estatística específica. Em 1967, Thomas Cover e Peter Hart publicaram um artigo seminal que formalizou as propriedades do algoritmo, incluindo limites para sua taxa de erro em relação ao classificador ótimo de Bayes. Isso estabeleceu o k-NN como uma abordagem teoricamente fundamentada em reconhecimento de padrões. O algoritmo ganhou popularidade nas décadas de 1960 e 1970 com o avanço da computação, pois exigia tempo mínimo de treinamento, mas armazenamento substancial. Desenvolvimentos posteriores, como a introdução de votação ponderada e aprendizado de métrica de distância, abordaram algumas de suas limitações.
Visão Geral do Algoritmo
Na classificação k-NN, a entrada consiste em um conjunto de treinamento de exemplos rotulados, cada um representado como um vetor de características em um espaço multidimensional. O algoritmo armazena esses vetores e seus rótulos. Quando um ponto de consulta é apresentado, ele calcula a distância da consulta a todos os pontos de treinamento, seleciona os k mais próximos e atribui a classe que aparece com mais frequência entre eles. Para k=1, a consulta é simplesmente atribuída à classe de seu vizinho mais próximo. A escolha de k é crítica: um k pequeno pode levar a alta variância e sensibilidade a ruído, enquanto um k grande pode suavizar demais a fronteira de decisão e incluir pontos de outras classes.
Para regressão, a saída é a média dos valores alvo dos k vizinhos mais próximos. Isso é conhecido como suavização por vizinho mais próximo. Se k=1, torna-se interpolação por vizinho mais próximo, onde o valor previsto é exatamente o do ponto de treinamento mais próximo. Variantes ponderadas atribuem maior influência a vizinhos mais próximos, frequentemente usando pesos proporcionais ao inverso da distância (1/d).
Métricas de Distância e Escala de Características
A escolha da métrica de distância é crucial. Para características contínuas, a distância euclidiana é a mais comum. Para características discretas, como em classificação de texto, a distância de Hamming ou métricas de sobreposição são usadas. Em domínios especializados, como análise de expressão gênica, coeficientes de correlação (Pearson, Spearman) foram empregados. A dependência do algoritmo em distância significa que características com unidades ou escalas diferentes podem dominar o cálculo. Portanto, normalizar cada característica para uma escala comum (por exemplo, z-score ou min-max scaling) é essencial para garantir contribuição igual. Esse pré-processamento pode melhorar significativamente a precisão.
Propriedades Estatísticas
De uma perspectiva estatística, o k-NN é um método não paramétrico porque não assume uma forma funcional para a distribuição subjacente dos dados. Os dados de treinamento são assumidos como pares (X_i, Y_i), onde X_i é um vetor de características e Y_i é o rótulo da classe. Para um ponto de consulta x, os pontos de treinamento são reordenados por sua distância a x. A taxa de erro do algoritmo converge para a taxa de erro de Bayes à medida que o tamanho da amostra aumenta, desde que k cresça apropriadamente com n e k/n se aproxime de zero. Essa propriedade, estabelecida por Cover e Hart, torna o k-NN assintoticamente ótimo. No entanto, em amostras finitas, o algoritmo sofre da maldição da dimensionalidade: à medida que o número de características aumenta, o volume do espaço cresce exponencialmente e os pontos se tornam esparsos, tornando as medidas de distância menos significativas.
Vantagens e Desvantagens
Uma grande vantagem do k-NN é sua simplicidade e ausência de fase de treinamento. Ele pode ser atualizado facilmente adicionando novos pontos de dados. Também é eficaz para problemas multiclasse e pode capturar fronteiras de decisão complexas. No entanto, tem desvantagens notáveis. O tempo de previsão é lento porque requer calcular distâncias a todos os pontos de treinamento, tornando-o impraticável para grandes conjuntos de dados sem otimização (por exemplo, usando KD-trees ou ball trees). É sensível a características irrelevantes e dados ruidosos. O algoritmo também é sensível à estrutura local dos dados, o que significa que outliers ou distribuições de classes desbalanceadas podem distorcer os resultados. Em distribuições assimétricas, classes majoritárias dominam porque são mais propensas a aparecer entre os k vizinhos. Ponderar por distância inversa ou usar técnicas de abstração pode mitigar isso.
Variantes e Extensões
Várias variantes abordam as limitações do k-NN. O k-NN ponderado atribui pesos aos vizinhos com base na distância, de modo que pontos mais próximos tenham mais influência. Métodos de aprendizado de métrica de distância, como large margin nearest neighbor e neighborhood components analysis, aprendem uma métrica de distância personalizada para melhorar a precisão. O k-NN editado remove pontos de treinamento ruidosos ou mal classificados para melhorar a generalização. O k-NN condensado reduz o tamanho do conjunto de treinamento mantendo apenas pontos essenciais para a classificação. O k-NN localmente adaptativo ajusta k com base na densidade da região ao redor do ponto de consulta. Essas variantes foram aplicadas em campos como aprendizado de máquina e inteligência artificial para melhorar o desempenho.
Aplicações
O algoritmo k-NN é usado em vários domínios. Em reconhecimento de padrões, é aplicado à classificação de imagens e reconhecimento de escrita manual. Na medicina, é usado para diagnóstico com base em características do paciente. Em finanças, ajuda na pontuação de crédito e detecção de fraude. Em sistemas de recomendação, encontra usuários ou itens semelhantes. Em bioinformática, classifica dados de expressão gênica. Sua simplicidade o torna uma linha de base comum para comparar modelos mais complexos como rede neural e aprendizado profundo.
Relação com Outros Métodos
O k-NN é uma forma de aprendizado baseado em instâncias, distinto de abordagens baseadas em modelos como rede neural ou máquina de vetores de suporte que constroem um modelo explícito durante o treinamento. Também está relacionado à estimativa de densidade não paramétrica. No contexto mais amplo de aprendizado de máquina, o k-NN é frequentemente usado como referência. Influenciou o desenvolvimento de hashing sensível à localidade e busca aproximada de vizinhos mais próximos, usados em sistemas de grande escala. Embora métodos modernos como aprendizado profundo tenham superado o k-NN em muitas tarefas, o k-NN permanece valioso para pequenos conjuntos de dados e previsões interpretáveis.
Considerações Práticas
Ao implementar o k-NN, vários problemas práticos surgem. O valor de k é tipicamente escolhido via validação cruzada. Valores ímpares de k são frequentemente usados para evitar empates em classificação binária. A escala de características é essencial. Estruturas de dados eficientes como KD-trees podem acelerar a busca por vizinhos mais próximos, mas degradam em altas dimensões. Para conjuntos de dados muito grandes, métodos aproximados são necessários. O uso de memória do algoritmo é proporcional ao tamanho do conjunto de treinamento, o que pode ser uma limitação. Em aplicações modernas, o k-NN às vezes é combinado com outros algoritmos, como usá-lo como classificador final sobre embeddings aprendidos de uma rede neural.
Ver Também
- aprendizado de máquina
- inteligência artificial
- rede neural
- aprendizado profundo
- Stanford AI Lab
- MIT CSAIL
- Carnegie Mellon University
- BAIR (Berkeley AI Research)
- Xerox PARC
- Thomas G. Dietterich
- Michael I. Jordan
- Daphne Koller
- Anima Anandkumar
- Samy Bengio
- Joshua Tenenbaum
- Brendan Lake
- Melanie Mitchell
- Aaron Courville
- Alexei Efros
- Ali Rahimi