Class Angular Distortion Index for Dimensionality Reduction

1. Declaração do Problema

Técnicas de Redução de Dimensionalidade (DR) (por exemplo, t-SNE, UMAP, PCA) são essenciais para visualizar dados de alta dimensão. No entanto, uma limitação crítica na avaliação atual de DR é a representação enganosa das relações entre clusters.

• A Questão Central: Embora muitos métodos de DR consigam separar clusters (tornando-os "manchas" distintas), eles frequentemente distorcem as relações geométricas globais entre esses clusters. Por exemplo, estruturas aninhadas, variedades curvas ou clusters entrelaçados podem ser achatados ou rearranjados arbitrariamente na projeção.
• Limitações das Métricas Existentes: As métricas de qualidade atuais falham em capturar essas distorções porque dependem de premissas falhas:
  • Premissa de Separabilidade: Métricas como Silhouette Score e Davies-Bouldin Index assumem que os clusters são compactos, globulares e bem separados. Elas recompensam projeções que criam "manchas" apertadas e isoladas, mesmo que isso destrua a verdadeira estrutura topológica (por exemplo, transformar esferas aninhadas em círculos separados).
  • Viés de Centróide: Métricas como Label Trustworthiness & Continuity (Label-T&C) dependem de centróides de clusters. Se os clusters se sobrepõem ou são aninhados (centróides coincidem), essas métricas falham em distinguir entre uma projeção fiel e uma aleatória.
  • Pontual vs. Nível de Cluster: A maioria das métricas avalia distâncias ponto a ponto ou pares de pontos, perdendo relações geométricas de ordem superior entre grupos de pontos.

2. Metodologia: Class Angular Distortion Index (CADI)

Os autores propõem o CADI, uma nova métrica projetada para avaliar a preservação de relações geométricas inter-cluster usando ângulos internos.

Conceito Central

Em vez de medir distâncias entre centróides ou pontos individuais, o CADI mede os ângulos internos formados por tripletos de pontos, onde o ponto de referência pertence a uma classe e os outros dois pontos pertencem a uma classe diferente.

• Intuição: Ao observar como um cluster $C_b$ "parece" da perspectiva de um ponto no cluster $C_a$ (via o ângulo $\angle jik$), a métrica captura a forma e a orientação relativa dos clusters.
• Diferenciabilidade: Como depende da similaridade de cosseno de ângulos, o CADI é diferenciável, permitindo seu uso como função de perda para otimização.

Definição Matemática

Dado um conjunto de dados $X$ e uma projeção $Y$, com uma partição de classes $C$:
$$\text{CADI}(X, Y, C) = \frac{1}{T} \sum_{i \in C_a, j,k \in C_b, j \neq k} \left( \cos(\theta_X(j,i,k)) - \cos(\theta_Y(j,i,k)) \right)^2$$
Onde:

• $i$ é um ponto de referência na classe $C_a$.
• $j, k$ são pontos em uma classe diferente $C_b$.
• $\theta$ representa o ângulo interno em $i$ formado pelos vetores para $j$ e $k$.
• $T$ é o número total de tripletos amostrados.
• Objetivo: Minimizar o CADI (valores mais próximos de 0 são melhores).

Implementação Prática

• Amostragem: Calcular a soma completa é $O(n^3)$. Os autores demonstram que amostrar $k = O(n)$ tripletos (especificamente $40n$) produz resultados estáveis com variância negligenciável, tornando a métrica escalável.
• Invariância: O CADI é invariante a translação, rotação e escala uniforme, pois depende exclusivamente de ângulos.
• AngleEmbedding: Os autores introduzem um novo algoritmo de DR, o AngleEmbedding, que usa o CADI como função de perda otimizada via uma rede neural paramétrica (rede feedforward) para gerar projeções que preservam especificamente relações angulares inter-classes.

3. Contribuições Principais

