Résumé Technique : ExDBSCAN – Expliquer DBSCAN par Raisonnement Contrefactuel

Énoncé du Problème

Le clustering est une technique fondamentale d'apprentissage non supervisé, mais il souffre d'un fossé significatif en matière d'interprétabilité par rapport à l'apprentissage supervisé. Bien que les explications contrefactuelles (EC) soient devenues la norme pour expliquer les modèles supervisés en identifiant les modifications minimales des entrées qui altèrent les prédictions, elles ne sont pas directement applicables au clustering. Ce fossé est particulièrement aigu pour DBSCAN (Density-Based Spatial Clustering of Applications with Noise), un algorithme populaire capable de trouver des clusters de formes arbitraires et d'identifier le bruit.

DBSCAN assigne les points comme étant des points centraux (core), des points frontières ou du bruit, sur la base de la densité-réachabilité définie par les paramètres $\varepsilon$ et $minPts$. Cependant, il n'offre aucune indication sur pourquoi un point spécifique a reçu son affectation ou si cette affectation est robuste face à de petits changements dans les données. Les méthodes d'EC existantes se heurtent à trois obstacles principaux lorsqu'elles sont appliquées à DBSCAN :

1. Absence de Différentiabilité : DBSCAN n'utilise pas de fonction de perte différentiable, ce qui empêche l'utilisation de méthodes de recherche basées sur le gradient, courantes dans la génération d'EC supervisée.
2. Absence de Probabilités : Contrairement aux modèles de classification, DBSCAN fournit des appartenances discrètes basées sur la connectivité plutôt que des probabilités de classe continues, sur lesquelles reposent de nombreuses méthodes d'EC agnostiques au modèle.
3. Structure de Similarité Complexe : La connectivité par densité de DBSCAN signifie que deux points peuvent être proches dans l'espace euclidien mais effectively distants en termes d'appartenance au cluster (nécessitant un long chemin connecté par densité). Les métriques de distance euclidienne standard utilisées par d'autres méthodes d'EC échouent à capturer cela, générant potentiellement des contrefactuels redondants ou invalides.

Méthodologie : ExDBSCAN

Les auteurs proposent ExDBSCAN, la première méthode d'explication post-hoc conçue spécifiquement pour DBSCAN. Elle génère des contrefactuels actionnables pour les transitions bruit-vers-cluster et cluster-vers-cluster, avec des garanties théoriques de validité.

Composants Principaux

1. Représentation de la Similarité Basée sur les Graphes :
   Au lieu de s'appuyer sur la distance euclidienne, ExDBSCAN modélise la structure du cluster comme un graphe pondéré non orienté $G(V, E)$.

   • Sommets ($V$) : Représentent les points centraux d'un cluster.
   • Arêtes : Relient deux sommets s'ils sont directement densité-réachables (distance $< \varepsilon$).
   • Poids : La distance euclidienne entre les points centraux connectés.
   • Métrique de Distance : La distance entre deux points quelconques est définie comme le chemin pondéré le plus court dans $G$. Cela garantit que la « proximité » respecte la structure de connectivité par densité du cluster.

2. Optimisation Inspirée de la Physique :
   Pour générer un ensemble de $k$ contrefactuels diversifiés et proches, ExDBSCAN modélise la sélection de points centraux de référence comme un problème de minimisation d'énergie physique. Le système traite les points centraux candidats comme des particules chargées soumises à deux forces :

   • Répulsion (Diversité) : Modélisée selon la loi de Coulomb, les points centraux candidats se repoussent mutuellement. La force de répulsion est inversement proportionnelle à la distance du chemin pondéré le plus court entre eux. Cela garantit que les contrefactuels sélectionnés sont répartis sur la structure de densité du cluster, évitant la redondance.
   • Attraction (Proximité) : Modélisée selon la loi de Hooke (forces de ressort), les points centraux candidats sont attirés par l'instance originale $p$ à expliquer. La force augmente linéairement avec la distance, biaisant la sélection vers les points centraux valides les plus proches.

   L'énergie totale $E_{C'}$ d'un ensemble de points centraux sélectionnés $C'$ est définie par :
   $$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)$$
   Où $D$ est la distance du graphe pondéré et $d$ est la distance euclidienne au point original.

