文章目录一. 决策树基本原理1. 定义2. 表示成条件概率二. 决策树的训练算法1. 划分选择的算法1.1. 信息增益ID3 算法1.2. 信息增益比C4.5 算法1.3. 基尼指数CART 算法举例说明计算各个类别的信息增益2. 叶子节点的选择3. 剪枝3.1. 预剪枝3.2. 后剪枝三. 决策树训练算法分类本文重点内容什么是决策树决策树的基本原理决策树训练方法防止过拟合的方法分类和回归决策树筛选原则一. 决策树基本原理1. 定义分类决策树模型是一种描述对实例进行分类的树形结构。决策树由节点和有向边组成。其中节点有两种类型内部节点和叶节点。内部节点表示一个特征或属性叶结点表示一个类结构如下图2. 表示成条件概率决策树还可以表示成在给定条件下类的条件概率分布。决策树将特征空间划分为会不相交的单元在每个单元定义一个类的概率分布这就构成了一个条件概率分布。条件概率计算方式:概率分布计算由各个单元给定条件下类的条件概率分布组成将这些概率沿着分支相乘即得出所需的概率。极大似然函数损失函数的优化。二. 决策树的训练算法决策树学习算法通常是递归的原则最优特征根据该特征对训练数据进行分割即特征空间的分割。决策树的结构收到很多因素影响特征选择、分裂点选择、树的深度、复杂度控制、剪枝等。1. 划分选择的算法特征选择在每个节点上如何选择一个特征进行分裂常用的特征选择指标有信息增益、信息增益率以及基尼指数ID3、C4.5、CART的等决策树算法。1.1. 信息增益ID3 算法信息熵的定义与计算信息增益的计算信息增益衡量了信息对数据集分类结果的贡献度。在构建决策树时ID3 算法选择信息增益最大的特征作为当前节点的划分特征。例如在一个判断水果是苹果还是橙子的决策树中有颜色、形状等特征通过计算这些特征的信息增益若颜色特征的信息增益最大那么就先根据颜色来划分节点。1.2. 信息增益比C4.5 算法信息增益比的引入原因信息增益存在一个问题它偏向于选择取值较多的特征。为了克服这个问题C4.5 算法引入了信息增益比。在决策树构建过程中C4.5 算法选择信息增益比最大的特征作为划分特征。例如在一个包含很多特征的数据集里有些特征虽然信息增益较大但它可能有过多的取值通过计算信息增益比可以更合理地选择划分特征。1.3. 基尼指数CART 算法基尼指数的含义基尼指数用于衡量数据集的纯度其值越小表示纯度越高。例如在客户流失预测的决策树中基尼不纯度可以帮助我们了解每个节点中客户流失或不流失的纯度情况。如果一个节点的基尼不纯度很高说明这个节点中的客户在流失与否的分类上很混乱需要进一步划分来提高纯度。基尼指数的作用划分特征。对于每个候选特征计算按照该特征划分后的基尼指数选择使得基尼指数最小的特征作为划分特征。这是因为最小的基尼指数意味着划分后子数据集的纯度最高这样可以构建出更有效的决策树。例如在信用风险评估决策树中有收入、负债、信用记录等多个特征。通过计算每个特征划分后的基尼指数选择能使基尼指数最小的特征如信用记录进行划分从而更好地将高风险和低风险客户区分开来。基尼指数可以防止过拟合基尼指数的使用有助于控制决策树的生长防止过拟合。如果不加以控制决策树可能会过度划分数据导致在训练数据上表现很好但在新数据上性能很差。通过选择基尼指数最小的特征进行划分决策树会优先选择最能有效降低数据集不纯度的特征避免构建过于复杂的决策树结构。例如在图像分类决策树中使用基尼指数来选择划分特征可以避免因一些噪声特征而构建出过于复杂的决策树从而使模型在新的图像数据上有更好的泛化能力。举例说明计算各个类别的信息增益计算各个类别的信息增益:计算数据集的经验熵H(D)计算特征A下(n个类别)各个类别的加权平均熵H ( D A i ) H(D_{Ai})H(DAi​)计算特征A的加权熵H ( D A ) ∑ i 1 n ( D A i / D ) H ( D A i ) H(D_A)\sum_{i 1}^{n}(D_{Ai}/D)H(D_{Ai})H(DA​)∑i1n​(DAi​/D)H(DAi​)求信息增益H ( D A ) H ( D ) − H ( A ) H(D_A)H(D)-H(A)H(DA​)H(D)−H(A)类别B同上然后对比信息增益选择大的信息增益作为分裂点2. 叶子节点的选择见p1083. 剪枝采用剪枝操作防止决策树出现过拟合可以把这种操作看成是一种对决策树采取的正则手段。常用的剪枝有预剪枝、后剪枝操作。3.1. 预剪枝预剪枝是指在模型训练之前给定一些限制条件这些限制条件可以阻止节点的进一步分裂。常见预剪枝的策略有限制树的最大深度。如果所有叶子都已经达到最大深度将停止训练。限制树的最大叶子数目。如果叶子数目达到这个上限将停止训练。限制每片叶子上最少的样本数。为每个节点设置最小样本数阈值如果节点的本数少于这个阈值则停止分裂。规定分割带来训练误差下降的下限。比如规定此下限为-0.3那么将无视所有致训练误差下降达不到0.3的分割条件。利用验证集进行预剪枝。如果有验证集可在决策树的训练过程中不断用验证进行评估。如果一次分割无法降低验证集上的误差该分割将不被进行。预剪枝的优点是可以在树的生长过程中减少计算量但缺点是可能会错过一些有用分裂导致模型的表达能力不足。3.2. 后剪枝后剪枝是在将决策树训练好之后从决策树的底部开始评估删除一个分割是否导致验证集误差下降。如果是则删除该分割即删除该分割产生的两个叶子节点并将它的父节点重新设为叶子节点否则保留该分割不断重复该步骤。后剪枝的优点是可以灵活控制模型的复杂度但缺点是计算量较大因为需要在树完全生长后进行剪枝。三. 决策树训练算法分类算法名称分裂准则处理类型树的结构缺失值处理剪枝处理应用范围ID3信息增益离散特征可以是多叉树不处理没有剪枝过程容易过拟合分类C4.5信息增益率连续特征可以是多叉树能处理数据集中存在缺失值的情况。它通过估算该特征对分类的贡献进行处理而不是简单地删除缺失数据。对于有缺失值的特征C4.5会计算每个可能的分裂点并考虑缺失值的不同处理方式对分类结果的影响采用了一种后剪枝方法即先完整地生长树然后再通过悲观剪枝策略来减少树的复杂性提高泛化能力分类CART基尼指数离散、连续均可二叉树对于缺失值的处理采用了概率加权的方法。它通过计算缺失随机变量的预测概率然后对每个可能的值进行加权平均使用后剪枝策略即先生成完整的树然后通过交叉验证来选择最优的剪枝树分类和回归参考《人工智能基础-姚期智》