Sparse $K$-spatial-median clustering for high-dimensional data

1. Formulação do Problema

O artigo aborda os desafios do agrupamento de dados de alta dimensão ($p \gg n$) caracterizados por duas dificuldades específicas:

1. Distribuições de cauda pesada e valores atípicos: Métodos clássicos como K-médias baseiam-se na média aritmética e na perda euclidiana quadrática, tornando-os altamente sensíveis a valores atípicos e ruídos de cauda pesada (por exemplo, distribuições $t$ multivariadas).
2. Variáveis irrelevantes: Em configurações de alta dimensão, uma grande proporção de características frequentemente não carrega informação discriminatória de agrupamento. A inclusão dessas variáveis "ruído" dilui o sinal de agrupamento, causando degradação de desempenho mesmo em métodos robustos, se estes tratarem todas as dimensões de forma igual.

Métodos de agrupamento esparsos existentes (por exemplo, K-médias esparsas) frequentemente utilizam encolhimento contínuo (regularização L1) para reduzir o peso de características irrelevantes, o que pode não produzir exclusão explícita de características e pode ser difícil de ajustar em configurações robustas. Além disso, métodos robustos padrão (como K-medianas) frequentemente carecem de equivariância à rotação, falhando em respeitar a geometria elíptica subjacente dos agrupamentos.

2. Metodologia

Os autores propõem um quadro unificado chamado Agrupamento K-spatial-median esparsos, que integra a estimativa robusta de centros com a seleção explícita de características. O quadro consiste em dois algoritmos complementares:

A. Conceito Central: Mediana Espacial

Em vez da média aritmética (K-médias) ou medianas coordenada a coordenada (K-medianas), o método utiliza a mediana espacial (mediana geométrica) como centro do agrupamento.

• Definição: A mediana espacial $m$ minimiza a soma das distâncias euclidianas: $m = \arg\min \sum \|x_i - m\|_2$.
• Vantagem: É equivariante à rotação (respeita a geometria multivariada) e robusta a caudas pesadas porque a função de perda cresce linearmente em vez de quadraticamente.

B. Algoritmo 1: SM–SSCM (Agrupamento por Mediana Espacial com Covariância de Sinal Espacial Comum)

Esta variante aborda escalas heterogêneas e dependência de características sem exclusão explícita de características.

• Etapa de Atribuição: Em vez da distância euclidiana padrão, utiliza uma métrica do tipo Mahalanobis construída a partir de uma Matriz de Covariância de Sinal Espacial (SSCM) comum.
• Estimação da SSCM: A matriz de dispersão é estimada usando sinais espaciais ($u_i = r_i / \|r_i\|$) dos resíduos, regularizada com um parâmetro de crista para garantir invertibilidade.
• Benefício: Isso adapta a métrica de distância à estrutura de correlação e escala dos dados, melhorando a precisão da atribuição em altas dimensões.

C. Algoritmo 2: SM Esparsos (Agrupamento por Mediana Espacial Esparsos)

Esta variante aborda o regime $p \gg n$ com variáveis irrelevantes introduzindo exclusão de características por limiarização dura.

• Pontuação de Separação: Em cada iteração, uma pontuação $s_j$ é computada para cada característica $j$ com base na dispersão dos centros do agrupamento ao longo daquela coordenada: $s_j = \sum_{k=1}^K |m_{kj} - \bar{m}_j|$.
• Exclusão Dura: Características com pontuações abaixo de um limiar $\tau$ são completamente excluídas da etapa de atribuição. Isso cria um conjunto explícito de variáveis ativas ($S(\tau)$) em vez de encolher pesos continuamente.
• Ajuste (Critério Gap): O limiar $\tau$ é selecionado automaticamente usando uma estatística Gap baseada em permutação. O algoritmo compara a separação entre agrupamentos observada contra uma distribuição de referência gerada permutando colunas (destruindo a estrutura do agrupamento enquanto preserva distribuições marginais). O $\tau$ que maximiza o Gap é selecionado.

D. Propriedades Teóricas

