算法简介
基于规则的分类器利用一组 "if...then" 规则对记录进行分类。这种模型直观且易于解释，非常适合需要明确决策逻辑的场景。
规则集通常表示为 $R = (r_1 \lor r_2 \lor \dots \lor r_k)$，其中每个 $r_i$ 代表一条分类规则。单条规则的形式如下：
$$r_i : (\text{条件}_i) \rightarrow y_i$$
规则右边是后件，包含预测类别 $y_i$；左边是前件（前提），由属性和属性值的合取构成：
$$\text{条件}_i = (A_1 , op , v_1) \land (A_2 , op , v_2) \land \dots \land (A_n , op , v_n)$$
其中 $(A_j, v_j)$ 是属性 - 值对，$op$ 是比较运算符（如 $=$, $\neq$, $<$, $>$, $\leq$, $\geq$）。如果规则的前件与记录 $x$ 的属性匹配，则称该规则覆盖了 $x$。当所有规则中只有 $r$ 被触发时，称 $r$ 被激活。
评估规则质量主要看覆盖率和准确率。给定数据集 $D$ 和规则 $r: A \rightarrow y$：
- 覆盖率：$D$ 中触发规则 $r$ 的记录比例，即 $|A| / |D|$。
- 准确率：触发 $r$ 的记录中类标号等于 $y$ 的比例，即 $|A \cap y| / |A|$。
工作原理
规则集的两个关键性质决定了分类的确定性：
- 互斥性：不存在两条规则被同一条记录同时触发。这确保每条记录至多被一条规则覆盖。
- 穷举性：任意属性组合都存在一条规则覆盖。这确保每条记录至少被一条规则覆盖。
两者结合保证每条记录被且仅被一条规则覆盖。若规则集不穷举，需添加默认规则 $r_d: () \rightarrow y_d$，其前件为空，用于捕获未被其他规则覆盖的记录，默认类 $y_d$ 通常是训练集中多数类。
若规则集不互斥，一条记录可能触发多条规则导致冲突。解决策略主要有两种：
- 有序规则：按优先级降序排列（基于准确率、覆盖率等）。测试记录由最高秩的规则分类，避免冲突。
- 无序规则：允许触发多条规则，采用投票机制，将记录指派给得票最多的类。
本文主要探讨基于有序规则的分类器。
处理规则冲突的策略
核心思想是对规则进行优先级排序，取高优先级规则对应的类别。常见方案包括：
- 规模序：赋予'最苛刻'规则最高优先级。苛刻性由规则前件的规模（属性测试数量）度量，激活具有最多属性测试的规则。
- 规则序：预先确定优先次序。可基于类的序（重要性高的类规则在前）或规则的序（基于质量）。
规则排序方案
排序可逐条或逐个类进行：
- 基于规则质量：依据准确度、覆盖率等度量排序。优点是测试记录总由'最好'的规则分类；缺点是秩越低越难解释，因为隐含假设了前面规则均不成立。
- 基于类标号：根据类的重要性排序。例如，误分类代价高的类规则优先。同类规则在一起出现，相对顺序不重要。缺点是低质量规则可能碰巧预测高秩类，导致高质量规则被忽略。
大多数算法（如 RIPPER）采用基于类标号的排序方案。
构建规则分类器的方法
提取规则旨在识别属性与类标号间的联系，分为两类：
- 直接方法：直接从数据中提取规则。将属性空间划分为子空间，同一子空间的记录可用一条规则分类。
- 间接方法：从其他模型（如决策树）中提取规则。为复杂模型提供简洁描述。
直接方法：顺序覆盖与 RIPPER
顺序覆盖算法常用于直接提取规则，以贪心方式增长。它一次提取一个类的规则，选择标准取决于类的普遍性或误分类代价。
Learn-One-Rule 函数
目标是提取覆盖大量正例、少量反例的规则。由于搜索空间指数级增长，采用贪心策略：
-
规则增长：
