Resumo Técnico: ExDBSCAN – Explicando DBSCAN com Raciocínio Contrafactual

Declaração do Problema

A agrupamento (clustering) é uma técnica fundamental de aprendizado não supervisionado, mas sofre de uma lacuna significativa de interpretabilidade em comparação com o aprendizado supervisionado. Embora explicações contrafactuais (ECs) tenham se tornado um padrão para explicar modelos supervisionados, identificando mudanças mínimas na entrada que alteram previsões, elas não são diretamente aplicáveis ao agrupamento. Essa lacuna é particularmente aguda para o DBSCAN (Agrupamento Espacial Baseado em Densidade para Aplicações com Ruído), um algoritmo popular capaz de encontrar clusters de formato arbitrário e identificar ruído.

O DBSCAN atribui pontos como núcleo, fronteira ou ruído com base na alcançabilidade por densidade definida pelos parâmetros $\varepsilon$ e $minPts$. No entanto, ele não oferece insights sobre por que um ponto específico recebeu sua atribuição ou se essa atribuição é robusta a pequenas mudanças nos dados. Os métodos existentes de EC enfrentam três obstáculos principais ao serem aplicados ao DBSCAN:

1. Falta de Diferenciabilidade: O DBSCAN não utiliza uma função de perda diferenciável, impedindo o uso de métodos de busca baseados em gradiente comuns na geração de EC supervisionada.
2. Ausência de Probabilidades: Diferentemente dos modelos de classificação, o DBSCAN fornece memberships discretas baseadas em conectividade, em vez de probabilidades de classe contínuas, das quais muitos métodos de EC agnósticos ao modelo dependem.
3. Estrutura de Similaridade Complexa: A conectividade por densidade do DBSCAN significa que dois pontos podem estar próximos no espaço euclidiano, mas efetivamente distantes em termos de membership no cluster (requerendo um longo caminho conectado por densidade). Métricas de distância euclidiana padrão usadas por outros métodos de EC falham em capturar isso, potencialmente gerando contrafactuais redundantes ou inválidos.

Metodologia: ExDBSCAN

Os autores propõem o ExDBSCAN, o primeiro método de explicação post-hoc adaptado especificamente para o DBSCAN. Ele gera contrafactuais acionáveis tanto para transições de ruído-para-cluster quanto de cluster-para-cluster, com garantias teóricas de validade.

Componentes Principais

1. Representação de Similaridade Baseada em Grafos:
   Em vez de depender da distância euclidiana, o ExDBSCAN modela a estrutura do cluster como um grafo ponderado não direcionado $G(V, E)$.

   • Vértices ($V$): Representam os pontos centrais (núcleos) de um cluster.
   • Arestas: Conectam dois vértices se eles forem diretamente alcançáveis por densidade (distância $< \varepsilon$).
   • Pesos: A distância euclidiana entre pontos centrais conectados.
   • Métrica de Distância: A distância entre quaisquer dois pontos é definida como o caminho mais curto ponderado em $G$. Isso garante que a "proximidade" respeite a estrutura de conectividade por densidade do cluster.

