回归方法、决策树和合奏学习1 逻辑斯蒂回归2 判别分类2.1 线性判别（LDA）2.2 二次判别分析（QDA）3 K最近邻分类4 决策树4.1 回归树4.2 分类树5 合奏学习新思路：集成树5.1 思路3：装袋（Bagging）和自助抽样法（Bootstrap）5.2 思路4：随机森林5.3 思路5：提升算法（Boosting）

回归方法、决策树和合奏学习

1 逻辑斯蒂回归

因变量是定性变量（假设只取两个值），自变量可以定量、定性（哑变量）。输出结果在0到1之间，用逻辑斯蒂函数

p(X)=\frac{e^{\beta_{0}+\beta_{1} X}}{1+e^{\beta_{0}+\beta_{1} X}}

逻辑斯蒂函数可以等价地写成

\frac{p(X)}{1-p(X)}=e^{\beta_{0}+\beta_{1} X}

$(0, \infty)$ 取对数，得:

\log \left(\frac{p(X)}{1-p(X)}\right)=\beta_{0}+\beta_{1} X \text { . }

极大似然估计参数，似然函数：

L\left(\beta_{0}, \beta_{1}\right)=\prod_{i: y_{i}=1} p\left(x_{i}\right) \prod_{i^{\prime}: y_{i^{\prime}}=0}\left(1-p\left(x_{i^{\prime}}\right)\right)

梯度下降法或牛顿迭代法求系数估计。

2 判别分类

贝叶斯定理：

p_{k}(x):=P(Y=k \mid X=x)=\frac{\pi_{k} f_{k}(x)}{\sum_{l=1}^{K} \pi_{l} f_{l}(x)}

$\pi_k$ $k$ 类的样本占总样本的比例。

$x$ $p_k(x)$ 达到最大的那个类，这种方法被称为贝叶斯分类器。

2.1 线性判别（LDA）

$f_{k}(x)$ 是正态的:

f_{k}(x)=\frac{1}{\sqrt{2 \pi} \sigma_{k}} \exp \left\{-\frac{1}{2 \sigma_{k}^{2}}\left(x-\mu_{k}\right)^{2}\right\}, \quad x \in R

$\sigma_{1}^{2}=\cdots=\sigma_{K}^{2}$ $\sigma^{2}$ , 那么:

p_{k}(x)=\frac{\pi_{k} \frac{1}{\sqrt{2 \pi} \sigma} \exp \left\{-\frac{1}{2 \sigma^{2}}\left(x-\mu_{k}\right)^{2}\right\}}{\sum_{l=1}^{K} \pi_{l} \frac{1}{\sqrt{2 \pi} \sigma} \exp \left\{-\frac{1}{2 \sigma^{2}}\left(x-\mu_{l}\right)^{2}\right\}}

$p_{k}(x)$ 两边取对数，可知贝叶斯分类器其实是将观测x分到使得

\delta_{k}(x)=x \frac{\mu_{k}}{\sigma^{2}}-\frac{\mu_{k}^{2}}{2 \sigma^{2}}+\log \pi_{k}

$K =2,\ \pi_{1}=\pi_{2}$ $2x\left(\mu_{1}-\mu_{2}\right)>\mu_{1}{ }^{2}-\mu_{2}{ }^{2}$ 时，贝叶斯分类器将观测分入类1, 否则分入类2. 贝叶斯决策边界:

x=\frac{\mu_{1}^{2}-\mu_{2}^{2}}{2\left(\mu_{1}-\mu_{2}\right)}=\frac{\mu_{1}+\mu_{2}}{2} \text { . }

2.2 二次判别分析（QDA）

$N\left(\mu_{k}, \sigma_{k}^{2}\right)$ , 在这种假设下，贝叶斯分类器把观测分入使得

\begin{aligned} \delta_{k}(x) &=-\frac{1}{2 \sigma_{k}^{2}}\left(x-\mu_{k}\right)^{2}+\log \pi_{k} \\ &=-\frac{1}{2 \sigma_{k}^{2}} x^{2}+\frac{x \mu_{k}}{\sigma_{k}^{2}}-\frac{\mu_{k}^{2}}{2 \sigma_{k}^{2}}+\log \pi_{k} \end{aligned}

