Rule Induction and Instance-Based Learning: A Unified Approach

1 Introduction

Several well-developed approaches to inductive learn­ ing currently exist, among them induction of decision trees [Quinlan, 1993a], rule induction [Clark and Niblett, 1989], and instance-based learning [Aha et al., 1991]. While accuracy in many practical domains is still far from 100%, it is unclear how much, if any, improvement is still possible with current methods. Empirical studies have also shown repeatedly that each approach works best in some, but not all, domains; this has been termed the selective superiority problem [Brodley, 1993]. Ideally, we would like to have an algorithm that in each domain of interest performs as well as the best of the algorithms above, or better. While it is now clearly understood that induction is a "zero-sum game", and thus this goal is unachievable for the set of all mathematically possi­ ble domains [Schaffer, 1994], it may well be possible to produce learners that perform better on a wide variety of real-world domains, at the cost of worse performance in domains that never occur in practice. One way to attempt this is by combining two or more of the basic approaches into an algorithm that will behave as the most appropriate of them in each situation. This line of research may be termed "empirical multi-strategy learn­ ing" [Michalski and Tecuci, 1994]. MCS [Brodley, 1993], KBNGE [Wettschereck, 1994] and ITRULE [Smyth et al. , 1990] are examples of systems of this type.

Two induction paradigms with largely complemen­ tary strengths and weaknesses are rule induction and instance-based learning (IBL). Rule induction systems often succeed in identifying small sets of highly predic­ tive features, and can make effective use of statistical measures to combat noise. However, they can only form axis-parallel frontiers in the instance space, and they have trouble recognizing exceptions, or in general small, low-frequency sections of the space; this is known as the small disjuncts problem [Holte et al., 1989]. Further, their general-to-specific, "separate and conquer" search strategy causes them to suffer from the splintering prob­ lem: as induction progresses, the amount of data left for further learning dwindles rapidly, leading to wrong decisions or insufficient specialization due to lack of ad­ equate statistical support. On the other hand, IBL (also known as nearest-neighbor) methods can form complex, non-axis-parallel frontiers, and are well suited to han­ dling exceptions, but can be very vulnerable to noise and irrelevant features.

This paper describes an approach to induction that attempts to overcome each of these methods' limitations by combining it with the other. The approach is imple­ mented in the RISE system. Unlike many other empir­ ical multi-strategy systems, RISE does not consist of a global procedure calling the different algorithms as sub­ procedures, but rather of a single, simple algorithm that can behave both as a nearest-neighbor classifier and a rule induction system. Hence its being termed a "uni­ fied" approach, instead of a "combined" one; many other unification schemes are of course possible.

The next section presents the RISE algorithm, fol­ lowed by the derivation of an upper bound for its time complexity. An empirical study is then reported, com­ paring RISE and several other systems on 30 domains from the UCI repository, and the results are interpreted. Finally, related work is discussed, and some directions for future research are outlined.

2 The RISE Algorithm

"RISE" stands for "Rule Induction from a ,S.et of Exemplars." This paper describes version 2.0 of the al­ gorithm. The learning and classification procedures will be considered in turn.

2.1 Representation and Search

