机器学习算法原理——决策树

决策树

已知：训练集：
$$T=\{(x_1,y_1),(x_2,y_2)\cdot \cdot \cdot \cdot ,(x_N,y_N)\}$$
其中 x i = ( x i ( 1 ) , x i ( 2 ) , ⋯   , x i ( n ) ) T ,    y i ∈ { 1 , 2 , ⋯   , K } ,    i = 1 , 2 , ⋯   , N ; x_{i}=(x_{i}^{(1)},x_{i}^{(2)},\cdots,x_{i}^{(n)})^{T},\;y_{i}\in\{1,2,\cdots,K\},\;i=1,2,\cdots,N; xi​=(xi(1)​,xi(2)​,⋯,xi(n)​)T,yi​∈{1,2,⋯,K},i=1,2,⋯,N;

目的：构造决策树，并对实例正确分类

分类决策树模型是一种描述对实例进行分类的树形结构。

If-then：决策树是通过一系列规则对数据进行分类的过程。

步骤：

• 构建根结点；
• 选择最优特征，以此分割训练数据集；
• 若子集被基本正确分类，构建叶结点，否则，继续选择新的最优特征；
• 重复以上两步，直到所有训练数据子集被正确分类。

条件概率分布

• 决策时：给定特征条件下类的 $P(Y|X)$ ；
• 条件概率分布：特征空间的一个划分（Partition）；
• 划分：单元（Cell）或区域（Region）互不相交。

所有区域合在一起，就是整个特征空间，一个单元对应一条路径。

决策树的条件概率分布由各个单元给定条件下类的条件概率分布组成。

决策树学习

本质：从训练数据集中归纳出一组分类规则，与训练数据集不相矛盾

假设空间：由无穷多个条件概率模型组成

一棵好的决策树：与训练数据矛盾较小，同时具有很好的泛化能力

策略：最小化损失函数

特征选择：递归选择最优特征生成:对应特征空间的划分，直到所有训练子集被基本正确分类

剪枝：避免过拟合，具有更好的泛化能力

特征选择

信息增益

熵表示随机变量的不确实性：
$$H(X)=-\sum _{i=1}^n{p}_i\log p_i$$
或：
$$H(p)=-\sum _{i=1}^n{p}_i\log p_i$$
随机变量的取值等概率分布的时候，相应的熵最大。
$$0\le H(p)\le \log n$$
条件熵：
$$H(Y|X)=\sum _{i=1}^n{p}_{i}H(Y|X=x_i)$$
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，则为经验熵（empirical entropy）和经验条件熵（empirical condition entropy）。

信息增益：得知特征 $A$ 而使类 $Y$ 的信息的不确定性减少的程度。
$$g(D,A)=H(D)-H(D|A)$$

信息增益的算法

设训练数据集为 $D$ ，$|D|$ 表示其样本容量，即样本个数。设有 $K$ 个类 $C_k$ ，$k=1,2,\cdots ,K$， $|C_k|$ 为属于类 $C_k$ 的样本个数，${\sum }_{k=1}^K|C_k|=|D|$ 。设特征 $A$ 有 $n$ 个不同的取值 { a 1 , a 2 , ⋯   , a n } \{a_1, a_2, \cdots, a_n\} {a1​,a2​,⋯,an​} ，根据特征 $A$ 的取值将 $D$ 划分为 $n$ 个子集 $D_1,D_2,\cdots ,D_n$ ，$|D_i|$ 为 $D_i$ 的样本个数，${\sum }_{i=1}^n|D_i|=|D|$ 。记子集 $D_i$ 中属于类 $C_k$ 的样本的集合为 $D_{ik}$ ，即 $D_{ik}=D_i\cap C_k$ ，$|D_{ik}|$ 为 $D_{ik}$ 的样本个数。

输入：训练数据集 $D$ 和特征 $A$

输出：特征 $A$ 对 $D$ 的信息增益 $g(D,A)$

• 计算经验熵 $H(D)$ ：
  $$H(D)=-\sum _{k=1}^K\frac{|C_k|}{|D|}{\log }_2\frac{|C_k|}{|D|}$$

• 计算经验条件熵 $H(D|A)$ ：

