# Comparing multiclass classification algorithms for a particular application

I am assessing a bunch of classification algorithms for a specific application with multiple classes. The classification algorithms that I am considering are:

1. Multinomial Logistic Regression (Matlab's 'mnrfit')
2. Multiclass SVM (K. Crammer and Y. Singer. On the Algorithmic Implementation of Multi-class SVMs, JMLR, 2001.). I will use the code provided by the authors since Matlab's 'svmtrain' only does binary classification.
3. Neural Networks (Matlab's 'nprtool')
4. Decision Trees (C4.5 and CART from Matlab's 'classregtree')
5. k-Nearest Neighbors (Matlab's 'ClassificationKNN')
6. Naive Bayes Classifier (Matlab's 'naiveBayes')
7. Discriminant Analysis (Matlab's 'ClassificationDiscriminant')
8. Random Forests (Matlab's 'TreeBagger')

I have the following questions:

1. Have I omitted any "obvious" multiclass classification algorithm that's a must-try? Or, are there any binary classifiers that can easily be used for multiclass with one-vs-all method.
2. Which of these are linear classifiers and which are non-linear classifiers? I know 3, 4 and 5 are non-linear by nature and 2 can be non-linear with the kernel trick.
3. Which of these are discrete classifiers and which are probabilistic? For example, logistic regression gives a probability for each class, while decision trees give exactly one class. On a related note, if I want to use ROC curves for comparison, how do I compare a discrete classifier with a probabilistic one, as the former gives only a point on the ROC plot?
4. Which of these are deterministic classifiers and which are stochastic? In other words, which classifiers will yield exactly the same results for multiple runs? This is important for me: For example in logistic regression I can be done with just one run, whereas for neural networks, I will have to train the net multiple times to avoid biased results.

Finally, are there any good papers which show how to compare various classification algorithms. I found this one which is quite good.

• I suppose you could include random forests as an extension of CART. Nov 11, 2013 at 16:35
• @gung: Seems appropriate. I could use Matlab's 'TreeBagger' for the purpose. Thanks. Nov 11, 2013 at 19:32
• 2 is not "non-linear with the kernel trick". It is non-linear if you use a non-linear basis function. The "kernel trick" you are mentioning allows solving the problem. Also, be careful with question 4. In general, the solution will often depend on the particular implementation - there are implementations of logistic regression that use stochastic gradient descent rather than Newton-Raphson to minimise the objective function, and as such don't converge in one step to a global minimum. Nov 11, 2013 at 21:24
• @means-to-meaning: Thanks for clearing that. In question 4, I meant stochasticity in the learning formulation, and not in the optimizer. Nov 11, 2013 at 21:51
• could you please send your Matlab code in which you compare the different multiclass classification algorithms? I'm working on the same problem and I have to find the more efficient and accurate one. Many thanks
– user58671
Oct 15, 2014 at 16:54