问题一: 机器学习的基本流程( 六 ) _机器学习

通过对比三种决策树的构造准则，以及在同一例子上的不同表现，我们不难总结三者之间的差异.
首先，ID3是采用信息增益作为评价标准，除了“会写代码”这一逆天特征外，会倾向于取值较多的特征.因为，信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着确定性更高，也就是条件熵越小，信息增益越大.这在实际应用中是一个缺陷.比如，我们引入特征“DNA”，每个人的DNA都不同，如果ID3按照“DNA”特征进行划分一定是最优的（条件熵为0），但这种分类的泛化能力是非常弱的.因此，C4.5实际上是对ID3进行优化，通过引入信息增益比，一定程度上对取值比较多的特征进行惩罚，避免ID3出现过拟合的特性，提升决策树的泛化能力.
其次，从样本类型的角度，ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量.C4.5处理连续型变量时，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性转换为布尔型，从而将连续型变量转换多个取值区间的离散型变量.而对于CART，由于其构建时每次都会对特征进行二值划分，因此可以很好地适用于连续性变量.
从应用角度，ID3和C4.5只能用于分类任务，而CART（ andTree，分类回归树）从名字就可以看出其不仅可以用于分类，也可以应用于回归任务（回归树使用最小平方误差准则）.
此外，从实现细节、优化过程等角度，这三种决策树还有一些不同.比如， ID3对样本特征缺失值比较敏感，而C4.5和CART可以对缺失值进行不同方式的处理；ID3和C4.5可以在每个结点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个结点只会产生两个分支，因此最后会形成一颗二叉树，且每个特征可以被重复使用；ID3和C4.5通过剪枝来权衡树的准确性与泛化能力，而CART 直接利用全部数据发现所有可能的树结构进行对比.
问题3 试用类C语言(或)写出剪枝算法.
一棵完全生长的决策树会面临一个很严重的问题，即过拟合.假设我们真的需要考虑DNA特征，由于每个人的DNA都不同，完全生长的决策树所对应的每个叶结点中只会包含一个样本，这就导致决策树是过拟合的.用它进行预测时，在测试集上的效果将会很差.因此我们需要对决策树进行剪枝，剪掉一些枝叶，提升模型的泛化能力.
决策树的剪枝通常有两种方法，预剪枝（Pre-）和后剪枝（）.那么这两种方法是如何进行的呢？它们又各有什么优缺点？
分析与解答
预剪枝，即在生成决策树的过程中提前停止树的增长.而后剪枝，是在已生成的过拟合决策树上进行剪枝，得到简化版的剪枝决策树.
■ 预剪枝
预剪枝的核心思想是在树中结点进行扩展之前，先计算当前的划分是否能带来模型泛化能力的提升，如果不能，则不再继续生长子树.此时可能存在不同类别的样本同时存于结点中，按照多数投票的原则判断该结点所属类别.预剪枝对于何时停止决策树的生长有以下几种方法.
（1）当树到达一定深度的时候，停止树的生长.

文章插图
（2）当到达当前结点的样本数量小于某个阈值的时候，停止树的生长.
（3）计算每次分裂对测试集的准确度提升，当小于某个阈值的时候，不再继续扩展.
预剪枝具有思想直接、算法简单、效率高等特点，适合解决大规模问题.但如何准确地估计何时停止树的生长（即上述方法中的深度或阈值），针对不同问题会有很大差别，需要一定经验判断.且预剪枝存在一定局限性，有欠拟合的风险，虽然当前的划分会导致测试集准确率降低，但在之后的划分中，准确率可能会有显著上升.