Impact of sparse features on tree-based models

Question

Say you have a highly imbalanced binary classification problem. Some of the features are binary features, where they're false most of the time, but when they're true they tend to be highly predictive (of the minority class). What impact, if any, would the sparseness of the feature have on the likelihood of the feature being picked as a split?

Answer 1

There are of course different split algorithms and losses that change the behaviour in these cases a little bit. However if we take a look at the most common choice in modern tree based algorithms we can deduce what the impact would be.

Let's have a scenario where we have two binary features that we have to decide between and their corresponding target distribution.

$$P(f_1=0) = 0.95$$

$$P(y=0|f_1=0)= 0.5$$

$$P(y=0|f_1=1)= 0.05$$

$$P(y=0) = 0.5225$$

This means feature 1 is mostly 0, it is 50/50 whether the target is 0 in this case but if it is 1 then the target is almost always 1 as well.

Now we have a second feature which is a bit different.

$$P(f_2=0) = 0.5$$

$$P(y=0|f_2=0)= 0.4225$$

$$P(y=0|f_2=1)= 0.6225$$

In this case the feature is split evenly and there is predictive impact but it is less extreme.

Gini impurity

By reducing the gini impurity we hope to minimize the number of splits neccessary. The current gini impurity is:

$$G_I(p) = 1 - 0.5225^2 - (1-0.5225)^2 = 0.4989875$$

When splitting on a feature we need to take the weighted average gini impurity and check the reduction.

$$G_{If1=0} = 0.5$$

$$G_{If1=1} = 1 - 0.05^2 - 0.95^2 = 0.095$$

Given that most splits (95%) will go the left we weight that one much more:

$$G_{If1} = 0.95*0.5 + 0.05*0.095 = 0.47975$$

In the second feature we have:

$$G_{If2=0} = 1 - 0.4225^2 - (1-0.4225)^2 = 0.4879875$$

$$G_{If2=1} = 1 - 0.6225^2 - (1-0.6225)^2 = 0.4699875$$

Given that the splits are equal we get a normal mean:

$$G_{If2} = 0.4879875*0.5 + 0.5*0.4699875 = 0.4789875$$

In this case it is a bit close but it would choose the less sparse feature. The reason is that while the minimum impurity is much worse, because the split is completely balanced the impact in reduction on both sides has a bigger effect. In the sparse case the split to the right has a major reduction but only counts for 0.05 of the cases while the impurity on the left is at it's highest. As you can see there is a trade-off between the impurity on either side and the amount of cases where the impurity is reduced.