决策树算法梳理

1. 信息论基础（熵 联合熵 条件熵 信息增益 基尼不纯度）
   a. 熵
   信息熵
   假设集合D中有y类样本，第k类的样本出现频率为Pk,则样本D的熵为
   
   其中，当样本 DD 中 |y|∣y∣ 类样本均匀分布时，这时信息熵最大，纯度最小，熵为
   
   当样本D中只有一类样本，此时信息熵最小，纯度最大，熵为
   
   ** 联合熵**
   因此如果在x的基础上加入了一个y，那么联合熵H(x,y) ，一定大于等于H(x)，H(y)，当且仅当加入的是常量的情况下，等号才成立。例如掷硬币，熵是1枚硬币，联合熵是2枚，肯定是联合更不确定了，熵更大。
   信息熵
   在某个条件确定的基础上，另一件事发生的概率H(y|x),确定性更大，熵更小。
   b. 信息增益
   假定在样本D中有某个离散特征 a有 V 个可能的取值 ，若使用特征 a 来对样本集 D 进行划分，则会产生 V个分支结点，其中第 v 个分支结点样本记为Dv，特征 a 对样本集 D 进行划分所获得的“信息增益”为
   

信息增益越大，表示使用特征a来对样本集进行划分所获得的纯度提升越大。
c.基尼系数
假定当前样本集合 D 中第 k 类样本所占的比例为 Pk，则 D 的基尼系数为

2. 决策树的不同分类算法（ID3算法、C4.5、CART分类树）的原理及应用场景
ID3决策树可以有多个分支，但是不能处理特征值为连续的情况。决策树是一种贪心算法，每次选取的分割数据的特征都是当前的最佳选择，并不关心是否达到最优。在ID3中，每次根据“最大信息增益”选取当前最佳的特征来分割数据，并按照该特征的所有取值来切分。
C4.5针对ID3采用的信息增益度量存在一个缺点，它一般会优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大)。但是较多取值的属性来进行划分带来的问题是它的泛化能力比较弱，不能够对新样本进行有效的预测。为了避免这个不足，C4.5中是用信息增益比率(gain ratio)来作为选择分支的准则。信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的Feature，在候选属性中选择基尼系数最小的属性作为最优划分属性。除此之外，C4.5还弥补了ID3中不能处理特征属性值连续的问题。但是，对连续属性值需要扫描排序，会使C4.5性能下降。信息增益率为：

增益率对特征值较少的特征有一定偏好，因此 C4.5 算法选择特征的方法是先从候选特征中选出信息增益高于平均水平的特征，再从这些特征中选择增益率最高的。
CART
ID3中根据属性值分割数据，之后该特征不会再起作用，这种快速切割的方式会影响算法的准确率。CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用基尼指数（Gini）来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似。CART中每一次迭代都会降低GINI系数。当CART是分类树时，采用GINI值作为节点分裂的依据；当CART是回归树时，采用样本的最小方差作为节点分裂的依据。

3. 分类树 VS 回归树
   提到决策树算法，很多想到的就是上面提到的ID3、C4.5、CART分类决策树。其实决策树分为分类树和回归树，前者用于分类，如晴天/阴天/雨天、用户性别、邮件是否是垃圾邮件，后者用于预测实数值，如明天的温度、用户的年龄等。
   作为对比，先说分类树，我们知道ID3、C4.5分类树在每次分枝时，是穷举每一个特征属性的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的熵最大的feature和阈值。以性别为例，按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。
   回归树总体流程也是类似，不过在每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差–即（每个人的年龄-预测年龄）^2 的总和 / N，或者说是每个人的预测误差平方和 除以 N。这很好理解，被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最靠谱的分枝依据。分枝直到每个叶子节点上人的年龄都唯一（这太难了）或者达到预设的终止条件（如叶子个数上限），若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

4. 决策树防止过拟合手段
   产生过度拟合数据问题的原因有哪些？

