I have 20000 potential features but only 200 instances, how can I do feature selection for an SVM classifier?

Question

I have 20,000 potential features, but only 200 instances, how can I do feature selection for an SVM classifier, especially LIBSVM?

Is there any fast way to do it rather than brute force? Since, there are too many potential combinations of features with a brute force approach. In the end, I would expect between 50 to 100 features to be enough to maximise unbiased performance.

I know the data can be separated through the RBF kernel. Linear kernel has some degree of separation but performs much worse than RBF.

Answer 1

The best approach for selecting from such a large set of feature variables is to perform sequential forward search. I recommend building a classifier from each individual feature using a fast construction algorithm. Use for example the J48 decision tree algorithm [1], which has been implemented also in Weka. You need to program a wrapping search algorithm around the classifier evaluation, to perform this 'over night'.

After having built each of the $20,000$ one-feature classifiers and having evaluated each one by say $5$-fold cross validation, you make a ranking of the most promising $50$ features. Then you start again by building decision trees, for each of the possible $50\cdot(50-1)$ two-feature classifiers from the $50$ subset. You make a selection of the best $100$ classifiers, and add a third feature from the most promising feature set. Gradually, you get to a situation where you have say $10-20$ features that perform nicely on your training set.

You can now train and test your support vector machine with this $10-20$ subset of features.

This approach does not in any way ensure optimality. There is no guarantee that the features left out early in your feature selection procedure will not have an important contribution to the test-set performance of your SVM. Nonetheless, this is a pragmatic way-of-working which can yield a well-performing classifier for the classification task at hand. The small number of training cases, $200$, is really the limiting factor.

[1] Ross Quinlan (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, San Mateo, CA.

Answer 2

How long does it take to fit and test the data with your classifier?

I did a homemade solution where I made a for-loop loop through each feature and run test the classifier with using all the features EXCEPT for that one, and then I stored the results in a list. The features with the worst performance decrease when excepted are obviously the most valuable. It's a relatively fast method if your classifier works quickly.