决策树算法梳理
1. 信息论基础（熵 联合熵 条件熵 信息增益 基尼不纯度）
熵：熵的本质是一个系统“内在的混乱程度”
联合熵：联合熵是一集变量之间不确定性的衡量手段。
条件熵：
信息增益：
基尼不纯度：基尼不纯度,是指将来自集合中的某种结果随机应用在集合中，某一数据项的预期误差率。是在进行决策树编程 的时候，对于混杂程度的预测中，一种度量方式。其公式为：IG(f)=∑i=1mfi(1−fi)=∑i=1mfi−∑i=1mf2i=1−∑i=1mf2i
2.决策树的不同分类算法（ID3算法、C4.5、CART分类树）的原理及应用场景
ID3算法：
ID3算法的核心思想即在决策树的各个节点上使用信息增益选择特征。从根节点开始，计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，再根据该特征的取值建立子节点，对子节点递归调用上述过程。即：
输入：训练数据集D，特征A，阈值beta ：
输出：决策树T
（1）若D中所有实例属于同一类Ck则T为单节点树，并将Ck作为该节点的类标记，返回T
（2）若A为空集，则通过统计D中实例数最大的类作为该节点类标记（即对于某一节点而言，没有其它特征可以进行分辨了，则对将该节点的类设置为分到该节点数据最多属于的类中），返回T
（3）否则计算A中各特征对D的信息增益,选择信息增益最大的特征 Ag ：
信息增益：g(D,A)=H(D)−H(D|A)
（4）若Ag的信息增益小于阈值，则将T作为单节点树，将D中实例数最大的类作为该节点的标记
（5）否则，对Ag每一个可能值 ai 将D划分为若干非空子集，将子集中实例数最大的类作为标记，构建子节点，返回树T
（6）对第i个子节点，以（5）中的子集作为训练集，A-Ag
作为特征集，递归调用（1）～（5），构建决策树。
C4.5算法：
信息增益与训练数据集D关于特征A的值的熵之比：
gr(D,A)=g(D,A)HA(D)
gr(D,A)=g(D,A)HA(D)
其中：
HA(D)=∑|Di||D|log(|Di||D|)
HA(D)=∑|Di||D|log(|Di||D|)
C4.5算法即是将ID3算法中选择特征的标准用信息增益比代替
CART分类树：
CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
CART算法由以下两步组成：
- 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。 - CART决策树的生成就是递归地构建二叉决策树的过程。CART决策树既可以用于分类也可以用于回归。本文我们仅讨论用于分类的CART。对分类树而言，CART用Gini系数最小化准则来进行特征选择，生成二叉树。 CART生成算法如下：
输入：训练数据集D，停止计算的条件：
输出：CART决策树。
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：
设结点的训练数据集为D，计算现有特征对该数据集的Gini系数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或 “否”将D分割成D1和D2两部分，计算A=a时的Gini系数。
在所有可能的特征A以及它们所有可能的切分点a中，选择Gini系数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
对两个子结点递归地调用步骤l~2，直至满足停止条件。
生成CART决策树。
算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的Gini系数小于预定阈值（样本基本属于同一类），或者没有更多特征。
3. 回归树原理
4. 决策树防止过拟合手段
产生原因1：样本问题
（1）样本里的噪音数据干扰过大，大到模型过分记住了噪音特征，反而忽略了真实的输入输出间的关系；（什么是噪音数据？）
（2）样本抽取错误，包括（但不限于）样本数量太少，抽样方法错误，抽样时没有足够正确考虑业务场景或业务特点，等等导致抽出的样本数据不能有效足够代表业务逻辑或业务场景；
（3）建模时使用了样本中太多无关的输入变量。
针对原因1的解决方法：
合理、有效地抽样，用相对能够反映业务逻辑的训练集去产生决策树；
原因2：构建决策树的方法问题
在决策树模型搭建中，我们使用的算法对于决策树的生长没有合理的限制和修剪的话，决策树的*生长有可能每片叶子里只包含单纯的事件数据或非事件数据，可以想象，这种决策树当然可以完美匹配（拟合）训练数据，但是一旦应用到新的业务真实数据时，效果是一塌糊涂。
上面的原因都是现象，但是其本质只有一个，那就是“业务逻辑理解错误造成的”，无论是抽样，还是噪音，还是决策树等等，如果我们对于业务背景和业务知识非常了解，非常透彻的话，一定是可以避免绝大多数过拟合现象产生的。因为在模型从确定需求，到思路讨论，到搭建，到业务应用验证，各个环节都是可以用业务敏感来防止过拟合于未然的。
针对原因2的解决方法（主要）：
剪枝：提前停止树的增长或者对已经生成的树按照一定的规则进行后剪枝。
5. 模型评估
分类树模型：采用通用的分类模型评估指标
Accuracy
Precision
Recall
F1-score
ROC曲线和AUC
PR曲线
回归树模型：采用通用的回归模型评估指标
MSE
MAE
R^2
6. sklearn参数详解，Python绘制决策树
criterion
默认基尼系数，写'entropy'使用信息增益。
一般，数据维度大、噪音大的时候，用基尼系数；感觉模型拟合程度不够的时候，用信息熵。
random_state
整数，随机数种子，确定之后不管运行多少次这个树不会变。
splitter
默认"best"，可以改成"random"，树就会更大。
一开始就设置random_state和splitter，防止模型过拟合。
以下参数用于剪枝，防止过拟合的关键：
max_depth
最大深度，最常用的参数，适用于高纬度样本量较少。一般可以从3开始试。
min_samples_leaf
每个叶子节点的最小样本数。
min_samples_split
一个节点想再往下分，需要包含的最少样本数。
整数，就是最小数目；浮点数，分完每个节点样本数的最小比例。
属性
feature_importances_
每个特征的重要性。
方法
xx.apply()
返回每条数据最终落在哪个叶子节点。
xx.fit()
返回建好的模型对象。
xx.predict()
返回每条数据预测的标签。
xx.score()
返回accuracy值。
参考博文：
https://blog.****.net/weixin_42169000/article/details/80253507
https://blog.****.net/e15273/article/details/79648502
https://blog.****.net/sinat_32043495/article/details/78729610