Datawhale集训营算法基础梳理任务3：决策树
【学习任务】
1. 信息论基础（熵 联合熵 条件熵 信息增益 信息增益比 基尼不纯度）？
2.决策树的不同分类算法（ID3算法、C4.5、CART分类树）的原理及应用场景？
3. 回归树原理？
4. 决策树防止过拟合手段？
1. 信息论基础（熵 联合熵 条件熵 信息增益 信息增益比 基尼不纯度）
1).熵
2).联合熵
3).条件熵
4).信息增益
5).信息增益比
6).基尼不纯度
2.决策树的不同分类算法（ID3算法、C4.5、CART分类树）的原理及应用场景
首先来理解决策树到底是什么呢？
决策树是一种基本的分类和回归方法.决策树模型呈树型结构。在分类问题中，表示基于特征对实例进行分类的过程，可以认为是if-then的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。决策树模型主要优点是具有可读性，在学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型，决策树学习通常包括3个步骤: 特征选择. 决策树生成和决策树剪枝。
决策树模型有两个过程：
1.学习过程：通过对训练样本的分析来确定“划分属性”（即内部结点对应的属性）
划分属性三种停止条件：
（1）当前结点包含的样本全属于同一类别，无需划分；
（2）当前属性集为空，或是所有样本在所有属性上的取值相同，无法划分；
（3）当前结点包含的样本集合为空，不能划分；
2.预测过程：将测试示例从根节点开始，沿着划分属性所构成的“判定测试序列”下行，直到叶结点。
直观感受一下决策是否决定相亲的决策树示意图：
决策树学习的思想主要来源于由Quinlan等人在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman等人在1983年提出的CART算法。
决策树学习通常包括3个步骤：
1.特征选择：
特征选择在于选取对训练数据具有分类能力的特征，在数据集中的所有特征列表中,选择分类效果最好的特征,尽可能的让划分的每个结果的尽可能属于同一个类别. 不同的决策树算法采用不同的衡量指标.ID3采用信息增益,C4.5采用信息增益比率,CART分类回归树当用于分类时,采用Gini指数。
2.决策树生成：
通常使用信息增益最大，信息增益比最大或基尼指数最小作为特征选择的准则。决策树的生成往往通过计算信息增益或其他指标，从根节点开始，递归地产生决策树。这相当于用信息增益或其他准则不断地选取局部最优特征，或将训练集分割为能够基本正确分类的子集。
决策树生成的流程：
3.决策树剪枝:
由于生成的决策树存在过拟合问题，需要对它进行剪枝，以简化学到的决策树。决策树的剪枝，往往从已生成的树上减掉一些叶节点或叶节点以上的子树，并将其父节点或根节点作为新的叶节点，从而简化生成的决策树。
ID3算法的基本思想:
采用信息增益作为于决策树节点的属性选择，每次优先选取信息量最多的属性，亦即能使熵值变为最小的属性，以构造一颗熵值下降最快 的决策树，到叶子节点处的熵值为0。此时，每个叶子 节点对应的实例集中的实例属于同一类。
ID3算法-流程 ：
1 .决定分类属性；
2. 对目前的数据表，建立一个节点N ；
3. 如果数据库中的数据都属于同一个类，N就是树叶，在树 叶上标出所属的类；
4. 如果数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在树叶上标出所属类别；
5 .否则，根据平均信息期望值E或GAIN值选出一个最佳属性 作为节点N的测试属性 ；
6 .节点属性选定后，对于该属性中的每个值： 从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏,如果分支数 据表非空，则运用以上算法从该节点建立子树。
C4.5算法的基本思想:
与ID3算法思想类似，不同之处在于采用信息增益比作为决策树节点的属性选择，以减少信息增益容易选择特征值多的特征的问题 。（ 信息增益反映的给定一个条件以后不确定性减少的程度,分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大）。
C4.5算法-流程 ：
CART算法的基本思想:
CART既可以用于分类也可以用于回归.它假设决策树是二叉树,内部结点特征的取值为"是"和"否".递归地构建二叉树,对回归树用平方误差最小化准则,对分类数用基尼指数最小化准则.
CART(分类)算法-流程 ：
1. 对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。
2).计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。
3.计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数。
4).在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2.
5).对左右的子节点递归的调用1-4步，生成决策树。
不同分类算法（ID3算法、、CART分类树）应用场景：
ID3算法：只能处理离散型属性，并且对倾向于选择取值较多的属性，只用于分类任务。
C4.5算法：可以处理离散型属性，也可以处理连续型属性，只用于分类任务。
CART算法：可以处理离散型属性，也可以处理连续型属性，可以用于分类也可以用于回归。
一道题分别用ID3，C4.5,CART算法建立决策树让你一目了然以上理论知识的实际运用？
今天回家从早上回家得用10多个小时，明天或者后天更新，敬请期待，嘻嘻。
3. 回归树原理
一个回归树对应着输入空间（即特征空间）的一个划分以及在划分单元上的输出值。采用的是启发式的方法选择最优的点来对输入空间进行划分，找到最优的切分变量后，依次将输入空间划分为两个区域，接着对每个区域重复上述划分过程，直到满足停止条件为止，当输入空间的划分确定时，用平方误差来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值，这样的回归树通常称为最小二乘法回归树。
最小二乘法回归树生成算法：
4. 决策树防止过拟合手段
一.首先来理解一下什么是过拟合？
直观理解过拟合是所建的模型在训练样本中表现很好，但在验证数据集以及测试数据集中表现不佳，比如要建立西瓜上列举的识别树叶的模型，需要对这个模型进行训练，当训练样本中的图片绝大部分是白杨树的树叶图片，经过多次训练后，基本白杨树的树叶图片的特点都全部被模型学习到，重点来了，要是拿一张柳树的叶子作为样本让建立好的模型识别，那很有可能模型会给出柳树的叶子不是树叶的结果，也就是过拟合了。
二.产生过度拟合数据问题的原因有哪些？
1.样本里的噪音数据干扰过大，大到模型过分记住了噪音特征，反而忽略了真实的输入输出间的关系；
2.样本数量太少，达不到训练效果。
3.模型训练过度，匹配度太完美。
三.决策树如何防止过拟合？
剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段，决策树剪枝的基本策略有“预剪枝”(prepruning)和“后剪枝”(post-pruning)
(1)预剪枝（prepruning）：在决策树生成的过程中，对每个结点在划分前先估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶节点；
先剪枝的方法：
有多种不同的方式可以让决策树停止生长，下面介绍几种停止决策树生长的方法：
1.定义一个高度，当决策树达到该高度时就可以停止决策树的生长，这是一种最为简单的方法；
2.达到某个结点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长。这种方法对于处理数据中的数据冲突问题非常有效；
3.定义一个阈值，当达到某个结点的实例个数小于该阈值时就可以停止决策树的生长；
4.定义一个阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值的大小来决定是否停止决策树的生长。
(2)后剪枝（postpruning）：先从训练集生成一棵完整的决策树，然后自底向上地对非叶子结点进行考擦，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
后剪枝的方法：
1)REP方法是一种比较简单的后剪枝的方法，在该方法中，可用的数据被分成两个样例集合：一个训练集用来形成学习到的决策树，一个分离的验证集用来评估这个决策树在后续数据上的精度，确切地说是用来评估修剪这个决策树的影响。这个方法的动机是：即使学习器可能会被训练集中的随机错误和巧合规律所误导，但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。
该剪枝方法考虑将书上的每个节点作为修剪的候选对象，决定是否修剪这个结点有如下步骤组成：
1：删除以此结点为根的子树
2：使其成为叶子结点
3：赋予该结点关联的训练数据的最常见分类
4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点