Clusterização Espectral

Visão geral

A clusterização espectral é uma família de métodos de clusterização não supervisionada que:

  1. Constrói um grafo de similaridade sobre os pontos de dados (nós são pontos, arestas conectam pontos similares),
  2. Calcula um pequeno conjunto de autovetores (eigenvectors) de um Laplaciano de grafo (graph Laplacian) derivado desse grafo,
  3. Usa esses autovetores como uma incorporação (embedding) de baixa dimensionalidade dos dados,
  4. Executa um método padrão de clusterização (com mais frequência Clusterização K-Means) no espaço incorporado.

A ideia-chave é que muitos formatos de cluster “difíceis” no espaço original (por exemplo, anéis concêntricos ou “duas luas”) tornam-se mais fáceis de separar após uma incorporação espectral baseada em grafo.

A clusterização espectral é amplamente usada em:

  • Segmentação de imagens (pixels/superpixels como nós),
  • Detecção de comunidades em redes,
  • Agrupamento de itens com base em similaridade par a par (documentos, usuários, produtos),
  • Qualquer cenário em que distâncias não são bem modeladas por geometria Euclidiana mas um grafo de similaridade é natural.

Intuição: clusterização como um problema de corte em grafo

Algoritmos tradicionais como k-means assumem que clusters são aproximadamente esféricos no espaço Euclidiano. A clusterização espectral, em vez disso, trata a clusterização como particionamento de um grafo de modo que:

  • Nós dentro do mesmo cluster sejam fortemente conectados (alta similaridade),
  • Nós entre clusters sejam fracamente conectados (baixa similaridade).

Uma formalização comum é minimizar um objetivo de corte em grafo (graph cut). Suponha que dividimos os nós em conjuntos (A) e (B). O corte é:

[ \text{cut}(A,B) = \sum_{i\in A, j\in B} w_{ij} ]

onde (w_{ij}) é o peso da aresta (similaridade).

Minimizar cut de forma ingênua tende a isolar conjuntos pequenos (até nós únicos). Para desencorajar cortes triviais, usam-se objetivos normalizados:

  • RatioCut: [ \text{RatioCut}(A,B) = \text{cut}(A,B)\left(\frac{1}{|A|} + \frac{1}{|B|}\right) ]

  • Corte Normalizado (Ncut) (Normalized Cut): [ \text{Ncut}(A,B) = \text{cut}(A,B)\left(\frac{1}{\text{vol}(A)} + \frac{1}{\text{vol}(B)}\right) ] onde (\text{vol}(A) = \sum_{i\in A} d_i) e (d_i=\sum_j w_{ij}) é o grau do nó.

Esses objetivos levam a problemas de otimização combinatórios (NP-difíceis em geral). Métodos espectrais resolvem um relaxamento contínuo, no qual a solução relaxada ótima é dada por autovetores de uma matriz Laplaciana.

Etapa 1: Construindo a matriz de afinidade (similaridade)

A clusterização espectral começa com uma matriz de afinidade (W \in \mathbb{R}^{n \times n}), onde (W_{ij}\ge 0) mede a similaridade entre pontos (x_i, x_j). Tipicamente:

  • (W) é simétrica: (W_{ij}=W_{ji}),
  • (W_{ii}=0) (frequentemente, embora não seja obrigatório).

Escolhas comuns de afinidade

1) Afinidade por kernel RBF / Gaussiano (grafo denso)

Uma escolha muito comum é:

[ W_{ij} = \exp\left(-\frac{|x_i-x_j|^2}{2\sigma^2}\right) ]

  • (\sigma) controla a “escala” das vizinhanças.
  • (\sigma) muito pequeno: o grafo fica quase desconectado (muitas arestas quase zero).
  • (\sigma) muito grande: o grafo fica quase totalmente conectado com pesos semelhantes (os clusters ficam borrados).

Isso produz uma matriz densa, que se torna cara para (n) grande.

2) Grafo de k-vizinhos mais próximos (kNN) (grafo esparso)

Conecte cada ponto aos seus (k) vizinhos mais próximos e defina pesos (por exemplo, RBF apenas nessas arestas):

  • (W_{ij} > 0) se (j) está entre os kNN de (i) (ou vice-versa),
  • caso contrário (W_{ij}=0).

Isso gera um grafo esparso (tipicamente muito mais escalável e frequentemente mais robusto).