$$H(D|A)=\sum _{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum _{i=1}^n\frac{|D_i|}{|D|}\sum _{k=1}^K\frac{|D_{ik}|}{|D_i|}{\log }_2\frac{|D_{ik}|}{|D_i|}$$

• 计算信息增益：
  $$g(D,A)=H(D)-H(D|A)$$

信息增益比

以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比（information gain ratio）可以对这一问题进行校正。

特征 $A$ 对训练数据集 $D$ 的信息增益比 $g_R(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 $D$ 关于特征$A$ 的值的熵 $H_A(D)$ 之比，即
$$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$
其中，$H_A(D)=-{\sum }_{i=1}^n\frac{|D_i|}{|D|}{\log }_2\frac{|D_i|}{|D|}$ ， $n$ 是特征 $A$ 取值的个数。

决策树的生成

ID3算法

输入：训练数据集 $D$ 、特征集 $A$ 、阈值 $\epsilon $

输出：决策树 $T$

• 判断 $T$ 是否需要选择特征生成决策树；
  • 若 $D$ 中所有实例属于同一类，则 $T$ 为单结点树，记录实例类别 $C_k$ ，以此作为该结点的类标记，并返回 $T$ ；
  • 若 $D$ 中所有实例无任何特征（$A=\varnothing$），则 $T$ 为单结点树，记录 $D$ 中实例个数最多类别 $C_k$ ，以此作为该结点的类标记，并返回 $T$ ；
• 否则，计算 $A$ 中各特征的信息增益，并选择信息增益最大的特征 $A_g$ ；
  • 若 $A_g$ 的信息增益小于 $ϵ$ ，则 $T$ 为单结点树，记录 $D$ 中实例个数最多类别 $C_k$ ，以此作为该结点的类标记，并返回 $T$ ；
  • 否则，按照 $A_g$ 的每个可能值 $a_i$ ，将 $D$ 分为若干非空子集 $D_i$ ，将 $D_i$ 中实例个数最多的类别作为标记，构建子结点，以结点和其子结点构成 $T$ ，并返回 $T$ ；
• 第 $i$ 个子结点，以 $D_i$ 为训练集，$A-A_i$ 为特征集合，递归地调用以上步骤，得到子树 $T_i$ 并返回。

C4.5算法

输入：训练数据集 $D$ 、特征集 $A$ 、阈值 $\epsilon $

输出：决策树 $T$

• 判断 $T$ 是否需要选择特征生成决策树；
  • 若 $D$ 中所有实例属于同一类，则 $T$ 为单结点树，记录实例类别 $C_k$ ，以此作为该结点的类标记，并返回 $T$ ；
  • 若 $D$ 中所有实例无任何特征（$A=\varnothing$），则 $T$ 为单结点树，记录 $D$ 中实例个数最多类别 $C_k$ ，以此作为该结点的类标记，并返回 $T$ ；
• 否则，计算 $A$ 中各特征的信息增益比，并选择信息增益比最大的特征 $A_g$ ；
  • 若 $A_g$ 的信息增益比小于 $ϵ$ ，则 $T$ 为单结点树，记录 $D$ 中实例个数最多类别 $C_k$ ，以此作为该结点的类标记，并返回 $T$ ；
  • 否则，按照 $A_g$ 的每个可能值 $a_i$ ，将 $D$ 分为若干非空子集 $D_i$ ，将 $D_i$ 中实例个数最多的类别作为标记，构建子结点，以结点和其子结点构成 $T$ ，并返回 $T$ ；
• 第 $i$ 个子结点，以 $D_i$ 为训练集，$A-A_i$ 为特征集合，递归地调用以上步骤，得到子树 $T_i$ 并返回。

剪枝

优秀的决策树：
在具有好的拟合和泛化能力的同时，

• 深度小；
• 叶结点少；
• 深度小并且叶结点少。

误差：训练误差、测试误差

过拟合：训练误差低，测试误差高（模型结构过于复杂）

欠拟合：训练误差高，测试误差低（模型结构过于简单）

剪枝：处理决策树的过拟合问题

预剪枝：生成过程中，对每个结点划分前进行估计，若当前结点的划分不能提升泛化能力，则停止划分，记当前结点为叶结点；

后剪枝：生成一棵完整的决策树之后，自底而上地对内部结点考察，若此内部结点变为叶结点，可以提升泛化能力，则做此替换。

预剪枝

常用的预剪枝方法：

• 限定决策树的深度
• 设定一个阈值（阈值过大可能会导致决策树过于简单）
• 设置某个指标（常用基于测试集上的误差率），比较结点划分前后的泛化能力

后剪枝

降低错误剪枝（Reduce Error Pruning）

原理：自下而上，使用测试集来剪枝。对每个结点，计算剪枝前和剪枝后的误判个数，若是剪枝有利于减少误判（包括相等的情况），则减掉该结点所在分枝。

错误率在验证集上计算出来。

• 计算复杂性是线性的
• 操作简单，容易理解
• 受测试集影响大，如果测试集比训练集小很多，会分类的精度，容易欠拟合。

悲观错误剪枝（Pessimistic Error Pruning）

原理：根据剪枝前后的错误率来决定是否剪枝。和降低错误剪枝（REP）不同之处在于，悲观错误剪枝（PEP）只需要训练集即可，不需要验证集，并且PEP是自上而下剪枝的。

设 $L$ 为叶子结点的个数， $Lea{f}_i$ 为第 $i$ 个叶子结点， $Leaf$ 剪枝后的叶子结点， $N(T)$ 为目标子树所包含的样本总个数。

• 计算剪枝前目标子树每个叶子结点的误差，并进行连续修正：

$$Error(Lea{f}_i)=\frac{error(Lea{f}_i)+0.5}{N(T)}$$

• 计算剪枝前目标子树的修正误差：

$$Error(T)=\sum _{i=1}^{L}Error\left({Leaf}_i\right)=\frac{{\sum }_{i=1}^{L}error\left({Leaf}_i\right)+0.5\ast L}{N(T)}$$

• 计算剪枝前目标子树误判个数的期望值：

$$E(T)=N(T)\times Error(T)=\sum _{i=1}^{L}error({Leaf}_i)+0.5\ast L$$

• 计算剪枝前目标子树误判个数的标准差：

$$std(T)=\sqrt{N(T)\times Error(T)\times (1-Error(T))}$$

• 计算剪枝前误判上限（即悲观误差）：

$$E(T)+std(T)$$

• 计算剪枝后该结点的修正误差：

$$Error(Leaf)=\frac{error(Leaf)+0.5}{N(T)}$$

• 计算剪枝后该结点误判个数的期望值：

$$E(Leaf)=error(Leaf)+0.5$$

• 比较剪枝前后的误判个数，如果满足以下不等式，则剪枝；否则，不剪枝。

$$E(Leaf)<E(T)+std(T)$$

最小误差剪枝（Minimum Error Pruning）

原理：根据剪枝前后的最小分类错误概率来决定是否剪枝。自下而上剪枝，只需要训练集即可。

设 $P{r}_k(T)$ 为 $T$ 属于 $k$ 类别的先验概率， $m$ 表示先验概率对后验概率的影响， $w_i$ 为叶子结点在 $T$ 中的权重。

• 在结点 $T$ 处，属于类别 $k$ 的概率：

$$\begin{array}{rl}& P_k(T)=\frac{n_k(T)+P{r}_k(T)\times m}{N(T)+m}\\ & m\to 0,P_k(T)\to \frac{n_k(T)}{N(T)}\\ & m\to \infty ,P_k(T)\to P{r}_k(T)\end{array}$$

• 在结点 $T$ 处，预测错误率：

E r r o r ( T ) = m i n { 1 − P k ( T ) } = m i n { N ( T ) − n k ( T ) + m ( 1 − P r k ( T ) ) N ( T ) + m } Error(T)=min\{1{-}P_{k}(T)\}=min\left\{{\frac{{N}(T)-n_{k}(T)+m(1-Pr_{k}(T))}{{N}(T)+m}}\right\} Error(T)=min{1−Pk​(T)}=min{N(T)+mN(T)−nk​(T)+m(1−Prk​(T))​}

• 若先验概率确定，就是以 $m$ 作为变量，求取 $Error(T)$ 的最小值：

$$\arg \underset{m}{\min }Error(T)$$

• 在无任何假设的情况下，通常假设各类别等概率出现，先验概率： $\mathcal{P}{r}_k(T)=\frac{1}{K}$ ，为便于演示，此处取 $m=1$ ：

$$Error(T)=\frac{N(T)-n_k(T)+K-1}{N(T)+K}$$

• 步骤：

  • 计算剪枝前目标子树每个叶子结点的预测错误率：

  $$Error(Lea{f}_i)=\frac{N(Lea{f}_i)-n_k(Lea{f}_i)+K-1}{N(Lea{f}_i)+K}$$

  • 计算剪枝前目标子树的预测错误率：

  $$Error(Leaf)=\sum _{i=1}^L{w}_{i}Error(Lea{f}_i)=\sum _{i=1}^L\frac{N(Lea{f}_i)}{N(T)}Error(Lea{f}_i)$$

  • 计算剪枝后目标子树的预测错误率：

  $$Error(T)=\frac{N(T)-n_k(T)+K-1}{N(T)+K}$$

  • 比较剪枝前后的预测错误率，如果满足以下不等式，则剪枝；否则，不剪枝。

  $$Error(T)<Error(Leaf)$$

基于错误的剪枝（Error Based Pruning）

原理：根据剪枝前后的误判个数来决定是否剪枝。自下而上剪枝，只需要训练集即可。

设 $e(T)$ 为午盘个数，$N(T)$ 为样本个数，$\alpha$ 为上分位数， $q_{\alpha }$ 为置信水平，常取 25% 。

• 计算剪枝前目标子树每个叶子结点的误判率上界：

$$U_{CF}\left(e\left({Leaf}_i\right),N\left({Leaf}_i\right)\right)=\frac{e\left({Leaf}_i\right)+0.5+\frac{q_{\alpha }^2}{2}+q_{\alpha }\sqrt{\frac{\left(e\left({Leaf}_i\right)+0.5\right)\left(N\left({Leaf}_i\right)-e\left({Leaf}_i\right)-0.5\right)}{N\left({Leaf}_i\right)}+\frac{q_{\alpha }^2}{4}}}{N\left({Leaf}_i\right)+q_{\alpha }^2}$$

• 计算剪枝前目标子树的误判个数上界：

$$E(Leaf)=\sum _{i=1}^{L}N\left({Leaf}_i\right)U_{CF}\left(e\left({Leaf}_i\right),N\left({Leaf}_i\right)\right)$$

• 计算剪枝后目标子树的误判率上界：

$$U_{CF}\left(e\left(T\right),N\left(T\right)\right)=\frac{e\left(T\right)+0.5+\frac{q_{\alpha }^2}{2}+q_{\alpha }\sqrt{\frac{\left(e\left(T\right)+0.5\right)\left(N\left(T\right)-e\left(T\right)-0.5\right)}{N\left(T\right)}+\frac{q_{\alpha }^2}{4}}}{N\left(T\right)+q_{\alpha }^2}$$

• 计算剪枝后目标子树的误判个数上界：

$$E(T)=N(T)U_{CF}(e(T),N(T))$$

• 比较剪枝前后的误判个数上界，如果满足以下不等式，则剪枝;否则，不剪枝。

$$E(T)<E(Leaf)$$

代价-复杂度剪枝（Cost-Complexity Pruning）

原理：根据剪枝前后的损失函数来决定是否剪枝。

设 $C(T)$ 为 $T$ 在训练集中的预测误差， $|T|$ 为树 $T$ 的叶结点个数，反映 $T$ 的复杂度（考验泛化能力）， $t$ 是树 $T$ 的叶结点，该叶结点有 $N_t$ 个样本点，其中 $k$ 类的样本点有 $N_{tk}$ 个， $H_t(T)$ 为叶结点 $t$ 上的经验熵 ， $\alpha \ge 0$ 为惩罚参数。

• 损失函数：

$$C_{\alpha }=C(T)+\alpha |T|$$

​ 其中， $C(T)={\sum }_{t=1}^{|T|}{N}_t{H}_t(T)=-{\sum }_{t=1}^{|T|}{\sum }_{k=1}^K{N}_{tk}\log \frac{N_{tk}}{N_t}$

• 正则化：

$$\underset{f\in \mathcal{F}}{\min }\frac{1}{N}\sum _{i=1}^{N}L(y_i,f(x_i))+\lambda J(f)$$

• 剪枝前的决策树记做下 $T_A$ ，计算每个叶子结点 $t$ 的经验熵（若使用基尼系数，则为 CART 算法）：

$$H_t=-\sum _{k=1}^K\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}$$

• 剪枝前决策树的损失函数为：

$$C_{\alpha }(T_A)=C(T_A)+\alpha |T_A|$$

• 剪枝后的决策树记做 $T_B$ ，损失函数为：

$$C_{\alpha }\left(T_B\right)=C\left(T_B\right)+\alpha \left|T_B\right|$$

• 比较剪枝前后的损失函数，如果满足以下不等式，则剪枝；否则，不剪枝。

$$C_{\alpha }\left(T_B\right)\le C_{\alpha }\left(T_A\right)$$

CART算法

假设现在有 $K$ 个类，样本点属于第 $k$ 个类的概率为 $p_k$ ，则概率分布的基尼指数为：
$$\mathrm{Gini}(p)=\sum _{k=1}^K{p}_k\left(1-p_k\right)=1-\sum _{k=1}^K{p}_k^2$$
二分类：
$$\mathrm{Gini}(p)=2p(1-p)$$
样本集 $D$ 的基尼系数：
$$\mathrm{Gini}(D)=1-\sum _{k=1}^K{\left(\frac{\left|C_k\right|}{|D|}\right)}^2$$
特征 $A$ 条件下，样本集 $D$ 的基尼指数为：
$$\mathrm{Gini}(D,A)=\frac{\left|D_1\right|}{|D|}\mathrm{Gini}\left(D_1\right)+\frac{\left|D_2\right|}{|D|}\mathrm{Gini}\left(D_2\right)$$

CART分类树

输入：训练数据集 $D$ 、特征集 $A$ 、阈值 $ϵ$

输出：CART决策树 $T$

• 从根节点出发，进行操作，构建二叉树；
• 结点处的训练数据集为 $D$ ，计算现有特征对该数据集的基尼指数，并选择最优特征。
  • 在特征 $A_g$ 下，对其可能取的每个值 $a_g$ ，根据样本点对 $A_g=a_g$ 的测试为“是”或“否”，将 $D$ 分割成 $D_1$ 和 $D_2$ 两部分，计算 $A_g=a_g$ 时的基尼指数。
  • 选择基尼指数最小的那个值作为该特征下的最优切分点。
  • 计算每个特征下的最优切分点，并比较在最优切分下的每个特征的基尼指数，选择基尼指数最小的那个特征，即最优特征。
• 根据最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
• 分别对两个子结点递归地调用上述步骤，直至满足停止条件（比如结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类)，或者没有更多特征），即生成 CART 决策树。

