The CN2 Induction Algorithm

Peter ClarkT. Niblett

article1989Machine-mediated learning1,560 citations

Introduces the CN2 rule induction algorithm, which combines the noise-handling capabilities and efficiency of decision trees with the flexible if-then representation of the AQ algorithm to learn accurate, interpretable classification rules from imperfect data.

Listen

Automating knowledge acquisition for expert systems is critical for building practical diagnostic and classification tools. However, real-world data frequently contain noise and imperfect descriptions. Early rule-induction algorithms suffered from notable drawbacks: decision-tree approaches struggled to output intuitive if-then rules, while traditional rule-based algorithms like AQ sought perfect consistency with training data, leading to severe overfitting and overly complex rule sets. To address this challenge, the article designs and evaluates CN2, a machine learning induction algorithm built to generate simple, accurate, and easily understood ordered if-then rules directly from noisy data.

The article evaluates CN2 by comparing its theoretical time complexity, predictive accuracy, and rule complexity against three benchmark methods: ASSISTANT (a noise-tolerant decision-tree system), AQR (a traditional AQ rule induction system), and a naive Bayesian classifier. The empirical evaluation spans three real-world medical diagnostic datasets—lymphography (148 cases), breast cancer recurrence (286 cases), and primary tumor localization (339 cases)—as well as two synthetic datasets with controlled noise levels ranging from 0% to 100% across 200 examples.

The analysis reveals several core findings. First, CN2 achieved predictive accuracy comparable to decision trees across the medical domains (82% versus 78% in lymphography, 71% versus 68% in breast cancer, and 36% versus 42% in primary tumor). Second, incorporating statistical significance tests enabled CN2 to generate substantially simpler rule sets than AQR, reducing rule complexity by roughly 80% to 95% across the medical tasks without degrading test accuracy. Third, in artificial tests, individual CN2 rules maintained high precision (often 85% to 99% accuracy) even as background noise increased, leaving residual errors to a single default rule at the end of the decision list. Finally, time-complexity analysis proved that CN2 scales linearly with the number of training examples, ensuring tractability on larger datasets, though the baseline Bayesian classifier was consistently the fastest.

These findings demonstrate that rule-learning systems can achieve noise resistance without relying on cumbersome post-processing or complex probabilistic matching. By outputting ordered decision lists, CN2 produces transparent logical rules that domain experts can easily inspect, validate, and use for explanations. This balance reduces the risk and operational cost of maintaining overfitted, brittle expert systems. However, tests at 100% noise revealed a notable limitation: CN2 still generated spurious rules in domains with few attribute values, indicating that its statistical significance threshold is sensitive to attribute characteristics and does not always halt cleanly in pure noise.

Organizations developing classification tools should consider CN2 when human-readable if-then rules are preferred over decision trees. Future work should focus on refining CN2's significance testing heuristic to better adapt to specific domain attributes, as well as exploring hybrid approaches that make probabilistic classifiers more interpretable for expert review.

The Turing Institute classification classification methods concept description CN2 induction algorithm AQ algorithm ASSISTANT algorithm

xaviercucurull/CN2 Clark et al (1989).pdf

Paper: Induction of Decision Trees, J. R. Quinlan (1986). Introduces ID3 and top-down decision-tree induction, establishing the foundational benchmark and search paradigm that CN2 modifies to produce noise-tolerant, ordered rule lists.

Paper: Fast Effective Rule Induction, William W. Cohen (1995). Advances the separate-and-conquer rule induction paradigm introduced in CN2 by incorporating efficient pruning and optimization to scale effectively to large, noisy datasets.
Paper: Very Simple Classification Rules Perform Well on Most Commonly Used Datasets, ROBERT C. HOLTE (1993). Evaluates the performance and complexity of ultra-simple single-attribute classification rules against more expressive decision-tree and rule-based learners like CN2.
Paper: Integrating Classification and Association Rule Mining, Bing Liu et al. (1998). Extends rule-based classification by constructing ordered classifiers directly from association rules to overcome limitations of traditional greedy heuristic induction.
Paper: Stop Explaining Black Box Machine Learning Models for High Stakes Decisions and Use Interpretable Models Instead, Cynthia Rudin (2019). Builds upon the interpretability goals of rule lists like CN2 by arguing for inherently interpretable sparse logical models over post-hoc explanations in high-stakes domains.
Paper: MetaCost: a general method for making classifiers cost-sensitive, Pedro M. Domingos (1999). Applies a cost-sensitive wrapper framework around standard induction algorithms, utilizing rule-based learners to minimize real-world misclassification costs.

