📊 statistics

focus and focus-cpt: Fast Online Changepoint Detection in R and Python

Cet article présente les progiciels `focus` et `focus-cpt` pour R et Python, qui implémentent une famille d'algorithmes exacts et efficaces pour la détection de points de rupture en ligne rapide sur des flux de données univariées et multivariées en exploitant la relation géométrique entre les candidats de points de rupture et la structure des données afin d'atteindre une complexité computationnelle logarithmique sans approximations.

Auteurs originaux : Gaetano Romano, Kes Ward, Yuntang Fan, Guillem Rigaill, Vincent Runge, Idris A. Eckley, Paul Fearnhead

Publié 2026-07-23

📖 8 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Gaetano Romano, Kes Ward, Yuntang Fan, Guillem Rigaill, Vincent Runge, Idris A. Eckley, Paul Fearnhead

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 science de la détection des changements soudains

Imaginez que vous observez une rivière. La plupart du temps, l'eau s'écoule à un rythme régulier et prévisible. Mais soudain, un énorme rocher tombe, ou une source cachée jaillit, et le courant change instantanément. Dans le monde de la science des données, c'est ce qu'on appelle la détection de points de rupture (changepoint detection). C'est l'art de repérer le moment exact où un processus passe d'un comportement à un autre. Qu'il s'agisse d'un moniteur cardiaque détectant un rythme irrégulier, d'une voiture autonome remarquant un piéton qui descend du trottoir, ou d'un satellite captant un sursaut d'énergie provenant du lointain espace, trouver ces « rochers » en temps réel est crucial.

Cependant, il y a un piège. À mesure que les données arrivent — des millions de points par seconde — vérifier chaque possibilité de changement devient un cauchemar informatique. C'est comme essayer de trouver un grain de sable spécifique sur une plage en mesurant chaque grain de sable depuis le début des temps à chaque fois qu'un nouveau arrive. C'est là qu'intervient la détection de points de rupture en ligne (online changepoint detection) : le défi de trouver le changement au moment où il se produit, sans être freiné par le passé. Le document que vous allez lire s'attaque à ce problème avec un nouvel outil ultra-rapide conçu pour capturer ces changements dans les flux de données, des simples lectures de température aux signaux multidimensionnels complexes, le tout en fonctionnant assez vite pour des décisions en temps réel.

L'article : Un démon de vitesse pour les flux de données

Les auteurs, une équipe de statisticiens et d'informaticiens, ont construit un nouveau package logiciel appelé focus (et son jumeau Python, focus-cpt) qui agit comme un détective ultra-efficace pour les flux de données. Leur principale conclusion est qu'ils peuvent calculer le « Rapport de Vraisemblance Généralisé » (GLR) — un test statistique sophistiqué qui demande : « Quelque chose vient-il de changer ? » — avec une vitesse incroyable et sans prendre de raccourcis.

Habituellement, vérifier un changement dans une longue liste de nombres est lent. Si vous avez $n$ points de données, une méthode naïve nécessite de vérifier chaque point de départ possible pour un changement, ce qui demande une puissance de calcul énorme (spécifiquement, $O(n^2)$ opérations). Les auteurs démontrent que leur nouvelle méthode, l'algorithme focus, peut effectuer exactement ce même calcul mais beaucoup plus rapidement. Au lieu de vérifier chaque grain de sable, ils utilisent une astuce géométrique ingénieuse. Ils imaginent les points de données comme une forme (un enveloppe convexe) et réalisent que seuls les « coins » de cette forme comptent. En ignorant les points situés à l'intérieur de la forme, ils peuvent réduire la liste des candidats à une taille infime et gérable. Cela signifie que le temps nécessaire pour vérifier un changement augmente très lentement (de manière logarithmique) même lorsque le flux de données devient énorme, ce qui est parfait pour les applications en temps réel.

Ce que l'article écarte :
Les auteurs s'opposent explicitement à l'utilisation d'« approximations » pour accélérer les choses. De nombreuses autres méthodes tentent de deviner la réponse ou de simplifier les calculs pour gagner du temps, mais les auteurs insistent sur le fait que leur méthode calcule la statistique GLR de manière exacte. Ils prouvent qu'il n'est pas nécessaire de sacrifier la précision pour la vitesse ; on peut obtenir la réponse précise sans le temps de traitement lent. Ils écartent également l'idée qu'il faille rescanner l'intégralité de l'historique des données à chaque fois qu'un nouveau point arrive. Leur méthode met à jour la liste des « suspects » (points de rupture candidats) de manière incrémentielle, en écartant ceux qui ne sont plus pertinents.

