Phase 02 - Lesson 06

K-vizinhos e distâncias mais próximos

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Guarde tudo. Preveja olhando para seus vizinhos. O algoritmo mais simples que realmente funciona.

Tipo: Construir Idioma: Python Pré-requisitos: Fase 1 (Lição 14 Normas e Distâncias) Tempo: ~90 minutos

Objetivos de aprendizagem

• Implementar classificação e regressão KNN do zero com K configurável e votação ponderada por distância
• Compare as métricas de distância L1, L2, cosseno e Minkowski e selecione a apropriada para um determinado tipo de dados
• Explique a maldição da dimensionalidade e demonstre por que KNN se degrada em espaços de alta dimensão
• Construa uma árvore KD para pesquisa eficiente do vizinho mais próximo e analise quando ela supera a força bruta

O problema

Você tem um conjunto de dados. Um novo ponto de dados chega. Você precisa classificá-lo ou prever seu valor. Em vez de aprender parâmetros dos dados (como regressão linear ou SVMs), basta encontrar os K pontos de treinamento mais próximos do novo ponto e deixá-los votar.

Estes são os K-vizinhos mais próximos. Não há fase de treinamento. Sem parâmetros para aprender. Nenhuma função de perda para minimizar. Você armazena todo o conjunto de treinamento e calcula as distâncias no momento da previsão.

Parece muito simples de trabalhar. Mas KNN é surpreendentemente competitivo para muitos problemas, especialmente com conjuntos de dados pequenos e médios, e compreendê-lo profundamente revela conceitos fundamentais: a escolha da métrica de distância (conectando-se à Fase 1, Lição 14), a maldição da dimensionalidade e a diferença entre aprendizado preguiçoso e ansioso.

KNN também aparece em toda parte na IA moderna, apenas com nomes diferentes. Bancos de dados de vetores KNN pesquisam embeddings. A geração aumentada de recuperação (RAG) encontra os K pedaços de documento mais próximos. Os sistemas de recomendação encontram usuários ou itens semelhantes. O algoritmo é o mesmo. A escala e as estruturas de dados são diferentes.

O Conceito

Como KNN funciona

Dado um conjunto de dados de pontos rotulados e um novo ponto de consulta:

1. Calcule a distância da consulta até cada ponto do conjunto de dados
2. Classifique por distância
3. Pegue os K pontos mais próximos
4. Para classificação: votação majoritária entre os K vizinhos
5. Para regressão: média (ou média ponderada) dos valores dos K vizinhos

graph TD
    Q["Query point ?"] --> D["Compute distances<br>to all training points"]
    D --> S["Sort by distance"]
    S --> K["Select K nearest"]
    K --> C{"Classification<br>or Regression?"}
    C -->|Classification| V["Majority vote"]
    C -->|Regression| A["Average values"]
    V --> P["Prediction"]
    A --> P

Esse é todo o algoritmo. Sem encaixe. Sem descida do gradiente. Sem épocas.

Escolhendo K

K é o único hiperparâmetro. Ele controla a compensação entre polarização e variância:

Um ponto de partida comum é K = sqrt(N) para um conjunto de dados de N pontos. Use K ímpar para classificação binária para evitar empates.

graph LR
    subgraph "K=1 (overfitting)"
        A["Jagged boundary<br>follows every point"]
    end
    subgraph "K=15 (good)"
        B["Smooth boundary<br>captures true pattern"]
    end
    subgraph "K=N (underfitting)"
        C["Flat boundary<br>predicts majority class"]
    end
    A -->|"increase K"| B -->|"increase K"| C

Métricas de distância

A função de distância define o que significa “próximo”. Métricas diferentes produzem vizinhos diferentes, previsões diferentes.

L2 (Euclidiano) é o padrão. Distância em linha reta.

d(a, b) = sqrt(sum((a_i - b_i)^2))

Sensível à escala de recursos. Sempre padronize os recursos antes de usar L2 com KNN.

