K-Vizinhos Mais Próximos (KNN)

Visão geral

k-Vizinhos Mais Próximos (k-Nearest Neighbors, k-NN ou KNN) é um método simples, não paramétrico (non-parametric) e baseado em instâncias (instance-based) usado para classificação (classification) e regressão (regression). Em vez de aprender um modelo paramétrico explícito durante o treinamento, o KNN em grande parte armazena os exemplos de treinamento e faz previsões consultando os k mais semelhantes pontos de treinamento para um novo ponto de consulta, onde a semelhança é tipicamente definida por meio de uma métrica de distância (distance metric).

O KNN costuma ser uma boa linha de base (baseline) e um modelo útil de “verificação de sanidade (sanity check)” — especialmente quando você suspeita que a fronteira de decisão (decision boundary) é irregular e não quer assumir uma forma linear (linear form) (como em Regressão Linear/Logística).

Intuição: “Você é como seus vizinhos”

Dada uma nova entrada (x):

  1. Calcule as distâncias de (x) para todos os pontos de treinamento ({(x_i, y_i)}_{i=1}^n).
  2. Selecione o conjunto (N_k(x)) dos k mais próximos pontos de treinamento.
  3. Prediga com base em seus rótulos/alvos:
    • Classificação: votação majoritária (opcionalmente ponderada pela distância)
    • Regressão: média (ou mediana) de seus valores-alvo (opcionalmente ponderada)

O KNN às vezes é chamado de aprendiz preguiçoso (lazy learner): o “treinamento” é barato, mas a predição pode ser cara porque depende da busca de vizinhos no momento da consulta.

Classificação com KNN

Regra básica (votação majoritária)

Para classificação com classes (c \in {1,\dots,C}), uma regra de predição comum é:

[ \hat{y}(x) = \arg\max_{c} \sum_{i \in N_k(x)} \mathbf{1}[y_i = c] ]

Isso produz uma fronteira de decisão por partes (piecewise) que se adapta à estrutura local dos dados. Se os rótulos de classe forem limpos e a métrica corresponder à noção de similaridade, o KNN pode aproximar fronteiras complexas sem ajustar parâmetros explicitamente.

Votação ponderada pela distância

Uma variante comum dá mais influência aos vizinhos mais próximos:

[ \hat{y}(x) = \arg\max_{c} \sum_{i \in N_k(x)} w_i ,\mathbf{1}[y_i=c] \quad\text{with}\quad w_i = \frac{1}{d(x,x_i)+\epsilon} ]

A ponderação por distância pode ajudar quando o vizinho mais próximo está muito mais perto do que os demais.

Saídas probabilísticas

Muitas implementações também estimam probabilidades de classe como a fração (ou fração ponderada) de vizinhos em cada classe. Isso pode ser útil para decisões por limiar e para avaliação com métricas sensíveis à calibração.

Regressão com KNN

Para regressão, o KNN prediz um valor numérico agregando alvos próximos:

Média (sem ponderação)

[ \hat{y}(x) = \frac{1}{k}\sum_{i \in N_k(x)} y_i ]

Média ponderada

[ \hat{y}(x) = \frac{\sum_{i \in N_k(x)} w_i y_i}{\sum_{i \in N_k(x)} w_i} ]

A regressão com KNN está intimamente relacionada à média local (local averaging) e pode ser vista como uma forma de suavização não paramétrica (nonparametric smoothing) (conceitualmente semelhante à regressão por kernel; veja também Métodos de Kernel para um contexto mais amplo).

Escolhendo **k**: compromisso viés–variância (bias–variance tradeoff)

O hiperparâmetro (hyperparameter) k controla a suavidade do modelo:

  • k pequeno (por exemplo, k=1–5)
    • Baixo viés, alta variância
    • Pode ajustar ruído; sensível a valores atípicos
    • A fronteira de decisão pode ser serrilhada
  • k grande (por exemplo, k=50, 100, …)
    • Maior viés, menor variância
    • Pode “apagar” a estrutura local
    • Tende a prever a classe majoritária global (classificação) ou a média global (regressão)

