Are there some samples that ID3 can't classify

Question

I wrote a ID3 program in python and when I test my program on the car evaluation and I find that some samples can't be classified. I think there are situations that some samples can't be classified. For example, suppose two features A and B (there are also other features), and A has three value "low" , "mid", "high", B has two value "small" and "big". First we choose feature B to split the dataset and the corresponding node is "Node B", the left branch of "Node B" has value "small" and at the same time all samples that feature A has value "mid" go to the left branch. Then in the right branch, there are no samples with feature A equal to "mid" and suppose at this branch we use feature A to split (the corresponding node is "Node A" )and it has two branches with value "low" and "high".

when we use this tree to classify samples, suppose there is a sample x that feature A has value "mid" , feature B has value "big", when it comes to "Node B" , it goes the right branch which is the "Node A". As Node A has two branches which has value "low" and "high", the value of feature A of X is "mid", so it will has no branch to go and it will not be classified.

So I'm wondering if the above situation is possible and if so, how to solve the problem and if not so, why.

Thanks!

Answer 1

Since you implemented your own version of ID3, you might have such a problem- It is not clear what was your implementation. By the way, there are plenty of ID3 implementations that you can use.

In many cases the nodes are binary rules functioning as "if... else...". In this case, all samples will be classified.

If your implementation allows nodes with multiple values, such case might arise. Note that even if you cover all samples in your train dataset your test dataset might contain new values. It is usually very domain dependent if such situation is likely. You can cope with that by adding "other" rule to your nodes.

Note that even if you'll get a classification of all samples this way, your classification on the "other rule classified samples" will probably be worse than the regular. You might want to mark them (e.g., providing also a confidence with the prediction) and do some more research on theses cases in case they reduce your overall performance.