How to proceed if a rule-based classification algorithm finds an instance that can be classified two ways? I am training a rule based algorithm (PRISM or CN.2) with n classes (y_1,y_2,..,y_n). All rules in the training RuleSet are in DFN form, like:
IF t_1 OR t_2 OR ... t_m THEN y_i (terms) , where
t_1 == lit_1 AND lit_2 AND ... lit_n (literals)

I believe it is possible to have an instance (example) that can be classified with more than one class when predicting in the test sample based on the RuleSet.  My question thus is:


*

*IF it is possible, How to proceed? (Do a major vote for the different classes?). Could you guys please provide me some links describing this type of "problem"?
 A: I decided to post an answer to my previous own question for those facing the same doubts. According to Ian H. Witten book, algorithms using Rule Based Learning can issue more than one classification for an instance in the test sample. It contrasts with Decision Trees, where all instances are classified/predicted uniquely. On page 115, the author discuss how to proceed when facing these ties.
A: What you are describing is somewhat similar to multiclass classification in Machine Learning. In one framing of the problem, you train a classifier for each class and then when you want to predict the class of a new observation, you make a prediction with each of the classifiers. You then end up in a situation similar to the one you describe.
You should first ask yourself if this really is a problem. If you view the classifier as characterizing a pattern that some set of observations has, then is it really a problem for an observation to have multiple patterns (i.e. belong to multiple groups)?
Assuming that you decide that this is a problem and you really want to decide on one class, what people typically do is use some confidence statistic that is produced by the classifier. Most classifiers produce, in addition to their classification, some kind of score, statistic or probability that quantifies how well the observation fits the class. Then, you simply select the class that has the best score.
If you do not have a confidence score, you could maybe try a simple Bayesian approach. This is not based on any literature, just an idea of mine: Let's say an observation was predicted to belong to classes A and B. You could ask what is the probability of P(actually A | predicted A) vs P(actually B | predicted B). You should be able to estimate all the necessary quantities from your training data.
