第15章 规则学习

🎯 学习目标

• 理解规则学习的基本概念和评价指标
• 掌握序贯覆盖算法的原理
• 理解规则剪枝和优化方法
• 了解归纳逻辑编程(ILP)的基本思想

15.1 基本概念

规则学习概述

规则学习（Rule Learning） 从数据中提取形如"IF condition THEN conclusion"的规则，是一种符号化的知识表示方法。

规则的形式

IF (条件1 AND 条件2 AND ...) THEN (结论)

例如：IF (天气=晴 AND 温度=高 AND 湿度=正常) THEN (适合打网球=是)

规则的评价指标

• 支持度（Support）：规则覆盖的样本数量或比例
• 置信度（Confidence）：在满足条件的样本中，结论正确的比例
• 覆盖率（Coverage）：规则能够分类的样本比例
• 准确率（Accuracy）：规则预测正确的样本比例

💡 为什么使用规则学习？

• 可解释性强：规则直观易懂，便于人类理解和验证
• 知识提取：将隐含在数据中的模式显式化
• 易于修改：可以根据领域知识手动调整规则
• 推理透明：决策过程可追溯

规则学习方法分类

• 序贯覆盖（Sequential Covering）：逐条学习规则，每次学习一条规则后，移除被该规则覆盖的样本，然后在剩余样本上学习下一条规则。代表算法：CN2、RIPPER、FOIL。
• 从决策树提取规则：先学习决策树，然后将每条从根到叶的路径转换为一条规则。优点：可以利用成熟的决策树算法。

演示如何从数据中学习IF-THEN规则，观察规则的覆盖率和准确率：

训练数据 (点击查看应用的规则)

#	天气	温度	湿度	风力	打球
1	晴	高	高	弱	否
2	晴	高	高	强	否
3	阴	高	高	弱	是
4	雨	适中	高	弱	是
5	雨	低	正常	弱	是
6	雨	低	正常	强	否
7	阴	低	正常	强	是
8	晴	适中	高	弱	否
9	晴	低	正常	弱	是
10	雨	适中	正常	弱	是
11	晴	适中	正常	强	是
12	阴	适中	高	强	是
13	阴	高	正常	弱	是
14	雨	适中	高	强	否

15.2 序贯覆盖

序贯覆盖算法框架

算法流程

1. 初始化：规则集 R = ∅，训练集 D' = D
2. While D' 不为空：
   • 学习一条新规则 r，使其尽可能准确地覆盖 D' 中的样本
   • 将 r 加入规则集：R = R ∪
   • 从 D' 中移除被 r 覆盖的样本
3. 返回规则集 R

学习单条规则

采用贪心策略，从最一般的规则开始，逐步添加条件（特化）：

1. 初始化：r = "IF True THEN class"（覆盖所有样本）
2. While 规则准确率不够高：
   • 枚举所有可能的新条件
   • 选择使得规则质量提升最大的条件加入 r
3. 返回规则 r

规则质量度量

• 信息增益：规则能带来多少信息量
• Laplace准确率：$(n_c+1)/(n+k)$，避免小样本问题
• FOIL Gain：考虑正例覆盖和负例排除的综合指标

RIPPER算法

RIPPER（Repeated Incremental Pruning to Produce Error Reduction） 是一种高效的序贯覆盖规则学习算法。

RIPPER的关键特性

• 增量规则生长：贪心地添加条件，直到规则不再覆盖负例
• 规则剪枝：基于验证集删除不必要的条件，防止过拟合
• 规则优化：在全部规则学习完成后，尝试替换或修订规则以提升性能
• 多类处理：按类别频率排序，依次为每个类学习规则

MDL原则

RIPPER使用最小描述长度（MDL）原则作为停止准则：

$$\text{DL(规则集)}+\text{DL(异常|规则集)}$$

当增加新规则导致总描述长度增加时停止，防止过拟合。

优点：高效，适合大规模数据；剪枝机制有效防止过拟合；生成的规则简洁。缺点：贪心搜索，可能错过最优规则；规则间可能有冲突；对噪声数据敏感。

15.3 剪枝优化

规则剪枝

学到的规则可能过于复杂，在训练集上表现很好但泛化能力差。规则剪枝 通过删除不必要的条件来简化规则，提高泛化能力。

简化剪枝（Reduced Error Pruning）

1. 将数据分为生长集和剪枝集
2. 在生长集上学习规则（可能过拟合）
3. 对每个规则，尝试删除每个条件
4. 如果删除条件后在剪枝集上性能提升或不变，则删除
5. 重复3-4直到无法改进

