目录
1. 信息论基础（熵 联合熵 条件熵 信息增益 基尼不纯度）
2.决策树的不同分类算法（ID3算法、C4.5、CART分类树）的原理及应用场景
3. 回归树原理
4. 决策树防止过拟合手段
5. 模型评估
6. sklearn参数详解，Python绘制决策树
1. 信息论基础（熵 联合熵 条件熵 信息增益 基尼不纯度）
熵：信息是很抽象的概念，一直都无法估计信息量，直到1948年，香农提出了“信息熵”的概念，指出了“信息是用来消除随机不确定性的东西”，解决了对信息的量化度量问题。
熵是用来衡量一个系统混论程度的物理量，代表一个系统中蕴含多少信息量，信息量越大表明一个系统不确定性就越大，就存在越多的可能性。
联合熵：两个随机变量X，Y的联合分布，可以形成联合熵（Joint Entropy），用H(X, Y)表示。即：H(X, Y) = -Σp(x, y) lnp(x, y)
条件熵：H(X|Y)
信息增益：
划分前样本集合D的熵是一定的 ，entroy(前)，使用某个特征A划分数据集D，计算划分后的数据子集的熵 entroy(后)
信息增益 = entroy(前) - entroy(后)
信息增益比：信息增益比 = 惩罚参数 * 信息增益
基尼不纯度：基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率
2.决策树的不同分类算法（ID3算法、C4.5、CART分类树）的原理及应用场景
ID3算法
ID3由Ross Quinlan在1986年提出。ID3决策树可以有多个分支，但是不能处理特征值为连续的情况。决策树是一种贪心算法，每次选取的分割数据的特征都是当前的最佳选择，并不关心是否达到最优。在ID3中，每次根据“最大信息熵增益”选取当前最佳的特征来分割数据，并按照该特征的所有取值来切分，也就是说如果一个特征有4种取值，数据将被切分4份，一旦按某特征切分后，该特征在之后的算法执行中，将不再起作用，所以有观点认为这种切分方式过于迅速。ID3算法十分简单，核心是根据“最大信息熵增益”原则选择划分当前数据集的最好特征，信息熵是信息论里面的概念，是信息的度量方式，不确定度越大或者说越混乱，熵就越大。在建立决策树的过程中，根据特征属性划分数据，使得原本“混乱”的数据的熵(混乱度)减少，按照不同特征划分数据熵减少的程度会不一样。在ID3中选择熵减少程度最大的特征来划分数据（贪心），也就是“最大信息熵增益”原则。下面是计算公式，建议看链接计算信息上增益的实例。
C4.5算法
C4.5是Ross Quinlan在1993年在ID3的基础上改进而提出的。.ID3采用的信息增益度量存在一个缺点，它一般会优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益?(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大).为了避免这个不足C4.5中是用信息增益比率(gain ratio)来作为选择分支的准则。信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的Feature。除此之外，C4.5还弥补了ID3中不能处理特征属性值连续的问题。但是，对连续属性值需要扫描排序，会使C4.5性能下降，
Cart树
CART（Classification and Regression tree）分类回归树由L.Breiman,J.Friedman,R.Olshen和C.Stone于1984年提出。ID3中根据属性值分割数据，之后该特征不会再起作用，这种快速切割的方式会影响算法的准确率。CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用基尼指数（Gini）来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似。CART中每一次迭代都会降低GINI系数。下图显示信息熵增益的一半，Gini指数，分类误差率三种评价指标非常接近。回归时使用均方差作为loss function。基尼系数的计算与信息熵增益的方式非常类似，公式如下
3. 回归树原理
为成功构建以分段常数为叶节点的树，需要度量出数据的一致性。第3章使用树进行分类，会在给定节点时计算数据的混乱度。那么如何计算连续型数值的混乱度呢？在这里，计算连续型数值的混乱度是非常简单的。首先计算所有数据的均值，然后计算每条数据的值到均值的差值。为了对正负差值同等看待，一般使用绝对值或平方值来代替上述差值。上述做法有点类似于前面介绍过的统计学中常用的方差计算。唯一不同就是，方差是平方误差的均值(均方差)，而这里需要的是平方误差的总值(总方差)。总方差可以通过均方差乘以数据集中样本点的个数来得到。
参考：
https://zhuanlan.zhihu.com/p/35351556
4. 决策树防止过拟合手段
预剪枝：是在决策树的生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分即结束树的构建并将当前节点标记为叶结点；
后剪枝：是先从训练集生成一棵完整的决策树，然后自底向上地对叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化为性能提升，则将该子树替换为叶结点。泛化性能的提升可以使用交叉验证数据来检查修剪的效果，通过使用交叉验证数据，测试扩展节点是否会带来改进。如果显示会带来改进，那么我们可以继续扩展该节点。但是，如果精度降低，则不应该扩展，节点应该转换为叶节点。
参考：
https://www.zhihu.com/search?type=content&q=决策树防止过拟合
5. 模型评估
分类树：Accuracy、Precision、Recall、F1 score、ROC曲线和AUC、PR曲线
回归树：平均绝对误差MAE、均方误差MSE、R-squared
6. sklearn参数详解，Python绘制决策树
参考资料：
https://blog.csdn.net/AdamTu18/article/details/88201760
https://blog.csdn.net/qq_24313621/article/details/86722461