Technische Samenvatting: Betti Getal Filtratie-gebaseerde Topologische Clustering (BFTC)

1. Probleemstelling

Traditionele clusteringalgoritmen (bijv. k-Means, DBSCAN, Spectrale Clustering) vertrouwen zwaar op Euclidische of kernel-gebaseerde gelijkenismaten. Hoewel effectief voor veel toepassingen, hebben deze methoden vaak moeite met datasets die complexe geometrische structuren vertonen, zoals niet-convexe vormen, meerdere schalen of verstrengelde manifolds. Ze falen vaak in het vastleggen van intrinsieke topologische kenmerken zoals lussen, holtes en hogere-dimensionale connectiviteit.

Bestaande Topological Data Analysis (TDA) benaderingen proberen dit gat te overbruggen, maar worden geconfronteerd met specifieke beperkingen:

• ToMATo: Vertrouwt op 0-dimensionale homologie (verbonden componenten) en dichtheidslandschappen, wat de mogelijkheid beperkt om hogere-dimensionale topologische informatie te integreren.
• TPCC: Gebruikt simpliciale complexen en Hodge-Laplaciaan, maar kan moeite hebben met het onderscheiden van regio's waar topologische kenmerken bij verschillende filtratieschalen ontstaan.
• Topological k-Means (TKM): Embedt persistentiediagrammen in Reproducing Kernel Hilbert Spaces (RKHS), maar richt zich op globale topologische samenvattingen in plaats van gelokaliseerde, multiscale topologie.

De kernuitdaging die dit werk aanpakt, is de behoefte aan een clusteringalgoritme dat gelijktijdig lokale geometrische nabijheid en hogere-dimensionale topologische structuren kan vastleggen op een multiscale wijze, zonder uitsluitend te vertrouwen op globale persistentie-samenvattingen of vaste topologische schalen.

2. Methodologie: BFTC Algoritme

De voorgestelde methode, Betti Getal Filtratie-gebaseerde Topologische Clustering (BFTC), construeert een topologie-bewuste gelijkenisstructuur via de volgende stappen:

A. Constructie van de Nabijheidsgraaf

Het algoritme begint met de constructie van een lokale nabijheidsgraaf voor de dataset $X$. Het onderste twee varianten:

1. k-NN BFTC: Gebruikt een k-nearest-neighbor graaf om uniforme cardinaliteit en gecontroleerde sparsiteit te garanderen.
2. $\epsilon$-BFTC: Gebruikt een $\epsilon$-nabijheidsgraaf gebaseerd op een vaste geometrische straal, wat natuurlijk aansluit bij metriek-drempelconstructies.

B. Lokale Vietoris-Rips Filtratie en Betti-sequenties

Voor elk datapunt $x_i$ construeert het algoritme een reeks geneste Vietoris-Rips (VR) complexen over de lokale nabijheid $N(x_i) \cup \{x_i\}$.

• Een filtratieschaal wordt gedefinieerd door een reeks drempelwaarden $\epsilon_1, \epsilon_2, \dots, \epsilon_L$.
• Voor elke schaal wordt het VR-complex $VR(x_i, \epsilon_l)$ gevormd.
• Betti-getallen: Het algoritme berekent Betti-getallen $\beta_m$ tot aan een door de gebruiker gespecificeerde maximale dimensie $M$ (waarbij $M$ de intrinsieke topologische complexiteit reflecteert, niet noodzakelijkerwijs de ambient dimensie van de kenmerken).
• Betti-sequenties: De sequentie van Betti-getallen over de filtratieschalen voor elke dimensie $m \in [0, M]$ vormt een Betti-sequentie $\beta^{(i)}_m = (\beta^{(i)}_{1m}, \dots, \beta^{(i)}_{Lm})$. Deze sequenties dienen als multiscale topologische signaturen van de lokale nabijheid.

C. Topologie-bewuste Gelijkenis en Graafverfijning

Het algoritme kwantificeert de topologische gelijkenis tussen naburige punten door de Betti-sequenties van de punten te vergelijken.

• Gelijkenismetriek: Cosinus-gelijkenis wordt berekend tussen de Belijke sequenties van aangrenzende punten $x_i$ en $x_j$ voor elke dimensie $m$:
  $$(d_{ij})_m = \frac{\langle \beta^{(i)}_m, \beta^{(j)}_m \rangle}{\|\beta^{(i)}_m\| \|\beta^{(j)}_m\|}$$
• Uitschieterverwijdering: Een set drempelwaarden $\alpha_0, \dots, \alpha_M$ wordt toegepast. Een buur $x_j$ wordt behouden in de verfijnde nabijheid $N'(x_i)$ alleen als $(d_{ij})_m \geq \alpha_m$ geldt voor alle dimensies $m$. Deze stap elimineert topologisch ongelijke buren en uitschieters, wat resulteert in een sparere, meer informatieve graaf.

