Como posso detectar programaticamente segmentos de uma série de dados para ajustar-se a diferentes curvas?

14

Existem algoritmos documentados para separar seções de um determinado conjunto de dados em diferentes curvas de melhor ajuste?

Por exemplo, a maioria dos humanos que olha para esse gráfico de dados o divide rapidamente em três partes: um segmento sinusoidal, um segmento linear e o segmento exponencial inverso. De fato, fiz este em particular com uma onda senoidal, uma linha e uma fórmula exponencial simples.

Gráfico de dados com três partes distintas visíveis

Existem algoritmos existentes para encontrar peças como essa, que podem ser ajustadas separadamente em várias curvas / linhas para criar uma espécie de série composta dos melhores ajustes dos subconjuntos dos dados?

Observe que, embora o exemplo tenha as extremidades dos segmentos praticamente alinhadas, isso não será necessariamente o caso; também pode haver um choque repentino nos valores em um corte de segmento. Talvez esses casos sejam mais fáceis de detectar.

Atualização: Aqui está uma imagem de um pequeno pedaço de dados do mundo real: Gráfico do mundo real

Atualização 2: aqui está um conjunto de dados do mundo real incomumente pequeno (apenas 509 pontos de dados):

4,53,53,53,53,58,56,52,49,52,56,51,44,39,39,39,37,33,27,21,18,12,19,30,45,66,92,118,135,148,153,160,168,174,181,187,191,190,191,192,194,194,194,193,193,201,200,199,199,199,197,193,190,187,176,162,157,154,144,126,110,87,74,57,46,44,51,60,65,66,90,106,99,87,84,85,83,91,95,99,101,102,102,103,105,110,107,108,135,171,171,141,120,78,42,44,52,54,103,128,82,103,46,27,73,123,125,77,24,30,27,36,42,49,32,55,20,16,21,31,78,140,116,99,58,139,70,22,44,7,48,32,18,16,25,16,17,35,29,11,13,8,8,18,14,0,10,18,2,1,4,0,61,87,91,2,0,2,9,40,21,2,14,5,9,49,116,100,114,115,62,41,119,191,190,164,156,109,37,15,0,5,1,0,0,2,4,2,0,48,129,168,112,98,95,119,125,191,241,209,229,230,231,246,249,240,99,32,0,0,2,13,28,39,15,15,19,31,47,61,92,91,99,108,114,118,121,125,129,129,125,125,131,135,138,142,147,141,149,153,152,153,159,161,158,158,162,167,171,173,174,176,178,184,190,190,185,190,200,199,189,196,197,197,196,199,200,195,187,191,192,190,186,184,184,179,173,171,170,164,156,155,156,151,141,141,139,143,143,140,146,145,130,126,127,127,125,122,122,127,131,134,140,150,160,166,175,192,208,243,251,255,255,255,249,221,190,181,181,181,181,179,173,165,159,153,162,169,165,154,144,142,145,136,134,131,130,128,124,119,115,103,78,54,40,25,8,2,7,12,25,13,22,15,33,34,57,71,48,16,1,2,0,2,21,112,174,191,190,152,153,161,159,153,71,16,28,3,4,0,14,26,30,26,15,12,19,21,18,53,89,125,139,140,142,141,135,136,140,159,170,173,176,184,180,170,167,168,170,167,161,163,170,164,161,160,163,163,160,160,163,169,166,161,156,155,156,158,160,150,149,149,151,154,156,156,156,151,149,150,153,154,151,146,144,149,150,151,152,151,150,148,147,144,141,137,133,130,128,128,128,136,143,159,180,196,205,212,218,222,225,227,227,225,223,222,222,221,220,220,220,220,221,222,223,221,223,225,226,227,228,232,235,234,236,238,240,241,240,239,237,238,240,240,237,236,239,238,235

Aqui está, com gráficos, com a posição aproximada de algumas arestas conhecidas de elementos do mundo real marcadas com linhas pontilhadas, um luxo que normalmente não teremos:

insira a descrição da imagem aqui

Um luxo que temos, no entanto, é retrospectivo: os dados no meu caso não são uma série temporal, mas são relacionados espacialmente; faz sentido analisar todo um conjunto de dados (geralmente 5000 - 15.000 pontos de dados) de uma só vez, não de maneira contínua.