L1 (Manhattan) soma diferenças absolutas. Mais robusto para valores discrepantes do que L2 porque não compensa as diferenças.

d(a, b) = sum(|a_i - b_i|)

Distância do cosseno mede o ângulo entre os vetores, ignorando a magnitude. Essencial para texto e incorporação de dados.

d(a, b) = 1 - (a . b) / (||a|| * ||b||)

Minkowski generaliza L1 e L2 com o parâmetro p.

d(a, b) = (sum(|a_i - b_i|^p))^(1/p)

p=1: Manhattan
p=2: Euclidean
p->inf: Chebyshev (max absolute difference)

Qual métrica usar depende dos dados:

Ponderado KNN

O padrão KNN dá peso igual a todos os K vizinhos. Mas um vizinho à distância 0,1 deveria ser mais importante do que um vizinho à distância 5,0.

** KNN** ponderado pela distância pondera cada vizinho inversamente pela distância:

weight_i = 1 / (distance_i + epsilon)

For classification: weighted vote
For regression:     weighted average = sum(w_i * y_i) / sum(w_i)

O épsilon evita a divisão por zero quando um ponto de consulta corresponde exatamente a um ponto de treinamento.

KNN ponderado é menos sensível à escolha de K porque vizinhos distantes contribuem muito pouco de qualquer maneira.

A maldição da dimensionalidade

KNN o desempenho diminui em dimensões elevadas. Esta não é uma preocupação vaga. É um fato matemático.

Problema 1: as distâncias convergem. À medida que a dimensionalidade aumenta, a razão entre a distância máxima e a distância mínima se aproxima de 1. Todos os pontos ficam igualmente "distantes" da consulta.

In d dimensions, for random uniform points:

d=2:    max_dist / min_dist = varies widely
d=100:  max_dist / min_dist ~ 1.01
d=1000: max_dist / min_dist ~ 1.001

When all distances are nearly equal, "nearest" is meaningless.

Problema 2: o volume explode. Para capturar K vizinhos dentro de uma fração fixa dos dados, você precisa estender seu raio de pesquisa para cobrir uma fração muito maior do espaço de recursos. O “bairro” em dimensões elevadas abrange a maior parte do espaço.

Problema 3: os cantos dominam. Em um hipercubo unitário em dimensões d, a maior parte do volume está concentrada perto dos cantos, não no centro. Uma esfera inscrita no cubo contém uma fração que desaparece do volume à medida que d cresce.

Consequência prática: KNN funciona bem em cerca de 20 a 50 recursos. Além disso, você precisa de redução de dimensionalidade (PCA, UMAP, t-SNE) antes de aplicar KNN, ou precisa usar estruturas de pesquisa baseadas em árvore que explorem a menor dimensionalidade intrínseca dos dados.

KD-trees: pesquisa rápida do vizinho mais próximo

Força bruta KNN calcula a distância da consulta até cada ponto de treinamento. Isso é O(n * d) por consulta. Para grandes conjuntos de dados, isso é muito lento.

Uma árvore KD particiona recursivamente o espaço ao longo dos eixos de recursos. Em cada nível, ele se divide em uma dimensão no valor mediano.

graph TD
    R["Split on x1 at 5.0"] -->|"x1 <= 5.0"| L["Split on x2 at 3.0"]
    R -->|"x1 > 5.0"| RR["Split on x2 at 7.0"]
    L -->|"x2 <= 3.0"| LL["Leaf: 3 points"]
    L -->|"x2 > 3.0"| LR["Leaf: 4 points"]
    RR -->|"x2 <= 7.0"| RL["Leaf: 2 points"]
    RR -->|"x2 > 7.0"| RRR["Leaf: 5 points"]

Para encontrar o vizinho mais próximo, atravesse a árvore até a folha que contém a consulta, depois volte e verifique as partições vizinhas apenas se elas puderem conter pontos mais próximos.

