人工智能

算法工程师的面试题

Unemployed_Youth_Job_Hunting

Posted by 邬小达 on October 30, 2020

算法面试问题

问题1：不平衡的正负样本的处理方法

方法一，对正样本或者负样本抽样

  • 随机欠采样。从多类样本中随机抽取一部分样本
  • 随机过采样。从少类样本中随机重复抽取样本，添加到少类样本中
  • SMOTE算法也是一种过采样。对少类样本中的一个样本i，smote算法会从其最近的K个样本中随机选取一个样本j，然后再i，j的连线上随机选取一点作为新样本加入到少类样本中。

基本策略：再缩放。以线性分类器为例，通常y>0.5判为正例，否则反例。那么y/(1-y)则反映了正例与反例可能性之比。y/(1-y)>0.5，代表预测为正例。我们可以基于这个算式调整权重，比如y/(1-y)*（负样本数量/正样本数量）。再缩放的思想简单，但实际操作却不平凡。一般是基于原始数据集进行训练学习，当用训练好的分类器预测时，将上述调整策略嵌入到决策过程中，称为“阈值移动”。

方法二，从算法层面出发，增加小样本错分的惩罚代价，并将此代价直接体现在目标函数里，即代价敏感。如把正样本的权重调高，Focal Loss方法。

损失函数和代价函数是同一个东西，目标函数是一个与他们相关但更广的概念，对于目标函数来说在有约束条件下的最小化就是损失函数（loss function）。目标函数是最终需要优化的函数，其中包括经验损失和结构损失。经验损失(loss)就是传说中的损失函数或者代价函数。结构损失(Ω)就是正则项之类的来控制模型复杂程度的函数。

问题2：XGBoost的并行体现在哪里

首先它会把特征排序后以block的形式存储在内存中，在后面迭代重复使用这个结构。这个block使得并行化成为了可能。

其次，是特征并行。在节点分裂的时候，计算特征的信息增益，选择增益最大的那个特征去做分割，各个特征的计算不相互干扰，可以多线程进行（同层级节点可并行）。

问题3：XGBoost在怎么选择节点的，它是如何判断应该用年龄还是性别

使用贪心算法，遍历所有特征：

  • 对每个特征所有取值排序，计算增益值

  • 最终得到所有特征中的最好特征的最好分裂值

XGBoost所使用的分位点算法，其核心思想是根据特征的分布取其分位点（权重直方图的计算方法）

我们可以发现，当推导目标的时候，像计算叶子节点分数和分支这样的策略会自然地出现，而不再是利用启发式规则，比如基于gini进行分支，叶子节点采用平均值

比如CART的分支是这样的：首先计算所有特征的基尼指数，选择基尼指数最小的特征作为内部节点，然后基于这个特征的不同取值产生子节点。直到信息增益很小或者没有特征可以选择为止。需要注意的是CART是一颗二叉树，每一步都是将特征A分为两部分，分别进入左右子树。

问题4：对于逻辑回归而言，共线性会造成什么后果

共线性问题对于逻辑回归损失函数的最优化没影响，参数都是一样更新，一样更新到收敛为止。所以对于预测来说没什么影响。并且对于线性回归模型，最小二乘法仍为回归系数的线性无偏估计。

共线性会引起以下问题：

  • 模型参数估计不准确，有时甚至会出现回归系数的符号与实际情况完全相反的情况。

  • 本应该显著的自变量不显著。也就是说，无法从p-值的大小判断出变量是否显著

  • 多重共线性使参数估计值的方差增大，模型参数不稳定，也就是每次训练得到的权重系数差异都比较大。

判断存在多重共线性的方法：

  • 方差膨胀因子VIF
  • 增加、删除一个变量或者改变一个观测值，回归系数的估计值发生较大变化
  • 一些重要的自变量没有通过显著性检验
  • 自变量的回归系数与定性分析的结果相违背，应该为正却为负
  • 一些重要变量的回归系数的标准差较大

