决策树

1 基础知识

1.1 熵

在物理学中表示一个系统的混乱程度，在信息论里面表示随机变量的不确定性的度量，熵越大，不确定性越大。

$$\begin{align*} H(p) = -\sum\limits_{i=1}^{n}p_{i}log ( p_{i} ) \end{align*}$$

显然$0 \le H(p) \le log(n)$，当且仅当$p_{1}=p_{2}=\cdots=p_{n}$时，$H(p)=log(n)$。

1.1.1 条件熵

在给定随机变量$X$的情况下，随机变量$Y$​的不确定性

$$\begin{align*} H(Y \vert X) = \sum\limits_{i=1}^{n}P(X=x_{i})H(Y \vert X=x_{i}), i=1,2,\cdots,n \end{align*}$$

1.1.2 联合熵

它是联合概率分布$P(X,Y)$的经验熵

$$\begin{align*} H(X,Y)= -\sum\limits_{i,j}P(X=x_{i},Y=y_{j})log(P(X=x_{i},Y=y_{j})) \end{align*}$$

1.1.3 交叉熵

记数据集的真实分布为 $p$，估计分布为 $q$，若用 $q$来拟合 $p$，则交叉熵损失为

$$\begin{align*} H(p,q)=-\sum\limits_{i=1}^{n}p_{i}log(q_{i}) \end{align*}$$

1.1.4 KL散度

用于衡量两个分布 $p, q$ 之间的差异程度

$$\begin{align*} D_{KL}(p \vert q) & = \sum\limits_{i=1}^{n} p_{i}log(\frac{p_{i}}{q_{i}}) & \\ & = \sum\limits_{i=1}^{n} p_{i}log(p_{i}) - \sum\limits_{i=1}^{n}p_{i}log(q_{i}) &\\ & = -H(p) + H(p,q) & \end{align*}$$

显然 $KL$ 散度是交叉熵和经验熵的差值。

1.2 信息增益

特征 $A$ 对训练集 $D$ 的的信息增益 $g(D,A)$ 定义为集合 $D$ 的经验熵 $H(D)$与集合 $D$ 在给定特征 $A$条件下的条件熵 $H(D \vert A)$之差

$$\begin{align*} g(D,A)=H(D)-H(D \vert A) \end{align*}$$

一般的，熵 $H(Y)$ 与条件熵 $H(Y \vert X)$之差称为互信息，在决策树里，信息增益等价于训练数据集中类别和特征的互信息。

1.3 信息增益率

