Furnkranz's FINDBESTRULE Algorithm
(Redirected from 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.
- It was first developed by Furnkranz (2017).
- See: Pattern Mining Algorithm, Decision Tree Induction Algorithm, Inductive Logic Programming, Propositional Rule, Firs-Order Logic Rule.
- (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>|
|while Rules ≠ ∅ do|
|Rules = Rules \ Candidates|
|for Candidate ∈ Candidates do|
|Refinements = REFINERULE(Candidate, Examples)|
|for Refinement ∈ Refinements do|
|if STOPPINGCRITERION (Refinement, Examples)|
|then next Refinement|
|NewRule = <Evaluation,Refinement>|
|Rules = INSERTSORT(NewRule, Rules)|
|if NewRule > BestRule|
|then BestRule = NewRule|
|Rules = FILTERRULES (Rules, Examples)|