K-Nearest Neighbors (KNN)

K-vizinhos mais próximos (KNN) é um algoritmo de aprendizado supervisionado que prevê o rótulo de um novo exemplo com base nos k exemplos rotulados mais próximos: uma votação majoritária entre esses vizinhos para classificação ou a média deles para regressão. O KNN é não paramétrico e "preguiçoso": não aprende pesos, simplesmente armazena os dados de treinamento e só realiza todo o trabalho quando uma previsão é solicitada. Evelyn Fix e Joseph Hodges apresentaram o método em 1951 e, em 1967, Thomas Cover e Peter Hart provaram que, com dados ilimitados, a regra do vizinho mais próximo tem uma taxa de erro no máximo duas vezes maior que a do melhor classificador possível. A mesma busca por vizinhos mais próximos agora funciona em grande escala em bancos de dados vetoriais e sistemas de recuperação de imagens que comparam embeddings de redes neurais.

Como o KNN faz uma previsão#

Para cada ponto de consulta, o KNN executa três etapas:

1. Medir a distância: Calcula a distância entre a consulta e cada exemplo armazenado. A distância euclidiana é o padrão; as distâncias de Manhattan e Minkowski são alternativas comuns, e a similaridade de cosseno é padrão para embeddings, nos quais a direção de um vetor carrega seu significado.
2. Selecionar os vizinhos: Mantém os k exemplos com as menores distâncias.
3. Combinar os rótulos: Na classificação, escolhe a classe mais comum entre os vizinhos; na regressão, calcula a média dos valores. Com ponderação por distância (weights="distance" no scikit-learn), os vizinhos mais próximos têm mais peso.

Cada característica contribui para a distância, então características em escalas maiores predominam: a renda em dólares ofuscaria a idade em anos. Por isso, os pipelines de KNN padronizam as características primeiro ou comparam embeddings de um modelo de extração de características, para que cada dimensão contribua em uma escala comparável.

Escolha de k#

O valor de k define o equilíbrio entre sobreajuste e subajuste. Com k = 1, cada ponto de treinamento, inclusive os ruidosos e rotulados incorretamente, ocupa sua própria região, e a fronteira de decisão fica irregular. Com um k muito grande, cada votação alcança muito longe da consulta e apaga fronteiras reais entre classes. Para duas classes, um k ímpar evita empates, e a validação cruzada é a forma padrão de escolher k. No conjunto de dados ruidoso two-moons do scikit-learn, a compensação aparece em três valores:

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

Com k = 1, o classificador memoriza seus pontos de treinamento, obtendo 1.00 neles e 0.83 nos pontos reservados para teste. Com k = 15, obtém 0.90 e 0.89, o melhor resultado de teste entre os três; com k = 300, quase metade dos 700 pontos de treinamento, a fronteira fica tão suavizada que ambas as pontuações caem para 0.84 e 0.81.

Aceleração da busca por vizinhos#

Uma busca por força bruta compara a consulta com todos os n pontos armazenados em d dimensões, então cada previsão custa na ordem de n × d operações, e a memória cresce com o conjunto de dados. Estruturas de particionamento espacial, como árvores k-d e árvores ball, ignoram a maioria das comparações em poucas dimensões, e algorithm="auto" do scikit-learn escolhe entre força bruta, árvore k-d e árvore ball. Em dimensões elevadas, a maldição da dimensionalidade faz com que as distâncias entre pontos sejam quase iguais, a poda da árvore deixa de compensar e sistemas grandes passam a usar índices aproximados de vizinhos mais próximos (ANN), como grafos HNSW e índices de arquivo invertido (IVF) com quantização de produto, implementados em bibliotecas como FAISS. Esses índices retornam a maioria dos vizinhos mais próximos verdadeiros comparando a consulta com apenas uma pequena fração dos vetores armazenados:

KNN vs. métodos relacionados#

• Agrupamento k-means: Um algoritmo não supervisionado que agrupa pontos sem rótulo em k agrupamentos em torno de centroides aprendidos. Os nomes compartilham uma letra por coincidência: em k-means, k conta os agrupamentos.
• Busca vetorial: A forma de recuperação da mesma operação: retorna os itens armazenados mais próximos de um embedding de consulta, geralmente por meio de um índice aproximado, e a aplicação usa esses itens diretamente.
• Máquinas de vetores de suporte e regressão logística: Modelos paramétricos que aprendem uma fronteira de decisão durante o treinamento, de modo que o custo da previsão permanece constante à medida que o conjunto de treinamento cresce.

Aplicações no mundo real#

• Sistemas de recomendação: A filtragem colaborativa baseada em itens recomenda produtos cujos vetores de avaliações ou compras estejam mais próximos dos itens de que um usuário já gostou.
• Detecção de anomalias: A distância de um ponto até seu k-ésimo vizinho mais próximo serve como pontuação de anomalia, destacando transações ou leituras de sensores distantes de todos os exemplos normais.
• Imputação de valores ausentes: KNNImputer do scikit-learn preenche cada lacuna com a média daquela característica entre as k linhas mais semelhantes.
• Recuperação de imagens e reidentificação: Os sistemas comparam o embedding de uma imagem com uma galeria para encontrar o mesmo produto, rosto ou pessoa visto por outra câmera. A solução de busca por similaridade da Ultralytics gera embeddings de uma pasta de imagens com o CLIP da OpenAI, calcula a similaridade de cosseno entre cada imagem indexada e uma consulta de texto como "carro vermelho" por meio de uma busca exata por força bruta e retorna as mais próximas, até 30 por padrão.