《机器学习》 第四章决策树 总结

基本流程
决策树（decision tree）：基于树的结构进行决策，从给定训练集学得一个树形模型对新示例进行分类。通常，一颗决策树包括一个根节点，若干内部节点和若干叶子节点。叶节点对应决策结果，其他节点对应一个属性测试，根节点包含样本全集。其流程遵循简单直观的”分而治之“（divide-and-conquer）策略

划分选择
我们希望决策树的分支节点包含的样本尽可能属于同一类别，即节点的纯度（purity）越来越高

信息熵（information entropy）：度量样本纯度最常用的一个指标，记为Ent(D)，其值越小，D的纯度越高

信息增益（information gain）：定义公式（4.2)。信息增益越大，意味着使用属性a进行划分所获得的纯度提升越大，因此可以用信息增益来进行决策树的划分属性选择

增益率（gain ratio）：信息增益准则对可取值数目较多的属性有所偏好，为了减少这种偏好造成的不利影响引入增益率。公式（4.3）。其中Ⅳ（a）称为属性a的固有值（intrinsic value）。增益率准则对可取值数目较少的属性有所偏好，因此有的算法先从候选划分属性中找出信息增益明显高于平均水平的属性，再从中选出增益率最高的

基尼值（gini value）：数据集D的纯度可以用基尼值公式(4.5)来度量，基尼值反映了数据集D中随机抽取的两个样本其类别标记不一致的概率。因此，基尼值越小，数据集D的纯度越高。属性a的基尼指数定义为公式(4.6)，在候选属性中选择基尼指数最小的属性作为最优划分属性

剪枝处理
剪枝（pruning）：决策树学习算法对付”过拟合“的主要手段，节点划分优势会导致决策树分支过多，以至于把训练集自身的一些它特点当作数据都具有的一般性质而导致过拟合。剪枝一般包括预剪枝（prepruning）和后剪枝（post-pruning）两种

预剪枝：在决策树生成过程中，对每个节点在划分前进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶结点。预剪枝降低了过拟合风险，也减少了决策树的训练时间和空间开销。但另一方面，有的分支在当前划分虽不能提升泛化性能甚至降低泛化性能，然而在其基础上进行的后续划分有可能导致性能的显著提高。因此预剪枝有可能带来欠拟合的风险

后剪枝：先从训练集生成一棵完整的决策树，然后自底向上对非叶结点进行考察，若将该非叶结点替换为叶结点能带来决策树泛化能力的提升，则将该子树换成叶结点。一般情形下，后剪枝决策树欠拟合风险很小，泛化性能往往高于预剪枝决策树，但后剪枝决策树训练的时间开销比未剪枝和预剪枝决策树都要大得多

连续值处理
连续属性离散化，采用二分法（bi-partition）对连续属性进行处理。使用公式(4.8)选取最优划分点对样本集合进行划分

缺失值处理
如果简单地放弃不完整样本，仅使用五缺失值的样本进行学习，显然是对数据的极大浪费。公式(4.9)(4.10)(4.11)为每个样本赋予一个权重，使得缺失值得样本以不同概率划分到不同的结点中取

多变量决策树
若把每个属性看成一个坐标轴，则d个属性描述得样本对应了d维空间上的一个数据点，对样本分类意味着在这个坐标空间中寻找不同样本之间得分类边界。决策树所形成得分类边界有一个明显特点：轴平行（axis-parrallel）。然而，当学习任务真实分类边界比较复杂时，必须使用很多段划分才能较好近似，此时决策树会相当复杂，需要进行大量属性测试，预测时间开销会很大

多变量决策树（multivariate decision tree）：实现斜划分，不再像单变量决策树一样轴平行。此时非叶节点不仅是针对某个属性，而是对属性得线性组合进行测试，试图建立一个合适得线性分类器

最后

以上就是过时短靴为你收集整理的《机器学习》 第四章决策树 总结的全部内容，希望文章能够帮你解决《机器学习》 第四章决策树 总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。