📊 statistics

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

Este artigo apresenta os pacotes de software `focus` e `focus-cpt` para R e Python, que implementam uma família de algoritmos exatos e eficientes para detecção rápida de pontos de mudança on-line em fluxos de dados univariados e multivariados, ao aproveitar a relação geométrica entre candidatos a pontos de mudança e a estrutura dos dados para alcançar complexidade computacional logarítmica sem aproximações.

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

Publicado 2026-07-23

📖 8 min de leitura🧠 Leitura aprofundada

CC BY 4.0

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

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

A Ciência de Detectar a Mudança Repentina

Imagine que você está observando um rio. Na maior parte do tempo, a água flui em um ritmo constante e previsível. Mas, de repente, uma enorme rocha cai ou uma nascente oculta irrompe, e a corrente muda instantaneamente. No mundo da ciência de dados, isso é chamado de detecção de mudança de ponto (changepoint detection). É a arte de identificar o momento exato em que um processo muda de um comportamento para outro. Seja um monitor cardíaco detectando um batimento irregular, um carro autônomo percebendo um pedestre saindo da calçada ou um satélite sentindo um surto de energia vindo do espaço profundo, encontrar essas "rochas" em tempo real é crucial.

No entanto, há um problema. À medida que os dados chegam — milhões de pontos por segundo — verificar cada possibilidade de mudança torna-se um pesadelo computacional. É como tentar encontrar um grão de areia específico em uma praia, medindo cada grão individualmente desde o início dos tempos toda vez que um novo grão chega. É aqui que entra a detecção de mudança de ponto online (online changepoint detection): o desafio de encontrar a mudança enquanto ela acontece, sem ficar preso pelo passado. O artigo que você está prestes a ler aborda esse problema com um novo conjunto de ferramentas ultrarrápidas, projetado para capturar essas mudanças em fluxos de dados, desde simples leituras de temperatura até sinais complexos e multidimensionais, tudo isso rodando rápido o suficiente para decisões em tempo real.

O Artigo: Um Velocista para Fluxos de Dados

Os autores, uma equipe de estatísticos e cientistas da computação, construíram um novo pacote de software chamado focus (e seu gêmeo em Python, focus-cpt) que atua como um detetive altamente eficiente para fluxos de dados. A principal descoberta deles é que podem calcular a "Razão de Verossimilhança Generalizada" (GLR) — um teste estatístico sofisticado que pergunta: "Algo acabou de mudar?" — com uma velocidade incrível e sem abrir mão da precisão.

Normalmente, verificar uma mudança em uma longa lista de números é lento. Se você tem $n$ pontos de dados, um método ingênuo exige a verificação de todos os pontos de partida possíveis para uma mudança, o que consome uma enorme capacidade de processamento (especificamente, $O(n^2)$ operações). Os autores mostram que seu novo método, o algoritmo focus, pode realizar exatamente esse mesmo cálculo, mas de forma muito mais rápida. Em vez de verificar cada grão de areia, eles usam um truque geométrico inteligente. Eles imaginam os pontos de dados como uma forma (um envelope convexo ou convex hull) e percebem que apenas os "cantos" dessa forma importam. Ao ignorar os pontos dentro da forma, eles conseguem reduzir a lista de candidatos a um tamanho minúsculo e gerenciável. Isso significa que o tempo necessário para verificar uma mudança cresce de forma muito lenta (logaritmicamente) mesmo à medida que o fluxo de dados se torna enorme, tornando-o perfeito para aplicações em tempo real.

O que o artigo descarta:
Os autores argumentam explicitamente contra o uso de "aproximações" para acelerar o processo. Muitos outros métodos tentam adivinhar a resposta ou simplificar a matemática para economizar tempo, mas os autores insistem que seu método calcula o estatístico GLR de forma exata. Eles provam que você não precisa sacrificar a precisão pela velocidade; é possível ter a resposta precisa sem o tempo de processamento lento. Eles também descartam a ideia de que você deve reexaminar todo o histórico de dados toda vez que um novo ponto chega. O método deles atualiza a lista de "suspeitos" (pontos de mudança candidatos) incrementalmente, descartando aqueles que não são mais relevantes.

