1
$\begingroup$

I just started studying decisions trees and I am trying to construct a tree for a training set which uses Status as the class label. I am using the misclassification error as measure of impurity. After the first iteration, the information gain indicates that Department should be the tree root. The following table represents the sub-table for Department = Secretary.

Training set after the first iteration

I got to this point and I don't know how to add the corresponding nodes to the tree. Should the next node be Age or Salary?

Thanks!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

You should process ALL of the possible splits and hope for information gain somewhere down the line.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This doesn't sound like a good idea to me. This can potentially lead to exponential blowup in running time on some data sets, if you get unlucky, and that sounds undesirable to me given how decision tree learning is typically used in practice. Do you have a citation or reference that suggests this approach? $\endgroup$
    – D.W. ♦
    Feb 17, 2016 at 3:14
0
$\begingroup$

You are asking how to resolve ties. The answer is: resolve the tie arbitrarily. In other words, randomly pick one of the attributes. As far as you can tell at this stage, they are all equivalent.

Is this optimal? No. But the ID3 algorithm is already not claimed to be optimal. It is a greedy algorithm, which means we make the best decision we can at each stage, using only local information, without trying to predict their future impact. The benefit of this approach is that you get an algorithm that is very efficient at computing a decision tree. And, while it might not output the optimal decision tree, experience suggests that the resulting decision tree is often still very good in practice.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.