阅读之前看这里👉：博主是正在学习数据分析的一员，博客记录的是在学习过程中一些总结，也希望和大家一起进步，在记录之时，未免存在很多疏漏和不全，如有问题，还请私聊博主指正。
博客地址：天阑之蓝的博客，学习过程中不免有困难和迷茫，希望大家都能在这学习的过程中肯定自己，超越自己，最终创造自己。

1.决策树原理

1.1原理

决策树呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的概率分布。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型；预测时，对新的数据，利用决策模型进行分类。

定义：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。

自己的理解：决策树算法，无论是哪种，其目的都是为了让模型的不确定性降低的越快越好，基于其评价指标的不同，主要是ID3算法，C4.5算法和CART算法，其中ID3算法的评价指标是信息增益，C4.5算法的评价指标是信息增益率，CART算法的评价指标是基尼系数。

1.2如何学习一棵决策树？

决策树的学习本质上就是从训练数据集中归纳出一组分类规则，使它与训练数据矛盾较小的同时具有较强的泛华能力。从另一个角度看，学习也是基于训练数据集估计条件概率模型。

决策树的损失函数通常是正则化的极大似然函数，学习的策略是以损失函数为目标函数的最小化（说完了策略，该说算法了）。

由于这个最小化问题是一个NP完全问题，现实中，我们通常采用启发式算法（这里，面试官可能会问什么是启发式算法，要有准备，SMO算法就是启发式算法）来近似求解这一最优化问题，得到的决策树是次最优的。

该启发式算法可分为三步：

• 特征选择
• 模型生成
• 决策树的剪枝

1.3能具体谈谈这三个步骤吗？

从总体上看，这三个步骤就是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程，这个过程就是划分特征空间，构建决策树的过程。

1.4如何选择最优特征呢？

简单讲，根据特征的分类能力去选择最优特征，特征分类能力的衡量通常采用信息增益或信息增益比。

1.5递归的终止条件是什么呢？

通常有两个终止条件，一是所有训练数据子集被基本正确分类。二是没有合适的特征可选，即可用特征为0，或者可用特征的信息增益或信息增益比都很小了。

2.谈谈对信息增益和信息增益率的理解？

特征选择的准则就是信息增益和信息增益比。

首先给出信息熵和条件熵的定义：

从概率统计的角度看，信息熵是对随机变量不确定性的度量，也可以说是对随机变量的概率分布的一个衡量。

条件熵，即为随机事件x发生的条件下y事件的信息熵的期望，即表示在已知随机变量下x的条件下随机变量y的不确定性的期望，强调的是随机事件x对随机事件y的不确定性的影响。

当熵和条件熵的概率由数据估计(极大似然估计)得到时，所对应的熵与条件熵分别成为经验熵和经验条件熵。

信息增益(互信息)：表示得知特征x的信息而使得类y的信息的不确定性减少的程度。定义为随机变量y的信息熵减去考虑随机变量x的y的条件熵，衡量在考虑随机变量x的情况下y的不确定性减少的程度：

特征$A$对训练数据集$D$的信息增益为$g(D,A)$，定义为集合$D$的经验熵$H(D)$与特征$A$给定条件下$D$的经验条件熵$H(D|A)$之差，即
$$g(D,A)=H(D)-H(D|A)$$

根据信息增益准则的特征选择方法是：对训练数据集(或子集)D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
ID3算法在每一次对决策树进行分叉选取最优特征时，会选取信息增益最高的特征来作为分裂特征。

信息增益的缺陷：以信息增益作为划分训练数据集的特征，信息增益准则对那些属性的取值比较多的属性有所偏好，也就是说，采用信息增益作为判定方法，会倾向于去选择属性取值比较多的属性。

• 信息增益主要用于帮助选择某个能够最大程度减少目标变量不确定性的特征（随机变量），考虑极端情况，当选择唯一id这种随机变量时，会导致条件熵为0，信息增益最大，但这种情况没有任何泛化意义，所以需要对类似的情况进行惩罚，从而帮助我们做出更合理的选择。

使用信息增益比可以对此问题进行校正：

特征$A$对训练数据集$D$的信息增益比为$g_R(D,A)$，定义信息增益为$g(D,A)$与训练数据集$D$关于特征A的熵$H_A(D)$之比，即
$$g_R(D,A)=g(D,A)/H_A(D)$$
其中$H_A(D)=-{\sum }_{i=1}^n\frac{|D_i|}{|D|}lo{g}_2\frac{|D_i|}{|D|}$，n是特征A取值的个数