1. Nova Métrica (CADI): Uma métrica de qualidade em nível de cluster que vai além das premissas de "globularidade" e "separabilidade" das métricas existentes. Ela visa especificamente a preservação de estruturas complexas como clusters aninhados, curvos ou entrelaçados.
2. Demonstração de Modos de Falha: O artigo fornece evidências extensas de que métricas existentes (Silhouette, Label-T&C, etc.) frequentemente classificam projeções aleatórias ou projeções de "manchas" mais alto do que projeções que preservam fielmente topologias complexas.
3. Algoritmo AngleEmbedding: Uma técnica supervisionada de DR inovadora que otimiza o CADI, provando que a métrica pode ser usada efetivamente para impulsionar a geração de projeções de alta fidelidade.
4. Benchmarking Abrangente: Avaliação em mais de 20 conjuntos de dados sintéticos e do mundo real (incluindo esferas aninhadas, anéis, expressão gênica e dados de texto), comparando o CADI com outras 8 métricas e 8 algoritmos de DR.

4. Resultados

A avaliação destaca discrepâncias significativas entre o CADI e as métricas existentes:

• Dados Sintéticos (Esferas Aninhadas e Anéis):
  • Cenário: Os dados consistem em 5 esferas aninhadas ou uma cadeia de anéis intertravados.
  • Métricas Existentes: Silhouette Score e Label-T&C frequentemente classificam t-SNE ou UMAP (que quebram os anéis em manchas separadas ou dispersam as esferas) como os melhores, ou até classificam Projeções Aleatórias altamente porque os centróides se sobrepõem.
  • CADI: Identifica corretamente o AngleEmbedding e o PCA (que preservam a ordenação linear ou aninhada) como os melhores, atribuindo as piores pontuações aos métodos que destroem a topologia.
• Dados do Mundo Real (Fígado, USPS, TREC):
  • Dados de Fígado: Células cancerígenas (HCC) têm maior variância do que células saudáveis. O t-SNE cria manchas de tamanho igual e separadas, escondendo essa variância. O CADI recompensa o AngleEmbedding e o PCA, que mostram corretamente o cluster HCC como mais disperso.
  • USPS (Dígitos): Os tamanhos dos clusters variam significativamente por dígito. O t-SNE força clusters de tamanho igual. O CADI recompensa projeções onde os tamanhos dos clusters refletem a verdadeira distribuição dos dados (preservada pelo AngleEmbedding).
  • Correlação: O CADI mostra baixa correlação com outras métricas (por exemplo, correlação de Spearman com Silhouette é ~0,24), confirmando que mede um aspecto distinto da qualidade da projeção.
• Ajuste de Hiperparâmetros: O CADI foi usado com sucesso para orientar a seleção de hiperparâmetros para o UMAP, identificando configurações que preservam melhor a estrutura global mesmo quando a inspeção visual é ambígua.

5. Significado e Conclusão

• Mudança de Paradigma: O artigo argumenta que, para tarefas envolvendo análise de relações entre clusters (por exemplo, entender hierarquia, aninhamento ou topologia global), as métricas atuais focadas em "separabilidade" são enganosas. O CADI oferece uma alternativa necessária para avaliar a fidelidade estrutural.
• Seleção de Ferramentas: Os autores esclarecem os casos de uso apropriados:
  • Use t-SNE/UMAP se o objetivo for simplesmente identificar o número de clusters ou para exploração inicial.
  • Use CADI/AngleEmbedding se o objetivo for entender como os clusters se relacionam entre si, suas posições relativas e suas formas geométricas.
• Trabalho Futuro: Os autores sugerem estender o AngleEmbedding para espaços não euclidianos (esferas, hiperboloides) e realizar análises teóricas mais aprofundadas sobre a agregação de erros angulares.

Em resumo, o CADI aborda uma lacuna crítica na avaliação de redução de dimensionalidade ao quantificar a distorção da geometria inter-cluster, fornecendo um guia mais confiável para analistas que trabalham com estruturas de dados complexas e não globulares.