97 lines
3.0 KiB
Markdown
Executable File
97 lines
3.0 KiB
Markdown
Executable File
# Covering Algorithms
|
|
|
|
- Each class in turn; find set of rules covering all examples
|
|
- At each stage, rule is identified that covers some examples
|
|
- Example is covered if satisfying conditions in the antecedent (LHS) of the rule
|
|
- Consider dataset with 2 predicting numeric attributes, and two class values.
|
|
- 
|
|
|
|
# PRISM: Simple Covering Algorithm
|
|
|
|
- Generates rule by adding tests that maximise probability of desired class
|
|
- Similar to situation in decision trees; problem of selecting attribute to split on
|
|
- Each new test reduces rules coverage
|
|
- Rule becomes more specific as tests are added
|
|
- Search strategy is general-to-specific
|
|
- 
|
|
|
|
## Selecting a Test
|
|
|
|
Goal: Maximise probability of desired class
|
|
|
|
- $t$ = total number of examples covered by rule
|
|
- $p$ = number of positive examples of the class covered by rule
|
|
- $t - p$ = number of errors made by rule
|
|
- => Select test that maximises ratio $p/t$
|
|
Stop Condition: $t-p=0$
|
|
- $p = t$, $p/t=1$
|
|
- Or, set of examples cannot be split further.
|
|
|
|
## Example: Contact Lenses Dataset | Class = Hard
|
|
|
|
### Selecting 1st Test of 1st Rule
|
|
|
|
- Rule to Seek: If ? { then recommendation = Hard }
|
|
|
|
|
|
#### Modified Rule and Coverage
|
|
|
|
- Rule with best test added: If astigmatism = Yes { then recommendation = Hard }
|
|
|
|
|
|
### Selecting 2nd Test of 1st Rule
|
|
|
|
- If astigmatism = Yes and ? { then recommendation = Hard }
|
|
|
|
|
|
|
|
#### Modified Rule and Its Coverage
|
|
|
|
- Rule with best test added: If astigmatism = Yes and tear rate = Normal { then recommendation = Hard }
|
|
|
|
|
|
### Selecting 3rd Test of 1st Rule
|
|
|
|
- If astigmatism = Yes and tear rate = Normal and ? { then recommendation = Hard }
|
|
|
|
- PRISM will use test with highest sample size, therefore using Myope.
|
|
|
|
### 1st Rule for Class = Hard
|
|
|
|
- Final Rule:
|
|
If astigmatism = Yes
|
|
and tear rate = Normal
|
|
and spectacle prescription = Myope
|
|
then recommendation = Hard
|
|
|
|
$p/t = 3/3 = 1$
|
|
|
|
# Pseudo-code for PRISM
|
|
|
|
For each class C
|
|
Init E to set of training examples
|
|
While E contains examples in class C
|
|
Create rule R with empty LHS predicting class C
|
|
Until p/t=1, do
|
|
For each attribute A not mentioned in R, and each value v
|
|
Consider adding condition A=v to LHS of R
|
|
Select A and v to maximise p/t
|
|
Break Ties by choosing largest sample
|
|
Add A=v to R
|
|
Remove examples covered by R from E
|
|
|
|
# Separate and Conquer
|
|
|
|
- PRISM with outer loop removed generates list of rules for one class
|
|
- PRISM with outer loop removed is separate and conquer algorithm
|
|
- Identify useful rule
|
|
- Separate examples covered
|
|
- Conquer remaining examples
|
|
|
|
# Rule Execution
|
|
|
|
- Default Rule
|
|
- If no rules cover example, prediction is the majority class (most frequent in training data)
|
|
- Conflict Resolution Strategy
|
|
- If more than one rule covers an example, select predicted class with highest recurrence in training data
|