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?

  • $\begingroup$ "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. $\endgroup$
    – gnasher729
    Mar 31, 2019 at 17:07
  • $\begingroup$ @gnasher729, en.wikipedia.org/wiki/ID3_algorithm $\endgroup$
    – D.W.
    Mar 31, 2019 at 17:17

1 Answer 1


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.


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.