whybird
fonte
1
ps primeiro post no CV; Sou desenvolvedor de software e normalmente saio mais com isso. Desculpas se violei tabus locais. Muitas das minhas buscas por respostas chegaram aqui, então achei que esse seria o melhor lugar para perguntar.
whybird
Por que você não publica os dados e tentarei responder sua pergunta por exemplo.
IrishStat
Uma possibilidade seria ajustar toda a família de curvas de uma só vez, usando um metamodelo. Para tornar as coisas mais precisas, suponha que seu objetivo final seja suavizar esse histograma, digamos, usando um KDE. Então, sua estimativa suave do KDE será mais precisa se você usar um modelo no qual a largura do kernel possa variar no intervalo de valores de como no modelo usado aqui, equações (2) - (3)x
user603
1
Você construiu o exemplo para que a idéia faça sentido: até agora, tudo bem. Com histogramas reais, é muito mais comum que uma forma complicada reflita uma mistura de distribuições sobrepostas: o interesse não está nos pontos de mudança no histograma observado, que geralmente não existem de maneira convincente ou não são a maneira correta de pensar em misturas. É possível, no entanto, que você esteja usando o "histograma" de uma maneira muito mais ampla do que o padrão na ciência estatística, onde isso significa gráfico de barras de distribuição de frequência ou probabilidade (apenas).
Nick Cox
@IrishStat - os conjuntos de dados usuais têm de 5000 a 15000 entradas. Eu estava tentando preparar um real resumido aqui, mas acabou sendo um exemplo ruim e tive que começar de novo. Por outro lado, fazer isso sugeriu uma resposta parcial para mim em termos de simplesmente suavizar e calcular a média de agrupamentos de dados para procurar inicialmente padrões, a serem refinados mais tarde, então obrigado por isso :) parece que poderia ser bom; Vou acrescentar isso à pergunta quando puder.
whybird

Respostas:

2

Minha interpretação da pergunta é que o OP está procurando metodologias que se encaixem na (s) forma (s) dos exemplos fornecidos, não nos resíduos do HAC. Além disso, são desejadas rotinas automatizadas que não requerem intervenção significativa de analistas ou humanos. Box-Jenkins pode não ser apropriado, apesar da ênfase nesse segmento, pois exige um envolvimento substancial dos analistas.

Existem módulos R para esse tipo de correspondência de padrão não baseada em momento. O agrupamento de distribuição de permutação é uma técnica de correspondência de padrões desenvolvida por um cientista do Instituto Max Planck que atende aos critérios descritos. Sua aplicação é para dados de séries temporais, mas não se limita a isso. Aqui está uma citação para o módulo R que foi desenvolvido:

pdc: um pacote R para agrupamento baseado em complexidade de séries temporais por Andreas Brandmaier

Além do PDC, há a rotina de aprendizado de máquina, iSax, desenvolvida por Eamon Keogh na UC Irvine, que também vale a pena comparar.

Finalmente, há este artigo sobre Data Smashing: Descobrindo a Ordem Espreita nos Dadospor Chattopadhyay e Lipson. Além do título inteligente, existe um objetivo sério no trabalho. Aqui está o resumo: "Do reconhecimento automático de fala à descoberta de estrelas incomuns, subjacente a quase todas as tarefas de descoberta automatizada está a capacidade de comparar e contrastar fluxos de dados entre si, para identificar conexões e detectar discrepâncias. Apesar da prevalência de dados, no entanto, métodos automatizados Um gargalo importante é que a maioria dos algoritmos de comparação de dados hoje conta com um especialista humano para especificar quais 'características' dos dados são relevantes para comparação. Aqui, propomos um novo princípio para estimar a semelhança entre as fontes de fluxos de dados, sem conhecimento de domínio nem aprendizado. Demonstramos a aplicação desse princípio à análise de dados de vários problemas desafiadores do mundo real, incluindo a desambiguação de padrões eletro-encefalográficos relativos a crises epilépticas, detecção de atividade cardíaca anômala a partir de gravações de som cardíaco e classificação de objetos astronômicos a partir de fotometria bruta. Em todos esses casos e sem acesso a nenhum conhecimento de domínio, demonstramos desempenho em pé de igualdade com a precisão alcançada por algoritmos e heurísticos especializados desenvolvidos por especialistas em domínio. Sugerimos que os princípios de esmagamento de dados possam abrir as portas para o entendimento de observações cada vez mais complexas, especialmente quando os especialistas não sabem o que procurar ". Em todos esses casos e sem acesso a nenhum conhecimento de domínio, demonstramos desempenho em pé de igualdade com a precisão alcançada por algoritmos e heurísticos especializados desenvolvidos por especialistas em domínio. Sugerimos que os princípios de esmagamento de dados possam abrir as portas para o entendimento de observações cada vez mais complexas, especialmente quando os especialistas não sabem o que procurar ". Em todos esses casos e sem acesso a nenhum conhecimento de domínio, demonstramos desempenho em pé de igualdade com a precisão alcançada por algoritmos e heurísticos especializados desenvolvidos por especialistas em domínio. Sugerimos que os princípios de esmagamento de dados possam abrir as portas para o entendimento de observações cada vez mais complexas, especialmente quando os especialistas não sabem o que procurar ".

