2
$\begingroup$

I am using xgboost and have a categorical unordered feature with 25 levels. So when i apply one hot encoding i have 25 columns. This introduces alot of sparsity. Even more unusual, my feature importance report shows 5 of these one hot encoded column in top 10, with one of them appearing at the top.

I tried to see if there was a diffrence in percentage of these categories between my binary classes (1, 0) but there isn't so i am a little perplexed as to why it is assigning such a high feature importance to them.

i have read online that if we have a categorical variable with q levels, the tree has to choose from ((2^q/2)-1) splits. For a dummy variable, there is only one possible split and this induces sparsity

i am not sure i understand this, say i have a column called color: red, green, blue,yellow , and i implement one hot encoding so is the number of splits that happen is 2^4/2 -1 = 3? if this increases as i have e.g. 2^25/2 -1, more splits means the tree is more likely to find a 'good split' for data at hand and lead to overfitting? But what i don't understand is how this splitting chages with dummy variables.. does that equation hold or not for one hot endoded variables.

am i interpreting this correctly?

sources elemts of statisicatl learning: enter image description here

https://towardsdatascience.com/one-hot-encoding-is-making-your-tree-based-ensembles-worse-heres-why-d64b282b5769#:~:text=For%20every%20tree%2Dbased%20algorithm,a%20feature%20and%20a%20value.&text=The%20trees%20generally%20tend%20to,values%20(0%20or%201).

Improve this question
$\endgroup$
1
  • $\begingroup$ I'm not at all answering your question, but to me, you should look at Category Encoders for such variables. This basically replaces the class found by a value representing how it acted in X_train. For example, if more than 80% of individuals with this class encountered in X_train were classified as "1", the value replacing this class will be close to 1. This avoids having too much variable with OneHot, on features with many levels. $\endgroup$
    – Adept
    Aug 11, 2020 at 12:15

1 Answer 1

Reset to default
2
$\begingroup$

i have read online that if we have a categorical variable with q levels, the tree has to choose from ((2^q/2)-1) splits. For a dummy variable, there is only one possible split and this induces sparsity

i am not sure i understand this, say i have a column called color: red, green, blue,yellow , and i implement one hot encoding so is the number of splits that happen is 2^4/2 -1 = 3?...

You have the order of the operations wrong there (probably because the "((2^q/2)-1)" you quote above is misleading, but compare to the ESL quote in your image): it's $$ \frac{2^4}{2}-1 = 2^{4-1}-1 = 7$$ possible splits, namely:
(red green blue) vs (yellow)
(red green yellow) vs (blue)
(red blue yellow) vs (green)
(green blue yellow) vs (red)
(red green) vs (blue yellow)
(red blue) vs (green yellow)
(red yellow) vs (green blue)

if this increases as i have e.g. 2^25/2 -1, more splits means the tree is more likely to find a 'good split' for data at hand and lead to overfitting?...

It is certainly true there are more possible splits, and that increases the model's capacity and hence perhaps increases overfitting. This is particularly worrisome if some of the levels are quite rare, and less so if you have a lot of data.

But what i don't understand is how this splitting chages with dummy variables.. does that equation hold or not for one hot endoded variables.

No, when you one-hot encode such a feature, the tree now must split on only one of those dummy variables (at a time). So, considering all the $q$ levels' new indicator variables, you have exactly $q$ splits to consider. In your example, they are the first four splits given above:
is_yellow=0 vs is_yellow=1
is_blue=0 vs is_blue=1
is_green=0 vs is_green=1
is_red=0 vs is_red=1

Improve this answer
$\endgroup$
5
  • $\begingroup$ this makes sense thanks for clearing up $\endgroup$
    – Maths12
    Sep 17, 2020 at 13:44
  • $\begingroup$ so, in summary having one hot encoded is not recommend because it reduces splits, and forces tree in one direction? @Ben Reiniger $\endgroup$
    – Maths12
    Sep 18, 2020 at 14:37
  • $\begingroup$ The main idea is that by one-hot encoding you've diluted the power of the categorical variables: the tree might have to make several sequential splits to get "the right" split of the category's levels, and in the greedy building approach that's not guaranteed, especially when other features are vying for attention. I've not seen a very convincing (thorough) test of that, but there are some examples out there where one-hot encoding decreases the performance of the model, and feature importances lend evidence that the above idea is the reason. $\endgroup$
    – Ben Reiniger ♦
    Sep 18, 2020 at 14:45
  • $\begingroup$ when you say feature importances lend evidence to it do you mean it's because in the report out of say the top 10 features 8 are OHE? $\endgroup$
    – Maths12
    Sep 20, 2020 at 19:06
  • 1
    $\begingroup$ The opposite: very few top features are the dummy variables. Here's an article that tries to support that: towardsdatascience.com/… And here's a more thorough study suggesting the opposite (but most of the datasets used don't have any large-cardinality categorical features, so I wouldn't call this definitive): feat.engineering/categorical-trees.html $\endgroup$
    – Ben Reiniger ♦
    Sep 21, 2020 at 3:01

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.