Orientação prática

  • Use validação cruzada (cross-validation) para escolher k com base na sua métrica de avaliação.
  • Considere usar k ímpar em classificação binária para reduzir empates (embora empates ainda possam ocorrer).
  • Em conjuntos de dados desbalanceados, ajustar apenas k pode não resolver o problema; considere estratégias de ponderação e amostragem (veja “Desbalanceamento de classes” abaixo).

Nota teórica (consistência)

Sob condições brandas (e com (k \to \infty) mas (k/n \to 0) quando (n \to \infty)), a classificação com KNN é universalmente consistente (universally consistent): seu erro se aproxima do erro ótimo de Bayes. Na prática, o comportamento em amostras finitas depende fortemente da métrica, do ruído e da dimensionalidade.

Métricas de distância: o que significa “mais próximo”?

O KNN depende criticamente da distância (ou similaridade) escolhida. As escolhas comuns incluem:

Euclidiana (L2)

[ d(x, x') = \sqrt{\sum_{j=1}^d (x_j-x'_j)^2} ]

Padrão em muitos cenários; funciona bem quando os atributos são contínuos e têm escalas semelhantes.

Manhattan (L1)

[ d(x, x') = \sum_{j=1}^d |x_j-x'_j| ]

Mais robusta a desvios grandes individuais e, às vezes, melhor em alta dimensão do que L2.

Minkowski

Generalização que inclui L1 e L2:

[ d_p(x, x') = \left(\sum_{j=1}^d |x_j-x'_j|^p \right)^{1/p} ]

Distância do cosseno (cosine distance) (comum para texto/representações vetoriais)

Frequentemente usada para vetores esparsos de alta dimensão (por exemplo, TF-IDF) ou representações vetoriais (embeddings) aprendidas:

[ \text{cosine_sim}(x,x')=\frac{x\cdot x'}{|x||x'|} ]

A distância do cosseno é tipicamente (1-\text{cosine_sim}).

Hamming (binário/categórico codificado)

Conta as posições que diferem; útil para vetores de bits ou codificações one-hot (com ressalvas).

Mahalanobis (sensível à correlação)

Considera a covariância dos atributos:

[ d_M(x,x') = \sqrt{(x-x')^\top \Sigma^{-1}(x-x')} ]

Isso se conecta ao aprendizado de métricas (metric learning); veja Aprendizado de Métricas para abordagens que aprendem distâncias/representações vetoriais para que os vizinhos sejam semanticamente significativos.

Escalonamento de atributos (feature scaling): essencial para métodos baseados em distância

Como as distâncias combinam diferenças atributo a atributo, a escala domina. Se um atributo varia de 0–100000 enquanto outro varia de 0–1, o atributo de grande escala vai sobrepujar as distâncias Euclidiana/Manhattan.

Abordagens padrão

  • Padronização (standardization) (z-score): subtrair a média, dividir pelo desvio padrão
  • Escalonamento min–max (min-max scaling): mapear para ([0,1])
  • Escalonamento robusto (robust scaling): usar mediana/IQR quando há muitos valores atípicos

Armadilha comum: vazamento de dados (data leakage)

Ajuste o escalonador apenas nos dados de treinamento, e então aplique aos dados de validação/teste. Vazamento de estatísticas do teste no escalonamento pode inflar o desempenho.

Exemplo prático (pipeline do scikit-learn)

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import GridSearchCV

pipe = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier())
])

param_grid = {
    "knn__n_neighbors": [3, 5, 11, 21, 41],
    "knn__weights": ["uniform", "distance"],
    "knn__metric": ["minkowski"],   # default p=2 is Euclidean
    "knn__p": [1, 2],               # Manhattan vs Euclidean
}

search = GridSearchCV(pipe, param_grid, cv=5, scoring="accuracy")
search.fit(X_train, y_train)

print(search.best_params_)
print("CV accuracy:", search.best_score_)
print("Test accuracy:", search.score(X_test, y_test))

Usar um pipeline garante que o escalonamento seja feito corretamente dentro de cada divisão da validação cruzada.

Complexidade computacional (computational complexity) e aceleração (acceleration)

Complexidade ingênua

Para cada ponto de consulta:

  • Calcular distâncias para (n) pontos de treinamento em (d) dimensões: (O(nd))
  • Selecionar as k menores distâncias: tipicamente (O(n)) com seleção parcial, ou (O(n \log n)) com ordenação completa
  • Memória: armazenar o conjunto de dados, (O(nd))

Isso pode ser caro para (n) grande ou (d) alto.

Estruturas de busca exata de vizinhos

Elas podem reduzir o tempo de consulta, especialmente em dimensões baixas a moderadas:

  • árvores k-d (k-d trees): eficientes para espaços Euclidianos de baixa dimensão; o desempenho piora conforme a dimensão cresce.
  • árvores de bolas (ball trees): particionam o espaço com hiperesferas; podem ajudar com certas distribuições e métricas.

Em muitas bibliotecas (incluindo scikit-learn), elas são usadas automaticamente dependendo das configurações e dos dados.

Vizinho mais próximo aproximado (approximate nearest neighbor, ANN)

Para aplicações em grande escala, métodos aproximados são frequentemente usados porque oferecem grandes ganhos de velocidade com perda mínima de acurácia:

  • hashing sensível à localidade (Locality-Sensitive Hashing, LSH): cria hashes de pontos de modo que pontos próximos colidam com maior probabilidade.
  • Métodos baseados em grafos como HNSW (Hierarchical Navigable Small World graphs): muito populares para ANN rápida em espaços de representações vetoriais.
  • bancos de dados vetoriais (vector databases) comumente implementam busca ANN para recuperação e recomendação.

ANN é especialmente relevante quando o KNN é aplicado a representações vetoriais vindas de modelos profundos (por exemplo, busca semântica), onde a busca exata é lenta demais.

Aplicações práticas

1) Linha de base para classificação tabular

O KNN pode ser uma linha de base competitiva em conjuntos de dados tabulares pequenos/médios, especialmente quando:

  • as fronteiras de decisão são não lineares
  • você tem densidade de dados suficiente para que vizinhanças locais sejam significativas
  • os atributos podem ser escalonados e as distâncias fazem sentido

No entanto, para muitos problemas tabulares, Árvores de Decisão e Ensembles frequentemente superam o KNN com menor sensibilidade ao escalonamento.

2) Recomendação e recuperação por similaridade

