Automatic threshold determination for anomaly detection

Question

I am working with a time series of anomaly scores (the background is anomaly detection in computer networks). Every minute, I get an anomaly score $x_t \in [0, 5]$ which tells me how "unexpected" or abnormal the current state of the network is. The higher the score, the more abnormal the current state. Scores close to 5 are theoretically possible but occur almost never.

Now I want to come up with an algorithm or a formula which automatically determines a threshold for this anomaly time series. As soon as an anomaly score exceeds this threshold, an alarm is triggered.

The frequency distribution below is an example for an anomaly time series over 1 day. However, it is not safe to assume that every anomaly time series is going to look like that. In this special example, an anomaly threshold such as the .99-quantile would make sense since the few scores on the very right can be regarded as anomalies.

And the same frequency distribution as time series (it only ranges from 0 to 1 since there are no higher anomaly scores in the time series):

Unfortunately, the frequency distribution might have shapes, where the .99-quantile is not useful. An example is below. The right tail is very low, so if the .99-quantile is used as threshold, this might result in many false positives. This frequency distribution does not seem to contain anomalies so the threshold should lie outside the distribution at around 0.25.

Summing up, the difference between these two examples is that the first one seems to exhibit anomalies whereas the second one does not.

From my naive point of view, the algorithm should consider these two cases:

• If the frequency distribution has a large right tail (i.e. a couple abnormal scores), then the .99-quantile can be a good threshold.
• If the frequency distribution has a very short right tail (i.e. no abnormal scores), then the threshold should lie outside the distribution.

/edit: There is also no ground truth, i.e. labeled data sets available. So the algorithm is "blind" against the nature of the anomaly scores.

Now I am not sure how these observations can be expressed in terms of an algorithm or a formula. Does anyone have a suggestion how this problem could be solved? I hope that my explanations are sufficient since my statistical background is very limited.

Thanks for your help!

Answer 1

You might find this paper of interest. See also more detailed presentation of similar models in West & Harrison. There are other examples of this sort of monitoring as well, many which are more recent, but this isn't exactly my wheelhouse :). Undoubtedly there are suitable implementations of these models, but I don't know what they might be offhand...

The basic idea is that you have a switching model where some observations/sequence of observations are attributed to abnormal network states while the rest are considered normal. A mixture like this could account for the long right tail in your first plot. A dynamic model could also alert you to abnormal jumps like at 8:00 and 4:00 in real-time by assigning high probability to new observations belonging to a problem state. It could also be easily extended to include things like predictors, periodic components (perhaps your score rises/falls a bit with activity) and that sort of thing.

Edit: I should also add, this kind of model is "unsupervised" in the sense that anomalies are caught either by showing a large mean shift or increase in variance. As you gather data you can improve the model with more informative prior distributions. But perhaps once you have enough data (and hard-won training examples by dealing with network problems!) you could devise some simple monitoring rules (thresholds, etc)

Answer 2

Do you have any 'labeled' examples of what constitutes an anomaly? i.e. values associated with a network failure, or something like that?

One idea you might consider applying is a ROC curve, which is useful for picking threshholds that meet a specific criteria, like maximizing true positives or minimizing false negatives.

Of course, to use a ROC curve, you need to label your data in some way.

Answer 3

The graph of the "original series" does not have to exhibit any pre-defined structure. What is critical is that the graph of the "residuals from a suitable model series" need to exhibit either a gaussian structure . This "gaussian structure" can usually obtained by incorporating one or more of the following "transformations" 1. an arima MODEL 2. Adjustments for Local Level Shifts or Local Time Trends or Seasonal Pulses or Ordinary Pulses 3. a weighted analysis exploiting proven variance heterogeneity 4. a possible power transformation ( logs etc ) to deal with a specific variance heterogenity 5. the detection of points in time where the model/parameters may have changed.

Intervention Detection will yield a statement about the statistical significance of the most recent event suggesting either normalcy or an anomaly

Answer 4

In the OP's reponse to my prior answer he has posted his data to the web. 60 readings per hour for 24 hours for 6 days . Since this is time series cross-sectional tools like DBSCAN have limited relevance as the data has temporal dependence. With data like this one normally looks for intra-hour and intra-day structure. In addition to these kinds of structure one can pursue the detection of anomalies which can be either one time only (pulse) or systematic in nature (level shift) using methods that are well documented (see the literature of Tsay,Tiao,Chen et.al.) These procedures yielded the following "anomalies'.Note that a level shift is essentially suggestive of separate "clusters".

                                HOUR/MINUTE     TIME

Answer 5

After a friend of mine pointed me into the direction of clustering algorithms, I stumbled across DBSCAN which builds clusters in n-dimensional space according to two predefined parameters. The basic idea is density-based clustering, i.e. dense regions form clusters. Outliers are returned separately by the algorithm. So, when applied to my 1-dimensional histogram, DBSCAN is able to tell me, whether my anomaly scores feature any outliers. Note: In DBSCAN, an outlier is just a point which does not belong to any cluster. During normal operations, I expect the algorithm to yield only a single cluster (and no outliers).

After some experimenting, I found out that the parameters $\epsilon \approx 0.1$ works well. This means that points have to exhibit a distance of at least 0.1 to the "normal" cluster in order to be seen as outlier.

After being able to identify outliers, finding the threshold boils down to simple rules such as:

• If the set exhibits outliers, set the threshold between the "normal" and "outlier" cluster so that the margin to both is maximized.
• If the set does not exhibit any outliers, set the threshold one standard deviation away from the outmost right point.

Anyway, thanks for all the helpful replies!