何女神，准备就期中考了，考到第7章，我有空继续看，顺便完善一下读书笔记，做人要有始有终。
回顾上节
提到了决策树的生成，主要是选择合理的分裂属性，并且修正合理的生成树，以获得较少的训练误差和不会过于臃肿的树结构，基于Occam’s Razor Rules，这有利于更强的泛化和预测能力。
第五章
这一章包含的内容多且重要，然而书本没有详细展开，这里我还是得仔细记录每一小节的内容。
5.1基于规则的分类器
分类模型用析取范式 $R=(r_1 \bigvee r_2 \bigvee … \bigvee r_k)$
这里R成为规则集
这里表示形式：$r_i:(条件_i)->y_i$
这里左边称为规则前提，右边为规则后件，包含预测结果。
分类规则的质量用覆盖率和准确率定义,D为数据集，A为规则前件，y为规则后件。
$$Converage（r) = \frac{|A|}{|D|}$$
$$Accuray(r)=\frac{|A\bigcap y|}{|A|}$$
基于定义，我们有互斥规则、穷举规则、有无序规则
由于规则集中的规则不一定是互斥的，所有有可能分类的时候某条记录会属于多个类（也就是说某条记录会同时触发规则集中的超过1条的过则，而被触发的规则的类标号也不一样），这种情况有两种办法解决。
(1）有序规则。将规则集中的规则按照优先级降序排列，当一个测试记录出现时，由覆盖记录的最高秩的规则对其进行分类，这就避免由多条分类规则来预测而产生的类冲突问题
(2）无序规则。允许一条测试记录触发多条分类规则，把每条被触发规则的后件看作是对相应类的一次投票，然后计票确定测试记录的类标号。通常把记录指派到得票最多的类。
假设现在有一个记录它不能触发规则集合中的任何一个规则，那么它该如何就行分类呢？解决办法也有两个：
（1）穷举规则。如果对属性值的任一组合，R中都存在一条规则加以覆盖，则称规则集R具有穷举覆盖。这个性质确保每一条记录都至少被R中的一条规则覆盖。
(2）如果规则不是穷举的，那么必须添加一个默认规则rd：（）->yd来覆盖那些未被覆盖的记录。默认规则的前件为空，当所有其他规则失效时被触发。yd是默认类，通常被指定为没有被现存规则覆盖的训练记录的多数类.
顺序覆盖算法
令E是训练记录，A是属性-值对的集合{（Aj,Vj）}
令Y0是类的有序集{y1,y2,...,yk}
令R={}是初始规则列表
for 每个类y in Y0-{yk} do
while 终止条件不满足 do
r = Learn-One-Rule(E,A,y)
从E重删除被r覆盖的训练记录
追加r到规则列表尾部:R=R V r
end while
end for
把默认规则{}->yk插入到规则列表R尾部
这里是直接方法里的Learn-One-Rule函数，采用贪心原则。因为要找最佳规则是个NP-HARD问题，通过贪心方式近似，先产生一个初始规则r,不断求精，然后满足某种终止条件，修剪规则以改进泛化误差。书中介绍了规则增长的策略，这里不详述。
对于候选规则的选择，这里使用似然比作为统计量：
$$R=2\sum_{i=1}^kf_ilog(\frac{f_i}{e_i})$$
或者规则覆盖率的度量Laplace以及FOIL信息增益
(在顺序覆盖算法中，需要删除覆盖到的训练记录，不然会重叠而误选。)可以使用RIPPER算法来建立规则集，而选取一个泛化能力较佳的模型。
跟决策树比较
可以看到与决策树的相似性，这里我们可以用决策树作为参考，间接产生规则。
它们间的比较：
- 规则集表达能力与之等价
- 基于规则分类器更易于解释，并性能相媲美
- 基于类的规则定序非常适应处理类分布不平衡的数据集
总结
算法思想：先从训练集生成规则集合，用合取条件表示。对每个待分类的记录和规则集合中的规则进行比较，如果某条规则被触发，则记录被分类。
