最近可能需要做风控方面的事情，需要事先研究下决策树方面的技术，还记得大学里学决策树时候，前面还能好好听，也能理解，一到讲什么悲观剪枝、什么熵、信息增益的那些公式的时候就一脸懵逼了，就听不进去了，所以借此机会再好好学习一下，通过这次学习我发现，现在来看这些东西，比上课那会儿好理解多了。。。我发现总是这样，以前觉得很难的东西，在成长一段时间后再去接触总是会变得简单了。

　　这篇笔记，我主要做三件事吧，第一：记录决策树的原理（ID3、C4.5）以及优化方法（剪枝策略）。第二：自己实现一个简单的决策树模型。三：用之前的神经网络和决策树模型做对比

决策树

　　决策树本质上其实是一个分类器，但是跟那些以向量作为输入的分类算法相比，决策树的优点在于：可读性好，具有描述性，有助于人工分析，我们能清楚的知道为什么这个数据就被分成了这个类。我们先来看个例子,假设我们有一组用户是否能够偿还债务的数据如下：

　　每一行代表一条数据，其中第一列为用户id，我们不用管，第二列到第四列为用户的属性，第五列为对用户能否偿还债务的分类结果。我们可以根据这组数据构建如下这样的一颗决策树：

　　那么，这时候如果再来一个用户，无房产、单身、年收入55k，那么根据上面的决策树，可以预测他无法偿还债务（蓝色虚线路径）。从上面的决策树，还可以知道是否拥有房产可以很大的决定用户是否可以偿还债务，对借贷业务具有指导意义。

属性

　　决策树中使用的属性，分为两种，如上面的例子所示，一种是离散型的属性，如是否拥有房产，它只有两个值，是和否，对于这种离散型的属性，我们可以按照两种方式来分类，第一，将一部分属性划分为一个子集，属于这个子集的就是一类，不属于这个子集的就是另一类，这样构造出来的是二叉树。第二，将每种离散属性作为一个单独的类别，这样构造出一个多叉树。

　　还有一种是连续型的属性，如上面例子中的年收入，对于这种属性，我们可以定一个阈值，令大于等于这个阈值的属性归为一类，而小于这个阈值的属性归为另外一类。

树的构建过程

　　那么给定一堆数据后，我们怎么构建一颗决策树呢，那肯定就是自顶向下不断地去选择节点的分类属性呗，所以关键在于我们怎么选择每个节点的分类属性呢？

　　按普通人能理解的方式：如果我选择了一个属性，这个属性有两个离散值A和B，样本中属于A的数据都被分类为1，而样本中属于B的数据都被分为2.还有一个属性也有两个离散值C和D，样本中属于C的数据有被分为1也有被分为2的，而样本中属于D的数据也一样有被分为1也有被分为2的，那么你这时候会选择哪个属性来分类呢？

　　肯定选第一个啊，第一个属性不就解决我们的分类问题了吗？以后只要碰到A属性值的数据那就是1类别，如果是B属性的数据那就是2类别，不用多想了啊。但是如果你选择第二个属性来分类，遇到C属性的数据，你还是不知道它属于哪一类，同样遇到D属性的数据，你也不知道它属于哪一类，可能还是要通过别的属性继续判断。

　　所以，根据一般人的观察，对于每个节点属性的选择，我们肯定是要选择，那些能尽可能将数据分类分的更纯的属性，但是这里的更纯我们虽然好理解，但是如果没有一个公式去定义，那么决策树也不好构建，所以利用统计学的相关知识，给出了很多对纯的定义。下面我们来介绍ID3算法里用到的信息增益。

信息增益

　　在介绍信息增益前，先来了解什么叫信息熵。信息熵表示的是不确定度，均匀分布时，不确定度最大，此时信息熵也就最大。当选择某个特征对数据集进行分类时，分类后的数据集信息熵会比分类前的小，其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。而我们的目标就是选择信息增益最大的特征来做为该节点的分类特征

　　那么为了确定信息增益最大的特征，我们需要计算出当前的信息熵，然后对每个特征，计算出分类后的信息熵，接着计算他们差值，得到信息增益，再选择最大的那个。

　　那么分类前的信息熵如何计算？假设在样本数据集 D 中，混有 c 种类别的数据，可以计算出该数据中的信息熵：

　　其中 D 表示训练数据集，c 表示数据类别数，Pi 表示类别 i 样本数量占所有样本的比例。

