0
$\begingroup$

Is the ID3 decision tree induction algorithm guaranteed to find an optimal decision tree (a tree that best classifies the training examples over all possible trees) for any given dataset?

$\endgroup$

2 Answers 2

2
$\begingroup$

It depends what you mean by "best classifies", but if you mean "is the tree with the best training performance", no. The best performance on the training examples is not really a desirable property because it encourages the model to just memorise the data instead of learning the underlying pattern. There are a number of trade-off which need to be made in constructing the model, I believe ID3 constructs a tree in a greedy way by splitting the nodes which maximise the information gain.

$\endgroup$
1
$\begingroup$

Unfortunately no. ID3 is greedy algorithm and selects attribute with max Info Gain in each recursive step. This does not lead to optimal solution in general. Additionally ID3 makes n-ary splits (splits on all possible categories of attributes) which also may not be optimal for the whole tree. Another problem is that ID3 uses Info gain that does not make a difference between attributes with different number of categories. This may lead to selection of ID as "optimal" split.

$\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.