CN2 Induction Algorithm

A CN2 Induction Algorithm is a rule induction algorithm based on a combination of AQ and ID3.

References

1989

 Let E be a set of classified examples. Let SELECTORS be the set of all possible selectors. Procedure CN2(E) Let RULE-LIST be the empty list. Repeat until BEST_CPX is nil or E is empty: Let BEST_CPX be Find-Best_Complex(E). If BEST_CPX is not nil, Then let E' be the examples covered by BEST_CPX. Remove from E the examples E' covered by BEST_CPX. Let C be the most common class of examples in E'. Add the rule 'If BEST_CPX then the class is C' to the end of RULE-LIST. Return RULE-LIST. Procedure Find-Best_Complex(E) Let STAR be the set containing the empty complex. Let BEST_CPX be nil. While STAR is not empty, Specialize all complexes in STAR as follows: Let NEWSTAR be the set {x ∧ y|x ∈ STAR, y ∈ SELECTORS}. Remove all complexes in NEWSTAR that are either in STAR (i.e., the unspecialized ones) or null (e.g., big = y ∈ big = n). For every complex Ci in NEWSTAR: If Ci is statistically significant and better than BEST_CPX by user-defined criteria when tested on E, Then replace the current value of BEST_CPX by Ci. Repeat until size of NEWSTAR ≤ user-defined maximum: Remove the worst complex from NEWSTAR. Let STAR be NEWSTAR. Return BEST_CPX.