Quão seguros eles estão?
O artigo apresenta o método como um fato matemático: o algoritmo calcula o estatístico exato. No entanto, as alegações de desempenho — especificamente que é rápido o suficiente para uso em tempo real e funciona bem em cenários complexos — são sustentadas por simulações e demonstrações, em vez de uma prova universal única para todos os cenários do mundo real. Os autores mostram, através de vários exemplos (dados simulados e estudos de caso do mundo real), que o método funciona conforme anunciado. Por exemplo, em suas simulações, eles mostram que, para um conjunto de dados de 6 dimensões, sua aproximação de "projeção" é significativamente mais rápida (levando cerca de 0,166 segundos comparado a 10,409 segundos para o método completo), enquanto produz resultados quase idênticos (uma diferença relativa média de apenas 0,0037).

O Kit de Ferramentas: Como Funciona no Mundo Real

O pacote está disponível tanto para R quanto para Python, duas linguagens populares de ciência de dados, e ambos compartilham o mesmo "cérebro" (um backend em C++), o que significa que produzem resultados idênticos. Isso facilita para os cientistas alternarem entre linguagens sem alterar sua lógica.

O kit de ferramentas é incrivelmente flexível. Ele pode lidar com:

Dados simples: Como um único fluxo de números (ex: temperatura).
Dados complexos: Múltiplos fluxos simultâneos (ex: um sensor em um satélite medindo calor, pressão e radiação ao mesmo tempo).
Diferentes tipos de dados: Funciona com dados que seguem padrões específicos (como a curva de sino de uma distribuição Gaussiana ou a contagem de eventos de uma distribuição de Poisson) e até com dados onde você não conhece o padrão (não paramétricos).

Os autores demonstram essa flexibilidade com alguns exemplos reais interessantes:

Basquete da NBA: Eles analisaram as pontuações de "Plus-Minus" do Cleveland Cavaliers. Ao usar um detector personalizado que observava mudanças tanto na média quanto na variabilidade das pontuações, eles conseguiram identificar o momento em que o desempenho do time mudou, o que coincidiu com o retorno de um jogador famoso.
Explosões de Raios Gama: Na vastidão do espaço, explosões de raios gama são flashes intensos de energia que duram apenas uma fração de segundo. Os autores usaram sua ferramenta Python para detectar essas explosões em tempo real a partir de dados de satélites. Como a ferramenta é muito rápida, ela consegue identificar o momento mais significativo da explosão conforme ela ocorre, sem precisar saber de antemão quanto tempo a explosão durará.
Picos Cerebrais: Eles aplicaram a ferramenta a dados de imagem de cálcio, que medem a atividade elétrica dos neurônios. Ao usar dois detectores — um observando picos para cima e outro para quedas — eles puderam inferir quando os neurônios disparavam em tempo real, um passo crucial para experimentos de "malha fechada" (closed-loop), onde um computador reage à atividade cerebral instantaneamente.

A "Magia" por trás da Velocidade

Para entender por que isso é importante, imagine que você é um segurança observando a transmissão de vídeo de uma rua movimentada. Um sistema ingênuo pararia o vídeo, voltaria ao início e verificaria cada quadro para ver se uma pessoa trocou de roupa. Isso levaria uma eternidade. O algoritmo focus é como um guarda que apenas lembra os "cantos" do movimento da multidão. Se uma pessoa caminha em linha reta, o guarda a ignora. Mas no momento em que alguém faz uma curva brusca (uma mudança), o guarda a sinaliza instantaneamente.

O artigo explica que essa lógica de "cantos" vem da geometria dos dados. Ao converter os dados em uma forma específica, o algoritmo pode provar matematicamente que qualquer ponto dentro da forma é impossível de ser o início de uma mudança. Isso permite que o computador "podar" (cortar) milhares de verificações desnecessárias instantaneamente.

Para dados de alta dimensão (onde você tem muitos sensores), os autores introduzem um atalho inteligente. Em vez de tentar encontrar os cantos de uma forma complexa e multidimensional (o que é difícil), eles projetam os dados em fatias menores e sobrepostas de 2D ou 3D, encontram os cantos ali e combinam os resultados. Eles mostram em suas simulações que este método de "projeção" é vastamente mais rápido do que tentar calcular a forma completa, mas captura as mudanças tão bem quanto o original.

