Mahalanobis Distance – Understanding the math with examples (python)

Mahalanobis distance is an effective multivariate distance metric that measures the distance between a point and a distribution. It is an extremely useful metric having, excellent applications in multivariate anomaly detection, classification on highly imbalanced datasets and one-class classification.This post explains the intuition and the math with practical examples on three machine learning use cases.

Content

1. Introduction
2. What’s wrong with using Euclidean Distance for Multivariate data?
3. What is Mahalanobis Distance?
4. The math and intuition behind Mahalanobis Distance
5. How to compute Mahalanobis Distance in Python
6. Usecase 1: Multivariate outlier detection using Mahalanobis distance
7. Usecase 2: Mahalanobis Distance for Classification Problems
8. Usecase 3: One-Class Classification
9. Conclusion

1. Introduction

Mahalanobis distance is an effective multivariate distance metric that measures the distance between a point (vector) and a distribution. It has excellent applications in multivariate anomaly detection, classification on highly imbalanced datasets and one-class classification and more untapped use cases.Considering its extremely useful applications, this metric is seldom discussed or used in stats or ML workflows. This post explains the why and the when to use Mahalanobis distance and then explains the intuition and the math with useful applications.

2. What’s wrong with using Euclidean Distance for Multivariate data?

Let’s start with the basics.Euclidean distance is the commonly used straight line distance between two points. If the two points are in a two-dimensional plane (meaning, you have two numeric columns (p) and (q)) in your dataset), then the Euclidean distance between the two points (p1, q1) and (p2, q2) is: This formula may be extended to as many dimensions you want: Well, Euclidean distance will work fine as long as the dimensions are equally weighted and are independent of each other. What do I mean by that? Let’s consider the following tables: The two tables above show the ‘area’ and ‘price’ of the same objects. Only the units of the variables change. Since both tables represent the same entities, the distance between any two rows, point A and point B should be the same. But Euclidean distance gives a different value even though the distances are technically the same in physical space.This can technically be overcome by scaling the variables, by computing the z-score (ex: (x – mean) / std) or make it vary within a particular range like between 0 and 1.But there is another major drawback.That is, if the dimensions (columns in your dataset) are correlated to one another, which is typically the case in real-world datasets, the Euclidean distance between a point and the center of the points (distribution) can give little or misleading information about how close a point really is to the cluster. The above image (on the right) is a simple scatterplot of two variables that are positively correlated with each other.That is, as the value of one variable (x-axis) increases, so does the value of the other variable (y-axis). The two points above are equally distant (Euclidean) from the center. But only one of them (blue) is actually more close to the cluster, even though, technically the Euclidean distance between the two points are equal. This is because, Euclidean distance is a distance between two points only. It does not consider how the rest of the points in the dataset vary.So, it cannot be used to really judge how close a point actually is to a distribution of points. What we need here is a more robust distance metric that is an accurate representation of how distant a point is from a distribution.

3. What is Mahalanobis Distance?

Mahalonobis distance is the distance between a point and a distribution. And not between two distinct points. It is effectively a multivariate equivalent of the Euclidean distance.It was introduced by Prof. P. C. Mahalanobis in 1936 and has been used in various statistical applications ever since. However, it’s not so well known or used in the machine learning practice. Well, let’s get into it. So computationally, how is Mahalanobis distance different from Euclidean distance?

1. It transforms the columns into uncorrelated variables
2. Scale the columns to make their variance equal to 1
3. Finally, it calculates the Euclidean distance.

The above three steps are meant to address the problems with Euclidean distance we just talked about. But how? Let’s look at the formula and try to understand its components.

4. The math and intuition behind Mahalanobis Distance

The formula to compute Mahalanobis distance is as follows:

where, 
 - D^2        is the square of the Mahalanobis distance. 
 - x          is the vector of the observation (row in a dataset), 
 - m          is the vector of mean values of independent variables (mean of each column), 
 - C^(-1)     is the inverse covariance matrix of independent variables.

