ROCCER: An Algorithm for Rule Learning Based on ROC Analysis

1 Introduction

Classification rule learning can be defined as the process of, given a set of training examples, finding a set of rules that can be used for classification or prediction. Almost all classification rule learning algorithms belong to one of two families, namely separate-and-conquer and divide-and-conquer algorithms. The two families share a number of characteristics, most notably the assumption that the example space contains large continuous regions of constant class membership. The major differences are outlined below.

In the separate-and-conquer family of classification rule learning algorithms [F¨urnkranz, 1999], the search procedure is generally an iterative greedy set-covering algorithm that on each iteration finds the best rule (according to a search criterion) and removes the covered examples. The process is repeated on the remaining examples until all examples have been covered or some stopping criterion has been met. In order to build a classifier, the rules found in each iteration are gathered to form either an ordered rule list (a decision list) or an unordered rule set. In the former case the classification is given by the first rule in the list that fires, while in the latter case the predictions of rules that fire are combined to predict a class.

This approach contrasts with the divide-and-conquer family of learning algorithms [Quinlan, 1993], where a global classifier is built following a top-down strategy by consecutive refinements of a partial theory. The result is generally expressed as a decision tree, which completely divides the instance space into non-overlapping axis-parallel hyperrectangles.

Peter A. Flach

Department of Computer Science University of Bristol Bristol, United Kingdom

Peter.Flach@bristol.ac.uk

As decision tree induction necessarily builds complete disjoint models, in some complex domains with highdimensional feature spaces these models can be quite complex. In such cases, individual rule learning algorithms may be preferable since they are capable of inducing overlapping and simpler rule sets [van den Eijkel, 2003]. However, one of the problems of set-covering rule learning is that rules are found in isolation, although they are used in the context of the others inside the classifier. This issue can pose several problems for a rule learning algorithm. First, from the learning perspective, fewer and fewer examples are available as covering progresses. In latter stages of induction, this may lead to fragmented training sets and rules with insufficient statistical support [Domingos, 1996]. Furthermore, each new rule is constructed in complete ignorance of the examples already covered by the previously induced rules. If a bad rule has been introduced in the rule set, there is no chance of finding a better rule for those examples (there is no backtracking).

In this work we present a new rule learning algorithm named ROCCER, aimed to overcome such problems. The main idea of the algorithm is to construct a convex hull in ROC space. We evaluate ROCCER on a broad set of benchmark domains from the UCI repository [Blake and Merz, 1998] and compare it with other rule induction methods. The paper is organized as follows. In Section 2 we discuss the background related to this work. Section 3 presents our proposed algorithm, and Section 4 contains the experimental evaluation. In Section 5 we make some concluding remarks.

2 Related work

Several approaches have been proposed in the literature to overcome the fragmentation problem. [Liu et al., 1998] decouple the rule generation from the covering step. The basic idea is to use an association rule algorithm to gather all rules that predict the class attribute and also pass a minimum quality criterion into the rule set. Although this approach might overcome some of the problems of the separateand-conquer approach, and its performance was reported to outperform standard rule learning algorithms in some domains, its main drawback is related to the number of generated rules. Often they considerably outnumber the examples, implying serious difficulties from a knowledge discovery point of view, since the understandability and usability of the generated model would decrease and the risk of overfitting would increase. This idea has been extended in the AprioriC and AprioriSD algorithms [Javanoski and Lavraˇc, 2001; Kavˇsek et al., 2003] by adding an additional filtering step to remove some of the redundant rules. However, AprioriC still tends to build large rule sets and AprioriSD has been developed mainly for subgroup discovery.

A different approach is to use weighted covering, which has been independently proposed by [Cohen and Singer, 1999] and [Weiss and Indurkhya, 2000]. Instead of completely removing the examples covered by the best rule on each iteration, their weights are decreased, and in each iteration the covering algorithm concentrates on highly-weighted (i.e., infrequently covered) examples. [Lavraˇc et al., 2004] also discuss the use of weighted covering in a subgroup discovery context. Alternative methods to remove redundant rules are based on pruning [F¨urnkranz and Widmer, 1994; Cohen, 1995].

Some authors propose the use of confidence thresholds for classification. [Gamberger and Lavraˇc, 2000] include only rules with high confidence in the rule set. The classifier then refuses to classify a new instance if none of the rules cover it. [Ferri et al., 2004] extends this idea by retraining a new classifier on the unclassified examples.

3 The ROCCER rule selection algorithm.

Our approach relies on using ROC analysis for selecting rules instead of using a classical covering algorithm. Roughly speaking, a ROC graph is a plot of the fraction of positive examples misclassified - false positive rate (fpr) - on the x axis against the fraction of positive examples correctly classified - true positive rate (tpr) - on the y axis. It is possible to plot in a ROC graph either a single rule, a classifier (formed by a rule set, or not) or even a partial classifier (formed by a subset of a rule set, for instance).

