Rule-based Classification

• Results easy to understand
  • For domain in which we work close to domain experts
• Rules of the type
  • If \(\langle att_1 = val_1 \& att_5 = val_5 \rangle\) then \(class_j\)

Splitting vs. Covering

• Decision trees
  • Based in splitting
• Splitting
  • Divide the training set in subsets
  • Select an attribute with a heuristic
  • Consider all classes in the partition
  • Add attributes to the tree trying to maximize the separation among classes

Splitting vs. Covering

• Rule-based learning
  • Based in covering
• Covering
  • Find conditions (attribute-value pairs)
    • Cover the highest # of examples of one class
    • Cover the least # of examples of the rest of the classes
    • Considers covering only one class (at a time)

Splitting vs. Covering

• Basic idea
  • Add tests to each rule that is being constructed
    • Trying to maximize coverage, minimizing errors
• Rules
  • Can express disjunctions easier than with trees
  • Extracting rules from trees usually produces more complex rules than necessary
  • Trees have something known as replicated subtree problem
    • Subtrees are repeated in different parts of the tree

Splitting vs. Covering

Decision Lists

• Usually, we generate decision lists
  • Rules evaluated with certain order
• Evaluation becomes easier but modularity decreases
• If we allow evaluating rules independently of the order
  • Can be more than one prediction for a single example
  • More difficult producing only one result

Splitting vs. Covering

• Rules
  • Construct trees from rules
    • Non-trivial
    • Usually produces incomplete trees
  • Advantage of rules versus trees
    • Usually represent “parts” of knowledge that are relatively independent

1R

• 1R is a very simple system, equivalent to a decision stump or decision tree with a single level
  • Constructs rules that test a single attribute-value pair
  • Tries all attribute-value pairs
  • Selects the one with the least number of errors
  • Ties are broken arbitrarily

1R

1R

• We get the following rules
  • If \(sky = sunny\) then \(Class = N\) (covers 5, has 2 errors)
  • If \(sky = overcast\) then \(Class = P\) (covers 4, has 0 errors)
  • If \(Sky = rainy\) then \(Class = P\) (Covers 5, has 2 errors)

1R

• Missing values are treated as a new value
• For continuous values we make a simple division
  • Sort attributes and compare with the class attribute
  • Suggest points of partition in each place in which the class changes
  • If there are two different classes for the same value
    • Move the partition point to an intermediate point with the following value (up or down) depending on where the majority class is
  • More serious problem
    • The algorithm has a tendency to construct rules for each partition
    • Perfect classification
    • With low future prediction
  • How we solve the problem
    • We require a minimum number of examples of the majority class in each partition
  • If there are adjacent classes with the same majority class
    • We put them together

1R

• We take the intermediate points
  • \(64.5, 66.5, 70.5, 72, 77.5, 80.5, 84\)
• Considering examples of different class, we move the frontier from 72 to 73.5

1R

• If we take at least \(3\) elements per partition

• If we put together classes with the same majority class

1R

• We get a rule of the type
  • If \(Temperature \leq 77.5\) then \(Class = P\) (covers 10, has 3 errors)
  • If \(Temperature > 77.5\) then \(Class = N\) (covers 4, has 2 errors)

• In the second rule we make a random selection because there is a tie

1R Algorithm

PRISM

• PRISM is a basic rule-based algorithm
  • Assumes no-noise in the data

PRISM Algorithm

PRISM

• Given t the total number of examples that comply with the condition (attribue-value)
• Given p the number of positive examples (or class in turn) covered by the rule
  • PRISM adds conditions to rules that maximize the relation \(p/t\)
    • Relation between pos examples covered and total number of examples covered to be higher

\[\frac{p}{t} = \frac{positive-covered}{total-covered}\]

PRISM

• The algorithm eliminates examples that the rule covers
  • The constructed rules have to be interpreted in order
    • New rules are added to cover remaining cases
  • Rules that depend in the order for its interpretation
    • Decision lists
  • Rules that don’t depend on order are more modular but
    • May produce several classifications
    • May not predict anything
    • With several classifications we may select the rule that covers more examples
    • If there is no classification, we choose the majority class
  • Ordered rules in general are produced faster because the number of examples to consider is reduced with each rule

PRISM Example

PRISM Example

• We start with P
  • W construct all possible combinations of pairs attribute-value and evaluate their prediction over class P
  • If \(A_1 = 1\) Then \(Class = P\), \(4/5\)
  • If \(A_1 = 0\) Then \(Class = P\), \(1/3\)
  • If \(A_2 = x\) Then \(Class = P\), \(1/4\)
  • If \(A_2 = y\) Then \(Class = P\), \(4/4\)
  • If \(A_3 = Triangle\) Then \(Class = P\), \(2/3\)
  • If \(A_3 = Circle\) Then \(Class = P\), \(2/3\)
  • If \(A_3 = Square\) Then \(Class = P\), \(1/2\)
  • If \(A_4 = a\) Then \(Class = P\), \(4/5\)
  • If \(A_4 = b\) Then \(Class = P\), \(1/3\)

