🤖 machine learning

Topology-Driven Clustering: Enhancing Performance with Betti Number Filtration

Cet article introduit BFTC, un nouvel algorithme de regroupement topologique qui exploite des séquences de Betti multi-échelles dérivées de filtrations de Vietoris-Rips locales pour construire des structures de similitude sensibles à la topologie, permettant ainsi de regrouper efficacement des structures de données complexes, non convexes et entrelacées, tout en surpassant les méthodes de pointe existantes.

Auteurs originaux : Arghya Pratihar, Kushal Bose, Swagatam Das

Publié 2026-07-22

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Arghya Pratihar, Kushal Bose, Swagatam Das

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

La Forme des Choses à Venir

Imaginez que vous essayiez de trier un immense tas de jouets mélangés. Il y a des blocs rouges, des balles bleues et des serpents verts. Si vous vous contentez de regarder à quel point ils sont proches les uns des autres sur le sol, vous pourriez regrouper les blocs rouges avec les balles bleues simplement parce qu'ils sont tombés l'un à côté de l'autre. C'est ainsi que de nombreux programmes informatiques traditionnels tentent de trier les données : ils mesurent la distance en ligne droite entre les points. Mais que se passe-t-il si les « serpents » sont en réalité de longues boucles sinueuses qui s'enroulent autour des « balles » ? La distance seule ne peut pas vous dire que le serpent est une forme unique et connectée ; elle ne voit qu'un ensemble de points dispersés.

Pour résoudre cela, les scientifiques utilisent un domaine appelé l'Analyse de Données Topologiques (TDA). Voyez la TDA comme un moyen de regarder les données non pas seulement comme un éparpillement de points, mais comme un paysage de collines, de vallées et de tunnels. Un outil clé de ce domaine est l'« homologie persistante », qui agit comme une caméra prenant des photos des données à différents niveaux de zoom. En zoomant, vous pouvez voir quelles caractéristiques (comme un trou dans un donut ou une boucle dans un serpent) restent visibles et lesquelles ne sont que du bruit aléatoire. Un autre concept clé est le « nombre de Betti », qui est simplement un décompte de ces caractéristiques : combien y a-t-il d'îles séparées ? Combien de tunnels ? Combien de bulles creuses ? En comptant ces formes, les ordinateurs peuvent comprendre la véritable structure des données, même lorsqu'elles sont tordues, emmêlées ou non convexes (c'est-à-dire qu'elles ne ressemblent pas à une simple balle ou une boîte).

L'Idée Majeure de l'Article : BFTC