Essa abordagem vai muito além do ajuste curvilíneo. Vale a pena conferir.

Mike Hunter
fonte
Obrigado - você está certo de que o que eu quero é encontrar clusters automaticamente, sem intervenção do analista. Para o que eu quero fazer para trabalhar, precisarei dividir conjuntos de dados de 5000 a 15000 pontos de dados em clusters que se adaptem bem a fórmulas simples (incluindo repetitivas) sem intervenção humana sobre grupos de cerca de 50000 desses conjuntos de dados em um prazo tolerável por humanos em hardware de computador doméstico.
whybird
Quanto a qual curva se encaixa em cada cluster, depois de detectar os limites por qualquer meio, é simples o suficiente para tentar modelos diferentes (onda senoidal, polinomial, exponencial) e ver qual dá um r ^ 2 comum melhor.
whybird
2
OK, acho que a falta de comunicação decorre disso: Sax e iSax são formatos de representação para armazenamento e processamento de séries temporais, não são algoritmos de clustering ou detecção de segmento / padrão (por postagem do OP). Pelo que entendi, sua resposta foi que Keogh criou um algoritmo baseado no formato de representação SAX e que resolve o problema do OP. Mas acho que não foi isso que você quis dizer?
Zhubarb
2
OK, não há necessidade de entrar em contato com Keogh, eu sei sobre o iSax e Sax , eles são formatos de representação para mineração eficiente de séries temporais. Os links os explicam. iSax é a versão mais recente. Fiquei empolgado com o meu mal-entendido da sua resposta, daí as perguntas (não tentando ser pedante) :).
Zhubarb
2
eu não estava tentando esconder nada, interpretei 'rotina isax' como um algoritmo operando em isax. Sugiro que sua resposta precise ser reformulada / modificada após o esclarecimento.
Zhubarb 17/06/2015
2

A detecção de pontos de mudança em uma série temporal requer a construção de um modelo ARIMA global robusto (certamente defeituoso por alterações de modelo e alterações de parâmetros ao longo do tempo no seu caso) e, em seguida, identificando o ponto de mudança mais significativo nos parâmetros desse modelo. Usando seus valores 509, o ponto de mudança mais significativo foi o período 353. Usei alguns algoritmos proprietários disponíveis no AUTOBOX (que eu ajudei a desenvolver) que poderiam ser licenciados para o seu aplicativo personalizado. A idéia básica é separar os dados em duas partes e, ao encontrar o ponto de mudança mais importante, analise novamente cada um dos dois intervalos de tempo separadamente (1-352; 353-509) para determinar outros pontos de mudança em cada um dos dois conjuntos. Isso é repetido até você ter k subconjuntos. Anexei o primeiro passo usando essa abordagem.insira a descrição da imagem aqui

insira a descrição da imagem aqui

IrishStat
fonte
Por que 353 é sinalizado quando 153 e 173 têm valores P mais baixos?
Nick Cox
@NickCox Good question! Ótimo comentário Para propósitos de previsão, a idéia é separar o subconjunto (mais significativo) mais recente do subconjunto mais antigo, motivo pelo qual 353 venceram ...
IrishStat
O título "PONTO DE
INTERRUPÇÃO
Obrigado! Isso é realmente interessante e muito apreciado. Posso entrar em contato com você para obter mais detalhes.
whybird
Obrigado pela explicação: a ideia é realmente explícita na última nota. (aliás, eu não vejo muito UPPER CASE na saída do programa desde o início dos anos 90. Eu recomendaria mudar "nível de confiança de 95%" para "nível de significância de 5%", assumindo que é isso que se entende.)
Nick Cox
2

Eu acho que o título do thread é enganoso: você não está procurando comparar funções de densidade, mas está realmente procurando por rupturas estruturais em uma série temporal. No entanto, você não especifica se essas quebras estruturais devem ser encontradas em uma janela de tempo rolante ou em retrospectiva, observando o histórico total da série temporal. Nesse sentido, sua pergunta é na verdade uma duplicata: Que método para detectar quebras estruturais em séries temporais?

Conforme mencionado por Rob Hyndman neste link, o R oferece o pacote strucchange para esse fim. Eu brinquei com seus dados, mas devo dizer que os resultados são decepcionantes [o primeiro ponto de dados é realmente 4 ou deveria ser 54?]:

