Ir para o conteúdo

k-Vizinhos Mais Próximos

O k-NN (Fix & Hodges, 1951; Cover & Hart, 1967) é o classificador mais intuitivo que existe: para classificar um ponto novo, olhe para os \(k\) pontos conhecidos mais parecidos e faça uma votação. Sem equações a ajustar, sem laço de treino — o "modelo" é os dados de treino.

O algoritmo

Para prever para um ponto de consulta \(x\):

  1. calcule a distância de \(x\) a todo ponto de treino;
  2. pegue os \(k\) mais próximos;
  3. classificação: preveja a classe majoritária entre eles (opcionalmente dando mais peso aos vizinhos mais próximos); regressão: preveja a média (ponderada) deles.
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

knn = make_pipeline(StandardScaler(),                 # distâncias precisam de escalonamento!
                    KNeighborsClassifier(n_neighbors=5))
knn.fit(X_train, y_train)

O k-NN é um aprendiz preguiçoso (baseado em instâncias): o fit apenas armazena os dados. Todo o trabalho acontece no momento da previsão — o perfil de custo oposto ao da maioria dos modelos (lento para prever, instantâneo para "treinar").

Métricas de distância

A noção de "parecido" é uma escolha de modelagem. Para a família de Minkowski,

\[ d_p(a, b) = \Big( \sum_{j=1}^{d} \lvert a_j - b_j \rvert^p \Big)^{1/p} \]
  • \(p = 2\): euclidiana — distância em linha reta, o padrão;
  • \(p = 1\): Manhattan — soma das diferenças de coordenadas; menos dominada por um único atributo de grande diferença;
  • similaridade de cosseno para vetores de texto/embedding (Representação de Texto); Hamming para vetores binários.

Escalone primeiro — sempre

As distâncias são dominadas por atributos com grandes faixas: renda (milhares) esmaga idade (dezenas). k-NN sem padronização é um bug, não um modelo. Da mesma forma, aplique one-hot em categorias nominais — categorias codificadas como inteiros criam distâncias fictícias.

Escolhendo k: viés–variância em sua forma mais pura

O \(k\) é o botão de complexidade, e ele mapeia perfeitamente no trade-off viés–variância — apenas invertido (\(k\) pequeno = modelo complexo):

Fronteiras de decisão do k-NN para k = 1, 15, 100

  • \(k = 1\): cada ponto de treino governa sua própria ilha — fronteira irregular, ruído memorizado, erro de treino zero, variância alta (sobreajuste);
  • \(k = 15\): fronteira suave seguindo a estrutura verdadeira — o ponto ideal aqui;
  • \(k = 100\) (metade do conjunto): a votação é engolida pela maioria global — viés alto (subajuste); em \(k = n\) toda previsão é a classe majoritária.

Escolha \(k\) por validação cruzada; valores ímpares evitam empates em problemas binários. Bons valores típicos crescem aproximadamente como \(\sqrt{n}\), mas valide em vez de confiar em regras de bolso.

Brinque você mesmo com a votação — arraste o ponto de consulta para a zona de sobreposição e observe o k pequeno oscilar enquanto o k grande permanece estável:

A maldição da dimensionalidade, revisitada

A premissa do k-NN — perto significa parecido — se degrada conforme as dimensões crescem (Redução de Dimensionalidade):

  • o volume cresce exponencialmente: com dados uniformes, cobrir 10% das amostras em \(d=100\) dimensões exige uma vizinhança abrangendo ~98% de cada eixo — os vizinhos "mais próximos" não estão próximos;
  • as distâncias par a par se concentram: a razão entre o vizinho mais distante e o mais próximo tende a 1, então a votação fica arbitrária;
  • atributos irrelevantes adicionam puro ruído à distância.

Remédios: seleção de atributos, PCA/UMAP antes do k-NN, ou aprendizado de métrica. Regra de bolso: o k-NN brilha em dimensões baixas a moderadas com muitos dados.

Perfil prático
Pontos fortes tempo de treino zero; naturalmente multiclasse; fronteiras não lineares de graça; um hiperparâmetro intuitivo; uma baseline forte
Fraquezas a previsão é \(O(n \cdot d)\) por consulta (mitigada por KD-trees/ball trees em baixas dimensões, NN aproximado — FAISS, HNSW — em escala); memória = conjunto inteiro; sensível a escalonamento, atributos irrelevantes e alta dimensionalidade
Usos clássicos candidatos de recomendação ("usuários como você"), recuperação de imagens, detecção de anomalias (distância ao k-ésimo vizinho), imputação (KNNImputer), busca semântica sobre embeddings

A operação "encontre os embeddings mais próximos" também é o coração dos bancos de dados vetoriais modernos que alimentam sistemas de LLM com recuperação aumentada (RAG) (A Fronteira) — ideias dos anos 1950 servindo sistemas dos anos 2020.

Material de aula

Notebook da aula (em português)

Notebook prático usado em sala — Aula 14 — K-NN: abrir no Colab

Quiz