【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。

1.剪枝优化

规则生成本质上是一个贪心搜索过程，需有一定的机制来缓解过拟合的风险，最常见的做法是剪枝（pruning）。与决策树相似，剪枝可发生在规则生长过程中，即“预剪枝”，也可发生在规则产生后，即“后剪枝”。通常是基于某种性能度量指标来评估增/删逻辑文字前后的规则性能，或增/删规则前后的规则集性能，从而判断是否要进行剪枝。

剪枝还可借助统计显著性检验来进行。例如CN2算法在预剪枝时，假设用规则集进行预测必须显著优于直接基于训练样例集后验概率分布进行预测。为便于计算，CN2使用了似然率统计量（Likelihood Ratio Statistics，简称LRS）。令$m_+,m_-$分别表示训练样例集中的正、反例数目，$\hat{m}_+,\hat{m}_-$分别表示规则（集）覆盖的正、反例数目，则有：

这实际上是一种信息量指标，衡量了规则（集）覆盖样例的分布与训练集经验分布的差别：LRS越大，说明采用规则（集）进行预测与直接使用训练集正、反例比率进行猜测的差别越大；LRS越小，说明规则（集）的效果越可能仅是偶然现象。在数据量比较大的现实任务中，通常设置为在LRS很大（例如0.99）时CN2算法才停止规则（集）生长。

后剪枝最常用的策略是“减错剪枝”（Reduced Error Pruning，简称REP），其基本做法是：将样例集划分为训练集和验证集，从训练集上学得规则集$\mathcal{R}$后进行多轮剪枝，在每一轮穷举所有可能的剪枝操作，包括删除规则中某个文字、删除规则结尾文字、删除规则尾部多个文字、删除整条规则等，然后用验证集对剪枝产生的所有候选规则集进行评估，保留最好的那个规则集进行下一轮剪枝，如此继续，直到无法通过剪枝提高验证集上的性能为止。

规则学习中常称为“生长集”（growing set）和“剪枝集”（pruning set）。

REP剪枝通常很有效，但其复杂度是$O(m^4)$，$m$为训练样例数目。IREP（Incremental REP）将复杂度降到$O(m \log ^2 m)$，其做法是：在生成每条规则前，先将当前样例集划分为训练集和验证集，在训练集上生成一条规则$\mathbf{r}$，立即在验证集上对其进行REP剪枝，得到规则$\mathbf{r}’$；将$\mathbf{r}’$覆盖的样例去除，在更新后的样例集上重复上述过程。显然，REP是针对规则集进行剪枝，而IREP仅对单条规则进行剪枝，因此后者比前者更高效。

若将剪枝机制与其他一些后处理手段结合起来对规则集进行优化，则往往能获得更好的效果。以著名的规则学习算法RIPPER为例，其泛化性能超过很多决策树算法，而且学习速度也比大多数决策树算法更快，奥妙就在于将剪枝与后处理优化相结合。

RIPPER全称Repeated Incremental Pruning to Produce Error Reduction。

RIPPER算法描述如图15.2所示。它先使用IREP*剪枝机制生成规则集$\mathcal{R}$。IREP*是IREP的改进，主要是以$\frac{\hat{m}_++(m_--\hat{m}_-)}{m_++m_-}$取代了IREP使用的准确率作为规则性能度量指标，在剪枝时删除规则尾部的多个文字，并在最终得到规则集之后再进行一次IREP剪枝。RIPPER中的后处理机制是为了在剪枝的基础上进一步提升性能。对$\mathcal{R}$中的每条规则$\mathbf{r}_i$，RIPPER为它产生两个变体：

• $\mathbf{r}’_i$：基于$\mathbf{r}_i$覆盖的样例，用IREP*重新生成一条规则$\mathbf{r}’_i$，该规则称为替换规则（replacement rule）；
• $\mathbf{r}’‘_i$：对$\mathbf{r}_i$增加文字进行特化，然后再用IREP*剪枝生成一条规则$\mathbf{r}’‘_i$，该规则称为修订规则（revised rule）。

接下来，把$\mathbf{r}’_i$和$\mathbf{r}’‘_i$分别与$\mathcal{R}$中除$\mathbf{r}_i$之外的规则放在一起，组成规则集$\mathcal{R}’$和$\mathcal{R}’’$，将它们与$\mathcal{R}$一起进行比较，选择最优的规则集保留下来。这就是图15.2中算法第4行所做的操作。