CART回归树

假设将输入空间划分为 $M$ 个单元 $R_1,R_2,\cdots ,R_m$ ，并在每个单元 $R_m$ 上有一个固定的输出值 $C_m$ 。回归树模型可表示为：
$$f(x)=\sum _{m=1}^M{c}_{m}I\left(x\in R_m\right)$$
平方误差：
$$\sum _{x_i\in R_m}{\left(y_i-f\left(x_i\right)\right)}^2$$
最优输出：
$${\hat{c}}_m=\mathrm{average}\left(y_i\mid x_i\in R_m\right)$$
选择第 $x^{(j)}$ 个变量和取值 $s$ ，分别作为切分变量和切分点，并定义两个区域：
$$R_1(j,s)=\left\{x\mid x^{(j)}⩽s\right\}{R}_2(j,s)=\left\{x\mid x^{(j)}>s\right\}$$
寻找最优切分变量 $j$ 和最优切分点 $s$：
$$\underset{j,s}{\min }\left[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}{\left(y_i-c_1\right)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}{\left(y_i-c_2\right)}^2\right]$$
对固定输入变量 $j$ 可以找到最优切分点 $s$ ：
$$\begin{array}{r}{\hat{c}}_1=\mathrm{ave}\left(y_i\mid x_i\in R_1(j,s)\right)\\ {\hat{c}}_2=\mathrm{ave}\left(y_i\mid x_i\in R_2(j,s)\right)\end{array}$$