Each example is a vector of attribute-value pairs, to­ gether with a specification. of the cl~s to which ~t be­ longs; attributes can be etther nommal (symbohc) or numeric. Each rule consists of a conjunction of an­ tecedents and a predicted class. Each antecedent is a condition on a single attribute, and there is at most one antecedent per attribute. Conditions on nominal at­ tributes are equality tests of the form a; = v;, where a; is the attribute and v; is one of its legal values. Cond~tions on numeric attributes take the form of allowable mter­ vals for the attributes, i.e., a; E [v;1, v;2], where Vjt and v·2 are two legal values for a;. Exemplars (i.e., examples u'sed as prototypes for classification) are viewed as. max­ imally specific rules, with conditions on ~II att~tbutes and degenerate (point) intervals for numenc attnbutes. A rule is said to cover an example if the example satis­ fies all of the rule's conditions; a rule is said to win an example if it is the nearest rule to the example according to the distance metric that will be described below.

The RISE algorithm is summarized in Table 1. RISE searches for "good" rules in a specific-to-general fash­ ion starting with a rule set that is the training set of exa~ples itself. RISE looks at each rule in turn, finds the nearest example of the same class that it does not already cover (i.e., that is at a distance greater than zero from it), and attempts to minimally gener~lize t~e ru~e to cover it. The generalization procedure 1s outhned m Table 2. If the change's effect on global accuracy is posi­ tive, it is retained; otherwise it is discarded. Generaliza­ tions are also accepted if they appear to have no effect on accuracy; this reflects a simplicity bias. This pro.ced~ue is repeated until, for each rule, attempted generahzatwn fails. In the worst case, no geJ1eralizations are performed, and the end result is simply a nearest-neighbor classifier using all the training examples as exemplars.

Accuracy is measured using a leave-one-out method­ ology: when attempting to classify an example, the cor­ responding rule is left out, unless it already covers other examples as well. A potential difficulty with this pro­ cedure is that it requires matching all rules (or all but one) with all training examples, and this would entail a high computational cost if it was repeatedly do~e as outlined. Fortunately, at each step only the change m ac­ curacy need~ to be computed. Each example memorizes the distance to its nearest rule and its assigned class. When a rule is generalized, all that is necessary is then to match that single rule against all examples, and check if it wins any that it did not before, and what its effect on these is. Previously misclassified examples that are now correctly classified add to the accuracy, and previously correctly classified examples that are now misclassified subtract from it. If the former are more numerous than the latter, the change in accuracy is positive, and the generalization is accepted.

Input: ES is the training set. Procedure RISE (ES) Let RS beES. Compute Acc(RS). Repeat For each ruleR in RS, Find the nearest example E to R not already covered by it (and of the same class). Let R' = Most..Specific_Generalization(R, E). Let RS' = RS with R replaced by R'. If Acc(RS') ~ Acc(RS) Then Replace RS by RS', If R' is identical to another rule in RS, Then delete R' from RS. Until no increase in Acc(RS) is obtained. Return RS.

Inputs: R = (a1, a2, ... , a A, cR) is a rule, E = (e1 , e2, ... , eA, C£) is an example. a; is either True, x; = r;, or ri,lower ~ Xi ~ ri,upper· Function Most..Specific_Generalization (R, E) For each attribute i, If a; = True then Do nothing. Else if i is symbolic and e; -:f r; then a; = True. Else if e; > r;,upper then r;,upper = e;. Else if e; < ri,lower then ri,lower = e;.

2.2 Classification

At performance time, classification of each test example is performed by finding the nearest rule to it, and assign­ ing the example to the rule's class. The distance mea­ sure used is a combination of Euclidean distance for nu­ meric attributes, and a simplified version of Stanfill and Waltz's value difference metric for symbolic attributes [Stanfill and Waltz, 1986].

Let E = (e1,e2, ... ,eA,cE) be an example with value e; for the ith attribute and class C£. Let R = (a1, a2, ... , aA, cR) be a rule with class CR ~nd cond.ition a; on the ith attribute, where a; = True tf there 1s no condition on i otherwise a; is x; = r; if i is symbolic and a; is ri,lower d x; ~ r;,upper if i is numeric. The distance D..(R, E) between Rand E is then defined as:

where the component distance c5(i) for the ith attribute lS:

SV DM(r;, e;) is the simplified value difference metric, defined as:

where :c; and :Cj are any legal values of the attribute, C is the number of classes, chis the hth class, and P(chl:c;) denotes the probability of Ch conditioned on :c;. If a value :c; dos not occur in training, its distance to all other val­ ues is taken to be 1. The essential idea behind VDM­ type metrics is that two values should be considered sim­ ilar if they make similar class predictions, and dissimi­ lar if their predictions diverge. This has been found to give ~ood results in several domains [Cost and Salzberg, 1993]. Notice that, in particular, SVDM(:c;,:ci) is al­ ways 0 if i = j.

The component distance for numeric attributes is de­ fined as:

Xmax and Xmin being respectively the maximum and minimum observed values for the attribute.

