title: ID3 binary tree or non-binary tree?
body: <p>I'm trying to implement ID3 or C4.5 algorithm.</p>
  
  <p>According to ID3 algorithm, the information gain is calculated as follows:</p>
  
  <p><a href="https://i.stack.imgur.com/1JeYu.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/1JeYu.png" alt="enter image description here"></a></p>
  
  <p>For example: training data like this:</p>
  
  <pre><code>credit      age      label   
  normal     young      yes
  normal     old      yes
  bad        old        no
  excellent  middle     yes 
  </code></pre>
  
  <p>The IG of credit should like this: <code>IG(credit) = H(D) - P(credit==normal)H(D|credit==normal) - P(credit==bad)H(D|credit==bad) - P(credit==excellent)H(D|credit==excellent)</code></p>
  
  <p>When I choose the credit as the best feature to split, in the following procedure, I will not consider the attribute "credit" again.</p>
  
  <p>However: I also see some one implemented like this:
  <code>IG(credit=normal) = H(D) - P(credit==normal)H(D|credit==normal) - P(credit ~= normal)H(D|credit ~= normal)</code></p>
  
  <p>When I choose credit == normal as the best feature to split, in the following procedure, I will consider the attribute "credit" again, like credit == "bad".</p>
  
  <p>The resulting tree of different IG calculation procudure, one is non-binary tree, the other is the binary tree.</p>
  
  <p>My question is whether two trees are equivalent? When I do testing on two trees, the results will always be the same? Or one is better than other? Or hard to say which is better, just depends on the data? </p>