Data compression for fast dimension reduction and clustering of high-dimensional discrete data

Resumo Técnico: Compressão de Dados para Redução Rápida de Dimensão e Agrupamento de Dados Discretos de Alta Dimensão

Definição do Problema
Dados discretos de alta dimensão (binários, categóricos e de valores de contagem) são prevalentes em campos como genômica, pesquisa de microbioma e análise comportamental. O agrupamento (clustering) desses dados apresenta desafios significativos: os métodos existentes são frequentemente computacionalmente exigentes, sensíveis à esparsidade e à natureza discreta do espaço amostral, ou projetados especificamente para dados contínuos. Em regimes de alta dimensão onde o número de variáveis $p$ excede ou rivaliza com o tamanho da amostra $n$, as abordagens padrão enfrentam a "maldição da dimensionalidade", onde as distâncias se tornam menos informativas, o ruído domina o sinal e modelos flexíveis tornam-se superparametrizados. Embora a redução de dimensão seja uma estratégia padrão para dados contínuos (ex: via PCA), aplicá-la a dados discretos não é trivial; incorporações (embeddings) ingênuas podem distorcer a estrutura, e muitos métodos específicos para dados discretos dependem de otimização estocástica, matrizes de dissimilaridade de pares ($O(n^2)$) ou pressupostos de distribuição específicos que limitam a escalabilidade e a generalidade.

Metodologia
Os autores propõem um framework de compressão de dados determinístico e não estocástico (denotado como DC) que mapeia observações discretas de alta dimensão para um espaço contínuo de baixa dimensão. O mecanismo central é uma codificação posicional escalonada:

1. Compressão Base-10: O método trata cada vetor de observação discreta $y_i \in \{0, \dots, K-1\}^p$ como um número na base $K$. Uma expansão padrão em base-$K$ resultaria em um mapeamento injetivo para um único número inteiro grande. No entanto, isso é computacionalmente inviável para $p$ grande devido ao crescimento exponencial dos pesos ($K^{p-j}$).
2. Transformação Escalonada: Para garantir a estabilidade numérica, os autores definem uma compressão escalonada $z_i$ onde os pesos são normalizados:
   $$z_i = \sum_{j=1}^p \frac{K^{p-j}}{p K^{1/K}} y_{ij}$$
   Os coeficientes são uniformemente limitados, garantindo que a transformação permaneça estável para $p$ grande e $K$ arbitrário.
3. Extensão Multidimensional: Para visualização ou para preservar mais informação, as variáveis são particionadas em $q$ blocos disjuntos. Cada bloco é comprimido independentemente usando o mesmo esquema de ponderação escalonada, resultando em um vetor contínuo $z_i \in \mathbb{R}^q$.
4. Ordenação de Variáveis: Para maximizar a contribuição de variância das características informativas, as variáveis dentro de cada bloco são ordenadas por ordem decrescente de variância amostral antes da compressão.
5. Agrupamento no Espaço Comprimido: Os dados contínuos de baixa dimensão resultantes $Z$ podem ser agrupados usando algoritmos padrão. Os autores avaliam especificamente k-means e Modelos de Mistura Gaussiana (GMM), observando que as variáveis comprimidas seguem aproximadamente uma distribuição Gaussiana sob condições de regularidade brandas (via Teorema do Limite Central).

Principais Contribuições Teóricas
O artigo estabelece três propriedades teóricas primárias da compressão proposta:

• Injetividade: O mapeamento é injetivo, o que significa que observações discretas distintas são garantidas de mapear para valores comprimidos distintos. Isso evita os "empates" (distâncias idênticas) comuns em métricas de distância discretas como a distância de Hamming.
• Gaussianidade Aproximada: Sob independência e condições de momento brandas, as coordenadas comprimidas são aproximadamente Gaussianas. Isso fornece uma justificativa teórica para o uso de agrupamento baseado em modelos (GMM) no espaço comprimido.
• Preservação de Centróides: A separação entre os centróides dos clusters no espaço original de alta dimensão é preservada no espaço comprimido. Se os centróides originais diferem em pelo menos uma coordenada, seus contrapartes comprimidos permanecem distintos. Isso garante que estruturas de agrupamento baseadas em localização permaneçam identificáveis após a redução de dimensão.

Resultados Empíricos
Os autores conduziram simulações extensas através de cinco cenários: dados de contagem independentes, dados de contagem correlacionados, dados binários, dados de contagem com ruído e variando tamanhos de amostra/dimensões ($n \in \{50, 200\}$, $p \in \{100, 5000\}$). O método proposto (DC) foi comparado contra PCA, t-SNE, Multidimensional Scaling (MDS), Spectral Clustering e k-means padrão.

• Acurácia: O agrupamento baseado em DC alcançou consistentemente altos valores de Índice Rand Ajustado (ARI), muitas vezes com recuperação quase perfeita dos clusters verdadeiros, superando técnicas de redução de dimensão concorrentes. O desempenho permaneceu robusto mesmo com variáveis correlacionadas e altas proporções de características de ruído.
• Robustez: Embora o k-means tenha performado bem em configurações limpas, o GMM (via pacote mclust) provou ser superior em cenários ruidosos, onde o ruído induziu geometrias de cluster não esféricas.
• Eficiência Computacional: O DC demonstrou melhorias substanciais de velocidade. Foi aproximadamente 14 vezes mais rápido que o MDS, 20 vezes mais rápido que o PCA e 181 vezes mais rápido que o t-SNE. A complexidade do DC é $O(np)$, comparada a $O(n^2p)$ para MDS e $O(n^2)$ para t-SNE.
• Aplicações: O método foi aplicado a registros de nomes de bebês irlandeses e dados de microbioma (comparando caçadores-coletores Hadza e adultos urbanos italianos), demonstrando utilidade prática para conjuntos de dados discretos de alta dimensão do mundo real.

Significância e Alegações
O artigo afirma oferecer um framework de agrupamento de dados discretos de alta dimensão que é escalável, computacionalmente eficiente e amplamente aplicável. Sua significância reside em preencher a lacuna entre a necessidade de redução de dimensão e as limitações dos métodos existentes para dados discretos. Ao fornecer uma transformação determinística, injetiva e numericamente estável, a abordagem permite que pesquisadores utilizem algoritmos de agrupamento padrão e eficientes (como k-means e GMM) em dados discretos sem o ônus computacional de ajustar modelos de mistura discretos de alta dimensão ou calcular dissimilaridades de pares. Os autores enfatizam que o método preserva a estrutura essencial de agrupamento (separação de centróides) enquanto converte os dados discretos em uma forma contínua adequada para modelagem Gaussiana, mitigando efetivamente a maldição da dimensionalidade para observações discretas.