k-NN, Naive Bayes

Por que k-NN e Naive Bayes ainda importam

k-Vizinhos Mais Próximos (k-Nearest Neighbors, k-NN) e Naive Bayes (NB) costumam ser ensinados cedo porque são simples. Eles também ainda são usados em sistemas reais porque são:

  • Baselines fortes (strong baselines): surpreendentemente competitivos em muitos cenários.
  • Rápidos para iterar: escolhas de modelagem mínimas, poucos hiperparâmetros.
  • Bons “checks de formato”: se modelos complexos não os superam, algo pode estar errado (atributos, vazamento, avaliação etc.).

Eles têm sucesso por razões diferentes:

  • k-NN depende de uma hipótese de similaridade (similarity assumption): “pontos próximos no espaço de atributos tendem a compartilhar rótulos”.
  • Naive Bayes depende de uma hipótese de independência condicional (conditional independence assumption): “os atributos são independentes dado a classe”.

Ambas as hipóteses frequentemente estão “erradas” no sentido estrito, mas ainda assim os métodos podem funcionar muito bem.

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

Ideia central e hipóteses

k-NN é um método baseado em instâncias (instance-based), não paramétrico (non-parametric). Não há uma fase explícita de treinamento que aprenda parâmetros (além de indexar os dados). Para prever para um novo ponto x, ele:

  1. Encontra os k pontos de treinamento mais próximos de x sob uma métrica de distância escolhida.
  2. Agrega seus rótulos (voto majoritário para classificação, média para regressão).

Hipótese-chave: a função de rótulo é localmente suave no espaço de atributos escolhido — pontos próximos devem ter saídas semelhantes.

Isso torna o k-NN altamente dependente de:

  • a representação de atributos
  • a métrica de distância
  • a escala dos atributos

Se o seu espaço de atributos corresponde à noção real de similaridade, k-NN pode ser muito forte. Se não, ele falha de forma contundente.

Algoritmo (classificação)

Dado o conjunto de treinamento (x_i, y_i):

  • Calcule as distâncias d(x, x_i) para todos os pontos de treinamento.
  • Seja N_k(x) o conjunto de índices das k menores distâncias.
  • Prediga:
    • Sem pesos: ŷ = mode({ y_i : i ∈ N_k(x) })
    • Ponderado pela distância: peso do voto w_i = 1 / (d(x, x_i) + ε) ou exp(-d^2 / σ^2)

Métricas de distância: o “modelo” dentro do k-NN

Escolhas comuns:

  • Euclidiana (L2): padrão para atributos contínuos e com escalas semelhantes.
  • Manhattan (L1): às vezes mais robusta em alta dimensionalidade.
  • Distância do cosseno (cosine distance): comum para embeddings de texto esparsos ou vetores TF-IDF (foca no ângulo, não na magnitude).
  • Hamming: codificações binárias/categóricas.
  • Métricas aprendidas (learned metrics): via Aprendizado de Métrica para fazer as distâncias corresponderem à similaridade semântica.

Nota prática: para tipos mistos de atributos ou similaridade complexa, o k-NN frequentemente funciona melhor quando você investe em aprendizado de representação (embeddings) em vez de ficar ajustando k.

Considerações práticas

Escalonamento de atributos não é opcional

Distâncias não têm sentido se um atributo domina pela escala. Abordagens padrão:

  • Padronização (média zero, variância unitária)
  • Escalonamento min-max
  • Normalização para similaridade do cosseno

Ao usar validação cruzada, o escalonamento deve ser ajustado apenas nos folds de treino para evitar vazamento.

Maldição da dimensionalidade

Em alta dimensionalidade, as distâncias tornam-se menos informativas: vizinhos mais próximos e mais distantes podem estar a distâncias semelhantes. Isso pode fazer o k-NN degradar rapidamente, a menos que:

Escolhendo `k`

  • k pequeno → baixo viés, alta variância (sensível a ruído).
  • k grande → viés mais alto, fronteira de decisão mais suave.

Regra prática: ajuste k com validação; valores ímpares ajudam a evitar empates em classificação binária.

Custo computacional

  • Custo de “treino”: baixo (armazenar dados).
  • Custo de predição (ingênuo): O(n · d) por consulta, onde n é o número de pontos de treino, d o número de atributos.

Acelerações:

  • KD-tree / Ball tree (efetivas em dimensionalidade baixa/moderada).
  • Vizinhos mais próximos aproximados (approximate nearest neighbors) (HNSW, IVF, quantização de produto) para recuperação em larga escala. Essas ideias também aparecem em Sistemas de Recomendação e busca semântica.

Quando k-NN funciona bem

  • Conjuntos de dados pequenos a médios em que armazenar todos os pontos é viável.
  • Espaços de atributos bem estruturados (bons embeddings, distância significativa).
  • Fronteiras de classe não lineares sem necessidade de treinamento de modelo.
  • Tarefas de similaridade com cold-start (por exemplo, “encontrar usuários/itens/documentos semelhantes”).