原因1：样本问题
（1）样本里的噪音数据干扰过大，大到模型过分记住了噪音特征，反而忽略了真实的输入输出间的关系；
（2）样本数量太少，抽样时没有足够正确考虑业务场景或业务特点等；
（3）建模时使用了样本中太多无关的输入变量。
原因2：构建决策树的方法问题
在决策树模型搭建中，我们使用的算法对于决策树的生长没有合理的限制和修剪的话，决策树的自由生长有可能每片叶子里只包含单纯的事件数据或非事件数据，可以想象，这种决策树当然可以完美匹配（拟合）训练数据，但是一旦应用到新的业务真实数据时，效果是一塌糊涂。

如何解决过度拟合数据问题的发生？

针对原因1的解决方法：合理、有效地抽样，用相对能够反映业务逻辑的训练集去产生决策树；

针对原因2的解决方法：剪枝：提前停止树的增长或者对已经生成的树按照一定的规则进行后剪枝。

剪枝的方法
剪枝是一个简化过拟合决策树的过程。有两种常用的剪枝方法：

a. 先剪枝（prepruning）：通过提前停止树的构建而对树“剪枝”

先剪枝的方法
1.定义决策树高度，当决策树达到该高度时就可以停止决策树的生长，这是一种最为简单的方法；2.达到某个结点的实例具有相同的特征向量，即使这些实例不属于同一类，也可以停止决策树的生长。这种方法对于处理数据中的数据冲突问题非常有效； 3.定义子节点个数阈值，当达到某个结点的实例个数小于该阈值时就可以停止决策树的生长； 4.定义增益阈值，通过计算每次扩张对系统性能的增益，并比较增益值与该阈值的大小来决定是否停止决策树的生长。

b.后剪枝（postpruning）：它首先构造完整的决策树，允许树过度拟合训练数据，然后对那些置信度不够的结点子树用叶子结点来代替。这个叶子节点所标识的类别通过多数原则(majority class criterion)确定。相比于先剪枝，这种方法更常用，正是因为在先剪枝方法中精确地估计何时停止树增长很困难。

后剪枝的方法
1)REP(错误率降低修剪)是一种比较简单的后剪枝的方法，在该方法中，可用的数据被分成两个样例集合：一个训练集用来形成学习到的决策树，一个分离的验证集用来评估这个决策树在后续数据上的精度，确切地说是用来评估修剪这个决策树的影响。决定是否修剪这个结点有如下步骤组成：
1：删除以此结点为根的子树，使其成为叶子结点
2：赋予该结点关联的训练数据的最常见分类
3：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点
由于使用独立的测试集验证原始决策树，修改后的决策树可能偏向于过度修剪。由于一些干扰的数据也可能出现在验证集中，若数据集较小，通常不考虑采用REP算法。

2)PEP,悲观错误剪枝,悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪。该方法引入了统计学上连续修正的概念弥补REP中的缺陷，在评价子树的训练错误公式中添加了一个常数，假定每个叶子结点都自动对实例的某个部分进行错误的分类。它不需要像REP那样，需要用部分样本作为测试数据，而是完全使用训练数据来生成决策树，又用这些训练数据来完成剪枝。决策树生成和剪枝都使用训练集, 所以会产生错分。
把一棵子树（具有多个叶子节点）的分类用一个叶子节点来替代的话，在训练集上的误判率肯定是上升的，但是在测试数据上不一定，我们需要把子树的误判计算加上一个经验性的惩罚因子，用于估计它在测试数据上的误判率。对于一棵叶子节点，它覆盖了N个样本，其中有E个错误，那么该叶子节点的错误率为（E+0.5）/N。这个0.5就是惩罚因子，那么对于该棵子树，假设它有L个叶子节点，则该子树的误判率估计为:

剪枝后该子树内部节点变成了叶子节点，该叶子结点的误判个数J同样也需要加上一个惩罚因子，变成J+0.5。那么子树是否可以被剪枝就取决于剪枝后的错误J+0.5在

