Skip to content
Voltar aos resultados

Agrupamento Espectral

Proposto por
Ng, A. Y.; Jordan, M. I.; Weiss, Y.
Ano
2002
Tipo
Graph-based clustering (spectral method)

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Agrupamento Espectral é um algoritmo de aprendizado não supervisionado baseado em grafos, formalizado por Ng, Jordan e Weiss em 2002, que mapeia pontos de dados para um espaço de autovalores de baixa dimensão derivado do Laplaciano do grafo de similaridade antes de aplicar k-means.

Essa incorporação espectral torna possível recuperar agrupamentos de forma arbitrária — anéis, crescentes, espirais entrelaçadas — que métodos baseados em distância euclidiana consistentemente falham em separar.

A intuição por trás do método

O k-means padrão particiona o espaço por distância em linha reta, portanto, só consegue encontrar aglomerados convexos e aproximadamente esféricos. O Agrupamento Espectral contorna isso pensando primeiro nos dados como uma rede: cada ponto é um nó, e as arestas entre os nós carregam um peso que reflete o quão similares são os dois pontos. Agrupamentos correspondem a regiões da rede que são densamente conectadas internamente, mas fracamente conectadas ao resto. A matriz Laplaciana do grafo codifica essa estrutura de conectividade, e seus autovetores menores agem como um sistema de coordenadas suave que estica os dados de modo que agrupamentos bem separados acabem distantes um do outro, mesmo quando estavam emaranhados no espaço original. Um passo simples de k-means nesse novo sistema de coordenadas, então, os separa de forma limpa.

História

As bases teóricas do agrupamento espectral remontam ao trabalho de Fiedler de 1973 sobre conectividade de grafos e o autovalor de conectividade algébrica. Shi e Malik (2000) trouxeram a abordagem para a visão computacional através de seu critério de cortes normalizados para segmentação de imagens. Ng, Jordan e Weiss (2002) apresentaram um algoritmo limpo e de propósito geral na NIPS — aquele agora mais comumente citado — juntamente com uma análise teórica de perturbação explicando quando e por que o método funciona. O tutorial de Von Luxburg de 2007 em Statistics and Computing unificou as formulações concorrentes, esclareceu o papel da normalização do Laplaciano e se tornou a referência padrão para praticantes. O agrupamento espectral agora ocupa um lugar central no currículo de aprendizado de máquina e permanece um tópico ativo de pesquisa, com trabalhos em andamento sobre aproximações escaláveis, kernels robustos e extensões para grafos e variedades.

Quando usar

O Agrupamento Espectral é bem adequado quando os agrupamentos nos dados são não convexos, não linearmente separáveis ou conectados por pontes finas que métodos de particionamento euclidiano não conseguem detectar — exemplos comuns incluem agrupamentos em forma de anel, espirais entrelaçadas e segmentos de imagem. É apropriado quando a similaridade par a par entre os pontos pode ser calculada de forma significativa (seja a partir de um kernel em características brutas ou de uma matriz de afinidade pré-fornecida), e quando o número de agrupamentos k é conhecido ou pode ser estimado pela heurística do eigengap. O método não requer suposições distribucionais sobre as formas dos agrupamentos. Limitações práticas incluem memória quadrática no número de pontos (para a matriz de afinidade completa) e tempo cúbico para a decomposição em autovalores, tornando a formulação padrão cara além de aproximadamente 10.000 pontos. Métodos aproximados (Nystrom, grafos esparsos, SVD randomizado) estendem seu alcance para conjuntos de dados maiores.

Limitações e considerações

  • A construção da matriz de afinidade completa n x n requer memória O(n^2) e tempo O(n^3) para decomposição em autovalores, tornando o algoritmo ingênuo infactível para grandes conjuntos de dados.
  • Os resultados são sensíveis à escolha da largura de banda sigma do kernel e à estratégia de construção do grafo; escolhas ruins podem fundir ou fragmentar agrupamentos.
  • A inicialização do k-means na incorporação espectral introduz aleatoriedade; execuções diferentes podem gerar partições diferentes.
  • Não escala graciosamente para espaços de características de muito alta dimensão sem uma cuidadosa seleção de kernel.
  • Fornece apenas rótulos de agrupamento; não oferece um modelo generativo nem uma extensão natural fora da amostra para novos pontos.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Detecta agrupamentos de forma arbitrária, incluindo configurações não convexas e não linearmente separáveis que derrotam o k-means e os modelos de mistura Gaussiana.
  • Pode operar em qualquer matriz de similaridade par a par, não apenas distâncias euclidianas, tornando-o aplicável a grafos, strings e outros dados estruturados.
  • A heurística do eigengap fornece uma orientação principiada e orientada por dados para a escolha do número de agrupamentos k.
  • Fundamentado em uma rica teoria espectral de grafos, permitindo análise formal de convergência e qualidade do agrupamento.
  • Conceitualmente simples e facilmente implementado usando bibliotecas padrão de álgebra linear.

Aplicações

  • Segmentação de imagem: particionamento de pixels ou superpixels em regiões perceptual e coherentemente unidas usando similaridade de características em nível de pixel.
  • Detecção de comunidades em redes sociais e biológicas onde a conectividade par a par, em vez de vetores de características, define a estrutura.
  • Bioinformática: agrupamento de genes ou proteínas por similaridade de perfil de expressão, onde agrupamentos de expressão raramente são convexos no espaço gênico.
  • Processamento de linguagem natural: agrupamento de documentos ou sentenças usando kernels de similaridade semântica.
  • Visão computacional: segmentação de movimento e particionamento de nuvens de pontos onde os limites dos agrupamentos são irregulares.
  • Análise exploratória de dados: revelação de estrutura de agrupamento não óbvia antes da aplicação de métodos confirmatórios.

