ID3 Algorithm Implementation

Information Gain Calculation (ID3)

Example Datasets:

Input Column Names

Input Dataset

Results

How does it work?

The formulas show the calculation of finding the root node using the ID3 algorithm, a popular method for decision tree learning. It uses entropy and information gain to determine the optimal splits for creating a decision tree. Input column names and corresponding data to see step-by-step calculations!

The ID3 algorithm begins with the original set \(S\) as the root node. On each iteration of the algorithm, it iterates through every unused attribute of the set \(S\) and calculates the entropy \(H(S)\) or the information gain \(IG(S)\) of that attribute. It then selects the attribute which has the smallest entropy (or largest information gain) value. The set \(S\) is then split or partitioned by the selected attribute to produce subsets of the data. (For example, a node can be split into child nodes based upon the subsets of the population whose ages are less than 50, between 50 and 100, and greater than 100.) The algorithm continues to recurse on each subset, considering only attributes never selected before.

There are two main formulas in use here, Entropy\((E)\) and Information Gain\((IG)\):

\( E(S) = \displaystyle\sum\limits_{i=1}^n -P_i*log_2P_i \)

where \(P_i\) = probability of choosing attribute \(i\) in column \(P\), and \(n\) is number of attributes in \(P\).

\( IG(P) = E(S) - \displaystyle\sum\limits_{i=1}^n p(S|P)*E(S|P) \)

where \(E(S)\) is the entropy of the column to be predicted (usually last), \(p(S|P)\) is the probability of the attribute P in its column and \(E(S|P)\) is the entropy of the attribute \(P\).

The second term of \(IG(P)\) can also be described as a weighted average of all the unique elements in a column. Explanation with Example