27
$\begingroup$

I've been beginning to work my way through Statistical Data Mining Tutorials by Andrew Moore (highly recommended for anyone else first venturing into this field). I started by reading this extremely interesting PDF entitled "Introductory overview of time-series-based anomaly detection algorithms" in which Moore traces through many of the techniques used in the creation of an algorithm to detect disease outbreaks. Halfway through the slides, on page 27, he lists a number of other "state of the art methods" used to detect outbreaks. The first one listed is wavelets. Wikipeida describes a wavelet as

a wave-like oscillation with an amplitude that starts out at zero, increases, and then decreases back to zero. It can typically be visualized as a "brief oscillation"

but does not describe their application to statistics and my Google searches yield highly academic papers that assume a knowledge of how wavelets relate to statistics or full books on the subject.

I would like a basic understanding of how wavelets are applied to time-series anomaly detection, much in the way Moore illustrates the other techniques in his tutorial. Can someone provide an explanation of how detection methods using wavelets work or a link to an understandable article on the matter?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
19
$\begingroup$

Wavelets are useful to detect singularities in a signal (see for example the paper here (see figure 3 for an illustration) and the references mentioned in this paper. I guess singularities can sometimes be an anomaly?

The idea here is that the Continuous wavelet transform (CWT) has maxima lines that propagates along frequencies, i.e. the longer the line is, the higher is the singularity. See Figure 3 in the paper to see what I mean! note that there is free Matlab code related to that paper, it should be here.

Additionally, I can give you some heuristics detailing why the DISCRETE (preceding example is about the continuous one) wavelet transform (DWT) is interesting for a statistician (excuse non-exhaustivity) :

  • There is a wide class of (realistic (Besov space)) signals that are transformed into a sparse sequence by the wavelet transform. (compression property)
  • A wide class of (quasi-stationary) processes that are transformed into a sequence with almost uncorrelated features (decorrelation property)
  • Wavelet coefficients contain information that is localized in time and in frequency (at different scales). (multi-scale property)
  • Wavelet coefficients of a signal concentrate on its singularities.
Improve this answer
$\endgroup$
0
19
$\begingroup$

The list in the presentation that you reference seems fairly arbitrary to me, and the technique that would be used will really depend on the specific problem. You will note however that it also includes Kalman filters, so I suspect that the intended usage is as a filtering technique. Wavelet transforms generally fall under the subject of signal processing, and will often be used as a pre-processing step with very noisy data. An example is the "Multi-scale anomaly detection" paper by Chen and Zhan (see below). The approach would be to run an analysis on the different spectrum rather than on the original noisy series.

Wavelets are often compared to a continuous-time fourier transform, although they have the benefit of being localized in both time and frequency. Wavelets can be used both for signal compression and also for smoothing (wavelet shrinkage). Ultimately, it could make sense to apply a further statistical after the wavelet transform has been applied (by looking in at the auto-correlation function for instance). One further aspect of wavelets that could be useful for anomaly detection is the effect of localization: namely, a discontinuity will only influence the wavelet that is near it (unlike a fourier transform). One application of this is to finding locally stationary time series (using an LSW).

Guy Nason has a nice book that I would recommend if you want to delve further into the practical statistical application: "Wavelet Methods in Statistics with R". This is specifically targeting the application of wavelets to statistical analysis, and he provides many real world examples along with all the code (using the wavethresh package). Nason's book does not address "anomaly detection" specifically, although it does do an admiral job of providing a general overview.

Lastly, the wikipedia article does provide many good introductory references, so it is worth going through it in detail.

[As a side note: if you are looking for a good modern technique for change point detection, I would suggest trying a HMM before spending too much time with wavelet methods, unless you have good reason to be using wavelets in your particular field. This is based on my personal experience. There are of course many other nonlinear models that could be considered, so it really depends on your specific problem.]

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Its not clear to me how Hidden Markov Models are used for anomaly detection but I would very much like to know. The part that is particularly unclear to me is how to create a correct underlying state machine with meaningful transition probabilities (unless it is just two states like "anomaly" and "not anomaly" with a naive transition probability between them). $\endgroup$
    – John Robertson
    Jun 29, 2012 at 18:11
6
$\begingroup$

Most commonly used and implemented discrete wavelet basis functions (as distinct from the CWT described in Robin's answer) have two nice properties that make them useful for anomaly detection:

  1. They're compactly supported.
  2. They act as band-pass filters with the pass-band determined by their support.

What this means in practical terms is that your discrete wavelet decomposition looks at local changes in the signal across a variety of scales and frequency bands. If you have (for instance) large-magnitude, high-frequency noise superimposed across a function that displays a low-magnitude shift over a longer period, the wavelet transform will efficiently separate these two scales and let you see the baseline shift that many other techniques will miss; a shift in this baseline can suggest a disease outbreak or some other change of interest. In a lot of ways, you can treat the decomposition itself as a smoother (and there's been quite a bit of work done on efficient shrinkage for wavelet coefficients in nonparametric estimation, see e.g. pretty much anything on wavelets by Donoho). Unlike pure frequency-based methods, the compact support means that they're capable of handling non-stationary data. Unlike purely time-based methods, they allow for some frequency-based filtering.

In practical terms, to detect anomalies or change points, you would apply a discrete wavelet transform (probably the variant known either as the "Maximum Overlap DWT" or "shift invariant DWT", depending on who you read) to the data, and look at the lower-frequency sets of coefficients to see if you have significant shifts in the baseline. This will show you when a long-term change is occurring underneath any day-to-day noise. Percival and Walden (see references below) derive a few tests for statistically significant coefficients that you could use to see if a shift like this is significant or not.

An excellent reference work for discrete wavelets is Percival and Walden, "Wavelet Methods for Time Series Analysis". A good introductory work is "Introduction to wavelets and wavelet transforms, a primer" by Burrus, Gopinath, and Guo. If you're coming from an engineering background, then "Elements of wavelets for engineers and scientists" is a good introduction from a signal-processing point of view.

(Edited to include Robin's comments)

Improve this answer
$\endgroup$
4
  • $\begingroup$ The first point you mention is false in general I suggest that you read the first sentence of the chapter books.google.fr/… in the book of Daubechie. In addition, If you had read my answer I already mentionned the nice property of the DWT in the 2nd part of my answer... $\endgroup$
    – robin girard
    Aug 8, 2010 at 18:13
  • $\begingroup$ To the first point, you're right. I should have said "Most commonly used/implemented discrete wavelet basis functions"; I'll edit to reflect that. To the second point, you gave a good answer for how the some CWTs (most often a DOG wavelet or the related Ricker wavelet; something like e.g. the Gabor wavelet would not provide the behavior your describe) can detect anomalies of the singularity kind. I was trying to give an analogous description of how DWT can be used for detecting other kinds of anomalies. $\endgroup$
    – Rich
    Aug 8, 2010 at 19:21
  • $\begingroup$ The second point you mention is also likely to be false: wavelet support (if it is compact) is giving information about the temporal localization of the wavelet not the frequency localization. $\endgroup$
    – robin girard
    Aug 9, 2010 at 7:30
  • $\begingroup$ Discrete wavelets -- or at least the vast majority of ones that are implemented and commonly used -- are typically designed to have useful frequency-based properties under the compact support constraint. The vanishing moment condition of Daubechies, for instance, is more or less equivalent to flatness in the pass-band. The frequency localization properties of wavelets are usually what lead the coefficients to be sparse representations and allow estimation of the noise variance under the "signal + additive zero-mean noise" assumption. $\endgroup$
    – Rich
    Aug 9, 2010 at 15:05
0
$\begingroup$

Really nice answers so far!

For the mathematical proof regarding robin's first sentence, (i.e. Wavelets are useful to detect singularities in a signal), originally by Yves Meyer, see Singularity Detection and Processing with Wavelets (Mallat and Hwang, 1992). Not only they are useful, they are guaranteed to concentrate around singularities and make them quantifiable via their Lipschitz measure, kind of an "if and only if" condition.

This said, I'd like to reflect on robin's hypothesis that singularities can be an anomaly, and possibly broaden it by rather saying that, since wavelet representations concentrate more on singularities, the result is generally sparser, and a sparser representation can allow to identify anomalies more reliably (even if just as a consequence of having less parameters).

Of course, not everything can be solved with wavelets, this is not the 90s anymore. Now we throw neural networks at everything!

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.