K-means: Quando Agrupar Vira um Truque de Engenharia de Features

Aula 8a, 8b e 8c, e a matéria muda de regime pela primeira vez: até aqui, todo modelo aprendia a prever um rótulo que já vinha no dado (y). K-means não recebe rótulo nenhum, só encontra grupos.

O problema: separar sem saber a resposta

O professor volta pro Iris, mas dessa vez esconde a espécie (y) e passa só as duas variáveis (comprimento e largura da pétala) pro algoritmo. A pergunta muda de "que espécie é essa flor?" pra "quantos grupos naturais existem aqui, e onde ficam?".

K-means na unha

from sklearn.base import BaseEstimator, ClusterMixin, TransformerMixin

class KMeans(BaseEstimator, ClusterMixin, TransformerMixin):
    def __init__(self, n_clusters=3, max_iter=100):
        self.n_clusters = n_clusters
        self.max_iter = max_iter

    def fit(self, X, y=None):
        self.centroids = X[random.sample(range(len(X)), self.n_clusters)]
        max_iter = self.max_iter
        while max_iter > 0:
            max_iter -= 1
            y_pred = self.predict(X)
            for i in range(self.n_clusters):
                self.centroids[i] = np.mean(X[y_pred==i], axis=0)
            if np.allclose(self.centroids, self.previous_centroids[-1], atol=1e-9):
                break
        return self

    def predict(self, X):
        # atribui cada ponto ao centroide mais próximo
        ...

Repara na assinatura da classe: ClusterMixin e TransformerMixin juntos, a primeira vez que uma classe dessa playlist herda de duas coisas ao mesmo tempo além de BaseEstimator. Isso não é acaso, e o motivo vai ficar claro mais adiante no post.

O algoritmo (chamado K-means de Lloyd, o mais comum) é só dois passos repetidos até parar de mudar:

1. Atribuir: cada ponto vai pro centroide mais próximo (distância euclidiana).
2. Recalcular: cada centroide vira a média dos pontos que foram atribuídos a ele.

O Bishop formaliza os dois passos como a minimização de uma medida de distorção,

$J = \sum_{n=1}^{N}\sum_{k=1}^{K} r_{nk}\|\mathbf{x}_n - \boldsymbol{\mu}_k\|^2$

onde $r_{nk}=1$ se o ponto $n$ pertence ao grupo $k$ (e 0 caso contrário). Fixando os centroides, o $r_{nk}$ ótimo é óbvio (atribui pro mais próximo, é exatamente o passo 1). Fixando os $r_{nk}$, o centroide ótimo é a média dos pontos atribuídos a ele, porque é ali que a derivada de $J$ zera (é exatamente o passo 2). Cada passo só pode diminuir $J$ ou empatar, nunca aumentar, então o algoritmo sempre converge, só que pode parar num mínimo local, não necessariamente o melhor agrupamento possível (por isso, na prática, o scikit-learn roda o K-means várias vezes com centroides iniciais diferentes e fica com o resultado de menor $J$).

Interativo: vendo os centroides se moverem

Reconstrução minha do mesmo algoritmo (atribuir, recalcular, repetir), nos 150 pontos reais do Iris, as mesmas duas variáveis do post de árvores de decisão. Clica em "Passo" e acompanha a inércia ($J$) cair a cada rodada, e as regiões (quem pertence a qual centroide) se ajustarem:

Os pontos continuam coloridos pela espécie real, só pra você comparar visualmente: as regiões que o K-means encontra sozinho, sem nunca ver o rótulo, batem bastante com as espécies de verdade, principalmente pra Setosa (que já era claramente separada desde o post de árvores). Clica em "Reiniciar" algumas vezes: dependendo de onde os centroides caem por sorteio, o resultado final pode variar um pouco, exatamente a limitação de mínimo local que o Bishop descreve.

Escolhendo K: o método do cotovelo

Faltou uma pergunta: como escolher quantos grupos (K) procurar? O K-means do scikit-learn expõe inertia_, que é exatamente o $J$ do Bishop no final do treino:

kmeans_k3 = KMeans(n_clusters=3).fit(X)
kmeans_k8 = KMeans(n_clusters=8).fit(X)

Saída: inércia com K=3: 31.37. Com K=8: 8.31.