A busca de vizinhos no estilo KNN é um padrão central em:

  • “usuários semelhantes a você” (filtragem colaborativa baseada em usuários)
  • “itens semelhantes a este item” (similaridade item-item)
  • recuperação por vizinho mais próximo sobre representações vetoriais (busca semântica)

Isso se sobrepõe conceitualmente a Sistemas de Recomendação.

3) Detecção de anomalias (anomaly detection) (baseada em distância)

Pontos distantes de seus vizinhos podem ser anomalias. Um método simples é pontuar um ponto por:

  • distância até seu k-ésimo vizinho mais próximo, ou
  • distância média até k vizinhos

Veja Detecção de Anomalias para estratégias mais amplas.

Armadilhas comuns e modos de falha

Dados de alta dimensionalidade (a “maldição da dimensionalidade (curse of dimensionality)”)

Em alta dimensão:

  • As distâncias tendem a se concentrar: vizinhos mais próximos e mais distantes podem ficar com distâncias semelhantes.
  • As vizinhanças se tornam menos significativas a menos que você tenha uma quantidade enorme de dados.
  • O KNN pode degradar significativamente com atributos brutos de alta dimensão.

Mitigações

  • Use Redução de Dimensionalidade (por exemplo, Análise de Componentes Principais (PCA) para atributos numéricos densos).
  • Use seleção de atributos (feature selection) para remover atributos irrelevantes/ruidosos.
  • Use representações vetoriais de um modelo de representação e, então, aplique KNN no espaço dessas representações (frequentemente combinado com busca ANN).
  • Considere modelos que lidam melhor com estrutura de alta dimensão (por exemplo, modelos lineares com regularização, SVMs ou aprendizado profundo dependendo do contexto).

Desbalanceamento de classes (class imbalance)