O artigo estabelece consistência de agrupamento e consistência de seleção de características para os métodos propostos sob um modelo elíptico de mistura com caudas sub-Weibull ou polinomiais.

• Consistência: À medida que $n \to \infty$, o algoritmo recupera a partição verdadeira e o conjunto verdadeiro de características informativas com probabilidade tendendo a 1, desde que a separação do sinal seja suficientemente forte em relação ao nível de ruído.
• Robustez: Limites teóricos mostram que a mediana espacial e a métrica SSCM mantêm estabilidade mesmo sob contaminação de cauda pesada.

3. Contribuições Principais

1. Quadro Robusto: Desenvolvimento de um quadro de agrupamento baseado em partição usando medianas espaciais, oferecendo robustez superior a caudas pesadas e valores atípicos em comparação com métodos baseados em média ou medianas coordenada a coordenada.
2. Seleção Explícita de Características: Introdução de um mecanismo de limiarização dura que produz conjuntos interpretáveis e exatos de variáveis retidas e excluídas, evitando a ambiguidade do encolhimento contínuo.
3. Ajuste Orientado por Dados: Proposta de um critério Gap baseado em permutação especificamente projetado para selecionar o limiar de esparsidade em configurações robustas e de alta dimensão.
4. Garantias Teóricas: Prova de consistência tanto para a partição de agrupamento quanto para a recuperação de suporte (seleção de características) sob modelos elípticos gerais com caudas pesadas.

4. Resultados Experimentais

Os autores avaliaram os métodos contra K-médias, K-medianas, K-médias esparsas e K-medianas esparsas usando simulações e dados reais.

• Estudos de Simulação:
  • Caudas Pesadas e Contaminação: Sob distribuições $t$ multivariadas e misturas gaussianas contaminadas, SM Esparsos e SM–SSCM superaram significativamente as linhas de base não robustas. SM Esparsos alcançou o maior Índice Rand Ajustado (ARI) em configurações contaminadas.
  • Altas Dimensões: À medida que a dimensão $p$ aumentava (até 400), métodos não esparsos deterioraram-se rapidamente. SM Esparsos manteve alta estabilidade e precisão, demonstrando a necessidade de exclusão de características.
  • Tipos de Valores Atípicos: O método mostrou resiliência particular contra contaminação célula a célula (corrupção de entradas individuais), onde superou consistentemente os concorrentes.
• Aplicações a Dados Reais:
  • Dados de Proteínas de Camundongos: Em um conjunto de dados de níveis de expressão de proteínas, os métodos propostos alcançaram ARI mais alto e maior estabilidade entre execuções em comparação com métodos clássicos.
  • Conjuntos de Dados de Referência: Testados em 8 conjuntos de dados UCI/KEEL (por exemplo, Iris, Wine, WDBC). Os métodos propostos foram competitivos ou superiores, com SM–SSCM se destacando em conjuntos de dados com correlações complexas e SM Esparsos performando melhor onde a esparsidade de características foi benéfica.

5. Significado

Este artigo fornece um avanço crítico para a análise de dados moderna onde conjuntos de dados são tanto de alta dimensão quanto propensos a valores atípicos.

• Impacto Prático: Oferece um algoritmo iterativo computacionalmente eficiente que não requer solucionadores de otimização complexos (ao contrário de algumas abordagens de verossimilhança penalizada), mas fornece seleção rigorosa de características.
• Insight Teórico: Preenche a lacuna entre estatística robusta (sinais/medianas espaciais) e aprendizado esparsos, provando que a limiarização dura pode ser consistente mesmo na presença de ruído de cauda pesada.
• Aplicabilidade: O método é particularmente valioso em campos como genômica, finanças e análise de imagens, onde os dados frequentemente exibem caudas pesadas, correlações complexas e uma alta proporção de variáveis de ruído.

Em resumo, o Agrupamento K-spatial-median esparsos oferece uma solução robusta, interpretável e teoricamente sólida para o agrupamento de dados de alta dimensão, lidando efetivamente com os duplos desafios de ruído/valores atípicos e características irrelevantes.