一.基本原理
决策树是一种树状结构模型，每一个根节点都是一个特征判断，它的叶子节点就是它的特征分类结果
决策树是一种分类和回归的基本模型，是一棵树的形式，其实就是将平时所说的 if-else 语句构建成了树的形式。决策树主要包括三个部分：内部节点，叶节点，边。构建决策树就是一个递归的选择内部节点，计算划分条件的边，最后到达叶子节点的过程
- 内部节点：划分的特征，也叫决策节点
- 叶节点：表示一个类，对应于决策结果
- 边：代表划分的条件
无论是哪种决策树算法，其目的都是为了让模型的不确定性降低的越快越好
基于评价指标的不同，主要分为：ID3算法，C4.5算法，CART算法
C4.5算法
ID3算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。ID3算法计算每个属性的信息增益，并选取具有最高增益的属性作为给定的测试属性。C4.5算法核心思想是ID3算法，是ID3算法的改进，改进方面有：
- 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足
- 在树构造过程中进行剪枝
- 能处理非离散的数据
- 能处理不完整的数据
优点：产生的分类规则易于理解，准确率较高
CART分类与回归树
是一种决策树分类方法，采用基于最小距离的基尼指数估计函数，用来决定由该子数据集生成的决策树的拓展形。如果目标变量是标称的，称为分类树；如果目标变量是连续的，称为回归树。分类树是使用树结构算法将数据分成离散类的方法
优点
- 非常灵活，可以允许有部分错分成本，还可指定先验概率分布，可使用自动的成本复杂性剪枝来得到归纳性更强的树
- 在面对诸如存在缺失值、变量数多等问题时CART 显得非常稳健
缺点
- 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效
- C4.5只适合于能够驻留于内存的数据集，当训练集大的无法在内容容纳时，程序无法运行
二.优缺点
优点
- 易于理解和解释，可以可视化分析，容易提取出规则
- 可以同时处理标称型数据和数值型数据
- 测试数据集时，运行速度比较快
- 可以很好的扩展到大型数据库中，同时它的大小独立于数据库的大小
- 计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征
- 擅长对人，地点，事物的一系列不同特征，品质，特性进行评估
- 需要很少的数据准备。其它很多算法都需要数据规范化，需要创建虚拟变量并删除空值等。但请注意，sklearn中的决策树模块不支持对缺失值的处理
- 既可以做回归又可以做分类
- 能够处理多输出问题，即含有多个标签的问题，注意与一个标签中含有多种标签分类的问题区分开
- 即使其假设在某种程度上违反了生成数据的真实模型，也能够表现良好
缺点
- 容易过拟合（后续出现了随机森林，减小了过拟合现象），使用剪枝来避免过拟合
- 对缺失数据处理比较困难
- 忽略数据集中属性的相互关联
- ID3算法计算信息增益时偏向数值比较多的特征
- 决策树可能不稳定，数据中微小的变化可能导致生成完全不同的树，这个问题需要通过集成算法来解决
- 决策树的学习是基于贪婪算法，它靠优化局部最优（每个节点的最优）来试图达到整体的最优，但这种做法不能保证返回全局最优决策树。这个问题可以由集成算法来解决，在随机森林中，特征和样本会在分枝过程中被随机采样
- 如果标签中的某些类占主导地位，决策树学习者会创建偏向主导类的树。因此，建议在拟合决策树之前平衡数据集
三.适用场景
- 适用于小数据集，在进行逐步应答过程中，典型的决策树分析会使用分层变量或决策节点。例如，可将一个给定用户分类成信用可靠或不可靠
- 适合数值型和标称型数据
- 基于规则的信用评估
- 赛马结果预测
- 因为它能够生成清晰的基于特征选择不同预测结果的树状结构，数据分析师希望更好地理解手上的数据的时候往往可以使用决策树
- 常见于垃圾邮件躲避检测中。它是相对容易被攻击的分类器。这里的攻击是指人为改变一些特征，使得分类器判断错误。因为决策树最终在底层判断是基于单个条件的，攻击者往往只需要改变很少的特征就可以逃过监测
- 受限于它的简单性，决策树更大的用处是作为一些更有用的算法的基石
四.推导
ID3算法
回归树
CART算法
五.常见面试题
1.信息增益到底怎么理解？
熵：表示随机变量的不确定性
条件熵：在一个条件下，随机变量的不确定性
信息增益：熵 - 条件熵
在一个条件下，信息不确定性减少的程度
所以，在特征选择的时候常常用信息增益，如果信息增益大的话，那么这个特征对于分类来说很关键，决策树就是这样来找特征的
2.cart树怎么剪枝？
3. 决策树和条件概率分布的关系？
决策树可以表示成给定条件下在特征空间和类空间上的条件概率分布
决策树实际上是将特征空间划分成了互不相交的单元，每个从根节点到叶节点的路径都对应着一个单元。决策树所表示的条件概率分布由各个单元给定条件下的类的条件概率分布组成。哪个类别有较大的条件概率，就把该单元中的实例强行划分为该类别
4.为什么使用贪心和其发生搜索建立决策树，为什么不直接使用暴力搜索建立最优的决策树？
决策树的目的是构建一个与训练数据拟合很好，并且复杂度小的决策树。因为从所有可能的决策树中直接选择最优的决策树是NP完全问题，在使用中一般使用启发式方法学习相对最优的决策树
5.决策树在做分类的过程中，会对特征进行重复选取吗？
会有可能
- 若特征为离散特征，如果决策树为二叉树，则可以在分类的子区间继续划分，如果决策树为多叉树，通常进行一次划分
- 若特征是连续特征，例如在CART树中。那么在一层划分的时候选择到了它，和别的特征划分到一个子树里（这些特征的基尼系数减小的更多），在下一层划分中，还有可能选中它和其他特征放在一起，因为CART就是这样不停地二分特征的unique的
6.如果特征很多，决策树中最后没有用到的特征一定是无用的吗？
不是无用的。可以从两个角度考虑：
- 特征替代性。如果可以已经使用的特征A和特征B可以提取特征C，特征C可能就没有被使用，但是如果把特征C单独拿出来进行训练，依然有效
- 决策树的每一条路径就是计算条件概率的条件。前面的条件如果包含了后面的条件，只是这个条件在这棵树中是无用的，如果把这个条件拿出来也是可以帮助分析数据
7.决策树算法的停止条件？
①最小节点数
当节点的数据量小于一个指定的数量时，不继续分裂，两个原因：
- 数据量较少时，再做分裂容易强化噪声数据的作用
- 降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响
②熵或者基尼值小于阈值
- 当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度数，节点停止分裂
③决策树的深度
- 达到指定的条件，决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂
④所有特征已经使用完毕，不能继续进行分裂
8.决策树出现过拟合的原因及解决方法？
可能原因：
- 在决策树构建的过程中，对决策树的生长没有进行合理的限制（剪枝）
- 在建模过程中使用了较多的输出变量，变量较多也容易产生过拟合
- 样本中有一些噪声数据，噪声数据对决策树的构建干扰很多，没有对噪声数据进行有效的剔除
解决方法：
- 选择合理的参数进行剪枝，可以分为预剪枝和后剪枝，一般我们用后剪枝来做
- K-folds交叉验证，将训练集分为k份，然后进行k次的交叉验证，每次使用k-1份作为训练样本数据集，另外一份作为测试集合
- 减少特征，计算每一个特征和响应变量的相关性，常见的为皮尔逊相关系数，将相关性较小的变量剔除，当然还有一些其它的方法来进行特征筛选，比如基于决策树的特征筛选，通过正则化的方式来进行特征选取等
9.简单解释一下预剪枝和后剪枝？
剪枝是预防决策树过拟合的方法之一，剪掉一些枝叶，可以提升模型的泛化能力。决策树的剪枝通常有两种方法，预剪枝和后剪枝
- 预剪枝的核心思想是在树中结点进行扩展之前，先计算当前的划分是否能带来模型泛化能力的提升，如果不能，则不再继续生长子树。此时可能存在不同类别的样本同时存于结点中，按照多数投票的原则判断该结点所属类别。预剪枝对于何时停止决策树的生长有以下几种方法：①当树到达一定深度的时候，停止树的生长 ②当到达当前结点的样本数量小于某个阈值的时候，停止树的生长 ③计算每次分裂对测试集的准确度提升，当小于某个阈值的时候，不再继续扩展
- 后剪枝的核心思想是让算法生成一棵完全生长的决策树，然后底层向上计算是否剪枝。剪枝过程将子树删除，用一个叶子结点替换该节点的类别同样按照多数投票的原则进行判断。同样的，后剪枝也可以通过在测试集上的准确率进行判断，如果剪枝过后准确率有所提升则进行剪枝。相比于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树，但时间开销会更大
10.ID3，C4.5，CART三者之间的区别是什么？
划分标准
- ID3使用信息增益偏向特征值多的特征
- C4.5使用信息增益克服信息增益的缺点，偏向于特征值小的特征
- CART使用基尼指数克服C4.5需要求log的巨大计算量，偏向于特征值较多的特征
使用场景
- ID3和C4.5都只能用于分类问题，CART可以用于分类和回归问题
- ID3和C4.5是多叉树，速度较慢，CART是二叉树，计算速度很快
样本数据
- ID3只能处理离散数据且缺失值敏感，C4.5和CART可以处理连续型数据且有多种方式处理缺失值
- 从样本量考虑的话，小样本建议C4.5，大样本建议CART
- C4.5处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而CART本身是一种大样本的统计方法，小样本处理下泛化误差较大
样本特征
- ID3和C4.5层级之间只使用一次特征，CART可多次重复使用特征
剪枝策略
- ID3没有剪枝策略
- C4.5是通过悲观剪枝策略来修正树的准确性
- CART是通过代价复杂度剪枝
11.什么样的决策树是比较好的决策树？
小的决策树要比深的大的决策树要好
- 可解释性比较好
- 冗余属性可以被去除
- 降低过拟合的风险