【算法岗必看系列】机器学习高频面试题一

前言

时光荏苒，白驹过隙，又是一年招聘季。楼主是去年毕业的应届生，当时春招找实习的时候，天天泡在牛客看面经刷题，好不怀念！现在准备整理下自己当时搜集的一些高频面试题，分享给牛友们。题目范围主要是机器学习以及深度学习相关的，都比较基础，但是非常经典，很多都在实际面试过程中碰到过，所以我每次面试前都会看一遍，这样会让自己更有底气（心理作用hhh）。这篇主要是机器学习相关的知识，之后还会更新深度学习相关的面试题，感兴趣的同学可以关注一波。

知识总结

线性回归模型
假设特征和结果满足线性关系；经过最⼤似然估计推导出来的待优化的⽬标函数与平⽅损失函数是等价的。

岭回归
加入L2正则项，等价于对参数w引入协方差为a的零均值高斯先验，不能做variable selection。
LASSO回归
加入L1正则项，等价于对参数w引入拉普拉斯先验，可以做variable selection。

LR原理
LR是一中常见的用于分类的模型，本质上还是一个线性回归，先把特征线性组合，然后使用sigmoid函数（单调可微）将结果约束到0~1之间，结果用于二分类或者回归预测。

模型参数估计
最大似然估计法估计模型参数，使用梯度下降或者拟牛顿法进行学习。
损失函数
最小化交叉熵误差，等价于最大似然估计
解决非线性分类问题
加核函数或特征变换，显式地把特征映射到高维空间。

SVM原理
一个样本集线性可分的时候，存在无穷个可以将两类数据正确分开，而SVM是通过最大化间隔来选择分类超平面，最大化这个间隔可以构造成一个约束最优化问题，这是一个凸二次规划问题，然后使用拉格朗日乘子法把约束优化问题转为无约束优化问题，令各个变量偏导为0代入拉格朗日函数得到它的对偶问题，最后用SMO算法来求解这个对偶问题。

解对偶问题的好处
一是对偶问题更好解，因为原问题是凸二次规划问题，对偶问题那里只需要求解alpha系数，而alpha系数只有支持向量才非0（KKT条件）。二是自然引入核函数，进而推广到非线性问题。
软间隔
当数据近似线性可分时，可以引入松弛变量，使间隔加上松弛变量大于等于1，针对每一个松弛变量都有一个惩罚。
核技巧
用一个变换把数据从原空间映射到新空间，数据在新空间是线性可分的。由于新空间有可能非常高维甚至无限维，难以计算且难以表示，所以不显式的定义该映射函数，而是定义一个函数把两个样本直接映射到他们在新空间的内积，因为求解对偶问题时只需要用到内积。常用核函数有高斯核、多项式核、线性核、拉普拉斯核、sigmoid核。
核函数的选择
根据专家先验知识，或采用交叉验证，试用不同的核函数（线性核，多项式核和径向基核函数）。

LR与SVM的异同

相同之处
如果不考虑核函数，LR和SVM都是线性分类器，都是监督算法，都是判别模型。
不同之处
- 损失函数不同，LR使用logistical loss（交叉熵），SVM使用hingeloss，SVM的损失函数自带正则项，而LR则需要自己添加正则项。
- 解决非线性问题时，SVM采用核函数机制，而LR一般不用，因为复杂核函数需要很大计算量，SVM中只有支持向量参与计算，而LR是全部样本都需要参与计算，若使用核函数计算量太大。
- 对异常值的敏感度不一样。LR中所有样本都对分类平面有影响，所以异常点的影响会被掩盖。但SVM的分类平面取决于支持向量，如果支持向量受到异常值影响，则结果难以预测。
- 在高维空间LR的表现比SVM更稳定，因为SVM是要最大化间隔，这个间隔依赖与距离测度，在高维空间时这个距离测度往往不太好。（所以需要做归一化）

分类任务常用的目标函数
交叉熵误差，hinge loss等。

相对熵
也称KL散度，相对熵可以用来衡量两个概率分布之间的差异。
交叉熵
可以用来计算学习模型分布与训练分布之间的差异，交叉熵损失通常适用于Softmax 分类器。最小化相对熵（KL散度）等价于最小化交叉熵，也等价于最大化似然估计。
Hinge loss（折页损失函数）
在二分类情况下，公式如下：L(y) =max(0 , 1–t*y)，其中，y是预测值(-1到1之间)，t为目标值(1或 -1)。其含义为，y的值在 -1到1之间即可，并不鼓励|y|>1，即让某个样本能够正确分类就可以了，不鼓励分类器过度自信，当样本与分割线的距离超过1时并不会有任何奖励。目的在于使分类器更专注于整体的分类误差。