Abstract

Systems for inducing concept descriptions from examples are valuable tools for assisting in the task of knowledge acquisition for expert systems. This paper presents a description and empirical evaluation of a new induction system, CN2, designed for the efficient induction of simple, comprehensible production rules in domains where problems of poor description language and/or noise may be present. Implementations of the CN2, ID3, and AQ algorithms are compared on three medical classification tasks.

Topics

classification classification methods concept description expert systems knowledge acquisition rule induction

Keywords

CN2 induction algorithm AQ algorithm ASSISTANT algorithm decision lists decision trees rule generation concept learning search heuristics classification accuracy

1. Introduction
2. CN2 and related algorithms
2.1 ASSISTANT
2.1.1 Concept description and interpretation in ASSISTANT
2.1.2 The ASSISTANT learning algorithm
2.1.3 Heuristic functions in ASSISTANT
2.2 AQR
2.2.1 Concept description and interpretation in AQR
2.2.2 The AQR learning algorithm
2.2.3 Heuristic functions in AQR
2.3 The CN2 algorithm
2.3.1. Relation to ID3 and AQ
2.3.2 Concept description and interpretation in CN2
2.3.3 The CN2 learning algorithm
2.4 A Bayesian classifier
2.4.1 Bayesian concept description and interpretation
2.4.2 The Bayesian learning algorithm
2.4.3 Bayesian heuristics
2.5 The default rule
3. Time complexity of the algorithms
3.1 Time complexity of ASSISTANT
3.2 Time complexity of CN2
3.3 Time complexity of AQR
3.4 Time complexity of the Bayesian classifier
3.5 Summary and actual run times
4. Experiments with the algorithms
4.1 Dependent measures
4.2 Experiments on natural domains
4.2.1 Three medical domains
4.2.2 Results with natural domains
4.3 Experiments on artificial domains
4.3.1 Two artificial domains
4.3.2 Results with artificial domains
5. Discussion
6. Conclusions
Acknowledgements
References

Knowls

Knowl 1 — The CN2 Rule Induction Algorithm
algorithm
The CN2 algorithm induces an ordered list of if-then classification rules (a decision list) from pre-classified training examples. It combines an ID3-like general-to-specific beam search across the space of rule conditions (complexes) with statistical stopping criteria to avoid overfitting in noisy domains. Unlike standard AQ, CN2 does not constrain search to conditions that cover a specific positive seed example or strictly exclude all negative examples.

The algorithm operates in two nested procedures: an outer covering loop (CN2) that extracts one rule at a time and removes covered examples, and an inner beam search (Find-Best-Complex) that searches for the most statistically significant, low-entropy complex.
Input: Training examples $E$ described by attributes, set of all possible selectors $SELECTORS$ , star size limit $s$ (maxstar), significance threshold $\alpha$
Output: Ordered decision list $RULE\text{-}LIST$
Procedure CN2( $E$ ):
     $RULE\text{-}LIST \leftarrow$ empty list
    repeat
         $BEST.CPX \leftarrow$ Find-Best-Complex( $E$ )
        if $BEST.CPX \neq \text{nil}$ then
             $E' \leftarrow$ subset of examples in $E$ covered by $BEST.CPX$
             $E \leftarrow E \setminus E'$
             $C \leftarrow$ most common class of examples in $E'$
            append rule "if $BEST.CPX$ then predict $C$ " to end of $RULE\text{-}LIST$
        end if
    until $BEST.CPX = \text{nil}$ or $E$ is empty
    append default rule "predict most frequent class in original training data" to end of $RULE\text{-}LIST$
    return $RULE\text{-}LIST$