Regras comuns de simetrização:

  • kNN mútuo: conecta (i)–(j) apenas se cada um estiver nos kNN do outro (mais esparso, pode desconectar).
  • kNN união: conecta se qualquer direção valer (menos esparso, mais conectado).

3) Grafo de vizinhança-ε

Conecte pontos dentro da distância (\epsilon):

  • Escolha (\epsilon) para que o grafo seja conectado (ou tenha um número razoável de componentes).

Isso pode ser sensível em alta dimensionalidade, onde as distâncias se concentram.

Orientações práticas para construir \(W\)

  • Escale as features: padronize ou normalize as entradas antes de calcular distâncias (por exemplo, z-score). Caso contrário, uma feature pode dominar a similaridade.
  • Prefira grafos esparsos para tamanhos de conjuntos de dados não triviais:
    • Grafos kNN frequentemente atingem um bom equilíbrio entre localidade e conectividade.
  • Considere “escala local” se a densidade variar:
    • Um truque conhecido (“clusterização espectral autoajustável”) define um (\sigma_i) local usando a distância ao (k)-ésimo vizinho e define
      [ W_{ij} = \exp\left(-\frac{|x_i-x_j|^2}{\sigma_i\sigma_j}\right) ]
    • Isso pode reduzir a sensibilidade a um único (\sigma) global.

Etapa 2: Matrizes Laplacianas e o que elas significam

Dado (W), defina a matriz de graus (D) como diagonal com:

[ D_{ii} = \sum_{j=1}^n W_{ij} ]

O Laplaciano de grafo codifica a conectividade e é central para a incorporação espectral.

Escolhas comuns de Laplaciano

Laplaciano não normalizado

[ L = D - W ]

Propriedades:

  • (L) é simétrico semidefinido positivo.
  • O menor autovalor é 0; o número de autovalores zero é igual ao número de componentes conectados no grafo.

Frequentemente associado a relaxamentos de RatioCut.

Laplaciano normalizado (simétrico)

[ L_{\text{sym}} = I - D^{-1/2} W D^{-1/2} ]

Frequentemente usado na prática devido a melhor comportamento quando os graus dos nós variam.

Laplaciano de caminhada aleatória

[ L_{\text{rw}} = I - D^{-1} W ]

Estreitamente relacionado a caminhadas aleatórias e cadeias de Markov em grafos.

Por que autovetores?

Em um caso ideal com (k) clusters perfeitamente desconectados (o grafo tem (k) componentes conectados):

  • Os primeiros (k) autovetores correspondentes ao autovalor 0 abrangem vetores indicadores dos componentes.
  • Em dados reais, os clusters são “quase” desconectados, e os menores autovetores fornecem uma incorporação contínua que separa grupos.

Isso é análogo em espírito à Análise de Componentes Principais (que também usa autovetores), mas os autovetores da clusterização espectral vêm de um Laplaciano de grafo, não de uma matriz de covariância.

Etapa 3: O algoritmo de clusterização espectral (variante normalizada)

Um pipeline padrão de clusterização espectral normalizada (semelhante a Ng, Jordan, Weiss) é:

  1. Construa a matriz de afinidade (W).
  2. Calcule (D) e (L_{\text{sym}} = I - D^{-1/2} W D^{-1/2}).
  3. Calcule os (k) menores autovetores de (L_{\text{sym}}); empilhe-os como colunas em (U \in \mathbb{R}^{n \times k}).
  4. Normalize por linha: (Y_{i\cdot} = U_{i\cdot} / |U_{i\cdot}|).
  5. Execute k-means nas linhas de (Y) para obter rótulos de cluster.

A etapa de normalização por linha é importante: ela faz a incorporação depender mais da direção do que da magnitude, o que empiricamente melhora a separação para Laplacianos normalizados.

Pseudocode

input: points x1..xn, number of clusters k, similarity parameters
W = build_affinity_graph(x1..xn)
Dii = sum_j Wij
Lsym = I - D^{-1/2} W D^{-1/2}
U = eigenvectors_of_smallest_k_eigenvalues(Lsym)
Y_i = U_i / ||U_i||   (row-normalize)
labels = kmeans(Y, k)
return labels

Escolhendo o número de clusters \(k\)

A clusterização espectral tipicamente exige (k) como entrada (como k-means). Estratégias comuns:

