title: Decision tree completeness and unclassified data
body: <p>I made a program that trains a decision tree built on the <strong>ID3</strong> algorithm using an <strong>information gain</strong> function (<strong>Shanon entropy</strong>) for feature selection (split).
  Once I trained a decision tree I tested it to classify unseen data and I realized that some data instances cannot be classified: <strong>there is no path on the tree that classifies the instance</strong>.</p>
  
  <p>An example (this is an illustration example but I encounter the same problem with a larger and more complex data set):</p>
  
  <ul>
  <li>Being <strong>f1</strong> and <strong>f2</strong> the predictor variables (features) and <strong>y</strong> the categorical variable, the values ranges are:
  
  <ul>
  <li><strong>f1</strong>: [<code>a1</code>; <code>a2</code>; <code>a3</code>]</li>
  <li><strong>f2</strong>: [<code>b1</code>; <code>b2</code>; <code>b3</code>]</li>
  <li><strong>y</strong> : [<code>y1</code>; <code>y2</code>; <code>y3</code>]</li>
  </ul></li>
  <li><p>Training data:</p>
  
  <pre><code>("a1", "b1", "y1");
  ("a1", "b2", "y2");
  ("a2", "b3", "y3");
  ("a3", "b3", "y1");
  </code></pre></li>
  <li><p>Trained tree:</p>
  
  <pre><code>     [f2] 
      / |  \ 
    b1  b2  b3 
    /    |   \ 
   y1   y2   [f1] 
             /  \ 
            a2   a3 
           /      \ 
          y3       y1 
  </code></pre></li>
  </ul>
  
  <p>The instance <code>("a1", "b3")</code> cannot be classified with the given tree.
  Several questions came up to me:</p>
  
  <ol>
  <li>Does this situation have a name? <em>tree incompleteness</em> or something like that?</li>
  <li>Is there a way to know if a decision tree will cover all combinations of unknown instances (all features values combinations)?</li>
  <li>Does the reason of this <em>"incompleteness"</em> lie on the topology of the data set or on the algorithm used to train the decision tree (<em>ID3</em> in this case) (or other)?</li>
  <li>Is there a method to classify these <em>unclassifiable</em> instances with the given decision tree? or one must use another tool (random forest, neural networks...)?</li>
  </ol>