1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – amol goel
    Oct 27, 2022 at 14:34
  • $\begingroup$ @amolgoel, this question only asks about categorical features. $\endgroup$
    – Ben Reiniger
    Oct 27, 2022 at 15:36
  • $\begingroup$ 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. $\endgroup$
    – amol goel
    Oct 27, 2022 at 16:03
  • $\begingroup$ 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. $\endgroup$
    – Iyar Lin
    Oct 27, 2022 at 16:27

1 Answer 1

2
$\begingroup$

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.

Historically, Quinlan's ID3 is the most well-known algorithm that handles only categorical variables, which has been later extended by the same author into C4.5 to handle both numerical and categorical variables; the latter holds also for CART developed by Breiman et. al.

If you are willing to try different frameworks and/or programming languages, you can explore the J48 implementation of WEKA in Java (Waikato Environment for Knowledge Analysis Machine Learning) or DecisionTree.jl in Julia; in the latter case, I suggest you read this issue which is essentially your doubt. I hope that this gives you some hope in solving your problem as both codes are open-sourced and can be inspected, if necessary.

$\endgroup$

Your Answer

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

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