7
$\begingroup$

When building a decision tree, suppose that there are two attributes that have the same maximum information gain.

Will there be any difference between choosing any of the two attributes to be a tree node? Or are there any other factors that I have to consider in order to decide which attribute should I choose?

$\endgroup$

4 Answers 4

2
$\begingroup$

You could look ahead at the information gain of the remaining attributes after a split and select based on that. In general though, if you're using information gain as your splitting criterion, it will be the only thing to look at.

$\endgroup$
3
  • $\begingroup$ Beside "information gain" (in the case that we have two best info gain), what should be another criteria? $\endgroup$
    – wannik
    Feb 22, 2012 at 3:05
  • 1
    $\begingroup$ You could use other criteria such as the Akaike information criterion. I don't think that anything should be another criterion though. $\endgroup$ Feb 22, 2012 at 17:55
  • 1
    $\begingroup$ If you were building a random forest, then you would be finding bootstrapped estimates of the information gain. That would give you a robust measure of information. $\endgroup$ Sep 29, 2015 at 19:47
7
$\begingroup$

The answer is simply that the first predictor (as found from left to right in the original data frame) is selected. See this thread for the proof. So, to sort everything out:

Will there be any difference between choosing any of the two attributes to be a tree node?

No, selecting one or the other makes absolutely no difference.

So for text classification, it will check in the alphabetical order.

This is only true to the extent that (the columns of) the data frame of predictors are ordered alphabetically.

You could look ahead at the information gain of the remaining attributes after a split and select based on that.

This is not a bad idea and is doable by hand for a small tree, but that's definitely not what's implemented in CART. First, it would be very expensive: imagine for a big tree, all the combinations that one would have to try. More importantly, this goes against the idea of recursive partitioning where at each step, the best predictor can be determined simply as the one that yields the best partition of the current node. This process is conditional on the previous splits (the current node was created by the previous splits); it's not the other way around. CART is inherently greedy and it was shown that looking ahead did not give significantly better results, see this PhD thesis section 2.5.4.

Can you try both trees, and see which creates a better separation at your terminal nodes and/or builds a tree that fits more closely with the theoretical understanding you have of your data?

Again, with a large number of predictors, the numbers of trees to try would be immense. Further, machine learning is often used when the understanding of the relationship between input and output variables is very limited (otherwise, an explicit model could be specified, see this paper), so making a decision based on theoretical understanding is most of the time not possible. Finally, CART trees are usually the base models of ensembles such as RForest and Boosting, where large numbers of trees are automatically grown, so it is completely impossible to inject any kind of human-understanding into the tree-building process in these cases.

$\endgroup$
1
  • $\begingroup$ I agree with you,when you have same information gain attributes,its better to used other models and croos check the results $\endgroup$
    – alily
    Aug 17, 2016 at 8:34
1
$\begingroup$

The decision tree method is a step-wise approach to model building, so variables entered earlier have a direct impact on which variables are entered later. Can you try both trees, and see which creates a better separation at your terminal nodes and/or builds a tree that fits more closely with the theoretical understanding you have of your data?

You could also see what the validation testing shows after building both trees, and go with the tree that fits all the data best.

$\endgroup$
1
$\begingroup$

I work with the text classification problem, and for the classification I am using decision tree classifiers(ID3, Random forests etc). So I can give you an example that is related to text classification. In classification we are going to deal with the different words as the attributes, and you can reduce the features using information gain threshold and once you have all the reduced features with you, it will follow the procedure that I have mentioned below.

While building the decision tree, it will start with the attribute having the highest information gain, and now there are more than one words/attributes with the same information gain value. So for text classification, it will check in the alphabetical order.

For example: for root node there are two words with highest information gain ("Good" with IG=0.5, and "Awesome" with IG=0.5), "Awesome" will be selected as the root node.

Hope this will help to solve the doubt.

It will be great if you can download the machine learning package called "Weka" and try out the decision tree classifier with your own dataset. As the beautiful thing is, after the classification process it will allow you to see the decision tree created. ID3, Random Tree and Random forest of Weka uses Information gain for splitting of nodes.

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