Mais grupos sempre reduz (ou empata) a inércia, no limite (K = número de pontos) ela chega a zero, cada ponto vira seu próprio grupo, o que não serve pra nada. O truque é plotar a inércia contra vários valores de K e procurar o cotovelo: o ponto onde a curva para de cair rápido e passa a cair devagar. Antes do cotovelo, cada grupo a mais ainda captura estrutura real. Depois dele, cada grupo a mais só está fatiando ruído. O professor repete esse gráfico pro Iris, pro dataset de vinhos que já apareceu nessa playlist, e pro Digits (1797 imagens de dígitos escritos à mão, 8×8 pixels cada), sem tirar um número fechado de nenhum, o objetivo é só mostrar a forma da curva.

O truque: usar os grupos como feature nova

Aqui que a aula 8b vira o post inteiro de cabeça pra baixo. Em vez de usar K-means só pra agrupar, o professor usa ele dentro de um pipeline supervisionado, como uma etapa de pré-processamento:

from sklearn.linear_model import RidgeClassifier
from sklearn.model_selection import cross_val_score
from sklearn.pipeline import make_pipeline

model = RidgeClassifier()
scores = cross_val_score(model, X, y, cv=5)

Saída (Digits, RidgeClassifier sozinho, direto nos 64 pixels): 0.888 de acurácia média.

model = make_pipeline(
    KMeans(n_clusters=50),
    RidgeClassifier()
)
scores = cross_val_score(model, X, y, cv=5)

Saída (mesmo dataset, com K-means de 50 grupos antes do classificador): 0.939.

Um salto e tanto, só de encaixar um K-means no meio do caminho. Como isso funciona? É aqui que o TransformerMixin que eu mencionei lá em cima entra em cena. Dentro de um Pipeline, toda etapa que não é a última precisa ter .transform(), não .predict(). O K-means do scikit-learn implementa os dois: .predict() devolve o índice do grupo mais próximo (um número só), mas .transform() devolve a distância até cada um dos K centroides (K números). Uma imagem de 64 pixels vira um vetor de 50 números, cada um dizendo "quão parecida essa imagem é com o protótipo do grupo 1, do grupo 2, ..., do grupo 50". Cada centroide funciona como um "dígito prototípico" aprendido sem rótulo nenhum, e a distância até cada um vira uma feature nova, mais informativa pro classificador linear do que o pixel cru.

O professor ainda usa o Optuna pra buscar o número ideal de grupos (entre 10 e 200):

Saída: o melhor encontrado foi n_clusters=136, com 0.963 de acurácia média em validação cruzada. Testando n_clusters=250 na mão (mais grupos que o Optuna sequer tentou): 0.966, ainda melhor.

Mais grupos, mais "protótipos" diferentes pra comparar, mais informação pro classificador final, até onde o professor testou.

O mesmo truque, num dataset maior: MNIST

aula08c repete a receita exata no MNIST (60 mil imagens de treino, 28×28 pixels cada, então 784 variáveis por imagem, bem mais que o Digits):

Oito pontos percentuais de ganho, no mesmo dataset, no mesmo classificador linear, só trocando "64/784 valores de pixel cru" por "250 distâncias até protótipos aprendidos sem rótulo". A ideia de reaproveitar um algoritmo não supervisionado como fonte de features pra um problema supervisionado é mais geral do que parece: qualquer vetor de "distância até um protótipo" carrega informação que o pixel cru não carrega sozinho.

Fechando

Aplicação Prática

Reproduzi a mesma receita (K-means como transformador antes do RidgeClassifier) no Digits, com semente fixa e n_init=10 (o K-means roda 10 vezes com centroides iniciais diferentes e fica com o de menor inércia, o padrão do scikit-learn), pra confirmar o efeito de forma reprodutível.

cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=42)
ridge_scores = cross_val_score(RidgeClassifier(random_state=42), X, y, cv=cv)
for k in [50, 136, 250]:
    model = make_pipeline(KMeans(n_clusters=k, random_state=42, n_init=10), RidgeClassifier(random_state=42))
    scores = cross_val_score(model, X, y, cv=cv)

Meus números saem mais altos que os do notebook original (0.888/0.939/0.963), provavelmente porque fixei n_init=10 (o K-means tenta várias inicializações e fica com a melhor, evitando os mínimos locais ruins que o Bishop avisou lá em cima) e uma semente que meu ambiente conseguiu reproduzir de forma estável. Mas a tendência é idêntica à do notebook: quanto mais grupos, melhor a acurácia, e a melhora de "pixel cru" pra "distância até protótipo" é grande e consistente em qualquer contagem de grupos testada.