Resumo Técnico: Agrupar e depois Incorporar: Uma Abordagem Modular para Visualização

Declaração do Problema

Métodos de redução de dimensionalidade, particularmente t-SNE e UMAP, são amplamente utilizados para visualizar dados de alta dimensão com estruturas agrupadas latentes. Embora esses métodos agrupem pontos de dados de forma eficaz e preservem informações locais, eles são conhecidos por distorcer a geometria global dos dados subjacentes. Especificamente, eles frequentemente falham em preservar as posições relativas, distâncias e tamanhos de diferentes clusters. Essa limitação decorre do "problema do adensamento" (crowding problem), onde os espaços de incorporação de baixa dimensão carecem de capacidade suficiente para acomodar todos os pontos em suas escalas de distância originais de alta dimensão, levando ao colapso de pontos distantes e à sobreposição de clusters distintos. Métodos existentes frequentemente forçam um compromisso entre a preservação da estrutura local (separação de clusters) e a preservação das distâncias globais.

Metodologia: O Framework Cluster+Embed (C+E)

Os autores propõem um framework modular de três etapas chamado Cluster+Embed (C+E) para abordar o compromisso entre fidelidade local e global. A abordagem desacopla o agrupamento (clustering), a incorporação local e o alinhamento global, permitindo que o analista selecione algoritmos específicos para cada etapa com base em seus objetivos de visualização.

Etapa 1: Agrupamento (Clustering)

Os dados $\{x_i\}_{i=1}^n$ são primeiro particionados em $\kappa$ clusters ($C_1, \dots, C_\kappa$) usando qualquer algoritmo de agrupamento escolhido (ex: Leiden, DBSCAN, k-means). Esta etapa revela explicitamente a estrutura de clusters presente nos dados. Pontos identificados como ruído podem ser descartados nesta fase.

Etapa 2: Incorporação de Cluster Individual

Cada cluster $C_l$ é incorporado separadamente em um espaço de baixa dimensão (tipicamente $\mathbb{R}^2$) usando um método de incorporação escolhido (ex: PCA, Isomap, TriMap).

• Justificativa: Incorporar clusters individualmente reduz a distorção em comparação com a incorporação de todo o conjunto de dados de uma só vez, pois o "problema do adensamento" é mitigado em subconjuntos menores e localizados.
• Escalonamento: Se o método de incorporação depender de informação ordinal, um fator de escala $\gamma_l$ é aplicado a cada cluster para minimizar a perda quadrática entre as distâncias incorporadas e as dissimilaridades originais.

Etapa 3: Alinhamento Global

Os clusters incorporados são alinhados em uma única incorporação global usando apenas transformações rígidas (translações, rotações e reflexões). O objetivo é posicionar os clusters em relação uns aos outros de modo que as dissimilaridades par a par entre pontos em diferentes clusters sejam preservadas o mais fielmente possível.

• Otimização: O alinhamento minimiza uma função de estresse (estresse de Kruskal) definida como:
  $$\min_{T_1, \dots, T_\kappa} \sum_{1 \le i < j \le \kappa} \sum_{l \in C_i} \sum_{m \in C_j} (\delta_{lm} - \|T_i(y_l) - T_j(y_m)\|)^2$$
  onde $\delta_{lm}$ é a dissimilaridade original e $T$ representa transformações rígidas.
• Mitigação do Adensamento via Escalonamento ($\alpha$): Para evitar a sobreposição na visualização final, os autores introduzem um parâmetro de ajuste $\alpha \ge 1$. A distância alvo entre os clusters é escalonada para $\alpha \delta_{lm}$. Isso efetivamente infla o espaço entre os clusters no mapa de baixa dimensão, evitando o problema do adensamento.
  • $\alpha$ pode ser ajustado manualmente ou automaticamente. Uma heurística automática é proposta: $\alpha = \max(1, \frac{\kappa \tau}{2\pi \Delta})$, onde $\tau$ é o diâmetro médio do cluster e $\Delta$ é a distância média inter-cluster.

Principais Contribuições

