机器学习面试干货精讲

Coggle数据科学

发布于 2019-09-12 17:23:32

7850

发布于 2019-09-12 17:23:32

文章被收录于专栏：Coggle数据科学Coggle数据科学

写于二零一八年二月十五日，农历大年三十

整体内容划分：

推荐书单、公开课
面试核心内容提纲

本内容涉及模型核心数学公式，把本人面试中常被问到问题以及模型知识点的总结，起到提纲挈领作用，在准备的过程中抓住每个模型的重点。

面试核心内容目录：

决策树
随机森林
Adaboost
GBDT
logistic 回归
SVM支持向量机
朴素贝叶斯
xgboost
lightgbm

面试核心内容提纲

一、决策树

1.1 原理

决策树是一种基本的分类与回归方法，其模型就是用一棵树来表示我们的整个决策过程。这棵树可以是二叉树（比如CART 只能是二叉树），也可以是多叉树（比如 ID3、C4.5 可以是多叉树或二叉树）。根节点包含整个样本集，每个叶节都对应一个决策结果（注意，不同的叶节点可能对应同一个决策结果），每一个内部节点都对应一次决策过程或者说是一次属性测试。从根节点到每个叶节点的路径对应一个判定测试序列。

举个例子：

就像上面这个例子，训练集由三个特征：outlook(天气)，humidity（度），windy（是否有风）。那么我们该如何选择特征对训练集进行划分？连续型特征（比如湿度）划分的阈值又是如何确定的？

决策树的生成就是不断的选择最优的特征对训练集进行划分，是一个递归的过程。递归返回的条件有三种：

当前节点包含的样本属于同一类别，无需划分；
当前属性集为空，或所有样本在属性集上取值相同，无法划分；
当前节点包含样本集合为空，无法划分。

1.2 ID3、C4.5、CART

这三个是非常著名的决策树算法。简单粗暴来说:

ID3 使用信息增益作为选择特征的准则；
C4.5 使用信息增益比作为选择特征的准则；
CART 使用 Gini 指数作为选择特征的准则。

熵(entropy)

在信息论与概率论中，熵用于表示随机变量不确定性的度量。

设X是一个有限状态的离散型随机变量，其概率分布为:

则随机变量

的熵定义为

熵越大，则随机变量的不确定性越大。

条件熵(conditional entropy)

随机变量

给定的条件下，随机变量

的条件熵

定义为：

其中，

。

信息增益(information gain)

信息增益表示的是：得知特征X的信息而使得类Y的信息的不确定性减少的程度。

具体定义如下。

特征A对训练数据集D的信息增益

定义为集合D的经验熵

与特征A给定条件下D的经验条件熵

之差，即

一般地，熵

与条件熵

之差称为互信息(mutual information).

ID3

熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。

信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性a来进行划分所获得的 “纯度提升” 越大。也就是说，用属性a来划分训练集，得到的结果中纯度比较高。

ID3优点是理论清晰、方法简单、学习能力较强，但也存在一些缺点：

只能处理分类属性的数据，不能处理连续的数据；
划分过程会由于子集规模过小而造成统计特征不充分而停止；
ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。

C4.5

C4.5 克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。公式：

其中

，

是特征

取值的个数

C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。

CART

CART 与 ID3，C4.5 不同之处在于 CART 生成的树必须是二叉树。也就是说，无论是回归还是分类问题，无论特征是离散的还是连续的，无论属性取值有多个还是两个，内部节点只能根据属性值进行二分。

CART 的全称是分类与回归树（classification and regression tree）。从这个名字中就应该知道，CART 既可以用于分类问题，也可以用于回归问题。

回归树

使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化了平方误差。

要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。

具体为，假设已将输入空间划分为

个单元

，即

个特征，并且在每个单元

上有一个固定的输出值

，于是回归树可以表示为

当输入空间的划分确定时，可以用平方误差

来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优值。

选择最优切分特征

和切分点

,具体做法为:

首先遍历特征

,对固定的切分特征

扫描切分点

,选择使上式达到最小值的对

分类树

使用 Gini 指数最小化准则来选择特征并进行划分；Gini 指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是，基尼指数是为了最小化误分类的概率。

