Can CUSUM be used to detect anomalies in clustered data?

Question

I am looking at approaches to detect anomalies in network traffic in terms of packets being sent with a very short inter-arrival time (IAT). Said differently, the longer (possibly) uniform IATs would be treated as normal observations while clusters of very short IATs should be treated as an anomaly.

I was looking into CUSUM via the R package qcc, the majority of the examples look at slight deviances from the normal as a means to detect anomalies with an upper and lower bound. When I ran a contrived dataset through the qcc function, the short time values are reported as run violations and some of my longer IATs are actually flagged as beyond limits.

I'm wondering if CUSUM is really the right choice here?

Furthermore, would it make more sense to model the distribution of the steady-state IATs and then compare to the distribution of the clustered distribution to infer abnormal behaviour?

As I can't 100% guarantee my data is 100% Gaussian; so GMM may not be appropriate.

Any suggestions much appreciated, I am happy to try multiple approaches until I find one that works.

Jonathan

Answer 1

Im not 100% sure I understand your post, but if you are looking for change points (e.g. medium term time periods where 'anomalous' values happen frequently, such as the orange points in your plot) then CUSUM is fine. It should detect the change (to the orange points) although it will take a while.

The textbook version of CUSUM only detects increases in the process mean, which is why it will be slow to flag the orange points as being a change point, since this is mostly a variance change. So you want to run a version of CUSUM for detecting variance changes as well as mean changes. This can be as simple as just squaring the data, and then running a standard CUSUM on the squared data. Make sure you configure the CUSUM to detect both increases and decreases (so you will end up with 4 CUSUM charts, one for an increase/decrease in process mean and one for an increase/decrease in process variance).

Since standard CUSUM assumes normality (or at least a known parametric form), it is sensitive to outliers as you say (i.e. the red points will be flagged as anomalous). To combat this, you want to use a nonparametric version of the CUSUM instead. Often this is done by transforming the data into ranks (so the smallest point gets replaced with the number '1', the next smallest with the number '2' etc), which is the usual approach in nonparametric tests such as Mann-Whitney and Kolmogorov Smirnov. You could also try using a parametric CUSUM with heavier tails (eg Student t) but this is a bit hacky.

I dont know whether there is an R version of nonparametric CUSUM, but there is an R version of a similar nonparametric change point algorithm in the 'cpm' package: https://cran.r-project.org/web/packages/cpm/cpm.pdf and https://www.jstatsoft.org/article/view/v066i03/v66i03.pdf. You probably want the Lepage test, which is nonparametric for both mean and variance shifts.