Riepilogo Tecnico: ExDBSCAN – Spiegare DBSCAN con il Ragionamento Controfattuale

Enunciato del Problema

Il clustering è una tecnica fondamentale di apprendimento non supervisionato, ma soffre di un divario significativo in termini di interpretabilità rispetto all'apprendimento supervisionato. Sebbene le spiegazioni controfattuali (CE) siano diventate uno standard per spiegare i modelli supervisionati identificando le minime modifiche agli input che alterano le previsioni, non sono direttamente applicabili al clustering. Questo divario è particolarmente acuto per DBSCAN (Density-Based Spatial Clustering of Applications with Noise), un algoritmo popolare in grado di trovare cluster di forma arbitraria e di identificare il rumore.

DBSCAN assegna i punti come punti centrali (core), di confine o rumore basandosi sulla raggiungibilità per densità definita dai parametri $\varepsilon$ e $minPts$. Tuttavia, non offre alcuna intuizione sul perché un punto specifico abbia ricevuto una determinata assegnazione o se tale assegnazione sia robusta a piccole variazioni dei dati. I metodi CE esistenti affrontano tre ostacoli principali quando applicati a DBSCAN:

1. Mancanza di Differenziabilità: DBSCAN non utilizza una funzione di perdita differenziabile, impedendo l'uso di metodi di ricerca basati sul gradiente comuni nella generazione di CE supervisionate.
2. Assenza di Probabilità: A differenza dei modelli di classificazione, DBSCAN fornisce appartenenze discrete basate sulla connettività piuttosto che probabilità di classe continue, su cui fanno affidamento molti metodi CE agnostici rispetto al modello.
3. Struttura di Similarità Complessa: La connettività per densità di DBSCAN significa che due punti possono essere vicini nello spazio euclideo ma efficacemente distanti in termini di appartenenza al cluster (richiedendo un percorso lungo connesso per densità). Le metriche di distanza euclidea standard utilizzate da altri metodi CE non riescono a catturare questo aspetto, potenzialmente generando controfattuali ridondanti o non validi.

Metodologia: ExDBSCAN

Gli autori propongono ExDBSCAN, il primo metodo di spiegazione post-hoc progettato specificamente per DBSCAN. Genera controfattuali azionabili sia per le transizioni da rumore a cluster sia per le transizioni da cluster a cluster, con garanzie teoriche di validità.

Componenti Principali

1. Rappresentazione della Similarità Basata su Grafi:
   Invece di affidarsi alla distanza euclidea, ExDBSCAN modella la struttura del cluster come un grafo pesato non orientato $G(V, E)$.

   • Vertici ($V$): Rappresentano i punti centrali di un cluster.
   • Archi: Collegano due vertici se sono direttamente raggiungibili per densità (distanza $< \varepsilon$).
   • Pesi: La distanza euclidea tra i punti centrali collegati.
   • Metrica di Distanza: La distanza tra due punti qualsiasi è definita come il percorso più breve pesato in $G$. Questo garantisce che la "prossimità" rispetti la struttura di connettività per densità del cluster.

2. Ottimizzazione Ispirata alla Fisica:
   Per generare un insieme di $k$ controfattuali diversificati e prossimi, ExDBSCAN modella la selezione dei punti centrali di riferimento come un problema di minimizzazione dell'energia fisica. Il sistema tratta i punti centrali candidati come particelle cariche soggette a due forze:

   • Repulsione (Diversità): Modellata sulla legge di Coulomb, i punti centrali candidati si respingono a vicenda. La forza di repulsione è inversamente proporzionale alla distanza del percorso più breve pesato tra di essi. Questo garantisce che i controfattuali selezionati siano distribuiti attraverso la struttura di densità del cluster, evitando ridondanze.
   • Attrazione (Prossimità): Modellata sulla legge di Hooke (forze elastiche), i punti centrali candidati sono attratti dall'istanza originale $p$ da spiegare. La forza aumenta linearmente con la distanza, orientando la selezione verso i punti centrali validi più vicini.

   L'energia totale $E_{C'}$ di un insieme di punti centrali selezionati $C'$ è definita come:
   $$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)$$
   Dove $D$ è la distanza del grafo pesato e $d$ è la distanza euclidea rispetto al punto originale.

3. Ottimizzazione e Costruzione:

   • NP-Difficoltà: Trovare l'insieme ottimale di punti centrali per minimizzare questa energia è dimostrato essere NP-difficile. ExDBSCAN impiega un algoritmo greedy per approssimare la soluzione. Seleziona iterativamente il punto centrale che minimizza l'energia totale del sistema dato l'insieme attualmente selezionato.
   • Generazione di Controfattuali: Una volta selezionato un insieme di punti centrali di riferimento, i controfattuali finali sono costruiti all'interno del vicinato $\varepsilon$ di questi nuclei. Nello specifico, un controfattuale $p'$ è posizionato a distanza $\varepsilon$ dal punto centrale di riferimento $q$ nella direzione del punto originale $p$.
   • Garanzia di Validità: Per costruzione, ogni controfattuale generato giace entro $\varepsilon$ da un punto centrale nel cluster target, garantendo che soddisfi i criteri di connettività per densità di DBSCAN e sia un membro valido del cluster target.