假设有

个类别，样本点属于第

类的概率为

,则概率分布的基尼指数定义为：

1.3 信息增益 vs 信息增益比

之所以引入了信息增益比，是由于信息增益的一个缺点。那就是：信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项，解决了这个问题。

1.4 Gini 指数 vs 熵

既然这两个都可以表示数据的不确定性，不纯度。那么这两个有什么区别那？

Gini 指数的计算不需要对数运算，更加高效；
Gini 指数更偏向于连续属性，熵更偏向于离散属性。

1.5 剪枝

决策树算法很容易过拟合（overfitting），剪枝算法就是用来防止决策树过拟合，提高泛华性能的方法，剪枝分为预剪枝与后剪枝。

预剪枝是指在决策树的生成过程中，对每个节点在划分前先进行评估，若当前的划分不能带来泛化性能的提升，则停止划分，并将当前节点标记为叶节点。

后剪枝是指先从训练集生成一颗完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点，能带来泛化性能的提升，则将该子树替换为叶节点。

那么怎么来判断是否带来泛化性能的提升呢？最简单的就是留出法，即预留一部分数据作为验证集来进行性能评估。交叉验证

预剪枝和后剪枝的比较

1.6 总结

决策树算法主要包括三个部分：特征选择、树的生成、树的剪枝。常用算法有 ID3、C4.5、CART。

特征选择。特征选择的目的是选取能够对训练集分类的特征。特征选择的关键是准则：信息增益、信息增益比、Gini 指数；
决策树的生成。通常是利用信息增益最大、信息增益比最大、Gini 指数最小作为特征选择的准则。从根节点开始，递归的生成决策树。相当于是不断选取局部最优特征，或将训练集分割为基本能够正确分类的子集；
决策树的剪枝。决策树的剪枝是为了防止树的过拟合，增强其泛化能力。包括预剪枝和后剪枝。

二、随机森林（Random Forest）

要说随机森林就要先说 Bagging，要说 Bagging 就要先说集成学习。

2.1 集成学习方法

集成学习（ensemble learning）通过构建并组合多个学习器来完成学习任务。集成学习将多个学习器进行结合，常获得比单一学习器显著优越的泛化性能。

个体学习器通常由一个现有的学习算法从训练数据产生（比如 C4.5,BP 等），此时集成中只包含同种类型的个体学习器，例如“决策树集成”中全是决策树，“神经网络集成”中全是神经网络，这样的集成是“同质”的，同质集成中的个体学习器称“基学习器”。当然也存在不同质的学习器存在于统一集成中，常称为“组件学习器”或直接称为个体学习器。《机器学习》周志华

原则：要获得比单一学习器更好的性能，个体学习器应该好而不同。即个体学习器应该具有一定的准确性，不能差于弱学习器，并且具有多样性，即学习器之间有差异。

根据个体学习器的生成方式，目前集成学习分为两大类：

个体学习器之间存在强依赖关系、必须串行生成的序列化方法。代表是 Boosting；
个体学习器之间不存在强依赖关系、可同时生成的并行化方法。代表是 Bagging 和随机森林（Random Forest）。

2.2 Bagging

bagging平均法

前面提到，想要集成算法获得性能的提升，个体学习器应该具有独立性。虽然 “独立” 在现实生活中往往无法做到，但是可以设法让基学习器尽可能的有较大的差异。

Bagging 给出的做法就是对训练集进行采样，产生出若干个不同的子集，再从每个训练子集中训练一个基学习器。由于训练数据不同，我们的基学习器可望具有较大的差异。

Bagging 是并行式集成学习方法的代表，采样方法是自助采样法（bootstrap），用的是有放回的采样。初始训练集中大约有 63.2% 的数据出现在采样集中。

Bagging 在预测输出进行结合时，对于分类问题，采用简单投票法；对于回归问题，采用简单平均法。

Bagging 优点：

高效。Bagging 集成与直接训练基学习器的复杂度同阶；
Bagging 能不经修改的适用于多分类、回归任务；
包外估计。使用剩下的样本作为验证集进行包外估计（out-of-bag estimate）。

