Finding “Gems” in Big Data

Detecting anomalous cases in large datasets is critical in conducting surveillance, countering credit-card fraud, protecting against network hacking, combating insurance fraud, and many more applications in government, business and healthcare. Learn how to do it online in “Anomaly Detection” course at Statistics.com.

In 1945, Count Richard Taaffe*, a Dublin gem collector, was sorting through a set of spinel gems that he had bought, and found one that refracted light differently – instead of simply bending light rays, it split them into two rays (“double refraction”).  The anomalous gem was named after him and earned a place on the “world’s rarest gems” list.  In analytics, it sometimes not the rule (i.e. the model) that is of interest, but rather the exception.

Detecting anomalous cases in large datasets is critical in conducting surveillance, countering credit-card fraud, protecting against network hacking, combating insurance fraud, and many more applications in government, business and healthcare.

The techniques of anomaly detection are not new to the era of Big Data.  Dr. Nitin Indurkhya, who teaches the Anomaly Detection course at Statistics.com, told me of an interesting application of anomaly detection to data that long pre-dates the era of Big Data.  A student in his course specialized in researching the records of civil service exams in Korea, dating back to medieval times.  These challenging and high stakes exams controlled access to jobs in the state bureaucracy.  The student found that one particular patrilineal kin group in Korea, the Andong Kim, stood apart from the other 700 – the Andong Kim were much younger at time of passing the exam than all the other groups.

Sometimes, the analyst has a set of known anomalies (labeled data), and identifying similar anomalies in the future can be handled as a supervised learning task (a classification model).  More often, though, little or no such “training” data are available.  In such cases, the goal is to identify cases that are very different from the norm.

Careful thought and analysis may be needed to define what is “normal.”  Distance metrics (e.g. Euclidean Distance) are often used to define groups (clusters) of records that are close to one another and, by exclusion, anomalies.  Applying this metric to stock returns, though, has limited utility.  Stocks that have returns that are far from the crowd may not be anomalies – they may be members of a group of stocks that experience extreme variability in return.  Using this distance metric, they are not only far from the crowd but probably far from each other, and yet they belong to a cluster that has its own (different) definition of normality.  In this case, using other attributes of stocks in the analysis can help tease out true anomalies.

Other challenges pointed out by Chandola, Banerjee and Kumar (in “Anomaly Detection: A Survey” in ACM Computing Surveys, July, 2009) include:

Some of the same statistical and machine-learning methods used for prediction and exploration are also used for anomaly detection, both relying on some form of distance measure.

One is k-nearest neighbors, in which the metric used is “distance to the kth nearest neighbor.”  The idea is to identify areas of density, where records are close to one another.  Distance to the kth nearest neighbor will, in such areas, be relatively low, and a record that is quite distant from its kth nearest neighbor is anomalous.

A related method is cluster analysis, in which distance between records is used to define clusters of records that are close to one another.