CN2算法是一种用于机器学习分类任务的规则归纳方法。它从数据集中生成一组if-then规则，其中每条规则由属性值条件的合取和一个预测类别组成。CN2由Peter Clark和Tim Niblett于1987年在图灵研究所提出，建立在早期Machine learning和Artificial intelligence工作的基础上。该算法以结合AQ家族的分离-征服搜索策略与决策树归纳中使用的信息论评估标准（如熵）而著称。它仍然是符号规则学习中的基础方法，提供可解释的模型，与Neural network和Deep learning方法的不透明性形成对比。
该算法通过迭代搜索覆盖训练示例子集的最佳规则，移除这些示例，并对剩余数据重复该过程来运行。这种分离-征服策略，也称为覆盖，使CN2区别于使用分治方法的决策树算法。CN2可以生成有序规则列表（决策列表）或无序规则集，具体取决于变体。原始版本生成有序列表，其中规则按顺序应用，第一个匹配的规则决定预测。后来的扩展，如CN2-SD（子群发现），将该算法调整为发现有趣的子群而非完整分类器。
搜索与评估
CN2在规则条件空间中进行束搜索。从空规则开始，它反复添加改善规则质量的条件，使用束宽参数限制每一步考虑的候选规则数量。搜索由评估函数引导，该函数衡量规则的质量。原始CN2使用基于熵的信息论度量，类似于ID3中的增益标准。具体来说，算法使用覆盖示例中类别分布的熵来评估规则，偏好降低熵的规则。后来的版本引入了拉普拉斯准确率估计，以避免过拟合，尤其是在处理小样本时。拉普拉斯校正为每个类别添加伪计数，提供更稳健的规则准确率估计。
束搜索本质上是贪婪的，因为它不回溯，但束宽允许同时探索多个有希望的路径。这种贪婪与探索之间的权衡是CN2的一个关键特征。搜索空间由数据中存在的属性-值对定义，条件通常采用attribute = value形式用于名义属性，或attribute <= value和attribute >= value形式用于数值属性，尽管原始算法专注于名义数据。
算法变体
多年来开发了CN2的几种变体。最重要的是CN2-SD，由Nada Lavrač及其同事于1990年代末提出，它将目标从分类转向子群发现。在子群发现中，目标是找到描述具有异常类别分布的有趣人口子群的规则，而非构建完整分类器。CN2-SD使用加权相对准确率度量来评估规则，平衡规则泛化性和分布异常性。另一种变体CN2-R，结合随机化测试来评估规则的统计显著性，过滤掉可能偶然出现的规则。这有助于生成更可靠和可泛化的规则集。
无序变体的CN2生成一组规则，其中每条规则独立学习，预测时应用所有规则并组合其预测，通常通过投票或选择特异性最高的规则。这种方法对于类别区域重叠的数据集可能更稳健。有序和无序规则的选择取决于应用；有序列表更简单且更快，而无序集可以为稀有类别提供更好的覆盖。
应用与影响
CN2已应用于多个领域，包括医疗诊断、故障检测和生态建模。其可解释性使其在理解决策过程至关重要的领域特别有价值，如医疗保健和法规合规。例如，在医疗应用中，CN2规则可以表示为简单条件，如if blood_pressure > 140 and age > 60 then high_risk，临床医生可以轻松验证。该算法也被用作Machine learning中符号和亚符号方法比较的基准。虽然现代方法如Deep learning在复杂任务上通常达到更高准确率，但CN2在需要透明模型或数据有限的问题上仍然相关。
该算法的影响扩展到后来的规则学习系统，如RIPPER和PART，它们采用了类似的搜索和评估策略。CN2基于熵的评估是决策树归纳和特征选择中更复杂信息论度量的先驱。其分离-征服框架已从理论上分析，与PAC学习框架和规则学习的复杂性有联系。
局限性与扩展
CN2有已知的局限性。它对噪声数据敏感，因为贪婪搜索可能过拟合虚假模式。束搜索虽然比纯爬山更彻底，但由于有限的向前看能力，仍可能错过最优规则。该算法假设属性独立，这在现实数据中可能不成立。扩展已解决其中一些问题。例如，通过离散化纳入连续属性，无论是作为预处理步骤还是在搜索中，允许CN2处理数值数据。使用统计测试，如CN2-R，减轻过拟合。最近的工作将CN2与集成方法结合，其中组合多个规则集以提高稳健性。
在现代Machine learning的背景下，CN2通常与Neural network方法对比。虽然神经网络可以自动学习复杂的特征交互，但它们需要大量数据且难以解释。另一方面，CN2生成紧凑、人类可读的规则，但可能在高维或高度非线性问题上遇到困难。这种权衡继续推动结合符号规则和亚符号学习的混合系统研究，这是神经符号AI更广泛领域中的一个话题。
实现与软件
CN2在多个机器学习库中实现。卢布尔雅那大学开发的Orange数据挖掘套件包含CN2学习器，Weka工具包也是如此。这些实现提供了用户友好的界面，用于将算法应用于真实数据集。该算法的简单性使其易于在各种编程语言中实现，并且经常用作Machine learning和数据挖掘课程中的教学示例。开源实现的可用性促进了其在研究和教育中的持续使用。
尽管于1980年代末引入，CN2仍然是机器学习从业者工具箱中的相关算法。其对可解释性的关注和高效的搜索策略确保了它在AI历史中的地位，与先于当前Deep learning主导地位的其他符号方法并列。截至2020年代，CN2仍在规则学习和可解释AI的研究中被引用，并作为评估较新规则归纳方法的基线。