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".


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?

  • $\begingroup$ 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. $\endgroup$
    – Bliss
    Commented Feb 5, 2012 at 14:46
  • 1
    $\begingroup$ 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$? $\endgroup$
    – jbowman
    Commented Feb 5, 2012 at 16:40
  • $\begingroup$ Gladly, only I don't know how to apply to solution you've suggested. Could you please explain? (Detailed math would be much appreciated) $\endgroup$
    – Bliss
    Commented Feb 5, 2012 at 18:03

1 Answer 1


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]))

  • $\begingroup$ 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)} ? $\endgroup$
    – Bliss
    Commented Feb 6, 2012 at 13:29
  • $\begingroup$ 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. $\endgroup$
    – jbowman
    Commented Feb 6, 2012 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.