Quelle est leur certitude ?
L'article présente la méthode comme un fait mathématique : l'algorithme calcule la statistique exacte. Cependant, les affirmations de performance — spécifiquement le fait qu'elle soit assez rapide pour une utilisation en temps réel et qu'elle fonctionne bien dans des scénarios complexes — sont étayées par des simulations et des démonstrations plutôt que par une preuve universelle unique pour chaque scénario réel possible. Les auteurs montrent, à travers divers exemples (données simulées et études de cas réels), que la méthode fonctionne comme annoncé. Par exemple, dans leurs simulations, ils montrent que pour un ensemble de données à 6 dimensions, leur approximation par « projection » est nettement plus rapide (prenant environ 0,166 seconde contre 10,409 secondes pour la méthode complète) tout en produisant des résultats presque identiques (une différence relative moyenne de seulement 0,0037).

L'outil : Comment il fonctionne sur le terrain

Le package est disponible pour R et Python, deux langages populaires en science des données, et ils partagent le même « cerveau » (un backend en C++), ce qui signifie qu'ils produisent des résultats identiques. Cela permet aux scientifiques de passer d'un langage à l'autre sans changer leur logique.

L'outil est incroyablement flexible. Il peut gérer :

Des données simples : Comme un flux unique de nombres (ex. : la température).
Des données complexes : Plusieurs flux simultanés (ex. : un capteur sur un satellite mesurant simultanément la chaleur, la pression et le rayonnement).
Différents types de données : Il fonctionne avec des données qui suivent des modèles spécifiques (comme la courbe en cloche d'une distribution gaussienne, ou le décompte d'événements d'une distribution de Poisson) et même avec des données dont on ne connaît pas le modèle (non paramétriques).

Les auteurs démontrent cette flexibilité avec des exemples concrets passionnants :

Basketball NBA : Ils ont analysé les scores « Plus-Minus » des Cleveland Cavaliers. En utilisant un détecteur personnalisé qui surveillait à la fois la moyenne des scores et la variabilité des scores, ils ont réussi à identifier précisément le moment où la performance de l'équipe a changé, ce qui coïncidait avec le retour d'un joueur célèbre.
Sursauts de rayons gamma : Dans l'immensité de l'espace, les sursauts de rayons gamma sont des éclats d'énergie intenses qui ne durent qu'une fraction de seconde. Les auteurs ont utilisé leur outil Python pour détecter ces sursauts en temps réel à partir de données satellites. Grâce à la rapidité de l'outil, il peut identifier le moment le plus significatif du sursaut au moment même où il se produit, sans avoir besoin de savoir à l'avance combien de temps le sursaut durera.
Spikes cérébraux : Ils ont appliqué l'outil à des données d'imagerie calcique, qui mesurent l'activité électrique des neurones. En utilisant deux détecteurs — l'un surveillant les pics vers le haut et l'autre les chutes vers le bas — ils ont pu déduire quand les neurones s'activaient en temps réel, une étape cruciale pour les expériences en « boucle fermée » où un ordinateur réagit instantanément à l'activité cérébrale.

La « magie » derrière la vitesse

Pour comprendre pourquoi c'est important, imaginez que vous êtes un agent de sécurité surveillant le flux vidéo d'une rue bondée. Un système naïf arrêterait la vidéo, reviendrait au début, et vérifierait chaque image pour voir si une personne a changé de vêtements. Cela prendrait une éternité. L'algorithme focus est comme un agent qui ne retient que les « coins » du mouvement de la foule. Si une personne marche en ligne droite, l'agent l'ignore. Mais dès que quelqu'un fait un virage brusque (un changement), l'agent le signale instantanément.

L'article explique que cette logique de « coin » provient de la géométrie des données. En convertissant les données en une forme spécifique, l'algorithme peut prouver mathématiquement que tout point situé à l'intérieur de la forme ne peut pas être le début d'un changement. Cela permet à l'ordinateur d'élaguer (couper) instantanément des milliers de vérifications inutiles.

Pour les données de haute dimension (où vous avez de nombreux capteurs), les auteurs introduisent un raccourci intelligent. Au lieu d'essayer de trouver les coins d'une forme complexe et multidimensionnelle (ce qui est difficile), ils projettent les données sur des tranches 2D ou 3D plus petites et qui se chevauchent, trouvent les coins sur ces tranches, puis combinent les résultats. Ils démontrent dans leurs simulations que cette méthode de « projection » est bien plus rapide que le calcul de la forme complète, tout en capturant les changements de la même manière.

Pourquoi cela importe

L'objectif ultime de cet article est de fournir une interface commune, rapide et précise pour les scientifiques et les ingénieurs qui doivent détecter des changements dans les flux de données immédiatement. Qu'il s'agisse de surveiller la santé d'un réseau électrique, de repérer une cyberattaque ou de décoder le signal d'un neurone, la capacité de traiter les données de manière exacte et efficace en temps réel change la donne. Les auteurs ont réussi à combler le fossé entre la théorie statistique complexe et les logiciels pratiques et utilisables, prouvant qu'il n'est pas nécessaire de choisir entre être rapide et être juste. On peut avoir les deux.

Résumé technique : focus et focus-cpt

Problématique

L'article traite du défi de la détection de points de rupture (changepoint detection) rapide en ligne pour les flux de données univariées et multivariées. Bien que la détection de points de rupture hors ligne ait connu des avancées méthodologiques significatives, les applications réelles en ingénierie, cybersécurité, neurosciences et astrophysique nécessitent de plus en plus une analyse en temps réel de données à haute fréquence.

Le problème statistique central consiste à tester si la distribution sous-jacente d'un flux de données a changé à un emplacement inconnu. L'approche standard utilise le test du Rapport de Vraisemblance Généralisé (GLR), qui compare la vraisemblance des données sous l'hypothèse nulle (pas de changement) par rapport à une hypothèse alternative (un changement s'est produit à un instant $\tau$ inconnu). Une implémentation séquentielle naïve du test GLR nécessite $O(n)$ opérations par pas de temps pour évaluer les $n-1$ localisations de points de rupture candidates, ce qui entraîne une complexité globale de $O(n^2)$ . Cette charge de calcul rend le test GLR exact infaisable pour les véritables applications en temps réel impliquant de longs flux de données.

