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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
answered Oct 27, 2017 at 14:03
$\begingroup$
$\endgroup$
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.
