Automatic threshold determination for anomaly detection

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.

• Just a note, the first graph does not look like anything normal for me. May 4 '11 at 8:06
• @cryptron, the key question is what is a sound threshold. For example if each raised alarm and non-raised alarm incurs certain costs, the threshold can be chosen such that minimises total costs. For that we need cost data. Without the exact definition of sound it is impossible to measure how to evaluate the method chosen for picking the threshold. May 4 '11 at 8:16
• @mpiktas: I have to admit, the word "sound" was unfortunate in this context because I have no way of rigorously evaluating the threshold (hence, I edited it away). Basically, the threshold is supposed to minimize false positives because they are way more costly than false negatives in network anomaly detection. May 4 '11 at 8:57
• @cryptron, do you have any data on what is a false positive? May 4 '11 at 9:05
• I'm confused by your plots. This is a univariate time series $\{x_t\}$ taking values in $0<x_t \leq 5$? Or should it be $0 <x_t \leq 0.5$? (from looking at the x axis in your first plot). A traceplot would be more helpful too. For example, do you get high scores for a sustained period of time or in short bursts (or both)? If both, is one more troubling than the other? If you can put down a reasonable model for the data you can use theoretical quantiles from the fitted distribution, which would solve the problem you've identified with the sample quantiles.
– JMS
May 4 '11 at 17:49

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)

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.

• Unfortunately, I have no labeled data sets. There is only the assumption, that long tails or outliers indicate anomalies in the data set. May 3 '11 at 19:15
• @cryptron I see. So what you need is a way to dynamically identify outliers.
– Zach
May 3 '11 at 20:15
• That would solve a part of the problem, yes. May 3 '11 at 21:39

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

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

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!

• @crypton How does DBSCAN deal with autocorrelated series. For example a time series 1,9,1,9,1,9,5 would have an inlier/unusual value. Does it deal with Level Shifts in the series or a number of possible trends ? How does it deal with seasonal autoregressive data where other than say June of each month the series is "regular" while every June the series is "large" . Do the "large June values" get detected as outliers ? Just curious ! May 17 '11 at 15:44
• @IrishStat Basically, DBSCAN clusters points in n-dimensional space. So its suitability for time series analysis is very limited. It works for my special case since I expect only a single cluster in my (1-dimensional) histogram. To answer your questions: When using appropriate parameters, the value 5 of your example would be detected as outlier. I suppose it can deal with trends, but in the time series '1, 2, 3, 4, 5, 6, 7, 2', the value 2 would not be regarded as outlier! I hope, that gives a rough idea about the capabilities and limitations of DBSCAN. May 18 '11 at 8:24
• @crypton Thanks for the info. It appears to me that when you refer to 1 cluster, you mean 1 and only 1 average. Even though there is no shift in average autocorrelation in your data renders it "time series" which suggests that DBSCAN may not be as useful as you think to separate signal from noise leading to efficient identification of anamolous data. May 18 '11 at 11:34
• @crypton It appears to me that one cluster implies 1 average as compared to a time series that had say 1,1,1,1,2,2,2,2 with some small deviations around these values. May 18 '11 at 13:23
• @crpton I think you are using a cross-sectional tool for a time series problem. Post the actual data and I will try to demonstrate anomaly detection to you with time series analysis May 18 '11 at 15:48