CN2 Induction Algorithm

(Redirected from CN2)
Jump to: navigation, search

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




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.
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.
Return BEST_CPX.

Table 3: The CN2 induction algorithm.