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.

  • $\begingroup$ How correlated are your 20,000 features? $\endgroup$ – kbrose Apr 27 '18 at 14:05
  • 2
    $\begingroup$ The short answer is that you can't. Do you have any outside knowledge to constrain the possible solution? It may be worth considering my advice here. $\endgroup$ – gung - Reinstate Monica Apr 27 '18 at 14:08
  • $\begingroup$ @kbrose Some are highly correlated, but I do not know which ones. However, performance is a bit low, so I need to select the best performance between the correlated features. Is there a good way to find out which features are correlated? $\endgroup$ – Aalawlx Apr 27 '18 at 15:20

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.


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.

  • $\begingroup$ This is usually known as "leave one feature out" or "backwards feature selection". It is generally a good solution, but not for my specific case, since I have too many features available, meaning that the features would over fit to my data set and probably not generalise. Forward feature selection is a better solution for such cases, but for my data set, it stalls and cannot select better features after adding the best three features; I could add sets of features instead, but that adds computational complexity that I cannot afford without a supercomputer. $\endgroup$ – Aalawlx Apr 29 '18 at 21:32
  • $\begingroup$ You're right, there's too few samples for this to be a good idea. $\endgroup$ – Daniel Slätt Apr 30 '18 at 10:09

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.