# CN2 algorithm

The CN2 algorithm is a rule induction method for classification, generating an ordered or unordered set of if-then rules from data. It combines the separate-and-conquer approach of AQ with entropy-based search, and was introduced in 1987 by Peter Clark and Tim Niblett.

The CN2 algorithm is a rule induction method used in machine learning for classification tasks. It generates a set of if-then rules from a dataset, where each rule consists of a conjunction of conditions on attribute values and a predicted class. CN2 was introduced in 1987 by Peter Clark and Tim Niblett at the Turing Institute, building on earlier work in [machine-learning](https://www.wikiprompt.org/wiki/machine-learning) and [artificial-intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence). The algorithm is notable for combining the separate-and-conquer search strategy of the AQ family with the information-theoretic evaluation criteria used in decision tree induction, such as entropy. It remains a foundational approach in symbolic rule learning, offering interpretable models that contrast with the opaque nature of [neural-network](https://www.wikiprompt.org/wiki/neural-network) and [deep-learning](https://www.wikiprompt.org/wiki/deep-learning) methods.

The algorithm operates by iteratively searching for the best rule that covers a subset of the training examples, removing those examples, and repeating the process on the remaining data. This separate-and-conquer strategy, also known as covering, distinguishes CN2 from decision tree algorithms that use a divide-and-conquer approach. CN2 can produce either an ordered rule list (decision list) or an unordered set of rules, depending on the variant. The original version generates an ordered list, where rules are applied in sequence and the first matching rule determines the prediction. Later extensions, such as CN2-SD (Subgroup Discovery), adapted the algorithm for discovering interesting subgroups rather than complete classifiers.

## Search and Evaluation

CN2 performs a beam search through the space of rule conditions. Starting with an empty rule, it repeatedly adds conditions that improve the rule's quality, using a beam width parameter to limit the number of candidate rules considered at each step. The search is guided by an evaluation function that measures the quality of a rule. The original CN2 used an information-theoretic measure based on entropy, similar to the gain criterion in ID3. Specifically, the algorithm evaluates rules using the entropy of the class distribution among covered examples, preferring rules that reduce entropy. Later versions introduced the Laplace accuracy estimate to avoid overfitting, especially when dealing with small samples. The Laplace correction adds a pseudo-count to each class, providing a more robust estimate of rule accuracy.

The beam search is greedy in nature, as it does not backtrack, but the beam width allows exploration of multiple promising paths simultaneously. This trade-off between greediness and exploration is a key characteristic of CN2. The search space is defined by the attribute-value pairs present in the data, and conditions are typically of the form `attribute = value` for nominal attributes or `attribute <= value` and `attribute >= value` for numeric attributes, though the original algorithm focused on nominal data.

## Algorithm Variants

Several variants of CN2 have been developed over the years. The most significant is CN2-SD, introduced in the late 1990s by Nada Lavrač and colleagues, which shifts the goal from classification to subgroup discovery. In subgroup discovery, the aim is to find rules that describe interesting population subgroups with unusual class distributions, rather than to build a complete classifier. CN2-SD uses a weighted relative accuracy measure to evaluate rules, balancing rule generality and distributional unusualness. Another variant, CN2-R, incorporates randomization tests to assess the statistical significance of rules, filtering out rules that could have arisen by chance. This helps in producing more reliable and generalizable rule sets.

The unordered variant of CN2 generates a set of rules where each rule is learned independently, and for prediction, all rules are applied and their predictions are combined, often by voting or by selecting the rule with the highest specificity. This approach can be more robust for datasets with overlapping class regions. The choice between ordered and unordered rules depends on the application; ordered lists are simpler and faster, while unordered sets can provide better coverage for rare classes.

## Applications and Impact

CN2 has been applied in various domains, including medical diagnosis, fault detection, and ecological modeling. Its interpretability makes it particularly valuable in fields where understanding the decision process is crucial, such as in healthcare and regulatory compliance. For example, in medical applications, CN2 rules can be expressed as simple conditions like `if blood_pressure > 140 and age > 60 then high_risk`, which clinicians can easily verify. The algorithm has also been used as a benchmark for comparing symbolic and sub-symbolic approaches in [machine-learning](https://www.wikiprompt.org/wiki/machine-learning). While modern methods like [deep-learning](https://www.wikiprompt.org/wiki/deep-learning) often achieve higher accuracy on complex tasks, CN2 remains relevant for problems requiring transparent models or when data is limited.

The algorithm's influence extends to later rule learning systems, such as RIPPER and PART, which adopted similar search and evaluation strategies. CN2's entropy-based evaluation was a precursor to more sophisticated information-theoretic measures used in decision tree induction and feature selection. Its separate-and-conquer framework has been analyzed theoretically, with connections to the PAC-learning framework and to the complexity of rule learning.

## Limitations and Extensions

CN2 has known limitations. It is sensitive to noisy data, as the greedy search can overfit to spurious patterns. The beam search, while more thorough than pure hill-climbing, can still miss optimal rules due to its limited lookahead. The algorithm assumes that attributes are independent, which may not hold in real-world data. Extensions have addressed some of these issues. For instance, incorporating continuous attributes through discretization, either as a preprocessing step or within the search, allows CN2 to handle numeric data. The use of statistical tests, as in CN2-R, mitigates overfitting. More recent work has integrated CN2 with ensemble methods, where multiple rule sets are combined to improve robustness.

In the context of modern [machine-learning](https://www.wikiprompt.org/wiki/machine-learning), CN2 is often contrasted with [neural-network](https://www.wikiprompt.org/wiki/neural-network) approaches. While neural networks can automatically learn complex feature interactions, they require large amounts of data and are difficult to interpret. CN2, on the other hand, produces compact, human-readable rules but may struggle with high-dimensional or highly non-linear problems. This trade-off continues to drive research in hybrid systems that combine symbolic rules with sub-symbolic learning, a topic of interest in the broader field of neuro-symbolic AI.

## Implementation and Software

CN2 is implemented in several machine learning libraries. The Orange data mining suite, developed at the University of Ljubljana, includes a CN2 learner, as does the Weka toolkit. These implementations provide user-friendly interfaces for applying the algorithm to real datasets. The algorithm's simplicity makes it easy to implement in various programming languages, and it is often used as a teaching example in courses on [machine-learning](https://www.wikiprompt.org/wiki/machine-learning) and data mining. The availability of open-source implementations has contributed to its continued use in research and education.

Despite being introduced in the late 1980s, CN2 remains a relevant algorithm in the toolbox of machine learning practitioners. Its focus on interpretability and its efficient search strategy ensure its place in the history of AI, alongside other symbolic methods that predate the current dominance of [deep-learning](https://www.wikiprompt.org/wiki/deep-learning). As of the 2020s, CN2 is still cited in research on rule learning and interpretable AI, and it serves as a baseline for evaluating newer rule induction methods.

---
Source: https://www.wikiprompt.org/wiki/cn2-algorithm
License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/)
Last updated: 2026-09-14T04:24:23.496462+00:00