达到最大的那一类。

$p$ $p(p+1)/2$ $K$ $Kp(p+1)/2$ 个参数。所以LDA没有QDA分类器光滑，LDA拥有更小的方差和更大的预测偏差。样本量小，用LDA；样本量多，用QDA。

3 K最近邻分类

$k$ $k$ 最近邻方法不具有显式学习过程。

$k$ 最近邻法的三个基本要素：

$k$ 的选择
距离度量
决策规则

$k$ $x$ $N_{k}(x)$ $N_{k}(x)$ $x$ $y$

y=\arg \max _{c_{j}} \sum_{x_{i} \in N_{k}(x)} I\left\{y_{i}=c_{j}\right\}, \quad i=1, \cdots, N ; j=1, \cdots, L ;

$k=1$ $k$ $k$ 的大小。

4 决策树

分而治之

因变量数值型 - 回归问题 - 回归树

因变量类别型 - 分类问题 - 分类树

模型具有可读性
预测的速度快

特征 $f_1,...,f_n$ ，例如颜色、形状。

对分类问题，在学习/训练/归纳的时候，基于特征拟合一个分类器模型。模型可以根据特征对新的数据分类。

数据生成分布

我们要用概率模型去学习
数据/标签对服从某种概率分布，称为数据的生成分布

概率分布：描述某些事件的可能性，所有可能的结果及其发生的概率。

决策树：

树的内部节点用特征作标签
树枝用是否符合特征来标签
叶子为类别标签

递归法：计算每个特征的“得分”，选择分数最高的特征，根据该特征的数值对数据进行划分并递归调用。

得分可以用训练误差（训练集上的平均误差率）衡量，对于分类问题，最常见的“误差”是错分的个数。

划分数据特征的得分

处理二值特征

训练误差
基尼系数：划分后标签比例的平方和
熵：划分后标签分布的不确定性

敏感度：熵>基尼系数>训练误差

处理非二分值特征

多值特征：处理成多个划分，处理成多个二值划分
实值特征：用比较或范围划分

递归法截止条件基本情况：如果所有数据属于同一类，使用该标签创建叶节点或者所有数据有相同的特征。

过拟合发生在模型太过偏向训练数据时，目标是学习一个一般的模型，既要符合训练数据也要符合其他数据（比如测试数据）。递归法截止条件除基本情况外，还可以包括树达到一定深度、剩下一定数量/比例的数据、足够小训练误差、使用验证数据等，来阻止过拟合。

修剪

树构建之后，返回并“修剪”树，即移除树的一些底层部分。类似于提前停止，但在整个树构建好以后完成。

规则：正则化方法

4.1 回归树

$R_{1}, \ldots, R_{J}$ . RSS的定义是:

\sum_{j=1}^{J} \sum_{i \in R_{j}}\left(y_{i}-\hat{y}\left(R_{j}\right)\right)^{2}

$\hat{y}\left(R_{j}\right)$ $j$ 个矩形区域中训练观测的平均响应值。

$J$ 个矩形区域，一般采用自上而下、贪婪的方法：递归二叉分裂。

$X_{j}$ $s$ ，将自变量空间分为两个区域:

\begin{array}{l} \left\{X \mid X_{j}<s\right\} \\ \left\{X \mid X_{j} \geq s\right\} \end{array}

选择出来的两个区域要能够使RSS尽可能地减少。

重复至某个停止标准，如所有区域包含的观测个数都不大于5.

过拟合 -> 剪枝

成本复杂性剪枝

$\alpha$ $\alpha$ $T \subset T_{0}$ $\alpha$ 值给定时，其对应的子树需使下式最小

\sum_{m=1}^{|T|} \sum_{i: \boldsymbol{x}_{i} \in R_{m}}\left(y_{i}-\hat{y}\left(R_{m}\right)\right)^{2}+\alpha|T|

