Alternatives to classification trees, with better predictive (e.g: CV) performance? I am looking for an alternative to Classification Trees which might yield better predictive power.
The data I am dealing with has factors for both the explanatory and the explained variables.
I remember coming across random forests and neural networks in this context, although never tried them before, are there another good candidate for such a modeling task (in R, obviously)?
 A: For multi-class classification, support vector machines are also a good choice. I typically use the the R kernlab package for this. 
See the following JSS paper for a good discussion: http://www.jstatsoft.org/v15/i09/
A: I think it would be worth giving a try to Random Forests (randomForest); some references were provided in response to related questions: Feature selection for “final” model when performing cross-validation in machine learning; Can CART models be made robust?. Boosting/bagging render them more stable than a single CART which is known to be very sensitive to small perturbations. Some authors argued that it performed as well as penalized SVM or Gradient Boosting Machines (see, e.g. Cutler et al., 2009). I think they certainly outperform NNs.
Boulesteix and Strobl provides a nice overview of several classifiers in Optimal classifier selection and negative bias in error rate estimation: an empirical study on high-dimensional prediction (BMC MRM 2009 9: 85). I've heard of another good study at the IV EAM meeting, which should be under review in Statistics in Medicine,

João Maroco, Dina Silva, Manuela Guerreiro, Alexandre de Mendonça. Do
  Random Forests Outperform Neural
  Networks, Support Vector Machines and
  Discriminant Analysis classifiers? A
  case study in the evolution to
  dementia in elderly patients with
  cognitive complaints

I also like the caret package: it is well documented and allows to compare predictive accuracy of different classifiers on the same data set. It takes care of managing training /test samples, computing accuracy, etc in few user-friendly functions.
The glmnet package, from Friedman and coll., implements penalized GLM (see the review in the Journal of Statistical Software), so you remain in a well-known modeling framework.
Otherwise, you can also look for association rules based classifiers (see the CRAN Task View on Machine Learning or the Top 10 algorithms in data mining for a gentle introduction to some of them).
I'd like to mention another interesting approach that I plan to re-implement in R (actually, it's Matlab code) which is Discriminant Correspondence Analysis from Hervé Abdi. Although initially developed to cope with small-sample studies with a lot of explanatory variables (eventually grouped into coherent blocks), it seems to efficiently combine classical DA with data reduction techniques.
References


*

*Cutler, A., Cutler, D.R., and Stevens, J.R. (2009). Tree-Based Methods, in High-Dimensional Data Analysis in Cancer Research, Li, X. and Xu, R. (eds.), pp. 83-101, Springer.

*Saeys, Y., Inza, I., and Larrañaga, P. (2007). A review of feature selection techniques in bioinformatics. Bioinformatics, 23(19): 2507-2517.

A: As already mentioned Random Forests are a natural "upgrade" and, these days, SVM are generally  the recommended technique to use. 
I want to add that more often than not switching to SVM yields very disappointing results. Thing is, whilst techniques like random trees are almost trivial to use, SVM are a bit trickier. 
I found this paper invaluable back when I used SVM for the first time (A Practical Guide to Support Vector Classication) http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf
In R you can use the the e1071 package for SVM, it links against the de facto standard (in free software at least!) libSVM library. 
A: It's important to bear in mind that there's no one algorithm that's always better than others. As stated by Wolpert and Macready, "any two algorithms are equivalent when their performance is averaged across all possible problems." (See Wikipedia for details.)
For a given application, the "best" one is generally one that is most closely aligned to your application in terms of the assumptions it makes, the kinds of data it can handle, the hypotheses it can represent, and so on.
So it's a good idea to characterise your data according to criteria such as:


*

*Do I have a very large data set or a modest one?

*Is the dimensionality high?

*Are variables numerical (continuous/discrete) or symbolic, or a mix, and/or can they be transformed if necessary?

*Are variables likely to be largely independent or quite dependent?

*Are there likely to be redundant, noisy, or irrelevant variables?

*Do I want to be able to inspect the model generated and try to make sense of it?


By answering these, you can eliminate some algorithms and identify others as potentially relevant, and then maybe end up with a small set of candidate methods that you have intelligently chosen as likely to be useful.
Sorry not to give you a simple answer, but I hope this helps nonetheless!
A: Its worth to take a look at Naive Bayes classifiers.  In R you can perform Naive Bayes classification in the packages e1071 and klaR.  