PRISM Example

• There is a perfect rule (If \(A_2 = y\) Then \(Class = P\))
  • We choose it and eliminate the covered examples

PRISM Example

PRISM Example

• We repeat the process with the remaining examples
  • If \(A_1 = 1\) Then \(Class = P\), \(1/2\)
  • If \(A_1 = 0\) Then \(Class = P\), \(0/2\)
  • If \(A_2 = x\) Then \(Class = P\), \(1/4\)
  • If \(A_3 = Triangle\) Then \(Class = P\), \(1/2\)
  • If \(A_3 = Circle\) Then \(Class = P\), \(0/1\)
  • If \(A_3 = Square\) Then \(Class = P\), \(0/1\)
  • If \(A_4 = a\) Then \(Class = P\), \(1/2\)
  • If \(A_4 = b\) Then \(Class = P\), \(0/2\)

PRISM Example

• We have three ties of 1/2 as maximum value
• We take one of them (randomly) and construct all the possible rules by adding possible attribute-value pairs
  • If \(A_1 = 1\) \(\&\) \(A_2 = x\) Then \(Class = P\), \(1/2\)
  • If \(A_1 = 1\) \(\&\) \(A_3 = Triangle\) Then \(Class = P\), \(1/1\)
  • If \(A_1 = 1\) \(\&\) \(A_3 = Circle\) Then \(Class = P\), \(0/0\)
  • If \(A_1 = 1\) \(\&\) \(A_3 = Square\) Then \(Class = P\), \(0/1\)
  • If \(A_1 = 1\) \(\&\) \(A_4 = a\) Then \(Class = P\), \(1/1\)
  • If \(A_1 = 1\) \(\&\) \(A_4 = b\) Then \(Class = P\), \(0/1\)

PRISM Example

• Again, we have ties, we take the first rule
• The rules for class P are:
  • If \(A_2 = y\) Then \(Class = P\)
  • If \(A_1 = 1\) \(\&\) \(A_3 = Triangle\) Then \(Class = P\)
• We repeat the same process for the other classes
• For class N, a possible set of rules is:
  • If \(A_2 = x\) \(\&\) \(A_1 = 0\) Then \(Class = N\)
  • If \(A_2 = x\) \(\&\) \(A_3 = Square\) Then \(Class = N\)

Other Decision Rule Learning Algorithms

• AQ
• CN2

AQ

• AQ was one of the first rules systems
  • Originally developed by Michalski (79)
  • Reimplemented and enhanced by other authors
    • AQ11, and AQ15
  • Its output is a set of classification rules of the type “if \(\dots\) then \(\dots\)”

AQ

• Main idea of AQ
  • Randomly select a seed example
  • Identify the closest example of another class
  • Especialize (add attribute-value conditions) to the current rule
    • So that it doesn’t cover that negative example
    • Try to cover the highest number of positive examples

AQ

• Several alternatives of rules are explored (beam-search)
• Some of heuristics used to select the best rule
  • Sum of positive covered pos and neg excluded (in a tie, prefer the shortest one)
  • Sum the number of examples correctly classified divided by the total number of covered examples
  • Maximizes the number of pos examples covered
• Main disadvantage
  • Sensible to noisy examples (i.e. if the seed has erroneous information)

CN2

• CN2 (Clark, Niblett, 88)
  • Work with data with noise
  • Avoid the overfitting found in systems such as AQ
• Main contribution
  • Eliminate the dependency of an especific example during the search process
  • It is the base of many current rule-based algorithms

CN2

• In CN2
  • We can especify don’t-care values
    • \(Weather = "?"\)
  • Unknown values
  • Keeps working with a beam search
  • Original heuristic based on entropy
    • \(Entropy= - \sum p_i log_2 (p_i)\)
    • \(p_i\) is the classes distribution of the coverage of each rule

CN2

• Selects the rule with the lowest entropy
  • The one that covers many examples of one class and a few of the other classes
• Uses a significance measure for selecting rules
  • Uses a threshold for the significance measure
    • Below thsi level, rules are rejected

Alternative Measures for Selection

• The simplest is the relative frequency of the positive covered examples
  • Has problems with small samples
  • \(m(R) = \frac{p}{t} = \frac{p}{p+n}\)
  • \(t =\) total number of examples covered by the rule \(= p + n\)
  • \(p =\) total number of positive examples covered by the rule

