Article Preview
TopIntroduction
Rule based algorithms are widely used and accepted to perform classification tasks due to their ease of interpretability and understanding. These classifiers build a model or rule set from training data as a set of high-quality rules, which can be used to predict the class labels of unlabeled instances (Wang & Karypis, 2003). There have been many rule based classification systems studied and proposed in a variety of applications, such as RIPPER (Cohen, 1995), FOIL (Quinlan & Gaetz, 1993), and CPAR (Yin & Han, 2003). However, if the test data used to evaluate the model is not as complete as the training data used to build the model, the classification accuracy suffers, as the model tends to follow the training data too closely. This is problematic since real world data is often incomplete. Thus, it is advantageous to have a rule set or model which is robust and can make accurate predictions when the test data is incomplete. This research explores the notion of adding robustness to rule based classifiers via divisive clustering.
Rule based classifiers are widely used because of the ease of interpretability of the models or set of rules they generate. These classifiers perform exceptionally well on complete data sets, meaning, the data is clean, correct, and does not have missing attribute values. To generate the model or train the classifier, the training process uses attributes and values relative to each other to segregate the data and generate a rule relative to a particular class. This poses a problem with incomplete data as the models produced by traditional rule based classifiers are sensitive to missing attribute values in new/unseen data.
Consider, for example, the data set provided in Table 1 and the resulting ID3 Decision Tree provided in Figure 1. The rules derived from this tree are:
Table 1. ID | Highest Ed | Entry Level | Visa Req | Hired |
1000 | Doctorate | No | US Citizen | Yes |
1001 | Bachelor | Yes | Foreign | No |
1002 | Master | No | Foreign | Yes |
1003 | Master | No | Foreign | No |
1004 | Bachelor | No | Foreign | Yes |
1005 | Bachelor | Yes | US Citizen | No |
1006 | Doctorate | Yes | US Citizen | Yes |
1007 | Master | No | US Citizen | No |
1008 | Master | Yes | US Citizen | No |
1009 | Bachelor | Yes | US Citizen | Yes |