3. Optimisation et Construction :

   • NP-Difficulté : Trouver l'ensemble optimal de points centraux pour minimiser cette énergie est prouvé comme étant NP-difficile. ExDBSCAN emploie un algorithme glouton pour approximer la solution. Il sélectionne itérativement le point central qui minimise l'énergie totale du système étant donné l'ensemble actuellement sélectionné.
   • Génération de Contrefactuels : Une fois un ensemble de points centraux de référence sélectionné, les contrefactuels finaux sont construits dans le voisinage $\varepsilon$ de ces cœurs. Spécifiquement, un contrefactuel $p'$ est placé à une distance $\varepsilon$ du point central de référence $q$ dans la direction du point original $p$.
   • Garantie de Validité : Par construction, chaque contrefactuel généré se trouve à moins de $\varepsilon$ d'un point central dans le cluster cible, garantissant qu'il satisfait les critères de connectivité par densité de DBSCAN et qu'il est un membre valide du cluster cible.

4. Gestion des Contraintes :
   La méthode prend en compte les caractéristiques non actionnables (par exemple, l'âge, le genre) en restreignant l'espace de recherche. Elle filtre les points centraux de sorte que leurs voisinages $\varepsilon$ soient accessibles sans modifier les attributs non actionnables, garantissant que les explications restent réalistes.

Contributions Clés

• Première Méthode d'EC Spécifique à DBSCAN : ExDBSCAN est la première méthode conçue pour générer des explications contrefactuelles spécifiquement pour le clustering basé sur la densité, couvrant à la fois les transitions bruit-vers-cluster et cluster-vers-cluster.
• Nouveau Modèle Inspiré de la Physique : Les auteurs introduisent un modèle qui équilibre proximité et diversité en utilisant la répulsion électrostatique et l'attraction de type ressort, tenant explicitement compte de la structure de connectivité par densité de DBSCAN via un graphe pondéré.
• Validité Théorique : La méthode fournit une garantie théorique (Théorème 3.1) que chaque contrefactuel généré est valide selon les règles d'affectation de DBSCAN.
• Supériorité Empirique : Une évaluation extensive sur 30 jeux de données tabulaires démontre que ExDBSCAN surpasse les bases de référence existantes (incluant des méthodes agnostiques au modèle comme BayCon, DiCE et Growing Spheres) en termes de validité, de proximité et de diversité.

Résultats Expérimentaux

Les auteurs ont évalué ExDBSCAN sur 30 jeux de données tabulaires OpenML contre sept bases de référence (incluant DiCE, BayCon, Growing Spheres et des variantes aléatoires).

• Validité : ExDBSCAN a atteint 100 % de validité sur toutes les requêtes. En revanche, les méthodes basées sur des substituts (DiCE-Surrogate, GS-Surrogate) et les méthodes agnostiques au modèle (BayCon) ont considérablement peiné, atteignant souvent des taux de validité inférieurs à 50 %. Cela est attribué à la discordance entre leurs objectifs d'optimisation continus et l'affectation discrète et basée sur la densité de DBSCAN.
• Proximité : Parmi les méthodes atteignant une validité élevée, ExDBSCAN a produit des contrefactuels significativement plus proches des instances originales que les concurrents. Cela est attribué à l'optimisation explicite du terme d'attraction de type ressort utilisant la distance basée sur le graphe.
• Diversité : ExDBSCAN a obtenu les scores de diversité les plus élevés. Son mécanisme de répulsion, basé sur la distance du chemin pondéré le plus court au sein du graphe du cluster, a garanti que les contrefactuels sélectionnés représentaient des alternatives distinctes au sein de la topologie du cluster, plutôt que d'être simplement proches dans l'espace euclidien.
• Temps d'Exécution : Bien qu'ExDBSCAN soit plus intensif en calculs qu'une heuristique aléatoire simple, il est généralement plus rapide que l'optimisation lourde requise par DiCE et BayCon, en particulier lorsque ces méthodes échouent à trouver des contrefactuels valides.

Importance et Revendications

L'article présente ExDBSCAN comme une étape cruciale vers la réduction du fossé d'interprétabilité dans l'apprentissage non supervisé. Les auteurs affirment que, en exploitant un raisonnement contrefactuel adapté aux mécanismes spécifiques de DBSCAN, les praticiens peuvent obtenir :

• Informations Actionnables : Comprendre quelles caractéristiques déterminent l'affectation d'un point à un cluster ou son statut de bruit.
• Vérifications de Robustesse : Évaluer si les affectations de clusters sont stables ou sensibles à de petites perturbations.
• Confiance et Transparence : Fournir des scénarios « et si » qui reflètent la véritable structure basée sur la densité des données, plutôt que des frontières artificielles créées par des modèles substituts.

Les auteurs notent modestement que bien qu'une étude utilisateur formelle dépasse le cadre de ce travail, la méthode fournit des exemples concrets et théoriquement fondés de la manière dont les affectations de clusters peuvent être modifiées. Ils suggèrent que des travaux futurs pourraient étendre ExDBSCAN à des scénarios incrémentaux ou de flux de données et explorer des stratégies d'optimisation plus sophistiquées au-delà de l'approximation gloutonne actuelle.