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):

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.

Feito à mão

Seis pontos, dois grupos óbvios e uma inicialização ruim de propósito — ambos os centros à esquerda:

Comece com \(\mu_1 = (1,1)\) e \(\mu_2 = (2,1)\) e gire a manivela:

Três coisas a tirar dessa tabela. A inércia cai monotonicamente — 284, 20,7, 2,67 — e isso é garantido: os dois passos só conseguem diminuí-la, razão pela qual o algoritmo sempre termina. O teste de convergência é sobre as atribuições, não sobre a inércia. E uma inicialização tão ruim quanto esta ainda se recuperou, em três iterações — mas nada garantia isso, que é para o que serve o n_init.

Percorra as mesmas duas operações aqui. As setas mostram para onde o passo 2 está prestes a mover cada cruz:

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\) 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.

Para o ponto A = (1,1) do exemplo à mão: o próprio grupo é {B, C}, a distâncias 1 e 1, então \(a = 1\). O outro grupo é {D, E, F}, à distância média \(b = 10{,}39\). Isso dá

que é a aparência numérica de "bem alojado no próprio grupo". Escolha qualquer ponto no simulador e acompanhe as duas médias que o compõem:

Agora varra o \(k\) e ponha os dois critérios lado a lado. Em bolhas limpas eles concordam; em outros formatos não — e o cotovelo é o que cede:

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):

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

Antes da comparação, veja a falha diretamente. O k-means impõe grupos convexos, esféricos e de tamanho parecido a qualquer coisa que você lhe der. Percorra os cinco formatos abaixo — as luas são cortadas atravessado, os anéis concêntricos são impossíveis para qualquer conjunto de centros, os grupos alongados são divididos na diagonal errada e, em ruído puro, ele ainda devolve partições arrumadas:

A lição não é que o k-means seja ruim. É que a métrica nem sempre avisa: em vários desses formatos a silhueta continua respeitável enquanto a partição não significa nada. Uma métrica só consegue pontuar a partição que recebe contra as suposições que ela compartilha com o algoritmo.

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

Material de aula

Vídeo

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

Referências

• Lloyd, S. P. "Least Squares Quantization in PCM." IEEE Trans. Inf. Theory 28 (1982). DOI
• Rousseeuw, P. J. "Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis." J. Comp. Appl. Math. 20 (1987). DOI
• Campello, R.; Moulavi, D.; Sander, J. "Density-Based Clustering Based on Hierarchical Density Estimates." PAKDD (2013). DOI

Bibliografia completa do curso na página de referências.

Quiz