Por Que Isso Importa

O objetivo final deste artigo é fornecer uma interface comum, rápida e precisa para cientistas e engenheiros que precisam detectar mudanças em fluxos de dados agora mesmo. Seja monitorando a saúde de uma rede elétrica, detectando um ataque cibernético ou decodificando o sinal de um neurônio, a capacidade de processar dados de forma exata e eficiente em tempo real é um divisor de águas. Os autores conseguiram unir a teoria estatística complexa e o software prático e utilizável, provando que você não precisa escolher entre ser rápido e ser correto. Você pode ter ambos.

Resumo Técnico: focus e focus-cpt

Declaração do Problema

O artigo aborda o desafio da detecção de pontos de mudança (changepoint detection) online rápida em fluxos de dados univariados e multivariados. Embora a detecção de pontos de mudança offline tenha visto avanços metodológicos significativos, aplicações do mundo real em engenharia, cibersegurança, neurociência e astrofísica exigem cada vez mais a análise em tempo real de dados de alta frequência.

O problema estatístico central envolve testar se a distribuição subjacente de um fluxo de dados mudou em uma localização desconhecida. A abordagem padrão utiliza o teste de Razão de Verossimilhança Generalizada (GLR), que compara a verossimilhança dos dados sob uma hipótese nula (sem mudança) contra uma hipótese alternativa (uma mudança ocorreu em algum momento $\tau$ desconhecido). No entanto, uma implementação sequencial ingênua do teste GLR requer $O(n)$ operações por passo de tempo para avaliar todos os $n-1$ locais candidatos de ponto de mudança, resultando em uma complexidade total de $O(n^2)$ . Esse fardo computacional torna o teste GLR exato inviável para aplicações reais de tempo real envolvendo fluxos de dados longos.

Metodologia

O artigo apresenta a família de algoritmos focus, implementada nos pacotes focus (R) e focus-cpt (Python). Esses algoritmos computam a estatística GLR de forma exata (sem aproximação), mas alcançam um custo por iteração de aproximadamente $O(\log(n)^d)$ para uma sequência $d$ -dimensional.

Insight Algorítmico Central

A eficiência do algoritmo focus baseia-se em um insight geométrico que conecta a localização dos candidatos a pontos de mudança à geometria do passeio aleatório dos dados.

Poda via Cascos Convexos (Convex Hulls): O algoritmo identifica que apenas um subconjunto de pontos de mudança candidatos $\tau$ poderá ser o maximizador da estatística GLR para qualquer par de parâmetros pré e pós-mudança $(\theta_0, \theta_1)$ .
Representação Geométrica: Ao definir um vetor dependente dos dados $P(\tau) = (\tau, \sum_{t=1}^\tau T(y_t))$ e um vetor dependente do modelo $\psi(\theta_0, \theta_1)$ , a razão de log-verossimilhança torna-se um produto escalar $\langle P(\tau), \psi(\theta_0, \theta_1) \rangle$ .
Manutenção do Conjunto Ativo: Maximizar este produto escalar é equivalente a encontrar o vértice do casco convexo do conjunto $\{P(\tau)\}$ que é o mais distante na direção de $\psi$ . Consequentemente, qualquer candidato $\tau$ cujo $P(\tau)$ esteja no interior do casco convexo pode ser permanentemente podado.
Complexidade Computacional:
- Univariado: O algoritmo mantém os vértices do casco usando um método relacionado ao algoritmo de Melkman, alcançando um custo amortizado de $O(1)$ por iteração.
- Multivariado: Para dados $d$ -dimensionais, o tamanho esperado do conjunto de candidatos ativos cresce como $O(\log(n)^d)$ . A implementação utiliza o algoritmo QuickHull intermitentemente para manter o casco. Para altas dimensões, uma aproximação projeta os dados em subconjuntos sobrepostos de $\tilde{d} \leq 5$ coordenadas para reduzir o fardo computacional enquanto retém o desempenho estatístico.

Modelos Suportados

O pacote suporta uma ampla gama de modelos da família exponencial natural e outras estruturas específicas:

