机器学习之决策树（DecisionTree）①——基本概念及思想
⽂章⽬录
什么是决策树?
引例
现有训练集如下，请训练⼀个决策树模型，对未来的西⽠的优劣做预测。
先不谈建⽴决策树模型的算法，我们先看⼀下基于“信息增益”（后⾯讲）⽣成的决策树的样⼦
⼀棵决策树包含⼀个根节点、若⼲个内部节点、若⼲个叶节点。叶节点对应于决策结果，其他节点对应于⼀个属性测试。每个节点包含的样本集合根据属性测试的结果被划分到⼦节点中。根节点（纹理）
包含样本全集，根节点下的节点（根蒂）包含所有纹理=清晰的样本。从根节点到每个叶节点的路径对应⼀个判定测试序列。决策树的学习就是要产⽣⼀棵对新样本预测正确率⾼的决策树。
中三决策树结构
小程序项目结点（node）：内部结点和叶结点。内部结点—>特征 ；叶结点—>标签
有向边
分类决策树
叶结点—>类别
回归决策树
叶结点—>实数
李航《统计学习⽅法》中的介绍
决策树(decision tree)是⼀种基本的分类与回归⽅法。决策树模型呈树形结构，在分类问题中，表⽰基于特征对实例进⾏分类的过程。
它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利⽤训练数据，根据损失函数最⼩化的原则建⽴决策树模型。预测时，对新的数据，利⽤决策树模型进⾏分类。决策树学习通常包括3个步骤：特征选择、决策树的⽣成和决策树的修剪。这些决策树学习的思想主要来源于由Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman等⼈在1984年提出的CART算法。
决策树是⼀种树形结构，其中每个内部节点表⽰⼀个属性上的测试，每个分⽀代表⼀个测试输出，每个叶节点代表⼀种类别。决策树是⼀种⼗分常⽤的分类回归⽅法
如何创建⼀颗决策树?
1. 第⼀步：确定评价决策树好坏的指标(⽤什么?)----->在测试集上的表现
2. 第⼆步：列举出所有可能的决策树，然后计算各⾃的指标，从⽽选出最优的⼀棵树
缺点是什么？----->从所有可能的决策树中选取最优的DT是⼀个NP-hard问题
特征选择
决策树学习的关键在于：在每个节点上如何选择最优划分属性。
折半查找法在引例中，在根节点上，优先选择了“纹理”作为划分属性，这种选择是有依据的。
⼀般⽽⾔，随着划分过程不断进⾏，我们希望决策树的分⽀节点所包含的样本尽可能属于同⼀类别，即节点的“纯度”越来越⾼。因此我们要找⼀个指标，去衡量划分数据集后“纯度提升的幅度”，然后选择能让“纯度提升的幅度”最⼤的特征去划分数据集。
常⽤的衡量“纯度提升的幅度”的指标有：信息增益、信息增益率、基尼指数。
基于信息增益⽣成决策树的算法，称为ID3算法。
基于信息增益率⽣成决策树的算法，称为C4.5算法。
基于基尼指数⽣成决策树的算法，称为CART算法。
启发式学习
贪⼼策略
贪⼼策略(⼀次找到最优模型)
思想：确定贪⼼指标，在候选⽅案集合中执⾏⼀个让贪⼼指标最⼤的⽅案。不会从全局最优的⾓度思
考问题，近似求解，这个解可能是次优解（sub-optimal）
决策树的贪⼼指标
信息增益: 信息增益 = 原来结点的不纯度 – ⼦结点不纯度的和。
候选⽅案集合（连续特征，离散特征）
连续特征： ⽐如年龄中<10岁，<20岁，<30岁等等都可以是划分点。假设：5种⽅案
离散特征：
多叉树：直接按照不同特征值划分即可，⽐如长相⾥的丑，中等，帅。1种⽅案
⼆叉树：丑/中等帅，丑中等/帅，丑帅/中等，都是划分点。3种⽅案
连续特征和离散特征划分点取并集，5+1或5+3种⽅案
启发式构建决策树过程
贪⼼指标与建树⽅法
建树的⽅法论
让叶结点尽早变得更纯
衡量不纯度的指标
树结点内样本标签不⼀致的程度
衡量变纯程度的指标（信息增益）
划分前的不纯度为a，⽐如划分后产⽣两个结点，它们的不纯度分别为b和c，可以对其加权为B和C，那信息增益=a-(B+C)建树过程
遍历全体划分点候选集，选择信息增益最⼤的划分点构建决策树，递归执⾏
最近很火的抖音音乐衡量不纯度的指标
衡量不纯度的指标与信息增益
基尼指数（分类）：
两次抽取，拿到两个不同类别实例的概率，如果结点中实例是纯的，那么基尼指数=0
⾹农熵（分类）：
刻画不确定程度，如果结点中实例是纯的，那么⾹农熵=0
均⽅误差（回归）：
结点内的均⽅误差
信息增益
信息增益 = 原来结点的不纯度 – ⼦结点不纯度的和。
信息增益与决策树算法
倩女幽魂手游新区
根据不同的衡量结点不纯的指标，⼀些⽆聊的⼤⼈⾮要说使⽤了不同的算法，并纷纷给这些构建决策树的算法起了名字。ID3算法：基于⾹农熵增益，缺点：会偏爱取值较多的特征
⾹农熵增益 = 结点的⾹农熵 – ⼦结点⾹农熵的带权和
C4.5算法：基于⾹农熵增益⽐，缺点：计算复杂度⾼
⾹农熵增益⽐ = 参数*⾹农熵增益 ps：某特征的特征值种类越多，那么参数越⼩。
CART分类算法：基于基尼指数增益
基尼指数增益 = 结点的基尼指数 – ⼦结点的基尼指数的带权和
CART回归算法：基于⽅差增益
⽅差增益 = 结点的⽅差 – ⼦结点的⽅差的带权和
启发式学习的两个问题
这个贪⼼指标怎么设计？
第⼀步：设计衡量结点不纯度的指标
第⼆步：设计衡量变纯程度的指标（信息增益，贪⼼指标）
第三步：遍历全体划分点候选集，选择信息增益最⼤的划分点构建决策树。反复执⾏构建树的枝⼲，直到达到停⽌条件，完成整棵决策树的构建
怎么确定全体划分点候选集？盛的组词是什么
连续特征： 先按照特征值排序，“见缝插针”，5个划分点
离散特征：
多叉树：1个划分点
⼆叉树： 2^(M-1)-1个划分点
连续特征和离散特征划分点取并集
决策树的剪枝
为什么要剪枝？
宽泛来讲：机器学习模型都会有过拟合风险，在训练集上表现的过于优秀，⽽泛化能⼒差，因此机器学习模型都有对应的防⽌过拟合的策略，决策树的策略就是剪枝
具体来讲：决策树⽣成算法会递归地建造决策树的分⽀，直到结点都很纯为⽌。这样产⽣的决策树往往对训练数据的分类很准确，但失去泛化能⼒，即发⽣过拟合了，因此，可通过主动去掉⼀些分⽀来降低过拟合的风险，提⾼模型泛化能⼒
预剪枝和后剪枝
剪枝是决策树学习算法对付“过拟合”的主要⼿段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分⽀过多，这时就可能因训练样本学得“太好”了，以致于把训练集⾃⾝的⼀些特点当作所有数据都具有的⼀般性质⽽导致过拟合。因此，可通过主动去掉⼀些分⽀来降低过拟合的风险。
决策树剪枝的基本策略有：“预剪枝”和“后剪枝”。
预剪枝是指在决策树⽣成过程中，对每个结点在划分前先进⾏估计，若当前结点的划分不能带来决策树准确率提升，则停⽌划分并将当前结点标记为叶结点；后剪枝则是先从训练集⽣成⼀棵完整的决策树，然后⾃底向上地对⾮叶结点进⾏考察，若将该结点对应的⼦树替换为叶结点能带来决策树准确率提升，则将该⼦树替换为叶节点。
先讨论“预剪枝”：
预剪枝是在建造决策树的过程中执⾏的，如果发现某个节点划分后准确率没有提⾼，就禁⽌划分。
桂花油优点：预剪枝使得决策树的分⽀都没有“展开”，降低了过拟合的风险，减⼩了训练时间。
缺点：有⽋拟合的风险。因为有些分⽀的当前划分虽不能提升准确率、甚⾄会暂时导致准确率下降，但是在其基础上的后续划分却有可能显著提升准确率。
无颜面对江东父老再讨论“后剪枝”：
后剪枝先从训练集⽣成⼀棵完成决策树，然后慢慢砍树，砍的位置：当前决策树叶节点的⽗节点，砍的条件是：如果能提⾼准确率就砍。
优点：⽋拟合风险很⼩，准确率⼀般优于“预剪枝”决策树。
缺点：训练时间长。
决策树模型优缺点
