机器学习周志华学习笔记-第15章<规则学习>
卷王，请看目录
- 15规则学习
- 15.1 基本概念
- 15.2 序贯覆盖
- 15.3剪枝优化
- 15.4 一阶规则学习
- 15.5 归纳逻辑程序设计
- 15.5.1 最小一般泛化
- 15.5.2 逆归结
15规则学习
15.1 基本概念
机器学习中的“规则”(rule)通常是指语义明确、能描述数据分布所隐含的客观规律或领域概念、可写成“若……,则……”形式的逻辑规则。“规则学习”(rule learming)是从训练数据中学习出一组能用于对未见示例进行判别的规则。
基本概念包括：
- 规则：通常形式为“如果条件，则结论”，例如：if A and B then C。
- 前件（Antecedent）：规则中的“如果”部分，如上述例子中的A and B。
- 后件（Consequent）：规则中的“则”部分，如上述例子中的C。
- 覆盖度（Coverage）：规则能够覆盖的样本数量。
- 准确度（Accuracy）：规则预测正确的样本数量与覆盖度的比值。
15.2 序贯覆盖
序贯覆盖（Sequential Covering）是一种常用的规则学习方法，其基本思想是逐步生成规则，每一步生成的规则尽可能覆盖更多的正例，同时不覆盖或尽可能少覆盖负例。
算法步骤如下：
- 初始化规则集合为空。
- 在训练集中找到覆盖最多未覆盖正例的规则R。
- 将R添加到规则集合中，并从训练集中移除R覆盖的样本。
- 重复步骤2和3，直到满足停止条件（如覆盖所有正例或达到预设的规则数量）。
15.3剪枝优化
规则生成本质上是一个贪心搜索过程，需有一定的机制来缓解过拟合的风险，最常见的做法是剪枝(pruning)。与决策树相似，剪枝可发生在规则生长过程中,即“预剪枝”,也可发生在规则产生后，即“后剪枝”。通常是基于某种性能度量指标来评估增/删逻辑文字前后的规则性能,或增/删规则前后的规则集性能，从而判断是否要进行剪枝。剪枝（Pruning）是为了防止过拟合，通过移除规则中的某些条件来简化规则。
- 前剪枝（Pre-Pruning）：在规则生成过程中，如果添加新条件不会显著提高规则的准确度，则停止添加。
- 后剪枝（Post-Pruning）：先生成完整的规则集，然后逐一尝试移除规则中的条件，如果移除后规则性能没有显著下降，则保留简化后的规则。
15.4 一阶规则学习
受限于命题逻辑表达能力，命题规则学习难以处理对象之间的“关系”(relation)。而关系信息在很多任务中非常重要。例如，“瓜1的颜色比瓜2更深，并且瓜1的根蒂比瓜2更蜷”,因此“瓜1比瓜2更好”。然而，这已超越了命题逻辑的表达能力，需用一阶逻辑表示，并且要使用一阶规则学习。
一阶规则学习（First-Order Rule Learning）使用一阶逻辑表示规则，可以处理更复杂的数据关系。
一阶逻辑：使用变量和一阶谓词表示规则，例如：for all x (P(x) -> Q(x))。
15.5 归纳逻辑程序设计
归纳逻辑程序设计（Inductive Logic Programming，ILP）是一阶规则学习的一种形式，它使用逻辑程序设计语言来表示规则。
15.5.1 最小一般泛化
最小一般泛化（Minimum Generalization）是在ILP中用于生成规则的技术，目的是找到能够覆盖更多正例的一般化规则。
泛化：将规则中的具体值替换为更一般的概念，例如：P(x) -> Q(x) 泛化为 P(y) -> Q(y)。
15.5.2 逆归结
逆归结（Inverse Resolution）是ILP中用于生成规则的方法，它从正例出发，通过逻辑推理的反向过程来构造规则。
算法步骤如下：
- 从正例出发，使用归结（Resolution）操作的反向过程，生成候选规则。
- 对候选规则进行评估，选择能够最好覆盖正例且不覆盖负例的规则。
- 重复步骤1和2，直到满足停止条件。
公式表示：
归结操作：P and ¬Q -> R 可以通过归结操作生成 P -> Q 或 ¬R -> ¬P。