The distance from a missing numeric value to any other is defined as 0. If a symbolic attribute's value is missing, it is assigned the special value "?". This is treated as a legitimate symbolic value, and its SVDM to all other values of the attribute is computed and used. In the present framework, this is a sensible policy: a miss­ ing value is taken to be roughly equivalent to a given possible value if it behaves similarly to it, and inversely if it doesn't.

When two or more rules are equally close to a test example, the rule that was most accurate on the training set wins. So as to not unduly favor more specific rules, the Laplace-corrected accuracy is used [Niblett, 1987]:

where R is any rule, Cis the number of classes, Nwon(R) is the total number or examples won by R, Ncorr(R) is the number of examples among those that R correctly classifies, and C is the number of classes. The effect of the Laplace correction is to make the estimate of a rule's accuracy converge to the "random guess" value of 1/C as the number of examples won by the rule decreases. Thus rules with high apparent accuracy are favored only if they also have high statistical support, i.e., if that apparent accuracy is not simply the result of a small sample.

3 Time Complexity of RISE

This section shows that RISE is a computationally effi­ cient algorithm by deriving an upper bound for its time complexity. Let E be the number of examples in the training set, A the number of attributes, Vs (VN) the av­ erage number of observed values per symbolic {numeric) attribute, R the number of rules, and C the number of classes. Assume for now that all attributes are symbolic. RISE can be divided into two parts: initialization and search. The initialization phase of the algorithm consists of three operations. The first is copying the examples to the rules, and takes O(EA) time. The second is compil­ ing a table of VDM distances, taking O(EA + AV§C) (EA to run through all the examples, for each one noting the correspondence between each attribute's value and the class, and AV§C to sum the results for all classes, for each pair of values of each attribute). The third op­ eration is finding each example's closest rule and com­ puting the initial accuracy of the rule set, which involves matching all rules against all examples. Since there are initially E rules, this takes O(E 2 A) time. The total time necessary for initialization is therefore O{E 2 A+ AV§C).

The search part of the algorithm consists of repeating four steps for each rule (see Table 1): finding its nearest example, generalizing it to cover the example, comparing the altered rule to all examples to see if any are newly won, and {if the change is adopted) comparing the rule to all other rules to check for duplications. These oper­ ations consume respectively O(EA), O(A), O(EA) and O(RA) time, for a total of O(EA + RA). Doing this for all rules thus takes O[R(EA + RA)] time. In RISE each example produces at most one rule, therefore R ~ E and this time is at worst O(E 2 A).

How many "repeat" cycles can the algorithm perform in the worst case? Two answers are possible, depend­ ing on how the stopping criterion is interpreted. If it is applied individually, i .e., generalization of a given rule stops as soon as covering the nearest example produces no improvement, then the "repeat" cycle is performed at worst O{A) times, since each cycle must remove at least one condition, and a rule contains at most A con­ ditions, this being true for each rule. On the other hand, if the stopping criterion is applied globally, i.e. general­ ization of a given rule stops only when no change to any rule produces an improvement, the "repeat" cycle can in theory be performed up to O(EA) times, because in the worst case only one condition of one rule will be dropped in each entire cycle, each time causing some currently­ unprofitable change in another rule to become profitable in the next round. This, however, is extremely unlikely. The two policies were empirically compared, showing no appreciable difference between the two in accuracy or time. (By default, global stopping is used.) Multiplying the values above by the cost of a single cycle yields a total time complexity of O(E 2 A 2 ) or O(E 3 A 2 ) respec­ tively. Since E 2: Vs, and assuming that A 2: C, which is generally the case, the smaller of those values domi­ nates the complexity of the initialization phase, and both therefore constitute upper bounds on the time complex­ ity of the whole algorithm in their respective situations.

Results in [Clark and Niblett, 1989] show that the basic step of the CN2 and AQ rule induction algorithms takes O(EAS) time plus a logarithmic term, where S is a user-set parameter related to the width of the search. This step is embedded in loops that may run up to O(EA) times, yielding a worst-case total time in ex­ cess of O(E 2 A 2 S). RISE's worst-case complexity is thus competitive with that of standard rule induction algo­ rithms.

The introduction of numeric values simply increases the values above by a factor of VN, since the single-step removal of a condition may now be replaced by at most O(VN) steps of expanding the corresponding interval. In practice only a small number of steps may actually be required.

4 Experiments and Results

4.1 Experimental Design

In order to verify if RISE's expected benefits are ob­ served in practice, experiments were carried out on 30 datasets from the UCI repository [Murphy and Aha, 1995]. Half of the domains were first used to select a default version of RISE by 10-fold cross-validation. The domains used in this phase were: breast cancer, credit screening ( crx) , chess endgames (kr-vs-kp ), Pima dia­ betes, hepatitis, iris, labor negotiations, lung cancer, liver disease, contact lenses, lymphography, primary tu­ mor, soybean (small), voting records, and wine. The ver­ sion of RISE thus selected is the one described in previ­ ous sections. RISE was then compared with state-of-the­ art representatives of other approaches on the remaining 15 domains: PEBLS 2.1 for IBL [Cost and Salzberg, 1993], CN2 6.1 for rule induction [Clark and Boswell, 1991], and C4.5 for induction of decision trees [Quin­ lan, 1993a]. PEBLS 2.1's inability to deal with missing values was overcome by grafting onto it an approach sim­ ilar to the one used by RISE, and numeric values were discretized as directed in the manual. C4.5RULES, the version of C4.5 that converts trees to rules, was chosen because rules have been observed to achieve the highest accuracies [Quinlan, 1987], and because they are more directly comparable to RISE. The default classifier, which assigns all test examples to the most frequent class, was also included in the study to provide a baseline.

The default versions of all algorithms were used. This ensures a fair comparison: RISE is tested on domains for which it was not fine-tuned, and its default version is compared with other default versions. (If anything, this procedure is unfavorable to RISE, because the test suite includes domains which were used in the development of the other algorithms, as reported in the references above) .

Each dataset was randomly divided 50 times into a training set containing two-thirds of the examples, and a testing set containing the remainder. To speed the ex­ periments, datasets with more than 1000 examples were first reduced to this size by random selection. Each algorithm was then trained on each of the 50 training sets, and its accuracy on the corresponding testing set recorded.

4.2 Results

Table 3 shows the average accuracy and sample stan­ dard deviation for each algorithm in each domain. The accuracy column for each algorithm is followed by a col­ umn showing the confidence level for the difference in accuracy between RISE and that algorithm, using a one­ tailed paired t test . A dash denotes less than 90% con­ fidence .

These results are more easily understood by summa­ rizing them in a few comparative measures. These are shown in Table 4. The first line shows the number of domains in which RISE achieved higher accuracy than the corresponding system, vs. the number in which the reverse happened. In each case the comparison is highly favorable to RISE. The second line considers only those domains in which the observed difference is significant with at least 95% confidence, and shows that most of the previous "wins" were indeed significant. The third line shows the results of applying a sign test to the val­ ues of line one. This consists of considering the number of wins as a binomial variable, and asking how unlikely the value obtained is (e.g., 13 wins in 15 trials vs. C4.5). This results in a confidence greater than 95% that RISE is a more accurate learner than CN2 and C4.5, if the set of domains used is assumed to be representative of real­ world tasks. The comparison with PEBLS in not con­ clusive (only 85% confidence) . The sign test, however, can be misled by very small, insignificant differences; a more sensitive procedure is the Wilcoxon signed-ranks test [DeGroot, 1986], which also takes into account the relative magnitudes of the differences between each pair of accuracies being compared. This produces confidences greater than 95% for all comparisons, reflecting that the larger, more significant differences in accuracy tend to be in RISE's favor, and inversely for the smaller, more uncertain ones.

The average accuracy across all domains is a measure of questionable significance, but it is often reported, and is also included here. RISE achieves the highest average accuracy. Finally, a comparison of all the algorithms was carried out by, for each domain, assigning 4 points to the most accurate algorithm, 3 to the second most accurate one, and so on. RISE obtains the highest score by a wide margin. This reflects the fact that RISE performs con­ sistently well, i.e., even when it is not the most accurate algorithm, it is almost always the second best one.

Many widely-used domains were not included in this study, because they had previously been used to fine­ tune RISE. As a further check that the results obtained were not a fortuitous consequence of the choice of do­ mains, the same experimental procedure was applied to the "training" domains, and the results merged with the above ones. The percentage of domains in which RISE wins vs. CN2 and C4.5 is now somewhat smaller, and vs. PEBLS it is higher. Overall the differences and confi­ dences obtained are substantially higher than before, re­ flecting the fact that twice as many domains were used. The sign and Wilcoxon tests both yield confidences in RISE's superiority in excess of 99% vs. all algorithms. Thus there is strong evidence that, if the domains used are considered representative, RISE is the most accurate of the algorithms tested.

Another significant observation is that , in approxi­ mately half of the test domains used (and similarly for the training ones), RISE's accuracy exceeds the highest of PEBLS's and CN2's. This shows that a multistrategy learning approach can not only often match the results of the best of its "parent" paradigms, but also achieve new synergies between them.

4.3 Discussion

The results above can be interpreted as follows.

Compared with IBL algorithms, RISE has the cru­ cial advantage of being able to select different sets of relevant features in different sections of the instance space. Several well-known methods for removing irrel­ evant features in nearest-neighbor classifiers exist [Aha and Bankert, 1994], but the decisions they make are very coarse, applying to the whole instance space at once. The same consideration holds for the many feature­ weighting schemes that have been proposed [Mohri and Tanaka, 1994]. Rule induction systems are able to detect that certain features are relevant only in the context of others, and RISE shares this ability: a feature may be dropped in some rules, but not others. Also, the VDM­ type metrics used by PEBLS and other systems are ef­ fective in reducing the influence of irrelevant features, but require numeric attributes to be discretized, losing the ordering information they contain. If a Euclidean­ type distance is used for numeric attributes, irrelevant ones may seriously affect the results. RISE is able to use Euclidean distance for numeric features, and gener­ alize or drop them if they are irrelevant. Additionally, RISE's search strategy is such that it only diverges from a nearest-neighbor classifier if this causes an estimate of accuracy to improve, and thus as long as this estimate is good RISE should be able to not perform worse in general than such a classifier.

Compared with rule induction algorithms (and deci­ sion tree ones, which share many biases with them), RISE has several notable advantages. First, due to the best-match policy it employs for classification, it is able to form complex, non-axis-parallel frontiers in the search space, and is thus at an advantage when these are appro­ priate. Second, because of its specific-to-general search direction, and the Laplace accuracy measure used to choose a winner when several rules cover an example, RISE is better able to deal with exceptions and small disjuncts: they will often be retained when generalizing, because absorbing or expanding them into larger rules would decrease accuracy; and at classification time, they will prevail over those larger rules if their Laplace accu­ racy is higher. Finally, RISE's "conquering without sep­ arating" search strategy avoids some of the difficulties of "separate and conquer" ones: each induction step is eval­ uated with respect to how it affects the accuracy of the rule set as a whole on the entire training set, mitigating the splintering problem.

RISE has some disadvantages. It is on average the slowest of the systems compared , although this is only of any significance in the largest domains (in all others, every algorithm runs in seconds on a Sun 670) . The two slowest domains were hypothyroid and splice junc­ tions, where RISE took respectively 119 minutes and 20 minutes. RISE has not been optimized , however, and several important components of the system are amenable to such optimization. Beyond that , window­ ing and other sampling techniques can be used without expected loss in accuracy [Catlett, 1991] . Also, even though RISE's memory cost is much smaller than that of a simple nearest-neighbor classifier, the rule sets it produces are not as compact as those output by C4.5 or CN2. RISE's greater costs will generally be a price well worth paying for the additional accuracy obtained. However, for domains of very large size, and/or when comprehensibility is paramount, a system like C4.5 will still be the first choice.

5 Related Work

The RISE approach should be seen in the context of previous work in inductive learning. Several algo­ rithms proposed in the literature can be seen as em­ pirical multi-strategy learners, but combining different paradigms from RISE's: decision trees, IBL and linear machines [Brodley, 1993], decision trees and rules [Quin­ lan, 1987], decision trees and perceptrons [Utgoff, 1989], rules and Bayesian classification [Smyth et al., 1990], back-propagation and genetic algorithms [Belew et al. , 1992), etc. Quinlan [Quinlan, 1993b] has successfully combined IBL with trees and other methods, but for the purpose of regression as opposed to classification, per­ forming this combination only at classification time, and in a way that depends critically on the predicted value being continuous.

AQ15 [Michalski et al., 1986] is a rule induction system that employs best-match classification. Its approach was carried further in the FCLS system [Zhang, 1990], which combines rules with exemplars in an attempt to alleviate the small disjuncts problem. Unlike RISE, FCLS em­ ploys different representations for rules and exemplars, and uses a separate-and-conquer strategy similar to that of its AQ ancestors.

Golding and Rosenbloom's Anapron system [Golding and Rosenbloom, 1991] combines case-based and rule­ based reasoning in a name-pronunciation task. It differs substantially from RISE in that it does not learn rules, but rather makes use of a pre-existing knowledge base. It also treats cases and rules separately, and employs a different matching procedure.

A system more similar to RISE is EACH/NGE [Salzberg, 1991], which produces and uses hyperrectan­ gles generalized from specific instances. It differs from RISE in many ways, however: it is applicable only in purely numerical domains, is an incremental algo­ rithm, never drops attributes, uses different heuristics and search strategies, allows only nested hyperrectan­ gles as opposed to arbitrary intersecting ones, always prefers the most specific hyperrectangle, etc. Recently Wettschereck and Dietterich [1995] have carried out a detailed comparison of NGE and k-nearest-neighbor (kNN), and designed an algorithm that combines the two [Wettschereck, 1994], but does not achieve greater accuracy than kNN alone. They found that NGE per­ forms substantially worse than kNN, and that the chief cause of this is NGE's use of overlapping rectangles. The fact that RISE performs better than nearest-neighbor, while NGE performs worse with a representation that is similar in the case of numeric attributes, deserves some attention.

In the cross-validation studies reported above, RISE's tie-breaking policy based on Laplace accuracy was com­ pared with one selecting the most specific rule as in NGE, and found to be clearly superior. This can be under­ stood as follows. In regions of overlap, NGE arbitrar­ ily assigns all examples to the class of the most specific hyperrectangle. In contrast, RISE's learning strategy approximates the optimal decision rule of placing the boundary between two classes at the point where the density of examples from one overtakes that of the other [Duda and Hart, 1973]. This is because a rule is started from each example, and its generalization halts when it would include more examples of other classes than of the example's one. The use of Laplace accuracy then implies that, given similar-sized samples, each rule pre­ vails in areas where the density of examples of its class is greater. RISE's batch-learning approach also avoids the problems that NGE's incremental learning one was observed to suffer from. These factors, and the exper­ imental results reported above, support the conclusion that generalizing instances to rules can indeed produce substantial improvements in accuracy, if done in an ap­ propriate manner.

6 Future Work

A priority area for future research is carrying out lesion studies and experiments in artificial domains to verify whether the interpretation of results in the previous dis­ cussion section is indeed correct. More detailed observa­ tion of RISE's workings is also needed to find out how well and how RISE is dealing with the splintering and small disjuncts problems.

Another important direction for research is extending RISE to make use of domain knowledge, bringing the analytical component into the current multistrategy ap­ proach.

7 Conclusions

This paper presented an approach to inductive learning that attempts to combine the best features of IBL and rule induction. The RISE algorithm searches for rules in a specific-to-general fashion, avoiding some of the pit­ falls of "separate and conquer" methods, and uses a best­ match classification procedure, enabling it to form non­ axis-parallel frontiers in the instance space. At the same time it shares with rule induction methods the ability to find small sets of highly predictive features in a context­ sensitive manner. In experiments on a large number of practical domains, RISE achieved significantly higher ac­ curacies than either of its parent approaches alone, and also compared favorably with a decision-tree algorithm. These results show that multistrategy learning can cre­ ate significant synergies between the methods it com­ bines, and thus produce improved classifiers.

Acknowledgments

This work was partly supported by JNICT /Programa Ciencia and Fulbright scholarships. The author is grate­ ful to Dennis Kibler and Mike Pazzani for many helpful comments and suggestions, to the creators of the CN2, PEBLS and C4.5 systems, and to all the people who pro­ vided the datasets used in the empirical study. Please see the documentation in the UCI Repository for de­ tailed information.