3.决策树出现过拟合的原因及其解决办法？

对训练数据预测效果很好，但是测试数据预测效果较差的现象称为过拟合。
原因：

1. 在决策树构建的过程中，对决策树的生长没有进行合理的限制（剪枝）；
2. 样本中有一些噪声数据，没有对噪声数据进行有效的剔除；
3. 在构建决策树过程中使用了较多的输出变量，变量较多也容易产生过拟合。

解决办法

1. 选择合理的参数进行剪枝，可以分为预剪枝和后剪枝，我们一般采用后剪枝的方法；
2. 利用K−folds交叉验证，将训练集分为K份，然后进行K次交叉验证，每次使用K−1份作为训练样本数据集，另外一份作为测试集；
3. 减少特征，计算每一个特征和响应变量的相关性，常见得为皮尔逊相关系数，将相关性较小的变量剔除；当然还有一些其他的方法来进行特征筛选，比如基于决策树的特征筛选，通过正则化的方式来进行特征选取等（决策的正则化，例如，L1和L2正则，具体是对谁的正则呢？怎样正则的呢？）。面试官顺便会问L1和L2，一定要搞明白

4.简单解释一下预剪枝和后剪枝，以及剪枝过程中可以参考的参数有哪些？

剪枝：
由于决策树生成算法递归产生决策树，虽然对训练数据分类很准确，但是对未知的测试数据分类没那么准确，容易出现过拟合。解决方法之一在上述问题中提到了就是进行剪枝，即将已生成的树进行简化的过程，具体的就是在已生成的树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化树的类型。（方法有优化损失函数等）判断方法，测试集上的准确率。

• 预剪枝：在决策树生成初期就已经设置了决策树的参数，决策树构建过程中，满足参数条件就提前停止决策树的生成。
  优点：降低了过拟合的风险，显著减少了决策树的训练时间开销和测试时间开销。但是，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分有可能导致性能显著提高。
  缺点：如何准确估计何时停止树的生长，针对不同问题会有很大的区别，另外具有局限性，但可能导致欠拟合。
• 后剪枝：后剪枝是一种全局的优化方法，它是在决策树完全建立之后再返回去对决策树进行剪枝。
  优点：欠拟合的风险小，泛化能力更强，但时间开销更大。
• 参数：树的高度、叶子节点的数目、最大叶子节点数、限制不纯度。

5.决策树的优缺点

优点：

1. 计算简单、速度快；
2. 可解释性强；
3. 比较适合处理有缺失属性的样本。

缺点：

1. 容易发生过拟合（随机森林可以很大程度上减少过拟合）；
2. 忽略了数据之间的相关性；
3. 对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征（只要是使用了信息增益，都有这个缺点，如RF）。对应的案例如下：有这么一个场景，在一个样本集中，其中有100个样本属于A，9900个样本属于B，用决策树算法实现对AB样本进行区分的时候，会发生欠拟合的现象。因为在这个样本集中，AB样本属于严重失衡状态，在建立决策树算法的过程中，模型会更多的偏倚到B样本的性质，对A样本的性质训练较差，不能很好的反映样本集的特征。（待解释！！！）。

6.决策树是如何处理缺失值的？

在决策树中处理含有缺失值的样本的时候，需要解决两个问题：

• 如何在属性值缺失的情况下进行划分属性的选择？
  可利用没有缺失的样本子集来判断属性的优劣。
• 给定划分属性，若样本在该属性上的值是缺失的，那么该如何对这个样本进行划分？（即到底把这个样本划分到哪个结点里？）
  让同一个样本以不同的概率划入到不同的子结点当中去。

测试样本在该属性值上有缺失值：
C4.5中采用的方法是：测试样本在该属性值上有缺失值，那么就同时探查（计算）所有分支，然后算每个类别的概率，取概率最大的类别赋值给该样本。

7.决策树与逻辑回归的区别？

