Riepilogo Tecnico: Betti Number Filtration-based Topological Clustering (BFTC)

1. Definizione del Problema

Gli algoritmi di clustering tradizionali (ad es., k-Means, DBSCAN, Spectral Clustering) si affidano pesantemente a misure di similarità euclidee o basate su kernel. Sebbene efficaci per molte applicazioni, questi metodi spesso faticano con dataset che presentano strutture geometriche complesse, come forme non convesse, molteplici scale o varietà intrecciate. Essi falliscono frequentemente nel catturare caratteristiche topologiche intrinseche come cicli, vuoti e connettività di dimensioni superiori.

Gli approcci esistenti di Analisi Topologica dei Dati (TDA) tentano di colmare questo divario, ma affrontano limitazioni specifiche:

• ToMATo: Si affida alla omologia di dimensione 0 (componenti connesse) e a paesaggi di densità, limitando la capacità di incorporare informazioni topologiche di dimensione superiore.
• TPCC: Utilizza complessi simpliciali e Laplaciani di Hodge, ma può avere difficoltà a distinguere regioni in cui le caratteristiche topologiche emergono a diverse scale di filtrazione.
• Topological k-Means (TKM): Incorpora diagrammi di persistenza in spazi di Hilbert con kernel riproducibile (RKHS), ma si concentra su riassunti topologici globali piuttosto che su una topologia locale e multiscala.

La sfida centrale affrontata da questo lavoro è la necessità di un algoritmo di clustering che possa simultaneamente catturare la prossimità geometrica locale e le strutture topologiche di dimensione superiore in modo multiscala, senza fare affidamento esclusivamente su riassunti di persistenza globale o scale topologiche fisse.

2. Metodologia: Algoritmo BFTC

Il metodo proposto, Betti Number Filtration-based Topological Clustering (BFTC), costruisce una struttura di similarità consapevole della topologia attraverso i seguenti passaggi:

A. Costruzione del Grafo di Vicinato

L'algoritmo inizia costruendo un grafo di vicinato locale per il dataset $X$. Supporta due varianti:

1. k-NN BFTC: Utilizza un grafo k-nearest-neighbor per garantire una cardinalità uniforme e una sparsità controllata.
2. $\epsilon$-BFTC: Utilizza un grafo di $\epsilon$-vicinato basato su un raggio geometrico fisso, allineandosi naturalmente alle costruzioni con soglia metrica.

B. Filtrazione Vietoris-Rips Locale e Sequenze di Betti

Per ogni punto dati $x_i$, l'algoritmo costruisce una serie di complessi Vietoris-Rips (VR) annidati sul suo vicinato locale $N(x_i) \cup \{x_i\}$.

• Una scala di filtrazione è definita da una sequenza di soglie $\epsilon_1, \epsilon_2, \dots, \epsilon_L$.
• Per ogni scala, viene formato il complesso VR $VR(x_i, \epsilon_l)$.
• Numeri di Betti: L'algoritmo calcola i numeri di Betti $\beta_m$ fino a una dimensione massima $M$ specificata dall'utente (dove $M$ riflette la complessità topologica intrinseca, non necessariamente la dimensione ambiente delle feature).
• Sequenze di Betti: Per ogni dimensione $m \in [0, M]$, la sequenza dei numeri di Betti attraverso le scale di filtrazione forma una sequenza di Betti $\beta^{(i)}_m = (\beta^{(i)}_{1m}, \dots, \beta^{(i)}_{Lm})$. Queste sequenze fungono da firme topologiche multiscala del vicinato locale.

C. Similarità Consapevole della Topologia e Raffinamento del Grafo

L'algoritmo quantifica la similarità topologica tra punti vicini confrontando le loro sequenze di Betti.

• Metrica di Similarità: La similarità del coseno è calcolata tra le sequenze di Betti dei punti adiacenti $x_i$ e $x_j$ per ogni dimensione $m$:
  $$(d_{ij})_m = \frac{\langle \beta^{(i)}_m, \beta^{(j)}_m \rangle}{\|\beta^{(i)}_m\| \|\beta^{(j)}_m\|}$$
• Rimozione degli Outlier: Viene applicato un insieme di soglie $\alpha_0, \dots, \alpha_M$. Un vicino $x_j$ è mantenuto nel vicinato raffinato $N'(x_i)$ solo se $(d_{ij})_m \geq \alpha_m$ per tutte le dimensioni $m$. Questo passaggio elimina i vicini topologicamente dissimili e gli outlier, producendo un grafo più sparso e informativo.

