1. 基本原理

1.1 原理

决策树算法是一种逼近离散函数值的方法。它是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。

决策树将算法组织成一颗树的形式。其实这就是将平时所说的if-then语句构建成了树的形式。决策树主要包括三个部分：内部节点、叶节点、边。内部节点是划分的特征，边代表划分的条件，叶节点表示类别。

构建决策树 就是一个递归的选择内部节点，计算划分条件的边，最后到达叶子节点的过程。 决策树在本质上是一组嵌套的if-else判定规则，从数学上看是分段常数函数，对应于用平行于坐标轴的平面对空间的划分。判定规则是人类处理很多问题时的常用方法，这些规则是我们通过经验总结出来的，而决策树的这些规则是通过训练样本自动学习得到的。

训练时，通过最大化Gini或者其他指标来寻找最佳分裂。决策树可以输特征向量每个分量的重要性。

决策树是一种判别模型，既支持分类问题，也支持回归问题，是一种非线性模型（分段线性函数不是线性的）。它天然的支持多分类问题。

1.2 决策树的构造

决策树的构造是一个递归的过程，有三种情形会导致递归返回：(1) 当前结点包含的样本全属于同一类别，这时直接将该节点标记为叶节点，并设为相应的类别；(2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分，这时将该节点标记为叶节点，并将其类别设为该节点所含样本最多的类别；(3) 当前结点包含的样本集合为空，不能划分，这时也将该节点标记为叶节点，并将其类别设为父节点中所含样本最多的类别。

决策树学习的关键在于如何选择划分属性，不同的划分属性得出不同的分支结构，从而影响整颗决策树的性能。属性划分的目标是让各个划分出来的子节点尽可能地“纯”，即属于同一类别。因此下面便是介绍量化纯度的具体方法，决策树最常用的算法有三种：ID3，C4.5和CART。

1.3 量化纯度方法

1.3.1 ID3算法

ID3算法使用信息增益为准则来选择划分属性，“信息熵”(information entropy)是度量样本结合纯度的常用指标，假定当前样本集合D中第k类样本所占比例为，则样本集合的信息熵定义为

只有一个类别时，熵为0， 熵越大表示越混乱

假定通过属性划分样本集D，产生了V个分支节点，v表示其中第v个分支节点，易知：分支节点包含的样本数越多，表示该分支节点的影响力越大。故可以计算出划分后相比原始数据集D获得的“信息增益”（information gain）。

4.png

信息增益越大，表示使用该属性划分样本集D的效果越好，因此ID3算法在递归过程中，每次选择最大信息增益的属性作为当前的划分属性。

1.3.2 C4.5算法

ID3算法存在一个问题，就是偏向于取值数目较多的属性，例如：如果存在一个唯一标识，这样样本集D将会被划分为|D|个分支，每个分支只有一个样本，这样划分后的信息熵为零，十分纯净，但是对分类毫无用处。因此C4.5算法使用了“增益率”（gain ratio）来选择划分属性，来避免这个问题带来的困扰。首先使用ID3算法计算出信息增益高于平均水平的候选属性，接着C4.5计算这些候选属性的增益率，增益率定义为

5.png

1.3.3 CART算法

CART决策树使用“基尼指数”（Gini index）来选择划分属性，基尼指数反映的是从样本集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini(D)越小越好，基尼指数定义如下：

6.png

进而，使用属性α划分后的基尼指数为：

7.png

1.4 剪枝处理

从决策树的构造流程中我们可以直观地看出：不管怎么样的训练集，决策树总是能很好地将各个类别分离开来，这时就会遇到之前提到过的问题：过拟合（overfitting），即太依赖于训练样本。剪枝（pruning）则是决策树算法对付过拟合的主要手段：

• 预剪枝（prepruning）：在构造的过程中先评估，再考虑是否分支。
• 后剪枝（post-pruning）：在构造好一颗完整的决策树后，自底向上，评估分支的必要性。

评估指的是性能度量，即决策树的泛化性能。之前提到：可以使用测试集作为学习器泛化性能的近似，因此可以将数据集划分为训练集和测试集。预剪枝表示在构造数的过程中，对一个节点考虑是否分支时，首先计算决策树不分支时在测试集上的性能，再计算分支之后的性能，若分支对性能没有提升，则选择不分支（即剪枝）。后剪枝则表示在构造好一颗完整的决策树后，从最下面的节点开始，考虑该节点分支对模型的性能是否有提升，若无则剪枝，即将该节点标记为叶子节点，类别标记为其包含样本最多的类别。

预剪枝处理使得决策树的很多分支被剪掉，因此大大降低了训练时间开销，同时降低了过拟合的风险，但另一方面由于剪枝同时剪掉了当前节点后续子节点的分支，因此预剪枝“贪心”的本质阻止了分支的展开，在一定程度上带来了欠拟合的风险。而后剪枝则通常保留了更多的分支，因此采用后剪枝策略的决策树性能往往优于预剪枝，但其自底向上遍历了所有节点，并计算性能，训练时间开销相比预剪枝大大提升。

1.4 连续值与缺失值的处理

1.4.1 连续值

对于连续值的属性，若每个取值作为一个分支则显得不可行，因此需要进行离散化处理，常用的方法为二分法，基本思想为：给定样本集D与连续属性α，二分法试图找到一个划分点t将样本集D在属性α上分为≤t与＞t。

• 首先将α的所有取值按升序排列，所有相邻属性的均值作为候选划分点（n-1个，n为α所有的取值数目）。
• 计算每一个划分点划分集合D（即划分为两个分支）后的信息增益。

• 选择最大信息增益的划分点作为最优划分点。

  
  
  11.png

1.4.2 缺失值

现实中常会遇到不完整的样本，即某些属性值缺失。有时若简单采取剔除，则会造成大量的信息浪费，因此在属性值缺失的情况下需要解决两个问题：（1）如何选择划分属性。（2）给定划分属性，若某样本在该属性上缺失值，如何划分到具体的分支上。假定为样本集中的每一个样本都赋予一个权重，根节点中的权重初始化为1，则定义：

12.png

对于（1）：通过在样本集D中选取在属性α上没有缺失值的样本子集，计算在该样本子集上的信息增益，最终的信息增益等于该样本子集划分后信息增益乘以样本子集占样本集的比重。即：

13.png

对于（2）：若该样本子集在属性α上的值缺失，则将该样本以不同的权重（即每个分支所含样本比例）划入到所有分支节点中。该样本在分支节点中的权重变为：

14.png

2. 面试题

（1） 简单介绍决策树算法
上面基本原理

（2）决策树和条件概率分布的关系？
决策树可以表示成给定条件下类的条件概率分布。
决策树中的每一条路径对应的都是划分的一个条件概率分布. 每一个叶子节点都是通过多个条件之后的划分空间，在叶子节点中计算每个类的条件概率，必然会倾向于某一个类，即这个类的概率最大。

（3）ID3算法—>C4.5算法—> CART算法

• 

  • 算法没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
  • 算法采用信息增益大的特征优先建立决策树的节点，偏向于取值比较多的特征
  • 算法对于缺失值的情况没有做考虑
  • 算法没有考虑过拟合的问题

• 在算法上面的改进

  • 连续的特征离散化
  • 使用信息增益比
  • 通过剪枝算法解决过拟合

• 的不足：

  • 生成的是多叉树
  • 只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
  • 由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算

• 算法

  • 可以做回归，也可以做分类，
  • 使用基尼系数来代替信息增益比
  • 分类树离散值的处理问题，采用的思路是不停的二分离散特征。

（4） 信息增益比相对信息增益有什么好处？

• 使用信息增益时：模型偏向于选择取值较多的特征
• 使用信息增益比时：对取值多的特征加上的惩罚，对这个问题进行了校正。

（5）决策树如何防止过拟合？

• 对于决策树进行约束：根据情况来选择或组合

  • 设置每个叶子节点的最小样本数，可以避免某个特征类别只适用于极少数的样本。

  • 设置每个节点的最小样本数，从根节点开始避免过度拟合。

  • 设置树的最大深度，避免无限往下划分。

  • 设置叶子节点的最大数量，避免出现无限多次划分类别。

  • 设置评估分割数据是的最大特征数量，避免每次都考虑所有特征为求“最佳”，而采取随机选择的方式避免过度拟合。

• 预剪枝(提前停止)：控制深度、当前的节点数、分裂对测试集的准确度提升大小

  • 限制树的高度，可以利用交叉验证选择
  • 利用分类指标，如果下一次切分没有降低误差，则停止切分
  • 限制树的节点个数，比如某个节点小于100个样本，停止对该节点切分

• 后剪枝(自底而上)：生成决策树、交叉验证剪枝：子树删除，节点代替子树、测试集准确率判断决定剪枝

  • 在决策树构建完成之后，根据加上正则项的结构风险最小化自下向上进行的剪枝操作. 剪枝的目的就是防止过拟合，是模型在测试数据上变现良好，更加鲁棒。

（6）决策树如何剪枝？

（7）决策树先剪枝还是后剪枝好？

（8）决策树的缺失值是怎么处理的
见基本原理

（9）决策树能否有非数值型变量？
当然可以，比如天气分为下雨和不下雨

（10）决策树的目标函数


其中代表叶节点个数

表示具体某个叶节点的样本数

表示叶节点上的经验熵

为正则项， 为参数

(11) 决策树怎么处理连续性特征？
因为连续特征的可取值数目不再有限，因此不能像前面处理离散特征枚举离散特征取值来对结点进行划分。因此需要连续特征离散化，常用的离散化策略是二分法，这个技术也是中采用的策略。下面来具体介绍下，如何采用二分法对连续特征离散化：

• 训练集D，连续特征，其中A有n个取值

• 对的取值进行从小到大排序得到：

• 寻找划分点，将D分为子集与

  • ：特征上取值不大于的样本
  • ：特征上取值大于的样本

• 对相邻的特征取值与，t再区间中取值所产生的划分结果相同，因此对于连续特征,包含有个元素的后选划分点集合

• 把区间的中位点作为候选划分点

• 按照处理离散值那样来选择最优的划分点,使用公式：
  
  其中是样本集基于划分点二分之后的信息增益。划分点时候选择使用最大的划分点。

(12) 决策树对离散值的处理
思想和相同，都是将连续的特征离散化。唯一区别在选择划分点时，C4.5是信息增益比，CART是基尼系数。

CART采用的是不停的二分。会考虑把特征分成和、和、和三种情况，找到基尼系数最小的组合，比如和，然后建立二叉树节点，一个节点是对应的样本，另一个节点是对应的样本。由于这次没有把特征的取值完全分开，后面还有机会对子节点继续选择特征划分和。这和不同，在或的一颗子树中，离散特征只会参与一次节点的建立。

（13）如果特征很多，决策树中最后没有用到的特征一定是无用吗？
不是无用的，从两个角度考虑：

• 特征替代性，如果可以已经使用的特征和特征可以提点特征，特征可能就没有被使用，但是如果把特征单独拿出来进行训练，依然有效

• 决策树的每一条路径就是计算条件概率的条件，前面的条件如果包含了后面的条件，只是这个条件在这棵树中是无用的，如果把这个条件拿出来也是可以帮助分析数据.

（14）决策树的优缺点：

• 优点:

  • 简单直观，生成的决策树很直观。
  • 基本不需要预处理，不需要提前归一化，处理缺失值。
  • 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
  • 可以处理多维度输出的分类问题。
  • 相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
  • 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
  • 对于异常点的容错能力好，健壮性高。
  • 用白盒模型，可清洗观察每个步骤，对大数据量的处理性能较好，更贴近人类思维。

• 缺点:

  • 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
  • 决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
  • 寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
  • 有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
  • 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。

（15）树形结构为什么不需要归一化

• 计算信息增益前，按照特征值进行排序，排序的顺序不变，那么所属的分支以及分裂点就不会有不同。

• 数值缩放不影响分裂点位置，对树模型的结构不造成影响。