Alternative Measures for Selection

• Laplacian estimator (CN2)
  • Assumes a uniform distribution of the \(k\) classes, (\(k = 2\))
  • \(m(R) = \frac{p+1}{p+n+k}\)

Alternative Measures for Selection

• Information gain \[\log_2 \frac{p}{p+n} - \log_2 \frac{P}{P+N}\]
• \(P\) and \(N\) are the examples covered before adding the new test

Alternative Measures for Selection

• Weighted relative accuracy

\[wra = \frac{p+n}{P+N} (\frac{p}{p+n} - \frac{P}{P+N})\]

Missing and Numerical Values

• Missing values in a Set-Covering algorithm
  • Ignore them (as if they didn’t appear in any condition)
  • Algorithms that learn decision lists have an advantage
    • Examples that appear to be difficult at the beginning are left to the end and can be solved
      • In general, in an easier way
• Numerical attributes can be treated in the same way than with decision trees

Pruning

• Pruning in the way to evaluate a rule
  • Consider the probability that a random rule gives equal or worse results than the rule being evaluated
    • Based in the improvement of the pos covered
• Idea
  • Generate rules that cover only pos examples
  • Probably these rules are over-especialized
  • Eliminate the last term added and verify if the rule is better than the previous one
  • We repeat the process until there are no improvements

Rule Pruning Algorithm

Rule Pruning Algorithm

• This algorithm doesn’t guarantee finding the best rules because of 3 main reasons
  • The algorithm to construct the rules, doesn’t necessarily produces the best rules to be reduced
  • The reduction of rules starts with the last condition, and that is not necessarily the best order to follow
  • The reduction of rules finishes when the estimated value changes, which doesn’t guarantee that keeping prunning might improve the estimated value again
• However, the procedure is good and fast

More on Pruning

• See the Reduced Error Pruning with Significance Tests and the Incremental Reduced Error Pruning papers

RIPPER

• RIPPER uses several measures and ideas at the same time
  • A set of examples is separated to decide on rule pruning
  • Information gain used to grow the rules
  • Uses the IREP measure to prune rules
  • Measure based on MDL as stop criterion for the global set of rules

RIPPER

• When building an initial set of rules it tries to optimize it
  • Takes each rule \(R_i\) from the total set of rules in turn
  • Grows a new rule and prunes it, pruning to reduce error in the entire dataset (the replacement rule)
  • Grows another rule from the beginning but by adding restrictions greedily
• At the end
  • It keeps the original rule, the replacement, or the revision rule
  • The selection is done by using the MDL principle

Building Rules from Trees

• It’s possible to do it directly
  • Rules have a tendency to be more complex than necessary
• Can use rules pruning techniques

Building Rules from Trees

• Combines the covering strategy with splitting
  • To construct a rule we construct a pruned tree (splitting)
  • The leaf with best coverage is transformed into a rule
  • Removes the examples covered by that rule (covering)
  • Repeats the process
  • Instead of constructing the whole tree, partial trees are built, leafs with the best entropy measure are expanded
  • Bias to produce simple sets of rules but with good accuracy

Ripple-down Rules

• Construct first rules that cover the highest number of cases
  • Those are later refined with exceptions
• It takes the majority class first
• Everything that doesn’t comply is taken as an exception to it
• Looks for the best rule (the one covering more cases) of another class and is added as an exception
• This divides again the data into those examples that comply with the new condition and those that don’t comply with it
• From those that don’t comply, again, we look for the best rule of another class and add it as an exception
• We continue with this process until all cases are covered

Ripple-down Rules

Ripple-down Rules

• Advantages of these rules
  • Most of the examples are covered by high level rules
  • Low level rules actually represent the exceptions

Rules that Consider Relations

• Domain of geometric objects
  • If \(width \geq 3.5\) and \(weight < 7\) then lying
  • If \(height \geq 3.5\) then \(standing\)
• If we see several examples in this domain
  • We notice that blocks of the class “standing” have higher height values than width values
  • It is possible to generate the rules
    • If \(width > height\) then \(lying\)
    • If \(height > width\) then \(standing\)
  • The particular values of width and height are not important any more, only the result of their comparison
• This type of rules is known as relational
  • Express relations between attributes
  • Instead of refering to facts about an attribute as in propositional rules

Rules that Consider Relations

• Other relational domain is the geometric figures domain
  • Represent a house as a triangle over a square
  • The shape of an object is represented with an attribute

Rules that Consider Relations

Rules that Consider Relations

• Latter we will learn how to work with relational domains
  • Graph-based Learning
  • Inductive Logic Programming