Hi Rob,
for uncorrelated data, I’d look at decision trees. The thresholding is hard to beat :-)
Also classifiers based on affine projection (Fisher, Logistic, Perceptron). For more complicated data, AdaBoost (with decision tree or affine) may be very fast. If you have enough samples to train it.
For complicated problems, I’m usually starting with non-parametric method (k-NN or Parzen) as the performance basis. Then, I’m using different tricks to make it faster. First is to move from non-paramteric to model-based (mixtures) - check out sdmixture estimating automatically number of components (http://prsysdesign.net/index.php/html/blog_comments/automatic_estimation_of_number_of_components_in_gaussian_mixtures/ )
Another option is to go from full k-NN to approximated one (see http://prsysdesign.net/index.php/html/blog_comments/fast_approximated_k_nn_classifier/ )
Third route, I found useful, is to approximate the desired (e.g. non-parametric) classifier by neural network. It’s usually much faster (affine projections with few exps). Added advantage is that the network outputs now have similar meaning as the original classifier outputs (and so can be used for ROC analysis). See example at: http://perclass.com/doc/kb/15.html
If you have a large number of samples to classify, and use PC hardware with multiple cores, you could benefit from parallelization (multi-threaded libPRSD does that transparently).
http://perclass.com/doc/guide/deployment.html
http://prsysdesign.net/index.php/html/software_benchmark/
Hope it helps,
Pavel