Tempo médio de consulta: O(log n) para dimensões baixas. Mas as árvores KD degradam-se para O(n) em dimensões altas (d > 20) porque o retrocesso elimina cada vez menos ramos.

Árvores de bola: melhor para dimensões moderadas

As árvores esféricas particionam os dados em hiperesferas aninhadas em vez de caixas alinhadas ao eixo. Cada nó define uma bola (centro + raio) que contém todos os pontos daquela subárvore.

Vantagens sobre as árvores KD:

• Funciona melhor em dimensões moderadas (até ~50)
• Lidar com estrutura não alinhada ao eixo
• Volumes delimitados mais restritos significam que mais ramificações são podadas durante a pesquisa

Tanto as árvores KD quanto as árvores esféricas são algoritmos exatos. Para pesquisas verdadeiramente em grande escala (milhões de pontos, centenas de dimensões), são usados ​​métodos aproximados do vizinho mais próximo (HNSW, fertilização in vitro, quantização de produto). Eles são abordados na Lição 14 da Fase 1.

Aprendizagem preguiçosa versus aprendizagem ansiosa

KNN é um aluno preguiçoso: não trabalha na hora do treinamento e trabalha na hora da previsão. A maioria dos outros algoritmos (regressão linear, SVMs, redes neurais) são aprendizes ávidos: eles fazem cálculos pesados ​​no momento do treinamento para construir um modelo compacto e, então, as previsões são rápidas.

A aprendizagem preguiçosa é ideal quando:

• O conjunto de dados muda frequentemente (adicionar/remover pontos sem retreinar)
• Você precisa de previsões para poucas consultas
• Você quer tempo zero de treinamento
• O conjunto de dados é pequeno o suficiente para que a pesquisa por força bruta seja rápida

KNN para regressão

Em vez da votação por maioria, KNN para regressão calcula a média dos valores alvo dos K ​​vizinhos.

prediction = (1/K) * sum(y_i for i in K nearest neighbors)

Or with distance weighting:
prediction = sum(w_i * y_i) / sum(w_i)
where w_i = 1 / distance_i

A regressão KNN produz previsões constantes por partes (ou suaves por partes com ponderação). Não pode extrapolar além do intervalo dos dados de treinamento. Se todas as metas de treinamento estiverem entre 0 e 100, KNN nunca preverá 200.

Construa

Etapa 1: Funções de distância

Implemente distâncias L1, L2, cosseno e Minkowski. Eles se conectam diretamente à Fase 1, Lição 14.

import math

def l2_distance(a, b):
    return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))

def l1_distance(a, b):
    return sum(abs(ai - bi) for ai, bi in zip(a, b))

def cosine_distance(a, b):
    dot_val = sum(ai * bi for ai, bi in zip(a, b))
    norm_a = math.sqrt(sum(ai ** 2 for ai in a))
    norm_b = math.sqrt(sum(bi ** 2 for bi in b))
    if norm_a == 0 or norm_b == 0:
        return 1.0
    return 1.0 - dot_val / (norm_a * norm_b)

def minkowski_distance(a, b, p=2):
    if p == float('inf'):
        return max(abs(ai - bi) for ai, bi in zip(a, b))
    return sum(abs(ai - bi) ** p for ai, bi in zip(a, b)) ** (1 / p)

Etapa 2: classificador KNN e regressor

Construa o KNN completo com K configurável, métrica de distância e ponderação de distância opcional.

class KNN:
    def __init__(self, k=5, distance_fn=l2_distance, weighted=False,
                 task="classification"):
        self.k = k
        self.distance_fn = distance_fn
        self.weighted = weighted
        self.task = task
        self.X_train = None
        self.y_train = None

    def fit(self, X, y):
        self.X_train = X
        self.y_train = y

    def predict(self, X):
        return [self._predict_one(x) for x in X]

Etapa 3: árvore KD para pesquisa eficiente

