k-Vizinhos Mais Próximos (k-NN)

Do pré-processamento ao primeiro algoritmo

O k-NN é um bom primeiro algoritmo de ML porque depende, de forma direta, de quase tudo visto até aqui:

1. Precisa de variáveis numéricas e na mesma escala;
2. É sensível a outliers e a dados desbalanceados;
3. Sua eficácia se degrada com muitas dimensões.

flowchart LR
    A["Tipos e escala"] --> B["Pré-processamento"]
    B --> C["k-NN<br/>primeiro algoritmo"]
    C --> D["Escolha de k<br/>e distância"]
    D --> E["Modelo treinado<br/>e validado"]
    style C fill:#8FB6D9,color:#12283F,stroke:#8FB6D9
    style E fill:#12283F,color:#ffffff,stroke:#12283F

INTUIÇÃO E FUNCIONAMENTO O que é o k-NN?

• k-NN (k-Nearest Neighbors) é um algoritmo baseado em instâncias (instance-based, ou lazy learning): não estima parâmetros a partir dos dados de treino — ele simplesmente os guarda.
• A ideia central: observações parecidas tendem a ter o mesmo rótulo (classificação) ou valores parecidos do alvo (regressão) — “diga-me quem são seus vizinhos e eu direi quem você é”.
• Por não ajustar parâmetros no treino, o k-NN é chamado de método não paramétrico: não assume uma forma funcional fixa (como uma reta, no caso da regressão linear) para a relação entre preditores e alvo.

INTUIÇÃO E FUNCIONAMENTO Como o algoritmo decide, passo a passo

Nesse exemplo, 4 dos 5 vizinhos mais próximos são da classe B — o ponto de consulta seria classificado como B.

MÉTRICAS DE DISTÂNCIA Distância euclidiana e Manhattan

• Distância euclidiana (a mais comum): \(\displaystyle d(x,y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}\) — distância “em linha reta” entre dois pontos no espaço de features.
• Distância Manhattan (ou city block): \(\displaystyle d(x,y) = \sum_{i=1}^{n} |x_i - y_i|\) — soma das diferenças absolutas em cada eixo, como se só fosse possível andar em quarteirões retos.
• Manhattan tende a ser mais robusta a outliers em uma única variável do que a euclidiana, pois não eleva as diferenças ao quadrado.

MÉTRICAS DE DISTÂNCIA Distância de Minkowski: uma família de métricas

A distância de Minkowski de ordem \(p\) generaliza euclidiana e Manhattan:

\[d(x,y) = \left(\sum_{i=1}^{n} |x_i - y_i|^p\right)^{1/p}\]

• \(p = 1\) → Manhattan
• \(p = 2\) → Euclidiana
• \(p \to \infty\) → Chebyshev: \(\max_i |x_i - y_i|\)

MÉTRICAS DE DISTÂNCIA Escolhendo (e preparando os dados para) uma métrica

• Distância do cosseno: \(\displaystyle \text{sim}(x,y) = \frac{x \cdot y}{\|x\|\,\|y\|}\) — mede o ângulo entre vetores, ignorando magnitude; comum em texto (vetores esparsos e de alta dimensão) e sistemas de recomendação.
• Todas as métricas de distância tratam cada variável com o mesmo peso — se as escalas forem diferentes, a variável de maior amplitude domina a distância.

ESCOLHA DE K O papel de k no viés e na variância

• k pequeno (ex.: k = 1): a predição depende de pouquíssimos vizinhos — fronteira de decisão muito irregular, alta variância, risco de overfitting (inclusive a ruído e outliers).
• k grande: a predição usa muitos vizinhos, suavizando a fronteira — menor variância, mas maior viés; k excessivamente grande tende a ignorar a estrutura local dos dados.
• k = 1 memoriza o conjunto de treino (erro de treino tende a zero); a pergunta relevante é sempre o erro no conjunto de teste.

ESCOLHA DE K Regras práticas para escolher k

• Um ponto de partida comum é \(k \approx \sqrt{n}\), em que \(n\) é o número de observações de treino — apenas um heurístico inicial, não uma regra ótima.
• Em problemas de classificação binária, prefira k ímpar, para evitar empates na votação majoritária.
• O valor ideal de k depende dos dados e deve ser escolhido por validação cruzada, não fixado a priori.

