Agrupamento Espectral

Atualizado 2025-11-05 Leitura 2 min

Resumo

O agrupamento espectral usa o espectro (autovalores/autovetores) de um grafo de similaridade para projetar os dados em um espaço onde o k-means pode separar facilmente os clusters.
Ele lida com estruturas não linearmente separáveis (por exemplo, círculos concêntricos, meias-luas) capturando conectividade em vez da distância euclidiana bruta.
Os principais hiperparâmetros incluem a definição de afinidade (rbf, grafo de vizinhos mais próximos, cosseno), o parâmetro de escala (gamma ou n_neighbors) e a estratégia de atribuição de rótulos.
Após computar os primeiros (k) autovetores do Laplaciano normalizado, normalize as linhas e execute k-means para obter os rótulos dos clusters.

Intuição #

Este método deve ser interpretado por meio de suas suposições, condições dos dados e como as escolhas de parâmetros afetam a generalização.

Explicação Detalhada #

1. Visão geral #

Dados pontos (x_i), criamos uma matriz de afinidade (W) cujas entradas refletem a similaridade par a par. O Laplaciano (não normalizado) do grafo é

$$ L = D - W, \quad D = \mathrm{diag}(d_1, \dots, d_n),\; d_i = \sum_j W_{ij}. $$

O agrupamento espectral tipicamente usa o Laplaciano simétrico normalizado

$$ L_{\mathrm{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}. $$

Tome os (k) autovetores associados aos menores autovalores de (L_{\mathrm{sym}}), empilhe-os na matriz (U), normalize cada linha e execute k-means nessas linhas. As atribuições resultantes são traduzidas de volta para as amostras originais.

2. Exemplo em Python #

import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib
from sklearn.datasets import make_circles
from sklearn.cluster import SpectralClustering

X, _ = make_circles(n_samples=500, factor=0.4, noise=0.05, random_state=0)

model = SpectralClustering(
    n_clusters=2,
    affinity="rbf",
    gamma=50,
    assign_labels="kmeans",
    random_state=0,
)
labels = model.fit_predict(X)

plt.figure(figsize=(6, 5))
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap="coolwarm", s=20)
plt.title("Spectral clustering result")
plt.tight_layout()
plt.show()

Exemplo de agrupamento espectral

3. Notas práticas #

Para grafos esparsos, use affinity="nearest_neighbors" e ajuste n_neighbors.
assign_labels="cluster_qr" pode ser mais estável que o k-means padrão para representações de alta dimensionalidade.
Sempre normalize os atributos antes de calcular as similaridades, caso contrário as escalas de gamma/distância perdem o significado.

4. Referências #

Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE TPAMI.
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. NeurIPS.
scikit-learn developers. (2024). Spectral clustering. https://scikit-learn.org/stable/modules/clustering.html#spectral-clustering