Mahalanobis distance for vector-classification

B"H

Hello,

Assume I have a very large set of vectors ($X_i$) over some feature space ($F_i$), each vector is labeled as either $+1$ or $-1$. For convenience lets refer to this set as "the history set".

THE QUESTION:

Given a new vector $X_{test}$ to be classified (as either "+1" or "-1"), I'd like to find the history set vector which is the closest to the $X_{test}$ vector (Mahalanobis-distance wise) and classify $X_{test}$ as that history-vector.

How can I find the closest history-vector?

• If needed: I can easily split the history-set into 2 sub-sets, each containing all equally-labeled vectors (i.e. one sub-set contains all "+1" labeled vectors, and the other - all "-1" labeled vectors). Features (Fi) covariance matrix can also be easily calculated for each of these vector-subsets. Commented Feb 5, 2012 at 14:46
• Why not just calculate the Mahalanobis distance from $X_{test}$ to each $X_i$, using the sample mean and covariance matrix for the appropriate subset (+1, -1) of the $X_i$? Commented Feb 5, 2012 at 16:40
• Gladly, only I don't know how to apply to solution you've suggested. Could you please explain? (Detailed math would be much appreciated) Commented Feb 5, 2012 at 18:03

Assuming there are some differences between the covariance matrices of the $X_i$ classified as $+1$ and those classified as $-1$, you could do the following:

1. Calculate the covariances for the two sets of $X_i$. I'll label them $\Sigma_{+}$ and $\Sigma_{-}$.

2. For all $i$ in the +-set: $d_{test,i} = \sqrt{(x_{test}-x_i)^{\text{T}}\Sigma_{+}^{-1}(x_{test}-x_i)}$. Similarly for the --set, just using $\Sigma_{-}^{-1}$ instead, obviously.

3. Take the $i$ associated with the minimum $d_{test,i}$ as your closest history-set vector.

The $d_{test,i}$ are the Mahalanobis distances between $X_{test}$ and the $X_i$.

Sample code in R for a single covariance matrix:

# Create sample history matrix with 100 entries
X <- matrix(rnorm(1000),10,100)
# Create sample test matrix
Xtest <- rnorm(10)

# Calculate the Mahalanobis distances
Sigma <- cov(t(X))
SInv <- solve(Sigma)

di <- rep(0, ncol(X))
for (i in 1:length(di)) {
di[i] <- sqrt(t(Xtest-X[,i]) %*% SInv %*% (Xtest-X[,i]))
}

which.min(di)

• Thanks much. Clarification: Assuming vectors Xi are ordered in rows, so that each column (of the matrix formed by this vector-arrangement) represents a certain feature: Is the covariance matrix you're referring to - the features' covariance matrix? In other words, assume there are N features (i.e. N columns, i.e. vectors Xi dimension is N), the covariance matrix would be of N x N size {and symmetrical as COV(Fi, Fj) = COV(Fj, Fi)} ? Commented Feb 6, 2012 at 13:29
• The code above assumed the vectors were in columns, so that each row of $X$ represented a feature. $\Sigma$ is 10 x 10, and is the covariance matrix of the features, as you thought. Commented Feb 6, 2012 at 14:40