Extending TCLUST to higher dimensions

Resumo Técnico: Estendendo o TCLUST para Dimensões Superiores via tHDDC

Definição do Problema
Outliers distorcem significativamente os resultados dos métodos de agrupamento padrão, frequentemente levando a partições não confiáveis onde clusters significativos são fundidos ou clusters espúrios são detectados. Embora técnicas de agrupamento robustas baseadas em poda (trimming), como o TCLUST (Trimmed Clustering), tenham sido desenvolvidas para mitigar esses problemas, elas enfrentam limitações severas em configurações de alta dimensionalidade. À medida que a dimensionalidade $p$ aumenta, o TCLUST enfrenta dificuldades devido a dois fatores principais: a complexidade computacional de estimar um grande número de parâmetros associados a estruturas de covariância completas e a dificuldade de inicializar o algoritmo de forma eficaz. Por outro lado, abordagens alternativas como o Robust Linear Grouping (RLG), que assumem que os clusters residem próximos a subespaços de menor dimensão, oferecem redução de dimensionalidade, mas sofrem com suposições simplificadoras, como erros ortogonais isotrópicos e dificuldades em lidar com subespaços que se interceptam.

Metodologia: A Abordagem tHDDC
Para abordar essas limitações, os autores propõem o tHDDC (Trimmed High-Dimensional Data Clustering), um método que unifica a robustez do TCLUST com a modelagem de subespaço do HDDC (High-Dimensional Data Clustering).

• Estrutura do Modelo: O tHDDC assume que os dados provêm de uma mistura de $G$ componentes gaussianos. Diferente do TCLUST, que estima matrizes de covariância completas, o tHDDC adota uma estrutura parcimoniosa onde cada cluster $g$ está concentrado em torno de um subespaço afim $B_g$ de dimensão intrínseca $q_g$ (onde $q_g < p$).
• Estrutura de Covariância: A matriz de dispersão $\Sigma_g$ para cada cluster é decomposta em um subespaço específico $B_g$ (espalhado pelos $q_g$ autovetores correspondentes aos maiores autovalores $\lambda_{g1}, \dots, \lambda_{gq_g}$) e um complemento ortogonal $B_g^\perp$. Em $B_g^\perp$, a variância é modelada por um único parâmetro comum $\lambda_g$. Isso reduz significativamente o número de parâmetros em comparação com a estimativa de covariância completa.
• Poda e Restrições: O método incorpora um nível de poda $\alpha$ para excluir as observações mais discrepantes (outliers). Para garantir a bem-postura matemática e evitar soluções degeneradas, duas restrições de razão de autovalores são impostas:
  1. Uma restrição $c_1$ sobre a razão dos maiores autovalores dentro dos subespaços.
  2. Uma restrição $c_2$ sobre a razão dos menores autovalores (a variância de ruído comum $\lambda_g$) entre os clusters.
• Algoritmo: Os autores apresentam um algoritmo viável baseado em "passos de concentração" (C-steps), uma adaptação do algoritmo EM. O procedimento envolve:
  1. Inicialização Aleatória: Seleção de pequenos subconjuntos de observações para inicializar os parâmetros do subespaço.
  2. C-steps: Atualização iterativa dos pesos de pertencimento (podando as observações de menor verossimilhança), atualização das médias dos clusters e atualização dos parâmetros do subespaço.
  3. Truncamento de Autovalores: Um procedimento específico é introduzido para aplicar as restrições de autovalores ($c_1, c_2$) após cada atualização, estendendo os métodos de truncamento usados no TCLUST.
  4. Estimativa da Dimensão Intrínseca: Um procedimento baseado no critério de Cattell é integrado para estimar automaticamente as dimensões intrínsecas $q_g$, utilizando uma penalidade de complexidade para evitar o sobreajuste (overfitting).

Principais Contribuições

1. Extensão Teórica: O artigo estabelece a existência e a consistência dos estimadores tHDDC sob condições moderadas, provando que o maximizador da população existe mesmo para distribuições de cauda pesada, desde que um nível de poda estritamente positivo seja utilizado.
2. Inovação Algorítmica: Um novo algoritmo de C-step é desenvolvido para lidar com a parametrização parcimoniosa específica do HDDC, integrando simultaneamente a poda robusta e as restrições de autovalores do TCLUST. Isso inclui um novo mecanismo de truncamento de autovalores para satisfazer as duplas restrições ($c_1, c_2$).
3. Seleção Automática de Dimensão: Os autores propõem um método para determinar automaticamente as dimensões intrínsecas $q_g$ dos subespaços, reduzindo a necessidade de especificação manual e mitigando o risco de sobreajuste através de um critério de verossimilhança penalizado pela complexidade.
4. Ferramentas de Diagnóstico: O artigo introduz ferramentas gráficas de diagnóstico, incluindo distâncias de escore (score distances) e distâncias ortogonais, para avaliar a adequação dos clusters e detectar anomalias, bem como "fatores discriminantes" para avaliar a confiabilidade das atribuições de cluster e das decisões de poda.

Resultos

• Estudo de Simulação: Experimentos com dados sintéticos em 200 dimensões ($p=200$) com graus variados de sobreposição de clusters e orientação de subespaço mostram que o tHDDC alcança uma precisão de classificação quase perfeita em todos os cenários. Em contraste, o TCLUST apresenta desempenho insatisfatório em altas dimensões, e o RLG falha quando os subespaços se interceptam. Além disso, o tHDDC é aproximadamente 2,5 a 3 vezes mais rápido computacionalmente que o TCLUST sob condições comparáveis.
• Aplicação em Dados Reais: O método foi aplicado a um conjunto de dados de dígitos manuscritos (USPS358) contaminado com outliers artificiais e reais. O tHDDC alcançou um erro de classificação de aproximadamente 7% (em dados não podados), superando significativamente o TCLUST (erro > 38%) e o HDDC não robusto (erro > 39%). A análise identificou e removeu com sucesso os outliers artificiais, preservando a estrutura dos clusters de dígitos.

Significância e Alegações
O artigo alega que o tHDDC fornece uma solução robusta e computacionalmente eficiente para o agrupamento em configurações de dimensionalidade moderadamente alta, onde métodos tradicionais como o TCLUST falham devido à explosão de parâmetros e sensibilidade à inicialização. Ao combinar as suposições de subespaço do HDDC com a poda robusta do TCLUST, o método oferece uma alternativa menos simplista ao RLG, capaz de lidar com subespaços que se interceptam e erros não isotrópicos. Os autores enfatizam que a metodologia é particularmente valiosa para conjuntos de dados com estruturas de clusters desconhecidas e contaminação, oferecendo tanto maior precisão quanto redução no custo computacional em comparação com as técnicas existentes de agrupamento robusto de alta dimensão. Trabalhos futuros incluem extensões para dados funcionais e estratégias de poda por célula (cellwise trimming).