[Solved]: In ID3 algorithm, which attribute to choose if information gains are equal?

Problem Detail: 

In the ID3 algorithm for building a decision tree, you pick which attribute to branch off on by calculating the information gain. What happens if the calculated information gain is equal for two different attributes? Can you choose either attribute as the new branch?

Asked By : badjr

Answered By : D.W.

Yes. As @Aaron says, it's fine to choose an attribute arbitrarily.

Keep in mind that choosing the attribute with the highest information gain is just a heuristic. It's a local greedy choice. There is no guarantee that making the local greedy choice at each level will necessarily give you a global optimum (i.e., the best possible decision tree); indeed, it might not do so. Instead, it is a heuristic that empirically seems to work pretty well in practice. Resolving ties arbitrarily is in line with that heuristic. There are already no guarantees when using this heuristic, so you're not giving up any theoretical guarantees in this way. The primary focus of this heuristic is to make it efficient to build a decision tree (so you don't have to try all exponentially possible decision trees); resolving ties arbitrarily is in keeping with that focus.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30303