11
$\begingroup$

I am new to machine learning and try to use scikit-learn(sklearn) to deal with a classification problem. Both DecisionTree and SVM can train a classifier for this problem.

I use sklearn.ensemble.RandomForestClassifier and sklearn.svm.SVC to fit the same training data(about 500,000 entries with 50 features per entry). The RandomForestClassifier comes out with a classifier in about one minute. The SVC uses more than 24 hours and still keeps running.

Why does the SVC perform so inefficiently? Is the data set too big for SVC? Is SVC improper for such problem?

Improve this question
$\endgroup$
14
$\begingroup$

Possibilities include the use of an inappropriate kernel (e.g. a linear kernel for a non-linear problem), poor choice of kernel and regularisation hyper-parameters. Good model selection (choice of kernel and hyper-parameter tuning is the key to getting good performance from SVMs, they can only be expected to give good results when used correctly).

SVMs often do take a long time to train, this is especially true when the choice of kernel and particularly regularisation parameter means that almost all the data end up as support vectors (the sparsity of SVMs is a handy by-product, nothing more).

Lastly, the no free lunch theorems say that there is no a-priori superiority for any classifier system over the others, so the best classifier for a particular task is itself task-dependent. However there is more compelling theory for the SVM that suggests it is likely to be better choice than many other approaches for many problems.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ 1. How do I know whether a problem is linear or not? According to the training data? 2. Could you recommend some materials about "how to make a good choice of kernel and tune the hyper-parameter"? $\endgroup$ – Java Xu Apr 27 '13 at 17:01
  • $\begingroup$ It isn't generally possible to know for certain that a problem is linear, but non-linear classifiers consistently out-performing non-linear ones is a clear indication that it is a non-linear task. $\endgroup$ – Dikran Marsupial Apr 29 '13 at 10:49
  • $\begingroup$ For tuning the kernel and regularisation parameters, cross-validation is a reasonable approach, using either a grid search or some numerical optimisation method (I use Nelder Mead simplex). For SVMs, the "span bound" provides a useful approximation to the leave-on-out cross-validation error. Note you need to use something like nested cross-validation is you also want an unbiased performance estimate (see the answers to other questions I gave given). $\endgroup$ – Dikran Marsupial Apr 29 '13 at 10:52
  • 1
    $\begingroup$ 500k data points is a big enough problem that kernel SVMs are likely to take a while to train. It's worth trying LinearSVM, which only supports a linear classifier but runs much faster, or an SGD classifier, which may be faster still. If that doesn't work well, you could try using kernel approximation, which lets you use linear classifier to approximate a nonlinear one. That said, random forests are a good algorithm too and may be best for your data. $\endgroup$ – Danica May 5 '13 at 0:52
18
$\begingroup$

Decision Trees and Random Forests are actually extremely good classifiers. While SVM's (Support Vector Machines) are seen as more complex it does not actually mean they will perform better.

The paper "An Empirical Comparison of Supervised Learning Algorithms" by Rich Caruana compared 10 different binary classifiers, SVM, Neural-Networks, KNN, Logistic Regression, Naive Bayes, Random Forests, Decision Trees, Bagged Decision Trees, Boosted Decision trees and Bootstrapped Decision Trees on eleven different data sets and compared the results on 8 different performance metrics.

They found that Boosted decision trees came in first with Random Forests second and then Bagged Decision Trees and then SVM

The results will also depend on how many classes you are actually classifying for.

Improve this answer
$\endgroup$
5
$\begingroup$

"whether a problem is linear or not" In a binary classification problem, if the dataset can be separated by a hyper-plane, it's a linear problem.

If the dataset is not linear separable, while you try a linear classifier to find such a hyper-plane that is not existed at all, the algorithm may seem to run forever.

One suggestion: You can sample a small portion of your data, and try these algorithms to see if it works in a small dataset. Then increase the dataset to check when does these problem occur.

Improve this answer
$\endgroup$
0
$\begingroup$

That is because of the nature of their decision boundaries. The decision boundary of SVM (with or without kernel) is always linear (in the kernel space or not) while the decision boundary of the decision tree is piece-wise linear ( non-linear).

Improve this answer
$\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.