Bagging 主要关注降低方差。（low variance）

偏差（bias）：描述的是预测值（估计值）的期望与真实值之间的差距。偏差越大，越偏离真实数据，如上图第二行所示。 方差（variance）：描述的是预测值的变化范围，离散程度，也就是离其期望值的距离。方差越大，数据的分布越分散，如上图右列所示。

2.3 随机森林（Random Forest）

2.3.1 原理

随机森林（Random Forest）是 Bagging 的一个变体。Ramdon Forest 在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入随机属性选择。

原来决策树从所有特征中，选择最优特征。Ramdom Forest 的每一颗决策树中的每一个节点，先从该节点的特征集中通过bootstrap的方法随机选择 K 个特征的子集，然后从这个特征子集中通过决策树算法选择最优特征进行划分。（注意：除了随机获取特征以外，还能随机获取样本集，使用这些随机抽取的样本得到不同的决策树）

控制了随机性的引入程度，是一个重要的超参数。

预测：

分类：简单投票法；
回归：简单平均法。

2.3.2 具体构造过程

从原始训练集中使用bootstrap方法随机有放回采样选出m个样本，共进行n_tree次采样，生成n_tree个训练集
对于n_tree个训练集，我们分别训练n_tree个决策树模型
对于单个决策树模型，假设训练样本特征的个数为n，那么每次分裂时根据信息增益/信息增益比/基尼指数选择最好的特征进行分裂
每棵树都一直这样分裂下去，直到该节点的所有训练样例都属于同一类。在决策树的分裂过程中不需要剪枝
将生成的多棵决策树组成随机森林。对于分类问题，按多棵树分类器投票决定最终分类结果；对于回归问题，由多棵树预测值的均值决定最终预测结果

2.3.3 优缺点

优点：

由于每次不再考虑全部的属性，而是一个属性子集，所以相比于 Bagging 计算开销更小，训练效率更高；
由于增加了属性的扰动，随机森林中基学习器的性能降低，使得在随机森林在起始时候性能较差，但是随着基学习器的增多，随机森林通常会收敛于更低的泛化误差，相比于 Bagging；
两个随机性的引入，使得随机森林不容易陷入过拟合，具有很好的抗噪声能力；
对数据的适应能力强，可以处理离散和连续的，无需要规范化；
可以得到变量的重要性，基于oob错误率（袋外错误率out-of-bag error）和基于 Gini 系数的变化。
不同决策树可以由不同主机并行训练生成，效率很高

缺点：

在噪声较大的时候容易过拟合。

三、AdaBoost

AdaBoost 是 Boosting 的代表，前面我们提到 Boosting 是集成学习中非常重要的一类串行化学习方法。

3.1 Boosting

Boosting 是指个体学习器之间存在强依赖关系，必须串行序列化生成的集成学习方法。他的思想来源是三个臭皮匠顶个诸葛亮。Boosting 意为提升，意思是希望将每个弱学习器提升为强学习器。

工作机制如下：

先从初始训练集中学习一个基学习器；
根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续收到更多关注；
基于调整后的样本分布来训练下一个基学习器；
如此反复，直到基学习器数目达到 T，最终将这 T 个基学习器进行加权结合。

对训练样本分布调整，主要是通过增加误分类样本的权重，降低正确分类样本的权重。

Boosting 关注的主要是降低偏差。（low bias）

3.2 AdaBoost 原理

面临两个问题：

在每一轮，如何改变训练数据的概率分布或者权值分布。（也可以重采样，但是 AdaBoost 没这么做）；
如何将弱分类器组合成强分类器。

AdaBoost 的做法：

提高那些被前一轮弱分类器错误分类样本的权值，降低那些被正确分类的样本的权值。这样一来，那些没有得到正确分类的数据，由于其权值的加大而受到后一轮弱分类器的关注；
采用加权多数表决。具体的，加大分类错误率低的分类器的权值，使其在表决中起较大作用，减少分类误差率大的弱分类器的权值，使其在表决中起较小作用。

弱分类器被线性组合成为一个强分类器。

训练目标：

最小化指数损失函数。

三部分组成：

