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

1.决策树模型（分类回归法）

1.1 基本概念

• 决策树可以是多叉树，它是描述实例分类的树结构
  
• 决策树由节点和有向边组成。节点进一步分为：内部节点（表示特征或属性）、叶节点（表示类别）
  
• 决策树采用规则（集合互斥且完备），一个实例只有一条路径；叶节点，即类别可以有多个路径
  

1.2 决策树的学习

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

2. 特征选择

• 特征选择的标准：信息增益，信息增益比
  

2.1 熵与条件熵

• 熵：随机变量中不确定性的度量。设是一个值数有限的离散随机变量，其概率分布为，则随机变量的熵定义为，也可写为
  
• 熵越大，随机变量的不确定性越大。当随机变量取等概率分布时，对应的熵最大
  
• 条件熵：在已知随机变量的条件下，随机变量的不确定性，定义为给定条件下条件概率分布的熵的数学期望，其中
  
• 如果从数据中估计熵和条件熵，它们分别称为经验熵和经验条件熵。
  

2.2 信息增益

• 信息增益：特征对训练数据集的信息增益定义为
  
• 互信息：熵和条件熵的区别。决策树学习中的信息增益相当于训练数据集中类和特征之间的互信息
  
• 信息增益准则：对于训练数据集（或子集），计算每个特征的信息增益，比较它们的大小，选择信息增益最大的特征
  
• 信息增益大的特征具有更强的分类能力
  
• 信息增益算法：
  
• 输入：训练数据集和特征
  
• 输出：特征在训练数据集上的信息增益
  
  
  
• 注：当特征值为时，对应的数据集确定为，所以
  

2.3 信息增益比

• 信息增益比：特征与训练数据集的信息增益比定义为
  

3. 决策树的生成

3.1 ID3算法

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

3.2 C4.5算法

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

四、决策树的剪枝

• 优秀的决策树分为三种：深度小；叶节点少；深度小，叶节点少
  

4.1 预剪枝

• 在生成决策树的过程中，如果当前节点的划分不能提高其泛化能力，则停止划分并记录为叶子节点
  
• 确定是否进行剪枝？基于测试集的错误率是否降低，即错误分类实例的比例。 （泛化随着错误率的降低而提高）
  

4.2 后剪枝

• 生成完整的决策树后，自下而上检查内部节点。如果内部节点变成叶子节点，则可以提高泛化能力，并进行这种替换。
  
• 悲观错误修剪：基于训练集，自顶向下。计算剪枝前误报的上限和剪枝后误报数的期望值
  
  
• 最小错误剪枝：基于训练集，自下而上。计算剪枝前后的最小分类错误概率来决定是否剪枝
  
  
• 基于错误剪枝：基于训练集，计算剪枝前后的误判次数，从而决定是否剪枝
  
  
• cost-complexity pruning：根据剪枝前后损失函数的大小（包括成本和复杂度）
  
• CART算法中进行决策树剪枝时，使用该方法进行判断
  

五、CART算法

5.1 回归树

假设和分别是输入和输出变量，是连续变量，给定训练数据集一棵回归树对应输入空间的划分和划分单元上的输出值。假设输入空间已经被划分为单元，并且每个单元上都有一个固定的输出值，那么回归树模型可以表示为当输入空间的划分确定时，可以表示为由平方误差 回归树是基于训练数据集的预测误差，并使用最小平方误差的准则来寻找每个单元的最优输出值。很容易知道，在单元上的最优值是输出对应所有输入实例在上的平均值，即

• 如何找到最佳分割点？基于最小化平方误差的原则
  
• 对于变量，比较每个分割点的平方误差值，选择最小的，其对应的为最优分割点
  
• 如何找到最优的分割变量？基于最小化平方误差的原则
  
• 找到每个变量的最优分割点，比较每个最优分割点的平方误差值，选择最小的，对应的就是最优分割变量
  
  

5.2 分类树

• 假设决策树是二叉树
  
• 特征选择：基于基尼指数最小化原则
  
• 假设有类，样本点属于类的概率为，则概率分布的基尼指数定义为
  
• 对于二分类问题，假设样本点属于第1个类的概率为,则概率分布的基尼指数为
  
• 对于给定的样本集，其基尼指数为，其中是中属于类的样本子集，是类数
  
• 在给定特征的条件下，集合的基尼指数定义为基尼指数的值越大，样本集的不确定性越大
  
  
  参考：《统计学习方法》李航著；B站UP主简博士《统计学习方法》视频 (关于决策树剪枝部分)