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?

  • 1
    $\begingroup$ Sorry, what do you mean by "sparse booleans (zero most of the time)"? Do you encode booleans as a {0,1} set and most of the time they are false? $\endgroup$
    – mapto
    Aug 22 '18 at 11:06
  • 1
    $\begingroup$ Yes, that's exactly it. I'll clarify it in the question. $\endgroup$ Aug 22 '18 at 11:07
  • $\begingroup$ Consider how your sparse data affects the feature importance function discussed here: machinelearningmastery.com/… $\endgroup$
    – mapto
    Aug 22 '18 at 11:24

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.


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.