Resumen Técnico: ExDBSCAN – Explicando DBSCAN con Razonamiento Contrafactual

Declaración del Problema

El agrupamiento es una técnica fundamental de aprendizaje no supervisado, pero adolece de una brecha significativa de interpretabilidad en comparación con el aprendizaje supervisado. Aunque las explicaciones contrafactuales (EC) se han convertido en un estándar para explicar modelos supervisados al identificar cambios mínimos en la entrada que alteran las predicciones, no son directamente aplicables al agrupamiento. Esta brecha es particularmente aguda para DBSCAN (Agrupamiento Espacial Basado en Densidad de Aplicaciones con Ruido), un algoritmo popular capaz de encontrar agrupaciones de forma arbitraria e identificar ruido.

DBSCAN asigna puntos como núcleo, borde o ruido basándose en la alcanzabilidad por densidad definida por los parámetros $\varepsilon$ y $minPts$. Sin embargo, no ofrece ninguna perspectiva sobre por qué un punto específico recibió su asignación o si dicha asignación es robusta ante pequeños cambios en los datos. Los métodos existentes de EC enfrentan tres obstáculos principales al aplicarse a DBSCAN:

1. Falta de Diferenciabilidad: DBSCAN no utiliza una función de pérdida diferenciable, lo que impide el uso de métodos de búsqueda basados en gradientes comunes en la generación de EC supervisada.
2. Ausencia de Probabilidades: A diferencia de los modelos de clasificación, DBSCAN proporciona membresías discretas basadas en la conectividad en lugar de probabilidades de clase continuas, de las cuales dependen muchos métodos de EC agnósticos al modelo.
3. Estructura de Similitud Compleja: La conectividad por densidad de DBSCAN significa que dos puntos pueden estar cerca en el espacio euclidiano pero efectivamente distantes en términos de membresía al agrupamiento (requiriendo un camino largo conectado por densidad). Las métricas de distancia euclidiana estándar utilizadas por otros métodos de EC no capturan esto, generando potencialmente contrafactuales redundantes o inválidos.

Metodología: ExDBSCAN

Los autores proponen ExDBSCAN, el primer método de explicación post-hoc diseñado específicamente para DBSCAN. Genera contrafactuales accionables tanto para transiciones de ruido a agrupación como de agrupación a agrupación, con garantías teóricas de validez.

Componentes Principales

1. Representación de Similitud Basada en Grafos:
   En lugar de depender de la distancia euclidiana, ExDBSCAN modela la estructura del agrupamiento como un grafo ponderado no dirigido $G(V, E)$.

   • Vértices ($V$): Representan los puntos núcleo de una agrupación.
   • Aristas: Conectan dos vértices si son directamente alcanzables por densidad (distancia $< \varepsilon$).
   • Pesos: La distancia euclidiana entre los puntos núcleo conectados.
   • Métrica de Distancia: La distancia entre dos puntos cualesquiera se define como el camino más corto ponderado en $G$. Esto asegura que la "proximidad" respete la estructura de conectividad por densidad del agrupamiento.

2. Optimización Inspirada en la Física:
   Para generar un conjunto de $k$ contrafactuales diversos y próximos, ExDBSCAN modela la selección de puntos núcleo de referencia como un problema de minimización de energía física. El sistema trata a los puntos núcleo candidatos como partículas cargadas sujetas a dos fuerzas:

   • Repulsión (Diversidad): Modelada según la ley de Coulomb, los puntos núcleo candidatos se repelen entre sí. La fuerza de repulsión es inversamente proporcional a la distancia del camino más corto ponderado entre ellos. Esto asegura que los contrafactuales seleccionados se distribuyan a través de la estructura de densidad del agrupamiento, evitando redundancias.
   • Atracción (Proximidad): Modelada según la ley de Hooke (fuerzas de resorte), los puntos núcleo candidatos son atraídos hacia la instancia original $p$ que se desea explicar. La fuerza aumenta linealmente con la distancia, sesgando la selección hacia los puntos núcleo válidos más cercanos.

   La energía total $E_{C'}$ de un conjunto de puntos núcleo seleccionados $C'$ se define 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)$$
   Donde $D$ es la distancia del grafo ponderado y $d$ es la distancia euclidiana al punto original.