分类器权重更新公式；
样本分布（也就是样本权重）更新公式；
加性模型。最小化指数损失函数。

3.3 AdaBoost 优缺点

优点：

Adaboost作为分类器时，分类精度很高
在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。
作为简单的二元分类器时，构造简单，结果可理解。
不容易发生过拟合

缺点：

对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。

四、GBDT

GBDT（Gradient Boosting Decision Tree）又叫 MART（Multiple Additive Regression Tree），是一种迭代的决策树算法。本小节从以下几个方面进行阐述：

Regression Decision Tree(DT)；
Gradient Boosting(GB)；
Shrinkage(算法的一个重要演进分支，目前大部分源码都是基于该版本实现)；
GBDT 适用范围；
与随机森林的对比。

4.1 DT：回归树 Regression Decision Tree

GBDT 中的树全部都是回归树，核心就是累加所有树的结果作为最终结果。只有回归树的结果累加起来才是有意义的，分类的结果累加是没有意义的。

GBDT 调整之后可以用于分类问题，但是内部还是回归树。

这部分和决策树中的是一样的，无非就是特征选择。回归树用的是最小化均方误差，分类树是用的是最小化基尼指数（CART）

4.2 GB：梯度迭代 Gradient Boosting

首先 Boosting 是一种集成方法。通过对弱分类器的组合得到强分类器，他是串行的，几个弱分类器之间是依次训练的。GBDT 的核心就在于，每一颗树学习的是之前所有树结论和的残差。

Gradient 体现在：无论前面一颗树的 cost function 是什么，是均方差还是均差，只要它以误差作为衡量标准，那么残差向量都是它的全局最优方向，这就是 Gradient。

4.3 Shrinkage

Shrinkage（缩减）是 GBDT 算法的一个重要演进分支，目前大部分的源码都是基于这个版本的。

核心思想在于：Shrinkage 认为每次走一小步来逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易防止过拟合。

也就是说，它不信任每次学习到的残差，它认为每棵树只学习到了真理的一小部分，累加的时候只累加一小部分，通过多学习几棵树来弥补不足。

具体的做法就是：仍然以残差作为学习目标，但是对于残差学习出来的结果，只累加一小部分（step* 残差）逐步逼近目标，step 一般都比较小 0.01-0.001, 导致各个树的残差是渐变而不是陡变的。

本质上，Shrinkage 为每一颗树设置了一个 weight，累加时要乘以这个 weight，但和 Gradient 没有关系。

这个 weight 就是 step。跟 AdaBoost 一样，Shrinkage 能减少过拟合也是经验证明的，目前还没有理论证明。

4.4 GBDT 适用范围

GBDT 可以适用于回归问题（线性和非线性）；
GBDT 也可用于二分类问题（设定阈值，大于为正，否则为负）和多分类问题。

4.5 GBDT 和随机森林区别（重点）

GBDT 和随机森林的相同点：
- 都是由多棵树组成；
- 最终的结果都由多棵树共同决定。
GBDT 和随机森林的不同点：
- 组成随机森林的可以是分类树、回归树；组成 GBDT 只能是回归树；
- 组成随机森林的树可以并行生成（Bagging）；GBDT 只能串行生成（Boosting）；这两种模型都用到了Bootstrap的思想。
- 对于最终的输出结果而言，随机森林使用多数投票或者简单平均；而 GBDT 则是将所有结果累加起来，或者加权累加起来；
- 随机森林对异常值不敏感，GBDT 对异常值非常敏感；
- 随机森林对训练集一视同仁权值一样，GBDT 是基于权值的弱分类器的集成；
- 随机森林通过减小模型的方差提高性能，GBDT 通过减少模型偏差提高性能。

TIP

1. GBDT 相比于决策树有什么优点

泛化性能更好！GBDT 的最大好处在于，每一步的残差计算其实变相的增大了分错样本的权重，而已经分对的样本则都趋向于 0。这样后面就更加专注于那些分错的样本。

2. Gradient 体现在哪里？

可以理解为残差是全局最优的绝对方向，类似于求梯度。

3. re-sample