Modelos Paramétricos: Gaussiano (mudança na média ou variância), Poisson, Binomial, Exponencial e Gamma.
Não Paramétrico: Um detector baseado na função de distribuição acumulada empírica (eCDF), que transforma o problema em múltiplos problemas de detecção Binomial através de quantis.
Autorregressivo (AR): Um detector para processos AR( $p$ ) que considera dependências temporais e comportamento transitório imediatamente após um ponto de mudança, evitando as armadil-has de uma simples pré-branqueamento (pre-whitening).

Implementação de Software

O pacote fornece interfaces unificadas em R (focus) e Python (focus-cpt), compartilhando um backend em C++. Isso garante paridade funcional e resultados idênticos em ambas as linguagens. A interface suporta:

Modo Online (Sequencial): Atualiza o estado do detector incrementalmente conforme os dados chegam.
Modo Offline (Batch): Processa conjuntos de dados inteiros para análise retrospectiva ou calibração de limiar (threshold).
Modularidade: Separação do estado do detector (lógica de poda) das funções de custo (avaliação de estatística), permitindo que usuários implementem funções de custo personalizadas sem reimplementar o algoritmo de poda central.

Principais Contribuições

GLR Exato com Complexidade Logarítmica: A principal contribuição é um algoritmo que computa a estatística GLR exata com um custo computacional que cresce logaritmicamente com o comprimento da sequência, tornando-o adequado para aplicações de tempo real onde abordagens ingênuas de $O(n^2)$ falham.
Estrutura Unificada: Um único pacote de software suportando uma grande variedade de distribuições (Gaussiana, Poisson, etc.), dimensões (univariado a multivariado) e estruturas de dados (i.i.d., não paramétrico, autorregressivo).
Poda Geométrica: Uma demonstração rigorosa de como a geometria do casco convexo pode ser explorada para podar o espaço de busca de candidatos a pontos de mudança sem sacrificar a otimalidade estatística.
Acessibilidade: Fornecimento de implementações robustas e prontas para produção tanto em R quanto em Python, facilitando a adoção por profissionais de diversas áreas.

Resultados e Aplicações

O artigo valida a metodologia através de exemplos simulados e aplicações do mundo real:

Simulação: Demonstra a habilidade do algoritmo em detectar mudanças em médias, variâncias e mudanças de distribuição não paramétrica. Destaca a eficiência da aproximação baseada em projeção para dados de alta dimensão, mostrando acelerações significativas com perda negligível de precisão estatística.
Pontuações NBA Plus-Minus: Aplicado aos dados de jogos do Cleveland Cavaliers para detectar mudanças no desempenho da equipe (média e variância) ao longo das temporadas. A função de custo personalizada identificou com sucesso a mudança da temporada 2014-2015 correspondente ao retorno de LeBron James, demonstrando robustez contra mudanças de variância.
Detecção de Explosão de Raios Gama (GRB): Utilizado em dados do Fermi-GBM para detectar GRB250814432. O gatilho baseado em focus identificou o intervalo mais significativo da explosão em tempo real sem conhecimento prévio da duração da explosão, superando métodos tradicionais de limiarização em termos de identificação da janela de detecção ideal.
Inferência de Spikes: Aplicado a dados de imagem de cálcio para inferir tempos de disparos (spikes) neuronais em tempo real. Ao usar dois detectores acoplados de um lado (para aumentos e decaimento), o método alcançou processamento de baixa latência adequado para experimentos de malha fechada (closed-loop).

Significância

O artigo posiciona o pacote focus como uma ferramenta crítica para preencher a lacuna entre a teoria estatística rigorosa e as demandas práticas da análise de dados em tempo real. Ao resolver o gargalo computacional do teste GLR exato, ele permite a implantação de detecção de pontos de mudança estatisticamente ótima em cenários anteriormente limitados por métodos aproximados ou mais lentos. Os autores enfatizam que o software foi projetado para ser uma interface comum para a família de algoritmos focus, suportando diversos casos de uso, desde monitoramento de IoT até astrofísica, e facilitando a transição da análise retrospectiva offline para sistemas de decisão online. O trabalho constrói sobre e estende desenvolvimentos metodológicos anteriores (Romano et al. 2023b; Ward et al. 2024; Pishchagina et al. 2025) em um ecossistema de software unificado e acessível.