What's an appropriate algorithm for classification with categorical features?

Question

My input data consists of a series of 8 integers. Each integer is a discrete token, rather than a relative numeric value (i.e. '1' and '2' are as distinct as are '1' and '100'). The output is a single binary value indicating success or fail. For example:

fail,12,35,60,82,98,111,142,161
success,23,46,59,87,102,121,145,161
fail,13,35,65,83,100,102,122,161

I have say 500,000 of these entries.

Success or failure is determined by the combination of the eight tokens that go to make up the input. I am certain that no single token will dictate success or failure, but there may be particular tokens or combinations of tokens which are significant in determining success or failure, I don't know, but would like to know.

My question is, what kind of machine learning algorithm should I implement to answer the question of which tokens and combinations of tokens are most likely to lead to success?

In case it's relevant or useful, a few more notes on the input data:

There is a limited range of tokens (and thus integers) in each slot. So with this data input:

success,A,B,C,D,E,F,G,H

A is always say one of 1, 2, 3, 4 or 5. B is always one of 6, 7 or 8. C is always one of 9, 10, 11 or 12. So in the general case, possible values for A are never possible values for the other slots and there are between 2 and 12 values for each slot. No idea if that makes a different to the answer but wanted to include it for completeness.

Answer 1

What you have is called a classification problem with categorical features. That is, the features can be represented numerically, but the numbers have no relative meaning.

Algorithms that rely on smooth function approximation will probably not work well here. These would include classic approaches to regression, and also function approximation via a neural network. That's because the data are anything but smooth!

In contrast, classic classification algorithms like Quinlan's C4.5 decision tree learner, (implemented in the Weka Toolkit as J48, and possibly in SciKitLearn as DecisionTreeClassifier, though the documentation is less clear), are ideal for this: they actually work by splitting up numeric values into discrete categories anyway, so there's no issue at all for them. Most versions also support a way to pre-tag features as categorical, and the algorithms rely on the cross-entropy of each feature's categories, without making assumptions of smoothness.