Heurística do salto de autovalores (eigengap heuristic)

Calcule autovalores (\lambda_1 \le \lambda_2 \le \dots) (para (L_{\text{sym}}), (\lambda_1) é próximo de 0). Procure um grande “salto”:

[ (\lambda_{k+1} - \lambda_k) \text{ é grande} ]

Interpretação: os primeiros (k) autovetores capturam uma forte estrutura de clusters; além disso, você está modelando ruído.

Armadilhas:

  • Não há salto claro em dados bagunçados.
  • O melhor “salto” pode corresponder a uma partição que não é significativa para sua aplicação.

Seleção baseada em estabilidade

Teste múltiplos valores de (k) e meça se as clusterizações são estáveis em:

  • subamostras por bootstrap,
  • diferentes sementes aleatórias,
  • pequenas mudanças nos parâmetros de afinidade.

Use restrições do domínio

Em aplicações como segmentação de imagens, você pode ter um número alvo de segmentos ou um intervalo. Para comunidades em redes, você pode preferir interpretabilidade em vez de puro eigengap.

Armadilhas práticas e considerações de engenharia

1) Escalonamento e sensibilidade a parâmetros de afinidade

A causa mais comum de falha é uma escala de similaridade ruim.

Sintomas:

  • Grafo muito desconectado: muitos componentes, autovetores viram indicadores triviais, a clusterização é instável.
  • Grafo muito denso/uniforme: autovetores não separam clusters.

Mitigações:

  • Use grafos kNN em vez de RBF denso.
  • Ajuste (\sigma) com um proxy de validação (silhueta no espaço incorporado, testes de estabilidade).
  • Considere escala local para densidade variável.

2) Grafos desconectados e múltiplos componentes

Se o grafo tiver múltiplos componentes conectados:

  • O Laplaciano tem múltiplos autovalores zero.
  • Você pode efetivamente obter clusters = componentes (o que pode ser desejável ou não).

Abordagens práticas:

  • Aumente o (k) do kNN (mais arestas),
  • Aumente (\sigma) ou (\epsilon),
  • Aceite componentes como clusters se isso fizer sentido (comum em clusterização baseada em conectividade).

3) Custo computacional e memória

Uma (W) densa custa:

  • Memória: (O(n^2))
  • Decomposição espectral: tipicamente superlinear; decomposição completa é (O(n^3))

Isso se torna impraticável além de algumas dezenas de milhares de pontos (frequentemente muito menos se for denso).

Mitigações:

  • Use grafos esparsos (kNN) e solucionadores de autovetores esparsos (Lanczos/ARPACK).
  • Use aproximações:
    • aproximação de Nyström (Nyström approximation) (amostrar colunas/landmarks),
    • métodos de features aleatórias / sketching,
    • métodos de “anchor graph”.
  • Se você só precisa dos menores (k) autovetores, use solucionadores iterativos em vez de decomposição completa.

4) Problemas de distância em alta dimensionalidade

Em alta dimensionalidade, distâncias Euclidianas podem se tornar menos informativas (“concentração de distância”). Isso prejudica a construção de afinidade.

Mitigações:

  • Normalize as features e considere redução de dimensionalidade (por exemplo, Análise de Componentes Principais) antes de construir (W).
  • Use uma similaridade adaptada ao domínio (similaridade do cosseno para embeddings de texto, métricas aprendidas, etc.).

5) Extensão fora da amostra (novos pontos)

A clusterização espectral básica é transdutiva (transductive): ela clusteriza os pontos fornecidos, mas não fornece diretamente um mapeamento para novos pontos.

Opções:

  • Reexecutar a clusterização incluindo novos pontos (caro).
  • Usar extensões ao estilo Nyström para incorporar novos pontos aproximadamente.
  • Treinar um modelo de regressão que mapeie features originais (\to) coordenadas da incorporação espectral (funciona se a incorporação for estável).

6) Relação com k-means e métodos de kernel

A clusterização espectral pode ser vista como:

  • Executar k-means após uma incorporação não linear baseada em grafo,
  • Fortemente relacionada ao k-means com kernel (kernel k-means) quando (W) é tratado como um kernel (com ressalvas sobre centralização/normalização). Isso a conecta conceitualmente a Métodos de Kernel.

Exemplo trabalhado (Python com scikit-learn)

