ID3 algorithm – decision tree construction

The ID3 algorithm constructs a decision tree from data based on the information gain. In the beginning, we start with the set, S. The data items in the set, S, have various properties, according to which we can partition the set, S. If an attribute, A, has the values {v₁, ..., v_n}, then we partition the set, S, into the sets S₁, ..., S_n, where the set, S_i, is a subset of the set, S, where the elements have the value, v_i, for the attribute, A.

If each element in the set, S, has the attributes A₁, ..., A_m, then we can partition the set, S, according to any of the possible attributes. The ID3 algorithm partitions the set, S, according to the attribute that yields the highest information gain. Now suppose that it has the attribute, A₁. Then, for the set, S, we have the partitions...