第五章（1）分类：基于规则的分类器

根据规则集来分类
分类规则的质量用覆盖率和准确率来度量
1. 覆盖率=触发规则r的记录/所有记录
2. 准确率=触发规则r且类标号正确的记录/触发规则r的记录
基于规则的分类器所产生的规则集的两个重要性质：
1. 互斥规则：规则集中不存在两条规则被同一个记录触发
2. 穷举规则：对属性值的任意组合，规则集中都有一条规则可以覆盖
3. 两个规则共同作用的规则集，保证一条记录有且仅有被一条规则覆盖；当然，很多分类器是不满足的，所以加入默认类（rd：（）->yd，yd是没被规则集覆盖的记录的多数类）
4. 规则集不是互斥时：
  1. 有序规则：规则集中的规则按照优先级降序排列，有序的规则集即决策表（规则秩由高到低排列）
  2. 无序规则：允许记录触发多条规则，把记录指派给多数类（有时规则会加权）
  3. 有序规则建模开销大且需要维护，无序规则则需要将记录和每一个规则进行比较
接下来都是有序规则的基于规则的分类器：
1. 两种规则的排序方案：
  1. 基于规则的排序方案：保证每一个记录都是由覆盖它的最好的规则来分类的，潜在的问题就是秩越低越难解释，因为只有排在该规则前面的规则不成立才能到这里
  2. 基于类的排序方案：属于同一类的规则集排在一起，同一类的规则之间排序并不重要，因为他们只要触发一个就能确定类；基于规则的分类器（如C4.5规则和RIPPER）都采用基于类的排序方案（下面的基础）
2. 建立基于规则的分类器的两种方法：
  1. 直接方法：直接从数据中提取分类规则；把属性空间划分为较小的子空间，使属于一个子空间的所有记录可以被分类
  2. 间接方法：从其他分类模型（决策树、神经网络）中提取分类规则；为较为复杂的分类模型提供简介的描述
3. 规则提取的直接方法：
  1. 顺序覆盖算法：从包含多个类的数据集中一次提取一个类的规则；在提取规则时，类y的训练记录被视为正例，如果一个规则覆盖大多数正例和极少数反例，那么这个规则是可取的，找到这样的规则就删除其覆盖的训练记录，将规则加入到决策表R的尾部，重复直到满足结束条件
    1. learn-one-rule：目标是提取一个分类规则，该规则覆盖大多数正例和少量反例；但是搜索空间呈指数级，所以用贪心的策略：
      1. 规则增长策略：一般的增长策略有两种：
        一般到特殊：在选定正例类y后，从一般的空规则集到一次选择一个合取项来覆盖，直到满足结束条件（如加入的合取项不能提高规则的质量）
        特殊到一般：随机的选择一个正例，一次删除一个合取项，覆盖更多的正例来泛化规则，直到结束条件（如当规则覆盖反例）
      2. 规则评估：需要一种评估量来确定添加或删除合取项
        似然比：正确预测数与随机预测的对比，较大的数值说明正确预测显著>随机猜测
        Laplace和m估计：考虑规则覆盖率的度量
        FOIL信息增益：首先，规则的支持度即其覆盖的正例数；选择高支持度和高准确率的规则；增加合取项后的信息增益
      3. 规则剪枝：对learn-one-rule产生的规则剪枝，用泛化误差估计来确定是否剪枝
    2. 顺序覆盖的基本原理：顺序覆盖必须删除提取规则覆盖的所有样例，这样做就不会影响到接下来的规则准确率计算
    3. *RIPPER算法：一种广泛使用的规则归纳算法，使用确认数据集；
      1. 对于二类问题：以多数类为默认类，为预测少数类学习规则；对于多类问题：按类的频率给类升序排序，第一次迭代将最少类的样例记为正例，开始提取规则，直达剩下默认类
      2. 规则增长：一般到特殊策略，使用FOIL信息增益来选择最佳合取项来添加到规则前件；规则剪枝使用确认集，确认集上的准确率是单调的，剪枝是从最后添加的合取项开始的
      3. 建立规则集：规则生成后，删除其覆盖的所有样例，只要规则不违反基于最小描述长度原则的终止条件，就将其加入到规则集中
4. 规则提取的间接方法：
  1. 决策树生成规则：原则上，决策树从根节点到叶节点的每一条路径都是一个分类规则且这样组合的规则集是完全且互斥的；规则可以简化
    1. 规则产生：每一条路径产生一条分类规则，对分类规则进行简化（只要简化后的规则的误差率<=原规则误差率，则保留悲观误差率最低的规则、剃刀原则），重复剪枝直到规则的悲观误差不再改进为止，再取出重复项
    2. 规则排序：基于类的排序方法排序
基于规则的分类器的特征：
1. 规则的表达能力几乎等价于决策树
2. 基于规则的分类器通常用来产生更易于解释的描述性模型，这样性能还不错
3. 基于类的排序方法的规则分类器适用于类分布不平衡的数据集

原文链接：https://blog.csdn.net/u013103305/article/details/83307680