Quando k-NN tem dificuldades

  • Atributos brutos de alta dimensionalidade sem boa representação.
  • n grande com restrições de latência (a menos que use indexação de ANN).
  • Classes fortemente desbalanceadas (vizinhos provavelmente dominados pela classe majoritária, a menos que você tenha cuidado).
  • Muitos atributos irrelevantes (a distância fica ruidosa).

Exemplo: classificação k-NN no scikit-learn

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

model = make_pipeline(
    StandardScaler(),
    KNeighborsClassifier(n_neighbors=5, weights="distance", metric="minkowski", p=2)
)

model.fit(X_train, y_train)
pred = model.predict(X_test)

print(classification_report(y_test, pred))

Principais conclusões do exemplo:

  • Use um pipeline para que o escalonamento seja aplicado corretamente.
  • Experimente weights="distance" quando você espera que vizinhos mais próximos sejam mais confiáveis.

Naive Bayes (NB)

Regra de Bayes e o modelo Naive Bayes

Naive Bayes é um modelo probabilístico, tipicamente paramétrico (parametric), generativo (generative). Ele modela a distribuição conjunta:

  • Escolha uma classe y de acordo com P(y)
  • Gere atributos x = (x1, x2, ..., xd) a partir de P(x | y)

Pela regra de Bayes:

P(y | x) ∝ P(y) * P(x | y)

A hipótese “naive” é:

P(x | y) = Π_j P(x_j | y) (os atributos são condicionalmente independentes dado a classe)

Assim, a regra de classificação torna-se:

ŷ = argmax_y [ log P(y) + Σ_j log P(x_j | y) ]

Usar logaritmos evita underflow numérico e transforma produtos em somas.

Por que a hipótese de independência ainda pode funcionar

Mesmo quando os atributos são correlacionados, Naive Bayes ainda pode classificar bem porque:

  • a classificação depende de escores relativos entre classes, não de probabilidades perfeitamente calibradas
  • erros nas estimativas de probabilidade podem se cancelar
  • com atributos esparsos de alta dimensionalidade (por exemplo, texto), a hipótese é “menos errada” na prática

Dito isso, as saídas de probabilidade frequentemente são mal calibradas; você pode precisar de calibração se as decisões dependerem de probabilidades.

Variantes comuns de Naive Bayes

A escolha depende do tipo de atributo:

Naive Bayes Multinomial (multinomial naive bayes) (contagens de texto)

Para contagens de palavras (bag-of-words):

  • x_j = contagem do token j
  • P(x | y) é multinomial com probabilidades de tokens específicas por classe

Frequentemente usado para detecção de spam, classificação de tópicos, sentimento.

Tipicamente combinado com:

  • bag-of-words ou n-grams
  • atributos de contagem ou TF-IDF (TF-IDF não é estritamente multinomial, mas funciona bem empiricamente)

Naive Bayes Bernoulli (bernoulli naive bayes) (atributos binários)

Para indicadores binários (palavra presente/ausente):

  • útil quando a presença importa mais do que a frequência

Naive Bayes Gaussiano (gaussian naive bayes) (atributos contínuos)

Assume:

  • x_j | y ~ Normal(μ_{y,j}, σ^2_{y,j})

Funciona como um baseline rápido para dados contínuos, mas pode ser sensível a distribuições não gaussianas e ao escalonamento de atributos.

Naive Bayes Complementar (complement naive bayes)

Uma variante projetada para funcionar melhor em classificação de texto desbalanceada, modelando estatísticas de “não a classe”.

Suavização: evitando probabilidades zero

Em Naive Bayes Multinomial/Bernoulli, se uma palavra nunca aparece em uma classe no treinamento, então P(word | class) = 0, o que pode zerar toda a verossimilhança.

Suavização de Laplace/aditiva (laplace/additive smoothing) corrige isso:

P(word=j | y) = (count(j,y) + α) / (total_count(y) + α*V)

  • α = 1 é suavização de Laplace
  • α menor pode funcionar melhor em vocabulários grandes

Considerações práticas

Velocidade de treinamento e inferência

NB é extremamente rápido:

  • o treinamento é essencialmente contar ocorrências de atributos por classe
  • a predição é um produto escalar dos atributos com log-probabilidades

Isso torna NB uma escolha forte para:

  • classificação de texto em tempo real
  • espaços de atributos esparsos grandes
  • baselines rápidos em pipelines de aprendizado de máquina

Interpretabilidade

Parâmetros de NB frequentemente são interpretáveis:

  • quais tokens são mais indicativos de cada classe
  • raciocínio no estilo log-odds (embora tenha cuidado com atributos correlacionados “contando duas vezes” a evidência)

Relação com modelos lineares