FRONTEIRAS DE DECISÃO Classificação e regressão com k-NN

• Classificação: o rótulo previsto é a classe mais frequente entre os \(k\) vizinhos (votação majoritária, com empates resolvidos por critérios adicionais, como o vizinho mais próximo entre os empatados).
• Regressão (k-NN regressor): o valor previsto é a média — ou a mediana, mais robusta a outliers — do alvo entre os \(k\) vizinhos.
• Em ambos os casos, o k-NN não produz uma fórmula fechada como \(\hat{y} = \beta_0 + \beta_1 x\): a “função” aprendida é, na prática, o próprio conjunto de treino.

FRONTEIRAS DE DECISÃO k = 1 x k = 15, na mesma base de dados

Com k = 1 a fronteira é irregular e se ajusta a cada ponto (inclusive ruído); com k = 15 ela fica mais suave e estável.

MALDIÇÃO DA DIMENSIONALIDADE O que é a maldição da dimensionalidade?

• À medida que o número de variáveis (dimensões) cresce, o volume do espaço cresce exponencialmente — os dados de treino ficam cada vez mais esparsos dentro desse espaço.
• Em alta dimensão, a diferença entre a distância ao vizinho mais próximo e a distância ao mais distante tende a diminuir relativamente — todos os pontos passam a parecer quase igualmente distantes.
• Isso é particularmente grave para o k-NN, cuja única noção de “similaridade” é justamente a distância entre pontos.

MALDIÇÃO DA DIMENSIONALIDADE Uma simulação real do fenômeno

Com poucas dimensões, a distância ao ponto mais próximo e ao mais distante são bem diferentes. Conforme o número de dimensões cresce, essa diferença relativa desaba — a noção de “vizinho mais próximo” perde poder discriminativo.

MALDIÇÃO DA DIMENSIONALIDADE O que fazer a respeito?

• Reduzir dimensionalidade antes de aplicar k-NN: seleção de variáveis (eliminação manual, VIF) ou redução por PCA.
• Priorizar variáveis com real poder discriminativo em vez de incluir todas as variáveis disponíveis “por garantia”.
• Em problemas de texto ou imagens (naturalmente muito dimensionais), é comum aplicar redução de dimensionalidade ou usar representações aprendidas (embeddings) antes do k-NN.

EFICIÊNCIA COMPUTACIONAL O custo computacional do k-NN

• O “treino” do k-NN é essencialmente gratuito — apenas armazena os dados. Todo o custo computacional é transferido para a predição.
• Busca por força bruta: calcular a distância do ponto de consulta a todos os \(n\) pontos de treino custa \(O(n)\) por predição — caro para bases muito grandes ou para uso em tempo real.
• Esse é um comportamento oposto ao de modelos paramétricos (ex.: regressão logística), em que o treino é mais custoso, mas a predição é praticamente instantânea.

EFICIÊNCIA COMPUTACIONAL k-NN ponderado por distância

• No k-NN “padrão”, todos os \(k\) vizinhos têm o mesmo peso no voto — mas um vizinho a distância 0,1 é intuitivamente mais relevante do que um a distância 4.
• k-NN ponderado: cada vizinho \(i\) recebe peso \(\displaystyle w_i = \frac{1}{d(x, x_i)}\) (ou \(1/d(x,x_i)^2\)), e o voto (ou a média, em regressão) é ponderado por \(w_i\):

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

• Ponderar por distância suaviza a escolha de k: vizinhos “extras” incluídos por um k um pouco maior têm influência proporcionalmente menor.

VALIDAÇÃO E USO PRÁTICO Ajuste de k por validação cruzada

• A curva de erro x k foi construída com um único split treino/teste — sujeita a variação por acaso, especialmente em bases pequenas.
• Validação cruzada (k-fold) repete o processo em várias partições dos dados de treino, escolhendo o \(k\) que minimiza o erro médio entre as partições — uma estimativa mais estável do que um único split.
• Esse é o mesmo princípio de amostragem estratificada aplicado especificamente à escolha de hiperparâmetro.

VALIDAÇÃO E USO PRÁTICO Vantagens e limitações do k-NN