I am writing a decision tree trained with the ID3 algorithm from scratch. I wanted to be able to train on and classify continuous data, so I implemented k-means clustering and reduced the range of values of any input training or predicting data.

However, I ran into the problem where an attribute value that was not encountered during training, in a deep node somewhere in the tree, but that exists further up was encountered. All data points with this specific attribute value probably ended up on a different branch of the tree.

So to 'solve' this, whenever an unknown attribute value is encountered for a node, I sent it down a random existing branch.

I get 95.45% accuracy using randomly split 85%-15% training-test data with iris.

Is this an acceptable approach to take or have I gotten something wrong here?

Here's the code: https://github.com/jamalmoir/ml_components/blob/master/ml_components/models/decision_tree.py



Do your leaf nodes return a probability distribution rather than a single class value e.g., the majority class of training instances that arrived at the node? If so, a better approach would be to send the test instance down every child path and average the probability distributions that are returned by the leaves.

Your good score of 95.45% on iris data suggests to me that it's not a very important detail in this example. Try some more challenging datasets and see if it makes a difference.

  • $\begingroup$ My leaf nodes just return a class label... Maybe I could look into probability distributions then. Thanks for the suggestion! I'll take a look at more challenging datasets. Thanks $\endgroup$ – Jamal Moir Feb 23 '17 at 4:53
  • $\begingroup$ It's a good idea to be returning distributions from your decision trees, because if you want to make an ensemble of decision trees, averaging the distributions will give you a more accurate classification than simply voting. $\endgroup$ – timleathart Feb 23 '17 at 20:18
  • $\begingroup$ I see, that's a good point. Thank you. I will definitely work on building probability distributions into my decision trees. $\endgroup$ – Jamal Moir Feb 24 '17 at 4:52

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.