大数据-201 数据挖掘 机器学习理论 - 决策树 局部最优 剪枝 分裂 二叉分裂

点一下关注吧！！！非常感谢！！持续更新！！！

目前已经更新到了：

• Hadoop（已更完）
• HDFS（已更完）
• MapReduce（已更完）
• Hive（已更完）
• Flume（已更完）
• Sqoop（已更完）
• Zookeeper（已更完）
• HBase（已更完）
• Redis （已更完）
• Kafka（已更完）
• Spark（已更完）
• Flink（已更完）
• ClickHouse（已更完）
• Kudu（已更完）
• Druid（已更完）
• Kylin（已更完）
• Elasticsearch（已更完）
• DataX（已更完）
• Tez（已更完）
• 数据挖掘（正在更新…）

章节内容

上节我们完成了如下的内容：

• 决策树 数据集划分
• 决策树生成 ID3 C4.5

决策树

决策树是一种基于树状结构的监督学习模型，常用于分类和回归任务。它的基本思想是通过一系列问题的分层次判断，将数据分割成越来越小的子集，直到达到预期的目标（如纯度较高的叶子节点，或预测值的误差足够小）。决策树的节点表示判断条件，分支表示不同的条件结果，最终的叶子节点对应具体的分类结果或预测值。

局部最优

在构建决策树的过程中，通常采用贪心算法，即在每一步选择当前条件下最佳的分割方式，而不考虑全局最优。这个方法被称为局部最优，因为它在每个步骤只关注当前的最佳决策，并不一定能保证得到整体最佳的结果。虽然这种方法可能导致最终的决策树不是最优的，但它在实际应用中计算效率较高，且在很多情况下能够得到合理的结果。

剪枝

剪枝是一种用于防止决策树过拟合的方法。在决策树的构建过程中，过度的分裂会导致模型对训练数据过度拟合，进而降低对新数据的泛化能力。剪枝的目的是通过去除一些不必要的分支，简化决策树结构，从而提升模型的泛化能力。常见的剪枝方法有预剪枝（pre-pruning）和后剪枝（post-pruning）。预剪枝在构建决策树时提前停止某些分裂，而后剪枝则是在树构建完成后再去掉一些不重要的分支。

分裂

分裂是决策树构建中的一个核心过程，指的是从根节点开始，根据某个特征的值，将数据划分到不同的子节点中。通过不断地分裂，决策树逐渐将数据集划分成更小的子集，使得每个子集内部的样本更具一致性。在分类任务中，分裂的目标是最大化信息增益或基尼系数的变化，在回归任务中则常采用均方误差或方差作为指标。分裂的过程直到达到设定的停止条件（如节点纯度、树的深度限制等）才会停止。

二叉分裂

二叉分裂是一种特定的分裂方式，每次只将节点分成两个子节点，形成一个二叉树结构。决策树可以通过二叉分裂的方式构建，其中每次分裂时，将样本数据分成两个互斥的子集。这种分裂方式的优点是结构简单，且在很多实现中效率较高。许多决策树算法（如CART算法）就是基于二叉分裂构建的。这种结构的决策树在每个节点上只能有两个分支，即「是」或「否」，从而确保树结构的简洁性。

修改局部最优条件

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

称为属性 a 的“固有值”（intrinsic value）
属性 a 的可能取值越多（即 V 越大），则 IV（a）的值通常会越大。
IV 值会随着叶节点上样本量的变小而逐渐变大，也就是说一个特征中如果标签分类太多，每个叶子上的 IV 值就会非常大。
值得注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一种启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

连续变量处理手段

在 C4.5 中，同样还增加了针对连续变量的处理手段。如果输入特征字段是连续型变量，则算法首先会对这一列数进行从小到大的排序，然后选取相邻的两个数的中间数作为切分数据集的备选点，若一个连续变量有 N 个值，则在 C4.5 的处理过程中将产生 N-1 个备选切分点，并且每个切分点都代表着一种二叉树的切分方案，例如：

这里需要注意的是，此时连续变量的处理并非是将其转换为一个拥有 N-1 个分类水平的分类变量，而是将其转换为了 N-1 个二分方案，而在进行了下一次的切分过程中，在 N-1 个方案都要单独带入考虑，其中每一个切分方案和一个离散变量的地位均相同（一个离散变量就是一个单独的多路切分方案）。
例如如下数据集，数据集中的只有两个字段，第一行代表年龄，是特征变量，第二行代表性别，是目标字段，则对年龄这一连续变量的切分方案如图所示：

从上述能够看出，在对于包含连续变量的数据集进行树模型构建的过程中要消耗更多的运算资源。但与此同时，我们也会发现，当连续变量的某中间点参与到决策的二分过程中，往往代表该点对于最终分类结果有较大影响，这也为我们连续变量的分箱压缩提供了指导性意见。

