# Decision tree implementation in python that correctly handles categorical variables

Is there a Decision tree implementation in python that correctly handles categorical covariates?

By "correct" I mean that it is able to send any subset of category levels down one daughter node and the rest down the the other. So far all implementations I came across required using one-hot-encoding representation. This is a serious limitation since it limits the tree to doing one-vs-rest splits which can greatly reduce accuracy.

To illustrate the problem we can take the iris dataset and randomly split each species to 2 sub-species:

data("iris")
library(rpart)
iris$$Species <- factor(as.vector(unlist(tapply(iris$$Species, iris\$Species,
function(x) paste0(x, sample(rep(c(1,2), length.out = length(x))))))))
r_tree <- rpart(Sepal.Length~Species, data = iris)

r_tree


Which gives:

n= 150

node), split, n, deviance, yval
* denotes terminal node

1) root 150 102.1683 5.843333
2) Species=setosa1,setosa2 50   6.0882 5.006000 *
3) Species=versicolor1,versicolor2,virginica1,virginica2 100  43.4956 6.262000
6) Species=versicolor1,versicolor2 50  13.0552 5.936000 *
7) Species=virginica1,virginica2 50  19.8128 6.588000 *


We can see that the tree was able to split along the original species by sending both sub-species of each original species down the same node. If we were to use one-hot-encoding, at least one of the sub-species would have had to end up in a different node than its' counterpart.

More on why one-hot encoding reduces accuracy can be found here.

• For numeric, Python sklearn implementation splits node in two. Split point is decided by finding gini at all possible split values. Split point corresponding to The highest gini or lowest impurity is taken. Commented Oct 27, 2022 at 14:34
• @amolgoel, this question only asks about categorical features. Commented Oct 27, 2022 at 15:36
• I don't see why Iyar can't have both subspecies under same node. It will depend on if such a split is possible by gini maximization. Commented Oct 27, 2022 at 16:03
• By definition every time a split is made one of the sub species will be sent down one node and the other down the other node. Commented Oct 27, 2022 at 16:27

I'm not aware of any specific implementation in Python that handles categorical data as you are asking. DecisionTreeClassifier of sklearn does not handle categorical data as the documentation says, and as this post discusses.