$|T|$ $R_m$ $m$ $\hat{y}\left(R_{m}\right)$ 是相应的响应预测值。

$\alpha$ ，使均方预测误差达到最小，从而确定最优子树。

4.2 分类树

递归二叉分裂。RSS的替代指标：

分类错误率

E_{m}=1-\max _{k} \hat{p}_{m k}

$\hat{p}_{\mathrm{mk}}$ $m$ $k$ $\max _{k} \hat{p}_{m k}$ 是分类正确率。

但分类错误率在分类树的构建中不够敏感，常用基尼指数和互熵衡量节点纯度。

基尼指数

G_{m}=\sum_{k=1}^{K} \hat{p}_{m k}\left(1-\hat{p}_{m k}\right) .

互熵

D_{m}=-\sum_{k=1}^{K} \hat{p}_{m k} \log \hat{p}_{m k}

5 合奏学习

基本想法：如果一个分类器运行良好，使用多个分类器共同作用。

$m$ $r$ 为一个分类器犯错误的概率，则

p(\text { error })=\sum_{i=(m+1) / 2}^{m}\left(\begin{array}{c} m \\ i \end{array}\right) r^{i}(1-r)^{m-i}

（二项分布的累积分布函数）

如何获得独立的分类器？

思路1：不同的学习方法

决策树，k-近邻，感知器，朴素贝叶斯，梯度下降变种1，梯度下降变种2……

优势：很多已有的方法，证明对一些问题表现较好

劣势：分类器经常不独立，犯同样的错误。比如这些都是线性模型，如果它们都犯同样错误，投票没有帮助。

思路2：分割训练数据

使用相同学习算法，但训练不同部分的训练数据。

优势：从不同数据学习，不会过拟合；容易实现；快速。

劣势：每个分类器只在小量的数据上训练，不一定比用全部数据加上正则化方法训练更好。

新思路：集成树

构建并整合多棵分类树
个体分类树应“好而不同”

两大类集成树的产生方法：

个体分类树之间不存在强依赖关系、同时生成的并行方法，如Bagging和随机森林
个体分类树之间存在强依赖关系、串行生成的序列化方法，如Boosting（Adaboost）

5.1 思路3：装袋（Bagging）和自助抽样法（Bootstrap）

装袋（Bagging）主要关注降低预测模型的方差。

$n$ $Z_{1}, \cdots, Z_{n}$ $\sigma^{2}$ $\bar{Z}=\frac{1}{n} \sum_{i=1}^{n} Z_{i}$ $\sigma^{2} / \mathrm{n}$ .

启发：从总体中抽取多个训练集，对每个训练集分别建立预测模型，再对由此得到的全部预测模型求平均，从而降低方差，得到一个集成模型。在实际中，不容易得到多个训练集。自助抽样法(Bootstrap)可以解决这个问题。

自助抽样法(Bootstrap)

训练数据和原始训练数据大小一样，使用训练数据作为数据生成分布，通过有重复抽样生成训练数据。

$B$ $B$ $B$ 个分类器中获得多数投票。

$\hat{f}^{1}(x), \cdots, \hat{f}^{B}(x)$ , 然后求平均，得到一个低方差的模型:

\hat{f}_{\text {avg }}(\boldsymbol{x})=\frac{1}{B} \sum_{b=1}^{B} \hat{f}^{b}(\boldsymbol{x}) .

$B$ 足够大，可稳定预测准确率。

$B$ 棵个体分类树上求平均值。平均值越大就说明这个自变量越重要。

On average, how many of the original observations are not present in an average bootstrap sample?

$n$ 次抽样中任何一次都没被选中的概率为

p=(1-1/n)^n.

$n$ 变大时，

\lim_{n\rightarrow \infty}(1-1/n)^n=1/e\approx 0.368,

$p\approx 0.368$ $n$ $p$ $X\sim B(n,p)$ ，即

P(X=k)=f(k,n,p)=\left(\begin{array}{c} n \\ k \end{array}\right)p^k(1-p)^{n-k},

$E[X]=np$ $1-p$ ）。

