# Decision tree completeness and unclassified data

I made a program that trains a decision tree built on the ID3 algorithm using an information gain function (Shanon entropy) 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: there is no path on the tree that classifies the instance.

An example (this is an illustration example but I encounter the same problem with a larger and more complex data set):

• Being f1 and f2 the predictor variables (features) and y the categorical variable, the values ranges are:
• f1: [a1; a2; a3]
• f2: [b1; b2; b3]
• y : [y1; y2; y3]
• Training data:

("a1", "b1", "y1");
("a1", "b2", "y2");
("a2", "b3", "y3");
("a3", "b3", "y1");

• Trained tree:

     [f2]
/ |  \
b1  b2  b3
/    |   \
y1   y2   [f1]
/  \
a2   a3
/      \
y3       y1


The instance ("a1", "b3") cannot be classified with the given tree. Several questions came up to me:

1. Does this situation have a name? tree incompleteness or something like that?
2. Is there a way to know if a decision tree will cover all combinations of unknown instances (all features values combinations)?
3. Does the reason of this "incompleteness" lie on the topology of the data set or on the algorithm used to train the decision tree (ID3 in this case) (or other)?
4. Is there a method to classify these unclassifiable instances with the given decision tree? or one must use another tool (random forest, neural networks...)?
• You can find an answer here (cf. comments too). – polkduran Mar 22 '16 at 11:15