输入：训练数据集 $D$ ，停止条件

输出：CART 决策树 $T$

• 从根节点出发，进行操作，构建二叉树；

• 结点处的训练数据集为 $D$ ，计算变量的最优切分点，并选择最优变量。
  $$\underset{j,s}{\min }\left[\underset{c_1}{\min }\sum _{x_i\in R_1(j,s)}{\left(y_i-c_1\right)}^2+\underset{c_2}{\min }\sum _{x_i\in R_2(j,s)}{\left(y_i-c_2\right)}^2\right]$$

  • 在第 $j$ 变量下，对其可能取的每个值 $s$ ，根据样本点分割成 $R_1$ 和 $R_2$ 两部分，计算切分点为 $s$ 时的平方误差。

  • 选择平方误差最小的那个值作为该变量下的最优切分点。

  • 计算每个变量下的最优切分点，并比较在最优切分下的每个变量的平方误差，选择平方误差最小的那个变量，即最优变量。

• 根据最优特征与最优切分点$(j,s)$，从现结点生成两个子结点，将训练数据集依变量配到两个子结点中去，得到相应的输出值。

$$R_1(j,s)=\left\{x\mid x^{(j)}⩽s\right\},R_2(j,s)=\left\{x\mid x^{(j)}>s\right\}$$