1. 对于拥有缺失值的数据，决策树可以应对，而逻辑回归需要挖掘人员预先对缺失数据进行处理；
2. 逻辑回归对数据整体结构的分析优于决策树，而决策树对局部结构的分析优于逻辑回归；（决策树由于采用分割的方法，所以能够深入数据内部，但同时失去了对全局的把握。一个分层一旦形成，它和别的层面或节点的关系就被切断了，以后的挖掘只能在局部中进行。同时由于切分，样本数量不断萎缩，所以无法支持对多变量的同时检验。而逻辑回归，始终着眼整个数据的拟合，所以对全局把握较好。但无法兼顾局部数据，或者说缺乏探查局部结构的内在机制。）
3. 逻辑回归擅长分析线性关系，而决策树对线性关系的把握较差。线性关系在实践中有很多优点：简洁，易理解，可以在一定程度上防止对数据的过度拟合。（我自己对线性的理解：1，逻辑回归应用的是样本数据线性可分的场景，输出结果是概率，即，输出结果和样本数据之间不存在直接的线性关系；2，线性回归应用的是样本数据和输出结果之间存在线性关系的场景，即，自变量和因变量之间存在线性关系。）
4. 逻辑回归对极值比较敏感，容易受极端值的影响，而决策树在这方面表现较好。
5. 应用上的区别：决策树的结果和逻辑回归相比略显粗糙。逻辑回归原则上可以提供数据中每个观察点的概率，而决策树只能把挖掘对象分为有限的概率组群。比如决策树确定17个节点，全部数据就只能有17个概率，在应用上受到一定限制。就操作来说，决策树比较容易上手，需要的数据预处理较少，而逻辑回归则要去一定的训练和技巧。
6. 执行速度上：当数据量很大的时候，逻辑回归的执行速度非常慢，而决策树的运行速度明显快于逻辑回归。
7. 从本质来考虑，决策树算法假设每一次决策边界都是和特征相互平行或垂直的，因此会将特征空间划分为矩形，因而决策树会产生复杂的方程式，这样会造成过拟合现象；逻辑回归只是一条平滑的边界曲线，不容易出现过拟合现象。

8.决策树的两种算法(ID3算法、C4.5算法)

• ID3算法
  ID3算法的核心是在决策树各个结点上应用信息增益准则选取特征，递归地构建决策树。
  具体地方法是：从根结点开始，对结点计算所有可能地特征地信息增益，选择增益最大地特征作为结点地特征，由该特征地不同取值建立子节点；再对子节点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止。最后得到一棵决策树。ID3算法相对于用极大似然估计法进行概率模型的选择。
• 具体方法
  对于离散变量，计算每一个变量的信息增益，选择信息增益最大的属性来作为结点的分裂属性；对于连续变量，首先将变量的值进行升序排列，每对相邻值的中点作为可能的分离点，对于每一个划分，选择具有最小期望信息要求的点作为分裂点，来进行后续的决策数的分裂。

ID3算法只有树的生成，所以该算法容易产生过拟合。

• C4.5算法与ID3算法相似，在生成过程中，用信息增益比来选择特征。

Q1:为什么连续特征的最佳分裂点选取使用信息增益而非信息增益率？

因为同一个特征下，最终的结果确定是二分，这种相对的比较，也就不存在信息增益自身的缺陷（倾向于选择情况更多的特征，现在情况只有两种）

Q2:为什么最佳特征的选择先考虑信息增益再考虑信息增益率？

首先，信息增益倾向于选择可取值数量较多的变量，信息增益率倾向于选择可取值数较少的变量（有点儿矫枉过正），所以采用启发式算法，先选取信息增益高于平均值的特征，再选取信息增益率最大的特征作为当前划分依据

9.CART算法的理解

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支为是，右分支为否。这样的决策树递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是输出的条件概率分布。

CART算法由以下两部分组成：
(1)决策树生成：基于训练集生成决策树，生成的决策树要尽量大；
(2)决策树剪枝：用验证集对已生成的树进行剪枝并选择最优树，这时将损失函数最小作为剪枝的标准。

分类树的生成：
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
1）对所有特征的所有可能切分点进行基尼指数计算
2）选择基尼指数最小的特征+切分点组合

CART的剪枝，总体而言就两个过程
1）根据生成的完整决策树，计算每个内部结点对应的损失函数增加量，然后砍去损失函数增加最多的结点，生成新树
2）对新树递归调用第一步，生成更多的新树，构成树集合
3）通过验证集选择最佳的决策树

10.三种方法之间的区别

1. ID3算法采用信息增益的缺陷，所以引入信息增益比，答案见上问题2。
2. 样本处理的角度，ID3只能处理离散型变量，而C4.5和CART都可以处理连续型变量。
3. 应用的角度，ID3和C4.5只能分类，而CART还可以用于回归任务。
4. ID3对样本特征缺失值较为敏感，而C4.5和CART可以对缺失值进行不同的处理。

参考博客和书籍：

决策树常见的面试点整理
李航《统计学习方法》
第2版 周志华《机器学习》
《百面机器学习》

—————————————————————————————————————————————————
博主码字不易，大家关注点个赞转发再走呗 ，您的三连是激发我创作的源动力^ - ^