LR逻辑回归为什么对特征进行离散化

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

正则项

结构风险最小化
即正则化。在经验风险最小化基础上加上正则项，惩罚复杂的模型。结构风险小同时需要经验风险小和模型简单，如贝叶斯估计中的最大后验概率估计。
经验风险最小化
即误差函数最小，样本数量大时，经验风险最小化学习效果好，如极大似然估计。样本少时会出现过拟合。
范数
其非负性使得它天然适合作为机器学习的正则项。
- L1范数：向量中各个元素绝对值之和。
- L2范数：向量中各个元素平方和的开二次方根。
- Lp范数：向量中各个元素绝对值的p次方和的开p次方根。
L1正则
项目标函数中增加所有权重w参数的绝对值之和, 逼迫更多w为零(也就是变稀疏. L2因为其导数也趋0, 奔向零的速度不如L1给力了)，倾向于使参数稀疏化；
L2正则项
倾向于使参数稠密地接近于0，目标函数中增加所有权重w参数的平方之和, 逼迫所有w尽可能趋向零但不为零。

决策树
概念：决策树一种基本的分类和回归方法，呈树形结构，表示基于特征对实例进行分类的过程。决策树的学习过程包括三个步骤：特征选择、决策树的生成以及决策树的修剪（预剪枝和后剪枝）。特征选择的准则是信息增益或者信息增益比（基尼系数）。

ID3生成算法
从根节点开始，对结点结算所有可能的特征的信息增益，选择信息增益最大的特征作为结点特征，然后对子节点递归的调用这个方法，构建决策树。信息增益偏向于选择取值较多的特征，容易过拟合。
C4.5生成算法
与ID3算法相似，用信息增益率（偏好可取值数目较少）来选择特征。小技巧：先找出信息增益高于平均水平的属性，再从中选择增益率最高的。
CART生成算法
全称分类树与回归树，可用于分类也可用于回归。分类树用基尼系数（越小越好）进行特征选择，用最小二乘回归树生成算法生成回归树（结点下所有点的均值作为该结点的预测值）。
基尼指数
反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此基尼指数越小，则数据集的纯度越高。
决策树的剪枝
通过极小化决策树整体的损失函数来进行剪枝。从树的叶节点开始向上回缩，假设回缩前树为Ta，回缩到父节点后树为Tb，计算两棵树的损失函数，如果回缩后损失函数变小，则剪枝，把父节点设为叶节点，这样迭代。

随机森林（样本随机性和特征随机性）

原理
由很多棵决策树组成，每棵决策树之间没有关联。每棵树的生成方法是，随机而且有放回地（如果没有放回那就每棵树都训练集完全不相交，太片面）从训练集选取N个（训练集大小为N）训练样本作为训练集，所以每棵树训练集都不一样，但包含重复样本，生成决策树选择特征时，从特征子集里面选择最优的特征用于分裂。得到森林后，输入样本让每棵决策树进行判断，输出结果为被最多决策树选择的分类。
与Bagging区别
与Bagging不一样的是会抽取与样本数目同样大小的样本来训练（Bagging一般少于n），且只用部分特征得到分类器（Bagging用全部特征）。
森林中任意两棵树的相关性
相关性越大，错误率越大。
森林中每棵树的分类能力
每棵树的分类能力越强，整个森林的错误率越低。
随机森林唯一的一个参数
特征个数m，减小m会降低树的相关性和分类能力，增加m两者也会随之增大。

集成学习

Bagging
对原数据有放回抽取，构建出多个样本数据集，训练出多个分类器。
Boosting
使用全部样本(可调权重)依次训练每个学习器, 迭代集成(平滑加权)。通过改变样本分布，对容易错分的数据加强学习，增加错分样本数据的权重。
两者区别：
- 样本选择不同
  Bagging是有放回地抽取数据集，每轮训练集是独立的。而Boosting每一轮的训练集不变，但是训练集中每个样本的权重会发生变化，根据上一轮分类结果调整。
- 样本权重不同
  Bagging每个样本权重相等，Boosting根据错误率不断调整样本的权重，被错分的样本权重会增加。
- 生成方式不同
  Bagging各个分类器可以并行生成，而Boosting只能顺序生成。
- 优化目标有差异
  Bagging减小的是方差，Boosting减小的是偏差。Bagging减小方差是因为对多个用不同训练集得到的分类器取了平均（取平均比单一的方差要小）。Boosting减小偏差是因为每次迭代都在之前误差的基础上进一步降低错误率，所以就是减小偏差，对于训练集的拟合程度好。

