基本概念
规则学习概述
规则学习（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 | 雨 | 适中 | 高 | 强 | 否 |
💡 序贯覆盖算法
算法流程
- 初始化：规则集R = ∅，训练集D' = D
- While D'不为空：
- • 学习一条规则r，尽可能准确覆盖D'中的样本
- • 将r加入规则集：R = R ∪ {r}
- • 从D'中移除被r覆盖的样本
- 返回规则集R
✓ 规则评价
- • 覆盖率：规则覆盖的样本数
- • 准确率：规则预测正确的比例
- • 置信度：满足条件时结论正确的概率
🎯 规则学习优势
- • 可解释性强，易于理解
- • 可以手动修改和调整
- • 知识显式化
📊 规则顺序
规则按优先级排列，从上到下匹配。最后的默认规则处理所有未被其他规则覆盖的情况。
序贯覆盖
序贯覆盖算法框架
算法流程
- 初始化：规则集R = ∅，训练集D′ = D
- While D′不为空：
- • 学习一条新规则r，使其尽可能准确地覆盖D′中的样本
- • 将r加入规则集：R = R ∪ {r}
- • 从D′中移除被r覆盖的样本
- 返回规则集R
学习单条规则
采用贪心策略，从最一般的规则开始，逐步添加条件（特化）：
- 初始化：r = "IF True THEN class"（覆盖所有样本）
- While 规则准确率不够高：
- • 枚举所有可能的新条件
- • 选择使得规则质量提升最大的条件加入r
- 返回规则r
规则质量度量
常用的规则质量度量包括：
- • 信息增益：规则能带来多少信息量
- • Laplace准确率：(nc + 1) / (n + k)，避免小样本问题
- • FOIL Gain：考虑正例覆盖和负例排除的综合指标
RIPPER算法
RIPPER（Repeated Incremental Pruning to Produce Error Reduction）是一种高效的序贯覆盖规则学习算法。
RIPPER的关键特性
- 增量规则生长： 贪心地添加条件，直到规则不再覆盖负例
- 规则剪枝： 基于验证集删除不必要的条件，防止过拟合
- 规则优化： 在全部规则学习完成后，尝试替换或修订规则以提升性能
- 多类处理： 按类别频率排序，依次为每个类学习规则
MDL原则
RIPPER使用最小描述长度（MDL）原则作为停止准则：
DL(规则集) + DL(异常|规则集)
当增加新规则导致总描述长度增加时停止，防止过拟合。
✓ 优点
- • 高效，适合大规模数据
- • 剪枝机制有效防止过拟合
- • 生成的规则简洁
✗ 缺点
- • 贪心搜索，可能错过最优规则
- • 规则间可能有冲突
- • 对噪声数据敏感
RIPPER算法演示
逐步展示RIPPER学习规则的过程（生长、剪枝、优化）
🚧 开发中...
剪枝优化
规则剪枝
学到的规则可能过于复杂，在训练集上表现很好但泛化能力差。规则剪枝通过删除不必要的条件来简化规则，提高泛化能力。
简化剪枝（Reduced Error Pruning）
- 将数据分为生长集和剪枝集
- 在生长集上学习规则（可能过拟合）
- 对每个规则，尝试删除每个条件
- 如果删除条件后在剪枝集上性能提升或不变，则删除
- 重复3-4直到无法改进
规则后剪枝策略
- 删除条件： 移除某个条件，使规则更一般化
- 删除规则： 移除整条规则，如果其对性能贡献不大
- 规则合并： 将相似的规则合并为一条更一般的规则
规则集优化
除了剪枝单条规则，还可以对整个规则集进行优化。
规则排序
规则应用顺序会影响预测结果。常用排序策略：
- 按准确率排序： 准确率高的规则优先
- 按覆盖度排序： 覆盖样本多的规则优先
- 按类别排序： 按类别重要性或频率排序
冲突解决
当多条规则同时适用于一个样本时，如何选择：
- • 第一匹配：使用第一条匹配的规则
- • 最高置信度：使用置信度最高的规则
- • 投票：所有匹配规则投票决定
💡 默认规则
通常需要一条默认规则来处理不被任何规则覆盖的样本， 如"IF True THEN 最常见类"。默认规则应放在最后。
规则剪枝过程
可视化规则剪枝如何提升泛化性能
🚧 开发中...
一阶规则学习
归纳逻辑程序设计（ILP）
归纳逻辑程序设计（Inductive Logic Programming, ILP）从样例中学习逻辑程序（一阶规则），能够表示复杂的关系和结构。
命题规则 vs 一阶规则
命题规则（Propositional Rules）
IF (天气=晴 AND 温度=高) THEN (打网球=是)
只能表示属性值的组合
一阶规则（First-Order Rules）
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 ∧ H ⊨ E+ 且 B ∧ H ⊭ E-
FOIL算法
FOIL（First-Order Inductive Learner）是经典的ILP算法，采用序贯覆盖策略学习一阶规则。
FOIL Gain
FOIL使用信息增益的变体来评估添加新文字（literal）的效果：
Gain = t · (log₂(p₁/(p₁+n₁)) - log₂(p₀/(p₀+n₀)))
t: 添加文字后仍满足的正例数
p₀, n₀: 添加前的正例数和负例数
p₁, n₁: 添加后的正例数和负例数
FOIL算法流程
- 初始化规则：只有头部，没有体部（覆盖所有样本）
- While 规则覆盖负例：
- • 枚举所有可能的文字（谓词、变量组合）
- • 选择FOIL Gain最大的文字加入规则体
- 将学到的规则加入规则集
- 移除被覆盖的正例
- 重复1-4直到所有正例被覆盖
💡 ILP的应用
- • 分子生物学：药物活性预测、蛋白质结构分析
- • 知识发现：从关系数据库中提取规则
- • 自然语言处理：学习语法规则
- • 机器人：学习动作规划规则
ILP家族关系学习
从家族关系事实中学习grandparent、uncle等关系的规则
🚧 开发中...
规则集学习
从决策树提取规则
决策树的每条从根到叶的路径可以转换为一条规则，这提供了另一种规则学习途径。
C4.5rules
C4.5rules算法从C4.5决策树提取规则：
- 用C4.5算法学习决策树
- 对每个叶节点，从根到叶的路径形成一条规则
- 对每条规则进行剪枝（删除不重要的条件）
- 对规则集进行优化（删除、合并规则）
- 按规则性能排序
✓ 优点
- • 利用成熟的决策树算法
- • 规则可以重叠（不同于树的互斥划分）
- • 规则更简洁、更易理解
✗ 缺点
- • 规则数量可能很多
- • 需要处理规则冲突
- • 可能丢失决策树的层次结构信息
规则集 vs 决策树 vs 决策列表
三种表示形式
决策树（Decision Tree）
层次结构，路径互斥，每个样本只匹配一条路径
决策列表（Decision List）
规则有序排列，使用第一条匹配的规则（if-then-else链）
规则集（Rule Set）
规则无序或按质量排序，可能多条规则匹配，需要冲突解决策略
选择建议
- 决策树： 适合需要快速分类、不要求高度可解释性的场景
- 规则集： 适合需要高可解释性、允许规则重叠的场景
- 决策列表： 适合规则有自然优先级、需要确定性预测的场景
规则学习的挑战
搜索空间巨大
可能的规则数量随特征和取值数指数增长，需要高效的搜索策略
规则质量评估
如何平衡简洁性和准确性，避免过拟合
规则冲突和冗余
多条规则可能相互矛盾或重复，需要后处理优化
类别不平衡
少数类样本可能被多数类规则覆盖，难以学习
未来方向： 结合神经网络的表示学习和规则学习的可解释性， 发展神经符号学习（Neuro-Symbolic Learning）， 在保持性能的同时提供可解释性。
决策树转规则集
演示如何从决策树提取规则，并进行剪枝优化
🚧 开发中...