特征 $A$ 对训练数据集 $D$ 的信息增益率 $g_{R}(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 $D$ 关于特征 $A$ 的值的熵 $H_{A}(D)$ 之比，即

$$\begin{align*} g_{R}(D,A)=\frac{g(D,A)}{H_{A}(D)} \end{align*}$$

其中

$$\begin{align*} H_{A}(D) = -\sum\limits_{i=1}^{n} \frac{\vert D_{i} \vert}{\vert D \vert} log_{2} \frac{\vert D_{i} \vert}{\vert D \vert} \end{align*}$$

$n$ 为特征 $A$ 的取值个数。

1.4 Gini 指数

对于一个 $K$ 分类问题，样本的概率分布为 $p_{k}$，则该分布的基尼指数为

$$\begin{align*} Gini(p) & =\sum\limits_{i=1}^{n} p_{k} (1-p_{k}) & \\ & =1 - \sum\limits_{i=1}^{n} p_{k}^{2} & \end{align*}$$

基尼指数 $Gini(D)$ 代表集合 $D$ 的不确定性，基尼指数$Gini(D,A)$ 表示经 $A = a$ 分割后集合 $D$ 的不确定性，基尼指数之越大，样本集合的不确定性也越大。

2 决策树

决策树是一个树状结构算法，它是一套 if else 规则，常用于解决分类问题。对于一个新样本，在经过层层 if else 规则之后，最终落在哪个叶子节点上，它就属于该节点所在的类别。决策树的由特征选择、树的生成、树的剪枝三步组成。常见的决策树算法有 ID3，C4.5，CART。

2.1 ID3 算法

$ID3$ 算法的核心是在决策树各个节点上用信息增益准则选择特征，递归地构建决策树。具体地，从根结点开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该结点的不同取值建立子节点，再对子结点递归调用上述方法，构建决策树，直到所有特征的信息增益均很小，或没有特征可以选择为止，最后得到决策树。$ID3$相当于是用极大似然法进行概率模型的选择。

注意：
(1) $ID3$​只能处理离散特征;
(2) 特征在不同层级之间不能反复使用;
(3) 使用信息增益来做特征选择，容易导致偏向于选择属性值多的特征，从直观上也能理解，一个特征属性值越多，包含的信息也就越多，用它来做分裂结点，数据集的不确定性降低地更快。

2.2 C4.5 算法

相较于 $ID3$ 算法，$C4.5$ 只是在选择分裂的时候用信息增益率来做特征选择。

注意：
(1) 相较于 $ID3$，$C4.5$ 既能处理离散特征也能处理连续特征;
(2) 使用信息增益率做特征选择，避免了偏向选择属性值较多的特征的问题;
(3) $C4.5$ 在处理连续型特征时，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续型特征转换为多个取值区间上的离散型特征;
(4) $C4.5$ 一般来说也是多叉树。

2.3 CART算法

$CART$ 全称是分类与回归树(Classify and Regression Tree)，它既可以用于分类也可以用于回归，$CART$ 算法中假设树是二叉树，内部节点特征取值为 “是” 和 “否”，左边是取值为 “是” 的分支，右边是取值为 “否” 的分支。

$CART$ 算法由两步组成：
(1) 决策树的生成：基于训练数据生成决策树，生成的决策树要尽量大;
(2) 决策树的剪枝：用验证数据集对已生成的决策树进行剪枝并选择最优子树，用损失函数最小作为选择标准。

注意：
(1) $CART$ 既可以做分类也可以做回归;
(2)不同于 $ID3$、$C4.5$ 可以是多叉树，$CART$ 只能是二叉树;
(3) $ID3$ 和 $C4.5$ 的特征是不能在不同层级之间复用的，而 $CART$ 可以;
(4) $C4.5$ 通过剪枝来平衡模型的准确性和泛化能力，而 $CART$ 直接利用全部数据发现所有可能的树进行对比.

2.4 决策树的剪枝

决策树生成算法递归地生成决策树，直到满足停止条件。这种情况下，对于训练集拟合效果较好，但在测试集上的效果往往不理想，即容易产生过拟。因此要对决策树进行剪枝，简化树状结构，提高泛化能力。

剪枝分为预剪枝和后剪枝。
预剪枝：在树的构建生长阶段进行剪枝，如果结点满足信息 $Gini$ 指数小于阈值或者该结点的样本数量少于特定值，则不再对该结点继续细分。
后剪枝：在树完全生长后再从叶子结点逐个往上剪枝，利用测试集数据验证剪枝前后，树的损失函数是否有变化。如果剪枝后损失函数减小，说明剪枝提高了模型泛化能力，否则不能剪枝。

3 面试题

3.1 简述决策树原理

决策树是一类常见的机器学习方法，它是基于树的结构进行决策的。每次做决策时选择最优划分属性，一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一个类别，即节点的“纯度”(purity)越来越高。

决策树学习算法包含特征选择、决策树的生成与剪枝过程。决策树的学习算法通常是递归地选择最优特征，并用最优特征对数据集进行分割。开始时，选择最优特征构建根节点，该特征有几种取值就分割为几个子集，每个子集分别递归调用此方法，返回节点，返回的节点就是上一层的子节点。直到达到终止条件（预剪枝条件等）。

关于熵和信息增益等的介绍见第1节。

常用的决策树算法有 $ID3$，$C4.5$ 和 $CART$，其中 $ID3$ 以信息增益为准则来选择划分属性，$C4.5$ 使用信息增益率来进行属性的选择，$CART$ 使用基尼系数来选择划分属性。

3.2 简述决策树的构建过程

数据预处理，根据信息增益或信息增益率准则选择分裂结点，树的剪枝。

3.3 简述信息增益率的优缺点

优点：$ID3$ 使用信息增益准则对决策树进行划分，其偏向于选择分支较多的特征分裂，因为具有较多属性值的特征分裂后其信息增益通常较大。此时就会有较大的概率出现每个分支节点只包含一个样本的情况，因为分支节点的纯度达到最大，但显然这种决策树的泛化能力较差，对新样本的预测能力较弱。信息增益率是对信息增益的一种改进，对属性值多的样本做一下惩罚，避免分类的时候偏向于优先划分属性值多的特征。

缺点：信息增益率偏向取值较少的特征，当特征取值较少时，信息增益率的计算公式中分母的值较小，因而信息增益率比较大。所以它偏向取值较少的特征。

我们在使用信息增益率时，通常也并不是直接使用。而是先在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

3.4 $C4.5$ 对 $ID3$ 做了哪些改进

ID3 算法是采用信息增益作为评价标准进行分支的决策树算法。

ID3的缺点：
(1) 它对取值较多的属性非常敏感，例如，数据集中的某个属性取值是不重复的，如果我们用这个属性来划分数据集，那么它的信息增益会很大，但这并不是我们想要的结果，因为它的泛化能力很差。
(2) ID3算法不能处理连续型属性。
(3) ID3算法不能处理属性具有缺失值的样本。
(4) ID3算法会生成很深的树，容易过拟合。

C4.5算法主要对ID3作出了以下方面的改进：
(1) 用信息增益率来选择属性，克服了用信息增益来选择属性时偏向选择值多的属性的不足。
(2) 可以处理连续数值型属性。
(3) 使用PEP(Pessimistic Error Pruning)的后剪枝策略。
(4) 能够处理缺失值。
$\qquad$处理的方式通常有三种：
$\qquad$① 赋上该属性最常见的值或者取均值；
$\qquad$② 丢弃有缺失值的样本；
$\qquad$③ 根据节点的样例上该属性值出现的情况赋一个概率，比如该节点上有10个样本，其中属性A的取值有6个为“高”，4个为“低”。那么对该节点上缺失的属性A，以0.6的概率设为“高”，0.4的概率设为“低”。

C4.5的缺点：
(1) 算法低效，在构造树的过程中，需要对数据集进行多次的顺序扫描和排序（主要在于对连续特征的处理上）。
(2) 内存受限，适合于能够驻留于内存的数据集，当训练集大到无法在内存中容纳时，程序无法运行。
(3) 无论是 ID3 还是 C4.5 最好在小数据集上使用，决策树分类一般只适用于小数据集。当属性取值很多时最好选择 C4.5 算法，而ID3 的效果会非常差。

3.5 $C4.5$ 是如何处理连续数值型属性的？

C4.5 既可以处理离散型特征，也可以处理连续型特征。对于连续分布的特征，其处理方法是：先把连续特征转换为离散特征再进行处理。虽然本质上特征的取值是连续的，但对于有限的采样数据它是离散的，如果有N个样本，那么我们就有N-1种离散化的方法(连续属性的离散化通常是分成两类，即将小于等于某一个分割点的样本分为一类，大于某一个分割点的样本分为一类)。具体分割点的选择依赖于信息增益，选择具有最大信息增益的分割点。另外，在分割之前，需要对连续属性进行排序（升序），这样可以大大减少运算量。经证明，在决定连续特征的分界点时采用信息增益这个指标，而选择属性的时候才使用信息增益率这个指标能选择出最佳分类特征。

具体步骤如下：
step1: 对特征的取值进行升序排序。
step2: 以两个取值之间的中点作为可能的分裂点，将数据集分成两部分，计算每个可能的分裂点的信息增益。优化算法就是只计算分类属性发生改变(对于升序排序的特征取值而言，对每一个分裂点都进行计算未免太过耗时，实践证明，取那些夹在相同分类属性之间的分裂点必不会时全局最小)的那些特征取值。
step3: 选择修正后信息增益最大的分裂点作为该特征的最佳分裂点。
step4: 计算最佳分裂点的信息增益率作为特征的信息增益率。

分裂点的信息增益修正方法：
$\qquad$将信息增益减去 $\frac{log_{2}(N-1)}{\vert D \vert}$ 得到修正后的信息增益，其中N是连续特征的取值个数，D是训练数据数目。此修正的原因是：当离散特征与连续特征并存时，C4.5算法倾向于选择连续特征做最佳树分裂点。

3.6 $C4.5$ 与 $CART$ 的区别

(1) $C4.5$ 只能做分类，$CART$ 既可以做分类也可以做回归，分类的时候用 $Gini$ 指数，回归的时候用平方差。
(2) $C4.5$ 可以是多叉树，而 $CART$ 只能是二叉树。
(3) $C4.5$ 的特征在每个层级之间不会复用，$CART$ 的每个特征可以复用。
(4) $C4.5$ 通过剪枝来平衡模型的准确性和泛化能力，而 $CART$ 直接利用全部数据发现所有可能的树进行对比。

3.7为什么要对决策树进行剪枝？

避免决策树过拟合(Overfitting)样本。$ID3、C4.5、CART$ 算法生成的决策树非常详细并且庞大，每个属性都被详细地加以考虑，决策树的树叶节点所覆盖的训练样本都是“纯”的。如果用这样的决策树对训练样本进行分类，其在训练样本上的表现非常好，误差率极低。但由于训练集中的错误数据也会被决策树学习，成为决策树的一部分，因而在测试集上的表现就没有那么好，甚至会很差，这就是所谓的过拟合(Overfitting)问题。Quinlan教授试验，在数据集中，过拟合的决策树的错误率比经过剪枝的决策树的错误率要高。

3.8 决策树的剪枝策略？

预剪枝

树的构造将提前停止，如果
(1) 树到达一定高度；
(2) 节点下包含的样本点数量小于一定数目；
(3) 信息增益小于一定的阈值等等；
(4) 节点下所有样本都属于同一个类别。

后剪枝

后剪枝的剪枝过程是删除一些子树，然后用其叶子节点代替，这个叶子节点所标识的类别通过大多数原则(majority class criterion)确定。所谓大多数原则，是指剪枝过程中，将一些子树删除而用叶节点代替，这个叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识，所标识的类称为majority class。

后剪枝首先通过完全分裂构造完整的决策树，允许过拟合，然后采取一定的策略来进行剪枝，常用的后剪枝策略包括：
(1) 降低错误剪枝 REP(Reduced Error Pruning);
(2) 悲观错误剪枝 PEP(Pessimistic Error Pruning);
(3) 基于错误剪枝 EBP(Error Based Pruning);
(4) 代价-复杂度剪枝 CCP(Cost Complexity Pruning);
(5) 最小错误剪枝 MEP(Minimum Error Pruning)

剪枝的准则：
(1) 使用训练集 (Training Set) 和验证集 (Validation Set) 来评估剪枝方法在修剪结点上的效用;
(2) 使用所有的训练集进行训练，但是用统计测试来估计修剪特定结点是否会改善训练集合外的数据的评估性能，如使用Chi-Square(Quinlan, 1986)测试来进一步扩展结点是否能改善整个分类数据的性能，还是仅仅改善了当前训练集合数据上的性能。
(3) 使用明确的标准来衡量训练样例和决策树的复杂度，当编码长度最小时，停止树增长，如MDL(Minimum Description Length)准则。

Reduced-Error Pruning(REP,错误率降低剪枝)

自底向顶剪枝：该剪枝方法考虑将树上的每个节点作为修剪的候选对象，决定是否修剪这个结点由如下步骤组成
step1：删除以此结点为根的子树;
step2：使其成为叶子结点;
step3：赋予该结点关联的训练数据的最常见分类;
step4：当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该结点。

因为训练集合的过拟合，使得验证集数据能够对其进行修正，反复进行上面的操作，从底向上的处理结点，删除那些能够最大限度的提高验证集的精度的结点，直到进一步修剪有害为止(有害是指修剪会减低验证集的精度)

REP是最简单的后剪枝方法之一，不过在数据量比较少的情况下，REP方法趋于过拟合而较少使用。这是因为训练集中的特性在剪枝过程中被忽略，所以在验证数据集比训练数据集合小的多时，要注意这个问题。

尽管REP有这个缺点，不过REP仍然作为一种基准来评价其它剪枝算法的性能。它对于两阶段决策树学习方法的优点和缺点提供了了一个很好的学习思路。由于验证集合没有参与决策树的创建，所以用REP剪枝后的决策树对于测试样例的偏差要好很多，能够在一定程度上解决过拟合问题。

Pessimistic Error Pruning(PEP, 悲观错误剪枝)

该算法被认为是当前决策树后剪枝算法中精度比较高的算法之一，但是仍存在有缺陷。首先，PEP算法是唯一使用Top-Down剪枝策略，这种策略会导致与预剪枝出现同样的问题，即将该结点的某子节点不需要被剪枝时被剪掉；另外PEP方法会有剪枝失败的情况出现。

虽然PEP方法存在一些局限性，但是在实际应用中表现出了较高的精度。另外，PEP方法不需要分离训练集和验证集，对于数据量比较少的情况比较有利。再者，其剪枝策略相比于其它方法效率更高，速度更快。因为在剪枝过程中，树中的每棵子树最多需要访问一次，在最坏情况下，它的计算时间复杂度也只和非剪枝树的非叶子节点数目成线性关系。

3.9 简述分类树与回归树的联系与区别

**分类树：**以C4.5分类树为例，C4.5分类树在每次分枝时，是穷举每一个feature的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的集合信息熵最小的阈值，按照该标准分枝得到两个新节点，用同样方法继续分枝直到得到类别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的类别不唯一，则以占有最多数的类别作为该叶子节点的最终分类类别。

**回归树：**回归树总体流程与分类树类似，区别在于，回归树的每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是信息熵(信息增益)，而是最小化均方误差即$\frac{1}{N}\sum\limits_{i=1}^{N}(第i个人的年龄-预测年龄)^{2}$。也就是被预测出错的人数越多，错的越离谱，均方误差就越大，通过最小化均方误差能够找到最可靠的分枝依据。分枝直到每个叶子节点上人的年龄都唯一或者达到预设的终止条件(如叶子个数上限)，若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

总结：
(1) 分类树使用信息增益或信息增益率来划分节点；每个节点样本的类别情况投票决定测试样本的类别。
(2) 回归树使用最小均方误差划分节点；每个节点样本的均值作为测试样本的回归预测值。

3.10 $CART$ 如何生成回归树？

3.11 $CART$ 对取值数目$\ge 3$ 的离散特征如何处理？

因为 $CART$ 是二叉树，所以对于样本中有 $N \ge 3$ 个取值的离散特征处理时也只能有两个分支，这就要通过人为的创建二取值序列并取 $Gini Gain$ 最小者作为树分叉决策点。如某特征值具有 [‘young’, ’middle’, ’old’] 三个取值，那么二分序列会有如下3种可能性(空集和满集在 $CART$ 分类中没有意义):

[((‘young’), (‘middle’, ‘old’)), ((‘middle’), (‘young’, ‘old’)), ((‘old’), (‘young’, ‘middle’))]

采用 $CART$ 算法，就需要分别计算按照上述 List 中的二分序列做分叉时的 $Gini$指数，然后选取产生最小的 $GiniGain$​​ 的二分序列做该特征的分叉二值序列参与树构建的递归。

CART不适用于离散特征有过多取值的场景。若一定要使用CART，最好预先人为的将离散特征的取值缩减。 那么对于二分后的左右分支，如果特征取值tuple中元素多于2个，该特征一般还是需要继续参与到子数据集的分割中去。这在一定程度上有助于提升模型的精度(一定意义上改进了C4.5完全的贪心算法，使得模型有一定的全局（局部）特征考量的性质)。

3.12 决策树如何处理缺失值？

缺失值问题可以从四个方面来考虑

(1)在进入模型开始训练之前，我们可以对缺失值做上一定的处理。
① 为缺失值赋上该属性最常见的值或者取均值；
② 如果数据集较大，可以丢弃有缺失值的样本；
③ 根据节点的样例上该属性值出现的情况赋一个概率，比如该节点上有10个样本，其中属性A的取值有6个为“高”，4个为“低”。那么对该节点上缺失的属性A，以0.6的概率设为“高”，0.4的概率设为“低”。

(2) 训练样本在分裂属性上存在缺失值如何处理？(计算分裂损失减少值时，忽略特征缺失的样本，最终计算的值乘以比例(实际参与计算的样本数除以总的样本数))。
$\qquad$假如使用ID3算法，那么选择分类特征时，就要计算所有特征的熵减(信息增益，Gain)。假设10个样本，特征是A，B，C。在计算 A 特征的熵时发现，第10个样本的 A 特征取值缺失，那么就把第10个样本去掉，用前9个样本组成新的样本集，在新样本集上按正常方法计算 A 特征的熵减。然后结果乘0.9（未缺失样本的比例$\frac{9}{10}$），就是 A 特征分裂最终的熵。

(3) 分类特征选择完成，对训练样本分类，发现样本特征缺失怎么办？（将该样本分配到所有子节点中，权重由1变为具有特征 A 的样本划分成的子集样本个数的相对比率，计算错误率的时候，需要考虑到样本权重)。