Boosting方法

AdaBoost
初始化样本权重，每个样本最开始的权重一样。训练弱分类器，若样本在这次训练中被正确分类，则降低它的权重，反之增加。这样多次训练得到多个弱分类器组成一个强分类器，误差率小的弱分类器拥有更大的权重。
提升树
提升树是迭代多棵回归树来共同决策，当采用平方误差函数，每一棵回归树学习的是之前所有树的结论和残差，拟合得到一个当前的残差回归树，最后累加所有树的结果作为最终结果。
- GBDT
  梯度提升树。利用损失函数的负梯度在当前模型的值作为提升树算法的残差的近似值。因为当损失函数不是平方误差时，残差不是简单的真实值减去预测值，把目标函数对当前模型求梯度，就可以得到模型改进的方向，负梯度就可以近似成残差。
- XGBoost
  基于C++通过多线程实现了回归树的并行构建，并在原有GBDT基础上加以改进，在目标函数增加了正则化项，正则项里包括了树的叶子结点个数、每个叶子结点上输出分数的L2模的平方和，且对目标函数做了二阶泰勒展开，从而极大提升了模型的训练速度和预测精度。

XGBoost为什么要泰勒展开
二阶导数有利于梯度下降更快更准，使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算。简短来说，就是为了统一损失函数求导的形式以支持自定义损失函数。
GBDT和XGBoost的区别

基分类器的选择：GBDT以CART做基分类器，XGBoost还支持线性分类器。
GBDT在优化时只用到了一阶导数信息，XGBoost对目标函数进行了二阶泰勒展开，同时用到一阶和二阶导数。
XGBoost在目标函数里加入了正则项，控制模型的复杂度。
XGBoost可以为缺失值或者指定的值指定分支的默认方向，对特征值有缺失的样本可以自动学习出他的分裂方向。
XGBoost支持并行，可以在特征粒度上并行，在训练前对特征进行分块排序，在寻找最佳分裂点的时候可以并行化计算，大大提升速度。

RF和GBDT的区别

相同点
都是由多棵树组成，最终的结果都是由多棵树一起决定。
不同点
- 组成随机森林的树可以分类树也可以是回归树，而GBDT只由回归树组成；
- 组成随机森林的树可以并行生成，而GBDT是串行生成；
- 随机森林的结果是多棵树投票表决的，而GBDT则是多棵树累加之和；
- 随机森林对异常值不敏感，而GBDT对异常值比较敏感；
- 随机森林是减少模型的方差，而GBDT是减少模型的偏差；

XGBoost和LightGBM的区别

XGBoost采用的是level-wise的分裂策略，而lightGBM采用了leaf-wise的策略，区别是XGBoost对每一层所有节点做无差别分裂，可能有些节点的增益非常小，对结果影响不大，但是XGBoost也进行了分裂，带来了务必要的开销。 leaft-wise的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂，如此递归进行，很明显leaf-wise这种做法容易过拟合，因为容易陷入比较高的深度中，因此需要对最大深度做限制，从而避免过拟合。
LightGBM使用了基于histogram的决策树算法，这一点不同与XGBoost中的exact算法，histogram算法在内存和计算代价上都有不小优势。

EM算法

定义：在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐性变量。
方法：最大期望算法经过两个步骤交替进行计算：第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。

归一化处理

标准化：把特征值变为均值0，方差1
归一化：把每个特征向量的值放缩到相同数值范围，如[0,1]
归一化的作用
- 加快梯度下降求最优解的速度。因为若两个特征的值区间相差大，数据会呈扁长形，梯度下降很可能会走之字形路线（垂直等高线走）。
- 可能提高精度。有些分类器依赖于计算样本之间的距离，而区间大特征值对距离影响会更大，但若区间小的特征值才是真正重要的特征，则容易被忽略。
哪些机器学习算法需要归一化
利用梯度下降法求解的模型一般需要归一化，如线性回归、LR、SVM、KNN、神经网络等。树形模型一般不需要归一化，因为他们不关心变量的值（数值缩放不影响分裂位置），而是关心变量的分布，如决策树、随机森林。

如何进行特征选择

特征选择是一个重要的数据预处理过程，主要有两个原因：一是减少特征数量、降维，使模型泛化能力更强，减少过拟合;二是增强对特征和特征值之间的理解.
常见的特征选择方式
- 去除方差较小的特征；
- 正则化：L1正则化能够生成稀疏的模型；L2正则化的表现更加稳定，由于有用的特征往往对应系数非零;
- 稳定性选择：在不同的数据子集和特征子集上运行特征选择算法，不断的重复，最终汇总特征选择结果。选择算法可以是回归、SVM或其他类似的方法。