问题5：特征交叉有什么用处

像逻辑回归这种线性模型是无法学到非线性关系的。那么我们可以通过变量交叉的方法，让逻辑回归学到非线性。比如健康和身高、体重这两个变量有关系，我可以将身高和体重交叉。比如通过身高的分布图，分位数等方法来看身高的分布情况，将其分为三个不同的类别（高、矮、正常）。体重也是一样，分为三类。那么两两交叉就可以生成9个特征，然后也可以进行ont-hot转为0，1变量

问题6：线性模型和树模型的区别

树模型可以捕捉非线性关系，准确率更高，可以处理成百上千的特征。而线性模型容易解释，训练和预测的速度更快。但线性模型也有其缺点。首先线性模型无法捕捉变量之间的非线性关系，需要通过大量的特征工程（特征组合）来提高模型的效果。其次，在数据预处理阶段，需要进行大量的特征处理，如特征归一化、离散化等。

问题7：XGBoos会调哪些参数

  • eta 。学习速率或步长，eta通过缩减特征的权重使提升计算过程更加保守，可以防止过拟合。越大，迭代的速度越快。
  • num_boost_round。迭代次数
  • max_depth。树的最大深度
  • subsample 。随机抽样的比例。如果设置为0.8则意味着将随机的从整体样本中中抽取80%的子样本建立树模型，这能够防止过拟合
  • gamma。“复杂性控制”，控制叶子的生成数量。对梯度提升树影响最大的参数之一。设定越大，算法就越保守，树的叶子数量就越少，模型的复杂度就越低。
  • early stopping。
  • scale_pos_weight。在正负样本不平衡时，可以用的参数。设置为正值，可以使算法更快收敛
  • objective。一般使用逻辑回归的损失函数，对数损失，binary:logistic

调参的时候，先将某个参数调到合适的值，然后再调另一个参数。比如迭代次数要放在最后调，先设置为较小的值，可以快速收敛。

问题8：XGboost和LightGBM的区别

LightGBM是微软出的新的boosting框架，基本原理与XGBoost一样，只是在框架上做了一优化（重点在模型的训练速度的优化）。

  • 更快的训练速度

  • 更低的内存消耗

  • 更好的准确率

  • 分布式支持，可以快速处理海量数据

XGBoost在选择特征的分隔点时，需要遍历所有的特征值。Lightgbm改进了这一特征选择方式，使用的是histogram（直方图）的方式，而不是全部特征进行计算。 还支持真正的分布式，多台机器一起跑。

优点1：histogram 算法

直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图。在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点。

histogram 算法的缺点是由于特征被离散化，它不能找到很精确的分割点，训练误差没有 pre-sorted 好。但在不同的数据集上的结果表明，离散化的分割点对最终的精度影响并不是很大，甚至有时候会更好一点。原因是决策树本来就是弱模型，分割点是不是精确并不是太重要；较粗的分割点也有正则化的效果，可以有效地防止过拟合从实验结果来看，

优点2：它抛弃了大多数 GBDT 工具使用的按层生长(level-wise) 的决策树生长策略，而使用了带有深度限制的按叶子生长 (leaf-wise) 算法。

  • level-wise 过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，不容易过拟合。但实际上level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销。因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。
  • leaf-wise则是一种更为高效的策略，每次从当前所有叶子中，找到分裂增益最大(一般也是数据量最大)的一个叶子，然后分裂，如此循环。因此同 level-wise 相比，在分裂次数相同的情况下，leaf-wise 可以降低更多的误差，得到更好的精度。leaf-wise 的缺点是可能会长出比较深的决策树，产生过拟合。因此 LightGBM 在leaf-wise 之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

优点3： histogram 做差加速。一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。通常构造直方图，需要遍历该叶子上的所有数据，但直方图做差仅需遍历直方图的 k 个桶。利用这个方法，LightGBM 可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。

