MAHALANOBIS DISTANCE

The Mahalanobis distance is used in recognition tasks, as it tells how far a point (a test pattern in feature space) is from a cluster of patterns (a class). A cluster of patterns defining a class is described by its average vector (centroid) and its covariance matrix,

m = ∑ xj
s = ∑ ( xj - m ) * ( xj - m )

where the sums range over the patterns (index j) in the cluster.

The Mahalanobis distance of the point P from the cluster C={m,s} is

dM(P, C) = (P - m) * s-1 * (P - m)



One of the problems using Mahalanobis distance is that it is based on the assumption of gaussian sample distributions, while in prcatice sample distridutions are asymmetric rather than normal. This can be taken into account with the asymmetric Mahalanobis distance. The basic idea is to approximate the distortions of the density level curves from the elliptical shape.

Suppose to have changed the frame of reference so that the covariance is diagonal, ie, to have transformed the sample vectors by the matrix T that diagonalizes the covariance s. Let hj be the eigenvalues of s and ej the corresponding eigenvectors. The values hj are the squared standard deviations of the distribution. Thus, in the new frame of reference the covariance is

diag( h1, ..., hn )

The Mahalanibis distance in the new frame of reference is

d(x) = ∑j (1/hj) (x-u | ej)2

Let u be the center (centroid) of the distribution. A new "center" m is chosen according to the distribution of the sample components along the eigenvalues. For each j let

mj = uj + (1/N) ∑ (x|ej)
where N is the number of samples in the class. Next the positive and negative variances along the eigenvectors directions are computed:
hj+ = (1/N+) ∑ [ (x | ej) - mj ]2
hj- = (1/N-) ∑ [ (x | ej) - mj ]2
The sums run over the samples with positive (negative) component along the eigenvector, relative to the offset center m.

The eigenvalus estimated from a finite number of samples usually contain errors, and this is likely to reduce the recognition rate. One way to take this into account is to restrict tha summations to the samples that lie within a fixed distance (proportional to the eigenvalues hj) from the center (u or m whichever is available).

The asymmetric Mahalanobis distance is now

d'(x) = ∑j (1/hja) (x-m | ej)2
where in each term the positive or negative variance is used according to the sign of (x-m | ej)

Finally the distance can be further modified by adding a bias b to the variances in the denominators:

d'(x) = ∑j (1/[ b + hja ]) (x-m | ej)2


Marco Corvi - Page hosted by geocities.com.