For a threshold-based classifier one can obtain several pairs of points (fpri, tpri) by varying the threshold. If we trace a line connecting those points we obtain a curve in the ROC space that represents the behaviour of the classifier over all possible choices of the respective threshold. In a rule learning context, [F¨urnkranz and Flach, 2005] show that rule learning using a set covering approach can be seen as tracing a curve in ROC space. To see why, assume we have a empty rule list, represented by the point (0,0) in ROC space. Adding a new rule Rj to the rule list implies a shift to the point (fpr j, tpr j), where fpr j and tpr j is the tpr and fpr of the partial rule list (interpreted as a decision list) containing all rules already learnt including Rj. A curve can be traced by plotting all partial rule lists (fpr j, tpr j), for j varying from 0 to the total number n of rules in the final rule list in the order they are learnt. A final default rule that always predicts the positive class can be added at the end, connecting the point (fprn, tprn) to the point (1, 1).

Our approach is based on this observation, and the fact that the points which represent the optimum thresholds lie on the upper convex hull of the ROC curve [Provost and Fawcett, 2001]. Rules come from a external larger set of rules (in our implementation, we use the Apriori association rule learning algorithm, fixing the head of the rules to each of the possible class values, allowing us to deal with multi-class problems) and we perform a selection step based on the ROC curve. The basic idea is to only insert a rule in the rule list if the insertion leads to a point outside the current ROC convex hull (the current ROC convex hull is the upper convex hull of the rules that are already in the rule list). Otherwise the rule is discarded. For a better understanding of how our algorithm works, we first describe it using an example.

Rules are selected separately for each class, and are kept in an ordered rule list. Let's label the class we are selecting rules for positive; the label negative represents the (conjunction of) examples in the other class(es). First, we initialize the rule list with a default rule, Rdefault, which always predicts positive. The current ROC convex hull is formed then by 2 points, (0,0) and (1,1) which means "ignore the default rule (classify everything as negative) or use the default rule (classify everything as positive)". We use fprRi, tprRi to refer to the rule Ri's true and false positive rates, and tpri, fpri to refer to a point i in the ROC curve, representing the corresponding rule list's true and false positive rates. Suppose now we are inserting a new rule R1. As the actual convex hull is formed only by the line segment (0,0)-(1,1), R1 will only be inserted if the point formed by the rule's (fprR1, tprR1) is above the convex hull. Let's say R1 is inserted. The current convex hull is then updated, and contains the points (0,0),(fpr1, tpr1),(1,1), where fpr1 = fprR1 and tpr1 = tprR1. This process is depicted in Figure 1.

Suppose we are now trying to insert a second rule R2. As we have said before, in the standard set-covering approach the learning of a new rule does not take into account the rules already learnt. In our approach, we try to overcome this issue using the ROC graph to analyze interactions among rules. We do this by comparing the rule we are trying to insert with the slopes of each of he line segments in the current convex hull in the ROC graph. In our example, if the slope of the point formed by the origin and (fprR2, tprR2) is above the line from the origin to the point (fpr1, tpr1), we say that R2 "improves in relation to" R1 and insert R2 in the rule list. This is similar to if R2 had been learned before R1 in the set-covering approach. By comparing with the rules which are already in the rule list, our algorithm provides a kind of backtracking. This insertion will, of course, produce changes to the other points in the ROC curve. The first non-trivial point in the ROC curve changes to (fprR2, tprR2). If R1 and R2 do not have any overlap, the second point will be (fprR2 + fprR1, tprR2 + tprR2). If R1 and R2 do have some overlap, however, we should discount the examples covered by both rules to calculate the second point.

If R2 is not inserted at the first iteration, we proceed by comparing with the remaining line segments in the ROC convex hull. Before we compare with the next line segment, we update R2's fpr and tpr by removing the examples covered by R1 (the examples which evaluate to true for R1's antecedent). In fact, we are "interpreting" R2 as ¬R1 ∧R2. If the updated position of R2 is above the line from R1 to Rdefault, R2 is inserted in the rule list after R1. This process is depicted in Figure 2. Otherwise (since no further rules remain) R2 is discarded. The pseudo-code of this algorithm is shown in Algorithm 1.

Algorithm 1: The ROCCER algorithm.

Data: RSin: A (large) rule set for a given class Result: RSout : A (smaller) rule list containing the selected rules RSout = {Rdefault}; foreach Rule ∈ RSin do TryToInsertRule(Rule) endfch return RSout procedure TryToInsertRule(Rule) RuleToCompare = first rule in RSout ; repeat if Rule's (fpr,tpr) is outside convex hull then Insert Rule into RSout before RuleToCompare else /* shift to a new origin */ Remove all the examples from Rule which are covered by RuleToCompare; Actualize Rule's (fpr,tpr); RuleToCompare = next rule in RSout endif until RuleToCompare ̸= Rdefault; if Rule is not inserted then Discard Rule endif