　　对每个特征，分类后的信息熵又如何计算呢？对应数据集 D，选择特征 A 作为决策树判断节点时，在特征 A 作用后的信息熵计算如下：

　　 　　其中 k 表示样本 D 被分为 k 个部分。

　　信息增益表示数据集 D 在特征 A 的作用后，其信息熵减少的值。公式如下： 　　

　　对于决策树节点最合适的特征选择，就是 Gain(A) 值最大的特征。

增益率

　　另一种刻画“纯度”的标准，增益率，这也是C4.5算法与ID3的不同之处。即在选择分类特征时不是选择信息增益最大的，而是选择增益率最大的。

　　这是因为ID3算法存在一个问题，就是偏向于多值属性，例如，如果存在唯一标识属性ID，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率（gain ratio）的信息增益扩充，试图克服这个偏倚。

　　C4.5算法首先定义了“分裂信息”，其定义可以表示成：

　　其中各符号意义与ID3算法相同，然后，增益率被定义为：

　　从这个公式可以看到，如果对于唯一性ID这样的多值属性，虽然Gain(A)大，但是它的split_info也会大，所以就不会被选择作为分类特征了，C4.5选择具有最大增益率的属性作为分裂属性，其具体应用与ID3类似，不再赘述。

基尼指数

　　基尼指数是另一种数据的不纯度的度量方法，其公式为：

　　其中 c 表示数据集中类别的数量，Pi 表示类别 i 样本数量占所有样本的比例。 从该公式可以看出，当数据集中数据混合的程度越高，基尼指数也就越高。当数据集 D 只有一种数据类型，那么基尼指数的值为最低 0。如果选取的属性为 A，那么分裂后的数据集 D 的基尼指数的计算公式为：

　　其中 k 表示样本 D 被分为 k 个部分，数据集 D 分裂成为 k 个 Dj 数据集。

　　对于特征选取，需要选择最小的分裂后的基尼指数。也可以用基尼指数增益值作为决策树选择特征的依据。公式如下：

　　于是，有了选择特征的方法，我们就可以从根节点开始，由顶至下地构造决策树了，直到某一个节点的所有数据都是同一类别，这个节点就被划为叶子节点了。

　　但是偶尔也存在一些特殊的情况，例如当所有属性都利用完之后，到某一个节点还是存在属于不同类别的数据，这种情况下，我们可以将该节点作为叶子节点，并将属于该节点下的样本中大多数所属的类别作为该节点的类别

剪枝

　　 　　剪枝对于决策树的优化是很重要的，因为我们是用训练集去构建决策树，这样很容易产生过拟合的现象，可能树的深度过深，节点过多。训练出来的决策树在训练集上有很高的准确率，但是在其他数据上也许就表现的很差。这时候，我们就需要对决策树进行剪枝。

　　剪枝分为先剪枝和后剪枝。

　　先剪枝：就是预先停止决策树的生长，也就是在构建决策树的过程中，我们就停止了决策树某个节点的继续分裂，而让它成为叶子节点。例如，在某个节点，我们本还可以继续选择一个特征来分类，但是我们不再选择特征，而让该节点成为叶子节点，并选择一个大多数样本所属的类别作为该叶子节点的类别，这就是先剪枝。至于在什么条件下需要这么做，就可以自己定制了，例如树的深度到达某一个阈值时，或者是样本中超过某个阈值的数据都属于一个类别后等等。但是先剪枝导致训练出来的树的深度较小，并且这种优化方案是没有什么依据的，准确率会较低。