Méthodologie

L'article présente la famille d'algorithmes focus, implémentée dans les packages focus (R) et focus-cpt (Python). Ces algorithmes calculent la statistique GLR exactement (sans approximation) mais atteignent un coût par itération d'environ $O(\log(n)^d)$ pour une séquence de dimension $d$ .

Intuition algorithmique centrale

L'efficacité de l'algorithme focus repose sur une intuition géométrique reliant la localisation des candidats aux points de rupture à la géométrie de la marche aléatoire des données.

Élagage par enveloppes convexes : L'algorithme identifie qu'un sous-ensemble de points de rupture candidats $\tau$ peut être le maximisateur de la statistique GLR pour toute paire de paramètres pré- et post-changement $(\theta_0, \theta_1)$ .
Représentation géométrique : En définissant un vecteur dépendant des données $P(\tau) = (\tau, \sum_{t=1}^\tau T(y_t))$ et un vecteur dépendant du modèle $\psi(\theta_0, \theta_1)$ , le rapport de log-vraisemblance devient un produit scalaire $\langle P(\tau), \psi(\theta_0, \theta_1) \rangle$ .
Maintenance de l'ensemble actif : Maximiser ce produit scalaire revient à trouver le sommet de l'enveloppe convexe de l'ensemble $\{P(\tau)\}$ qui est le plus éloigné dans la direction de $\psi$ . Par conséquent, tout candidat $\tau$ dont le $P(\tau)$ se situe à l'intérieur de l'enveloppe convexe peut être définitivement élagué.
Complexité de calcul :
- Univarié : L'algorithme maintient les sommets de l'enveloppe en utilisant une méthode liée à l'algorithme de Melkman, atteignant un coût amorti de $O(1)$ par itération.
- Multivarié : Pour des données de dimension $d$ , la taille attendue de l'ensemble de candidats actifs croît comme $O(\log(n)^d)$ . L'implémentation utilise l'algorithme QuickHull de manière intermittente pour maintenir l'enveloppe. Pour les hautes dimensions, une approximation projette les données sur des sous-ensembles de coordonnées chevauchants de taille $\tilde{d} \leq 5$ afin de réduire la charge de calcul tout en préservant la performance statistique.

Modèles supportés

Le package supporte une large gamme de modèles issus de la famille exponentielle naturelle et d'autres structures spécifiques :

