Furnkranz's FINDBESTRULE Algorithm

A Furnkranz's FINDBESTRULE Algorithm is a Rule Induction Algorithm that searches for a rule which to optimize a pre-defined quality criterion.

• Context:
  • It was first developed by Furnkranz (2017).
  • …
• Example(s):
  • Furnkranz (2017) - FINDBESTRULE Algorithm (pseudocode),
  • …
• Counter-Example(s):
  • CN2 Algorithm,
  • FOIL Algorithm,
  • FURIA Algorithm,
  • LEM-based Algorithms,
  • PROGOL Algorithm,
  • RIPPER Algorithm,
  • Rulearner Alogrithm,
  • RULEX Algorithm.
• See: Pattern Mining Algorithm, Decision Tree Induction Algorithm, Inductive Logic Programming, Propositional Rule, Firs-Order Logic Rule.

---

---

References

2017

• (Furnkranz, 2017) ⇒ Johannes Furnkranz (2017). "Rule Learning". In: Sammut & Webb (2017). DOI:10.1007/978-1-4899-7687-1_744
  • QUOTE: FINDBESTRULE is a prototypical algorithm that searches for a rule which optimizes a given quality criterion defined in EVALUATERULE. The value of this heuristic function is the higher the more positive and the less negative examples are covered by the candidate rule. FINDBESTRULE maintains Rules, a sorted list of candidate rules, which is initialized by the procedure INITIALIZERULE. New rules will be inserted in appropriate places (INSERTSORT), so that Rules will always be sorted in decreasing order of the heuristic evaluations of the rules. At each cycle, SELECTCANDIDATES selects a subset of these candidate rules, which are then refined using the refinement operator REFINERULE. Each refinement is evaluated and inserted into the sorted Rules list unless the STOPPINGCRITERION prevents this. If the evaluation of the NewRule is better than the best rule found previously, BestRule is set to NewRule. FILTERRULES selects the subset of the ordered rule list that will be used in subsequent iterations. When all candidate rules have been processed, the best rule will be returned.

procedure FINDBESTRULE (Examples, BestRule)
Input: Examples, a set of positive and negative examples for a class c.
InitRule = INITIALIZERULE(Examples)
InitVal = EVALUATERULE(InitRule)
BestRule = <InitVal,InitRule>
Rules= {BestRule}
while Rules ≠ ∅ do
	Candidates=SELECTCANDIDATES(Rules, Examples)
	Rules = Rules \ Candidates
	for Candidate ∈ Candidates do
		Refinements = REFINERULE(Candidate, Examples)
		for Refinement ∈ Refinements do
			Evaluation=EVALUATERULE(Refinement, Examples)
			if STOPPINGCRITERION (Refinement, Examples)
				then next Refinement
			NewRule = <Evaluation,Refinement>
			Rules = INSERTSORT(NewRule, Rules)
			if NewRule > BestRule
				then BestRule = NewRule
			endfor
		endfor
	Rules = FILTERRULES (Rules, Examples)
endwhile
Output: BestRule

---