N-ary decision tree with categorical features

Question

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:

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?

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.