① 单独为属性缺失的样本划分一个分支子集。
② 比如该节点是根据 A 特征划分，但是待分类样本 A 特征缺失，怎么办呢？假设 A 特征离散，有1、2两种取值，那么就把该样本分配到两个子节点中去，但是权重由1变为相应离散值个数占样本的比例，然后计算错误率的时候乘以样本权重。注意，不是每个样本都是权重为1，存在分数。

(4) 训练完成，给测试集样本分类，有缺失值怎么办？(分类时，如果待分类样本有缺失变量，而决策树决策过程中没有用到这些变量，则决策过程和没有缺失的数据一样；否则，如果决策要用到缺失变量，决策树也可以在当前节点做多数投票来决定(选择样本数最多的特征值方向))

① 如果有单独的缺失分支，使用此分支。
② 给待分类样本的 A 特征分配一个最常出现的属性值，然后进行分支预测。
③ 根据其他特征为该待分类样本填充一个特征a值，然后进行分支处理。
④在决策树中 A 特征节点的分支上，遍历 A 特征节点的所有分支，探索可能所有的分类结果，然后把这些分类结果结合起来一起考虑，按照概率决定一个分类。
⑤ 待分类样本在到达 A 特征节点时就终止分类，然后根据此时 A 节点所覆盖的叶子节点类别状况为其分配一个发生概率最高的类。

