9
$\begingroup$

A decision tree, while performing recursive binary splitting, selects an independent variable (say $X_j$) and a threshold (say $t$) such that the predictor space is split into regions {$X|X_j < t$} and {$X|X_j >= t$}, and which leads to greatest reduction in cost function.

Now let us suppose that we have a variable with categorical values in {$X$}. Suppose we have label-encoded it and its values are in the range 0 to 9 (10 categories).

  1. If DT splits a node with the above algorithm and treat those 10 values are true numeric values, will it not lead to wrong/misinterpreted splits?
  2. Should it rather perform the split based on == and != for this variable? But then, how will the algorithm know that it is a categorical feature?
  3. Also, will one-hot encoded values make more sense in this case?
Improve this question
$\endgroup$

3 Answers 3

Reset to default
9
$\begingroup$

You are right on all counts:

  1. If DT splits a node with the above algorithm and treat those 10 values are true numeric values, will it not lead to wrong/misinterpreted splits?

Yes absolutely, for exactly the reason you mention below:

  1. Should it rather perform the split based on == and != for this variable? But then, how will the algorithm know that it is a categorical feature?

Yes, as you correctly assume a (true) categorical variable should be compared only for equality, not order.

In general the algorithm cannot guess the nature of the feature, there has to be some parameters in the implementation which provide it with this information. Some implementations allow this, for example with Weka the features are typed with either a "numeric" or "nominal" (categorical) type.

  1. Also, will one-hot encoded values make more sense in this case?

Correct again, that's what should be done for a categorical feature in case the implementation treats all the features as numeric values.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you for the detailed answer. With respect to #2, does those implementations of DT check the values of categorical variables for equality rather than less and greater than values? Also, is there any Python implementation available for the same? $\endgroup$
    – Supratim Haldar
    Aug 9, 2019 at 7:47
  • $\begingroup$ Question 1: yes indeed, the algorithm can select a categorical variable and one of its values instead of a numeric variable and a threshold, then create a binary node where the condition is equality. Question 2: I don't know sorry, I'm not familiar with python libraries. There should be, I guess. $\endgroup$
    – Erwan
    Aug 9, 2019 at 10:32
  • 1
    $\begingroup$ @SupratimHaldar: Splitting on "Xi==a" is equivalent to the usual splitting on dummified data (unless ensembling with feature subsetting), so may not be implemented anywhere (in favor of just letting the user one-hot encode). But, a more general splitting, by picking any bipartition of the levels, can be done, in some special cases with an efficient search, and this is implemented in some packages. datascience.stackexchange.com/a/52103/55122 $\endgroup$
    – Ben Reiniger ♦
    Aug 9, 2019 at 16:00
  • $\begingroup$ Hi @BenReiniger for the answer and pointing to the other answer, it was very useful. One question - what exactly is meant by "... ordering the categories according to their average response value ..."? I will read the relevant section of ESL, but can you please provide a quick high level overview? $\endgroup$
    – Supratim Haldar
    Aug 13, 2019 at 14:50
  • 1
    $\begingroup$ @SupratimHaldar: "their average response value" means, for each level (of the categorical feature), computing the mean response/target/dependent value among sample points in that level. The smart splitting then considers the levels as though they were ordinal, in the order of their average response. (A bit like target/mean encoding, but this happens to the population at each node, rather than globally before training.) $\endgroup$
    – Ben Reiniger ♦
    Aug 13, 2019 at 16:07
4
$\begingroup$

  1. Yes, it will add a certain bias given by the fact that we are inserting an ordering that is not intrinsic to the categories

  2. Not really. The natural way to deal with a categorical feature that has L classes would be to explore ALL possible partitions! That means $2^L-1$ partitions!

  3. Only partially. OHE makes theoretically sense but does not work well for high cardinality features. In general, for Regression and Binary Classfication problems, the optimal solution is target encoding, as expressed by Breiman in his original paper on Classification and Regression Trees (1984). Indeed, he proves that by ordering the categories by mean response value (or probability), one can find the optimal split among the $2^L-1$ possible ones by only evaluating the L-1 splits of the so ordered categories.

One hot encoding is not that good for trees as it forces them to make many, sparse splits that can only separate few features, and it is particularly detrimental in case of high cardinalities. In that sense, Binary Encoding or even a Numerical Encoding might help achieve better separations with a less depth, even though they do insert a bias towards certain types of splits.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Might I add, that having seen people perform ordinal encoding on nominal variables, trees manage to perform quite decently. I've had a similar question here, where ordinal encoding was giving better results compared to target encoding while using trees. Target encoding can easily make your model overfit, but theoritically , as you said , it is the best technique among others since it orders the categories as they should be ordered , given the target response. $\endgroup$
    – Blenz
    Dec 13, 2019 at 11:22
  • 1
    $\begingroup$ True, target encoding can bring to overfitting. Numerical (ordinal) encoding and binary can often beat OHE in high cardinality situations. $\endgroup$
    – Davide ND
    Dec 13, 2019 at 11:27
  • $\begingroup$ Is there any freely available access to this proof of target encoding? I would like to understand why it works... $\endgroup$
    – Maverick Meerkat
    Nov 22 at 14:51
1
$\begingroup$

A decision tree has to convert continuous variables to have categories anyway. There are different ways to find best splits for numeric variables. In a 0:9 range, the values still have meaning and will need to be split anyway just like a regular continuous variable. If you considered each value as separate categories, you are basically just splitting at every possible point.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you. Actually my question was about "categorical" values (eg - male and female etc) and not "ordinal" (eg - low, medium, high etc). Thus, for categorical values where the corresponding numeric values has to significance, will the DT algorithm not lead to wrong splits? Because male=1, female=2 VS male=2, female=1 is same for me, but DT will not know that. $\endgroup$
    – Supratim Haldar
    Aug 9, 2019 at 7:46
  • 1
    $\begingroup$ Oh okay sorry I misinterpreted your question. But yes, if you just encode dummy variables then this wont be a problem. Also in some languages or frameworks, you can simply declare variable type and then it one hot encodes for you etc. $\endgroup$
    – fractalnature
    Aug 13, 2019 at 19:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.