# N-ary decision tree with categorical features

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?

It looks like your features are not really categorical, at least age: with categorical features the possible values are known at training, so normally you cannot have a case like this (otherwise it means that the training set is not large enough, so not representative).
However this can happen with numerical features. But with numerical features the condition on the node 'age' would not be if age==5 then... as in the categorical case, it would be for instance if age < 5.5 then .... Such a condition can handle the case age=4.
• Its true that I didn't specify it but you can look at age as a categorical feature with values 4=new_car 5=old_car 6=very_old_car and same thing would apply. Does that just mean that training set is not large enough? It seems to me that with much many features the chances of having a "representative" training set decrease. Is there a way to fight this?
• @dzi oh ok, I think I see your confusion: in a binary decision tree the conditions are like if feature==value then ... else ..., i.e. any other value goes to the 'else' statement. In ID3 each node is indeed supposed to lead to every possible value of the variable, I don't see why this would be unrealistic. It's possible that a variable is never selected, but for any selected variable all of its values must be represented. Commented Nov 17, 2022 at 19:28