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: [
- f2: [
- y : [
- f1: [
("a1", "b1", "y1"); ("a1", "b2", "y2"); ("a2", "b3", "y3"); ("a3", "b3", "y1");
[f2] / | \ b1 b2 b3 / | \ y1 y2 [f1] / \ a2 a3 / \ y3 y1
("a1", "b3") cannot be classified with the given tree.
Several questions came up to me:
- Does this situation have a name? tree incompleteness or something like that?
- Is there a way to know if a decision tree will cover all combinations of unknown instances (all features values combinations)?
- 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)?
- Is there a method to classify these unclassifiable instances with the given decision tree? or one must use another tool (random forest, neural networks...)?