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

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.