Introdução ao K-Nearest Neighbors (KNN)

O algoritmo KNN é uma das abordagens mais intuitivas no aprandizado de máquina, baseado no princípio de que amostras semelhantes residem próximas umas das outras no espaço de características. Diferente de modelos paramétricos, o KNN é um método de lazy learning, onde a fase de treinamento consiste apenas em armazenar o conjunto de dados, e a computação real ocorre apenas durante a inferência.

Componentes Essenciais

Fundamentos Matemáticos e Métricas de Distância

A escolha da métrica de distância é crucial, pois define a geometria do espaço de busca. Abaixo estão as métricas mais utilizadas e suas respectivas fórmulas para vetores \(x\) e \(y\) de dimensão \(d\):

• Distância Euclidiana (L2): \( \sqrt{\sum_{i=1}^{d} (x_i - y_i)^2} \). Ideal para dados contínuos e densos, mas sensível a outliers.
• Distância de Manhattan (L1): \( \sum_{i=1}^{d} |x_i - y_i| \). Mais robusta em espaços de alta dimensionalidade e dados esparsos.
• Distância de Minkowski (Lp): Generalização das anteriores, controlada pelo parâmetro \(p\).
• Similaridade de Cosseno: Mede o ângulo entre os vetores, ignorando a magnitude. Amplamente usada em processamento de linguagem natural e sistemas de recomendação.

Implementação Prática em Python

Abaixo, apresentamos uma implementação personalizada de um classificador KNN, utilizando vetorização com NumPy para otimizar o cálculo das distâncias e argpartition para evitar a ordenação completa do array, garantindo maior eficiência computacional.

import numpy as np
from collections import Counter

class ClassificadorKNN:
    def __init__(self, k_vizinhos=3, metrica='euclidiana'):
        self.k = k_vizinhos
        self.metrica = metrica
        self.dados_treino = None
        self.rotulos_treino = None

    def _calcular_distancias(self, amostra_alvo, conjunto_dados):
        # Vetorização para cálculo rápido de distâncias
        if self.metrica == 'euclidiana':
            return np.sqrt(np.sum((conjunto_dados - amostra_alvo) ** 2, axis=1))
        elif self.metrica == 'manhattan':
            return np.sum(np.abs(conjunto_dados - amostra_alvo), axis=1)
        else:
            raise ValueError("Métrica não suportada.")

    def fit(self, X_treino, y_treino):
        self.dados_treino = np.asarray(X_treino)
        self.rotulos_treino = np.asarray(y_treino)
        return self

    def predict(self, X_teste):
        X_teste = np.asarray(X_teste)
        previsoes = []
        
        for alvo in X_teste:
            distancias = self._calcular_distancias(alvo, self.dados_treino)
            # Utilizando argpartition para obter os K menores índices sem ordenar tudo
            indices_vizinhos = np.argpartition(distancias, self.k)[:self.k]
            rotulos_vizinhos = self.rotulos_treino[indices_vizinhos]
            
            # Votação majoritária
            classe_mais_comum = Counter(rotulos_vizinhos).most_common(1)[0][0]
            previsoes.append(classe_mais_comum)
            
        return np.array(previsoes)

Estruturas de Dados para Aceleração: KD-Tree e Ball-Tree

O cálculo de força bruta possui complexidade \(O(N \cdot D)\) por consulta, o que é inviável para grandes bases. Para contornar isso, utilizamos estruturas de particionamento espacial:

• KD-Tree: Particiona o espaço em hiperretângulos. Extremamente eficiente para dimensões baixas (\(D < 20\)), mas sofre com a maldição da dimensionalidade em espaços maiores.
• Ball-Tree: Utiliza hiperesferas para agrupar os pontos. Apresenta melhor desempenho e estabilidade em dimensionalidades moderadas a altas, suportando diversas métricas de distância não-euclidianas.

A Maldição da Dimensionalidade

À medida que o número de características (\(D\)) aumenta, o volume do espaço cresce exponencialmente, fazendo com que os dados se tornem esparsos. Consequentemente, a distância entre o ponto mais próximo e o mais distante tende a se igualar, invalidando a premissa de proximidade do KNN.

Estratégias de Mitigação:

1. Redução de Dimensionalidade: Aplicação de PCA, t-SNE ou UMAP para projetar os dados em um subespaço relevante.
2. Seleção de Features: Remoção de variáveis redundantes ou com baixa correlação com o alvo.
3. Hash Sensível à Localidade (LSH): Técnica de busca aproximada que mapeia itens similares para os mesmos "buckets" com alta probabilidade.

Engenharia de Features e Escalonamento

Como o KNN é estritamente baseado em distâncias, a escala das variáveis impacta diretamente o modelo. Uma feature com variância alta dominará o cálculo de distância se os dados não forem normalizados. O uso de Pipeline é obrigatório para evitar vazamento de dados (data leakage) durante a validação cruzada.

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

# Pipeline para evitar vazamento de dados
pipeline_knn = Pipeline([
    ('escalonador', RobustScaler()), # Robusto a outliers
    ('knn', KNeighborsClassifier(n_neighbors=5, weights='distance'))
])

# O pipeline garante que o fit_transform seja aplicado apenas no treino
# e o transform apenas no teste durante o cross-validation

Variantes e Otimizações do Algoritmo

Para lidar com ruídos e desbalanceamentos, diversas variações do KNN clássico foram desenvolvidas:

Aplicações Industriais

• Sistemas de Recomendação: Filtragem colaborativa baseada em usuários ou itens, utilizando similaridade de cosseno para lidar com esparsidade de matrizes de avaliação.
• Detecção de Anomalias: Cálculo da distância para o K-ésimo vizinho (ou LOF - Local Outlier Factor) para identificar pontos que residem em regiões de baixa densidade.
• Classificação de Imagens e Texto: Quando combinado com extração de features profundas (ex: embeddings de CNNs ou BERT), o KNN atua como um classificador few-shot eficiente em cenários com dados rotulados limitados.