The Curse of high Dimension And Distance

Question

For extracting features from video frames (2 sample/sec) I use keras framework in python and load VGG16 that input size is (150,150,3) and output size is (4,4,512). After the feature extraction step I want to cluster frame features with Hierarchical K-Means.

My problems are as follow:

1. I save each frame features in a vector which size is 8192. For a video that have 8000 frames if only reduce each frame size to (150,150) and extract features then I have a feature matrix with size (640,8192). As you can see feature matrix for even one video is very large ans besides "sparse". What is the best way to reduction its dimension?
2. What is the best metric for calculation distance between two pair of frame features? The space is so sparse and even feature values are so small, so Euclidean Distance is not a wise choise!!

CLARIFICATION

What is the frame feature:

As you already knew, videos are nothing but frames, and with the help of deep learning (VGG16 (without the last fully connected layer)) we can extract its features in the way we like. for more information kaggle.com/keras/vgg16
In this particular case, output features have the size of (4*4*512) that become 8192 number in a row vector.

Data:

My data as I mentioned above is a very sparse and large matrix (640,8192). Non-zero values are rarely up to 100.

IDEAS

For Dimension Reduction:

Two method are available for DR

1. Principal component analysis (PCA): A statistical procedure that uses an orthogonal transformation to convert a set of observations of possibly correlated variables into a set of values of linearly uncorrelated variables called principal components. (source: https://en.wikipedia.org/wiki/Principal_component_analysis)
   
   
2. Singular-Value Decomposition (SVD): A factorization of a real or complex matrix. It is the generalization of the eigen decomposition of a positive semi definite normal matrix (for example, a symmetric matrix with positive eigenvalues) to any m*n matrix via an extension of the polar decomposition. (source: https://en.wikipedia.org/wiki/Singular-value_decomposition)

Most important parameter of these two methods is "n_components" that is number of components to keep. This parameter have the value of min(n_samples, n_features). As you can guess, components that we kept with this module is depend of Sample Number and Feature Number. Suppose that we have two videos with feature matrices with size of (140, 8192) and (640, 8192). First element is number of frames and second element is number of features. The output of PCA for these two videos is (140, 140) & (640, 640). We have to have matrices with same axis to check distance and clustering. How to solve this problem?

I know that this clarification is too long to read, but it's worth it!

Answer 1

Dimension reduction is always a trade-off between resources and precision. You can use PCA (setting a high value of n, say 5000) and use the measure of exactly how much variation is addressed by each component to try and determine the number of principle components to keep. Maybe 80% is enough, but if you've only explained 30% of your data's variance after 5000 principle components, then maybe you need an alternative.

One way to plot this visually is to plot the number of components as x, and the explained variance as y. You're likely to get a curve that starts off shallow, and gets steeper at some point (or starts steep, and levels off to shallow, depending on which way your x-axis is ordered). Finding the "elbow" of this curve will deliver the point at which the cost of adding an additional component yields less and less explanatory value. It's not a perfect answer, but will give you an indication of roughly where to set your n.

sklearn.decomposition.PCA has an output that shows the explained variance after fitting - use this to help get a better feel for your data.

So the short version of this is, you can run PCA with any number n you want, but only pick the top k components where in combination, they do a good enough job (where "good enough" is defined by you) of explaining the variance in your data.

Alternately, look into building an auto-encoder using a convolutional neural net (Keras/Tensorflow), these tend to do very good job of compression, especially where more linear methods (like PCA) find the task more challenging.

[EDIT] Also, to address your final point - PCA wont ever reduce the feature space to a value less than the number of observations. That is, where you're feeding it with a small number of observations vs a large number of features, you can't force PCA to reduce the feature-size to a value lower than your observation count.

Either build up more data, or generate it using your initial dataset as a starting point, and duplicating it (sensibly, adding some random variation perhaps) so that you can reliably squirt in a large enough dataset.

This itself might pose you some problems, since now you'll have to deal with a larger memory footprint due to the input length, rather than the feature-width.

Brute-forcing it so that your PCA squeezes your feature-width down to only 50 components would limit your issue in the first place, and perhaps your resultant feature space will continue to provide you with enough explanation of variance to be useful. It's common to only use maybe 5 components for example, but with an associated loss of precision. The truth lies in your data.

Answer 2

For high dimensions, I read that Cosine Similarity works better than Euclidean Distance (https://en.wikipedia.org/wiki/Cosine_similarity). Maybe you can try this.