3.13 如果决策树属性用完了仍未对决策树完成划分应该怎么办？

当训练集很大以及特征数量并不是很多的情况下，这种状况很容易发生。此时的解决方法一般有两种：
(1) 一种即退出模型，做特征组合、交叉等操作扩充特征。当有了足够多的特征后，便可以有效改善这种情况。但在一般情况下，树模型如果特征过多，相当容易过拟合。
(2) 另一种方法便是直接对叶子节点采用**“多数表决”**，即使用节点中出现最多的类别作为该节点的标签。

3.14 决策树中过拟合出现的原因以及如何避免过拟合？

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

解决方法:
(1) 选择合理的参数(树的深度，叶子结点上的样本数量，不纯度，最大叶子节点数等)进行剪枝，可以分为预剪枝和后剪枝，我们一般采用后剪枝的方法；
(2) 利用K -folds交叉验证，将训练集分为K份，然后进行K次交叉验证，每次使用K − 1 份作为训练样本数据集，另外一份作为测试集；
(3) 减少特征数量，剔除低相关特征，通过L1正则化进行特征选择。
(4) 剔除异常值。

3.15 决策树需要进行归一化处理吗？

决策树是一种简单高效并且具有强解释性的概率模型，是给定特征条件下所属类别的条件概率分布的一种退化表示(虽然它并不求解概率密度函数，但依据训练样本可以用类别频率来代替概率)。

