In which I implement Anomaly Detection for a sample data set from Andrew Ng's Machine Learning Course.¶

Week 9 of Andrew Ng's ML course on Coursera discusses two very common applied ML algorithms: anomaly detection (think fraud detection or manufacturing quality control) and recommender systems (think Amazon or Netflix). Here I focus on the anomaly detection portion and use the homework data set to learn about the relevant python tools.

Tools Covered:¶

• EllipticEnvelope for fitting a multivariate Gaussian with a robust covariance estimate
• IsolationForest for a decision-tree approach to anomaly detection in higher dimensions
• countourf and meshgrid for plotting countours of a 3D function
• StratifiedKFolds for manually creating class-balanced cross-validation train/test splits
• GridSearchCV with make_scorer for using a different evaluation metric than your estimator's default

Quick Look at the Data¶

Anomaly Detection: Node Failure in a Network of Servers¶

In the anomaly detection part of this homework we are trying to predict when a particular server in a network is going to fail - hopefully an anomalous event! We have two data sets from this system to practice on: a toy set with only two features, and a higher dimensional data set that presents more of a challenge. In both sets each observation is a "response" from a server, which has certain characteristics like throughput in mb/sec and latency in milliseconds (the two features in the toy data set).

For both data sets we have labels for the points, meaning we know which server responses actually heralded a server failure and are considered "anomalous".

Since this cluster is pretty isotropic we shouldn't have much trouble with simple independent Gaussian modeling assumption common in density estimation for anomaly detection.

The second data set is a more difficult (read: realistic) set, it lives in a higher dimensinoal space and has fewer observations. We can't plot this data set natively, but we can do PCA to cast it to 2D. In theory the mode of the data in $R^n$ should still look like the mode of the data in $R^2$, right? (Right??).

So even after some drastic compression (3-fold reduction) we can still see that outliers are more "marginal".

Anomaly Detection (AD)¶

The heart of all AD is that you want to fit a generating distribution or decision boundary for normal points, and then use this to label new points as normal (AKA inlier) or anomalous (AKA outlier) This comes in different flavors depending on the quality of your training data (see the official sklearn docs and also this presentation):

• Unsupservised (Outlier Detection). We have an unlabeled training set that we assume contains normal and outlier points, and we want to use robust tools which have a way of fitting a density to just the mode of the data and ignoring points far from this mode.
• Semi-Supervised (Novelty Detection). We have a labeled training set containing only normal points that we fit a density for. Then we predict whether new points are anomalous or normal based on this density.
• Fully Supervised. We have a labeled training set of known normal and known outlier points. We fit a density estimate using only normal points, and then fit a decision threshold on this density using a reserved sample of normal points and the known outliers. That is, you choose the probability threshold $\epsilon$ that gives you the best F1 score (or other evaluation metric suitable for skewed classes).

Anomaly Detection in Sklearn¶

Scikit-learn has a host of AD-related tools:

• OneClassSVM: (supervised or semi-supervised) can fit a tight decision boundary around a set of normal points, but it will not do well with a mixed data set already containing outliers.
• EllipticEnvelope: (unsupervised or supervised) it fits the tightest Gaussian (smallest volume ellipsoid) that it can while discarding some fixed fraction of contamination points set by the user.
• IsolationForest: (unsupervised) this is a decision tree technique that works well in higher dimensional sets (since we've not covered decision trees I'll leave this alone).

A wonderful graphic from the sklearn user guide shows a comparison of the performance of these tools on different data sets:

Unsupervised AD with EllipticEnvelope¶

First let's pretend we don't have labels, i.e. we don't know which server responses actually heralded a server failure and are considered "anomalous". Let's see how reasonable of a picture we can paint with an unsupervised approach.

A relatively simple model for the inlier-generating distribution is the multivariate Gaussian, which is parameterized by $\mu \in R^n$ and a covariance matrix $\Sigma \in R^{nxn}$. This model can capture correlations between the data, so it can distort the Gaussian along any $x_i = x_2$ line and take an ellipsoid shape generally. The class EllipticEnvelope takes your unlabeled $X$ and fits such a multivariate Gaussian density to it.

The presence of outliers in $X$ can cause a huge distortion in the fitted Gaussian, but a more robust estimate can be had by modifying the parameter contamination which indicates the fraction of points in $X$ which the class is free to discard in fitting. EllipticEnvelope will then determine which points to discard such that it can fit the ellipsoid with smallest volume. With an unlableled data set we'll have to guess a reasonable level for outlier contamination: something between 0 and 5 % should be realistic if your dealing with actual outliers.

Per usual, this class implements a predict method which returns a binary "outlier" or "not outlier" decision. Alternatively the decision_function method returns a continuous value that reflects the fitted density at the input point(s).

A good way to visualize the fitted Gaussian distributions are with a countour plot over a meshgrid representing our feature plane.

Overly Robust Covariance Estimation¶

Using a contamination value of 3.5% looks reasonable, but not great. What happens if we just don't tell the class how much contamination there is? To my eye it gets a little overexcited in discarding points... Probably better in most cases to set a reasonable contamination value.

Supervised AD with EllipticEnvelope and GridSearchCV¶

Obviously we don't want to just guess a good contamination value - and in higher dimensional sets we'd be hard-pressed to get any kind of visual feedback on our guesses. Since we have labels for our data we can run use EllipticEnvelope in a supervised way with a grid search through the contamination parameter. This turns out to be not quite so straightforward as with some estimators...

First we need to recast our y-values into the form that EllipticEnvelope uses: 1 and -1 rather than 0 and 1. We'll also reshape it to the right sklearn shape (a true vector rather than an array of arrays).

Sadly with very skewed classes we can't do simple K-Fold cross-validation because we probably won't get a good sampling of the underrepresented class in each fold. We instead want StratifiedKFold, which pays attention to lables to ensure a representative balance in each fold. This would* be what GridSearchCV uses by default if our estimator was a classifier, but EllipticEnvelope is not. So instead we need to specify the grid search cv as an iterable which contains manual train/test splits... boo :(

Finally, the default scoring for EllipticEnvelope is mean classification accuracy, which is absolutely terrible for skewed class applications (it does very well by just ignoring the underrepresented class entirely). We'll want to instead use the recall_score metric which reflects how well the algorithm can correctly identify positive examples (outliers). This metric can be transformed into a sklearn scoring function using the make_scorer function.

Higher Dimensional Anomaly Detection¶

Now let's try this on the high-dimensional data set. This is going to be much more difficult because now we have 11 features and only 100 observations! First get $y2$ ship shape:

Don't Use EllipticEnvelope Unless You Have Lots of Data¶

To fit the full multivariate Gaussian we need at least $n^2/2$ points, where $n$ is the number of features. We really don't have enough data to do a good job with this model, so let me just show you how bad it actually is...

Remember, we're in $R^{11}$ so we'll need our PCA-compressed representations to visualize these results.

Try IsolationForests for High Dimensions¶