例如上述案例，若要对 Age 列进行压缩，则可考虑使用 36.5 对其进行分箱，则分箱结果对于性别这一目标字段仍然具有较好的分类效果，这也是决策树最常见的用途之一，也是最重要的模型指导分箱的方法。

决策树的拟合度优化

在实际操作中，我们判断模型的是否拟合往往是从模型训练误差和泛化误差，二者结合使用就能判断模型是否存在过拟合现象。虽然我们之前举例时并没有对数据集进行切分，但任何有监督学习算法建模过程中都需要进行训练集和测试集的划分，决策树也不例外，进而我们可用交叉验证计算训练误差和泛化误差，进而判断决策树是否存在过拟合。
这是一套通用的判断有监督学习算法是否过拟合的方法，同时通用的方法中还有更高级的方法。
但对于决策树而言，有一套决策树独有的防止过拟合的解决方案–剪枝。

决策树剪枝

所谓剪枝是指在决策树中去除部分叶节点，剪枝（Pruning）主要用来防止过拟合，对于一般的数据集如果总是追求纯的叶节点，或者观测数较小的叶节点，很容易使得树过于庞杂，尤其是存在可以反复使用的连续变量的时候，此时就需要主动去掉一些分支来降低过拟合的风险。

常见的剪枝策略有“预剪枝”（Pre-Pruning）和“后剪枝”（Post-Purning）

• 预剪枝：在决策树生成的过程中，对每个节点在划分前先进行估计，如果当前的节点划分不能带来决策树泛化性能（预测性能）的提升，则停止划分并且当前节点标记为叶节点。
• 后剪枝：先训练生成一颗完整的树，自底向上对非叶节点进行考察，如果该节点对应的子树替换为叶节点能带来决策树泛化能力的提升，则该子树替换为叶节点。

分裂准则

二叉递归划分：条件成立向左，反之向右

• 对于连续变量：条件是属性小于等于最优分裂点
• 对于分类变量：条件是属性属于若干类

二叉分裂优点

相比多路分裂导致数据碎片化的速度慢，允许在一个属性上重复分裂，即可以在一个属性上产生足够多的分裂。两路分裂带来的树预测性能提升足以弥补其相应的树易读性损失。

对于属性不同的被预测变量 Y 分裂准则不同：

• 分类树：Gini 准则，与之前的信息增益很类似，Gini 系数度量一个节点的不纯度。
• 回归树：一种常见的分割标准是偏差减少（Stand Deviation Reduction，SDR），类似于最小均方差 LS（Least Squares 预测错误的平方和）准则。

利用测试集进行剪枝

简单讨论 CART 算法剪枝过程，该过程也是测试集用于修正模型的最佳体现。例如，在如下训练集中训练得到的模型，黑色数字表示训练集上的分类情况，红色数字表示模型作用于验证集上的分类情况。

则 CART 算法利用验证集剪枝的过程如下：

• 判断每个叶节点在验证集上的错误率
• 节点 4 的错误率：e(4) = 1/3
• 节点 5 的错误率 e(5) = 1
• 节点 6 的错误率 e(6) = 1
• 节点 7 的错误率为 e(7) = 4 / 9

计算节点总加权平均错误率并和父节点进行比较，加权方法就是乘以该节点样本数量占父节点样本总量的百分比（测试集）：

如节点 2 的错误率为 e(2)=1/4，而节点 4 和节点 5 的加权平均错误率为 e(4) * 3/4 + e(5) * 1/4 = 2/4，因此子节点错误率更高，考虑剪枝。
节点 3 的错误率为 e(3) = 4/10，而 e(6)* 1/10 + e(7)*9/10 = 5/10，因此考虑剪枝。
节点 2 和节点 3 的加权平均错误率 e(2) * 4/14 + e(3) * 10/14 = 5/14，比父节点（节点 1）的错误率 e(1) = 7/14 要小，因此保留该节点，停止剪枝。

可以看出，CART 算法剪枝过程更易理解也更便于操作，同时我们也能看到对于建立模型的算法而言，测试集不仅能够对模型准确率进行评估，同时还能起到修正优化模型的作用。

测试集和验证集

对于大多数模型而言，测试集实际上的作用就是用来修正模型，为了提高修正的准确率，我们也可以采用交叉验证的方法，反复判别模型修改条件（如是否要剪枝），并设置模型修改出发条件（如多数验证情况需要修改则对其进行修改），从而提高模型优化的可靠性。

而除了训练集和测试集之外，我们还尝尝会划分一个验证集，验证集数据不参与建模叶不参与模型修改和优化，只用于模型最终优化后的模型效力。

而训练集、测试集和验证集的划分通常遵照 6:2:2 的比例进行划分，当然也可以根据实际需求适当调整划分比例，但无论如何，测试集和验证集数据量都不宜过多也不宜过少，该二者数据集数据均不参与建模，若占比太多，则会对模型的构建过程造成较大的影响（欠拟合），而若划分数据过少，训练集数据量较大，则又可能造成过拟合，数据集的划分也是影响拟合度的重要因素。