$${\hat{c}}_m=\frac{1}{N_m}\sum _{x_i\in R_m(j,s)}{y}_i,x\in R_m,m=1,2$$

• 继续对两个子区域调用上述步骤，直至满足停止条件，即生成 CART 决策树。

$$f(x)=\sum _{m=1}^M{c}_{m}I\left(x\in R_m\right)$$

总结归纳

• 决策树不一定是二叉树，可能是多叉树，即：决策树可以做多分类。

• 决策树的内部结点表示一个特征或属性，叶结点表示一个类。

• 决策树符合 if-then 规则，互斥且完备，即：每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。

• 决策树还可以看成是由给定条件下类的条件概率分布组成的，即在上一个特征发生的条件下求取下一个特征发生的概率。

• 任何一棵多叉树都可以表示成二叉树的形式，这也是为什么在悲观错误剪枝（Pessimistic Error Pruning）和基于错误的剪枝（Error Based Pruning）中具有二项分布的身影 。

• 随机变量的取值等概率分布的时候，相应的熵最大。通俗理解为：等概率分布时，随机变量取到每一个值的概率都相同，此时随机变量的不确定性最大。

• 决策树还表示给定特征条件下类的概率分布，即在上一个特征发生的前提下寻找下一个特征发生的概率。

$$g(D,A)=H(D)-H(D|A)$$

