# How to calculate information gain in ID3?

I am trying to implement a decision tree classifier using ID3 algorithm. According to Aritificial Intelligence - A Modern Approach, information gain of attribute A is given by:

Gain(A) = B(p/p+n) - Remainder(A)

where B is the entropy of a Boolean random variable and p and n are the number of positive and negative examples in the training set.

My question is:

do p and n always refer to examples in the full dataset, or the remaining examples in current partition of the set?

If the former applied, the value of B would remain fixed throughout the training procedure. Is this correct?

• "ID3 is a metadata container most often used in conjunction with the MP3 audio file format. It allows information such as the title, artist, album, track number, and other information about the file to be stored in the file itself". I'm confused here. Mar 31, 2019 at 17:07
• @gnasher729, en.wikipedia.org/wiki/ID3_algorithm
– D.W.
Mar 31, 2019 at 17:17

## 1 Answer

It's important to use the current partition. See, e.g., the pseudocode in Wikipedia: https://en.wikipedia.org/wiki/ID3_algorithm#Pseudocode

Typically, this is implemented as a recursive algorithm. When you recurse, you don't recurse on the entire training set; you recurse on the subset of examples that reach the tree node you're trying to build.