优点4：支持类别特征的输入，不需要进行One-Hot的0/1展开。

作者：柯国霖 链接：https://www.zhihu.com/question/51644470/answer/130946285

问题9：XGBoost有哪些缺点

XGBoost适用于高偏差，低方差的训练集，方差较大的数据和异常值会对模型造成一定的影响。而随机森林适用于高方差，低偏差的训练集。

在参数确定的情况下，XGBoost训练时间短。但如果需要调参的参数多，则总体耗时长。

问题10：常见聚类算法

K-均值聚类、高斯混合模型聚类、自组织映射神经网络（SOM）、层次聚类、基于密度聚类算法（DBSCAN）

问题11：为什么要进行标准化

不同特征之间的量纲不一致，比如交易价格是以元为单位，交易数量以手为单位，不同特征之间不可比。当标准化后，所有特征归一化到[0,1]，变为可比较了。

标准化的使用场景通常涉及到距离的计算，如聚类、KNN、SVM，还有是Lasso回归、岭回归和主成分分析。

像决策树、随机森林这类不需要进行标准化。因为节点的选择只关注当前特征自身的区间切分，而与特征之间的相对大小无关。

问题12：随机森林和XGBoost是如何计算变量重要性的

随机森林：变量X的重要性得分是通过在样本中随机打乱X的值，然后比较模型前后的out-of-bag error得出的。

XGBoost：有三种计算重要性的方法

  • weight，使用特征在所有树中作为划分属性的次数。

  • gain，使用特征在作为划分变量后的平均增益。

  • cover，使用特征在作为划分属性时对样本的覆盖度。

问题13：XGBoost如何填充缺失值

随机森林无法处理缺失数据，而XGBoost可以处理缺失数据。XGBoost把缺失值当做稀疏矩阵来对待。缺失值数据会被分到左子树和右子树分别计算损失，选择较优的那一个。如果训练中没有数据缺失，预测时出现了数据缺失，那么默认被分类到右子树。

问题14：Lasso回归和岭回归的区别

Lasso和岭回归在标准线性回归的基础上修改损失函数（经验损失+结构损失，修改的是结构损失）。Lasso使用L1正则，岭回归使用L2正则

L1：向量中各个元素绝对值的和。

L2：向量中各元素平方和求平方根。

Lasso和岭回归都是用来解决标准线性回归的过拟合问题。不同点：

  • L1比L2更容易获得稀疏解（参数为0）。在解空间上，L1正则是多边形，L2正则是圆形，多边形的解空间更容易在尖角处与等高线碰撞出稀疏解。

  • Lasso 可以用来做 feature selection，而岭回归不行
  • 从贝叶斯角度看，Lasso（L1 正则）等价于参数 w 的先验概率分布满足拉普拉斯分布，而岭回归（L2 正则）等价于参数 w 的先验概率分布满足高斯分布，而拉普拉斯分布使参数为0的可能性更大

机器学习指标

1.WOE

WOE的全称是“Weight of Evidence”，证据权重。

WOE表示的是某一类别正样本的比例与某一类别负样本比例的比值，再取对数。衡量的是该类别区分正负样本的能力。 \(Distribution1(i) = count(Y=1)(i)/ count(Y=1) (all)\)

\[Distribution0(i) = count(Y=0)(i)/ count(Y=0) (all)\] \[WOE = ln(Distribution1(i)/ Distribution0(i))\]

WOE可能为负，但其绝对值越大，对于分类贡献越大。

2.IV

IV的全称是Information Value，信息量。 \(IV(i) = (Distribution1(i)–Distribution0(i))*WOE\)

\[IV = ∑IV(i)\]

IV值衡量的是一个变量的预测能力。类似的指标还有信息增益、基尼系数等。

WOE可能为负值，IV值不可能为负。

3.Precision和Recall

precision，精确率。模型预测为正例的总样本里面，模型预测正确的多少比例。指标高，目的是挑出最有把握的。

