Decision Tree only splits to the left

Question

I can’t really understand, why my decision tree only splits to the left.

I originally have 2 categorical features (further named feature 0 and 1), which I concat to one feature since feature 1 is dependent on feature 0.

Example:

Feature 0: A Feature 1: b

New Feature: A_b

Now I use this new feature (One-Hot-Encoded) to predict some categories.

There is just the problem that, by doing that the decision tree only grows to the left. Although the Gini on the right leaf nodes are still really high, and there are also enough samples to split further on the right subsets.

But if I just use the 2 features without concatenation it splits in both direction. But I can’t do that since both features are dependent on each other.

By dependent I mean the following:

Not every category of feature 1 appears with feature 0. Hence the decision tree would build rules, which aren’t representing what could be possible in reality.

Answer 1

This is the typical behavior if you have only one one-hot-encoded feature.

Explanation

1. With a single one-hot-encoded feature, the feature-vector has the form of an $n$-dimensional vector where exactly one element is $1$ and all other features are $0$. Hence, the decision tree is trained with $n$ features.
2. Typical decision trees (note that there are exceptions) find in each split one dimension $i$ and a threshold $t$. All samples with $x_i\leq t$ go to the left and all samples with $x_i > t$ go to the right. If only the two values $0$ and $1$ occur, it is safe to assume that the threshold is $0.5$ (although the value depends on the implementation).
3. If we now look at a split $x_i \leq t$, all samples with $x_i=1$ go to the right. Since exactly one feature is $1$, all samples on the right look exactly the same and no more splitting can be done on the right. On the left side, there are still differences (we know that $x_i=0$, but not, which other category is $1$), so there can still be splits on the left side.

How to fix this?

1. Don't merge the features. Decision trees can handle dependencies between features quite well. So there is no need for dependency-related preprocessing.
2. Add additional information:
   • Are there any "clusters" or hierarchies in your categories? E.g. if you have country names as features, then you might add the continent as another feature. This would allow the decision tree to split e.g. by Europe / Non-Europe first instead of France/Non-France. This could lead to a more balanced tree.
   • You can even go further and add numeric information (e.g. size of a country in above example, or hue-value of a color name). Everything that allows the tree to split the categories into two groups instead of moving one category to the right side and all others to the left side.
3. Use a different encoding. There are multiple alternatives to one-hot-encoding that allow for better splits. One example is the target encoding. If you use scikit-learn, you could have a look at the category encoder package.