Aplicação de wavelets a algoritmos de detecção de anomalias baseados em séries temporais

25

Comecei a trabalhar nos tutoriais de mineração de dados estatísticos de Andrew Moore (altamente recomendado para quem mais se aventurar nesse campo). Comecei lendo este PDF extremamente interessante, intitulado "Visão geral introdutória dos algoritmos de detecção de anomalias baseados em séries temporais", nos quais Moore acompanha muitas das técnicas usadas na criação de um algoritmo para detectar surtos de doenças. No meio dos slides, na página 27, ele lista vários outros "métodos de ponta" usados ​​para detectar surtos. O primeiro listado é wavelets . Wikipeida descreve uma wavelet como

uma oscilação em forma de onda com uma amplitude que começa em zero, aumenta e depois volta a zero. Normalmente pode ser visualizado como uma "breve oscilação"

mas não descreve sua aplicação às estatísticas, e minhas pesquisas no Google produzem trabalhos altamente acadêmicos que pressupõem um conhecimento de como as wavelets se relacionam com estatísticas ou livros completos sobre o assunto.

Gostaria de ter um entendimento básico de como as wavelets são aplicadas à detecção de anomalias de séries temporais, da mesma forma que Moore ilustra as outras técnicas em seu tutorial. Alguém pode fornecer uma explicação de como os métodos de detecção usando wavelets funcionam ou um link para um artigo compreensível sobre o assunto?

Oren Hizkiya
fonte

Respostas:

19

