Subscribe to DSC Newsletter

Have You Heard About Unsupervised Decision Trees

Summary: Unless you’re involved in anomaly detection you may never have heard of Unsupervised Decision Trees.  It’s a very interesting approach to decision trees that on the surface doesn’t sound possible but in practice is the backbone of modern intrusion detection.

 

I was at a presentation recently that focused on stream processing but the use case presented was about anomaly detection.  When they started talking about unsupervised decision trees my antenna went up.  What do you mean unsupervised decision trees?  What would they split on?

It turns out that if you’re in the anomaly detection world unsupervised decision trees are pretty common.  Since I’m not in that world and I suspect few of us are, I thought I’d share what I found.

 

Anomaly versus Sparse Data

A few weeks back we featured techniques for dealing with imbalanced data sets.  We observed that there’s no standard for when the imbalance becomes so great that it ought to be considered an anomaly.  Like great art, you’ll know it when you see it.

The anomalies that we’re going to use as illustrations here are about intrusion detection.  Although these may occur many times during a day they are extremely rare compared to the torrent of data being produced by regular web logs and system packets.  On a more human scale, anomalies could be events of credit card fraud or the detection of cancer from among normal CT scans.

If you think your use case is on the borderline between just being sparse and being an anomaly, do what we all do, try it both ways and see what works best.

 

Supervised Versus Unsupervised

In anomaly detection we are attempting to identify items or events that don’t match the expected pattern in the data set and are by definition rare.  The traditional ‘signature based’ approach widely used in intrusion detection systems creates training data that can be used in normal supervised techniques.  When an attack is detected the associated traffic pattern is recorded and marked and classified as an intrusion by humans.  That data then combined with normal data creates the supervised training set.

In both supervised and unsupervised cases decision trees, now in the form of random forests are the weapon of choice.  Decision trees are nonparametric; they don’t make an assumption about the distribution of the data.  They’re great at combining numeric and categoricals, and handle missing data like a champ.  All types of anomaly data tend to be highly dimensional and decision trees can take it all in and offer a reasonably clear guide for pruning back to just what’s important.

To be complete, there is also category of Semi-Supervised anomaly detection in which the training data consists only of normal transactions without any anomalies.  This is also known as ‘One Class Classification’ and uses one class SVMs or autoencoders in a slightly different way not discussed here.

The fact is that supervised methods continue to be somewhat more accurate than unsupervised in intrusion detection but they are completely unable to identify new zero-day attacks which are perhaps an even more serious threat.

 

Unsupervised Decision Trees

The concept of unsupervised decision trees is only slightly misleading since it is the combination of an unsupervised clustering algorithm that creates the first guess about what’s good and what’s bad on which the decision tree then splits.

 

Step 1:  Run a clustering algorithm on your data.  Pretty much all the clustering techniques have been tried and good old k-NN still seems to work best.  It might be tempting to set K=2 but it would be unrealistic to expect a good result given the different types of intrusion that may be present.  Practical guidance is to set K at a minimum of 10 and experiment with values up to 50.  Since the data is unlabeled there is no objective function to determine an optimum clustering.

It’s not covered in the literature but this might be a good point to try SMOTE (Synthetic Minority Oversampling Technique) discussed in the earlier article on imbalanced data sets since its objective is to clarify the boundaries among clusters.

 

Step 2:  Having recorded the cluster on your data, run the decision tree in the normal manner.  Clearly if K is large this will be a multi-class problem where you will need to interpret the threshold values to spot the anomalies.

Focusing on the k-NN methods the results are quite good as you can see from this ROC curve run against breast cancer detection benchmark data.  (Note the AUC axis is cutoff at 0.5).

 

The real implementation of anomaly detection unsupervised decision trees is somewhat more complex and there are issue of different types of anomalies, procedures for data normalization, and variations in the benchmark data sets themselves.  If you want to deep dive this I suggest the article from which these graphics were derived which compares eight different techniques across a variety of data sets.

 

In Best Practice

There are Python scripts for Unsupervised Random Forests that will make your life much easier if you’d like to explore this.  Boni Bruno, Chief Solutions Architect of Analytics from Dell EMC’s Emerging Technologies Division gave the presentation I attended.  The scenario he described was monitoring for intrusion detection in a worldwide geographically distributed group of data centers and doing it from a single location.

The core of the technology architecture was Spark Streaming where an operator in the stream contained the detection algorithm built with the Python Unsupervised Random Forests script.  Alert notifications are sent out in less than 5 seconds of the intrusion detection. 

Of equal interest was that the system was designed to gather a new (and truly Big data) data set every 24 hours to retrain the model so that any new Zero-day exploits could be caught in near real time.

 

 

About the author:  Bill Vorhies is Editorial Director for Data Science Central and has practiced as a data scientist since 2001.  He can be reached at:

[email protected]

Views: 5317

Comment

You need to be a member of Data Science Central to add comments!

Join Data Science Central

Comment by William Vorhies on November 7, 2017 at 2:01pm

The nearest neighbor algorithm identifies 'famililes' of irregular events.  Each of these families is given a name or code.  The original data which might comprise dozens or even a hundred observations about each event (for example the details of the web log or systems packets is then coded with these anomaly family name codes.  From there it's pretty straightforward to run your favorite binary or multi-class classifier, most likely a random forest or a variation like XG Boost to predict the associated variables.

Comment by Sinead Brack on November 5, 2017 at 7:14am

Dr. Vorhies, 

Could you explain specifically how the second split of a decision tree is calculated, please?

Kind regards,

Sinead

Comment by Scott Edwards on October 24, 2017 at 6:13am
Thanks for an interesting article Bill. I'm curious though - I've never seen k-NN used for unsupervised learning (only supervised) - can you point me to anything that explains how it works or has code?
Comment by Dr. S. Lakshmi Sevukamoorthy on October 22, 2017 at 8:55pm

Thanx for the vision

Comment by abbas Shojaee on October 20, 2017 at 9:27am

Am I missing something? unsupervised decision trees are among hierarchical clustering methods, which has been around. You can use an elbow function or draw a dendrogram and choose a specific level to cut the tree. Clusters(branches) at the top level with few cases contain outliers or anomaly groups.

Comment by Lee McGraw on October 19, 2017 at 11:25am

Interesting article.

Follow Us

Videos

  • Add Videos
  • View All

Resources

© 2017   Data Science Central   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service