Como funciona

Como funciona

1

Uma matriz de similaridade (afinidade) par a par W é construída a partir dos dados. A escolha mais comum é o kernel Gaussiano (RBF), que atribui alto peso a pares próximos e peso próximo de zero a pares distantes. O parâmetro de largura de banda sigma controla a rapidez com que a similaridade decai com a distância; escolhê-lo bem é crítico. Alternativamente, um grafo k-vizinhos mais próximos pode ser usado para representações mais esparsas em grandes conjuntos de dados.

Fórmula
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

A matriz de grau D é a matriz diagonal cuja i-ésima entrada é a soma da i-ésima linha de W. De W e D, o Laplaciano do grafo normalizado (simétrico) L_sym é formado. Esta matriz captura a estrutura completa de conectividade do grafo de similaridade; seu espectro de autovalores revela quantos agrupamentos naturais os dados contêm e quão claramente separados eles estão.

Fórmula
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}
3

Os k autovetores correspondentes aos k menores autovalores de L_sym são calculados. Esses autovetores formam as colunas da matriz de incorporação U, que tem uma linha por ponto de dados. Neste espaço espectral k-dimensional, pontos que pertencem ao mesmo agrupamento são aproximados, mesmo que estivessem intercalados no espaço de características original.

Fórmula
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]
4

Cada linha de U é dividida por sua norma euclidiana para projetar os pontos incorporados na hiperesfera unitária. Essa normalização, introduzida por Ng, Jordan e Weiss, remove diferenças espúrias de escala entre autovetores e garante que o passo subsequente de k-means se concentre na estrutura angular da incorporação, em vez de na magnitude.

Fórmula
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}
5

O agrupamento k-means padrão é aplicado às linhas da matriz de incorporação normalizada T. Como a incorporação espectral já desentrelaçou a geometria dos agrupamentos, o k-means encontra partições significativas mesmo para formas de agrupamento não convexas. Os rótulos dos agrupamentos são então mapeados de volta para os pontos de dados originais.

Erros comuns

  • Escolha de sigma sem validação cruzada principiada ou auto-ajuste; uma largura de banda muito pequena cria um grafo desconectado, enquanto uma muito grande funde agrupamentos distintos.
  • Negligência na normalização das linhas da matriz de afinidade antes do k-means (o passo de normalização de linha de Ng et al. é essencial para estabilidade).
  • Ignorar o eigengap: usar um k fixo sem inspecionar o espectro de autovalores frequentemente leva a sub ou supersegmentação.
  • Aplicar o algoritmo completo a conjuntos de dados com dezenas de milhares de pontos sem mudar para uma variante aproximada ou esparsa.
  • Confundir Laplacianos não normalizados (L = D - W) e normalizados (L_sym, L_rw), que podem alterar as atribuições de agrupamento substancialmente.

Perguntas frequentes

Como escolho o número de agrupamentos k?

A heurística do eigengap é a orientação padrão: calcule os autovalores do Laplaciano normalizado em ordem crescente e procure o maior intervalo entre autovalores consecutivos. O índice onde este intervalo ocorre sugere o número natural de agrupamentos. Quando o eigengap é ambíguo, abordagens baseadas em estabilidade — executar o algoritmo para vários valores de k e comparar as atribuições de agrupamento entre perturbações — podem ajudar.

Como devo definir a largura de banda sigma do kernel Gaussiano?

Uma heurística comum é a mediana das distâncias par a par no conjunto de dados, ou um esquema de auto-ajuste de vizinhos mais próximos (Zelnik-Manor & Perona, 2004) que atribui uma largura de banda local a cada ponto. Na prática, sigma deve ser validado inspecionando a conectividade do grafo de afinidade resultante: cada ponto deve ter pelo menos alguns vizinhos de alto peso, e o grafo não deve se fragmentar em componentes isolados.

Por que o passo de normalização de linha é necessário?

Os autovetores do Laplaciano podem diferir substancialmente em escala. Sem normalizar cada linha da matriz de incorporação para comprimento unitário, o passo de k-means pode ser dominado por autovetores com grandes magnitudes e ignorar componentes informativos, mas de menor magnitude. A normalização de linha introduzida por Ng, Jordan e Weiss mapeia todos os pontos para a esfera unitária para que o k-means responda à geometria angular da incorporação.

O agrupamento espectral pode lidar com conjuntos de dados muito grandes?

Não em sua forma ingênua, que requer memória O(n^2) e tempo O(n^3) para decomposição em autovalores. Para n grande, remédios padrão incluem: construir um grafo esparso de k-vizinhos mais próximos em vez de uma matriz de afinidade completa; usar a aproximação de Nystrom para estimar autovetores a partir de uma subamostra; ou aplicar SVD randomizado. Esses métodos aproximados recuperam a maior parte da precisão a uma fração do custo.

Métodos relacionados

Fontes

  1. Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 14, 849–856.

    Abrir referência da publicação
    Copiado.
  2. von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.

    Abrir referência DOI
    Copiado.
  3. Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.

    Abrir referência DOI
    Copiado.