Improve classification with many categorical variables

Question

I'm working on a dataset with 200,000+ samples and approximately 50 features per sample: 10 continuous variables and the other ~40 are categorical variables (countries, languages, scientific fields etc.). For these categorical variables, you have for example 150 different countries, 50 languages, 50 scientific fields etc...

So far my approach is:

1. For each categorical variable with many possible value, take only the one having more than 10000 sample that takes this value. This reduces to 5-10 categories instead of 150.

2. Build dummy variable for each categorical one (if 10 countries then for each sample add a binary vector of size 10).

3. Feed a random forest classifier (cross-validate the parameters etc...) with this data.

Currently with this approach, I only manage to get 65% accuracy and I feel like more can be done. Especially I'm not satisfied with my 1) since I feel like I shouldn't arbitrarily remove the "least relevant values" according the the number of sample they have, because these less represented values could be more discriminative. On the other hand, my RAM can't afford adding 500 columns * 200000 rows to the data by keeping all possible values.

Would you have any suggestion to cope with this much categorical variables?

Answer 1

1. Random forests should be able to handle categorical values natively so look for a different implementation so you don't have to encode all of those features and use up all your memory.

2. The problem with high cardinality categorical features is that it is easy to over fit with them. You may have enough data that this isn't an issue but watch out for it.

3. I suggest looking into random forest based feature selection using either the method Breiman proposed or artificial contrasts. The artificial contrasts method (ACE) is interesting because it compares the importance of the feature to the importance of a shuffled version of itself which fights some of the high cardinality issues. There is a new paper "Module Guided Random Forests" which might be interesting if you had many more features as it uses a feature selection method that is aware of groups of highly correlated features.

4. Another sometime used option is to tweak the algorithm so it uses the out of bag cases to do the final feature selection after fitting the splits on the in bag cases which sometimes helps fight overfitting.

There is an almost complete ace implementation here and I have a more memory efficient/fast RF implementation that handles categorical variables natively here...the -evaloob option supports option 4 I'm working on adding support for ACE and a couple of other RF based feature selection methods but it isn't done yet.

Answer 2

Instead of dummifying your categories, why wouldn't you simply use a single numerical variable for each? In the context of random forests, I've often been wondering about the consequence of doing that (because I agree that it sounds suspcious to introduce ordinality in categorical data with which if often doesn't make sense), but in practice (at least with the scikit-learn implementation of RFs I've been using), I've often observed that it doesn't make a difference on the results (I'm not sure why though).

Answer 3

I think you should consider a/more variable reduction technique(s). It gets rid of the not so influent predictors.

I have been reading a lot about data pre-processing and it is a great solution to reduce the n° of your variables.

My suggestions are as follows:

• for qualitative variables, replace missing values with category "missing". It can introduce bias if the data is not missing at random, but at least you'll have all your observations intact and the missingness might reveal a different behaviour.
• eliminate zero variance predictors or near-zero variance predictors (be careful not to eliminate dummy variables with high unbalanced categories that can separate your Y efficiently. Make some graphs for the variables you think might be important). In R, you can use the 'nzv' function from the 'caret' package. This will highly reduce your data dimension.
• eliminate correlated predictors. Use Kendall's correlation matrix because it is more fit to construct in the presence of categorical variables. The downside is you have to transform all your nominal vars into categorical ones.
• there are feature selection methods that will reduce their number even more (clustering - you choose a single representative of each cluster, the LASSO regression, etc...). I haven't had the chance to test them yet because the other steps reduced my variables to under 100.

Also, I would suggest using the AdaBoost algorithm instead of the RF. Personally, the researches that I've done gave me very similar Gini coefficients for both these methods. The good part about AdaBoost is that in R, it handles missing observations. So you can skip the 1st step of this list

I hope it helped a little. Good luck

Answer 4

You may want to consider mixed-effects models. They are popular in social science due to their performance on high-cardinality categorical data, and I have used them to make great predictive models outperforming popular machine learning approaches like gradient boosted trees, random forests, and elastic-net regularized logistic regression. The most well-known implementation is R's lme4 package; the function you'd use for classification is glmer, which implements mixed-effects logistic regression. You may have issues with scaling to your dataset, but I have done 80k rows with 15 features without too much difficulty.

Answer 5

1. When you say "build dummy variable for each categorical one", sounds like you're using Python not R? R randomforest can natively handle categoricals, also consequential memory reduction. Try R.

2. Next, you don't need to manually prune/merge the categorical levels, that sounds like a major pain. And even if you did, you're not guaranteed that the most populous categories are the most predictive. Control randomforest complexity with parameter nodesize: start with a large nodesize, and progressively reduce it (this is hyperparameter search).

3. Variable selection will be useful. @lorelai gives good recommendations. Try to eliminate useless (low-importance or highly-correlated) features. Tree construction is quadratic to the number of features, so if you even eliminate a third it'll pay dividends.

Answer 6

You should look at the H2O.ai package. It handles categorical variables out of the box without having to do any encoding (make sure the variables are factors).

I particularly like their implementation of Gradient Boosted Machine (GBM) because you can then look at the variable importance after building the model. GBM's also have the nice feature of being resistant to overfitting.

If you want to explore other models, they have: GLM, Random Forest, Naive Bayes, Deep Learning, etc.

See: http://docs.h2o.ai/h2o/latest-stable/h2o-docs/data-science/gbm.html

It's also easy to install (Windows, Linux, Mac) and easy to run with API's using R, Python, Java, and Scala.

It can use multiple cores to speed things up.

In the near future, they will support GPUs.

It's also open source and free (There is Enterprise support).