Em classificação desbalanceada, a votação majoritária pode enviesar fortemente para a classe majoritária.

Sintomas

  • Alta acurácia, mas baixa revocação (recall) na classe minoritária
  • Probabilidades previstas enviesadas para a maioria

Mitigações

  • Use votação ponderada pela distância (weights="distance").
  • Use ideias de vizinhança condicionada por classe (por exemplo, k diferente por classe) ou ajuste limiares de decisão usando probabilidades.
  • Rebalanceie os dados de treinamento (sobreamostragem/subamostragem) e avalie com métricas apropriadas (por exemplo, F1, ROC-AUC, PR-AUC).

Atributos irrelevantes e tipos de dados mistos

O KNN pode sofrer se:

  • alguns atributos forem irrelevantes, mas escalonados de forma semelhante (eles adicionam ruído à distância)
  • variáveis categóricas forem codificadas de forma inadequada (por exemplo, inteiros arbitrários implicam uma ordenação falsa)

Mitigações

  • Pré-processamento cuidadoso: codificação one-hot (com atenção à esparsidade), ponderação de atributos informada pelo domínio, ou representações vetoriais aprendidas para categorias.
  • Considere funções de distância projetadas para tipos mistos (mais comuns em bibliotecas especializadas).

Valores atípicos e rótulos ruidosos

Com k pequeno, um único ponto rotulado incorretamente pode inverter previsões localmente. Com k grande, o ruído é “médio”, mas a estrutura local pode ser perdida.

Mitigações

  • Aumente k moderadamente
  • Use ponderação por distância
  • Limpe rótulos/valores atípicos se possível

Mudança de distribuição entre treino/teste

O KNN assume que pontos “próximos” no conjunto de treinamento refletem vizinhanças no momento do teste. Com mudança (escalonamento diferente, novas regiões do espaço de atributos), o KNN pode falhar severamente.

Variantes e extensões

KNN ponderado (weighted KNN)

Já cobrimos votação/média ponderadas pela distância; você também pode ponderar atributos ou usar métricas aprendidas.

Vizinhos por raio (radius neighbors)

Em vez de k fixo, inclua todos os pontos dentro de um raio (r). Isso pode adaptar o tamanho da vizinhança, mas pode produzir vizinhanças vazias em regiões esparsas.

Aprendizado de métricas + KNN

Um padrão moderno comum é:

  1. aprender uma representação (representação vetorial) onde exemplos similares ficam próximos
  2. executar KNN nesse espaço

Isso é central em muitos sistemas de recuperação e está intimamente relacionado a Aprendizado de Métricas.

Checklist de implementação (prático)

  • Escolha uma métrica de distância sensata para o seu tipo de dado.
  • Sempre aplique escalonamento de atributos para distâncias L1/L2/Minkowski.
  • Ajuste:
    • n_neighbors (k)
    • weights (uniforme vs distância)
    • parâmetros da métrica (por exemplo, p para Minkowski)
  • Use validação cruzada e métricas apropriadas para o seu problema (especialmente sob desbalanceamento).
  • Considere busca aproximada de vizinhos se (n) for grande.
  • Tenha cautela em alta dimensão; considere representações vetoriais ou Redução de Dimensionalidade.

Resumo

O KNN é um método conceitualmente direto: predizer a partir dos rótulos/valores de pontos de treinamento próximos. Seus pontos fortes são simplicidade, flexibilidade e bom desempenho em alguns problemas de baixa a moderada dimensionalidade com bom escalonamento de atributos e uma métrica de distância significativa. Suas fraquezas são computação lenta no tempo de consulta (a menos que seja acelerado), sensibilidade ao pré-processamento e à escolha da métrica, e comportamento degradado em alta dimensionalidade e em cenários desbalanceados.

Quando usado de forma criteriosa — frequentemente com escalonamento, seleção de métrica e aceleração — o KNN continua sendo uma linha de base importante, um componente útil em pipelines de recuperação/recomendação e uma porta de entrada para ideias mais avançadas como representações vetoriais aprendidas e busca de vizinhos mais próximos aproximada.