recall，召回率。真实是正例的总样本里面，模型预测正确的有多少比例。指标高，目的是把所有是正例的都选上。

4.KS

KS：计算每个评分区间累计正样本占比与累计负样本占比差的绝对值（累计bad%-累计good%），然后对这些绝对值取最大值。

横坐标代表信用分，纵坐标代表比率。 两条曲线分别是TPR 和 FPR。

KS衡量的是正负样本群体累计分布的最大差异。KS越高，排序能力越强。

KS值的取值范围是[0，1]。通常来说，值越大，表明正负样本区分的程度越好。并非所有的情况KS都是越高越好的，尤其在征信模型中。

征信模型中，最期望得到的信用分数分布是正态分布，对于正负样本分别而言，也都期望是呈正态分布的样子。如果KS值过大，一般超过0.9，就可以认为正负样本分得过开了，不太可能是正态分布的，反而是比较极端化的分布状态（U字形，两边多，中间少），这样的分数就很不好，基本可以认为不可用。

KS值仅仅代表模型的区分正负样本的能力，不能表示区分得是否准确，即便好坏客户完全分错，KS值依然可以很高。

5.ROC和AUC

ROC曲线的横坐标为false positive rate（FPR）（假正确率）。

FPR：模型错认为正类的负实例占所有负实例的比例。

纵坐标为true positive rate（TPR）（真正确率），即召回率。

TPR：模型所识别出的正实例占所有正实例的比例。

ROC曲线将TPR和FPR画在一条曲线上，KS曲线则是将FPR和TPR画作两条曲线。

AUC考察的是算法在一般情况下的泛化能力。机器学习得到的是每个样本的概率预测值，在0-1之间。当把预测值与某个分类阈值进行比较，可以把大于阈值定义为1，小于阈值定义为0，这样就得到一个评价指标的值。通过改变不同的阈值可以得到一组评价指标的值。这组评价指标的期望可以认为是AUC。

AUC值就是ROC曲线下的面积值，而KS值就是KS曲线中两条曲线之间的最大间隔距离。

6.F1

\[F1 = （2*precision*recall）/（precision + recall）\]

7.PSI

PSI：描述群体稳定性指标，用于评价模型打分的稳定。 \(PSI = (actual\% - expected\%)ln(\frac {actual\%}{expected\%})\)

\[actual\%代表实际分布在某个打分区间上样本占总样本的比例\] \[expected\%代表在预期分布在某个打分区间上样本占总样本的比例\]

通常而言，以验证样本通常作为实际分布，训练样本作为预期分布。

模型

1.随机森林（Random Forest）：

是一种将弱学习器进行组合，从而提升为强学习器的一种算法。随机森林是包含多个决策树的分类器，根据每个决策树的分类结果投票来决定目标变量的分类。这样可以做到减小模型的方差，增加预测的准确性。（回归问题则使用分类之后的均值作为结果）。随机森林构建的两个重点是数据的随机性选取（有放回的抽样）以及变量的随机选取。

参数：n_estimators（树的棵树）、max_depth（树的最大生长深度）、min_samples_leaf（叶子的最小样本数量）、max_features（最大选择特征数）

优点

  • 准确率高、不会造成过拟合；
  • 不需要调一大堆参数；
  • 适合并行化处理，能处理高维度数据。

2.GBDT梯度提升决策树（Gradient Boost Decision Tree）：

是基于决策树的集成学习模型。Boost是”提升”的意思，每一次新的训练是基于上一颗树的残差（预测值与真实值的差值）作为优化目标，来生成新的树。

比如A的真实年龄是18岁，但第一棵树得出的预测结果是12岁，相差6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，假如训练完之后预测出来的结果为6，那么两棵树累加起来就是真实年龄了；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学习。

优点

  • 精度高、能处理非线性数据。

缺点

  • 并行复杂（因为上下两颗树有联系）