Uma demonstração clássica é clusterizar um conjunto de dados de “duas luas”, em que k-means no espaço original tem dificuldade, mas a clusterização espectral tem sucesso.

import numpy as np
from sklearn.datasets import make_moons
from sklearn.cluster import KMeans, SpectralClustering
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import adjusted_rand_score

# Data: two interleaving half-circles
X, y_true = make_moons(n_samples=1000, noise=0.06, random_state=0)

# Always scale before distance-based graphs
X = StandardScaler().fit_transform(X)

# Baseline: k-means in original space
kmeans = KMeans(n_clusters=2, n_init=20, random_state=0)
y_km = kmeans.fit_predict(X)

# Spectral clustering with a kNN affinity graph
spec = SpectralClustering(
    n_clusters=2,
    affinity="nearest_neighbors",
    n_neighbors=15,   # key parameter; tune this
    assign_labels="kmeans",
    random_state=0
)
y_sc = spec.fit_predict(X)

print("ARI k-means:", adjusted_rand_score(y_true, y_km))
print("ARI spectral:", adjusted_rand_score(y_true, y_sc))

Notas:

  • n_neighbors controla a esparsidade/conectividade do grafo. Muito pequeno pode desconectar; muito grande pode “lavar” a estrutura.
  • affinity="rbf" também está disponível, mas então você deve ajustar gamma (relacionado a (\sigma)) cuidadosamente.

Aplicações

Segmentação de imagens

Pixels (ou superpixels) formam nós; pesos combinam proximidade espacial e similaridade de cor/textura. O objetivo de corte normalizado foi historicamente influente aqui.

Dicas práticas:

  • Use superpixels para reduzir (n) drasticamente.
  • Garanta que as afinidades reflitam tanto aparência quanto localidade espacial (caso contrário, cores semelhantes distantes podem se conectar incorretamente).

Detecção de comunidades em redes

Se você já tem um grafo (rede social, grafo de cop compra), você pode usar a adjacência ou adjacência ponderada como (W). A clusterização espectral pode recuperar comunidades quando as arestas são mais densas dentro de grupos do que entre grupos.

Ressalva: redes reais podem ter distribuições de grau com cauda pesada; Laplacianos normalizados são frequentemente preferíveis.

Clusterização de embeddings (texto, usuários, produtos)

Se você tem embeddings vetoriais de um modelo (por exemplo, embeddings de um modelo de linguagem), a clusterização espectral pode ajudar quando os clusters são não convexos ou conectados por cadeias.

Nesses casos:

  • Considere similaridade do cosseno para afinidades (converta para pesos não negativos).
  • Prefira grafos kNN para gerenciar escala.

Quando usar clusterização espectral (e quando não)

Use clusterização espectral quando:

  • Os formatos dos clusters são não convexos (por exemplo, “luas”, anéis),
  • Um grafo ou similaridade par a par é mais natural do que distância Euclidiana bruta,
  • Você tem computação suficiente para cálculos de autovetores (ou pode usar métodos esparsos/aproximados).

Evite ou seja cauteloso quando:

  • (n) é muito grande e você não consegue construir um bom grafo esparso ou uma boa aproximação,
  • A escala de similaridade é incerta e o ajuste é difícil,
  • Você precisa de uma regra fácil de predição fora da amostra,
  • Os dados são bem separados e convexos — métodos mais simples como Clusterização K-Means, Modelos de Mistura Gaussiana ou DBSCAN podem ser mais fáceis de colocar em produção.

Resumo

A clusterização espectral reformula a clusterização como particionamento de grafo: constrói um grafo de afinidade, calcula um Laplaciano, usa um pequeno número de autovetores do Laplaciano para incorporar pontos e, então, clusteriza nesse espaço incorporado. Ela é poderosa para estruturas de cluster não convexas e dados nativos de grafos, mas exige escolhas cuidadosas quanto a:

  • Construção de afinidade (kNN vs RBF, escalonamento),
  • Tipo de Laplaciano (não normalizado vs normalizado),
  • Seleção de (k) (salto de autovalores, estabilidade),
  • Escalabilidade (grafos esparsos, solucionadores iterativos de autovetores, aproximações).

Na prática, o sucesso da clusterização espectral é frequentemente determinado menos pelos autovetores em si e mais pela qualidade e pela escala do grafo de similaridade que você constrói.