I want to build an n-ary decision tree with categorical features. I am using ordinary ID3 algorithm to build a tree.

Lets take the next dataset as a training dataset for building a decision tree:

dors age cost
1 4 0
2 4 1
3 5 0
3 6 1

A decision tree will look as such:

decision tree

Lets say now in test or prod time, an example comes with features dors=3 age=4 our tree cannot classify this example even though it has seen examples where doors=3 and examples where age=4. My implementation throws an error that value is missing and sklearn implementations of decision trees are always binary trees. Overall it cannot be expected that we covered all possible combinations in training set so there could always be examples in test set with unique combination of feature values which our tree cannot classify. How can this problem be solved and what are some solutions for solving it?


1 Answer 1


Your model naturally can't have learned anything about such an instance, so you have to make some sort of assumption if you don't want to just give up like your current implementation. One that comes to mind is to treat age as missing at the second node; there are several ways to handle missing values in a tree model, at either training or prediction time, see this answer. Since this particular use-case is only at prediction, I think either the weighted distribution or surrogate methods are most likely to be useful. The latter doesn't work in your small example (there are no other features to act as surrogate), but if there were other features that could serve as a surrogate, it seems likely to produce better results than simply dividing the sample across children.

  • $\begingroup$ This did open up a few possibilities for a solution. I will look deeper into this. Does this mean that my problem is is practically equivalent to "missing values" problem? Is there another way to fight this? $\endgroup$
    – dzi
    Nov 17, 2022 at 17:23
  • $\begingroup$ @dzi I think there's room for solutions that don't mimic missing value treatments, but I'm not aware of any. $\endgroup$ Nov 17, 2022 at 17:28

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.