2. Otimização Inspirada na Física:
   Para gerar um conjunto de $k$ contrafactuais diversos e próximos, o ExDBSCAN modela a seleção de pontos centrais de referência como um problema de minimização de energia física. O sistema trata pontos centrais candidatos como partículas carregadas sujeitas a duas forças:

   • Repulsão (Diversidade): Modelada após a lei de Coulomb, os pontos centrais candidatos repelem-se mutuamente. A força de repulsão é inversamente proporcional à distância do caminho mais curto ponderado entre eles. Isso garante que os contrafactuais selecionados estejam distribuídos pela estrutura de densidade do cluster, evitando redundância.
   • Atração (Proximidade): Modelada após a lei de Hooke (forças de mola), os pontos centrais candidatos são atraídos para a instância original $p$ a ser explicada. A força aumenta linearmente com a distância, enviesando a seleção para os pontos centrais válidos mais próximos.

   A energia total $E_{C'}$ de um conjunto de pontos centrais selecionados $C'$ é definida como:
   $$E_{C'} = \sum_{V_i \in C'} \sum_{V_j \in C': j > i} \frac{1}{D(V_i, V_j)} + \sum_{V_i \in C'} d^2(p, V_i)$$
   Onde $D$ é a distância do grafo ponderado e $d$ é a distância euclidiana até o ponto original.

3. Otimização e Construção:

   • NP-Dificuldade: Encontrar o conjunto ótimo de pontos centrais para minimizar essa energia é provado ser NP-difícil. O ExDBSCAN emprega um algoritmo ganancioso para aproximar a solução. Ele seleciona iterativamente o ponto central que minimiza a energia total do sistema dado o conjunto atualmente selecionado.
   • Geração de Contrafactuais: Uma vez selecionado um conjunto de pontos centrais de referência, os contrafactuais finais são construídos dentro da $\varepsilon$-vizinhança desses núcleos. Especificamente, um contrafactual $p'$ é colocado à distância $\varepsilon$ do núcleo de referência $q$ na direção do ponto original $p$.
   • Garantia de Validade: Por construção, cada contrafactual gerado está dentro de $\varepsilon$ de um ponto central no cluster de destino, garantindo que ele satisfaça os critérios de conectividade por densidade do DBSCAN e seja um membro válido do cluster de destino.

4. Tratamento de Restrições:
   O método leva em conta características não acionáveis (por exemplo, idade, gênero) restringindo o espaço de busca. Ele filtra pontos centrais de modo que suas $\varepsilon$-vizinhanças sejam alcançáveis sem modificar atributos não acionáveis, garantindo que as explicações permaneçam realistas.

Contribuições Principais

• Primeiro Método de EC Específico para DBSCAN: O ExDBSCAN é o primeiro método projetado para gerar explicações contrafactuais especificamente para agrupamento baseado em densidade, cobrindo tanto transições de ruído-para-cluster quanto de cluster-para-cluster.
• Modelo Inovador Inspirado na Física: Os autores introduzem um modelo que equilibra proximidade e diversidade usando repulsão eletrostática e atração tipo mola, levando explicitamente em conta a estrutura de conectividade por densidade do DBSCAN por meio de um grafo ponderado.
• Validade Teórica: O método fornece uma garantia teórica (Teorema 3.1) de que cada contrafactual gerado é válido sob as regras de atribuição do DBSCAN.
• Superioridade Empírica: Avaliação extensa em 30 conjuntos de dados tabulares demonstra que o ExDBSCAN supera as linhas de base existentes (incluindo métodos agnósticos ao modelo como BayCon, DiCE e Growing Spheres) em validade, proximidade e diversidade.

Resultados Experimentais

Os autores avaliaram o ExDBSCAN em 30 conjuntos de dados tabulares do OpenML contra sete linhas de base (incluindo DiCE, BayCon, Growing Spheres e variantes aleatórias).

• Validade: O ExDBSCAN alcançou 100% de validade em todas as consultas. Em contraste, métodos baseados em surrogate (DiCE-Surrogate, GS-Surrogate) e métodos agnósticos ao modelo (BayCon) lutaram significativamente, frequentemente alcançando taxas de validade abaixo de 50%. Isso é atribuído à incompatibilidade entre seus objetivos de otimização contínua e a atribuição discreta e baseada em densidade do DBSCAN.
• Proximidade: Entre os métodos que alcançaram alta validade, o ExDBSCAN produziu contrafactuais significativamente mais próximos das instâncias originais do que os concorrentes. Isso é atribuído à otimização explícita do termo de atração tipo mola usando a distância baseada em grafos.
• Diversidade: O ExDBSCAN alcançou as maiores pontuações de diversidade. Seu mecanismo de repulsão, baseado na distância do caminho mais curto ponderado dentro do grafo do cluster, garantiu que os contrafactuais selecionados representassem alternativas distintas dentro da topologia do cluster, em vez de apenas estarem próximos no espaço euclidiano.
• Tempo de Execução: Embora o ExDBSCAN seja computacionalmente mais intensivo do que uma heurística aleatória simples, ele é geralmente mais rápido do que a otimização pesada exigida pelo DiCE e BayCon, particularmente quando esses métodos falham em encontrar contrafactuais válidos.

Significado e Alegações

O artigo posiciona o ExDBSCAN como um passo crítico para fechar a lacuna de interpretabilidade no aprendizado não supervisionado. Os autores afirmam que, ao aproveitar o raciocínio contrafactual adaptado aos mecanismos específicos do DBSCAN, os praticantes podem obter:

• Insights Acionáveis: Compreender quais características impulsionam a atribuição de um ponto a um cluster ou seu status como ruído.
• Verificações de Robustez: Avaliar se as atribuições de cluster são estáveis ou sensíveis a pequenas perturbações.
• Confiança e Transparência: Fornecer cenários "e se" que refletem a verdadeira estrutura baseada em densidade dos dados, em vez de limites artificiais criados por modelos surrogate.

Os autores notam modestamente que, embora um estudo de usuário formal esteja além do escopo deste trabalho, o método fornece exemplos concretos e teoricamente fundamentados de como as atribuições de cluster podem ser alteradas. Eles sugerem que trabalhos futuros poderiam estender o ExDBSCAN para cenários incrementais ou de streaming e explorar estratégias de otimização mais sofisticadas além da aproximação gananciosa atual.