​ 要使 $g(D,A)$ 变小，需使 $H(D|A)$ 变大，表示为：已知特征 $A$ 的条件下对集合 $D$ 的分类效果好。

• 决策树生成过程中，若特征 $A_g$ 只有一种可能值，此时 $H(D)$ 和 $H(D|A)$ 均为 0 ，信息增益也为 0 ，必小于 $ϵ$ ，应生成叶结点。

• 决策树生成时，当所有特征的信息增益均小于 $ϵ$ 时，决策树完成构建。

• 以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。使用信息增益比（information gain ratio）可以对这一问题进行校正。

• ID3算法和C4.5算法，只有划分依据不同，ID3算法依据信息增益划分，C4.5算法依据信息增益比划分。

• C4.5算法较ID3算法，它可以处理连续型的数据，但不适用于大型数据。

• 预剪枝是自上而下的过程，后剪枝是自下而上的过程。其中悲观错误剪枝（Pessimistic Error Pruning）较为特殊，它归属于后剪枝，但却是自上而下剪枝。

• 连续性修正：

  • 将伯努利分布 $B(1,p)$ 重复 $n$ 次，就是二项分布 $B(n,p)$ 。

  • 棣莫弗-拉普拉斯中心极限定理：

    ​ 设随机变量 $Y_n\sim B(n,p)(0<p<1,b\ge 1)$

  $$\underset{n\to \infty }{\lim }P\left\{a<\frac{x_n-np}{\sqrt{np(1-p)}}\le b\right\}={\int }_a^b\frac{1}{\sqrt{2\pi }}{e}^{-\frac{t^2}{2}}dt$$

  ​ 其中，$\frac{1}{\sqrt{2\pi }}{e}^{-\frac{t^2}{2}}$ 就是正态分布的概率密度函数。

  ​ 该定理表明：正态分布是二项分布的极限分布。

  ​ 即：$n\to \infty ,B(n,p)\to B(np,np(1-p))$

  • 二项分布为离散型随机变量，分布函数是阶梯状；正态分布为连续性随机变量，而正态分布的曲线穿过了每个阶梯的中心点。在 $[a,a+0.5)$ 区间内，二项分布的分布函数大于正态分布；在 $(a+0.5,a+1]$ 区间内，正态分布的分布函数大于二项分布。

  • 若直接用正态分布求概率，结果偏大，体现在概率直方图中：

    • 当求取坐标为 $(a,b)$ 时，二项分布会求取 $[a+1,b-1]$ 的面积，正态分布则会包含一部分 $(a-1,a),(b,b+1)$ 的面积。

  • 当二项分布的期望 $np$ 大到可以用正态分布近似的时候，应对正态分布做连续性修正，视概率求取边界对积分边界进行 $\pm 0.5$ 处理（根据四舍五入计数法，经过$0.5$ 修正后的边界内的整数个数等于二项分布区间内的整数个数）。

    对于 $X\sim B(n,p)$ ：

    若求取概率 $P(a<X<b)$ ，有：
    $$\sum _{k=a+1}^{b-1}{C}_n^k\frac{1}{p^n}\approx {\int }_{a+0.5}^{b-0.5}\frac{1}{\sqrt{2\pi }}{e}^{-\frac{t^2}{2}}dt$$
    若求取概率 $P(a\le X\le b)$ ，有：
    $$\sum _{k=a}^b{C}_n^k\frac{1}{p^n}\approx {\int }_{a-0.5}^{b+0.5}\frac{1}{\sqrt{2\pi }}{e}^{-\frac{t^2}{2}}dt$$
    对于 $(a,b)$ ，连续性修正后的正态分布区间 $(a+0.5,b-0.5)$ 内取整即为二项分布在区间 $(a,b)$ 内取整。

    对于 $[a,b]$ ，连续性修正后的正态分布区间 $(a-0.5,b+0.5)$ 内取整二项分布在区间 $[a,b]$ 内取整。