概率模型是不需要归一化的，概率模型不关心变量的值，而是关心变量的分布和变量之间的条件概率。数值缩放不会影响决策树的分裂点位置。

3.16 常用的决策树一定是二叉树吗？二叉决策树与多分支决策树相比各有什么特点？

不一定，C4.5和ID3都是多叉树。

二叉决策树不像多叉树那样会形成过多的数据碎片，而二叉决策树可能会得到更深的最终决策树。

3.17 在一棵决策树构建过程中较为耗时的步骤是什么？

确定最佳分割点，在该步骤中需要对特征值进行排序，计算信息增益等，非常耗时。

3.18 举例说明什么时候其他模型比决策树会有更好的表现

决策树算法主要应用于非线性模型，若已知数据集是满足线性假设的，那么我们可以直接用一个线性模型取得比较好的预测结果。

3.19 决策树在选择特征进行分类时一个特征被选择过后，之后还会选择到这个特征吗？

ID3和C4.5的特征在层级之间不会重复，但CART是会复用的。

3.20 决策树模型的优缺点

优点：
① 易于理解，决策树易于理解和实现。人们在通过解释后都有能力去理解决策树所表达的意义。
② 数据处理简单，决策树能够直接处理自变量的缺失值。其他的算法模型往往要求先把数据一般化，比如去掉多余的或者空白的属性。
③ 能够同时处理数据型变量和类别变量。其他的技术往往要求特征是单一类型的。
④ 是一个白盒模型，如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
⑤ 易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。
⑥ 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
⑦ 如果有不相关的 feature，没什么干扰，如果数据中有不相关的 feature，这个 feature 可能不出现在树的节点里。逻辑回归和 SVM 没有这样的天然特性(但是有相应的解决方案，比如逻辑回归里的 L1 正则化)。
⑧ 决策树可以用作变量选择的工具。
⑨ 决策树只使用了定序或连续自变量取值的大小顺序，它对自变量的测量误差或异常值是稳健的。