Due to overlapping coverage among rules, this process does not necessarily lead to a convex curve. The insertion of a new rule in the rule list may introduce concavities before or after the point of insertion. If concavities occur after an insertion, the inserted rule covers examples originally covered by subsequent rules, which decreases the latter's precision. In this case, we remove the rules where the concavity occurs. Alternatively, if the concavity occurs before the insertion point, both rules share a region where they misclassify some examples. In this case, it is unreasonable to use the partial rule list including the first rule but excluding the second, because the corresponding ROC point is under the convex hull. Therefore, we construct the disjunction of the two rules and treat it as a single rule.

In our implementation, rules presented to ROCCER are initially ordered, using the Euclidean distance to the point (0,1) in the ROC space. However, due to the possibility to remove a selected rule and the (implicit) backtracking, the order dependence in selecting rules is lower than a decision list in inducing rules. Experiments with another orderings would be an interesting issue for further work, though.

This concludes the description of the training phase. For classification, we also use a ROC-based method. Bayes' theorem states that the odds that a classifier correctly classifies an instance (posterior odds) is given by the likelihood ratio times the odds of the instance being of the predicted class (prior odds). In ROC space, the likelihood ratio can be interpreted as tpr/fpr. Recall that we selected rules separately for each class. Thus, we have a ROC convex hull for each class. To classify a new instance we also consider each class separately, and, for each class, we determine the first rule that fires in the respective ROC convex hull. This rule has an associated (tpr, fpr) in the ROC curve, which yields a likelihood ratio. The posterior odds is then converted back to a probability (for ranking), or we select the class with maximum posterior odds (for classification).

4 Experimental evaluation

In order to empirically evaluate our proposed approach, we performed a experimental evaluation using 16 data sets from UCI [Blake and Merz, 1998]. We used only data sets without missing values, as Apriori (the association rule algorithm we use to generate the rules for subsequent selection by ROCCER) can't handle them. Table 1 summarizes the data sets employed in this study. It shows, for each data set, the number of attributes (#Attrs), the number of examples (#Examples), and percentage of examples in the majority class (%MajClass) - although ROCCER can handle more than two classes, in order to calculate AUC values we restricted our experiments to twoclass problems. For data sets having more than two classes, we chose the class with fewer examples as the positive class, and collapsed the remaining classes as the negative.

ROCCER's results were compared with those obtained by the following rule learning systems:

CN2 This algorithm is a classical implementation of the separate-and-conquer rule learning family. In its first version [Clark and Niblett, 1989] CN2 induces a decision list using entropy as a search heuristic. It has later been modified to incorporate the induction of unordered rule sets and Laplace error correction as evaluation function [Clark and Boswell, 1991].

• Ripper [Cohen, 1995] proposed Ripper in the Incremental Reduced Error Pruning (IREP) [F¨urnkranz and Widmer, 1994] context. It has features such as error-based pruning and an MDL-based heuristic for determining how many rules should be learned.
• Slipper This algorithm is a further improvement of Ripper which uses a weighted set-covering approach [Cohen and Singer, 1999].
• C4.5 [Quinlan, 1993]'s C4.5 is almost a standard in empirical comparison of symbolic learning algorithms. It is a member of divide-and-conquer family. C4.5 uses information gain as quality measure to build a decision tree and a post-pruning step based on error reduction. We can consider each branch in a decision tree as a rule.

Ripper and Slipper were used with -a option to generate rules for both classes. CN2 was used in its two versions, ordered (CN2OR) and unordered (CN2). We also evaluated both pruned (C45) and non-pruned (C45NP) trees induced by C4.5. All other parameters were set to default values. In order to calculate the AUC values we estimated probabilities of each rule using Laplace correction. For the unordered version of CN2, probabilities were estimated using all fired rules. AUC values were estimated using the trapezoidal rule. We used [Borgelt and Kruse, 2002]'s implementation of Apriori to generate the large rule sets used by ROCCER. The parameters were set to 50% of confidence and 1/3 of the percentage of minority class as support. For ROCCER, the probabilities were estimated by the posterior odds (described in Section 3). We also compare with a bagging of all rules generated by Apriori.

We ran the experiments using 10-fold stratified crossvalidation. The experiment is paired, i.e., all inducers were given the same training and test files. The averaged AUC values (and respective standard deviations in brackets) are shown in Table 2. We also perform a two-tailed Dunett multiple comparison with a control procedure 1 using ROCCER as control (the other results against ROCCER). Cells having AUC values statistically better than ROCCER are represented in dark gray while light gray is used to represent cells statistically worse than ROCCER, both with 95% confidence level.

