Large no of categorical variables with large no of categories

Question

I'm working on a binary classification problem where the dataset is slightly imbalanced (30% class 0 | 70% class 1).

Most of my features are categorical with large number of categories. For example: one of them has 310 categories but the top 10 most frequently occurring variables account for ~50% of the training and test data. I was thinking of keeping these top k frequently occurring values and encoding all the other values as another category "others".

Would it be okay to do so?

Also, what kind of classifier would be optimal for such a task? I was looking at random forests. However, due to noisy data (too many categories, too many features) my model doesn't generalize too well (low recall and precision).

Thank you for your time.

PS: Data not time series

Answer 1

I used to work a lot with such data in the past.
When you have many categorical features with high cardinality, you must avoid one-hot encoding them because it consumes too much memory and above all trees built from them will be too deep and worse than trees built without one-hot encoding.
You need a Tree based model library implemented with native categorical feature support (i.e. not needing the categorical features to be one-hot encoded).
I suggest you to use one of those 4 implementations :
- CatBoost
- LightGBM
- H2O GBM
- H2O Random Forest
Scikit learn and XGBoost implementations still need one-hot encoded categorical variables so I don't recommend using one of these libraries if your dataset has high cardinality categorical variables (i.e. with more than about 10 levels/categories).
See this :

LightGBM offers good accuracy with integer-encoded categorical features. LightGBM applies Fisher (1958) to find the optimal split over categories as described here. This often performs better than one-hot encoding.

Answer 2

"I was thinking of keeping these top k frequently occurring values and encoding all the other values as another category "others". Would it be okay to do so?", for me also it should be ok.

I have few more comments:

1. You can also try with new features. That is combine multiple categorical features, instead of using all of them independently.
2. Since you have many categorical features, one hot encoding of every categorical feature will generate a huge list of features, which may overfit your model. You can also try without One Hot Encoding as it's not always mandatory for Decision tree.

Answer 3

Hi and welcome to the forum. Just as an idea:

The strategy you suggested (extracting important classes in the X and leave the rest as "other") may work and it‘s worth a try. Make sure you don‘t throw away information by keeping the levels in the "other" category.

The alternative is (of course) to one-hot encode all classes.

In any case, I would check if regulation (by L2 or L1 norm) is useful.

Some background: L1 regulation can shrink features to zero, L2 regulation can shrink features but they never become zero.

So say you have a lot of one-hot encoded features but you have no idea which one are really important. Just let the computer do the job of selecting features by L1 regulation.

Method wise, the problem sounds like a candidate for boosting. Boosting is similar to random forest, but in addition, the algorithm tried to focus on especially hard to predict rows/observations. This is done by growing a lot of very small trees.

Prominent algorithms are LightGBM, Catboost, XGboost. They all offer support for regulation.

So I would start with "a lot" one-hot encoded features and boost with L1 regulation to get rid of irrelevant features.

Answer 4

Encoding categorical variables so that you do not lose information and do not add non-existent relationships between the categories is fundamental to achieving good performance from your model.

You can not simply LabelEncode your categories because they add non-existent relationships. For example, if you have a feature named 'color' which takes on three values - Red, Blue and Green and you encode Red as 1, Blue as 2 and Green as 3, this will imply relationships such as

$$Red < Blue < Green$$ $$Blue = (Red + Green)/2$$

Because of the curse of dimensionality, you can not use OneHotEncoder as that will inflate your feature space beyond your model's comprehension because of a relatively smaller dataset.

The approach of taking only top k frequently occurring categories will be suboptimal as you loose information. A better approach would be to use a FrequencyEncoder which replaces categories with their frequencies (or counts) of occurrence.

More sophisticated approaches like Target Encoding and Contrast Coding Schemes which take target variable into account when encoding categories are known to perform better in cases of high cardinality categories.

If some of your categories have string values which are not domain-specific you can convert them into meaningful vectors using pre-trained Word2Vec. If any of your categories contain long text (e.g. description of an event), you can train your own Word2Vec on sentences built from values of such a category. By taking a weighted-average of the vectors from a sentence, you can encode sentences.

As far as models are concerned, with the right kind of encoding, Random Forests and Gradient Boosted Machines will work just fine. SVMs and Vanilla Neural Networks are also worth considering. To boost your accuracy you can definitely use XGBoost.

Answer 5

If you're using python and sklearn I'd suggest you take a look at http://contrib.scikit-learn.org/categorical-encoding/

There's a large number of different encoding schemes you can experiment with. Many of them have parameters such as smoothing for the TargetEncoder which you can select using hyper-parameter optimisation to ensure you don't overfit.