I'm a Computer Science student trying to implement the ID3 Algorithm and some of it isn't clear to me. The way I understand it, the ID3 algorithm involves building a (decision) tree by selecting an attribute for each node. Say I've selected Attribute A, which has 3 possible values for the root node.

enter image description here

Is it correct that the root node, which is now A, should have 3 branches? (i.e., one branch for each possible value of A? And can I select the same attribute for multiple child nodes of A? In other words, is selection of attributes mutually exclusive by level or by node? Because if it's mutually exclusive by node, then what happens if I run out of attributes?


1 Answer 1


It is correct that the branches are mutually exclusive, and that you can not select the same attribute value for multiple child nodes of A. The reason to why this is sufficient relates to your second question.

As soon as you run out of attributes down the tree, this means that along the path from root to the leaf node where you are you have passed each attribute, and just have chosen a specific value for each instance. Because of that all instance within your leaf node will be exactly the same, and are thus expected to have the same class. If this not the case then your data contains noise, and can thus not be perfectly classified.

It may help to look at the features of an instance as a logical AND rule. An instance with feature values F1 = cold, F2 = rain, F3=black basically says COLD AND RAIN AND BLACK, which is exactly the logical rule that you will obtain when traversing down the tree from root to path.

From the above it follows that whenever you split the data on all attributes (no matter what order) you will always perfectly classify every instance in the data, hence the reason that decision trees are high variance models. However it is still important to choose the features in such an order that keeps the tree small (and thus less complex), which makes it more likely to generalise on unseen data.

Note that in case of numerical attributes you can obviously not choose all feature values, and work with intervals. Here it may occur that in a leaf the data is still slightly mixed, which may result in a mixture of classes at the leaf node. However by choosing the intervals sufficiently small, or based on some criteria (such as the information gain) none of this should be an issue.


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.