Mahalanobis distance between two clusters

Question

I want to calculate the Mahalanobis distance between cluster $a$ and cluster $b$, each consisting from a set of multidimensional points. Assuming no correlation, calculating the distance between a random point $p$ and cluster $b$ can be achieved using the normalized Euclidean distance formula:

$$ d(p,b)=\sqrt{ \sum_{i=1}^d \frac{(p_i-b_i)^2}{\sigma_i^2}}$$

where $d$ is the number of dimensions and $\sigma_i^2$ is the squared standard deviation for each dimension in cluster $b$.

Now, I want to estimate the Mahalanobis distance between clusters $a$ and $b$. Should I assume that cluster $a$ is a single point (i.e. $a$'s centroid)? Or should I normalize using the standard deviation of both clusters? In the latter case that would translate in the following formula:

$$ d(a,b)=\sqrt{ \sum_{i=1}^d \frac{(a_i-b_i)^2}{(\sigma_i^a)^2 \cdot (\sigma_i^b)^2}}$$

where $\sigma_i^b$ is the standard deviation for dimension $i$ in cluster $b$ and $\sigma_i^a$ is the standard deviation for dimension $i$ in cluster $a$.

Thank you in advance.

Answer 1

---------Please check the edits also for this answer---------------------

According to me, its very application specific, and depends on what you want to do. I will prefer second approach in a generic application because if 2 clusters between whom we are calculating distance are having high standard deviation, should have small distance. Another approach I can think of is a combination of the 2. Calculate the Mahalanobis distance between 2 centroids and decrease it by the sum of standard deviation of both the clusters. I thought about this idea because, when we calculate the distance between 2 circles, we calculate the distance between nearest pair of points from different circles. Now think of circumference of the circle centered by centroid of circle. and the rest is obvious :)

EDIT:

As pointed out by @MarcusD in the comment, I will try to explain a bit:

1. I remarked "very application specific" because in some cases where our answer should remain same irrespective of the standard deviation of the data, then first approach will work better.

2. For reference check. Kevin murphy- ML A probabilistic approach Pg. 104, 2 Class LDA. The second approach is exactly this one. If you are not having this book, google Linear discriminant analysis.

   3. The approach I gave is not theoretically different from LDA, but it is somewhat easier to implement in cases where the number of clusters is less.

Answer 2

Mahalanobis distance depends on the covariance matrix, which is usually local to each cluster.

If you want a distance of two clusters, the following two approaches stand out:

1. the weighted average distance of each object to the other cluster, using the other clusters Mahalanobis distance. You could approximate this by using the distance of the centroid only. Maybe use the maximum of the two clusters to resolve asymmetry. This will likely not be a metric.

2. divergence measures, that measure the overlap of the two Gaussians, and not of the individual data points. I believe some of the divergence measures should be metric.

Answer 3

Why not compute the inter-cluster distance as the average Mahalanobis distance from each point in a cluster A to each point in cluster B?