GBDT 也可以在使用残差的同时引入 Bootstrap re-sampling，GBDT 多数实现版本中引入了这个选项，但是是否一定使用有不同的看法。

原因在于 re-sample 导致的随机性，使得模型不可复现，对于评估提出一定的挑战，比如很难确定性能的提升是由于 feature 的原因还是 sample 的随机因素。

五、Logistic 回归（熟悉推导过程）

LR 原理；
参数估计；
LR 的正则化；
为什么 LR 能比线性回归好？
LR 与 MaxEnt 的关系。

5.1 LR 模型原理

首先必须给出Logistic分布：

是位置参数，

是形状参数。对称点是

，

越小，函数在

附近越陡峭。

然后，二分类 LR 模型，是参数化的 logistic 分布，使用条件概率来表示：

然后，一个事件的几率（odds）：指该事件发生与不发生的概率比值：

对数几率：

那么对于逻辑回归而言，

的对数几率就是：

最终，输出

的对数几率是输入

的线性函数表示的模型，这就是逻辑回归模型。

5.2 参数估计

在统计学中，常常使用极大似然估计法来估计参数。即找到一组参数，使得在这组参数下，我们数据的似然度（概率）最大。(极大似然估计：就是利用已知的样本结果信息，反推最具有可能（最大概率）导致这些样本结果出现的模型参数值，即‘模型已定，参数未知’)

似然函数：

对数似然函数：

如何得到逻辑回归的损失函数?

我们希望上式越大越好，换句话说，对于给定样本数量

，我们希望

越小越好，这个也就是LogLoss。

对应的损失函数：

为什么LR的输入特征一般是离散的而不是连续的？

在工业界，很少直接将连续值作为逻辑回归模型的特征输入，而是将连续特征离散化为一系列0、1特征交给逻辑回归模型，这样做的优势有以下几点：

离散特征的增加和减少都很容易，易于模型的快速迭代；
稀疏向量内积乘法运算速度快，计算结果方便存储，容易扩展；
离散化后的特征对异常数据有很强的鲁棒性：比如一个特征是年龄>30是1，否则0。如果特征没有离散化，一个异常数据“年龄300岁”会给模型造成很大的干扰；
逻辑回归属于广义线性模型，表达能力受限；单变量离散化为N个后，每个变量有单独的权重，相当于为模型引入了非线性，能够提升模型表达能力，加大拟合；
离散化后可以进行特征交叉，由M+N个变量变为M*N个变量，进一步引入非线性，提升表达能力；
特征离散化后，模型会更稳定，比如如果对用户年龄离散化，20-30作为一个区间，不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反，所以怎么划分区间是门学问；
特征离散化以后，起到了简化了逻辑回归模型的作用，降低了模型过拟合的风险。

李沐少帅指出，模型是使用离散特征还是连续特征，其实是一个“海量离散特征+简单模型” 同 “少量连续特征+复杂模型”的权衡。既可以离散化用线性模型，也可以用连续特征加深度学习。就看是喜欢折腾特征还是折腾模型了。通常来说，前者容易，而且可以n个人一起并行做，有成功经验；后者目前看很赞，能走多远还须拭目以待。

5.3 最优化方法

逻辑回归模型的参数估计中，最后就是对

求最小值。这种不带约束条件的最优化问题，常用梯度下降，牛顿法和拟牛顿法，共轭梯度法来解决。

使用梯度下降法求解逻辑回归参数估计

求

梯度：

更新

：

5.4 正则化

正则化为了解决过拟合问题。分为 L1 和 L2 正则化。主要通过修正损失函数，加入模型复杂性评估；正则化是符合奥卡姆剃刀原理：在所有可能的模型中，能够很好的解释已知数据并且十分简单的才是最好的模型。

表示范数，

和

分别应用 L1 和 L2 正则。

L1 正则化。向量中各元素绝对值之和。又叫做稀疏规则算子（Lasso regularization）。关键在于能够实现特征的自动选择，参数稀疏可以避免非必要的特征引入的噪声；
L2 正则化。使得每个元素都尽可能的小，但是都不为零。在回归里面，有人把他的回归叫做岭回归（Ridge Regression），也有人叫他 “权值衰减”（weight decay）。