Ir para o conteúdo

Agrupamento

O agrupamento (clustering) é a tarefa não supervisionada por excelência: agrupar observações de modo que pontos no mesmo grupo sejam semelhantes e pontos em grupos diferentes sejam dissimilares — sem rótulos para guiar ou avaliar o agrupamento. Usos típicos: segmentação de clientes, detecção de anomalias, compressão de imagens, organização de documentos (o caminho para a modelagem de tópicos).

Como não há verdade de referência, todo resultado de agrupamento é uma hipótese sobre estrutura, e as suposições do algoritmo determinam que tipo de estrutura ele consegue encontrar.

k-means

O algoritmo clássico (Lloyd, 1957/1982). Escolha \(k\); encontre os centroides \(\mu_1, \dots, \mu_k\) que minimizam a soma dos quadrados intra-cluster (inércia):

\[ \min_{\mu_1,\dots,\mu_k} \; \sum_{i=1}^{n} \min_{j} \; \lVert x_i - \mu_j \rVert^2 \]

O algoritmo de Lloyd alterna dois passos até as atribuições pararem de mudar:

  1. Atribuir: cada ponto se junta ao centroide mais próximo;
  2. Atualizar: cada centroide se move para a média dos pontos atribuídos a ele.
from sklearn.cluster import KMeans

km = KMeans(n_clusters=3, n_init=10, random_state=0)   # n_init: reinícios
labels = km.fit_predict(X_scaled)
km.inertia_          # soma dos quadrados intra-cluster
km.cluster_centers_

Propriedades e armadilhas:

  • Você precisa escolher \(k\) de antemão;
  • Converge para um ótimo local — daí os múltiplos reinícios (n_init);
  • Assume que os agrupamentos são convexos, aproximadamente esféricos, de tamanho semelhante (particiona o espaço em células de Voronoi em torno dos centroides);
  • Baseado em distância → escalone seus atributos (Pré-processamento);
  • Todo ponto é atribuído a um agrupamento — o k-means não tem conceito de ruído ou outliers.

Rode você mesmo o algoritmo de Lloyd — os dados têm 3 blobs reais; observe o que acontece com k = 2 ou k = 5 e como diferentes inícios aleatórios convergem para diferentes ótimos locais:

Escolhendo k

  • Método do cotovelo: plote a inércia vs \(k\); a inércia sempre diminui, então procure o "cotovelo" onde os ganhos achatam. Heurístico e muitas vezes ambíguo.
  • Escore de silhueta: para cada ponto, com \(a\) = distância média ao seu próprio agrupamento e \(b\) = distância média ao agrupamento vizinho mais próximo,
\[ s = \frac{b - a}{\max(a, b)} \in [-1, 1]. \]

\(s\) médio perto de 1 → agrupamentos compactos e bem separados; perto de 0 → sobrepostos; negativo → provavelmente mal atribuídos. Escolha o \(k\) que maximiza a silhueta média.

from sklearn.metrics import silhouette_score
silhouette_score(X_scaled, labels)

Agrupamento hierárquico

O agrupamento aglomerativo constrói um dendrograma: começa com cada ponto como seu próprio agrupamento, funde repetidamente os dois agrupamentos mais próximos até restar um só e então corta a árvore no nível desejado. Não é preciso fixar \(k\) de antemão — você o escolhe pelo corte.

A definição de "agrupamentos mais próximos" é o linkage (encadeamento):

Linkage Distância entre agrupamentos Comportamento
single par de pontos mais próximo encontra cadeias alongadas, sensível a ruído
complete par mais distante agrupamentos compactos
average distância média par a par meio-termo
Ward funde minimizando o aumento de inércia semelhante ao k-means, padrão mais comum 
from sklearn.cluster import AgglomerativeClustering
labels = AgglomerativeClustering(n_clusters=3, linkage='ward').fit_predict(X_scaled)

O custo é \(O(n^2)\) de memória/tempo — tranquilo para milhares de pontos, proibitivo para milhões.

DBSCAN e HDBSCAN: agrupamento por densidade

O DBSCAN (Ester et al., 1996) define agrupamentos como regiões densas separadas por regiões esparsas, usando dois parâmetros: eps (raio da vizinhança) e min_samples (pontos necessários para chamar uma vizinhança de densa).

  • Ponto central (core): tem ≥ min_samples vizinhos dentro de eps;
  • Ponto de borda: está dentro de eps de um ponto central, mas não é central;
  • Ruído: nenhum dos dois — o DBSCAN rotula outliers (rótulo −1) em vez de forçá-los para dentro de agrupamentos.

Pontos fortes: encontra agrupamentos de forma arbitrária, sem \(k\) para escolher, detecção de ruído embutida. Fraquezas: um único eps global falha quando os agrupamentos têm densidades diferentes; eps não é intuitivo de ajustar.

O HDBSCAN (Campello, Moulavi & Sander, 2013) elimina o eps global: constrói uma hierarquia sobre todos os níveis de densidade e extrai os agrupamentos mais estáveis, lidando com dados de densidade variável com essencialmente um parâmetro intuitivo (min_cluster_size). Essa robustez é o motivo de o BERTopic usar HDBSCAN para agrupar embeddings de documentos — documentos que não se encaixam em nenhum tópico simplesmente viram ruído em vez de poluir os tópicos.

from sklearn.cluster import HDBSCAN   # scikit-learn ≥ 1.3
labels = HDBSCAN(min_cluster_size=10).fit_predict(X_scaled)

As suposições importam: k-means vs DBSCAN

k-means vs DBSCAN em blobs e duas luas

Em blobs convexos ambos têm sucesso. Nas duas luas, o k-means falha por construção — só consegue traçar fronteiras de Voronoi entre centroides — enquanto o DBSCAN acompanha a densidade e recupera os crescentes, marcando pontos avulsos como ruído.

Escolhendo um algoritmo

Situação Recorra a
Agrupamentos convexos e de tamanho semelhante; n grande; precisa de velocidade k-means (ou MiniBatchKMeans)
Quer um dendrograma / taxonomia; n pequeno hierárquico (Ward)
Formas arbitrárias, ruído/outliers esperados DBSCAN
Formas arbitrárias com densidade variável (ex.: embeddings) HDBSCAN

Valide como um cético

Sem rótulos, sempre inspecione os agrupamentos: escores de silhueta, projeções 2D (PCA/UMAP) e — o mais importante — se os agrupamentos significam algo no domínio. Um agrupamento que ninguém consegue nomear raramente é útil.

Material de aula

Notebook da aula (em português)

Notebook prático usado em sala — Aula 07 — Clustering: abrir no Colab

Vídeo

Algoritmo k-means (k-médias)

Algoritmo k-means (k-médias) — em português

Quiz