3. Optimización y Construcción:

   • NP-Dureza: Se ha demostrado que encontrar el conjunto óptimo de puntos núcleo para minimizar esta energía es NP-duro. ExDBSCAN emplea un algoritmo voraz para aproximar la solución. Selecciona iterativamente el punto núcleo que minimiza la energía total del sistema dado el conjunto actualmente seleccionado.
   • Generación de Contrafactuales: Una vez seleccionado un conjunto de puntos núcleo de referencia, los contrafactuales finales se construyen dentro de la $\varepsilon$-vecindad de estos núcleos. Específicamente, un contrafactual $p'$ se coloca a una distancia $\varepsilon$ del punto núcleo de referencia $q$ en la dirección del punto original $p$.
   • Garantía de Validez: Por construcción, cada contrafactual generado se encuentra dentro de $\varepsilon$ de un punto núcleo en el agrupamiento objetivo, asegurando que cumple con los criterios de conectividad por densidad de DBSCAN y es un miembro válido del agrupamiento objetivo.

4. Manejo de Restricciones:
   El método tiene en cuenta las características no accionables (por ejemplo, edad, género) restringiendo el espacio de búsqueda. Filtra los puntos núcleo de tal manera que sus $\varepsilon$-vecindades sean alcanzables sin modificar atributos no accionables, asegurando que las explicaciones permanezcan realistas.

Contribuciones Clave

• Primer Método de EC Específico para DBSCAN: ExDBSCAN es el primer método diseñado para generar explicaciones contrafactuales específicamente para el agrupamiento basado en densidad, cubriendo tanto transiciones de ruido a agrupación como de agrupación a agrupación.
• Nuevo Modelo Inspirado en la Física: Los autores introducen un modelo que equilibra la proximidad y la diversidad utilizando repulsión electrostática y atracción tipo resorte, teniendo en cuenta explícitamente la estructura de conectividad por densidad de DBSCAN mediante un grafo ponderado.
• Validez Teórica: El método proporciona una garantía teórica (Teorema 3.1) de que cada contrafactual generado es válido bajo las reglas de asignación de DBSCAN.
• Superioridad Empírica: Una evaluación exhaustiva en 30 conjuntos de datos tabulares demuestra que ExDBSCAN supera a las líneas base existentes (incluyendo métodos agnósticos al modelo como BayCon, DiCE y Growing Spheres) en validez, proximidad y diversidad.

Resultados Experimentales

Los autores evaluaron ExDBSCAN en 30 conjuntos de datos tabulares de OpenML frente a siete líneas base (incluyendo DiCE, BayCon, Growing Spheres y variantes aleatorias).

• Validez: ExDBSCAN logró una validez del 100% en todas las consultas. En contraste, los métodos basados en sustitutos (DiCE-Sustituto, GS-Sustituto) y los métodos agnósticos al modelo (BayCon) lucharon significativamente, a menudo logrando tasas de validez inferiores al 50%. Esto se atribuye a la discrepancia entre sus objetivos de optimización continua y la asignación discreta basada en densidad de DBSCAN.
• Proximidad: Entre los métodos que lograron alta validez, ExDBSCAN produjo contrafactuales significativamente más cercanos a las instancias originales que sus competidores. Esto se atribuye a la optimización explícita del término de atracción tipo resorte utilizando la distancia basada en grafos.
• Diversidad: ExDBSCAN logró las puntuaciones de diversidad más altas. Su mecanismo de repulsión, basado en la distancia del camino más corto ponderado dentro del grafo del agrupamiento, aseguró que los contrafactuales seleccionados representaran alternativas distintas dentro de la topología del agrupamiento, en lugar de simplemente estar cerca en el espacio euclidiano.
• Tiempo de Ejecución: Aunque ExDBSCAN es computacionalmente más intensivo que una heurística aleatoria simple, generalmente es más rápido que la optimización pesada requerida por DiCE y BayCon, particularmente cuando esos métodos fallan en encontrar contrafactuales válidos.

Significado y Afirmaciones

El artículo posiciona a ExDBSCAN como un paso crítico hacia la superación de la brecha de interpretabilidad en el aprendizaje no supervisado. Los autores afirman que, al aprovechar el razonamiento contrafactual adaptado a los mecanismos específicos de DBSCAN, los profesionales pueden obtener:

• Perspectivas Accionables: Comprender qué características impulsan la asignación de un punto a un agrupamiento o su estado como ruido.
• Verificaciones de Robustez: Evaluar si las asignaciones de agrupamiento son estables o sensibles a pequeñas perturbaciones.
• Confianza y Transparencia: Proporcionar escenarios de "qué pasaría si" que reflejan la verdadera estructura basada en densidad de los datos, en lugar de límites artificiales creados por modelos sustitutos.

Los autores notan modestamente que, aunque un estudio formal con usuarios está más allá del alcance de este trabajo, el método proporciona ejemplos concretos y fundamentados teóricamente de cómo pueden alterarse las asignaciones de agrupamiento. Sugieren que el trabajo futuro podría extender ExDBSCAN a escenarios incrementales o de flujo de datos y explorar estrategias de optimización más sofisticadas más allá de la aproximación voraz actual.