已知输入变量与输出变量均为连续变量的预测问题被称为回归问题；

输出变量为有限个离散变量的预测问题称为分类问题。

决策树是一种常见的分类与回归方法，因其呈树状结构而得名。决策树算法的思路简单易懂，但也包含丰富的内容：随机森林、GBDT、Xgboost等流行算法都是在其模型上的延伸。

Q1 简要介绍决策树是什么

决策树是一种描述对实例进行分类的结构。

严格来说，决策树由结点与有向边共同构成树形结构；其中结点又分为内部结点、叶节点，他们分别表示特征、类别。决策树要解决的问题本质上就是从训练数据找到一组“最佳“的分类规则，这个树可能有多个，也可能没有。“最佳”则用损失函数来靠近。

决策树的核心思想就是，找到一个最优特征，对该特征进行最好的划分，并且重复上述步骤，不断丰富内部节点，直到满足指定条件。

决策树的实施包括什么？

决策树的实施包括特征选择，决策树的生成与树的修剪。

1. 特征选择

由于通常实际项目中的特征变量数都会远远大于两个。此时对多个特征进行先后顺序不同的决策时会有不同的结果与准确率，所以就需要“特征选择”来决定当前应选用哪个特征来划分。

直观来讲，当下特征中对分类“最有效”的特征应该优化选择；比如判断是否爱吃四川火锅，“是否爱吃辣”比“是否有洁癖”更有代表性，所以应当排在前面。

从定量的角度，信息增益与信息增益比就是可以表示特征“有效性”的指标。

(1)熵

香农曾说过，信息是用来消除随机不确定性的东西。回到分类问题本身，对于用决策树分类前的数据，因为没有其类别的任何信息，此时数据的不确定性是最大的，熵也是最大的；对于决策树分类后的数据，理论上，特征信息被最有效地利用了，数据的随机不确定性也得到最大程度的消除，数据最后被安排在几种类别中，此时数据的不确定性是最小的，即熵是最小的；而过程中每用一个特征进行一次决策，就能降低一次数据的熵。自然地，当下最优的特征就是使熵降低最多的特征。这就是信息增益的主要思想。

(2)信息增益

那么如何理解信息增益呢？根据定义，信息增益可以视作某一特征对数据集混乱程度降低的贡献程度:即当某个特征确定下来后，数据集熵的降低得越明显，说明该特征对数据集提供了更多的信息，贡献度越大。

一般地，这个差值也称为互信息。

2.那么如何理解信息增益呢？根据定义，信息增益可以视作某一特征对数据集混乱程度降低的贡献程度:即当某个特征确定下来后，数据集熵的降低得越明显，说明该特征对数据集提供了更多的信息，贡献度越大。
一般地，这个差值也称为互信息。

2.决策树的生成

在确定了特征选择的方法后，树就可以一层一层生成了。本节介绍的ID3算法与C4.5算法是由Quinlan分别在1986年与1993年提出的。

(1)ID3 算法

ID3算法在特征选择的过程，用上文所述的信息增益原则进行；在树的生成过程，对所选取的特征的不同取值进行划分；最后建立一棵决策树。值得注意的是在决策树生成前要先设定好一个阈值，当余下所有特征的信息增益小于这个阈值时，树的生长就完成了。

(2)C4.5 算法

C4.5算法是ID3算法的延伸，在特征选择的过程中，用信息增益比的原则进行，这是与ID3算法不同的地方；在树的生成过程，对所选的特征的不同取值进行划分；最后建立一颗决策树。

3.决策树的修剪
根据上述算法生成的决策树，由于考虑到每个特征的每种可能取值，容易出现过拟合，即对训练数据的分类准确率很高，对测试数据分类的准确率比较低。这是决策树的算法特征所决定的，所以对决策树的修剪就显得非常重要。
本文介绍的是用极小化损失函数进行剪枝的方法。损失函数如下所示：

其中T表示确定的一棵决策树，该数共有｜T｜个叶子结点，每个结点下包含训练样本Nt个，Ht（T)表示训练样本Nt的经验熵。

可以看到损失函数包括两部分:决策树分类结果的熵与决策树的叶子结点数量。

极小化损失函数时，既需要使得决策树分类后的数据熵很小，同时也需要满足决策树的叶子结点不能太多，即决策树不能太大。其中系数α表示对两者的平衡，α越大，就越倾向于牺牲一定的模型准确率以减少树的叶子结点数量；反之相反。

剪枝的具体步骤如下:

1)计算每个结点的经验熵。

2)计算损失函数：记当前树的某个叶子结点剪掉前后的树的损失函数，记为Cα（T前)与Cα（T后)，若Cα（T前)≥Cα（T前)，则剪掉该叶子结点，其父结点成为新的叶子结点，得到一颗新的决策树。

3)对决策树的叶子结点重复2)的过程，直至不能再剪裁为止。

Q2 决策树算法的优点和缺点是什么？

优点：

1)思路简明，计算速度快。

2)决策树的分类规则非常清晰，能够看到那些特征比较重要，具有较强的可解释性。能够同时处理数据型和常规型属性。很多算法要求数据属性是统一的。

3)对缺失值不敏感，可以处理不相关特征数据。

4)不需要任何参数假设。

缺点：

1)对连续的特征变量处理效果不好，因为算法模型中主要都是对分类变量的特征讨论的，例如树的生成时将某一特征的所有属性都生成子叶。

2)在树的生成过程中，对某一特征进行划分时会将该特征每一可能的取值分为一类，就会使得树对取值较多的连续变量过于敏感；例如，如果某特征的每一取值的样本都是唯一的，即是同一类的，用该特征进行划分就会有明显的信息增益。但实际中这并不是最有意义的特征。

3)非常容易过拟合。

Q3 试着简要介绍随机森林

由于决策树分类器的缺点和分类方法自身较为单薄， Leo Breiman和 Adele Cutler于2001年提出了随机森林算法，随机森林，顾名思义，就是指利用多棵决策树对样本进行训练并预测的一种方法。

随机森林的思想可以用一个简单例子来解释。

假设多位评委为饭店评定星级，每位评委都应独立地对餐品做出“五级”或“四级”的评价，最终该饭店的星级，则由所有评委的评价结果决定，最多评委评价的级别就是该饭店的星级。

这里，整个评委团队就像是随机森林的算法模型，饭店则是待测对象，饭店的最终星级由评委团队中每一位评委的投票结果决定。

随森林包含多个决策树，就算每棵树的分类能力比较弱，或者存在误差，但依靠大量决策树的投票结果，误差会相对抵消，从而使得效果较好的“决策树”的分类结果表现出来。这就是随机森林算法的思想。

同样是决策树，随机森林模型既可以处理回归问题，也可以处理分类问题。原因是在随机森林的实施过程中，使用的是不同于上述简单分类决策树的CART决策树。

简要介绍随机森林实施步骤与特点。

1.CART决策树

在介绍随机森林的实验步骤之前，需要先简要介绍一下CART决策树。CART模型的全称是分类与回归树模型，是在1984年由Breiman由出。不同于简单分类决策树，CART决策树是二叉树，即要求对每次某个特征划分时只能分为两类，但会对该特征的不同取值进行多次划分，以保证信息得到充分使用。

下面分别介绍回归树与分类树是如何进行特征选择与树的生成的。

(1)回归树

已知决策树本质上是建立一种划分特征空间的规则，一个特征空间对应着一个输出值。

则回归树模型可写为:

其中Rk表示一划分好的特征空间域，一共有K个这样的划分，每一个划分的特征空间的输出值为ck，ck的取值为属于特征空间Rk的样本点的输出值的平均水平，I(x∈Rk)则为示性函数。
特征选择和树的生成其实就是对特征空间建立划分规则的过程。不同于简单分类决策树，回归树始终满足如下损失函数，并以此为原则进行特征空间的划分:

那怎么认识这个损失函数呢？

首先，由于CART决策树是二叉树，所以每次划分会把特征空间划分为两部分，损失函数就是两部分数据的误差的和，这两部分特征空间分别记为R1（j，s)与R2（j，s)。为什么划分好的特征空间会与（j，s)有关呢？假设在一结点选择特征x以及其某一取值s，划分时则将特征空间分为｛x≥s｝与｛x＜s｝两部分。所以特征空间是由（j，s)共同确定的。最小化损失函数是要使得两部分的误差都很小。

然后以第一个部分的误差为例，来看怎么定义一个特征空间内的样本点的误差。根据回归决策树的性质，一个特征范围内的取值是一样的，所以误差才有：

而最合理的c1取值应该是使得改组内方差最小的值(均值)。这也和回归树模型中Ck的取值方法是统一的。

(2)分类树

分类树（classification tree)简单地说，就是根据训练数据集构造一个类似树形的分类决策模型，然后用这个模型来辅助决策。

