DBSCAN e Aprendizado Semi-Supervisionado: Quando Agrupar Ajuda a Rotular

Aula 9a e 9b. O Bishop não cobre nem DBSCAN nem aprendizado semi-supervisionado no livro (os dois ficaram mais populares na literatura depois de 2006), então esse post fica mais em cima do que o professor mostrou, com bem menos citação direta ao livro do que o normal por aqui.

Onde o K-means quebra a cara

O professor gera um dataset sintético clássico, make_moons: dois arcos entrelaçados, tipo duas meias-luas encaixadas.

from sklearn.datasets import make_moons
X, y = make_moons(n_samples=1000, noise=0.05, random_state=42)

Roda o K-means que eu já vi no post anterior com K=2 nesse dado, e o resultado é ruim: K-means sempre corta o espaço em regiões convexas (cada ponto vai pro centroide mais próximo, então a fronteira entre grupos é sempre uma reta), mas as duas luas não são convexas, elas se encaixam uma na curva da outra. O K-means acaba cortando quase no meio, ignorando o formato real dos arcos. Medindo a concordância entre o agrupamento do K-means e a divisão real das duas luas (usando o índice de Rand ajustado, uma métrica que vale 1 quando os grupos batem perfeitamente com a divisão real e perto de 0 quando é como sortear ao acaso): 0.24. Quase não bateu.

DBSCAN: agrupar por densidade, não por distância até um centro

O professor descreve o algoritmo em texto puro, sem fórmula:

• Pra cada ponto, conta quantos outros pontos estão a uma distância pequena $\varepsilon$ (epsilon) dele. Essa é a vizinhança-$\varepsilon$.
• Se um ponto tem pelo menos min_samples vizinhos nessa distância (contando ele mesmo), ele é um ponto central (mora numa região densa).
• Todo ponto na vizinhança de um ponto central pertence ao mesmo grupo. Como essa vizinhança pode conter outros pontos centrais, uma cadeia de pontos centrais vizinhos forma um grupo só, não importa o quão longo o "cordão" fique.
• Todo ponto que não é central e não está na vizinhança de nenhum central é ruído (rótulo -1), não pertence a grupo nenhum.

A diferença de fundo pro K-means: DBSCAN nunca assume que um grupo tem "um centro". Ele só segue regiões densas, então consegue acompanhar formatos tortos, como duas meias-luas.

from sklearn.cluster import DBSCAN
dbscan = DBSCAN(eps=0.05, min_samples=5)
y_pred = dbscan.fit_predict(X)

Saída (eps=0.05): 7 grupos, 77 pontos marcados como ruído.

$\varepsilon$ pequeno demais fragmenta o dado inteiro em pedacinhos, porque poucos pontos caem dentro de uma vizinhança tão apertada.

dbscan = DBSCAN(eps=0.2, min_samples=5)

Saída (eps=0.2): exatamente 2 grupos, zero pontos de ruído, índice de Rand ajustado de 1.0: bate perfeitamente com a divisão real das duas luas.

Interativo: mexendo em eps e min_samples ao vivo

Reconstrução minha do algoritmo (numa amostra de 300 pontos das mesmas duas luas, pra rodar rápido no navegador). Mexe nos dois controles e observa como o número de grupos e de pontos de ruído muda:

Com eps bem pequeno, quase todo mundo vira ruído (cinza). Subindo eps aos poucos, os grupos começam a se formar, até que num certo ponto as duas luas aparecem inteiras. Passar demais do ponto certo funde as duas luas numa só. min_samples funciona parecido: valores altos exigem uma vizinhança mais lotada pra alguém virar ponto central, então grupos ficam mais exigentes (mais ruído, grupos mais "sólidos").

O problema de não ter .predict()

DBSCAN não guarda centroide nenhum, então não tem como perguntar "esse ponto novo pertence a qual grupo?" do mesmo jeito que o K-means faz. A solução do professor: treinar um KNN separado, usando só os pontos centrais do DBSCAN (dbscan.components_) e o grupo de cada um como rótulo.

from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors=50)
knn.fit(dbscan.components_, dbscan.labels_[dbscan.core_sample_indices_])
print(knn.predict(X_new))

Saída: [1, 0, 1, 0] pros 4 pontos novos testados.

