决策树

决策树是一种基本的分类与回归方法，其每个非叶结点表示一个特征属性，每个叶结点存放一个类别(target)。使用决策树进行决策的的过程就是从根节点开始，根据非叶结点表示的特征属性逐一向下进行判断，直到到达对应的叶子结点，并以该叶子结点的类别作为决策结果。

1. 决策树生成算法

决策树学习过程中最关键的是如何选择最优的划分属性，一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”。

信息熵(information entropy)：是度量样本集合纯度常用的一种指标。若样本的属性都一样，则包含的信息很单一，信息熵的值较小；若样本的属性不一样，则包含的信息较多，信息熵的值较大。假定当前样本集合 中第 类样本所占比例为 ，则 的信息熵定义为：

基尼指数(gini index)：是另一个表示样本纯度的方法。直观来说 反映了从数据集 中随机抽取两个样本，其类别标记不一致的概率。因此基尼指数越小，数据集 的纯度越高：
采用基尼指数计算更快

1）ID3算法

ID3算法的核心是根据信息增益进行决策树的生长：

其中 表示当前选择的特征属性， 表示根据特征属性 划分后的样本子集。 |y|：target属性的总数，常为2，{见面，不见}V：特征a中的属性数目，如a为学历，{本科，硕士，博士}，此时V=3

直观理解：某特征a包含的种类v越多，则相当于把D越细分，每个v中包含的数据量越少，则越可能每个v中包含的target类越少，根据信息熵公式，则信息量越小，那么信息增益就越大。所以ID3更偏好取值多的特征。 缺点：实际上，信息增益准则对可取值数目较多的属性有所偏好。取值多的特征，更容易使样本子集更纯，故选择该特征得到的信息增益更大，因此训练得到的是一棵庞大且深度较浅的树。

2）C4.5算法

为减少信息增益准则的偏好带来的不利影响，C4.5决策树算法使用“增益率”来选择最优划分属性：

其中：

若a的子集数目越多(即V越大)，则 的值越大，信息增益率准则偏向选择取值较少的特征

3）CART算法

CART算法根据基尼指数进行决策树的生长：

2. 树长到什么时候停止

• 当前结点包含的样本全属于同一类别(target)，无需划分
• 当前属性集为空，所有属性都已经用过了

• 所有样本在所有属性上取值相同，无法划分

  3. 剪枝处理

  剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段，分为“预剪枝”和“后剪枝”。
  进行剪枝时，将数据集分为训练集和验证集。根据某叶子结点中包含的训练集类别哪个最多判断该叶子结点属于什么类别，根据验证集被正确分类比例判断决策树的泛化能力。

  1）预剪枝

  在决策树生成过程中，对每个结点在划分前进先进行估计(用验证集)，若当前结点的划分不能带来决策树泛化性能提升，则停止该结点划分，并将当前结点标记为叶结点。

  2）后剪枝

  先根据训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

  4. 回归决策树

  CART(Classification And Regression Tree)是决策树的一种，CART算法既可以用于创建分类树（Classification Tree），也可以用于创建回归树（Regression Tree），两者在建树的过程稍有差异。
  CART回归树是假设树为二叉树，通过不断将特征进行分裂。比如当前树结点是基于第j个特征值进行分裂的，设该特征值小于s的样本划分为左子树，大于s的样本划分为右子树。
  
  而CART回归树实质上就是在该特征维度对样本空间进行划分，而这种空间划分的优化是一种NP难问题，因此，在决策树模型中是使用启发式方法解决。典型CART回归树产生的目标函数为（与分类的gini指标不同）：
  
  因此，当我们为了求解最优的切分特征j和最优的切分点s，就转化为求解这么一个目标函数：
  
  所以我们只要遍历所有特征的的所有切分点，就能找到最优的切分特征和切分点。最终得到一棵回归树。

  5. 决策树不需要归一化

  因为数值缩放不影响分裂点位置，对树模型的结构不造成影响。 按照特征值进行排序的，排序的顺序不变，那么所属的分支以及分裂点就不会有不同。而且，树模型是不能进行梯度下降的，因为构建树模型（回归树）寻找最优点时是通过寻找最优分裂点完成的，因此树模型是阶跃的，阶跃点是不可导的，并且求导没意义，也就不需要归一化。
  对于线性模型，特征值差别很大时，运用梯度下降的时候，损失等高线是椭圆形，需要进行多次迭代才能到达最优点。 但是如果进行了归一化，那么等高线就是圆形的，促使SGD往原点迭代，从而导致需要的迭代次数较少。

  Q&A

  1. 决策树中有哪些参数？

• （特征选择标准）criterion：’gini’(default)、’entropy’

• （划分特征）splitter：’best’(default)、’random’，选择所有特征进行树生成或随机选择部分特征
• （target权重）class_weight：None(default)、’balanced’，解决训练样本类别不平衡问题

• （剪枝）：防止过拟合：

        1. **max_depth**：最大深度
        1. **min_samples_leaf**：节点切分后每个子节点数据量的阈值，若都低于该值，则不划分；或选择能满足该阈值的切分特征
        1. min_impurity_split：切分点最小不纯度，若节点不纯度小于该值，则该点不再划分
        1. min_impurity_split：切分增益阈值，若节点切分增益均小于该值，则该点不划分
        1. min_samples_split：节点再划分所需最小样本量，若少于该值，则该点不再划分

  2. 决策树如何防止过拟合？

  通过剪枝防止过拟合：

     1. 预剪枝：生成树过程中剪枝，效率高，适合解决大规模问题；有欠拟合风险（譬如某个划分导致测试集准确率降低，但在之后的划分中准确率可能显著上升，若预剪枝则破坏该效果）
     1. 后剪枝：可以得到泛化能力更强的决策树；时间开销大。

  3. 逻辑回归和决策树区别？

1. 逻辑回归是线性模型，决策树是非线性模型。
2. 逻辑回归可以提供每个观察点的概率，而决策树只返回结果。
3. 逻辑回归模型不能处理缺失值，决策树模型可以。（先忽略缺失样本进行划分，再分别分类到各个类，取最好的划分结果）
4. 逻辑回归侧重于数据的整体结构（每次考虑样本的所有特征），决策树侧重于数据的局部结构（每次只考虑一个特征对label的影响）。故决策树更容易过拟合，要通过剪枝避免过拟合。