顺序覆盖
知识点概述
顺序覆盖（Sequential Covering）是一种贪心算法框架，用于迭代地学习决策规则，最终形成一个决策列表。它的核心策略是“分而治之”（separate-and-conquer）：找到一个好的规则，覆盖一部分数据点，然后将这些数据点“分离”出去，在剩下的数据点上重复此过程。
教材原文
顺序覆盖 (Sequential Covering) 是一个通用过程，它重复学习单个规则以创建一个决策列表（或集合），该决策列表（或集合）按规则覆盖整个数据集。许多规则学习算法是顺序覆盖算法的变体。 … 这个想法很简单：首先，找到一个适用于某些数据点的好规则；删除规则所涵盖的所有数据点…重复规则学习，在剩余的点删除覆盖的点，直到没有剩余的点或满足另一个停止条件为止。
详细解释
- 核心思想: 与一次性学习所有规则的算法不同，顺序覆盖算法逐条地、贪心地学习规则。
- 算法流程 (以二分类为例):
- 初始化: 从一个空的规则列表开始。将其中一个类别定为“正类”，另一个为“负类”。
- 循环学习: a. 学习单条规则: 在当前所有数据点上，使用某种搜索策略（如下文所述）找到一条能够最佳地覆盖“正类”样本的规则（例如，准确率最高的规则）。 b. 分离 (Separate): 将被这条新规则覆盖的所有数据点（无论它们被正确分类还是错误分类）从数据集中移除。 c. 征服 (Conquer): 在剩余的数据点上，重复步骤 a 和 b，继续寻找下一条最好的规则。
- 停止: 当所有“正类”样本都被覆盖，或者找不到满足最低质量要求的规则时，循环停止。
- 收尾: 最后，通常会添加一个默认规则（例如，预测为“负类”），以覆盖所有剩余的实例。
- 如何学习单条规则?: 学习单条规则本身是一个搜索问题。一种常见的方法是束搜索（Beam Search）：
- 先学习一棵决策树。
- 从根节点开始，贪心地沿着能产生最“纯净”子集的路径向下搜索。
- 这条从根到叶节点的路径就构成了一条决策规则的条件。
- 多类别问题: 对于多类别问题，通常采用“一对多”（one-vs-rest）策略。先按类别的稀有程度排序，从最稀有的类别开始，为其学习规则，然后将其样本移除，再处理次稀有的类别，以此类推。
- RIPPER算法: 是顺序覆盖算法的一个著名变体，它在学习到规则列表后，还会进行一个“剪枝”后处理阶段，以优化规则集，防止过拟合。
学习要点
- 掌握顺序覆盖算法“分而治之”的核心策略。
- 理解算法的迭代过程：学习规则 → 移除已覆盖样本 → 在剩余样本上继续学习。
- 知道学习单条规则本身是一个搜索过程，例如可以通过构建决策树并寻找最佳路径来实现。
- 了解RIPPER是顺序覆盖框架下的一个具体实现。
实践应用
许多经典的规则学习算法，如CN2、RIPPER等，都基于顺序覆盖框架。它们被广泛应用于需要高可解释性的领域，如：
- 医疗诊断系统: 生成一组有序的、易于医生理解的诊断规则。
- 信用风险评估: 建立一套清晰的客户风险等级判断标准。
关联知识点
- 前置知识: 22-理论方法-决策规则, 20-理论方法-决策树
- 后续知识: 25-理论方法-贝叶斯规则列表