3. XGBoost

以决策树为基学习器的GB算法，但是扩展和改进了GBDT。相比GBDT的优点有：

  • XGBoost在代价函数里自带加入了正则项，用于控制模型的复杂度。
  • XGBoost在进行节点的分裂时，支持各个特征多线程进行增益计算，因此算法更快，准确率也相对高一些。
  • GBDT只支持CART作为基学习器，XGBoost还支持线性分类器作为基学习器。
  • 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。 二阶导数有利于梯度下降的更快更准。
  • 传统的GBDT在每轮迭代时使用全部的数据，而XGBoost则可以对数据进行抽样。
  • XGBoost允许在每一轮boosting迭代中使用交叉验证。因此，可以方便地获得最优boosting迭代次数。

4.Wide&Deep

Google在2016年提出的一类用于分类和回归的深度学习模型，目前在Google Play应用商店的推荐场景中有使用。Wide&Deep模型的核心思想是结合线性模型的记忆能力（Memorization）和DNN模型的泛化能力（Generalization），在训练过程中同时优化两个模型的参数，从而达到整体模型的预测能力最优。在销量预测任务中使用Wide&Deep模型，既可以加入传统特征工程，又可以把ID类特征引入模型中，在训练中自动学习Embedding，且受益于DNN类模型较强的拟合效果，达到更准确的预测效果。

5.朴素贝叶斯（Naive Bayes）

当你在街上看到一个黑人，你十有八九猜非洲。因为黑人中非洲人的比率最高，也就是说选择条件概率最大的类别，这就是朴素贝叶斯的思想基础。对于待分类的物体，计算在它出现的条件下各个目标类别Y出现的概率，哪个最大，就认为此物体属于哪个类别。

优点

  • 倘若条件独立性假设确实满足，朴素贝叶斯将会比逻辑回归收敛得更快，因此你只需要更少的训练数据；当条件独立性假设不成立时，朴素贝叶斯在实践中仍然有着不俗的表现。

缺点

  • 它学习不了特征间的交互关系

6.支持向量机（SVM）

希望通过一个超平面来对数据进行分类。比如对于两个特征形成的二维空间，可以通过一条直线来分类。进一步，对于n个特征形成的n维空间，可以通过核函数将原始数据映射到高维空间。在高维空间中，点与点之间更加分散，数据就能够线性分离。

优点

  • 在超高维的文本分类问题中特别受欢迎。可用于线性/非线性分类，也可以用于回归；低泛化误差。

缺点

  • 内存消耗大，难以解释，计算速度慢和调参复杂；
  • 对参数和核函数的选择比较敏感。

7.决策树（CART）

基于树的结构来对分类问题进行决策。树的分支就是每一个决策的结果，比如是否为本科学历，年龄的范围，最后到树的末端就是要预测的目标Y（对于数值型变量，最好的办法是预先做离散化处理。当然决策树中的C4.5也自带了离散化的策略，即二分法）。

优点

  • 计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征；
  • 它可以有效地处理特征间的交互关系并且是非参数化的，因此对异常值不敏感，数据不需要满足线性可分。

缺点

  • 单颗决策树分类能力弱，并且对连续值变量难以处理（数值变量必须离散化）;
  • 容易过拟合（后续出现了随机森林，减小了过拟合现象）;
  • 不支持在线学习，于是在新样本到来后，决策树需要全部重建。

8.KNN分类方法

简单的说就是当要了解一个人的收入时，只需要看他周围的人的平均收入是多少就行啦。用数学的方式表示就是把数据看成在多元空间中的点，先计算未知点与已知点之间的距离，将距离进行排序，找出与未知点距离最近的K个点，根据这K个点的类别投票来决定未知点的类别。

优点

  • 精度高、无数据输入假定，稳健性强，模型参数简单，可构成非线性决策边界。

缺点

  • 空间复杂度高，计算量大，对异常值和不平衡数据较为敏感。