4
$\begingroup$

I have a cluster of p-dimensional points and given a new p-dimensional point $x$ I want to determine whether or not it is likely to belong to this cluster.

The cluster is made up of $n$ p-dimensional points, I am making the assumption that these points are drawn from a multivariate Gaussian distribution with sample mean ${\hat{\mu_X}}$ and sample covariance matrix $\hat{\sigma_X}$.

Given a new point $x$ I am trying to decide if it is likely to belong to this cluster using the following threshold on the Mahalanobis distance: $$\frac{n}{(n-1)^2}\left(X_i-\hat{\mu}_X\right)'\hat{\sigma}_X^{-1}\left(X_i-\hat{\mu}_X\right)>B_{0.95}\left(\frac{p}{2},\frac{n-p-1}{2}\right)$$

However, some clusters have very few sample points $n$ in which case calculating the inverse covariance matrix $\hat{\sigma_X}^{-1}$ becomes impossible.

Are there any other equivalent or more appropriate measure I can use in this case?

$\endgroup$
  • $\begingroup$ Hi Aly, I added the term Mahalanobis distance to your question as this is the what your distance is actually called. Did you search for strategies to determine Mahalanobis distance for small sample sizes? $\endgroup$ – cbeleites Feb 13 '13 at 15:27
  • $\begingroup$ there is something wrong with the lhs of your inequality: both parameters of of a beta distribution have to be positive! $\endgroup$ – user603 Feb 13 '13 at 22:57
  • 1
    $\begingroup$ @Aly i've also added what i believe is a necessary factor (n/(n-1)**2)... $\endgroup$ – user603 Feb 14 '13 at 17:59
6
$\begingroup$

You can compute the pseudo-Mahalanobis distance by using the pseudo-inverse:

$$W_i'\hat{\sigma}_W^{-1}W_i$$

where

$$W^*=\left(X_i-\hat{\mu}_X\right)$$

and

$$W=W^*V_{W^*}$$

where

$V_{W^*}$ is the $V$ matrix of the SVD decomposition of $W^*$

Then simply compute the Mahalanobis distances on the matrix $W$ (instead of $X$).

note that you need to replace $p$ in the left hand side of your inequality by $p^*$ (the rank of $V_{W^*}$)

$\endgroup$
  • $\begingroup$ Can you provide a reference to this distance measure? $\endgroup$ – Aly Feb 28 '13 at 12:30
  • $\begingroup$ @Aly here or also here $\endgroup$ – user603 Feb 28 '13 at 13:14
  • $\begingroup$ thanks, so if I make the small singular values in the V matrix set to zero, this should reduce the instability in the calculation of the pseudoinverse? $\endgroup$ – Aly Feb 28 '13 at 13:56
  • $\begingroup$ where is that coming from? The method I suggest above involves 3 equations....none of which mentions setting anything to 0. Your SVD routine will itself remove the components with no variance. $\endgroup$ – user603 Feb 28 '13 at 14:14
  • $\begingroup$ so is what you have mentioned is equivalent to me using pinv in matlab? $\endgroup$ – Aly Feb 28 '13 at 14:42
1
$\begingroup$

The covariance matrix cannot be inverted if it is not of full rank (in practice, you also want a decently low condition number.

There are two ways to improve the situation:

  • add more cases (samples)
  • reduce the number of variates (features)

That is:

  • cut out features of which your expert knowledge says that they are not contributing to the clustering and/or
  • compress your data into fewer features.
    You may be able to do the calculations if you move for example into the space of the first few principal components.
$\endgroup$
1
$\begingroup$

Here is, not an alternative metric, but an alternative method for computing the Mahalanobis distance that does not require inverting the covariance matrix $\hat{\sigma}_X$ :

  • Let $y = x - {\hat{\mu_X}}$
  • Find lower triangular matrix $L$ so that $ \hat{\sigma}_X = L L^{T}$
  • Solve $Lz = y$ for $z$
  • Mahalanobis distance $ = \sqrt{z^T z}$

The second step is a Cholesky decomposition, easily done in MATLAB as L=chol(Sigma,'lower'), or Python as L=numpy.linalg.cholesky(Sigma)

(See this question for more)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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