的标准误差内。对于样本的误差率e，我们可以根据经验把它估计成伯努利分布，那么可以估计出该子树的误判次数均值和标准差

使用训练数据，子树总是比替换为一个叶节点后产生的误差小，但是使用校正的误差计算方法却并非如此。剪枝的条件:当子树的误判个数大过对应叶节点的误判个数一个标准差之后，就决定剪枝：

这个条件就是剪枝的标准。当然并不一定非要大一个标准差，可以给定任意的置信区间，我们设定一定的显著性因子，就可以估算出误判次数的上下界。

5. 模型评估
   自助法（bootstrap）：
   训练集是对于原数据集的有放回抽样，如果原始数据集N，可以证明，大小为N的自助样本大约包含原数据63.2%的记录。当N充分大的时候，1-（1-1/N）^(N) 概率逼近 1-e^(-1)=0.632。抽样 b 次，产生 b 个bootstrap样本，则，总准确率为（accs为包含所有样本计算的准确率）：
   
   准确度的区间估计：
   将分类问题看做二项分布，则有：
   令 X 为模型正确分类，p 为准确率，X 服从均值 Np、方差 Np（1-p）的二项分布。acc=X/N为均值 p，方差 p（1-p）/N 的二项分布。acc 的置信区间：
   

6. sklearn参数详解，Python绘制决策树
   1.Criterion这个参数正是用来决定不纯度的计算方法的。sklearn提供了两种选择：
   1）输入”entropy“，使用信息熵（Entropy）
   2）输入”gini“，使用基尼系数（Gini Impurity）

   2. random_state & splitter
   random_state用来设置分枝中的随机模式的参数，默认None，在高维度时随机性会表现更明显，低维度的数据（比如鸢尾花数据集），随机性几乎不会显现。输入任意整数，会一直长出同一棵树，让模型稳定下来。

splitter也是用来控制决策树中的随机选项的，有两种输入值，输入”best"，决策树在分枝时虽然随机，但是还是会优先选择更重要的特征进行分枝（重要性可以通过属性feature_importances_查看），输入“random"，决策树在分枝时会更加随机，树会因为含有更多的不必要信息而更深更大，并因这些不必要信息而降低对训练集的拟合。这也是防止过拟合的一种方式。当你预测到你的模型会过拟合，用这两个参数来帮助你降低树建成之后过拟合的可能性。当然，树一旦建成，我们依然是使用剪枝参数来防止过拟合。

3.剪枝参数
max_depth：限制树的最大深度，超过设定深度的树枝全部剪掉
min_samples_leaf 限定一个节点在分枝后的每个子节点都必须包含至少min_samples_leaf个训练样本，否则分枝就不会发生，或者，分枝会朝着满足每个子节点都包含min_samples_leaf个样本的方向去发生
min_samples_split限定，一个节点必须要包含至少min_samples_split个训练样本，这个节点才允许被分枝，否则分枝就不会发生。
max_features限制分枝时考虑的特征个数，超过限制个数的特征都会被舍弃。
min_impurity_decrease限制信息增益的大小，信息增益小于设定数值的分枝不会发生。

4.score确认最优模型参数

5.目标权重参数
class_weight样本标签平衡的参数。对样本标签进行一定的均衡，给少量的标签更多的权重，让模型更偏向少数类，向捕获少数类的方向建模。该参数默认None，此模式表示自动给与数据集中的所有标签相同的权重。
min_weight_fraction_leaf基于权重的剪枝参数。这将比不知道样本权重的标准（比如min_samples_leaf）更少偏向主导类。如果样本是加权的，则使用基于权重的预修剪标准来更容易优化树结构，这确保叶节点至少包含样本权重的总和的一小部分。

6.重要属性和接口
属性是在模型训练之后，能够调用查看的模型的各种性质。对决策树来说，最重要的是feature_importances_，能够查看各个特征对模型的重要性。