I have read that decision trees can handle categorical columns without encoding them.
However, as decision trees make splits on the data, how does it handle Nominal Categorical variables?
Surely a standard numerical split would be spurious in this situation.
The fact is, if you feed a training dataset with categorical features without numerical encoding into a decision tree, say, in scikit-learn of Python, you see an error message, as the package has no idea how to do the binary split with your (nominal) categorical feature.
In principle, we can choose to do tree split in a way that all different values of a categorical feature give rise to different branches. However, if the number of categories is large, you will get a shallow tree which is not good for capturing complex dependencies.
The usual approach to deal with categorical features is to first numerically encode them, either one-hot, hash, target encoding...,etc. Target encoding is appealing in that it does not create many features, but the issue of target leakage has been perplexing until the recent emergence of catboost. https://arxiv.org/abs/1706.09516
To address your further question: Both latest versions of XGBoost and LightGMB support one-hot encoding and and a special kind of target statistics encoding. https://xgboost.readthedocs.io/en/stable/tutorials/categorical.html https://lightgbm.readthedocs.io/en/latest/Features.html#optimal-split-for-categorical-features
The trick for the latter comes from Fisher's paper "On Grouping for Maximum Homogeneity" back in 1958. The question we have is to get the best split for an internal node in the tree growth. Best is defined in terms of some kind of homogeneity. Suppose a categorical feature has values $\{a,b,c,d\}$. Then, Fisher told us that we don't need to enumerate all possible partitions, $\{\{a\}, \{b,c,d\}\}$, $\{\{a,b\},\{c,d\} \}$,...etc. but it suffices to partition according to some order of elements. The ordering implemented in both XGBoost and LightGBM is the gradient statistics. That is, you first convert a (nominal) categorical feature to a numerical one by gradient statistics and then find the best split like what you do with a numerical feature.
Yes, in the sense that you only need to specify which columns are of the categorical type and then the package finding the optimal split automatically for those categorical features internally according to the passage above. Let me stress that it feels like no encoding is done and the packages handle categorical columns automatically, but it is the gradient statistics (a kind of target encoding) under the hood.
It depends on what you want to do. XGBoost used to not support automatic handling of categorical features but now they do. LightGBM, XGBoost, and Catboost are state-of-the-art boosting machine packages. I am not in a position to benchmark their performances, but all of these provide a pretty good API to deal with categorical features.
One caveat: There is one issue of the gradient statistics encoding. In such encoding target values are used and so target leakage exists. Catboost improved this by using a special kind of target statistics encoding.
In short, in principle you can split in a way that each category is mapped to a new branch. This is a split according to a nominal categorical feature without encoding, but it is no good. So we do need some kind of good encoding to do the split and the state-of-the-art packages all support automatic handling of categorical features. If you dataset is small and exhibits prediction bias, you may try catboost.
Use dummy variables for most accurate results. For example if you have 4 cities, create dummy variables: city_2, city_3, city_4, where a sample coming from city_4, would have values 0 for city_2 and 3, and a 1 for city_4. You will notice I did not write city_1, this is because if you have zeroes for city_2,3,4, that implies a 1 for city_1. Doing this insures higher accuracy, and less correlation.
A different type of solution is by using a numerical feature with possible values: 1,2,3,4. This however, leads to lower accuracy as the machine learning model tries to 'understand' the relationships between the values. It is intuitive to understand why having the category city encoded the same way as age, for example, is not a good idea.