什么时候装袋表现较好

装袋倾向于减少分类器的方差；通过投票，分类器对于有噪音的数据更加稳健。

装袋对于以下分类器有用：

不稳定的分类器：训练集中的微小变化产生了非常不同的模型
容易过度拟合的分类器，装袋有和正则化类似的作用

5.2 思路4：随机森林

以决策树为基础构建Bagging分类树的基础上，进一步在决策树的训练过程中引入了自变量的随机选择，从而达到对树的去相关（decorrelating），实现对Bagging的改进。

$q\ (1 \leq q \leq p)$ $q$ $q$ $q=p$ $q$ $p$ 的平方根。

若个体分类树有高度相关性，对高度相关的变量求平均无法大幅度减少方差。而随机森林对不相关变量求平均，可大幅度降低方差。

样本多样性来自

Bagging：样本扰动
随机森林：样本扰动+自变量扰动

5.3 思路5：提升算法（Boosting）

强分类器

$\epsilon$ $p$ $1-p$ $<\epsilon$ 的分类器。

弱分类器

$p$ $1-p$ $<0.5$ 的分类器。

弱分类器更好构造，通过Boosting提升。

训练：开始给所有数据赋予相同权重，迭代中学习一个弱分类器并保存，然后改变数据权重。对正确分类的数据减小权重，对错误分类的数据增加权重，从而学习另外一个弱分类器。

分类：从每个学习到的分类器做预测，基于每个弱分类器的表现对预测做加权投票。

Boosting可将弱分类器提升为强分类器。根据分类器的表现对训练样本分布进行调整，使先前分类器错分的训练样本在后续得到更多的关注。

Adaboost是Boosting中的一种，算法：

输入 $D=\left\{\left(\boldsymbol{x}_{1}, y_{1}\right), \cdots,\left(\boldsymbol{x}_{m}, y_{m}\right)\right\}$ $\mathfrak{L} ;$ $T$ ;

过程：

$\mathcal{D}_{1}(\boldsymbol{x})=1 / m$ $t=1, \cdots, T$ $h_{t}=\mathfrak{L}\left(D, \mathcal{D}_{t}\right)$ $\epsilon_{t}=P_{\boldsymbol{x} \sim \mathcal{D}_{t}}\left(h_{t}(\boldsymbol{x}) \neq f(\boldsymbol{x})\right)$ $\epsilon_{t}>0.5$ $\alpha_{t}=\frac{1}{2} \ln \left(\frac{1-\epsilon_{t}}{\epsilon_{t}}\right)$ ; (g) 令

\begin{aligned} \mathcal{D}_{t+1}(\boldsymbol{x}) &=\frac{\mathcal{D}_{f}(\boldsymbol{x}) \exp \left(-\alpha_{t} f(\boldsymbol{x}) h_{t}(\boldsymbol{x})\right)}{Z_{t}} \\ &=\frac{\mathcal{D}_{t}(\boldsymbol{x})}{Z_{t}} \times\left\{\begin{array}{ll} \exp \left(-\alpha_{t}\right), & \text { 如果 } h_{t}(\boldsymbol{x})=f(\boldsymbol{x}) \\ \exp \left(\alpha_{t}\right), & \text { 如果 } h_{t}(\boldsymbol{x}) \neq f(\boldsymbol{x}) \end{array}\right. \end{aligned}

$Z_{t}$ 是归一化常数; (h) 循环结束.

输出 $H(\boldsymbol{x})=\operatorname{sign}\left(\sum_{t=1}^{T} \alpha_{t} h_{t}(\boldsymbol{x})\right)$ .

从偏差-方差权衡角度，Adaboost更关注降低偏差。

提升决策树桩

使用boosting算法的最常用的分类器之一是决策树：可以使用浅（2-3级树），更常见的是1级树，叫决策树桩，询问有关单个特征的一个问题。

线性分类器，每个树桩定义该维度的权重，如果学习了那个维度的多个树桩，那么它就是加权平均值。

boosting在各种问题上应用非常成功，即使经过大量迭代也不会过度拟合。