例如下图是一个简单的是否举行某个活动的决策树(分类树)：

　　 　　　　　　　　

　

我们可以通过上面的决策树进行预测，当天气晴朗，交通畅通时，我们预测该活动很可能要举办；当天下小雨交通拥挤时，我们预测活动很可能被取消。

这只是一个简单的小例子，真实中的决策树方法包括以下几个步骤：

(1)收集数据：可以使用任何方法。

(2)准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。

(3)选取划分算法：根据数据的特点，选取合适的划分算法

(4)构造决策树：使用选取的划分算法构造树形的决策模型

(5)测试算法：使用经验树计算错误率

(6)使用算法：使用决策树模型预测决策

2.随机森林的实施步骤

1）随机有放回地从N个训练样本中抽取N个样本，作为生成树的训练集。

2）对K个特征随机选k个作为特征子集在对树做特征选择时，从特征子集中选择最优的特征。

3）让树做最大程度的生长，不做树的修剪。

4）重复1）～3）的步骤T次，建立T棵决策树；若是分类问题，则某样本T棵决策树的投票结果即为最终类别；若是回归问题，则T棵决策树的回归结果的算术平均值即为最终结果。

3.随机森林的几个特点

1）采用Bootstrap抽样法。原因在于:若不如此，会使得每棵树的分类结果一样；这样失去了树之间的独立性，随机森林的“投票”思想也就失去了意义。

2）每次随机从特征中选取k≤K个作为特征子集建立决策树。一方面，可以降低复杂度，加快算法的实施过程；另一方面，可以保证树与树之间有更好的独立性。实际上当k-K时，这里的决策树就等价于普通的CART决策树；k≤K亦可增强模型的泛化能力。

3）不需要对树进行剪裁。已知剪裁是为了避免决策树的过拟合；但由于随机森林的实施过程对样本和特征都进行了随机选择，再加上最终投票的形式，不剪枝也不会出现过拟合，所以就不必剪裁了。

Q4如何做随机森林参数的选择

在实施步骤中包含两个参数:特征子集的数量和需建立的决策树数量T

对于后者，由投票的思想，理论上T应该越大越好；但由于会影响算法的复杂度，应选择适当的T使得准确率与复杂度达到平衡。

对于前者，已知当k较大时，树与树相关性比较强，会影响模型的准确率；k较小时，单棵树的分类能力太差，也会影响模型的准确率。经验上一般把特征数量的对数作为特征子集的数量。

为了更好地取得合适的k，通常会用袋外错误率最低的方法。

实际上，使用 Bootstrap法确定每棵树的训练集时，对于第i棵树，约有三分之一的样本没有参与树的生成；这些样本被称为这棵树的袋外样本(oob样本)由此，袋外错误率(out-of–bag error)的定义如下:

其中N1表示对于某个样本，它作为oob样本的树它的分类错误的棵数，N表示对于某个样本，计算它作为oob样本的树的数量。可证明 oob error是随机森林泛化误差的一个无偏估计。

Q5试简要介绍随机森林的优缺点

优点:

1）在当前所有算法中，有较好的准确率。

2）可高度并行化，对于大数据大样本很有优势。

3）实现过程相对简单。

4）模型较稳健，对部分的特征缺失不敏感。

5）随机森林算法能够降低方差。为什么能降低方差呢？因为随机森林的预测输出值是多课决策树的均值，如果有n个独立同分布的随机变量xi,它们的方差都为γ2，则它们的均值的方差为：

缺点：

1）对于噪音比较大的样本集，容易过拟合。

2）取值划分较多的特征容易对模型产生更大的影响，从而影响模型的效果

常见面试笔试题:随机森林的“随机性”表现在哪里？比决策树好在哪里？

分析:“随机性”表现在两方面:一方面，每棵决策树的样本是经过 Bootstrap随机选取的；另一方，每棵决策树生成所用到的特征是从所有特征集中随机选取的。

相较于决策树，正因为随机森林的“随机性”，其在过拟合问题上有所改善，极大地提高了分类模型的准确率。

Q6决策树中C4.5算法优化了ID3算法的什么缺点

ID3算法使用信息增益来选择用于分组的变量，但是这样可能会出现偏向于取值比较多的变量的情况，并使得模型预测的准确率下降。而C4.5利用信息增益率能够有效地解决上述ID3使用信息增益时出现的问题。

C4.5算法在构造决策树的过程中可以进行相应的剪枝，但是ID3算法没有。并且C4.5算法在对数据预处理的时候还会对连续型的变量进行离散化处理。