¿Cuál es la mejor manera de predecir una clase +/- en un escenario de aprendizaje automático donde tengo k características trinarias y un conjunto de datos del orden de cientos o miles?

Suponiendo que las características no son ordinales (e incluso si lo son), comenzaría con ingenuos bayes.
Maneja las características categóricas correctamente y, a menudo, produce resultados sorprendentemente buenos. Puede configurarlo fácilmente con R (solo reemplace los datos del iris con sus datos):

#get the data data<-iris #get data statistics summary(data) #split to train and test randomly index<-1:nrow(data) train<-sample(index,100) test<-index[-train] #install the needed package for Naive Bayes (called e1071) if(require("e1071")==FALSE) install.packages("e1071") #create an instance of the Naive Bayes classifier classifier<-naiveBayes(data[train,1:4], data[train,5]) #predict results<-predict(classifier, data[test,-5]) #show results table(results, data[test,5]) 

También puede encontrar una implementación en Python, Weka, RapidMiner y, básicamente, en cualquier otra plataforma de análisis.