Dans cet article, les auteurs présentent une nouvelle méthode appelée Betti Number Filtration-based Topological Clustering (Regroupement Topologique basé sur la Filtration des Nombres de Betti), ou BFTC pour plus de brièveté. Ils soutiennent que, bien que les méthodes précédentes aient tenté d'utiliser ces idées topologiques, elles ont souvent manqué leur cible en regardant l'ensemble du jeu de données à la fois ou en ne comptant que les caractéristiques les plus simples (comme le simple comptage d'îles). Le BFTC suggère une approche plus intelligente : observer les données localement, comme un détective examinant un quartier spécifique, et compter les formes complexes à chaque échelle.

Voici comment la magie opère, étape par étape :

La Surveillance du Quartier : D'abord, l'algorithme choisit un point et regarde ses voisins immédiats (soit les $k$ amis les plus proches, soit tout le monde dans un certain rayon).
L'Objectif de Zoom (Filtration) : Au lieu de simplement regarder ce voisinage une seule fois, le BFTC crée une « filtration ». Imaginez que vous gonflez lentement un ballon autour de votre quartier. À mesure que le ballon grandit, il connecte des points qui étaient éloignés. À chaque étape de ce gonflement, l'algorithme construit une forme temporaire (appelée complexe de Vietoris–Rips) et compte les trous et les boucles.
L'Empreinte Digitale Topologique : À mesure que le ballon se gonfle, de petit en grand, le nombre de trous change. Un petit ballon peut voir 10 îles séparées. Un ballon de taille moyenne peut les voir fusionner en 2 îles avec 1 tunnel. Un grand ballon peut voir tout devenir 1 île géante. Cette séquence de nombres est appelée une séquence de Betti. C'est comme une empreinte digitale unique pour ce quartier spécifique, décrivant comment sa forme évolue.
Correspondance des Empreintes : L'algorithme compare ensuite les séquences de Betti des points voisins. Si deux points ont des séquences similaires (ce qui signifie que leurs voisinages évoluent de la même manière lors du zoom arrière), ils sont considérés comme « topologiquement similaires », même s'ils ne sont pas physiquement les plus proches.
Le Nettoyage : L'algorithme utilise ces similitudes pour nettoyer la carte. Il élimine les « valeurs aberrantes » ou les voisins qui ne correspondent pas au schéma topologique, créant ainsi une carte plus propre et plus précise de la structure réelle des données.
Le Tri Final : Enfin, il utilise une technique mathématique standard (le clustering spectral) sur cette nouvelle carte tenant compte de la topologie pour regrouper les données en grappes (clusters).

Ce Qu'Ils Ont Trouvé

Les auteurs ont testé le BFTC sur une variété de jeux de données complexes, y compris des données synthétiques conçues pour tromper d'autres algorithmes. Ceux-ci comprenaient :

Tori Liés : Deux donuts (tori) qui sont imbriqués comme une chaîne.
Formes Tordues : Des données qui forment des spirales, des cercles et des sphères mélangées.
Données du Monde Réel : Des jeux de données comme le « Zoo » (classification des animaux), « Ecoli » (bactéries) et « MNIST » (chiffres manuscrits).

Les résultats ont été très prometteurs. Dans les simulations, le BFTC a systématiquement surpassé les autres méthodes de pointe, y compris les anciennes approches topologiques comme ToMATo, TPCC et TKM. Par exemple, sur le jeu de données « Tori Liés » (où deux donuts sont emmêlés), le BFTC a obtenu des scores quasi parfaits (ARI de 1,00 et NMI de 1,00), tandis que d'autres méthodes peinaient à séparer les deux formes imbriquées. Même lorsque les chercheurs ont ajouté du bruit (statique aléatoire) aux données, le BFTC est resté robuste, suggérant qu'il peut bien gérer les informations réelles et désordonnées.

L'article a également exploré comment différents réglages affectent les résultats. Ils ont découvert que l'utilisation de la similitude cosinus (comparer la direction des séquences de Betti plutôt que simplement leur taille) fonctionnait mieux que les mesures de distance standard. Ils ont également découvert que la taille du « voisinage » est importante : si le voisinage est trop petit, il manque la vue d'ensemble ; s'il est trop grand, il connecte des formes sans rapport. Cependant, en ajustant ces paramètres, le BFTC a réussi à identifier des structures complexes que d'autres algorithmes avaient manquées.

Ce Qu'Il Ne Fait Pas (Encore)

Il est important de noter ce que l'article ne prétend pas. Les auteurs ne disent pas que cette méthode est une solution miracle pour tous les problèmes. Ils soulignent explicitement que leur méthode repose sur le calcul des nombres de Betti, ce qui peut devenir coûteux en termes de calcul si l'on tente de compter des trous de très haute dimension (comme des trous en 4D ou 5D) dans des ensembles de données massifs. Ils suggèrent que pour les très hautes dimensions, il est préférable de s'en tenir aux dimensions plus basses (comme 0, 1 ou 2) où les mathématiques sont gérables.

De plus, bien que l'article prouve mathématiquement que l'algorithme est stable (ce qui signifie que de petits changements dans les données ne provoquent pas l'effondrement des résultats), ces preuves sont théoriques et basées sur des hypothèses. Les succès réels présentés dans l'article sont basés sur des simulations et des expériences sur des jeux de données spécifiques, et non sur une garantie universelle pour toutes les données possibles de l'univers. Les auteurs suggèrent que les travaux futurs pourraient se concentrer sur la manière de rendre la méthode plus rapide pour les jeux de données à grande échelle et sur l'exploration de la façon de choisir automatiquement les meilleurs réglages sans aide humaine.

En bref, le BFTC suggère qu'en écoutant la « forme » des données à travers l'évolution de leurs trous et de leurs boucles, nous pouvons trier des informations complexes et emmêlées bien mieux qu'en mesurant simplement la proximité entre les points.

Résumé Technique : Regroupement Topologique basé sur la Filtration des Nombres de Betti (BFTC)

1. Énoncé du Problème

Les algorithmes de regroupement traditionnels (ex. : k-Means, DBSCAN, Clustering Spectral) reposent fortement sur des mesures de similitude euclidiennes ou basées sur des noyaux. Bien qu'efficaces pour de nombreuses applications, ces méthodes peinent souvent face à des ensembles de données présentant des structures géométques complexes, telles que des formes non convexes, des échelles multiples ou des variétés entrelacées. Elles échouent fréquemment à capturer les caractéristiques topologiques intrinsèques comme les boucles, les vides et la connectivité de dimension supérieure.

Les approches existantes de l'Analyse des Données Topologiques (TDA) tentent de combler cette lacune mais font face à des limitations spécifiques :

ToMATo : Repose sur l'homologie de dimension 0 (composantes connexes) et des paysages de densité, ce qui limite sa capacité à incorporer des informations topologiques de dimension supérieure.
TPCC : Utilise des complexes simpliciaux et des Laplaciens de Hodge, mais peut éprouver des difficultés à distinguer les régions où les caractéristiques topologiques émergent à différentes échelles de filtration.
Topological k-Means (TKM) : Imbrique les diagrammes de persistance dans des Espaces de Hilbert à Noyau Reproduisant (RKHS), mais se concentre sur des résumés topologiques globaux plutôt que sur une topologie locale et multi-échelle.

Le défi central abordé par ce travail est le besoin d'un algorithme de regroupement capable de capturer simultanément la proximité géométrique locale et les structures topologiques de dimension supérieure de manière multi-échelle, sans dépendre uniquement de résumés de persistance globaux ou d'échelles topologiques fixes.

2. Méthodologie : Algorithme BFTC

La méthode proposée, le Regroupement Topologique basé sur la Filtration des Nombres de Betti (BFTC), construit une structure de similitude sensible à la topologie via les étapes suivantes :

A. Construction du Graphe de Voisinage

L'algorithme commence par construire un graphe de voisinage local pour l'ensemble de données $X$ . Il prend en charge deux variantes :

k-NN BFTC : Utilise un graphe de k-plus proches voisins pour assurer une cardinalité uniforme et une parcité contrôlée.
$\epsilon$ -BFTC : Utilise un graphe de voisinage $\epsilon$ basé sur un rayon géométrique fixe, s'alignant naturellement avec les constructions de seuils métriques.

B. Filtration de Vietoris-Rips Locale et Séquences de Betti

Pour chaque point de donnée $x_i$ , l'algorithme construit une série de complexes de Vietoris-Rips (VR) imbriqués sur son voisinage local $N(x_i) \cup \{x_i\}$ .

Une échelle de filtration est définie par une séquence de seuils $\epsilon_1, \epsilon_2, \dots, \epsilon_L$ .
Pour chaque échelle, le complexe VR $VR(x_i, \epsilon_l)$ est formé.
Nombres de Betti : L'algorithme calcule les nombres de Betti $\beta_m$ jusqu'à une dimension maximale $M$ spécifiée par l'utilisateur (où $M$ reflète la complexité topologique intrinsèque, et non nécessairement la dimension ambiante des caractéristiques).
Séquences de Betti : Pour chaque dimension $m \in [0, M]$ , la séquence des nombres de Betti à travers les échelles de filtration forme une séquence de Betti $\beta^{(i)}_m = (\beta^{(i)}_{1m}, \dots, \beta^{(i)}_{Lm})$ . Ces séquences servent de signatures topologiques multi-échelles du voisinage local.

C. Similitude Sensible à la Topologie et Raffinement du Graphe

L'algorithme quantifie la similitude topologique entre les points voisins en comparant leurs séquences de Betti.

Métrique de Similitude : La similitude cosinus est calculée entre les séquences de Betti des points adjacents $x_i$ et $x_j$ pour chaque dimension $m$ :
$(d_{ij})_m = \frac{\langle \beta^{(i)}_m, \beta^{(j)}_m \rangle}{\|\beta^{(i)}_m\| \|\beta^{(j)}_m\|}$
Suppression des Valeurs Aberrantes (Outliers) : Un ensemble de seuils $\alpha_0, \dots, \alpha_M$ est appliqué. Un voisin $x_j$ est conservé dans le voisinage raffiné $N'(x_i)$ uniquement si $(d_{ij})_m \geq \alpha_m$ pour toutes les dimensions $m$ . Cette étape élimine les voisins topologiquement dissemblables et les valeurs aberrantes, produisant un graphe plus parcimonieux et plus informatif.

D. Clustering Spectral

Une matrice d'adjacence pondérée symétrique $A'$ est construite à partir du graphe raffiné en utilisant un noyau gaussien. La matrice Laplacienne $L' = D' - A'$ est calculée, et le clustering spectral (via k-Means sur les vecteurs propres des $p$ plus petites valeurs propres) est appliqué pour obtenir les clusters finaux.

3. Principales Contributions

L'article présente trois contributions majeures :

Nouvel Algorithme (BFTC) : Un algorithme de regroupement efficace qui construit des complexes de Vietoris-Rips sur des voisinages locaux et évalue les nombres de Betti jusqu'à une dimension prescrite. Il utilise des séquences de Betti pour mesurer la similitude topologique, allant au-delà de la simple connectivité ( $\beta_0$ ) pour capturer des caractéristiques de dimension supérieure.
Efficacité sur les Structures Complexes : La méthode est spécifiquement conçue pour traiter des ensembles de données aux formes et structures complexes et entrelacées en exploitant les caractéristiques topologiques sous-jacentes à travers plusieurs échelles.
Analyse Théorique : L'article fournit des fondements théoriques étendus concernant la convergence et la stabilité de BFTC. Il établit que, sous des conditions raisonnables de séparation géométrique et spectrale, l'algorithme est structurellement stable ; de petites perturbations dans les données d'entrée ne modifient pas le regroupement résultant (à permutation de labels près).

4. Résultats Expérimentaux

Les auteurs ont évalué BFTC (variantes k-NN et $\epsilon$ ) contre des méthodes de référence de pointe (k-Means, Spectral, DBSCAN, ToMATo, TPCC, TKM, etc.) sur des ensembles de données synthétiques et réels.

Ensembles de Données Synthétiques : Sur des jeux de données avec des structures non convexes et entrelacées (ex. : Linked Tori, 3MC, Smile1, Torus Sphere Line), BFTC a systématiquement obtenu des scores d'indice de Rand ajusté (ARI) et d'information mutuelle normalisée (NMI) supérieurs. Par exemple, sur le jeu de données Linked Tori avec du bruit ( $\rho=0.3$ ), k-NN BFTC a atteint un ARI de 0,49 et un NMI de 0,56, surpassant nettement les concurrents comme DBSCAN (0,01 ARI) et ToMATo (0,17 ARI).
Ensembles de Données Réels : Les expériences sur les jeux de données UCI (Zoo, Ecoli, Wisconsin B.C., Glass, ORHD, MNIST, Phishing URL) ont démontré que BFTC surpasse presque tous les concurrents.
Robustesse : La méthode a montré une stabilité face aux perturbations de bruit gaussien.
Études d'Ablation :
- Construction du Voisinage : Les voisinages k-NN et $\epsilon$ se sont tous deux révélés efficaces, bien que le k-NN offre un comportement spectral plus fluide pour les variétés très entrelacées.
- Métriques de Distance : La similitude cosinus entre les séquences de Betti s'est avérée nettement plus efficace que la distance euclidienne pour capturer les relations topologiques.
- Fonctions de Noyau : L'inclusion d'un noyau gaussien dans la matrice d'adjacence a amélioré les performances par rapport aux graphes non pondérés.

5. Signification et Revendications

L'article affirme que BFTC représente une avancée significative en intégrant l'information topologique multi-échelle directement dans le processus de regroupement. Contrairement aux méthodes précédentes qui reposent sur des résumés de persistance globaux ou des échelles fixes, BFTC capture une topologie locale multi-échelle via des séquences de Betti.

Les auteurs soutiennent que cette approche permet à l'algorithme de :

Distinguer les régions d'une variété où les caractéristiques topologiques émergent à différentes échelles de filtration.
Capturer simultanément la proximité géométrique et les structures topologiques de dimension supérieure (boucles, vides).
Fournir une solution robuste pour les ensembles de données aux structures complexes, non convexes et entrelacées là où les méthodes traditionnelles basées sur l'Euclidien échouent.

L'analyse théorique soutient davantage les résultats empiriques, affirmant que BFTC est non seulement calculablement fini, mais aussi structurellement stable, garantissant que le pipeline de regroupement est localement invariant aux petites perturbations des données d'entrée. Le travail conclut que l'exploration des aspects topologiques pour les ensembles de données à grande échelle avec des structures complexes et chevauchantes reste une direction prometteuse pour la recherche future.