D. Clustering Spettrale

Viene costruita una matrice di adiacenza pesata simmetrica $A'$ dal grafo raffinato utilizzando un kernel Gaussiano. La matrice Laplaciana $L' = D' - A'$ viene calcolata, e il clustering spettrale (tramite k-Means sugli autovettori dei primi $p$ autovalori più piccoli) viene applicato per ottenere i cluster finali.

3. Contributi Chiave

Il documento delinea tre contributi primari:

1. Nuovo Algoritmo (BFTC): Un algoritmo di clustering efficiente che costruisce complessi di Vietoris-Rips sui vicinati locali e valuta i numeri di Betti fino a una dimensione prestabilita. Utilizza le sequenze di Betti per misurare la similarità topologica, andando oltre la semplice connettività ($\beta_0$) per catturare caratteristiche di dimensione superiore.
2. Efficacia su Strutture Complesse: Il metodo è specificamente progettato per gestire dataset con strutture complesse e intrecciate, sfruttando le caratteristiche topologiche sottostanti.
3. Analisi Teorica: Il documento fornisce estesi fondamenti teorici riguardanti la convergenza e la stabilità di BFTC. Stabilisce che, sotto ragionevoli condizioni di separazione geometrica e spettrale, l'algoritmo è strutturalmente stabile; piccole perturbazioni nei dati di input non alterano il clustering risultante (fino alla permutazione delle etichette).

4. Risultati Sperimentali

Gli autori hanno valutato BFTC (varianti sia k-NN che $\epsilon$) contro i baseline allo stato dell'arte (k-Means, Spectral, DBSCAN, ToMATo, TPCC, TKM, ecc.) su dataset sintetici e reali.

• Dataset Sintetici: Su dataset con strutture non convesse e intrecciate (ad es., Linked Tori, 3MC, Smile1, Torus Sphere Line), BFTC ha costantemente ottenuto punteggi superiori di Adjusted Rand Index (ARI) e Normalized Mutual Information (NMI). Ad esempio, sul dataset Linked Tori con rumore ($\rho=0.3$), k-NN BFTC ha raggiunto un ARI di 0.49 e un NMI di 0.56, superando significativamente i concorrenti come DBSCAN (0.01 ARI) e ToMATo (0.17 ARI).
• Dataset Reali: Gli esperimenti su dataset UCI (Zoo, Ecoli, Wisconsin B.C., Glass, ORHD, MNIST, Phishing URL) hanno dimostrato che BFTC ha superato quasi tutti i contendenti.
• Robustezza: Il metodo ha mostrato stabilità contro le perturbazioni di rumore Gaussiano.
• Studi di Ablazione:
  • Costruzione del Vicinato: Sia i vicinati k-NN che $\epsilon$ si sono dimostrati efficaci, sebbene il k-NN offra un comportamento spettrale più fluido per varietà altamente intrecciate.
  • Metriche di Distanza: La similarità del coseno tra le sequenze di Betti è risultata significativamente più efficace della distanza Euclidea nel catturare le relazioni topologiche.
  • Funzioni Kernel: L'inclusione di un kernel Gaussiano nella matrice di adiacenza ha migliorato le prestazioni rispetto ai grafi non pesati.

5. Significato e Rivendicazioni

Il documento afferma che BFTC rappresenta un avanzamento significativo integrando l'informazione topologica multiscala direttamente nel processo di clustering. A differenza dei metodi precedenti che si affidano a riassunti di persistenza globale o scale fisse, BFTC cattura la topologia multiscala localizzata attraverso le sequenze di Betti.

Gli autori sostengono che questo approccio permette all'algoritmo di:

• Distinguere le regioni di una varietà in cui le caratteristiche topologiche emergono a diverse scale di filtrazione.
• Catturare simultaneamente la prossimità geometrica e le strutture topologiche di dimensione superiore (cicli, vuoti).
• Fornire una soluzione robusta per dataset con strutture complesse, non convesse e intrecciate dove i metodi basati sull'Euclideo tradizionale falliscono.

L'analisi teorica supporta ulteriormente i risultati empirici, affermando che BFTC non è solo computazionalmente finito, ma anche strutturalmente stabile, garantendo che la pipeline di clustering sia localmente invariante rispetto a piccole perturbazioni nei dati di input. Il lavoro conclude che l'esplorazione degli aspetti topologici per dataset su larga scala con strutture sovrapposte complesse rimane una direzione promettente per la ricerca futura.