Mas isso tem um problema: KNN sempre encontra um vizinho mais próximo, não importa a distância, então ele vai "prever" um grupo pra qualquer ponto, mesmo um bem longe de tudo, que deveria ser ruído. O ajuste fino: olhar a distância até o vizinho mais próximo e, se for grande demais (o professor usa o próprio eps como corte), marcar como ruído (-1) em vez de forçar num grupo.

Trocando de assunto: e se rótulo for caro?

A segunda metade da aula muda de problema, mas reaproveita a ideia de agrupar sem rótulo. Cenário: 1400 imagens de dígitos escritos à mão pra treinar, mas rotular cada uma é trabalho manual caro, então só dá pra rotular 50.

n_labeled = 50
log_reg = LogisticRegression(solver="liblinear", max_iter=5000)
log_reg.fit(X_train[:n_labeled], y_train[:n_labeled])

Saída (rotulando as 50 primeiras imagens, na ordem que vieram): 0.766 de acurácia no teste.

Saída (se eu tivesse rótulo pras 1400, o teto teórico): 0.902.

O truque: escolher quais 50 rotular, não quais vêm primeiro

Em vez de rotular as 50 primeiras (ordem arbitrária), o professor usa K-means com K=50 (o mesmo orçamento de rótulos!) pra achar 50 grupos nas 1400 imagens sem rótulo, e escolhe, de cada grupo, a imagem mais próxima do centro (a mais "típica" daquele grupo):

kmeans = KMeans(n_clusters=50)
X_digits_dist = kmeans.fit_transform(X_train)
representative_digit_idx = np.argmin(X_digits_dist, axis=0)

Só essas 50 imagens representativas são rotuladas manualmente (o professor colou os rótulos certos na mão, célula 8 do notebook). Treinando com só essas 50:

Saída: 0.834. Melhor que os 50 rótulos aleatórios (0.766), com o mesmo número de rótulos.

Faz sentido: 50 imagens escolhidas pra representar 50 grupos diferentes cobrem mais variedade do que 50 imagens na ordem em que apareceram (que podem repetir o mesmo estilo de "7" várias vezes e nunca mostrar um "3" torto).

Propagação: espalhar o rótulo pro grupo inteiro

Se a imagem representante do grupo 12 é um "7", é razoável supor que todo mundo no grupo 12 também é um "7" (foi por isso que caíram no mesmo grupo, afinal). Propagando o rótulo do representante pra cada membro do cluster:

y_train_propagated = np.empty(len(X_train), dtype=np.int32)
for i in range(k):
    y_train_propagated[kmeans.labels_==i] = y_representative_digits[i]

Saída: treinando com os 1400 rótulos propagados (mas só 50 verdadeiramente checados à mão): 0.869. E conferindo contra o rótulo real (coisa que só dá pra fazer aqui porque é um exercício, na vida real você não saberia): a propagação acerta 95.4% das vezes.

Um refinamento a mais: descartar, de cada grupo, o 20% mais distante do centro (os pontos "na fronteira", mais prováveis de pertencer errado ao grupo) antes de propagar:

Saída: sobra 1111 exemplos (de 1400), com 97.7% de acerto na propagação (subiu de 95.4%). Treinando só com esses: 0.879, o melhor resultado da aula usando só 50 rótulos de verdade.

E o padrão se repete trocando LogisticRegression por KNN, Random Forest, Naive Bayes Gaussiano e NearestCentroid: em todo classificador testado, "representativo" bate "50 aleatórios", e "propagado" bate "representativo sozinho".

Fechando

Aplicação Prática

Reproduzi a cadeia completa (50 aleatórios → representativos → propagados) no mesmo dataset de dígitos, com semente fixa, pra confirmar que o ganho não foi coincidência de uma rodada só.

log_reg = LogisticRegression(solver="lbfgs", max_iter=5000, random_state=42)
# ... mesmo procedimento do professor, com random_state fixo em cada etapa

Meus números batem de perto com os do notebook original (0.766 / 0.834 / 0.869 / 0.954 / 0.902), a diferença mora só na semente aleatória e no solver da regressão logística (troquei liblinear por lbfgs, porque a versão mais nova do scikit-learn no meu ambiente não aceita mais liblinear em problemas com mais de duas classes). A ordem entre as estratégias é idêntica em ambas as rodadas: aleatório perde pra representativo, que perde pra propagado, confirmando que o ganho é real, não sorte de uma rodada específica.