So, how to understand the above formula? Let’s take the (x – m)^T . C^(-1) term. (x – m) is essentially the distance of the vector from the mean. We then divide this by the covariance matrix (or multiply by the inverse of the covariance matrix). If you think about it, this is essentially a multivariate equivalent of the regular standardization (z = (x – mu)/sigma).That is, z = (x vector) – (mean vector) / (covariance matrix). So, What is the effect of dividing by the covariance? If the variables in your dataset are strongly correlated, then, the covariance will be high. Dividing by a large covariance will effectively reduce the distance.Likewise, if the X’s are not correlated, then the covariance is not high and the distance is not reduced much. So effectively, it addresses both the problems of scale as well as the correlation of the variables that we talked about in the introduction.

5. How to compute Mahalanobis Distance in Python

Let’s write the function to calculate Mahalanobis Distance.

6. Usecase 1: Multivariate outlier detection using Mahalanobis distance

Assuming that the test statistic follows chi-square distributed with ‘n’ degree of freedom, the critical value at a 0.01 significance level and 2 degrees of freedom is computed as:That mean an observation can be considered as extreme if its Mahalanobis distance exceeds 9.21. If you prefer P values instead to determine if an observation is extreme or not, the P values can be computed as follows: If you compare the above observations against rest of the dataset, they are clearly extreme.

7. Usecase 2: Mahalanobis Distance for Classification Problems

Mahalanobis distance can be used for classification problems. A naive implementation of a Mahalanobis classifier is coded below. The intuition is that, an observation is assigned the class that it is closest to based on the Mahalanobis distance. Let’s see an example implementation on the BreastCancer dataset, where the objective is to determine if a tumour is benign or malignant.

Let’s split the dataset in 70:30 ratio as Train and Test. And the training dataset is split into homogeneous groups of ‘pos'(1) and ‘neg'(0) classes. To predict the class of the test dataset, we measure the Mahalanobis distances between a given observation (row) and both the positive (xtrain_pos) and negative datasets(xtrain_neg). Then that observation is assigned the class based on the group it is closest to.Let’s build the MahalanobiBinaryClassifier. To do that, you need to define the predict_proba() and the predict() methods. This classifier does not require a separate fit() (training) method.Output:Let’s see how the classifier performed on the test dataset.Output:Mahalanobis distance alone is able to contribute to this much accuracy (92%).

8. Usecase 3: One-Class Classification

One Class classification is a type of algorithm where the training dataset contains observations belonging to only one class.With only that information known, the objective is to figure out if a given observation in a new (or test) dataset belongs to that class. You might wonder when would such a situation occur.Well, it’s a quite common problem in Data Science.For example consider the following situation: You have a large dataset containing millions of records that are NOT yet categorized as 1’s and 0’s. But you also have with you a small sample dataset containing only positive (1’s) records. By learning the information in this sample dataset, you want to classify all the records in the large dataset as 1’s and 0’s. Based on the information from the sample dataset, it is possible to tell if any given sample is a 1 or 0 by viewing only the 1’s (and having no knowledge of the 0’s at all). This can be done using Mahalanobis Distance.Let’s try this on the BreastCancer dataset, only this time we will consider only the malignant observations (class column=1) in the training data.Splitting 50% of the dataset into training and test. Only the 1’s are retained in the training data.Let’s build the MahalanobisOneClassClassifier and get the mahalanobis distance of each datapoint in x from the training set (xtrain_pos).We have the Mahalanobis distance and the actual class of each observation. I would expect those observations with low Mahalanobis distance to be 1’s. So, I sort the mdist_actuals by Mahalanobis distance and quantile cut the rows into 10 equal sized groups. The observations in the top quantiles should have more 1’s compared to the ones in the bottom. Let’s see.If you notice above, nearly 90% of the 1’s (malignant cases) fall within the first 40%ile of the Mahalanobis distance.Incidentally, all of these are lower than the critical value pf 14.05. So, let’s the critical value as the cutoff and mark those observations with Mahalanobis distance less than the cutoff as positive.So, without the knowledge of the benign class, we are able to accurately predict the class of 87% of the observations.

Conclusion

In this post, we covered nearly everything about Mahalanobis distance: the intuition behind the formula, the actual calculation in python and how it can be used for multivariate anomaly detection, binary classification, and one-class classification. It is known to perform really well when you have a highly imbalanced dataset. Hope it was useful? Please leave your comments below and I will see you in the next one.