Procedure Find-Best-Complex( $E$ ):
     $STAR \leftarrow \{\text{empty complex}\}$
     $BEST.CPX \leftarrow \text{nil}$
    while $STAR$ is not empty do
         $NEWSTAR \leftarrow \{ x \land y \mid x \in STAR, y \in SELECTORS \}$
        remove from $NEWSTAR$ all complexes that are in $STAR$ (unspecialized) or are null (contain contradictory selectors)
        for each complex $C_i \in NEWSTAR$ do
            if $C_i$ is statistically significant at threshold $\alpha$ and better than $BEST.CPX$ on $E$ (lower entropy) then
                 $BEST.CPX \leftarrow C_i$
            end if
        end for
        if $|NEWSTAR| > s$ then
            sort complexes in $NEWSTAR$ by quality (entropy)
            trim $NEWSTAR$ to keep only the best $s$ complexes
        end if
         $STAR \leftarrow NEWSTAR$
    end while
    return $BEST.CPX$
Knowl 2 — Decision List Representation and Inference in CN2
model/method
CN2 represents induced knowledge as an ordered list of if-then rules, structured as a decision list:

$\text{if } \text{complex}_1 \text{ then predict } \text{class}_1$ $\text{else if } \text{complex}_2 \text{ then predict } \text{class}_2$ $\dots$ $\text{else predict } \text{default class}$

Each condition (a complex) is a conjunction of attribute selectors (e.g., $(\text{Temperature} > 60) \land (\text{Weather} = \text{wet} \lor \text{stormy})$ ). The final fallback rule predicts the overall majority class from the original training set.

Execution semantics follow deterministic, top-down sequential evaluation: when classifying an unseen instance, the rules are evaluated in top-to-bottom order. The predicted class is assigned by the very first rule whose complex is satisfied by the instance. If no induced rule fires, the default rule assigns the training set's majority class. This ordered rule execution eliminates the need for conflict resolution heuristics (such as probabilistic degrees of confirmation) required by unordered rule sets.
Knowl 3 — Complex Quality and Significance Evaluation Functions in CN2
equation
CN2 uses two distinct heuristic functions during beam search to evaluate rule condition candidates (complexes):
1. Complex Quality (Entropy): To evaluate how purely a complex identifies a single class, CN2 calculates Shannon entropy over the distribution of covered examples:
$\text{Entropy} = -\sum_{i=1}^n p_i \log_2(p_i)$

where $n$ is the number of target classes and $p_i$ is the empirical probability of class $i$ among the subset of training examples $E'$ that satisfy the complex. Lower entropy indicates higher purity and is favored by the search.
1. Complex Significance (Likelihood Ratio Statistic): To determine whether an apparent regularity reflects genuine attribute-class correlation rather than random sample variation, CN2 computes the likelihood ratio test statistic against the null hypothesis of random selection:
$2 \sum_{i=1}^n f_i \log\left(\frac{f_i}{e_i}\right)$

where $F = (f_1, \dots, f_n)$ is the observed class frequency distribution of examples satisfying the complex, and $E = (e_1, \dots, e_n)$ is the expected class frequency distribution if the $N = \sum_{i=1}^n f_i$ covered examples were distributed proportionally to the class frequencies across the entire current training set ( $e_i = N \cdot P(\text{class}_i)$ ). This statistic is distributed approximately as $\chi^2$ with $n - 1$ degrees of freedom. A candidate complex is pruned if its significance statistic fails to exceed a user-specified confidence threshold $\alpha$ (e.g., 90%, 95%, or 99%).
Knowl 4 — Time Complexity of the CN2 Specialization Step and Overall Search
theoretical result
For a classification task with $e$ training examples, $a$ binary attributes, and a maximum star/beam size $s$ , the computational complexity of a single specialization step in CN2 is bounded by:

$O(a \cdot s(e + \log(a \cdot s)))$

This bound arises from three substeps:
1. Generating candidate specializations by multiplying $s$ complexes in the star by $2a$ single-selector rules: $O(a \cdot s)$ .
2. Evaluating each generated complex over the training set: $O(s \cdot e \cdot a)$ .
3. Sorting candidate complexes by entropy and trimming the star to size $s$ : $O(a \cdot s \log(a \cdot s))$ .
Consequently, the per-step runtime of CN2 scales linearly with the number of training examples $e$ . Under ideal noise-tolerant conditions where the induced rule set size remains bounded as $e$ increases, the total execution time remains linear in $e$ . In the worst case where CN2 overfits and generates $e$ distinct rules of length $a$ , the total worst-case time complexity is $O(a^2 \cdot e^2 \cdot s)$ .

