规则归纳(RIPPER)
- 提出者
- William W. Cohen
- 年份
- 1995
- 类型
- Supervised rule learning algorithm
- 类别
- Rule learning
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
规则归纳,特别是 RIPPER(Repeated Incremental Pruning to Produce Error Reduction)算法,是一种监督式机器学习方法,它从带标签的训练数据中学习一套紧凑的 IF-THEN 分类规则。RIPPER 由 William W. Cohen 于 1995 年提出,它采用“分而治之”(separate-and-conquer)策略,并结合最小描述长度(MDL)剪枝,生成既准确又易于理解的规则,使其成为归纳规则学习领域的里程碑式算法。
方法背后的直觉
想象一下为医生编写一份诊断检查表:每条规则都捕捉了能够可靠预测诊断的特定症状组合。RIPPER 从患者数据中自动构建这份检查表。它一次草拟一条规则,尽可能多地覆盖阳性病例,然后在一组保留数据上交叉检查每条规则,以去除过于具体的条件。最终结果是一个简短、人类可读的规则集,无需检查整个训练历史即可应用于新患者。
历史学
规则归纳的根源可以追溯到早期的机器学习系统,如 AQ (Michalski, 1969) 和 CN2 (Clark and Niblett, 1989)。Cohen 在 1995 年的 RIPPER 论文中,通过引入增量剪枝和基于 MDL 的优化,解决了这些前驱算法的计算效率低下和过拟合倾向问题。RIPPER 在 1995 年的 ICML 上发表,由于其具有竞争力的准确性和透明度,迅速成为基准算法,并且至今仍是规则学习文献和教科书中的标准参考。
何时使用
当模型可解释性是主要要求时,如临床决策支持、欺诈检测或合规设置,使用 RIPPER 进行规则归纳是合适的。它适用于混合的标称和数值特征,并且可以合理地扩展到数万个实例。RIPPER 假设训练标签足够可靠,并且潜在的决策边界可以通过轴对齐的合取来近似。它不太适用于高维连续特征空间或需要概率校准输出的任务;在这些情况下,梯度提升树或逻辑回归可能更优。
局限与注意事项
- 在非常高维或稀疏的特征空间中,规则质量会显著下降
- 有序规则列表可能对类别顺序敏感;最后学习的少数类可能得到较弱的规则
- 不产生校准的概率估计,限制了在成本敏感或排序任务中的使用
- 合取规则无法捕捉需要非轴对齐边界的复杂交互,除非进行特征工程
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 生成人类可读的 IF-THEN 规则,领域专家可以审计和验证
- 高效的分而治之学习结合 MDL 剪枝可减少过拟合
- 无需大量预处理即可处理标称和数值属性
- 与中等数据集规模下的集成方法相比,通常训练速度更快
应用
- 临床决策支持和医学诊断规则提取
- 金融交易监控中的欺诈和异常检测
- 使用词汇和结构特征进行文本分类
- 通过可解释的警报规则进行网络入侵检测
- 通过可操作的业务规则进行客户流失预测
使用方式
使用方式
RIPPER 一次处理一个类别,将所有剩余实例视为负例集。它通过反复添加最大化阳性实例与覆盖实例总数之比的条件来贪婪地增长合取规则。一旦规则增长完成,所有被其覆盖的实例都会被移除,然后学习下一条规则,遵循 Cohen (1995) 所描述的经典分而治之范式。
公式
\text{For each class } c \in \mathcal{C} \text{, grow a rule } R: \text{cond} \Rightarrow c \text{ maximizing } \frac{p}{p+n}在保留的验证分区上,使用指标 (p - n) / (p + n) 对每个候选规则进行剪枝,其中 p 和 n 分别表示正确覆盖和错误覆盖的实例数。只要剪枝能增加此值,就从规则的尾部向内部删除条件,以防止因恰好拟合训练集的过于具体的合取而导致的过拟合。
公式
\text{Prune rule } R \text{ by removing conditions to maximize } v(R, \text{prune set}) = \frac{p - n}{p + n}在学习完所有每个类别的规则后,RIPPER 会运行一个可选的、由最小描述长度原理指导的优化过程。对于最终规则集中的每条规则,算法会考虑替换或修改它,并且仅当更改能减少规则集和剩余误分类数据的组合描述长度时才接受该更改,从而在准确性和模型复杂度之间取得平衡。
公式
\text{Minimize description length: } DL(\text{ruleset}) + DL(\text{data} \mid \text{ruleset})在预测时,规则按学习顺序应用。一个未见过的实例被分配给第一个其条件全部满足该实例特征值的规则的类别标签。如果没有规则触发,该实例将归入默认类别,通常是训练数据中的多数类,从而确保输入空间的完全覆盖。
公式
\hat{y} = c_k \text{ where } R_k \text{ is the first rule in the ordered list that fires on instance } \mathbf{x}常见陷阱
- 在没有足够保留剪枝数据的小型数据集上应用 RIPPER 会导致过度剪枝、覆盖率低的规则
- 忽略类别不平衡会导致默认类别吸收少数类,掩盖少数类召回率差的问题
- 将学习到的规则顺序视为因果而非预测会导致探索性分析中的误解
- 跳过 MDL 优化过程(某些实现中可用)可能会在最终集合中留下冗余或冲突的规则
常见问题
RIPPER 与决策树有何不同?
两者都学习轴对齐边界,但决策树递归地划分整个特征空间,产生分层结构。RIPPER 则使用分而治之学习有序规则列表,当只有少数特定类别的模式很重要时,可以产生更紧凑的表示。规则也比树路径更容易让领域专家单独阅读。
RIPPER 能处理多类别问题吗?
可以。RIPPER 通过依次为每个类别学习规则来扩展到多类别设置,规则从最稀有的类别到最常见的类别排序。在学习后续类别的规则之前,会移除被早期类别规则覆盖的实例。默认规则将多数类分配给任何未被显式规则覆盖的实例。
最小描述长度原理在 RIPPER 中起什么作用?
MDL 提供了一个正式的标准来平衡规则复杂性与数据拟合。在优化阶段,RIPPER 倾向于选择总描述长度(包括规则和误分类实例的编码)更短的规则集。这可以防止算法保留过于具体的规则,这些规则会记住噪声而不是捕捉数据中的真实模式。
相关方法
参考文献
Cohen, W. W. (1995). Fast effective rule induction. Proceedings of the 12th International Conference on Machine Learning, 115–123.
打开 DOI 文献已复制。