缺点：
① 很容易在训练数据中生成复杂的树结构，造成过拟合。剪枝可以缓解过拟合。
② 不适合处理高维数据，当属性数量过大的时候，部分决策树就不太适用了。
③ 每个非叶节点的划分都只考虑单个变量，因此很难发现基于多个变量的组合的规则。
④ 为每个非叶节点选择最优划分时，都仅考虑对当前节点划分的结果，这样只能够达到局部最优，而无法达到全局最优。
⑤ 由于决策树的贪心特性，树的结构不稳定，往往一个样本的输入会导致树结构很大的变动。
⑥ 无法解决异或问题，而神经网络可以解决该问题。
⑦ 如果某些特征的样本比例过大，生成的决策树容易偏向于这些特征。可以通过调节样本权重来改善。

3.21 树模型的应用场景

① 如果不强调模型的解释度，尽量避免单棵决策树，用集成树模型。
② 在集成树模型中，优先推荐使用XGBoost。
③ 在中小数据集上，优先选择集成树模型。大数据集上推荐神经网络。
④ 在需要模型解释度的项目上，优先使用树模型。
⑤ 在项目时间较短的项目上，如果数据质量低(大量缺失值、噪音等)，优先使用集成树模型。
⑥ 在硬件条件有限及机器学习知识有限的前提下，优先选择树模型。