Table 2 shows relatively few statistically significant differences. Comparing against C4.5, ROCCER achieved 4 wins and 1 loss. This is the same score if we compare ROCCER against Ripper. Against Slipper, the results are 5 wins and no losses. A comparison of ROCCER against C4.5 without pruning, CN2 and CN2 ordered yield 2 losses and no wins. We believe these two losses are due to the high degree of class skew in those two datasets (they are the most skewed in our study). In order to allow Apriori to find rules for both classes in these domains, the support parameter used in Apriori is very low. In these cases we have both a small number of rules generated for the minority class and a large number of rules generated for the majority class. Further improvements should be made in ROCCER to cope with such situations (for instance, it would be interesting to introduce different minimum support for each class). Taking into account all the rule learning algorithms, the score is 12 wins and 9 losses (all losses are concentrated in the two skewed domains, though). Comparing with all the generated rules, ROCCER produced 6 wins and no losses. We also compute AUC value on selecting k (the same number as ROCCER)random rules and rules with higher individual AUC values. Due to lack of space results are not shown in this paper, but they are in most of the cases significantly worst and never better than ROCCER. This indicates that ROCCER's selection procedure is responsible for a gain of performance over all the presented rules.

The good results with both versions of CN2, and the relatively poor AUC figures for Ripper and Slipper, are worth noticing, and may be explained by the absence of pruning mechanisms. It has already been reported in the literature that non-pruned trees are better for probability prediction and thus produce higher AUC values [Provost and Domingos, 2003]. It might be expected that a similar phenomenon also would occur with algorithms from the separate-and-conquer family. Ripper and Slipper are - at least conceptually - similar to CN2 but incorporate, respectively, rule pruning and weighted coverage.

Table 3 presents the average size (in number of rules) of the rule sets for each algorithm. Size 0 means that the classifier is formed only by the default rule. The picture here is more clear. Apart from some exceptions, ROCCER produces smaller rule sets than C4.5 without pruning, CN2 (both ordered and unordered), and Slipper. On the other hand, Ripper produced (significantly) smaller rule sets in 7 out of 16 domains, and there were 8 draws and 1 win. A further investigation involving the data sets where most of the algorithms produced smaller rule sets than ROCCER (Breast, Heart, Ionosphere and Kr-vs-kp) might produce some insights for improvements to our approach.

1 Multiple comparison is used to adjust the observed significance level for the fact that multiple comparisons are made. If we use a t-test, and as each comparison has up to 5% Type I error, then the Type I error rate over the entire group can be much higher than 5%.

We conclude from Tables 2 and 3 that ROCCER combines, in a sense, the best of both worlds: it achieves AUC values that are comparable to those of unpruned decision trees and CN2, but without the large number of rules induced by those systems. Finally, Table 4 presents statistics of the individual rules that comprise the rule sets, which demonstrates another advantage of the ROCCER approach. Support ranges from 0 to 100% and is a measure of the relative coverage of each rule. Weighted relative accuracy (WRAcc) ranges from 0 to 0.25 and assesses the significance of a rule, in terms of difference between the observed and expected numbers of true positives. The odds ratio ranges from 0 to ∞ and is a measure of strength of association. It can clearly be seen that the rules selected by ROCCER have considerably higher values for all measures. This means that the rules are more meaningful in isolation, without reference to the other rules in the rule set. Thus, ROCCER successfully overcomes one of the main drawbacks of the set-covering approach.

A final word should be said regarding computational complexity. ROCCER is, of course, computationally more expensive than the other algorithms. In the worst case, the complexity is O(n 2 ), where n is the number of rules used as input. However, on average, the number of iterations is Ω(mn), where m is the number of rules selected by the algorithm. Due to lack of space we will not report runtime statistics for all data sets. For most datasets the runtime ranges from a few seconds to 10 minutes per fold (on a Pentium 4 2.4Ghz machine with 512MB of RAM). For these datasets, the number of rules used as input is up to 1,000. For some domains (Krvs-kp and Satimage) the number of rules generated by Apriori is very high (more than 40,000). The runtime in these cases is on average nearly 1.5 hours per fold.

5 Conclusion

We presented ROCCER, a rule selection algorithm based on ROC analysis. ROCCER operates by selecting rules from a larger set of rules by maintaining a ROC convex hull in the ROC space. Featuers of ROCCER's approach include implicit backtracking and discovery of pairs of related rules. Experimental results demonstrate AUC values that are compatible with the best probability predictors such as unpruned decision trees, achieved with considerably smaller rule sets. The rules that compose the rule sets induced by ROCCER have also higher values of support, weighted relative accuracy and odds ratio, and thus are more meaningful as individual rules.

Acknowledgments

This work is partially supported by the Brazilian Research Concil CAPES (Process no. BEX1340/03-8), and was carried out while the first author was visiting the University of Bristol.