Why decision tree needs categorical variable to be encoded?

Question

As per my intuition, decision trees should work better with categorical variables than with continuous variables. If this is the case, why is encoding needed on categorical variables? Can someone give me the intuition behind this?

Answer 1

...why is encoding needed on categorical variables?

That isn't true; decision trees can be built on both continuous and categorical features. (Why don't tree ensembles require one-hot-encoding? ) Some implementations, however, do not support categorical variables (notably sklearn (for now, update) and xgboost (their old politics, update)).

Now, there is a question of efficiency: the number of bipartitions of the set of categories is exponential in the number of categories, so a complete search of the possible splits is only practical for categorical variables with few categories.
There turns out to be a (surprising?) simplification though: if the underlying problem is a regression with MSE, or a binary classification with cross-entropy or Gini index, then the optimal split can be found by ordering the categories according to their average response value and treating it now as an ordinal variable split. (That said, still having many categories, especially small ones, might lead to heavy overfitting.) See Elements of Statistical Learning, section 9.2.4.

Some implementations perform the exhaustive bipartition search but cap the number of categories allowed. LightGBM and rpart perform the ordered search. (some R discussion, LightGBM).

All of the above is based on CART-based trees, but there is also another thread of trees by Quinlan (IDE, C4.5, etc.). Those will create higher arity splits for categoricals, with one child node for each category.

Answer 2

As I understand it, decision trees use the rules < threshold_value or >= threshold_value to group observations together, where threshold_value is the value of a variable which minimises the cost function for a particular split. (It's equally likely that the tree uses <= and > but that's just semantics).

This obviously works fine for numeric variables, but it does not work well with categorical variables - especially when the categorical variable cannot be ordered in a meaningful way. Therefore we need to numerically encode the categorical variable.

Answer 3

This is needed because not all the machine learning algorithms can deal with categorical data. Many of them cannot operate on label data directly. They require all input variables and output variables to be numeric. That's why We need to encode them.

Answer 4

A categorical variable should be encoded as number, anyway. You can encode it as sequence: 1, 2, 3... for example. It this case it's called ordinals. It's always possible to encode categorical variable as ordinals by mapping a number for each category. But it doesn't always make sense, because categories aren't always sequential.

1. For example, if you have 'low', 'middle', 'high' as values of categorical variable, it's reasonable to treat it as ordinals and encode it as 1, 2, 3. So, if algorithm splits the variable, and {1} goes to one branch and {2,3} to the other, it'd reasonable because 'middle' and 'high' are clearly separated from 'low' and they can form two different categories.

2. But if the values are 'spoon', 'fork', 'knife', it doesn't make sense to encode it as numbers, because tree algorithm would split the numerical value of the variable and it doesn't make sense why 'knife' and 'fork' should go to one branch and 'spoon' to the other. But that would be the case, if they are encoded as 1, 2, 3 and the it's split as {1} in one branch and {2, 3} in the other. So, in this case it's better to one-hot encode them. This way algorithm would treat them as non-sequential binary variables and they would have the same chance to fall into one separate branch with each other.

Answer 5

From what I understand from the sklearn long trove of discussion about implementing this in their base tree model:

To define an optimal way to split the categorical data into two groups you would have to look at all possible split. Enumerating all possible split grows up with 2 to the power of the number of categories wich is rapidly intractable. This is why you need specific algorthms to proceed to near-optimal splits / perform encoding to avoid this enumeration problem.