Re:Practical and robust anomaly detection in time series
by joeyo on Wednesday January 07, 2015 @04:58AM
(#8849667)
> but this test has a Gaussian assumption, not a Poisson assumption.
In practice the Gaussian assumption might not be too badly abused (at least for Twitter) since the Poisson distribution approaches the Gaussian when lambda is large.
The data they are looking at is essentially a univariate stochastic point process, that is, an arrival process. The most important special case is the Poisson process. There the times between arrivals are independent, identically distributed random variables with exponential distribution with parameter the arrival rate. The number of arrivals in an interval is random with Poisson distribution (compare with the terms of the Taylor series for exp(x)).
See early in
E. Cinlar, 'Introduction to Stochastic Processes'.
There for the Poisson process there is a 'qualitative, axiomatic' definition -- an arrival process with stationary, independent increments. A cute derivation from this just qualitative description results in the details of the Poisson process.
One point about this qualitative approach is that commonly in practice the assumptions are obvious just intuitively.
Another solid approach to a Poisson process is the renewal theorem; there is a careful treatment in W. Feller's now classic volume II.
The theorem says that under mild assumptions a sum of independent renewal processes converges to a Poisson process. Arrivals at Twitter look like a nearly perfect example.
So, basically without any anomalies the Twitter data is a Poisson process.
Observation (2).
In part, the anomaly detector is based on the extreme Studentized deviate (ESD) statistical hypothesis test as in
http://www.itl.nist.gov/div898/handbook/eda/section3/eda35h3...
but this test has a Gaussian assumption, not a Poisson assumption. So, there should be some mention of justifying using a Gaussian assumption.
Point (1).
The work in the OP, that is, an anomaly detector, is basically, nearly inescapably and necessarily a statistical hypothesis and, thus, faces the usual issues of false alarm rate (significance level of the test, conditional probability of Type I error given an anomaly), detection rate, and the classic Neyman-Pearson best possible result.
In particular, it is important and usually standard to have a means to adjust, control, and know the false alarm rate, but in the OP I saw no mention of false alarm rate, power of the test, etc.
On a server farm bridge or in a network operations center (NOC) with near real time anomaly detection, false alarm rate too high is a serious concern. With realistic detectors, false alarm rate too low means detection rate too low and is also a concern.
More.
There are some tests that are both multi-dimensional and distribution-free, with false alarm rate known exactly in advance and adjustable in small steps over a wide range. Such tests might be good for monitoring for 'zero day' problems, that is, ones never seen before, in serious server farms and networks.