Rule ordering can be implemented on a rule-by-rule basis or on a class-by-class basis. The difference between these schemes is illustrated in Figure 5.1.
Rule-Based Ordering Scheme This approach orders the individual rules by some rule quality measure. This ordering scheme ensures that every test record is classified by the “best” rule covering it. A potential drawback ofthis scheme is that lower-ranked rules are much harder to interpret because they assume the negation of the rules preceding them. For example, the fourth rule shown in Figure 5.1 for rule-based ordering,
Aquatic Creature : semi ——+ Amphibians,
has the following interpretation: If the vertebrate does not have any feathers or cannot fly, and is cold-blooded and semi-aquatic, then it is an amphibian.
2L2 Chapter 5 Classification: Alternative Techniques
Rule-Based Ordering
(Skin Cover=feathers, Aerial 9r”31u1s=yes) ==> Birds
(Body temperature=warm-blooded, Gives Birth=yes) ==> 1446t”;.
(Body temperature=warm-blooded, Gives Birth=no) =-> Birds
(Aquatic Creature=semi)) ==> 4606;6;”n.
(Skin Cover=scales, Aquatic Creature=no) =-> Reptiles
(Skin Cover=scales, Aquatic gt”u1u1s=yes) ==> Fishes
(Skin Cover=none) ==> Amphibians
Class-Based Ordering
(Skin Cover=feathers, Aerial gte2luvs=yes) ==> Birds
(Body temperature=warm-blooded, Gives Birth=no) ==> Birds
(Body temperature=warm-blooded, Gives Birth=yes) ==> J1l36P41t
(Aquatic Creature=semi)) ==> 4601”;6′”n.
(Skin Cover=none) ==> Amphibians
(Skin Cover=scales, Aquatic gr”s1u1e=no) ==> Reptiles
(Skin Cover=scales, Aquatic gtsslups=yes) ==> Fishes
Figure 5.1. Comparison between rule-based and class-based ordering schemes.
The additional conditions (that the vertebrate does not have any feathers or cannot fly, and is cold-blooded) are due to the fact that the vertebrate does not satisfy the first three rules. If the number of rules is large, interpreting the meaning of the rules residing near the bottom of the list can be a cumbersome task.
Class-Based Ordering Scheme In this approach, rules that belong to the same class appear together in the rule set R. The rules are then collectively sorted on the basis of their class information. The relative ordering among the rules from the same class is not important; as long as one of the rules fires, the class will be assigned to the test record. This makes rule interpretation slightly easier. However, it is possible for a high-quality rule to be overlooked in favor of an inferior rule that happens to predict the higher-ranked class.
Since most of the well-known rule-based classifiers (such as C4.5rules and RIPPER) employ the class-based ordering scheme, the discussion in the re- mainder of this section focuses mainly on this type of ordering scheme.
5.1.3 How to Build a Rule-Based Classifier
To build a rule-based classifier, we need to extract a set of rules that identifies key relationships between the attributes of a data set and the class label.
5 .1 Rule-BasedClassifier 2I3
There are two broad classes of methods for extracting classification rules: (1) direct methods, which extract classification rules directly from data, and (2) indirect methods, which extract classification rules from other classification models, such as decision trees and neural networks.
Direct methods partition the attribute space into smaller subspaces so that all the records that belong to a subspace can be classified using a single classi- fication rule. Indirect methods use the classification rules to provide a succinct description of more complex classification models. Detailed discussions of these methods are presented in Sections 5.1.4 and 5.1.5, respectively.
5.L.4 Direct Methods for Rule Extraction
The sequential covering algorithm is often used to extract rules directly from data. Rules are grown in a greedy fashion based on a certain evaluation measure. The algorithm extracts the rules one class at a time for data sets that contain more than two classes. For the vertebrate classification problem, the sequential covering algorithm may generate rules for classifying birds first, followed by rules for classifying mammals, amphibians, reptiles, and finally, fishes (see Figure 5.1). The criterion for deciding which class should be gen- erated first depends on a number of factors, such as the class prevalence (i.e., fraction of training records that belong to a particular class) or the cost of misclassifyirig records from a given class.
A summary of the sequential covering algorithm is given in Algorithm 5.1. The algorithm starts with an empty decision list, .R. The Learn-One- Rule function is then used to extract the best rule for class y that covers the current set of training records. During rule extraction, all training records for class gr are considered to be positive examples, while those that belong to
Algorithm 5.1 Sequential covering algorithm. t: Let E be the training records and ,4 be the set of attribute-value pairs, {(,4i, u7)}. 2: Let Y, be an ordered set of classes {yt,yz,. . . ,a*}. 3: Let R: { } be the init ial rule l ist. 4: for each class U e Yo – {gr} do 5: while stopping condition is not met do 6: r +- Learn-One-Rule (E, A, y). 7: Remove training records from -E that are covered by r. 8 : Add r to thebo t tomo f t he ru le l i s t : -R – – ‘ RVr . 9: end while
10: end for 11: Insert the default rule, {} + Uk, to the bottom of the rule list R.
2L4 Chapter 5 Classification: Alternative Techniques
other classes are considered to be negative examples. A rule is desirable if it
covers most of the positive examples and none (or very few) of the negative examples. Once such a rule is found, the training records covered by the rule are eliminated. The new rule is added to the bottom of the decision list R. This procedure is repeated until the stopping criterion is met. The algorithm then proceeds to generate rules for the next class.
Figure 5.2 demonstrates how the sequential covering algorithm works for
a data set that contains a collection of positive and negative examples. The rule ,R1, whose coverage is shown in Figure 5.2(b), is extracted first because it covers the largest fraction of positive examples. All the training records covered by .Rl are subsequently removed and the algorithm proceeds to Iook for the next best rule. which is R2.
– : ” ” ” ” ‘ : :++: i++ i :+ – r :
– : – . – . – – . – 1 . – ;
(a)Original Data
(c) Step 2
Figure 5.2. An example of the sequential covering algorithm.
i R l :
-+ +,+
T
(b)Step 1
: R 2
: R 1 i – : . . , . . . . . . . i
-+ *+*
(d) Step 3
Rule-BasedClassifier 2L5
Learn-One-Rule F\rnction
The objective of the Learn-One-Rule function is to extract a classification rule that covers many of the positive examples and none (or very few) of the negative examples in the training set. However, finding an optimal rule is computationally expensive given the exponential size of the search space. The Learn-one-Rule function addresses the exponential search problem by growing the rules in a greedy fashion. It generates an initial rule r and keeps refining the rule until a certain stopping criterion is met. The rule is then pruned to improve its generalization error.
Rule-Growing Strategy There are two common strategies for growing a classification rule: general-to-specific or specific-to-general. Under the general- to-specific strategy, an initial rule r , {} – 3r is created, where the left-hand side is an empty set and the right-hand side contains the target class. The rule has poor quality because it covers all the examples in the training set. New
(b) Specificto-general
Figure 5.3. General{o-specific and specific-to-general rule-growing strategies.
5 . 1
Body Temperature = warm-blooded
Body Temperature = warm-blooded, Has Legs = yes => Mammals
Body Temperature = warm-blooded, – Gives Birth = yes => Mammals _
(a) General-to-specif ic
Body Temperature=warm-blooded, Skin Cover=hair, Gives Birth=yes, Aquatic creature=no, Aerial Creature=no
Has Legs=yes, Hjbernales=no => Mammals
Skin Cover=hair, Gives Birth=yes Aquatic Creature=no, Aerial Creature=no,
Has Legs=yes, Hibernates=no => Mammals
Body Temperature=warm-blooded, Skin Cover=hair, Gives Birth=yes,
Aquatic creature=no, Aeilal Creature=no Has Legs=yes => Mammals
2L6 Chapter 5 Classification: Alternative Techniques
conjuncts are subsequently added to improve the rule’s quality. Figure 5.3(a) shows the general-to-specific rule-growing strategy for the vertebrate classifi- cation problem. The conjunct Body Tenperature=warn-blooded is initially chosen to form the rule antecedent. The algorithm then explores all the possi-
ble candidates and greedily chooses the next conjunct, Gives Birth=yes, to be added into the rule antecedent. This process continues until the stopping criterion is met (e.g., when the added conjunct does not improve the quality of the rule).