图15.2中重复次数取值$k$时亦称RIPPERk，例如RIPPER5意味着k=5。

第1步：基于IREP*生成规则集。

第4步：后处理。

第5步：去除已被覆盖的样例。

为什么RIPPER的优化策略会有效呢？原因很简单：最初生成$\mathcal{R}$的时候，规则是按序生成的，每条规则都没有对其后产生的规则加以考虑，这样的贪心算法本质常导致算法陷入局部最优；RIPPER的后处理优化过程将$\mathcal{R}$中的所有规则放在一起重新加以优化，恰是通过全局的考虑来缓解贪心算法的局部性，从而往往能得到更好的效果。

2.式(1)的解释

式(1)上面一段话中有一句“假设用规则集进行预测必须显著优于直接基于训练样例集后验概率分布进行预测”，这里简单解释下什么叫“直接基于训练样例集后验概率分布进行预测”。比如训练集有80%都是正例，那就将所有样本都预测为正例，也就是永远预测概率更大的那一类。

我们通过几个例子来解释下LRS。假设训练集有100个样本，正例$m_+=50$，反例$m_-=50$。假设规则A覆盖了20个样本，其中$\hat{m}_+=18, \hat{m}_-=2$，则LRS的计算如下：

LRS比较大，说明规则A还是很有用的，可以很好的区分正负样例。同样的训练集，假设规则B也是覆盖了20个样本，但是有$\hat{m}_+=11, \hat{m}_-=9$，此时LRS为：

LRS很小，说明规则B没啥价值。注意，对于正负样例不平衡的训练集，LRS也同样适用。

最后，再解释下为什么在LRS很大时CN2算法停止规则（集）生长。如果某一步开始，LRS已经很大，说明这条规则已经把一个明显不同于全局分布的区域抓出来了，再继续细分可能收益不大，容易过拟合或者使规则变得太复杂，因此就可以停止继续长下去。

3.REP,IREP,IREP*

3.1.REP

假设任务是判断是否适合打篮球，我们基于训练集得到的初始规则集如下：

• 规则1：$(天气=晴) \land (温度=适中) \land (风力=小) \land (鞋子=运动鞋) \to 打篮球$
• 规则2：$(天气=阴) \land (场地=室内) \to 打篮球$
• 规则3：$(朋友=参加) \land (时间=晚上) \to 打篮球$

REP会先得到完整的规则集$R=\{ 规则1,规则2,规则3\}$。然后它会整体考虑剪枝，比如尝试：

• 方案1：删掉规则1中的“$(鞋子=运动鞋)$”。
• 方案2：删掉规则1中的“$(风力=小) \land (鞋子=运动鞋)$”。
• 方案3：删掉整个规则2。
• 方案4：删掉规则3中的“$(时间=晚上)$”。
• 方案5：删掉整个规则3。

然后把每个候选规则集拿到验证集上测试。例如发现：

• 原始规则集$R$的验证集准确率为82%。
• 方案1规则集的验证集准确率为85%。
• 方案3规则集的验证集准确率为78%。
• 方案4规则集的验证集准确率为86%。

REP会选择验证集准确率最高的方案4规则集，然后继续下一轮，直到再剪枝也不能提升验证集性能。

3.2.IREP

使用和第3.1部分一样的例子。IREP不会等规则1、规则2、规则3全部生成后再统一开始剪枝。IREP会先生成规则1，然后立刻只剪规则1，比如尝试：

• 规则1-1：$(天气=晴) \land (温度=适中) \land (风力=小) \to 打篮球$
• 规则1-2：$(天气=晴) \land (温度=适中) \to 打篮球$
• 规则1-3：$(天气=晴) \to 打篮球$

如果在验证集上比较后，发现规则1-3最好，于是我们就使用规则1-3替换规则1，并将规则1-3覆盖的样本剔除，再继续学习下一条规则2。

3.3.IREP*

相比IREP，IREP*主要是把规则好坏的评价指标从单纯的准确率改成了$\frac{\hat{m}_++(m_--\hat{m}_-)}{m_++m_-}$。

• Previous
  【机器学习基础】第六十九课：[规则学习]序贯覆盖