0
$\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!

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\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 '16 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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