Construa uma árvore KD do zero que se divide recursivamente na mediana de cada dimensão.

class KDTree:
    def __init__(self, X, indices=None, depth=0):
        # Recursively partition the data
        self.axis = depth % len(X[0])
        # Split on median of the current axis
        ...

    def query(self, point, k=1):
        # Traverse to leaf, then backtrack
        ...

Veja code/knn.py para a implementação completa com todos os métodos auxiliares e demonstrações.

Etapa 4: dimensionamento de recursos

KNN requer escalonamento de recursos porque as distâncias são sensíveis às magnitudes dos recursos. Um atributo que varia de 0 a 1000 dominará um atributo que varia de 0 a 1.

def standardize(X):
    n = len(X)
    d = len(X[0])
    means = [sum(X[i][j] for i in range(n)) / n for j in range(d)]
    stds = [
        max(1e-10, (sum((X[i][j] - means[j]) ** 2 for i in range(n)) / n) ** 0.5)
        for j in range(d)
    ]
    return [[((X[i][j] - means[j]) / stds[j]) for j in range(d)] for i in range(n)], means, stds

Use-o

Com scikit-learn:

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

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier(n_neighbors=5, metric="euclidean")),
])
clf.fit(X_train, y_train)
print(f"Accuracy: {clf.score(X_test, y_test):.4f}")

Scikit-learn usa automaticamente árvores KD ou árvores de bola quando o conjunto de dados é grande o suficiente e a dimensionalidade é baixa o suficiente. Para dados de alta dimensão, recorre-se à força bruta. Você pode controlar isso com o parâmetro algorithm.

Para pesquisa de vizinhos mais próximos em larga escala (milhões de vetores), use FAISS, Annoy ou um banco de dados de vetores:

import faiss

index = faiss.IndexFlatL2(dimension)
index.add(embeddings)
distances, indices = index.search(query_vectors, k=5)

Exercícios

1. Implemente a classificação KNN em um conjunto de dados 2D com 3 classes. Trace o limite de decisão para K=1, K=5, K=15 e K=N. Observe a transição do overfitting para o underfitting.

2. Gere 1.000 pontos aleatórios em 2, 5, 10, 50, 100 e 500 dimensões. Para cada dimensionalidade, calcule a razão entre a distância máxima entre pares e a distância mínima entre pares. Trace a relação versus dimensionalidade para visualizar a maldição da dimensionalidade.

3. Compare L1, L2 e distância do cosseno para KNN em um problema de classificação de texto (use vetores TF-IDF). Qual métrica oferece a melhor precisão? Por que o cosseno tende a vencer no texto?

4. Implemente uma árvore KD e meça o tempo de consulta versus força bruta para conjuntos de dados de 1k, 10k e 100k pontos em 2D, 10D e 50D. Em que dimensionalidade a árvore KD deixa de ser mais rápida que a força bruta?

5. Construa um regressor ponderado KNN para y = sin(x) + ruído. Compare-o com KNN não ponderado para K=3, 10, 30. Mostre que a ponderação produz previsões mais suaves, especialmente para K grande.

Termos-chave

Leitura Adicional

• Cover & Hart: Nearest Neighbor Pattern Classification (1967) - o artigo fundamental KNN provando que tem uma taxa de erro no máximo duas vezes maior que Bayes ideal
• Friedman, Bentley, Finkel: Um algoritmo para encontrar as melhores correspondências no tempo esperado logarítmico (1977) - o artigo original da árvore KD
• Beyer et al.: Quando o "vizinho mais próximo" é significativo? (1999) - análise formal da maldição da dimensionalidade para o vizinho mais próximo
• scikit-learn Documentação dos vizinhos mais próximos - guia prático com seleção de algoritmo
• [FAISS: Uma biblioteca para pesquisa eficiente de similaridade] (https://github.com/facebookresearch/faiss) - Biblioteca do Meta para pesquisa aproximada de vizinho mais próximo em escala de bilhões