D. Spectrale Clustering

Een symmetrische gewogen adjacency matrix $A'$ wordt geconstrueerd uit de verfijnde graaf met behulp van een Gaussische kernel. De Laplacian-matrix $L' = D' - A'$ wordt berekend, en spectrale clustering (via k-Means op de eigenvectoren van de kleinste $p$ eigenwaarden) wordt toegepast om de uiteindelijke clusters te verkrijgen.

3. Belangrijkste Bijdragen

Het artikel schetst drie primaire bijdragen:

1. Nieuw Algoritme (BFTC): Een efficiënt clusteringalgoritme dat Vietoris-Rips complexen over lokale nabijheden construeert en Betti-getallen evalueert tot aan een voorgeschreven dimensie. Het maakt gebruik van Betti-sequenties om topologische gelijkenis te meten, waarmee het verder gaat dan eenvoudige connectiviteit ($\beta_0$) om hogere-dimensionale kenmerken te vangen.
2. Effectiviteit op Complexe Structuren: De methode is specifiek ontworpen om datasets met complexe, verstrengelde vormen en structuren aan te kunnen door gebruik te maken van onderliggende topologische kenmerken over meerdere schalen.
3. Theoretische Analyse: Het artikel biedt uitgebreide theoretische onderbouwingen met betrekking tot de convergentie en stabiliteit van BFTC. Het stelt vast dat onder redelijke geometrische en spectrale scheidingsvoorwaarden, het algoritme structureel stabiel is; kleine perturbaties in de invoerdata veranderen de resulterende clustering niet (op een permutatie van labels na).

4. Experimentele Resultaten

De auteurs hebben BFTC (zowel k-NN als $\epsilon$ varianten) geëvalueerd tegen state-of-the-art baselines (k-Means, Spectral, DBSCAN, ToMATo, TPCC, TKM, etc.) op synthetische en real-world datasets.

• Synthetische Datasets: Op datasets met niet-convexe en verstrengelde structuren (bijv. Linked Tori, 3MC, Smile1, Torus Sphere Line) behaalde BFTC consistent superieure Adjusted Rand Index (ARI) en Normalized Mutual Information (NMI) scores. Bijvoorbeeld, op de Linked Tori dataset met ruis ($\rho=0.3$), behaalde k-NN BFTC een ARI van 0.49 en NMI van 0.56, wat aanzienlijk beter is dan concurrenten zoals DBSCAN (0.01 ARI) en ToMATo (0.17 ARI).
• Real-World Datasets: Experimenten met UCI-datasets (Zoo, Ecoli, Wisconsin B.C., Glass, ORHD, MNIST, Phishing URL) toonden aan dat BFTC bijna alle concurrenten versloeg.
• Robuustheid: De methode toonde stabiliteit tegen Gaussian ruis-perturbaties.
• Ablatie-studies:
  • Nabijheidsconstructie: Zowel k-NN als $\epsilon$-nabijheden bleken effectief, hoewel k-NN een soepeler spectraal gedrag bood voor sterk verstrengelde manifolds.
  • Afstandmetrieken: Cosinus-gelijkenis tussen Betti-sequenties bleek aanzienlijk effectiever dan Euclidische afstand voor het vastleggen van topologische relaties.
  • Kernfuncties: De inclusie van een Gaussische kernel in de adjacency matrix verbeterde de prestaties vergeleken met ongewogen grafen.

5. Betekenis en Claims

Het artikel beweert dat BFTC een belangrijke vooruitgang vertegenwoordigt door multiscale topologische informatie direct in het clusteringproces te integreren. In tegen tegenstelling tot eerdere methoden die vertrouwen op globale persistentie-samenvattingen of vaste schalen, vangt BFTC gelokaliseerde multiscale topologie via Betti-sequenties.

De auteurs stellen dat deze aanpak het algoritme in staat stelt om:

• Regio's van een manifold te onderscheiden waar topologische kenmerken bij verschillende filtratieschalen ontstaan.
• Gelijktijdig geometrische nabijheid en hogere-dimensionale topologische structuren (lussen, holtes) te vangen.
• Een robuuste oplossing te bieden voor datasets met complexe, niet-convexe en verstrengelde structuren waar traditionele Euclidische methoden falen.

De theoretische analyse ondersteunt de empirische resultaten verder en stelt dat BFTC niet alleen computationeel eindig is, maar ook structureel stabiel, wat garandeert dat de clustering-pipeline lokaal invariant is voor kleine perturbaties in de invoerdata. Het werk concludeert dat het verkennen van topologische aspecten voor grootschalige datasets met complexe overlappende structuren een veelbelovende richting is voor toekomstig onderzoek.