1. Framework Modular: O artigo introduz uma abordagem modular transparente, onde o agrupamento, a incorporação e o alinhamento são etapas distintas. Isso permite que os usuários escolham algoritmos específicos para cada etapa visando propriedades de visualização específicas (ex: usar TriMap para recall de kNN ou PCA para preservação de distância).
2. Controle Explícito da Geometria Global: Ao contrário do t-SNE e UMAP, que lidam de forma implícita e muitas vezes opaca com a estrutura global através de dinâmicas de forças direcionadas, o C+E otimiza explicitamente a preservação das distâncias inter-cluster via alinhamento rígido.
3. Solução para o Problema do Adensamento: O método aborda o problema do adensamento não alterando o kernel (como o t-SNE faz com o kernel de Cauchy), mas escalonando explicitamente as distâncias inter-cluster via o parâmetro $\alpha$, garantindo que os clusters distintos não se sobreponham enquanto mantêm sua organização relativa.
4. Transparência: A abordagem é mais interpretável do que os métodos de ponta a ponta porque a preservação da estrutura local (dentro dos clusters) e da estrutura global (entre os clusters) é tratada por mecanismos separados e controláveis.

Resultados Experimentais

Os autores avaliaram o C+E em conjuntos de dados sintéticos e do mundo real (MNIST, dados de organoides cerebrais humanos, dados de córtex de camundongo) contra baselines incluindo t-SNE, UMAP, PCA, Isomap, PHATE e TriMap.

• Dataset de Formas Sintéticas: O C+E alcançou métricas locais perfeitas (recuperando configurações exatas de clusters) e manteve a orientação global, enquanto o t-SNE e o UMAP introduziram distorção local significativa.
• MNIST: O C+E separou clusters com sucesso e os organizou em agrupamentos significativos (ex: agrupando dígitos semelhantes). Enquanto o t-SNE mostrou um recall de kNN superior para $k$ pequeno, o C+E superou o t-SNE e o UMAP em métricas globais (preservação de classe e preservação de distância inter-cluster).
• Dados de Organoides Cerebrais Humanos: As incorporações do C+E revelaram uma trajetória de desenvolvimento temporal clara e agrupamentos distintos de tipos celulares. Preservou métricas globais comparáveis ou superiores ao PCA e L-Isomap, oferecendo simultaneamente melhor estrutura local e menos colapso do que o t-SNE ou UMAP.
• Dados de Córtex de Camundongo: O C+E revelou uma estrutura de grosso a fino (separando neurônios inibitórios/excitatórios e não-neurônios) que não estava presente em outros métodos. Embora a escala da incorporação tenha sido inflada (levando a um estresse normalizado mais alto), métricas globais invariantes de escala favoreceram o C+E sobre o UMAP e o t-SNE.

Significância e Alegações

O artigo afirma que o C+E oferece uma alternativa competitiva aos métodos de visualização existentes ao estabelecer um equilíbrio entre uma incorporação local fiel e uma organização global fiel.

• Gestão de Compromisso (Trade-off): O método reconhece o compromisso inerente entre a preservação local e global, mas fornece um mecanismo (o parâmetro $\alpha$) para gerenciar explicitamente esse compromisso.
• Flexibilidade: O framework permite que os usuários priorizem métricas específicas (ex: recall de kNN via TriMap ou preservação de distância via PCA) sem sacrificar o arranjo global dos clusters.
• Limitações: Os autores observam modestamente que o t-SNE continua sendo o estado da arte para maximizar o recall de kNN para $k$ pequeno. Eles sugerem que o recall de kNN do C+E pode ser melhorado aumentando $\alpha$ ou criando mais clusters, embora isso corra o risco de introduzir falsos clusters. A complexidade computacional da etapa de alinhamento escala quadraticamente com o número de pontos, embora estratégias de subamostragem sejam empregadas para mitigar isso.

Em conclusão, os autores argumentam que o C+E fornece uma abordagem mais transparente e controlável para visualizar dados agrupados, preservando tanto a geometria interna dos clusters quanto o posicionamento relativo dos próprios clusters, o que é frequentemente perdido nas populares técnicas de redução de dimensionalidade não lineares.