4. Gestione dei Vincoli:
   Il metodo tiene conto delle caratteristiche non azionabili (ad esempio, età, genere) limitando lo spazio di ricerca. Filtra i punti centrali in modo che i loro vicinati $\varepsilon$ siano raggiungibili senza modificare gli attributi non azionabili, garantendo che le spiegazioni rimangano realistiche.

Contributi Chiave

• Primo Metodo CE Specifico per DBSCAN: ExDBSCAN è il primo metodo progettato per generare spiegazioni controfattuali specificamente per il clustering basato sulla densità, coprendo sia le transizioni da rumore a cluster sia le transizioni da cluster a cluster.
• Nuovo Modello Ispirato alla Fisica: Gli autori introducono un modello che bilancia prossimità e diversità utilizzando repulsione elettrostatica e attrazione di tipo elastico, tenendo esplicitamente conto della struttura di connettività per densità di DBSCAN tramite un grafo pesato.
• Validità Teorica: Il metodo fornisce una garanzia teorica (Teorema 3.1) che ogni controfattuale generato sia valido secondo le regole di assegnazione di DBSCAN.
• Superiorità Empirica: Una valutazione estesa su 30 dataset tabellari dimostra che ExDBSCAN supera le basi di confronto esistenti (inclusi metodi agnostici rispetto al modello come BayCon, DiCE e Growing Spheres) in termini di validità, prossimità e diversità.

Risultati Sperimentali

Gli autori hanno valutato ExDBSCAN su 30 dataset tabellari OpenML contro sette basi di confronto (inclusi DiCE, BayCon, Growing Spheres e varianti casuali).

• Validità: ExDBSCAN ha raggiunto il 100% di validità su tutte le query. Al contrario, i metodi basati su surrogati (DiCE-Surrogate, GS-Surrogate) e i metodi agnostici rispetto al modello (BayCon) hanno faticato significativamente, raggiungendo spesso tassi di validità inferiori al 50%. Ciò è attribuito alla discrepanza tra i loro obiettivi di ottimizzazione continui e l'assegnazione discreta basata sulla densità di DBSCAN.
• Prossimità: Tra i metodi che hanno raggiunto un'alta validità, ExDBSCAN ha prodotto controfattuali significativamente più vicini alle istanze originali rispetto ai concorrenti. Ciò è attribuito all'ottimizzazione esplicita del termine di attrazione di tipo elastico utilizzando la distanza basata su grafi.
• Diversità: ExDBSCAN ha ottenuto i punteggi di diversità più alti. Il suo meccanismo di repulsione, basato sulla distanza del percorso più breve pesato all'interno del grafo del cluster, ha garantito che i controfattuali selezionati rappresentassero alternative distinte all'interno della topologia del cluster, anziché essere semplicemente vicini nello spazio euclideo.
• Tempo di Esecuzione: Sebbene ExDBSCAN sia computazionalmente più intensivo di un semplice euristico casuale, è generalmente più veloce dell'ottimizzazione pesante richiesta da DiCE e BayCon, in particolare quando tali metodi non riescono a trovare controfattuali validi.

Significato e Affermazioni

Il documento posiziona ExDBSCAN come un passo critico verso la chiusura del divario di interpretabilità nell'apprendimento non supervisionato. Gli autori affermano che, sfruttando il ragionamento controfattuale adattato alle meccaniche specifiche di DBSCAN, i praticanti possono ottenere:

• Intuizioni Azionabili: Comprendere quali caratteristiche guidano l'assegnazione di un punto a un cluster o il suo status di rumore.
• Controlli di Robustezza: Valutare se le assegnazioni dei cluster sono stabili o sensibili a piccole perturbazioni.
• Fiducia e Trasparenza: Fornire scenari "what-if" che riflettono la vera struttura basata sulla densità dei dati, piuttosto che confini artificiali creati da modelli surrogati.

Gli autori notano con modestia che, sebbene uno studio formale con gli utenti sia al di fuori della portata di questo lavoro, il metodo fornisce esempi concreti e teoricamente fondati di come le assegnazioni dei cluster possano essere alterate. Suggeriscono che il lavoro futuro potrebbe estendere ExDBSCAN a scenari incrementali o di streaming ed esplorare strategie di ottimizzazione più sofisticate oltre l'attuale approssimazione greedy.