Normalize vector-based integer data

Question

I'll preface my question by saying I have a very limited knowledge of statistics, and while I've put some thought into this problem, I'm a bit stuck! Onwards...

I have a collection of fixed-size vectors of the form $\overline{v} = \{ c_0,\ldots,c_n \}$, where each $c_i \in \mathbb{Z}^*$ and relates to an observation of some unique phenomenon $i$. Each $c_i$ are independent of each other.

From a 'training' set $V$ of many such vectors, I would like to compute:

• The average (expected?) count and standard deviation (error? confidence?) for each phenomenon $i$
• Given some new vector $\overline{v}$, some measure of 'distance' from what is 'expected', with respect to $V$.

There's one troubling complication: the observation magnitudes $c_i$ for each vector may be scaled differently. I do not know what these scaling factors are for each vector. However, I do know that each $c_i$ in a vector have correct relative proportions to one another.

I'm thinking that I need to:

1. Normalize the $c_i$ values in each vector $\overline{v}$ so that all vectors in $V$ are directly comparable to each other. I'm currently thinking I should either normalize each vector by standardizing to z-scores or by converting to unit vectors using the L2-norm.

2. Once normalized and comparable, take the average and standard deviation of all $c_i$ values for each $\overline{v} \in V$, giving the expected normalized average $u_i$ and standard deviation $\sigma_i$ for each phenomenon $i$. This gives rise to a vector of 'expected' values with standard deviations for each phenomenon, $\hat{v} = \{u_0 \pm \sigma_0, \ldots, u_n \pm \sigma_n \}$.

3. Use $\hat{v}$ together with the notion of vector distance (in the 'normalized' space) to determine how close/far some new vector $\overline{v}$ is from that is expected.

Am I on the right track?

Answer 1

The standard "distance" metric that one typically uses for this type of problem is the Mahalanobis distance.

Assuming that you choose to adopt the Mahalanobis distance as your preferred distance metric, then step 1 that you outlined is indeed correct: normalize all vectors in the training set $V$, plus the new test vector $\overline{v}$, using the L2-norm.

On step 2, your initial description is pretty close, but it's actually slightly more complicated than that. Your idea to calculate the mean vector $\widehat{v}$ over all of the individual normalized vectors in $V$ is correct, however what you need to calculate next is not just the $n$ (or rather, $n+1$, given that you've chosen to index from zero) individual variances, rather, what you actually need is the full $n \times n$ (or $(n+1) \times (n+1)$) covariance matrix. In a MATLAB setting, for example, you'd calculate this using the cov function. The reason why you need the full covariance matrix, and not just the variances (which correspond to the diagonals of the full covariance matrix) is that the variances by themselves don't fully describe the multidimensional shape of $V$'s probability distribution: the random variations among pairs of vector component values may in principle be "correlated"; i.e., an upward statistical fluctuation in the $i$th component of an instance vector $\overline{v}$ could be associated with either an upward fluctuation in the $(i+1)$st component, or a downward fluctuation, or the two might be completely neutral with respect to one another. These potential shape differences are correspondingly encoded by either positive, negative, or zero values for the off-diagonal components of the covariance matrix.

Anyway, once you have the covariance matrix $C$, and the normalized expectation vector $\widehat{v}$, then finally for step 3 you may calculate the Mahalanobis distance of a new test vector $\overline{v}$ using $$d(\overline{v}, \widehat{v}) = \sqrt{(\overline{v} - \widehat{v})^{T} C^{-1} (\overline{v} - \widehat{v})}$$ where $C^{-1}$ represents the matrix inverse of $C$; i.e., $C^{-1}C = I$ (i.e., calculate using inv in MATLAB).

One more point to note: if you have a large number of new vectors $\overline{v}$ whose distance you'd like to calculate, so many instances that collectively they may actually be considered to form their own sample distribution, then as an alternative option you may choose to calculate a net Bhattacharya distance between the two distributions (i.e., the entire training set vs. the entire test set) instead. Of course it really depends on the details of your specific problem context whether or not that would make any sense in this case.

EDIT:

I forgot to mention, there is actually a rather specific reason why Mahalanobis distance is usually a logical choice of distance metric. It's because it appears in the generic expression for the pdf of a multivariate (i.e., vectorized) normal distribution: $$p(\overrightarrow{x}) = \frac{1}{\sqrt{(2 \pi)^{N} \det(C)}} \exp\left[-\frac{\left(\overrightarrow{x}-\overrightarrow{\mu}\right)^{T} C^{-1} \left(\overrightarrow{x}-\overrightarrow{\mu}\right)}{2}\right]$$ In this expression, $\overrightarrow{x}$ represents a multivariate random variable which is normally distributed; it's equivalent to $\overline{v}$ in the above notation, assuming that $\overline{v}$ were normally distributed (often--though not always--the case in real life situations). The value $\overrightarrow{\mu}$ represents the Gaussian mean, equivalent to $\widehat{v}$, while $C$ again represents the covariance, and $N$ gives the number of dimensions or vector components.

The key is to recognize that any set of points $\overrightarrow{x}_{1}, \overrightarrow{x}_{2}, ..., \overrightarrow{x}_{M}$ which all have equal Mahalanobis distances will trace out a contour of equal probability encircling the mode of the pdf. Or, phrased a slightly different way, if I were to give you two random points $(\overrightarrow{x}_{a}, \overrightarrow{x}_{b})$, and then ask you to compare them and tell me which of the two is the further outlier, the Mahalanobis distance is the fundamental underlying concept which permits you to answer that question: by definition, the point with the larger Mahalanobis distance must have a smaller Gaussian probability associated with it, and it is therefore the further of the two outliers.

You should bear in mind, of course, that if your set $V$ of normalized training vectors isn't actually Gaussian, then the above discussion doesn't quite apply precisely; Mahalanobis distance might not be the correct choice of distance metric in that case. But for most practical real life situations, positing variables that are normally distributed often makes a very safe starting assumption.