　　后剪枝：后剪枝则是在决策树构建完成后，根据一些规则去将一些子树替换为叶节点，从而达到剪枝的目的。后剪枝的准确度比先剪枝要高，但是会导致之前的一些计算的浪费。这里主要介绍三种后剪枝算法：Reduced-Error Pruning(REP,错误率降低剪枝）、Pesimistic-Error Pruning(PEP,悲观错误剪枝）、Cost-Complexity Pruning（CCP，代价复杂度剪枝)

REP 错误率降低剪枝

　　首先，该剪枝算法，需要用验证集来验证是否需要剪枝，也就是先把数据集分为训练集和验证集，训练集用于训练得到决策树，验证集用来决定如何剪枝。

　　这个方法的动机是：即使学习器可能会被训练集中的随机错误和巧合规律所误导，但验证集合不大可能表现出同样的随机波动。所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验。

　　方法是，自底向上处理每个非叶结点，决定是否修剪这个结点有如下步骤组成：

　　1：删除以此结点为根的子树

　　2：使其成为叶子结点

　　3：赋予该结点关联的训练数据的最常见分类

　　4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点

　　这样一直处理，直到无法找到这样的节点为止。

　　REP是最简单的剪枝策略，但是通常会造成过度修剪，所以一般不采用。

PEP 悲观错误剪枝

　　悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪，它与REP的区别在于，只考虑训练集，而不利用验证集来计算错误率。

　　首先，我们自顶向下处理每个非叶子节点，首先计算该节点的错误率，假设以该节点为根节点的子树下有L个叶子节点，对于其中一个叶子节点来说，覆盖N个样本，其中有E个错误分类了，那么它的误判率就是E/N，但是我们知道，把一颗子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，所以，我们在计算子树的错误率时，要加上一个惩罚因子，因此子树中一个叶子节点的错误率就是(E+0.5)/N。这个0.5就是惩罚因子。那么对于这颗子树，因为它有L个叶子节点，所以它的错误率e1就是：

　　这样的话，我们可以看到一颗子树虽然具有多个子节点，但由于加上了惩罚因子，所以子树的误判率计算未必占到便宜。

　　接着，假设把以该节点为根节点的子树替换为叶子节点，我们需要计算叶子节点的错误率。假设替换后，误判个数为J，覆盖样本还是N，那么替换后的叶子节点错误率e2为：（J+0.5)/N。这里也加上0.5，是因为我们给每个叶子节点都要加上惩罚因子，当该节点被替换为叶子结点后，他的误判数也得遵守规则，加上一个0.5.

　　这样，我们得到了替换前的子树的错误率和替换后的叶子结点错误率，是不是直接相比，如果替换后的错误率低，就可以修剪呢？并不是，而是要满足：当子树的误判个数大过对应叶节点的误判个数一个标准差之后，就决定剪枝。那么这个标准差怎么计算呢，首先，节点的误判次数是一个二项分布（伯努利分布），误判的概率为p，p就是上面那个公式计算得到的e1，那么标准差t就是：

　　这样，只要满足 N*e1-t> N*e2 就可以剪枝了。

　　举例如下：

　　但是PEP剪枝算法是自顶向下，所以也跟先剪枝一样存在一个问题，就是容易造成剪枝过度。

CCP 代价复杂度剪枝

　　CCP剪枝算法分为两个步骤：

　　1.对于完全决策树T的每个非叶结点计算α值，循环剪掉具有最小α值的子树，直到剩下根节点。在该步可得到一系列的剪枝树｛T0，T1，T2……Tm｝,其中T0为原有的完全决策树，Tm为根结点，Ti+1为对Ti进行剪枝的结果；

　　2.从子树序列中，根据真实的误差估计选择最佳决策树。也就是从上面那个序列中，拿出每一个决策树，根据样本，计算一下错误率，然后选择错误率最小的那颗树作为剪枝结果。

　　可以看到，关键在于α值如何计算，α又叫表面误差率增益值，计算及示例如下：

随机森林

　　随机森林是为了解决决策树过拟合的另一种有效方法。它的核心在于使用多个独立构建的决策树去对数据分类，最后采用投票的方式（多数决策树的分类结果）获得最终的分类结果。 　　 　　随机森林的重点在于随机，随机表现为两个方面：一是采样数据随机，它使用的是有放回的随机抽样。例如我有N个样本，我每次从里面抽出来一个样本，然后再放回去，再重复抽，这样最后得到的数据集里可能会出现重复的数据。这样森林中的每个决策树都使用的不是相同的数据，相对独立，而且也不是用的全部的样本数据，因此也不会过度的overfitting。

　　第二个随机就是，在确定节点的分类特征时，并不会选择全部的特征作为候选特征，而是随机选择几个固定的特征，这样又进一步降低了树之间的相关性。当然这个选择特征的数量不能太小也不能太大，太小了单颗树的精度太低，太大了树之间的相关性又加强了。

　　当然，也可以在最好的几个分类属性中随机选择一个作为分类特征。

　　那么至于为什么随机森林效果会好，我们看这样一个例子：假设每颗树不一样，单独预测错误率大概都是40%(够弱了吧，很多时候都会犯错)，但三颗树组合的后的错误率就变成了35.2%（至少一半以上（两颗树）同时犯错结果才会犯错），其计算方法为：

　　另外，因为每棵树都是独立的，因此随机森林很适合并行化计算，训练速度快。

GBDT