Knowl 5 — Classification Accuracy and Syntactic Complexity on Medical Benchmarks

data/table

Performance of CN2 (tested at 90%, 95%, and 99% significance thresholds) was evaluated against unpruned ASSISTANT, pruned ASSISTANT, a naive Bayesian classifier, AQR (standard AQ covering without pre/post-pruning), and a majority default rule across three medical diagnostic datasets from the Institute of Oncology in Ljubljana (70% train / 30% test splits averaged over 5 runs; star size $s = 15$ ):

Algorithm	Lymphography		Breast Cancer		Primary Tumor
	Accur.	Comp.	Accur.	Comp.	Accur.	Comp.
Default Rule	56%	1	71%	1	26%	1
Assistant (Unpruned)	79%	41	62%	112	40%	178
Assistant (Pruned)	78%	36	68%	44	42%	52
Bayes	83%	240	65%	540	39%	465
AQR	76%	76	72%	208	35%	562
CN2 (90% Thresh.)	78%	24	70%	28	37%	33
CN2 (95% Thresh.)	81%	22	70%	20	36%	42
CN2 (99% Thresh.)	82%	12	71%	4	36%	19

Complexity is defined as the total number of tree nodes for ASSISTANT, the total number of selectors in the induced rule set for AQR and CN2, the matrix entry count for Bayes, and 1 for the default rule. The data show that increasing CN2's significance threshold to 99% sharply reduces syntactic complexity (e.g., from 24 down to 12 selectors in Lymphography, and 28 down to 4 in Breast Cancer) while maintaining or improving test classification accuracy, achieving competitive predictive accuracy with much simpler rule sets than AQR or unpruned decision trees.

Knowl 6 — Overfitting Mitigation in CN2 Compared to AQR and Decision Trees

empirical result

Comparing training set accuracy against test set accuracy highlights how CN2 and pruned decision trees prevent overfitting to noise compared to strict covering algorithms like AQR:

Algorithm	Lymphography		Breast Cancer		Primary Tumor
	Train	Test	Train	Test	Train	Test
Default Rule	54%	56%	70%	71%	23%	26%
Assistant (Pruned)	98%	78%	85%	68%	53%	42%
Bayes	89%	83%	70%	65%	48%	39%
AQR	100%	76%	100%	72%	75%	35%
CN2 (99% Thresh.)	91%	82%	72%	71%	37%	36%

AQR enforces near-complete training set consistency (achieving 100% training accuracy on Lymphography and Breast Cancer), which severely degrades test set generalization due to noise overfitting. In contrast, CN2 (at a 99% significance threshold) terminates search when candidate complexes lack statistical significance, yielding training accuracies closely aligned with test accuracies (e.g., 72% train vs. 71% test on Breast Cancer; 37% train vs. 36% test on Primary Tumor) and preventing the memorization of sample-specific noise.

Knowl 7 — Noise Degradation and Non-Default Rule Accuracy in Controlled Synthetic Domains

data/table

In controlled synthetic domains containing 12 attributes and 200 examples evenly split between two classes (where target concepts are single conjunctive rules), artificial noise was introduced into the training data by randomizing attribute and class values across varying percentages (0% to 100%). Half of the data was used for training and half for noise-free testing (averaged over 5 runs):

Domain A1 (12 attributes, 2 values per attribute):

Noise	CN2 (99% Threshold)			Assistant (Unpruned)		Assistant (Pruned)
Level	Tot. Acc.	Nondef. Acc.	Comp.	Accur.	Comp.	Accur. Comp.
0%	95%	100%	3	99%	8	99% 8
2%	88%	99%	5	96%	16	98% 11
5%	88%	95%	10	91%	32	95% 16
10%	82%	95%	15	86%	45	91% 24
20%	73%	86%	20	76%	60	84% 27
40%	67%	76%	25	65%	74	76% 23
60%	56%	64%	26	62%	75	67% 23
100%	45%	49%	28	46%	85	43% 12

