37
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ If you're still interested, you might want to check my answer on dimensionality reduction and my answer on hierarchical classification. $\endgroup$ – Aleksandr Blekh Jan 29 '15 at 15:40
  • 1
    $\begingroup$ 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. $\endgroup$ – smci Nov 16 '16 at 12:51
  • $\begingroup$ See also stats.stackexchange.com/questions/146907/… $\endgroup$ – kjetil b halvorsen Jun 29 at 19:48
20
$\begingroup$

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 Brieman 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 effichent/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.

$\endgroup$
  • 4
    $\begingroup$ All these suggestions are interesting, I agree that random forest should handle natively categorical variables, but scikit-learn doesn't... I think that's one of scikit's main flaw btw. I'll try your code on my data to see what happens, and I'll see about your other suggestions ! $\endgroup$ – Bertrand R Apr 25 '14 at 23:53
  • 1
    $\begingroup$ Try out the R implementation. Running it is a one liner. Reading the data is extremely easy and there is a new-ish paralell implementation which is blazing fast and memory efficient: r-bloggers.com/… On the other hand. Are your classes imbalanced? in the r implementation you can grow each tree from a balanced bootstrap sample sampsize=c(x,x). This has produced better binary classifications for me. You can play around with the sizes and tweak the classification very easily using the OOB confusion matrix R outputs. $\endgroup$ – JEquihua Apr 26 '14 at 15:50
  • 2
    $\begingroup$ R's randomForest implementation allows factors with a maximum of 32 levels. scikit-learn is less restrictive, providing you first create dummy variables (see the pandas.get_dummies function). H2O's implementation of random forest has performed really well for me (see 0xdata.com/docs/master/model/rf). $\endgroup$ – Alex Woolford Jun 23 '15 at 15:33
  • 1
    $\begingroup$ there is a newer and faster implementation of random forest, the package is called ranger. Great stuff really. Orders of magnitude faster and doesn't have the 32 levels limit. $\endgroup$ – marbel Jan 7 '16 at 1:17
6
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ This is fine for categorical features with n<=3 as you can generate all of the same splits as you would by considering the feature natively as categorical. For larger n it is possible to achieve sets of splits that are equivalent to the categorical split but the algorithm may or may not find them as efficiently...however if you split the feature into n numerical features you are also reducing the efficiency with which the algorithm can find splits. Someone needs to add categorical variable support into the scikit-learn implementation as it is great otherwise. $\endgroup$ – Ryan Bressler Apr 25 '14 at 18:10
  • $\begingroup$ I agree with you when you say that it sounds suspicious to introduce ordinality in categorical data... I'd rather not have to do so, but I can at least give it a try and see what happens ! $\endgroup$ – Bertrand R Apr 25 '14 at 23:50
  • 4
    $\begingroup$ I had a long discussion about this question on the sklearn mailing list (you can read parts of it here: mail-archive.com/scikit-learn-general@lists.sourceforge.net/…). The opinion of one of the implementers was that with sufficiently deep trees, ordinal-encoded categorical features might work reasonably well (in addition to being more computationally efficient). Anyway, if you try it, I'd be very interested to hear about your results/conclusion, as this is an issue I keep bumping into. $\endgroup$ – cjauvin Apr 26 '14 at 0:39
  • 1
    $\begingroup$ So I tried to keep a single numerical variable for the categorical ones, and it actually works surprisingly well, and much better than adding a great number of binary entries... I also tried to sort the values according to their mean wrt to the target. And it works fine too $\endgroup$ – Bertrand R Apr 28 '14 at 20:45
  • $\begingroup$ I'm not surprised by that actually.. it's in line with what I have observed in a couple of different settings, although judging by the number of upvotes, this is a rather counterintuitive idea. $\endgroup$ – cjauvin Apr 28 '14 at 22:21
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$
  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.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.