今天我们探讨一下有关决策树的剪枝，以及由剪枝引出的一系列问题
为什么要剪枝
回顾上一节，我们知道决策树的生成是要达到局部最优，那么我们如何理解这个局部最优呢？我想就是将训练集完全分开，然而将训练集完全分开，就会使模型复杂度迅速上升，从而出现过拟合的现象。于是我们就要用到剪枝，剪掉对于分类并不重要的模型特征，从而达到全局最优
用于ID3与C4.5的剪枝算法
为什么说是用于ID3与C4.5的剪枝算法呢？因为与CART算法相比，他们的剪枝算法是不一样的，不过其实，就算是ID3与C4.5的剪枝算法也有许多种：
- 预剪枝：预剪枝就是在生成决策树时，设置某个约束条件，来限制决策树的增长,限制模型复杂度的上升。但是（据说）预剪枝的算法在现实应用中效果并不令人满意。
- 后剪枝：相比预剪枝，后剪枝就是在生成决策树之后，通过某些规则，对决策树进行剪枝。
我们这里着重介绍两种剪枝算法：
首先是昆兰大佬在C4.5中提出的Pessimistic Error Pruning (PEP，悲观剪枝）：
PEP后剪枝技术是由大师Quinlan提出的。它不需要像REP(错误率降低修剪)样，需要用部分样本作为测试数据，而是完全使用训练数据来生成决策树，又用这些训练数据来完成剪枝。决策树生成和剪枝都使用训练集, 所以会产生错分。
至于原理，我这里就不说了，为什么不说呢？暂时我还没搞懂。所以只贴上一些博客，代日后过来填坑。
悲观剪枝看这里
然后就是李航老师正在书中写的通过决策树的损失函数最小化来进行剪枝，首先我们先看一下决策树的损失函数是什么？
先看第一项：Nt是该叶子节点对应的样本数量，H(T)是该叶子节点的经验熵，|T|是叶子节点的数量，第一项控制表示的是模型对训练集的拟合程度。
再看第二项：alpha是参数，他表示的是模型的复杂程度，也叫作正则化项，用来防止过拟合。
那么，怎么理解这个损失函数呢？
X如果可以取三个值：x1,x2,x3,概率分别为p1,p2,p3。那么-log(p1),-log(p2),-log(p3)相应称为x1,x2,x3的自信息，代表了它们各自的不确定性（信息论）。X的熵指的是X的所有取值的期望，H(X)可以理解为平均值，那X总的不确定性其实也可以用3H(X)来表示。题中N个结点，每个Nt结点都可以理解为这样的X，那么整棵树的不确定性（损失）就是所有叶结点的总熵NtHt(T)的和，而不是平均值Ht(T)的和。函数后面的|T|是对整棵决策树的复杂度的惩罚项，结点数越多，越复杂。
也就是说，原来我们生成决策树的时候，只考虑了模型对训练集的拟合程度，但是却忽略了过拟合的问题，现在我们加入正则化项来解决这个问题。
还想说些什么呢？
开始我和朋友讨论，这种方法可不可以作为预剪枝的算法进行剪枝，后来我想明白了：不行，因为我们这种剪枝方式，是从下而上的剪枝，但是预剪枝是从上到下，因为我们并不知道如果是分裂下去会不会让损失函数减小，比如可能这一次我们判断损失函数会变大，所以停止了生成，但是他的下一次生成可能就会减少，所以，我认为不行。
同时，这里也就提到了REP与PEP的缺点，就是都是从上到下的剪枝，从而会导致一些不必要的剪枝。
正则化
最后，我想提一下有关正则化的东西，我们从L1正则化来理解一下正则化这个概念：
正则化，就是在原来的损失函数中加入正则项，来控制约束模型的复杂度，从而避免过拟合。
L1正则化和L2正则化可以看做是损失函数的惩罚项。所谓『惩罚』是指对损失函数中的某些参数做一些限制。对于线性回归模型，使用L1正则化的模型建叫做Lasso回归，使用L2正则化的模型叫做Ridge回归（岭回归）。下图是Python中Lasso回归的损失函数，式中加号后面一项α||w||1即为L1正则化项。
Lasso regression
L1正则化有助于生成一个稀疏权值矩阵，进而可以用于特征选择。
稀疏矩阵指的是很多元素为0，只有少数元素是非零值的矩阵，即得到的线性回归模型的大部分系数都是0. 通常机器学习中特征数量很多，例如文本处理时，如果将一个词组（term）作为一个特征，那么特征数量会达到上万个（bigram）。在预测或分类时，那么多特征显然难以选择，但是如果代入这些特征得到的模型是一个稀疏模型，表示只有少数特征对这个模型有贡献，绝大部分特征是没有贡献的，或者贡献微小（因为它们前面的系数是0或者是很小的值，即使去掉对模型也没有什么影响），此时我们就可以只关注系数是非零值的特征。这就是稀疏模型与特征选择的关系。
为什么L1正则化可以生成稀疏矩阵呢？
假设有如下带L1正则化的损失函数：
J=J0+α∑w|w|(1)
其中J0J0是原始的损失函数，加号后面的一项是L1正则化项，αα是正则化系数。注意到L1正则化是权值的绝对值之和，J是带有绝对值符号的函数，因此J是不完全可微的。机器学习的任务就是要通过一些方法（比如梯度下降）求出损失函数的最小值。当我们在原始损失函数J0后添加L1正则化项时，相当于对J0做了一个约束。令L=α∑w|w|，则J=J0+L，此时我们的任务变成在LL约束下求出J0J0取最小值的解。考虑二维的情况，即只有两个权值w1和w2，此时L=|w1|+|w2|，对于梯度下降法，求解J0的过程可以画出等值线，同时L1正则化的函数L也可以在w1w2的二维平面上画出来。如下图：
类似，我们可以考虑一下，更高维度的正则项，那么就像二维的情况一样，会有许多突出的"尖"在轴上，所以就会许多交点的值为0。虽然不能很好的解释为什么他消除了过拟合，但是至少我们看到了，通过这种方法，我们用更少的特征做到了一个很好的效果，奥卡姆剃刀。
如果大家还想了解有关L2正则化的内容，大家可以看这个知乎的回答
最后解释一下，为什么这一节没有代码，是因为前面生成决策树的时候埋了一个坑，如果要写的话，可能得从头改了，可你也知道，我懒，哈哈哈，以后补上吧
