二.西瓜书——线性模型、决策树

第三章线性模型

1.线性回归

“线性回归”(linear regression)试图学得一个线性模型以尽可能准确地预测实值输出标记.

2.对数几率回归

假设我们认为示例所对应的输出标记是在指数尺度上变化，那就可将输出标记的对数作为线性模型逼近的目标，即

$lny=w^Ta+b.$

由此，引入对数几率回归：

称为“几率”(odds),反映了a作为正例的相对可能性.对几率取对数则得到“对数几率”(log odds,亦称logit)

3.线性判别分析

LDA的思想非常朴素：给定训练样例集，设法将样例投影到一条直线上，使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离；在对新样本进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定新样本的类别.

4.多分类学习

利用二分类学习器来解决多分类问题:

“一对一”(One vs.One,简称OvO):OvO将这N个类别两两配对，从而产生N(N-1)/2个二分类任务
“一对其余”(One vs.Rest,简称OvR)：OvR则是每次将一个类的样例作为正例、所有其他类的样例作为反例来训练N个分类器.
MvM是每次将若干个类作为正类，若干个其他类作为反类.显然，OvO和 OvR是MvM的特例.

MvM的正、反类构造必须有特殊的设计，不能随意选取.这里我们介绍一种最常用的 MvM 技术：“ 纠错输出码 ”(E rror Correcting Ou t p u t C o d es , 简称 E C O C ) .

ECOC Dietterich and Bakiri,1995]是将编码的思想引入类别拆分，并尽可能在解码过程中具有容错性.ECOC工作过程主要分为两步：

编码：对N个类别做 M 次划分，每次划分将一部分类别划为正类，一部分划为反类，从而形成一个二分类训练集；这样一共产生M个训练集，可训练出M个分类器.
- 解码：M个分类器分别对测试样本进行预测，这些预测标记组成一个编码.将这个预测编码与每 个类别各自的编码进行比较，返回其中距离最小的类别作为最终预测结果.
  
  为什么称为“纠错输出码”呢?这是因为在测试阶段，ECOC编码对分类器的错误有一定的容忍和修正能力.例如图3.5(a)中对测试示例的正确预测编码是 ( - 1 , + 1 , + 1 , - 1 , + 1 ) , 假设在预测时某个分类器出错了，例如 f 2 出错从而导致了错误编码(-1,-1,+1,-1,+1),但基于这个编码仍能产生正确的最终分类结果C3.一般来说，对同一个学习任务，ECOC编码越长，纠错能力越强.然而，编码越长，意味着所需训练的分类器越多，计算、存储开销都会增大；另一方面，对有限类别数，可能的组合数目是有限的，码长超过一定范围后就失去了
  
  意义 .
  
  5.类别不平衡问题
  
  类别不平衡(class-imbalance)就是指分类任务中不同类别的训练样例数目差别很大的情况.
  
  类别平衡时， y > 0.5 时判别为正例，否则为反例 . y实际上表达了正例的可能性，几率分类规则为:
  
  类别不平衡时，只要分类器的预测几率高于观测几率就应判定为正例，即

此时，需要进行再缩放:

大体上有三类做法：

第一类是直接对训练集里的反类样例进行“欠采样”(undersampling),即去除一些反例使得正、反例数目接近，然后再进行学习；
第二类是对训练集里的正类样例进行“过采样”(oversampling),即增加一些正例使得正、反例数目接近，然后再进行学习；
第三类则是直接基于原始训练集进行学习，但在用训练好的分类器进行预测时，将式(3.48)嵌入到其决策过程中，称为“阈值移动”(threshold-moving).

欠采样法的时间开销通常远小于过采样法，因为前者丢弃了很多反例，使得分类器训练集远小于初始训练集，而过采样法增加了很多正例，其训练集大于初始训练集.需注意的是，过采样法不能简单地对初始正例样本进行重复采样，否则会招致严重的过拟合；

第四章决策树

1.基本流程

决策树将样本根据属性测试的结果被划分到子结点中；根结点包含样本全集.从根结点到每个叶结点的路径对应了一个判定测试序列.决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”(divide-and-conquer)策略

策树的生成是一个递归过程.在决策树基本算法中，有三种情形会导致递归返回：

(1)当前结点包含的样本全属于同一类别，无需划分；
(2)当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；利用当前结点的后验分布
(3)当前结点包含的样本集合为空，不能划分.当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别.把父结点的样本分布作为当前结点的先验分布.

2.划分选择

一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高.

（1）信息增益

信息熵的定义

Ent(D)的值越小，则D的纯度越高.

信息增益的计算为父节点的信息熵减去划分后各子节点的信息熵之和，其中子节点信息熵的权重为第v个分支节点样本数/父节点样本数

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯 度提升”越大.ID3决策树学习算法以信息增益为准则来选择划分属性.

例如：

（2）增益率

当考虑编号时，每个类别仅仅包含1个样本，此时信息增益最大，这些分支结点的纯度已达最大.然而，这样的决策树显然不具有泛化能力，无法对新样本进行有效预测.

也就是说，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法[Quinlan,1993]不直接使用信息增益，而是使用“增益率”(gainratio)来选择最优划分属性采用与式(4.2)相同的符号表示，增益率定义为

IV(a)称为属性a的“固有值”(intrinsic value)[Quinlan,1993].属性a的可能取值数目越多(即V越大),则IV(a)的值通常会越大.

需注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5

算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的.

(3)基尼指数

CART决策树[Breiman et al.,1984]使用“基尼指数”(Gini index)来选择划分属性.采用与式(4.1)相同的符号，数据集D的纯度可用基尼值来度量：

直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率.因此，Gini(D)越小，则数据集D的纯度越高

采用与式(4.2)相同的符号表示，属性a的基尼指数定义为

3.剪枝处理

预剪枝：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；
后剪枝：先从训练集生成一棵完整的决策树然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点.

预剪枝使得决策树的很多分支都没有“展开”,这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销.但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险.

后剪枝决策树通常比预剪枝决策树保留了更多的分支.一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树.但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多.