Sequential Covering

The idea in a sequential covering algorithm is to learn one rule, remove the data it covers, then repeat.



;Examples is the set of examples;

; e.g.

; 1- Wind(d1)=Strong, Humdity(d1)=Low, Outlook(d1)=Sunny, PlayTennis(d1)=No

; 2- Wind(d2)=Weak, Humdity(d2)=Med, Outlook(d2)=Sunny, PlayTennis(d2)=Yes

; 3- Wind(d3)=Med, Humdity(d3)=Med, Outlook(d3)=Rain, PlayTennis(d3)=No

;Target_attribute is the one wish to learn.

; e.g. PlayTennis(x)

;Attributes is the set of all possible attributes.

; e.g. Wind(x), Humidity(x), Outlook(x)

; Threshold is the desired performance.

;


Sequential_covering (Target_attribute, Attributes, Examples, Threshold) :

  Learned_rules = {}

  Rule = Learn-One-Rule(Target_attribute, Attributes, Examples)



  while Performance(Rule, Examples) > Threshold :

    Learned_rules = Learned_rules + Rule

    Examples = Examples - {examples correctly classified by Rule}

    Rule = Learn-One-Rule(Target_attribute, Attributes, Examples)



  Learned_rules = sort Learned_rules according to performance over Examples

  return Learned_rules

We require Learn-One-Rule to have high (perfect?) accuracy but not necessarily high coverage (i.e., when it makes a prediction it should be true).
Since it performs a greedy search it is not guaranteed to find the best or smallest set of rules that cover the training examples.