NB produz uma regra de decisão linear no espaço de atributos para variantes comuns. Pode parecer com Regressão Linear/Logística, mas:

  • NB é generativo (modela P(x|y) e P(y))
  • regressão logística é discriminativa (discriminative) (modela P(y|x) diretamente) A regressão logística frequentemente vence com dados suficientes; NB pode vencer com pouquíssimos dados ou texto esparso de altíssima dimensionalidade.

Exemplo: classificação de spam com NB Multinomial

from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.naive_bayes import MultinomialNB
from sklearn.metrics import classification_report

texts = [
    "cheap pills buy now", "limited time offer", "meeting agenda for tomorrow",
    "project update and timeline", "win money win prizes", "let's schedule a call"
]
labels = [1, 1, 0, 0, 1, 0]  # 1=spam, 0=ham

X_train, X_test, y_train, y_test = train_test_split(
    texts, labels, test_size=0.33, random_state=0, stratify=labels
)

model = make_pipeline(
    TfidfVectorizer(ngram_range=(1,2), min_df=1),
    MultinomialNB(alpha=0.5)
)

model.fit(X_train, y_train)
pred = model.predict(X_test)

print(classification_report(y_test, pred))

Notas:

  • TfidfVectorizer com bigramas frequentemente melhora o desempenho.
  • Para atributos de contagem pura, CountVectorizer também é comum.
  • Se seu conjunto de dados for desbalanceado, considere ComplementNB e avalie com métricas além de acurácia.

Comparando k-NN vs Naive Bayes

Forças e fraquezas em resumo

  • k-NN

    • Prós: fronteiras não lineares flexíveis; simples; pode ser muito preciso com bons embeddings; sem treino.
    • Contras: lento na inferência sem indexação; sensível a escalonamento e atributos irrelevantes; tem dificuldades em alta dimensionalidade.

  • Naive Bayes

    • Prós: extremamente rápido; forte para texto/dados esparsos; funciona bem com poucos dados; simples e razoavelmente interpretável.
    • Contras: a hipótese de independência pode estimar mal probabilidades; pode ser superado por modelos discriminativos com dados suficientes; a calibração pode ser ruim.

Como escolher na prática

Escolha k-NN quando:

  • você tem uma métrica de distância significativa (ou embeddings aprendidos)
  • o conjunto de dados não é grande demais, ou você pode usar índices de ANN
  • as fronteiras de decisão provavelmente são não lineares
  • você quer um baseline forte “baseado em similaridade” (comum em recuperação e recomendação)

Escolha Naive Bayes quando:

  • os atributos são esparsos e de alta dimensionalidade (texto)
  • você precisa de treinamento/inferência extremamente rápidos
  • você tem poucos dados rotulados e quer um baseline robusto
  • interpretabilidade no nível de atributo importa (por exemplo, quais palavras impulsionam o spam)

Se você estiver trabalhando com dados tabulares e quiser forte desempenho, considere também Árvores de Decisão & Ensembles como próximo passo; para classificação baseada em margem, veja SVMs.

Armadilhas comuns e boas práticas

Armadilhas de k-NN

  • Vazamento de dados via pré-processamento: sempre ajuste escaladores/codificadores dentro dos folds de validação cruzada (use pipelines).
  • Ignorar desbalanceamento de classes: considere ponderação por distância, votação ponderada por classe, ou reamostragem.
  • Escolher a distância errada: cosseno frequentemente supera Euclidiana para vetores esparsos.
  • Rótulos ruidosos/outliers: k pequeno fará overfit; considere k maior ou variantes de vizinho mais próximo editado/condensado.

Armadilhas de Naive Bayes

  • Contagens zero sem suavização: sempre use alpha > 0 para multinomial/bernoulli.
  • Modelo de atributos incompatível: use Multinomial/Bernoulli para texto, Gaussiano para contínuos (como baseline).
  • Probabilidades excessivamente confiantes: se você usa probabilidades para limiares de decisão, considere calibração (por exemplo, regressão isotônica) e valide com cuidado.
  • Atributos correlacionados: NB pode “contar duas vezes” a evidência; seleção de atributos ou migração para regressão logística pode ajudar.

Onde eles se encaixam em um fluxo de trabalho moderno de ML

Apesar da ascensão do aprendizado profundo, k-NN e NB continuam valiosos:

  • Como baselines de primeira linha para pipelines de classificação/regressão.
  • Como componentes dentro de sistemas maiores:
    • k-NN para recuperação por vizinho mais próximo, busca por similaridade, deduplicação e recomendação baseada em embeddings (veja Sistemas de Recomendação).
    • Naive Bayes para triagem rápida de texto, filtros de spam e bootstrap de rótulos.
  • Como ferramentas de diagnóstico:
    • Se k-NN com um bom embedding falha, a representação pode estar fraca.
    • Se NB falha em texto, atributos ou tokenização podem ser o gargalo.

Em resumo: estes são modelos “simples” cuja eficácia depende menos de otimização sofisticada e mais de escolher atributos que correspondam às suas hipóteses.