样本不均匀

加权：不同类别分错的代价设为不同。
采样：上采样和下采样，上采样是把小众类复制多份，下采样是从大众类中选取部分样本。
- 上采样
  上采样会把小众样本复制多份，一个点会在高维空间中反复出现，这会导致一个问题，那就是运气好就能分对很多点，否则分错很多点。为了解决这一问题，可以在每次生成新数据点时加入轻微的随机扰动。
- 下采样
  因为下采样会丢失信息，为了减少信息的损失，第一种方法可以利用模型融合的方法（bagging）：多次下采样（放回采样，这样产生的训练集才相互独立）产生多个不同的训练集，进而训练多个不同的分类器，通过组合多个分类器的结果得到最终的结果。第二种方法利用增量训练的思想（Boosting）：先通过一次下采样产生训练集，训练一个分类器，对于那些分类正确的大众样本不放回，然后对这个更小的大众样本下采样产生训练集，训练第二个分类器，以此类推，最终组合所有分类器的结果得到最终结果。

模型评价指标

TP：正类预测为正类
FN：正类预测为负类
FP：负类预测为正类
TN：负类预测为负类
精确率：预测为正的样本当中有多少预测正确了，P = TP/(TP+FP)
召回率：真正为正的样本当中有多少被预测，R = TP/(TP+FN)
F1值: 综合考虑了精确率和召回率，2/F1 = 1/R + 1/P
ROC：横轴是假阳性，FPR=FP/(FP+TN)，真实的反例中，预测为正例的比例；纵轴是真阳性，TPR=TP/(TP+FN)，真实的正例中，预测为正例的比例；绘制方法：假设已有一系列样本被分为正类的概率，按概率值从大到小排序，依次将该概率值作为阈值来预测分类，每个阈值都对应一对FPR、TPR，这样一来就能绘制出曲线。
AUC：ROC曲线的面积，AUC大的分类器效果更好。

常用计算距离的方法

欧氏距离：将样本的不同属性之间的差别等同对待，但实际上可能有些属性更重要。适用于各分量的度量标准统一的情况。
曼哈顿距离：两个点在标准坐标系上的绝对轴距之和。计算速度快
切比雪夫距离：国王可以直行、横行、斜行，所以国王走一步可以移动到相邻8个方格中的任意一个。国王从格子(x1,y1)走到格子(x2,y2)最少需要的步数叫切比雪夫距离。

聚类
常用方法有：层次的方法（hierarchical method）、划分方法（partitioning method）、基于密度的方法（density-based method）、基于网格的方法（grid-based method）、基于模型的方法（model-based method）等。

经典K-means（划分）算法流程
1. 随机地选择k个对象，每个对象初始地代表了一个簇的中心；
2. 对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；
3. 重新计算每个簇的平均值，更新为新的簇中心；
4. 不断重复ii、iii，直到准则函数收敛。
K个初始类簇点的选取还有两种方法
- 选择彼此距离尽可能远的K个点；
- 先对数据用层次聚类算法进行聚类，得到K个簇之后，从每个类簇中选择一个点，该点可以是该类簇的中心点，或者是距离类簇中心点最近的那个点。
K值的选择
轮廓系数，求出所有样本的轮廓系数后再求平均值就得到了平均轮廓系数。平均轮廓系数的取值范围为[-1,1]，且簇内样本的距离越近，簇间样本距离越远，平均轮廓系数越大，聚类效果越好。那么，很自然地，平均轮廓系数最大的k便是最佳聚类数。
经典DBSCAN算法流程
1. DBSCAN通过检查数据集中每点的Eps邻域来搜索簇，如果点p的Eps邻域包含的点多于MinPts个，则创建一个以p为核心对象的簇；
2. 然后，DBSCAN迭代地聚集从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并；
3. 当没有新的点添加到任何簇时，该过程结束。
K-means与DBSCAN对比
和传统的K-Means算法相比，DBSCAN最大的不同就是不需要输入类别数k，当然它最大的优势是可以发现任意形状的聚类簇，而不是像K-Means，一般仅仅使用于凸的样本集聚类。同时它在聚类的同时还可以找出异常点
DBSCAN的主要优点有
- 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集；
- 可以在聚类的同时发现异常点，对数据集中的异常点不敏感；
- 聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。
DBSCAN的主要缺点有
- 如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合；
- 如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进；
- 调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵϵ，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。