Domain A2 (12 attributes, 8 values per attribute):

Noise	CN2 (99% Threshold)			Assistant (Unpruned)		Assistant (Pruned)
Level	Tot. Acc.	Nondef. Acc.	Comp.	Accur.	Comp.	Accur. Comp.
0%	93%	98%	8	99%	6	99% 6
2%	83%	99%	10	97%	12	97% 12
5%	86%	94%	13	96%	15	96% 15
10%	80%	98%	10	93%	22	93% 22
20%	73%	88%	15	85%	27	85% 27
40%	68%	82%	5	75%	33	75% 33
60%	63%	90%	4	66%	40	66% 40
100%	50%	58%	1	55%	43	55% 43

In both domains, the 'Nondef. Acc.' (accuracy of CN2 rules excluding cases where the fallback default rule fires) remains high even as noise increases, indicating that individual induced rules capture strong regularities while the default rule handles unresolved cases.

Knowl 8 — Susceptibility of Static Significance Cutoffs in Large Hypothesis Spaces
limitation
When evaluated on pure noise (100% randomized training data), an ideal noise-tolerant learner should induce no rules and output a single default rule (complexity 1). However, CN2's likelihood ratio significance cutoff is susceptible to false-positive regularities when the hypothesis space is large and individual rule coverage is moderately high.

In synthetic Domain A1 (12 binary attributes), CN2 with a 99% threshold induces a complex rule list of size 28 on 100% noisy data rather than converging to complexity 1. Because the search space contains $12 \times 11 \times 10 = 1320$ candidate rules of length 3 and each such rule covers an average of $100 / 2^3 \approx 12.5$ examples, evaluating thousands of rules guarantees that some chance correlations pass the static 99% significance threshold.

In contrast, in Domain A2 (12 attributes with 8 values each), average coverage for length 3 rules drops to $100 / 8^3 \approx 0.2$ examples, preventing spurious rules from passing the significance threshold and allowing CN2 to successfully converge to complexity 1. This demonstrates that fixed statistical significance thresholds fail to account for multiple testing over large hypothesis spaces and need to be adaptive to attribute arity and domain size.

Coverage note — None was omitted; all key contributions including algorithm specifications, heuristics, complexity bounds, benchmark comparisons, noise experiments, and analytical limitations are fully represented.

References