Wavelets são úteis para detectar singularidades em um sinal (veja, por exemplo, o artigo aqui (veja a figura 3 para uma ilustração) e as referências mencionadas neste artigo.Eu acho que singularidades às vezes podem ser uma anomalia?

A idéia aqui é que a Transformada de Onda Contínua (CWT) possui linhas máximas que se propagam ao longo de frequências, ou seja, quanto maior a linha, maior a singularidade. Veja a Figura 3 no artigo para ver o que quero dizer! observe que existe um código Matlab gratuito relacionado a esse documento, ele deve estar aqui .


Além disso, posso fornecer algumas heurísticas que detalham por que a transformada de wavelet DISCRETE ( DWT ) é interessante para um estatístico (desculpe não exaustividade):

  • Existe uma ampla classe de sinais (realistas (espaço de Besov)) que são transformados em uma sequência esparsa pela transformação wavelet. ( propriedade de compactação )
  • Uma ampla classe de processos (quase estacionários) que são transformados em uma sequência com recursos quase não correlacionados ( propriedade decorrelation )
  • Os coeficientes da wavelet contêm informações localizadas no tempo e na frequência (em diferentes escalas). (propriedade de várias escalas)
  • Os coeficientes wavelet de um sinal concentram-se em suas singularidades .
Robin Girard
fonte
19

A lista na apresentação a que você se refere parece bastante arbitrária para mim, e a técnica que seria usada dependerá realmente do problema específico. Você notará, no entanto, que ele também inclui filtros Kalman , então eu suspeito que o uso pretendido seja uma técnica de filtragem. As transformadas Wavelet geralmente se enquadram no assunto do processamento de sinal e geralmente serão usadas como uma etapa de pré-processamento com dados muito ruidosos. Um exemplo é o artigo " Detecção de anomalias em várias escalas " de Chen e Zhan (veja abaixo). A abordagem seria executar uma análise no espectro diferente, e não na série barulhenta original.

As wavelets são frequentemente comparadas a uma transformação de fourier em tempo contínuo, embora tenham o benefício de serem localizadas em tempo e frequência. As wavelets podem ser usadas para compressão de sinal e também para suavização (retração da wavelet). Por fim, poderia fazer sentido aplicar uma estatística adicional após a transformação da wavelet ter sido aplicada (examinando a função de correlação automática, por exemplo). Um outro aspecto das wavelets que poderia ser útil para a detecção de anomalias é o efeito da localização: a descontinuidade apenas influenciará a wavelet que está próxima a ela (ao contrário de uma transformação de Fourier). Uma aplicação disso é encontrar séries temporais localmente estacionárias (usando um LSW).

Guy Nason tem um bom livro que eu recomendaria se você se aprofundar na aplicação estatística prática: " Métodos Wavelet em Estatística com R ". Isso visa especificamente a aplicação de wavelets à análise estatística, e ele fornece muitos exemplos do mundo real junto com todo o código (usando o pacote wavethresh ). O livro de Nason não trata especificamente da "detecção de anomalias", embora faça um trabalho de almirante ao fornecer uma visão geral.

Por fim, o artigo da Wikipedia fornece muitas boas referências introdutórias, portanto vale a pena analisá-lo em detalhes.

[Como uma observação lateral: se você estiver procurando uma boa técnica moderna para detecção de pontos de mudança, sugiro tentar um HMM antes de passar muito tempo com os métodos wavelet, a menos que você tenha um bom motivo para usar wavelets em seu campo específico. Isso é baseado na minha experiência pessoal. É claro que existem muitos outros modelos não lineares que podem ser considerados, portanto, isso realmente depende do seu problema específico.]

Shane
fonte
11
Não está claro para mim como os Modelos Hidden Markov são usados ​​para detecção de anomalias, mas eu gostaria muito de saber. A parte que não me parece particularmente clara é como criar uma máquina de estados subjacente correta com probabilidades significativas de transição (a menos que sejam apenas dois estados como "anomalia" e "não anomalia" com uma probabilidade de transição ingênua entre eles).
John Robertson
6

As funções básicas de wavelets discretas mais usadas e implementadas (distintas da CWT descrita na resposta de Robin) têm duas boas propriedades que as tornam úteis para a detecção de anomalias:

  1. Eles são compactamente suportados.
  2. Eles atuam como filtros de passagem de banda com a banda de passagem determinada por seu suporte.

O que isso significa em termos práticos é que sua decomposição discreta de wavelets analisa as mudanças locais no sinal através de uma variedade de escalas e faixas de frequência. Se você tem (por exemplo) ruído de alta frequência e alta magnitude sobreposto a uma função que exibe uma mudança de baixa magnitude por um período mais longo, a transformação wavelet separará eficientemente essas duas escalas e permitirá que você veja a mudança da linha de base que muitas outras técnicas vão faltar; uma mudança nessa linha de base pode sugerir um surto de doença ou alguma outra mudança de interesse. De várias maneiras, você pode tratar a decomposição em si como mais suave (e houve muito trabalho feito no encolhimento eficiente dos coeficientes de wavelets na estimativa não paramétrica, veja, por exemplo, praticamente qualquer coisa nas wavelets da Donoho). Ao contrário dos métodos puros baseados em frequência, o suporte compacto significa que eles são capazes de lidar com dados não estacionários. Ao contrário dos métodos puramente baseados em tempo, eles permitem alguma filtragem baseada em frequência.

Em termos práticos, para detectar anomalias ou alterar pontos, você aplicaria uma transformação wavelet discreta (provavelmente a variante conhecida como "Maximum Overlap DWT" ou "shift invariant DWT", dependendo de quem você lê) nos dados e procure nos conjuntos de coeficientes de frequência mais baixa para verificar se há mudanças significativas na linha de base. Isso mostrará quando uma alteração de longo prazo está ocorrendo sob qualquer ruído do dia-a-dia. Percival e Walden (veja as referências abaixo) fazem alguns testes para coeficientes estatisticamente significativos que você pode usar para ver se uma mudança como essa é significativa ou não.

Um excelente trabalho de referência para wavelets discretas é Percival e Walden, "Wavelet Methods for Time Series Analysis". Um bom trabalho introdutório é "Introdução às wavelets e transformadas de wavelets, uma cartilha" de Burrus, Gopinath e Guo. Se você tem experiência em engenharia, "Elementos de wavelets para engenheiros e cientistas" é uma boa introdução do ponto de vista do processamento de sinais.

(Editado para incluir os comentários de Robin)

Rico
fonte
O primeiro ponto que você menciona é falso em geral. Sugiro que você leia a primeira frase do capítulo books.google.fr/… no livro de Daubechie. Além disso, Se você tinha lido a minha resposta eu já mencionada a boa propriedade da DWT na segunda parte da minha resposta ...
robin Girard
Para o primeiro ponto, você está certo. Eu deveria ter dito "Funções básicas de wavelets discretas mais usadas / implementadas"; Vou editar para refletir isso. Para o segundo ponto, você deu uma boa resposta sobre como alguns CWTs (na maioria das vezes uma wavelet DOG ou a wavelet Ricker relacionada; algo como, por exemplo, a wavelet Gabor não forneceria o comportamento descrito) pode detectar anomalias do tipo singularidade. Eu estava tentando fornecer uma descrição análoga de como o DWT pode ser usado para detectar outros tipos de anomalias.
Rico
O segundo ponto mencionado também é falso: o suporte da wavelet (se for compacto) está fornecendo informações sobre a localização temporal da wavelet e não a localização da frequência.
Robin girard
As wavelets discretas - ou pelo menos a grande maioria das implementadas e comumente usadas - geralmente são projetadas para ter propriedades úteis baseadas em frequência sob a restrição de suporte compacto. A condição de momento de fuga dos Daubechies, por exemplo, é mais ou menos equivalente à planicidade na banda passante. As propriedades de localização de frequência das wavelets são geralmente o que levam os coeficientes a serem representações esparsas e permitem estimar a variação do ruído sob a suposição "sinal + ruído aditivo zero zero".
Rich