3.22 决策树与逻辑回归的区别

① 决策树可以处理有缺失值的数据，而逻辑回归需要预先对缺失数据进行处理；
② 逻辑回归对数据整体结构的分析优于决策树，而决策树对局部结构的分析优于逻辑回归；(决策树由于采用分割的方法，所以能够深入数据内部，但同时失去了对全局的把握。一个分层一旦形成，它和别的层面或节点的关系就被切断了，以后的挖掘只能在局部中进行。同时由于切分，样本数量不断萎缩，所以无法支持对多变量的同时检验。而逻辑回归，始终着眼整个数据的拟合，所以对全局把握较好。但无法兼顾局部数据，或者说缺乏探查局部结构的内在机制)
③ 逻辑回归擅长分析线性关系，而决策树对线性关系的把握较差但对非线性数据拟合效果较好。线性关系在实践中有很多优点：简洁，易理解，可以在一定程度上防止对数据的过度拟合。
④ 逻辑回归对异常值比较敏感，容易受极端值的影响，而决策树对异常值具有稳健性。
⑤ 应用上的区别：决策树的结果相比于逻辑回归略显粗糙。逻辑回归原则上可以提供数据中每个样本点的概率，而决策树只能把挖掘对象分为有限的概率组群。比如决策树确定17个节点，全部数据就只能有17个概率，在应用上受到一定限制。就操作来说，决策树比较容易上手，需要的数据预处理较少，而逻辑回归则要去一定的训练和技巧。
⑥ 执行速度上：当数据量很大的时候，逻辑回归的执行速度非常慢，而决策树的运行速度明显快于逻辑回归。