Measuring Distortion in the Empty Regions of Dimensionality Reduction Scatterplots with the Gap Index

Resumo Técnico: Medindo a Distorção nas Regiões Vazias de Gráficos de Dispersão de Redução de Dimensionalidade com o Índice de Lacuna (Gap Index)

Problema
A Redução de Dimensionalidade (RD) é essencial para visualizar dados de alta dimensão, mas todas as projeções acarretam distorção, a menos que os dados residam em uma variedade (manifold) 2D. Embora existam métricas de qualidade para quantificar essa distorção, as métricas populares atuais (ex: estresse, confiabilidade, continuidade) focam primariamente na preservação de relações entre pontos de dados, como distâncias par a par ou vizinhanças. Essas métricas frequentemente falham em capturar distorções nas "regiões vazias" ou lacunas entre os pontos. No entanto, esses espaços vazios são visualmente críticos; eles definem a separação entre clusters e a estrutura percebida pelos usuários. Consequentemente, as métricas podem reportar alta qualidade (baixa distorção) mesmo quando uma projeção cria padrões espúrios ou separações enganosas no espaço vazio, levando à excessiva confiança na análise visual.

Metodologia: O Índice de Lacuna (Gap Index - GI)
Os autores introduzem o Índice de Lacuna (GI), uma métrica de qualidade projetada para quantificar especificamente a distorção dentro das áreas vazias de uma projeção 2D. O GI opera decompondo o espaço visual em triângulos e comparando sua deformação contra o espaço de alta dimensão. O cálculo segue um pipeline modular:

1. Triangulação: A projeção 2D é particionada em um conjunto de triângulos não sobrepostos usando triangulação de Delaunay. Este método foi escolhido por sua eficiência computacional ($O(N \log N)$), sua capacidade de cobrir o invólucro convexo dos dados e sua propriedade de evitar triângulos finos e numericamente instáveis.
2. Deformação de Triângulos: Para cada triângulo $t_i$ na projeção 2D, o triângulo correspondente $\hat{t}_i$ é identificado no espaço de alta dimensão usando os mesmos três vértices. A deformação é calculada comparando as áreas relativas desses triângulos.
   • A área relativa é definida como a área do triângulo dividida pela soma de todas as áreas dos triângulos no respectivo espaço. Esta normalização garante que a métrica seja invariante à escala.
   • O valor de deformação $D(t_i, \hat{t}_i)$ é computado como a diferença entre as áreas relativas, normalizada pelo máximo das duas. Isso resulta em um valor em $[-1, 1]$, onde valores positivos indicam estiramento (a lacuna é maior em 2D do que em alta dimensão) e valores negativos indicam compressão.
   • Crucialmente, a área do triângulo de alta dimensão pode ser computada usando apenas distâncias par a par (via fórmula de Heron), o que significa que o GI não requer coordenadas explícitas de alta dimensão, apenas uma matriz de distâncias.
3. Agregação: Para produzir uma métrica escalar única, o GI agrega os valores absolutos de deformação de todos os triângulos usando uma média ponderada. O peso $w_i$ para cada triângulo é o máximo de sua área relativa no espaço 2D ou no espaço de alta dimensão. Isso garante que grandes lacunas, visualmente salientes (seja na projeção ou nos dados originais), tenham uma influência maior na pontuação final.
4. Visualização: O GI pode ser sobreposto ao gráfico de dispersão colorindo os triângulos de acordo com seus valores de deformação. Um mapa de cores divergente (azul para compressão, vermelho para estiramento, amarelo para nenhuma distorção) visualiza a distorção regional. Para mitigar o ruído visual das fronteiras dos triângulos, os autores propõem aplicar um desfoque gaussiano (Gaussian blur) ao fundo.

Principais Contribuições

1. Identificação de Limitações: O artigo destaca que as métricas de qualidade padrão são insensíveis a deformações estruturais em regiões vazias que possuem alto impacto visual, podendo induzir o analista ao erro.
2. Proposta de Nova Métrica: Os autores introduzem o Índice de Lacuna, uma métrica que desloca o foco das relações ponto a ponto para a distorção dos espaços vazios (lacunas) entre os pontos.
3. Benchmarking e Implementação: O artigo fornece uma coleção de conjuntos de dados artificiais e reais para testar o GI contra métricas populares (estresse, confiabilidade, continuidade, estabilidade, coesividade). Uma implementação open-source em Python é fornecida para reproduzir os resultados.

Resultos
A avaliação demonstra que o GI é sensível a distorções que outras métricas não detectam:

• Sensibilidade a Artefatos Visuais: No experimento do "conjunto de dados plano" (pontos distribuídos aleatoriamente em um plano 2D imerso em 3D), o PCA produz uma projeção perfeita (GI = 0), enquanto o t-SNE cria lacunas do tipo cluster espúrias. Embora o estresse e a confiabilidade reportem distorção mínima para o t-SNE, o GI identifica corretamente a significativa distorção visual causada pelas lacunas artificiais.
• Interpretabilidade: Em conjuntos de dados sintéticos (ex: um cubo 3D com uma face ausente), a visualização do GI destaca claramente onde o espaço vazio foi esticado ou comprimido, permitindo que os usuários infiram a estrutura original de alta dimensão (ex: identificar que uma grande área vermelha na projeção corresponde a uma face ausente no objeto 3D).
• Desempenho: O GI é computacionalmente eficiente, sendo dominado pela complexidade $O(N \log N)$ da triangulação de Delaunay, tornando-o adequado para grandes conjuntos de dados.

Significância e Alegações
O artigo afirma que o Índice de Lacuna oferece um complemento necessário às métricas de qualidade existentes ao abordar um ponto cego na análise visual: a confiabilidade das regiões vazias. Ao focar nas lacunas que definem clusters e padrões, o GI proporciona uma visão mais holística da qualidade da projeção que se alinha melhor com a percepção humana. Os autores asseguram que o GI é rápido de computar, interpretável e capaz de detectar pequenas deformações estruturais que possuem alto impacto visual, as quais são frequentemente negligenciadas por métricas centradas em pontos. O trabalho revisita e estende conceitos anteriores de triangulação de projeções, formalizando-os em uma métrica de qualidade normalizada e agregada, adequada tanto para avaliação escalar quanto para visualização regional.