在训练集中，学到一条规则后，将这条规则所覆盖的样例（满足规则的样例，或叫支持该规则的样例）全去掉，形成一个较小的训练集，再在其上进行规则学习，直至训练集为空，这就是序贯覆盖法。

序贯覆盖

【西瓜书第15.2节】以二分类问题为例，讨论序贯覆盖法。

在训练集中，学到一条规则后，将这条规则所覆盖的样例（满足规则的样例，或叫支持该规则的样例）全去掉，形成一个较小的训练集，再在其上进行规则学习，直至训练集为空，这就是序贯覆盖法。 “序贯”一词体现出逐条得出规则，形成规则集。

例1：用序贯覆盖法产生规则长度为1的规则集

1. 初始化：$\oplus \leftarrow$ （这是条空规则）。

2. 产生长度为1的规则：$\oplus \leftarrow {\mathbf{f}}_1$。

其中，候选文字${\mathbf{f}}_1$是体现关系的表达式：“R(属性$i$,属性值$ij$)”，表示“属性$i$=属性值$ij$（属性$i$的第$j$个取值）”，如，(色泽=青绿)，这里，关系R指“=”。

• 取训练集的正例子集中出现的某个R关系作为候选${\mathbf{f}}_1$。
• 对候选${\mathbf{f}}_1$进行判断：是否“仅覆盖正例”（也即判断该R关系是否在反例中出现），仅覆盖正例的${\mathbf{f}}_1$为合格的规则。

3. 录取合格规则$\oplus \leftarrow {\mathbf{f}}_1$，并将其所覆盖的正例全去掉。

4. 在新的训练集中，再依上述方法继续录取合格的且长度为1的规则，直至训练集中的正例子集为空。 即找出了一个覆盖所有正例的规则集 { r + 1 } \{\boldsymbol{r}_+^1\} {r+1​}（上标表示长度为1，下标“$+$”表示以覆盖正例作为录取准则）。

5. 采用同样的方法，找出一个覆盖所有反例的规则集 { r − 1 } \{\boldsymbol{r}_-^1\} {r−1​}。

6. 最后，处理 { r + 1 } ∪ { r − 1 } \{\boldsymbol{r}_+^1\}\cup \{\boldsymbol{r}_-^1\} {r+1​}∪{r−1​}中的规则冲突。

例2：用序贯覆盖法产生规则长度为2的规则集

1. 基础：训练集$D$以及上述已训练出的规则集 { r + 1 } ∪ { r − 1 } \{\boldsymbol{r}_+^1\}\cup \{\boldsymbol{r}_-^1\} {r+1​}∪{r−1​}。

2. 构造两重循环：对 { r + 1 } \{\boldsymbol{r}_+^1\} {r+1​}中的规则排序（如，以覆盖最多的优先），设条件依次为：$({\mathbf{f}}_1,{\mathbf{f}}_2,\cdots ,{\mathbf{f}}_n)$，遍历地取出条件for$({\mathbf{f}}_i,1⩽i⩽n)$（第一层循环），遍历$j⩾i$取出条件 for$({\mathbf{f}}_j,i⩽j⩽n)$（第二层循环）。

3. 在两重循环体中进行判断：若${\mathbf{f}}_i\wedge {\mathbf{f}}_j$在反例中出现，则淘汰该条件${\mathbf{f}}_i\wedge {\mathbf{f}}_j$；否则接收该规则$\oplus \leftarrow {\mathbf{f}}_i\wedge {\mathbf{f}}_j$，并将其覆盖的所有正例集删除，即更新训练集。

4. 在上述循环过程中，若新训练集的正例集为空，则退出两重循环。 若两重循环结束后，新训练集的正例集不空，则再补充循环：遍历地取出条件for$({\mathbf{f}}_i,1⩽i⩽n)$，若规则$\oplus \leftarrow {\mathbf{f}}_i\wedge 1$（视为长度为2）覆盖新训练集的一些正例，则接收该规则并更新训练集，直至训练集中正例集为空。

5. 上述过程即找到了一个覆盖所有正例的规则长度为2的规则集 { r + 2 } \{\boldsymbol{r}_+^2\} {r+2​}，同样，找到一个覆盖所有反例的规则长度为2的规则集 { r − 2 } \{\boldsymbol{r}_-^2\} {r−2​}。

6. 处理规则冲突后，得到样本集的长度为2的规则集： { r + 2 } ∪ { r − 2 } \{\boldsymbol{r}_+^2\}\cup \{\boldsymbol{r}_-^2\} {r+2​}∪{r−2​}。

使用上述方法可以产生长度更长的规则，显然，最长规则的长度不会超过 { r + 1 } \{\boldsymbol{r}_+^1\} {r+1​}中的规则数。

放松约束：上述判断规则是否被接收时，要求R“仅覆盖正例”，可放松为“尽可能多地覆盖正例，并尽可能少地覆盖反例”，定量描述为： 给定$\frac{\text{R覆盖的反例数}}{\text{R覆盖的正例数}}$一个阈值，小于该值的R为合格。

上述循环方法会有“组合爆炸”问题，因此，在实践中，使用两种策略：

(i) 自顶向下“特化”：即由短规则逐步变为长规则；

(ii) 自底向上“泛化”：即由长规则逐步变为短规则。

在寻找最优的规则集时，需要对规则进行取舍，涉及评估规则优劣的标准，通常考虑的优先级为：

(i) 规则的准确率；

(ii) 覆盖的样例数；

(iii) 属性的次序（即更在乎哪些属性）；

注意：依序贯覆盖法生成的规则集并不唯一。

前述是以二分类为例，对于多分类问题，以正在考虑的类别$k$为正例，其他类别为反例，产生 { r + k } \{\boldsymbol{r}_{+k}\} {r+k​}，然后，处理冲突得到 ∪ k = 1 K { r + k } \cup _{k=1}^K\{\boldsymbol{r}_{+k}\} ∪k=1K​{r+k​}即可。

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：15.3 归结与逆归结（你可知“反证法”原理？）
下一篇：15.5 剪枝优化(预剪枝（阻止生长）和后剪枝（“由长变短”）)