• 悲观错误剪枝（Pessimistic Error Pruning）中，$E(T)=N(T)\times Error(T)$ 的实质就是二项分布的期望 $E(X)=np$ ， $std(T)=\sqrt{N(T)\times Error(T)\times (1-Error(T))}$ 的实质就是二项分布的标准差 $\sqrt{D(X)}=\sqrt{np(1-p)}$ 。

• 悲观错误剪枝（Pessimistic Error Pruning）中，剪枝后只有一个叶结点，没有标准差和方差。

• 最小误差剪枝（Minimum Error Pruning）引入了贝叶斯思维，加入了先验概率影响因子。

• 关于最小误差剪枝（Minimum Error Pruning）中的 $m$ ，应该计算得到而不是直接给出。应在已知先验概率的情况下，通过迭代或网格搜索等方法确定 $\min Error(T)$，此时才符合标题中的“最小误差”。当类别总数较大时，先验概率至关重要，更不应该随意设定 $m$ 的值。

• 上 $\alpha$ 分位数：$P(X\ge x_{\alpha })=\alpha$ ； 下 $\alpha$ 分位数：$P(X\le x_{\alpha })=\alpha$ 。

• 对于基于错误的剪枝（Error Based Pruning）中误判率上界的分析：

  • 该结点的误判率（连续修正）：

  $$error(T)=\frac{e(T)+0.5}{N(T)}$$

  • 二项分布的标准差 $std(T)=np(1-p)$：

  $$N(T)\cdot \frac{e(T)+0.5}{N(T)}\cdot (1-\frac{e(T)+0.5}{N(T)})=\sqrt{\frac{\left(e\left(T\right)+0.5\right)\left(N\left(T\right)-e\left(T\right)-0.5\right)}{N\left(T\right)}}$$

  • 加入置信水平的标准差：

$$\sqrt{\frac{\left(e\left(T\right)+0.5\right)\left(N\left(T\right)-e\left(T\right)-0.5\right)}{N\left(T\right)}+\frac{{q_{\alpha }}^2}{4}}$$

• 熵和基尼系数类似，均表示随机变量的不确定性。
• CART 假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支为“是”，右分支为“否”。
• CART 决策树既能做分类也能做回归。