规则后剪枝策略

• 删除条件：移除某个条件，使规则更一般化
• 删除规则：移除整条规则，如果其对性能贡献不大
• 规则合并：将相似的规则合并为一条更一般的规则

规则集优化

规则排序

规则应用顺序会影响预测结果。常用排序策略：按准确率排序、按覆盖度排序、按类别排序。

冲突解决

当多条规则同时适用于一个样本时：第一匹配（使用第一条匹配的规则）、最高置信度（使用置信度最高的规则）、投票（所有匹配规则投票决定）。

💡 默认规则

通常需要一条默认规则来处理不被任何规则覆盖的样本，如"IF True THEN 最常见类"。默认规则应放在最后。

15.4 一阶规则学习

归纳逻辑程序设计（ILP）

归纳逻辑程序设计（Inductive Logic Programming, ILP） 从样例中学习逻辑程序（一阶规则），能够表示复杂的关系和结构。

命题规则 vs 一阶规则

命题规则：IF (天气=晴 AND 温度=高) THEN (打网球=是) — 只能表示属性值的组合。

一阶规则：

parent(X,Y) :- father(X,Y).
grandparent(X,Z) :- parent(X,Y), parent(Y,Z).

可以表示对象间的关系、使用变量和量词。

ILP的输入

• 背景知识（Background Knowledge） B：已知的事实和规则
• 正例（Positive Examples） $E^{+}$：目标关系的正样本
• 负例（Negative Examples） $E^{-}$：目标关系的负样本

目标：学习假设H，使得 $B\wedge H\models E^{+}$ 且 $B\wedge H⊭E^{-}$

FOIL算法

FOIL（First-Order Inductive Learner） 是经典的ILP算法，采用序贯覆盖策略学习一阶规则。

FOIL Gain

FOIL使用信息增益的变体来评估添加新文字（literal）的效果：

$$\text{Gain}=t\cdot ({\log }_2\frac{p_1}{p_1+n_1}-{\log }_2\frac{p_0}{p_0+n_0})$$

t: 添加文字后仍满足的正例数；$p_0,n_0$: 添加前的正例数和负例数；$p_1,n_1$: 添加后的正例数和负例数。

FOIL算法流程

1. 初始化规则：只有头部，没有体部（覆盖所有样本）
2. While 规则覆盖负例：枚举所有可能的文字，选择FOIL Gain最大的文字加入规则体
3. 将学到的规则加入规则集
4. 移除被覆盖的正例
5. 重复1-4直到所有正例被覆盖

💡 ILP的应用

• 分子生物学：药物活性预测、蛋白质结构分析
• 知识发现：从关系数据库中提取规则
• 自然语言处理：学习语法规则
• 机器人：学习动作规划规则

15.5 规则集学习

从决策树提取规则

决策树的每条从根到叶的路径可以转换为一条规则，这提供了另一种规则学习途径。

C4.5rules算法

1. 用C4.5算法学习决策树
2. 对每个叶节点，从根到叶的路径形成一条规则
3. 对每条规则进行剪枝（删除不重要的条件）
4. 对规则集进行优化（删除、合并规则）
5. 按规则性能排序

优点：利用成熟的决策树算法；规则可以重叠（不同于树的互斥划分）；规则更简洁、更易理解。缺点：规则数量可能很多；需要处理规则冲突；可能丢失决策树的层次结构信息。

规则集 vs 决策树 vs 决策列表

• 决策树（Decision Tree）：层次结构，路径互斥，每个样本只匹配一条路径
• 决策列表（Decision List）：规则有序排列，使用第一条匹配的规则（if-then-else链）
• 规则集（Rule Set）：规则无序或按质量排序，可能多条规则匹配，需要冲突解决策略

选择建议：决策树适合需要快速分类的场景；规则集适合需要高可解释性、允许规则重叠的场景；决策列表适合规则有自然优先级、需要确定性预测的场景。

规则学习的挑战

• 搜索空间巨大：可能的规则数量随特征和取值数指数增长
• 规则质量评估：如何平衡简洁性和准确性，避免过拟合
• 规则冲突和冗余：多条规则可能相互矛盾或重复
• 类别不平衡：少数类样本可能被多数类规则覆盖

未来方向：结合神经网络的表示学习和规则学习的可解释性，发展神经符号学习（Neuro-Symbolic Learning），在保持性能的同时提供可解释性。