raw = c(54,53,53,53,53,58,56,52,49,52,56,51,44,39,39,39,37,33,27,21,18,12,19,30,45,66,92,118,135,148,153,160,168,174,181,187,191,190,191,192,194,194,194,193,193,201,200,199,199,199,197,193,190,187,176,162,157,154,144,126,110,87,74,57,46,44,51,60,65,66,90,106,99,87,84,85,83,91,95,99,101,102,102,103,105,110,107,108,135,171,171,141,120,78,42,44,52,54,103,128,82,103,46,27,73,123,125,77,24,30,27,36,42,49,32,55,20,16,21,31,78,140,116,99,58,139,70,22,44,7,48,32,18,16,25,16,17,35,29,11,13,8,8,18,14,0,10,18,2,1,4,0,61,87,91,2,0,2,9,40,21,2,14,5,9,49,116,100,114,115,62,41,119,191,190,164,156,109,37,15,0,5,1,0,0,2,4,2,0,48,129,168,112,98,95,119,125,191,241,209,229,230,231,246,249,240,99,32,0,0,2,13,28,39,15,15,19,31,47,61,92,91,99,108,114,118,121,125,129,129,125,125,131,135,138,142,147,141,149,153,152,153,159,161,158,158,162,167,171,173,174,176,178,184,190,190,185,190,200,199,189,196,197,197,196,199,200,195,187,191,192,190,186,184,184,179,173,171,170,164,156,155,156,151,141,141,139,143,143,140,146,145,130,126,127,127,125,122,122,127,131,134,140,150,160,166,175,192,208,243,251,255,255,255,249,221,190,181,181,181,181,179,173,165,159,153,162,169,165,154,144,142,145,136,134,131,130,128,124,119,115,103,78,54,40,25,8,2,7,12,25,13,22,15,33,34,57,71,48,16,1,2,0,2,21,112,174,191,190,152,153,161,159,153,71,16,28,3,4,0,14,26,30,26,15,12,19,21,18,53,89,125,139,140,142,141,135,136,140,159,170,173,176,184,180,170,167,168,170,167,161,163,170,164,161,160,163,163,160,160,163,169,166,161,156,155,156,158,160,150,149,149,151,154,156,156,156,151,149,150,153,154,151,146,144,149,150,151,152,151,150,148,147,144,141,137,133,130,128,128,128,136,143,159,180,196,205,212,218,222,225,227,227,225,223,222,222,221,220,220,220,220,221,222,223,221,223,225,226,227,228,232,235,234,236,238,240,241,240,239,237,238,240,240,237,236,239,238,235)
raw = log(raw+1)
d = as.ts(raw,frequency = 12)
dd = ts.intersect(d = d, d1 = lag(d, -1),d2 = lag(d, -2),d3 = lag(d, -3),d4 = lag(d, -4),d5 = lag(d, -5),d6 = lag(d, -6),d7 = lag(d, -7),d8 = lag(d, -8),d9 = lag(d, -9),d10 = lag(d, -10),d11 = lag(d, -11),d12 = lag(d, -12))

(breakpoints(d ~d1 + d2+ d3+ d4+ d5+ d6+ d7+ d8+ d9+ d10+ d11+ d12, data = dd))
>Breakpoints at observation number:
>151 
>Corresponding to breakdates:
>163 

(breakpoints(d ~d1 + d2, data = dd))
>Breakpoints at observation number:
>95 178 
>Corresponding to breakdates:
>107 190 

Eu não sou um usuário regular do pacote. Como você pode ver, depende do modelo que você se encaixa nos dados. Você pode experimentar

library(forecast)
auto.arima(raw)

que fornece o modelo ARIMA mais adequado.

HOSS_JFL
fonte
Obrigado! Eu editei a palavra 'histograma' do título; Inicialmente, eu o havia usado incorretamente e esqueci de editar o título quando o removi do corpo em uma edição anterior em resposta a um comentário.
whybird
Meus dados são, na verdade, uma série de dados relacionados espacialmente, não são baseados no tempo e geralmente não existirão em linha reta ou mesmo em um plano com bastante frequência - mas você está certo que, em algum nível fundamental, pode ser considerado da mesma forma caminho; Eu acho que isso pode ser parte do motivo de minhas pesquisas anteriores não encontrarem as respostas que eu esperava.
whybird
O primeiro ponto de dados nesse exemplo é realmente um 4, mas pode ser que tenhamos atingido o final de uma estrutura anterior ou talvez tenha sido ruído; Eu ficaria feliz em deixar isso de fora, mas qualquer que seja o sistema que eu invente também terá que lidar com coisas assim.
whybird
Ah, e a análise é retrospectiva. Vou editar a pergunta para esclarecer.
whybird