Modèles paramétriques : Distributions Gaussienne (changement de moyenne ou de variance), Poisson, Binomiale, Exponentielle et Gamma.
Non-paramétrique : Un détecteur basé sur la fonction de répartition empirique (eCDF), qui transforme le problème en plusieurs problèmes de détection Binomiale à travers les quantiles.
Auto-régressif (AR) : Un détecteur pour les processus AR( $p$ ) qui prend en compte les dépendances temporelles et le comportement transitoire immédiatement après un point de rupture, évitant les pièges du simple blanchiment (pre-whitening).

Implémentation logicielle

Le package fournit des interfaces unifiées en R (focus) et en Python (focus-cpt), partageant un backend C++ commun. Cela garantit une parité fonctionnelle et des résultats identiques entre les deux langages. L'interface supporte :

Mode en ligne (séquentiel) : Met à jour l'état du détecteur de manière incrémentielle à mesure que les données arrivent.
Mode hors ligne (par lots) : Traite des jeux de données entiers pour l'analyse rétrospective ou le calibrage de seuils.
Modularité : Séparation de l'état du détecteur (logique d'élagage) de la fonction de coût (évaluation de la statistique), permettant aux utilisateurs d'implémenter des fonctions de coût personnalisées sans réimplémenter l'algorithme d'élagage central.

Contributions clés

GLR exact avec complexité logarithmique : La contribution principale est un algorithme qui calcule la statistique GLR exacte avec un coût de calcul qui croît logarithmiquement avec la longueur de la séquence, ce qui le rend adapté aux applications en temps réel là où les approches $O(n^2)$ naïves échouent.
Cadre unifié : Un package logiciel unique supportant une grande variété de distributions (Gaussienne, Poisson, etc.), de dimensions (univarié à multivarié) et de structures de données (i.i.d., non-paramétrique, auto-régressif).
Élagage géométrique : Une démonstration rigoureuse de la manière dont la géométrie de l'enveloppe convexe peut être exploitée pour élaguer l'espace de recherche des candidats aux points de rupture sans sacrifier l'optimalité statistique.
Accessibilité : Fournir des implémentations robustes et prêtes pour la production en R et en Python, facilitant l'adoption par les praticiens dans divers domaines.

Résultats et applications

L'article valide la méthodologie à travers des exemples simulés et des applications réelles :

Simulation : Démontre la capacité de l'algorithme à détecter des changements de moyennes, de variances et des décalages de distribution non-paramétriques. Il souligne l'efficacité de l'approximation par projection pour les données de haute dimension, montrant des accélérations significatives avec une perte négligeable de précision statistique.
Scores NBA Plus-Minus : Appliqué aux données de matchs des Cleveland Cavaliers pour détecter les changements de performance de l'équipe (moyenne et variance) au fil des saisons. La fonction de coût personnalisée a identifié avec succès le changement de la saison 2014-2015 correspondant au retour de LeBron James, démontrant une robustesse face aux changements de variance.
Détection de sursauts gamma (GRB) : Utilisé sur les données Fermi-GBM pour détecter le GRB250814432. Le déclencheur basé sur focus a identifié l'intervalle le plus significatif du sursaut en temps réel sans connaissance préalable de la durée du sursaut, surpassant les méthodes de seuillage traditionnelles pour identifier la fenêtre de détection optimale.
Inférence de pics (Spike Inference) : Appliqué aux données d'imagerie calcique pour inférer les temps de pics neuronaux en temps réel. En utilisant deux détecteurs unidirectionnels couplés (pour les augmentations de type "up-changes" et de type "decay"), la méthode a permis un traitement à faible latence adapté aux expériences en boucle fermée.

Signification

L'article positionne le package focus comme un outil critique pour combler le fossé entre la théorie statistique rigoureuse et les exigences pratiques de l'analyse de données en temps réel. En résolvant le goulot d'étranglement computationnel du test GLR exact, il permet le déploiement de la détection de points de rupture statistiquement optimale dans des scénarios auparavant limités par des méthodes approximatives ou plus lentes. Les auteurs soulignent que le logiciel est conçu comme une interface commune pour la famille d'algorithmes focus, supportant des cas d'utilisation diversifiés, de la surveillance de l'IoT à l'astrophysique, et facilitant la transition de l'analyse rétrospective hors ligne vers des systèmes de prise de décision en ligne. Ce travail s'appuie sur et étend les développements méthodologiques précédents (Romano et al. 2023b ; Ward et al. 2024 ; Pishchagina et al. 2025) en un écosystème logiciel unifié et accessible.