1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – dzi
    Commented Nov 17, 2022 at 17:17
  • $\begingroup$ @dzi A categorical variable has only a finite number of values, so increasing the size of the training set with random instances is guaranteed to reach the full set of values at some point. Supervised learning relies on the assumption that the training set is a representative sample, but If you have 3 possible values but the training set contains only two, it's definitely not a representative sample for your data. $\endgroup$
    – Erwan
    Commented Nov 17, 2022 at 18:34
  • $\begingroup$ But there are all 3 possible values in training set, there just isnt a combination of all possible values for number of doors and age. Expecting all possible combinations of all features to be present isnt realistic $\endgroup$
    – dzi
    Commented Nov 17, 2022 at 18:56
  • 1
    $\begingroup$ @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. $\endgroup$
    – Erwan
    Commented Nov 17, 2022 at 19: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.