• 决策树学习的三个步骤：特征选择、决策树的生成和决策树的修剪

一、决策树模型（分类与回归方法）

1.1 基本概念

• 决策树可为多叉树，是描述对实例进行分类的树形结构
• 决策树由结点和有向边组成。其中结点又分为：内部结点（表示特征或属性）、叶结点（表示类别）
• 决策树采用$if-then$规则(集合互斥且完备)，一个实例仅有一条路径；叶结点，即类别可有多条路径

1.2 决策树的学习

• 学习过程：决策树通过给定特征条件下类的条件概率分布$P(X|Y)$，对特征空间进行一个划分，且划分得到的各个单元互不相交
• 假设空间：由无穷多个条件概率模型组成
• 学习策略：以损失函数为目标函数的最小化，其中损失函数通常是正则化的极大似然函数
• 学习算法：递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类过程
  • 决策树的生成(考虑局部最优)：对特征空间的划分，直至所有训练子集被基本正确分类
  • 决策树的剪枝(考虑全局最优)：避免过拟合，具有更好的泛化能力
• 一棵好的决策树：在保证训练误差较小的情况下，具有良好的泛化能力。因此在决策树生成后，需对其进行剪枝处理，以提高泛化能力

二、特征选择

• 特征选择的准则：信息增益、信息增益比

2.1 熵与条件熵

• 熵：随机变量不确定性的度量。设$X$是一个取有限个值的离散随机变量，其概率分布为$$P(X=x_i)=p_i，i=1,2,\cdots ,n$$则随机变量$X$的熵定义为$$H(X)=-\sum _{i=1}^n{p}_i\log p_i$$也可记作$H(p)$
  • 熵越大，随机变量的不确定性就越大。随机变量取等概率分布时，相应的熵最大
• 条件熵：在已知随机变量$X$的条件下随机变量$Y$的不确定性，定义为$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望$$H(Y|X)=\sum _{i=1}^n{p}_{i}H(Y|X=x)$$其中$p_i=P(X=x_i)，i=1,2,\cdots ,n$
• 若是由数据估计得到的熵与条件熵，分别称为经验熵与经验条件熵

2.2 信息增益

• 信息增益：特征$A$对训练数据集$D$的信息增益$g(D,A)$定义为$$g(D,A)=H(D)-H(D|A)$$
• 互信息：熵$H(Y)$与条件熵$H(Y|X)$之差。决策树学习中的信息增益等价于训练数据集中类与特征的互信息
• 信息增益准则：对训练数据集(或子集)$D$，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征
• 信息增益大的特征具有更强的分类能力
• 信息增益的算法：
  • 输入：训练数据集$D$和特征$A$
  • 输出：特征$A$对训练数据集$D$的信息增益$g(D,A)$
    
    
• 注：当特征取值为$a_i$时，所对应的数据集确定为$D_i$，故$P(D|A=a_i)=P(D_i)$

2.3 信息增益比

• 信息增益比：特征$A$对训练数据集$D$的信息增益比$g_R(D,A)$定义为$$g_R(D,A)=\frac{g(D,A)}{H(D)}$$

三、决策树的生成

3.1 ID3算法

• 选择信息增益最大的特征作为结点的特征
• 经验熵大的时候，信息增益值会偏大
  
  

3.2 C4.5算法

• 选择信息增益比最大的特征作为结点的特征
  
• 处理离散或连续随机变量，但不适用于样本量过大的数据

四、决策树的剪枝

• 优秀的决策树有三种：深度小；叶结点少；深度小且叶结点少

4.1 预剪枝

• 在决策树的生成过程中，若当前结点的划分不能提高其泛化能力，则停止划分，并将其记为叶结点
• 判断是否进行剪枝处理？基于测试集的误差率是否降低，即错误分类的实例占比。(随着误差率下降，泛化能力提高)

4.2 后剪枝

• 在生成一棵完整额决策树后，自下而上地对内部结点进行考察，若内部结点变为叶结点，可提升泛化能力，则做此替换
  • 悲观错误剪枝：基于训练集，自上而下进行。计算剪枝前误判上限与剪枝后误判个数的期望值
    
  • 最小误差剪枝：基于训练集，自下而上进行。计算剪枝前后的最小分类错误概率，从而决定是否剪枝
    
  • 基于错误剪枝：基于训练集，计算剪枝前后的误判个数，从而决定是否剪枝
    
  • 代价-复杂度剪枝：根据剪枝前后的损失函数大小(包括代价和复杂度)
    • CART算法中进行决策树剪枝时，使用该方法进行判断

五、CART算法

5.1 回归树

假设$X$与$Y$分别为输入和输出变量，并且$Y$是连续变量，给定训练数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } D=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\} D={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}一个回归树对应着输入空间的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为$M$个单元$R_1,R_2,\cdots ,R_M$，并且在每个单元$R_m$上有一个固定的输出值$c_m$，于是回归树模型可表示为$$f(x)=\sum _{m=1}^M{c}_{m}I(x\in R_m)$$当输入空间的划分确定时，可以用平方误差${\sum }_{x_i\in R_m}(y_i-f(x_i){)}^2$来表示回归树基于训练数据集的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元$R_m$上的$c_m$的最优值${\hat{c}}_m$是$R_m$上的所有输入实例$x_i$对应得输出$y_i$的均值，即$${\hat{c}}_m=ave(y_i|x_i\in R_m)$$

• 如何寻找最优切分点？基于平方误差最小化原则
  • 对于$j$个变量$x^{(j)}$，比较每个切分点$s_1,s_2,\cdots$的平方误差值，选取最小的，其对应的$s_i$即为最优切分点
• 如何寻找最优切分变量？基于平方误差最小化原则
  • 找每个变量的最优切分点，比较每个最优切分点的平方误差值，选取最小的，对应的$x^{(j)}$即为最优切分变量
    

5.2 分类树

• 假设决策树为二叉树
• 特征选择：基于基尼指数最小化原则
  • 假设有$K$个类，样本点属于第$k$类的概率为$p_k$，则概率分布的基尼指数定义为$$Gini(p)=\sum _{k=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$$
  • 对于二分类问题，假设样本点属于第1个类的概率为$p$,则概率分布的基尼指数为$$Gini(p)=2p(1-p)$$
  • 对于给定的样本集合$D$，其基尼指数为$$Gini(D)=1-\sum _{k=1}^K(\frac{|C_k|}{|D|}{)}^2$$这里，$C_k$是$D$中属于第$k$类的样本子集，$K$是类的个数
  • 在给定特征$A$的条件下，集合$D$的基尼指数定义为$$Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$基尼指数值越大，样本集合的不确定性也就越大
    
    
    参考：《统计学习方法》李航著；B站UP主简博士《统计学习方法》视频 (关于决策树剪枝部分)