# 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.

• Great question! Welcome to the site :) – Stumpy Joe Pete Nov 11 '13 at 16:27
• I suppose you could include random forests as an extension of CART. – gung - Reinstate Monica Nov 11 '13 at 16:35
• @gung: Seems appropriate. I could use Matlab's 'TreeBagger' for the purpose. Thanks. – Prometheus Nov 11 '13 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. – means-to-meaning Nov 11 '13 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. – Prometheus Nov 11 '13 at 21:51