1.Cestnik, B., Kononenko, I., & Bratko, I. (1987). ASSISTANT 86: A knowledge-elicitation tool for sophisticated users. Proceedings of the Second European Working Session on Learning (pp. 31-45). Bled, Yugoslavia: Sigma Press.
2.Chan, P. K. (1988). A critical review of CN2: A polythetic classifier system (Technical Report CS-88-09). Nashville, TN: Vanderbilt University, Department of Computer Science.
3.Iba, W., Wogulis, J., & Langley, P. (1988). Trading off simplicity and coverage in incremental concept learning. Proceedings of the Fifth International Conference on Machine Learning (pp. 73-79). Ann Arbor, MI: Morgan Kaufmann.
4.Jackson, J. (1985). Economics of automatic generation of rules from examples in a chess end-game (Technical Report UIUCDCS-F 85-932). Urbana: University of Illinois, Computer Science Department.
5.Kalbfleish, J. (1979). Probability and statistical inference (Vol. 2). New York: Springer-Verlag.
6.Kononenko, I., Bratko, I., & Roskar, E. (1984). Experiments in automatic learning of medical diagnostic rules (Technical Report). Ljubljana, Yugoslavia: E. Kardelj University, Faculty of Electrical Engineering.
7.Michalski, R. S. (1969). On the quasi-minimal solution of the general covering problem. Proceedings of the Fifth International Symposium on Information Processing (pp. 125-128). Bled, Yugoslavia.
8.Michalski, R. S., & Chilausky, R. (1980). Learning by being told and learning from examples: An experimental comparison of the two methods of knowledge acquisition in the context of developing an expert system for soybean disease diagnosis. International Journal of Policy Analysis and Information Systems, 4, 125-160.
9.Michalski, R. S., & Larson, J. (1983). Incremental generation of $VL_1$ hypotheses: The underlying methodology and the description of the program AQ11 (Technical Report ISG 83-5). Urbana: University of Illinois, Computer Science Department.
10.Michalski, R. S., Mozetic, I., Hong, J., & Lavrac, N. (1986). The multipurpose incremental learning system AQ15 and its testing application to three medical domains. Proceedings of the Fifth National Conference on Artificial Intelligence (pp. 1041-1045). Philadelphia: Morgan Kaufmann.
11.Mowforth, P. (1986). Some applications with inductive expert system shells (TIOP 86-002). Glasgow, Scotland: Turing Institute.
12.Niblett, T. (1987). Constructing decision trees in noisy domains. Proceedings of the Second European Working Session on Learning (pp. 67-78). Bled, Yugoslavia: Sigma Press.
13.Niblett, T., & Bratko, I. (1987). Learning decision rules in noisy domains. In M. A. Bramer (Ed.), Research and development in expert systems (Vol. 3). Cambridge: Cambridge University Press.
14.O'Rorke, P. (1982). A comparative study of inductive learning systems AQ11P and ID3 using a chess end-game test problem (Technical Report ISG 82-2). Urbana: University of Illinois, Computer Science Department.
15.Paterson, A., & Niblett, T. (1982). ACLS manual, Version 1 (Technical Report). Glasgow, Scotland: Intelligent Terminals Limited.
16.Quinlan, J. R. (1983). Learning efficient classification procedures and their application to chess end games. In R. S. Michalski, J. G. Carbonell, & T. M. Mitchell (Eds.), Machine learning: An artificial intelligence approach. Los Altos, CA: Morgan Kaufmann.
17.Quinlan, J. R. (1987a). Simplifying decision trees. International Journal of Man-Machine Studies, 27, 221-234.
18.Quinlan, J. R. (1987b). Generating production rules from decision trees. Proceedings of the Tenth International Joint Conference on Artificial Intelligence (pp. 304-307). Milan, Italy: Morgan Kaufmann.
19.Quinlan, J. R., Compton, P. J., Horn, K. A., & Lazarus, L. (1987). Inductive knowledge acquisition: A case study. Applications of expert systems. Wokingham, England: Addison-Wesley.
20.Rivest, R. L. (1987). Learning decision lists. Machine Learning, 2, 229-246.
21.Wald, A. (1947). Sequential analysis. New York: Wiley.

Citation

MLA

Clark, P., and T. Niblett. “The CN2 Induction Algorithm”. Machine Learning, vol. 3, no. 4, 1989, pp. 261–83, https://doi.org/10.1023/A:1022641700528.

APA

Clark, P., & Niblett, T. (1989). The CN2 Induction Algorithm. Machine Learning, 3(4), 261–283. https://doi.org/10.1023/A:1022641700528

Chicago

Clark, P., and T. Niblett. 1989. “The CN2 Induction Algorithm”. Machine Learning 3 (4): 261–83. https://doi.org/10.1023/A:1022641700528.

Harvard

Clark, P. and Niblett, T. (1989) “The CN2 Induction Algorithm”, Machine Learning, 3(4), pp. 261–283. Available at: https://doi.org/10.1023/A:1022641700528.

Vancouver

1. Clark P, Niblett T (1989) The CN2 Induction Algorithm. Machine Learning 3:261–283

BibTeX

@article{Clark_1989, title={The CN2 Induction Algorithm}, volume={3}, ISSN={1573-0565}, url={http://dx.doi.org/10.1023/A:1022641700528}, DOI={10.1023/a:1022641700528}, number={4}, journal={Machine Learning}, publisher={Springer Science and Business Media LLC}, author={Clark, Peter and Niblett, Tim}, year={1989}, month=Mar, pages={261–283} }

Metadata:Crossref

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

The CN2 Induction Algorithm

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — The CN2 Rule Induction Algorithm

Knowl 2 — Decision List Representation and Inference in CN2

Knowl 3 — Complex Quality and Significance Evaluation Functions in CN2

Knowl 4 — Time Complexity of the CN2 Specialization Step and Overall Search