机器学习面试八股4
51 随机森林 RF
通过对训练数据样本以及属性进行有放回的抽样（针对某一个属性随机选择样本）这里有
两种，一种是每次都是有放回的采样，有些样本是重复的，组成和原始数据集样本个数一
样的数据集；另外一种是不放回的抽样，抽取出大约 60%的训练信息。由此生成一颗 CART
树，剩下的样本信息作为袋外数据，用来当作验证集计算袋外误差测试模型；把抽取出的
样本信息再放回到原数据集中，再重新抽取一组训练信息，再以此训练数据集生成一颗
CART 树。这样依次生成多颗 CART 树，多颗树组成森林，并且他们的生成都是通过随机采
样的训练数据生成，因此叫随机森林。RF 可以用于数据的回归，也可以用于数据的分类。
回归时是由多颗树的预测结果求均值；分类是由多棵树的预测结果进行投票。正式由于它
的随机性，RF 有极强的防止过拟合的特性。由于他是由 CART 组成，因此它的训练数据不
需要进行归一化，因为每课的建立过程都是通过选择一个能最好的对数据样本进行选择的
属性来建立分叉，因此有以上好处的同时也带来了一个缺点，那就是忽略了属性与属性之
间的关系。
52KMeans 讲讲，KMeans 有什么缺点，K 怎么确定
1 初始化常数 K，随机选取初始点为质心
2 计算样本与每个质心之间的相似度，将样本归类到最相似的类中
3 重新计算质心
4 重复计算一下过程，直到质心不再改变
5 输出最终的质心以及每个类
k-means 存在缺点：
1）k-means 是局部最优的，容易受到初始质心的影响；比如在下图中，因选择初始质心不
恰当而造成次优的聚类结果。
2）同时，k 值的选取也会直接影响聚类结果，最优聚类的 k 值应与样本数据本身的结构信
息相吻合，而这种结构信息是很难去掌握，因此选取最优 k 值是非常困难的。
3）由于每次都要计算所有的样本与每一个质心之间的相似度，故在大规模的数据集上，K-
Means 算法的收敛速度比较慢。
K 值得确定：
法 1：通过枚举，令 k 从 2 到一个固定值如 10，在每个 k 值上重复运行数次 kmeans(避免局
部最优解)，并计算当前 k 的平均轮廓系数，最后选取轮廓系数最大的值对应的 k 作为最终
的集群数目。
时间复杂度：O(N)
轮廓系数取值范围为[-1,1]，取值越接近 1 则说明聚类性能越好，相反，取值越接近-1 则说
明聚类性能越差。
轮廓系数不应该用来评估不同聚类算法之间的优劣，比如 Kmeans 聚类结果与 DBSCAN 聚类
结果之间的比较。缺点：不适合基高密度的聚类算法 DBSCAN
53DBSCAN 原理和算法伪代码，与 kmeans，OPTICS 区别
DBSCAN 聚类算法原理
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚类算法，它是一种基
于高密度连通区域的、基于密度的聚类算法，能够将具有足够高密度的区域划分为簇，并
在具有噪声的数据中发现任意形状的簇。我们总结一下 DBSCAN 聚类算法原理的基本要点：
https://blog.csdn.net/hansome_hong/article/details/107596543
DBSCAN 算法是一种基于密度的聚类算法：
1.聚类的时候不需要预先指定簇的个数
2.最终的簇的个数不确定
2 个算法参数：邻域半径 R 和最少点数目 minpoints
DBSCAN 算法将数据点分为三类：
1.核心点：在半径 Eps 内含有超过 MinPts 数目的点。
2.边界点：在半径 Eps 内点的数量小于 MinPts,但是落在核心点的邻域内的点。
3.噪音点：既不是核心点也不是边界点的点
4 种点的关系：密度直达，密度可达，密度相连，非密度相连
在这里插入图片描述
，而 DBSCAN 的时间复杂度是 O(m^2)，
3．K 均值一般聚类所有对象，而 DBSCAN 丢弃被它识别为噪声的对象。
4.K 均值使用簇的基于原型的概念，而 DBSCAN 使用基于密度的概念
5.K 均值很难处理非球形的簇和不同大小的簇。DBSCAN 可以处理不同大小或形状的簇，并
且不太受噪声和离群点的影响
6. 基本 K 均值算法等价于一种统计聚类方法（混合模型），假定所有的簇都来自球形高斯
分布，具有不同的均值，但具有相同的协方差矩阵。DBSCAN 不对数据的分布做任何假定
7. K 均值可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是 DBSCAN 会合并有重
叠的簇。
OPTICS：链接
DBSCAN 算法中，有两个初始参数 Eps（邻域半径）和 minPts(Eps 邻域最小点数)需要手动设
置，并且聚类的结果对这两个参数的取值非常敏感，不同的取值将产生不同的聚类结果。
为了克服 DBSCAN 算法这一缺点，提出了 OPTICS 算法，该算法可以让算法对半径 Eps 不再
敏感。只要确定 minPts 的值，半径 Eps 的轻微变化，并不会影响聚类结果
2 个新的定义：
核心距离：一个对象 p 的核心距离是使得其成为核心点的最小半径，如果 p 不是核心点，
其可达距离没有定义。
可达距离：对于核心点 x 的邻点 x1、x2、…xn 而言，如果他们到点 x 的距离大于点 x’的核
心距离，则其可达距离为该点到点 x 的实际距离；如果他们到点 x 的距离核心距离小于点
x’的核心距离的话，则其可达距离就是点 x 的核心距离，
54OPTICS 算法描述
输入：样本集 D, 邻域半径 ε, 给定点在 ε 领域内成为核心对象的最小领域点数 MinPts
输出：具有可达距离信息的样本点输出排序
55 层次聚类两种方式
层次聚类：
层次聚类就是一层一层的进行聚类，可以由上向下把大的类别（ cluster）分割，叫作分裂
法；也可以由下向上对小的类别进行聚合，叫作凝聚法；但是一般用的比较多的是由下向
上的凝聚方法
1、分裂法：
分裂法指的是初始时将所有的样本归为一个类簇，然后依据某种准则进行逐渐的分裂
直到达到某种条件或者达到设定的分类数目。用算法描述：
输入：样本集合 D，聚类数目或者某个条件（一般是样本距离的阈值，这样就可不设
置聚类数目）
输出：聚类结果
1.将样本集中的所有的样本归为一个类簇；
repeat：
2.在同一个类簇（计为 c）中计算两两样本之间的距离，找出距离最远的两个样本 a,b；
3.将样本 a，b 分配到不同的类簇 c1 和 c2 中；
4.计算原类簇（c）中剩余的其他样本点和 a，b 的距离，若是 dis(a)<dis(b)，则将样本点归
到 c1 中，否则归到 c2 中；
util： 达到聚类的数目或者达到设定的条件
2、凝聚法：
凝聚法指的是初始时将每个样本点当做一个类簇，所以原始类簇的大小等于样本点的个数
然后依据某种准则合并这些初始的类簇，直到达到某种条件或者达到设定的分类数目。用
算法描述：
输入：样本集合 D，聚类数目或者某个条件（一般是样本距离的阈值，这样就可不设置聚
类数目）
输出：聚类结果
1.将样本集中的所有的样本点都当做一个独立的类簇；
repeat：
2.计算两两类簇之间的距离（后边会做介绍），找到距离最小的两个类簇 c1 和 c2；
3.合并类簇 c1 和 c2 为一个类簇；
util： 达到聚类的数目或者达到设定的条件
56bagging 和 boosting 的区别
Bagging 是从训练集中进行子抽样组成每个基模型所需要的子训练集,然后对所有基模型预
测的结果进行综合操作产生最终的预测结果。
Boosting 中基模型按次序进行训练,而基模型的训练集按照某种策略每次都进行一定的转化 ,
最后以一定的方式将基分类器组合成一个强分类器。
1）样本选择上：Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训
练集之间是独立的。Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的
权重发生变化。而权值是根据上一轮的分类结果进行调整。
2）样例权重：Bagging：使用均匀取样，每个样例的权重相等。Boosting：根据错误率不断
调整样例的权值，错误率越大则权重越大。
3）预测函数：Bagging：所有预测函数的权重相等。Boosting：每个弱分类器都有相应的权
重，对于分类误差小的分类器会有更大的权重。
4）并行计算：Bagging：各个预测函数可以并行生成。Boosting：各个预测函数只能顺序生
成，因为后一个模型参数需要前一轮模型的结果。
5)Bagging 中的基模型为强模型,Boosting 中的基模型为弱模型。
57XGBOOST 和 GDBT 的区别
GDBT 在函数空间中利用梯度下降法进行优化而 XGBoost 在函数空间中使用了牛顿法进行优
化。即 GDBT 在优化中使用了一阶导数信息,而 XGB 对损失函数进行了二阶泰勒展开,用到了
一阶和二阶倒数信息。
XGB 在损失函数中加入了正则项(树叶子节点个数,每个叶子节点上输出 score 的 L2 模平方和。
对于缺失的样本,XGB 可以自动学习出它的分裂方向。
GDBT 的节点分裂方式使用的是 gini 系数,XGB 通过优化推导出分裂前后的增益来选择分裂节
点。
XGB 在处理每个特征列时可以做到并行。
58GDBT 的原理,以及常用的调参参数
先用一个初始值去学习一棵树,然后在叶子处得到预测值以及预测后的残差,之后的树则基于
之前树的残差不断的拟合得到,从而训练出一系列的树作为模型。
n_estimators 基学习器的最大迭代次数,
learning_rate 学习率，
max_lead_nodes 最大叶子节点数,
max_depth 树的最大深度
min_samples_leaf 叶子节点上最少样本数。
59stacking 和 blending 的区别?
Stacking 和 blending 的区别在于数据的划分,blending 用不相交的数据训练不同的基模型,并
将其输出取加权平均。而 stacking 是将数据集划分为两个不相交的集合,在第一个集合的数
据集中训练多个模型,在第二个数据集中测试这些模型,将预测结果作为输入,将正确的标签
作为输出,再训练一个高层的模型。
60AdaBoost 和 GBDT 的区别,
AdaBoost 通过调整错分的数据点的权重来改进模型,而 GBDT 是从负梯度的方向去拟合改进
模型
AdaBoost 改变了训练数据的权值,即样本的概率分布,减少上一轮被正确分类的样本权值,提
高被错误分类的样本权值,而随机森林在训练每棵树的时候,随机挑选部分训练集进行训练。
在对新数据进行预测时,AdaBoost 中所有树加权投票进行预测,每棵树的权重和错误率有关,
而随机森林对所有树的结果按照少数服从多数的原则进行预测。
随机森林，它属于 Bagging 类的算法。使用随机森林解决回归问题，只需要将所有回归决
策树的预测值取平均即可。Boosting 类算法在解决回归问题时，只需要将个体学习器的预
测值加权求和即可
61gbdt 推导
链接
是一种基于 boosting 集成学习思想的加法模型，是一种用于回归的机器学习算法，该算法
由多棵回归决策树组成，所有树的结论累加起来做最终答案。训练时采用前向分布算法进
行贪婪的学习，每次迭代都学习一棵 CART 树来拟合之前 t-1 棵树的预测结果与训练样本真
实值的残差。GBDT 中的决策树是个弱模型，深度较小一般不会超过 5，叶子节点的数量也
不会超过 10，
GBDT:应用：：：二分类，多分类，特征组合，所有回归问题
GBDT 和随机森林的相同点：
1）都是由多棵树组成；2）最终的结果都是由多棵树一起决定
GBDT 和随机森林的不同点
随机森林对异常值不敏感，GBDT 对异常值非常敏感；
随机森林对训练集一视同仁，GBDT 是基于权值的弱分类器的集成；
随机森林是通过减少模型方差提高性能，GBDT 是通过减少模型偏差提高性能
决策树模型的优点如下。
1）容易理解和解释，树可以被可视化。2）不需要太多的数据预处理工作，即不需要进行
数据归一化，创造哑变量等操作。3）隐含地创造了多个联合特征，并能够解决非线性问题
62xgboost 的特征重要性计算
特征重要性可以用来做模型可解释性 xgboost 实现中 Booster 类 get_score 方法输出特征重要
性，其中 importance_type 参数支持三种特征重要性的计算方法：
1.importance_type=weight（默认值），特征重要性使用特征在所有树中作为划分属性的次
数。
2.importance_type=gain，特征重要性使用特征在作为划分属性时 loss 平均的降低量。
3.importance_type=cover，特征重要性使用特征在作为划分属性时对样本的覆盖度
63xgboost 原理，怎么防过拟合
XGBoost 属于加法模型，其基函数为回归决策树；
XGBoost 的目标函数为损失函数+正则化项，且损失函数使用了二阶泰勒展开；
XGBoost 使用前向分步算法，通过最小化目标函数来进行模型的优化与学习。
在 xgboost 调中，一般有两种方式用于控制过拟合：1）直接控制参数的复杂度：包括
max_depth， min_child_weight， gamma；2）add randomness 来使得对训练对噪声鲁棒。
包括 subsample colsample_bytree，或者也可以减小步长 eta，但是需要增加 num_round，来
平衡步长因子的减小。
64xgboost，rf，lr 优缺点场景
xgb
优缺点：
1）在寻找最佳分割点时，考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低，
xgboost 实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候
选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
2）xgboost 考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认
方向，这能大大提升算法的效率，paper 提到 50 倍。
3）特征列排序后以块的形式存储在内存中，在迭代中可以重复使用；虽然 boosting 算法迭
代必须串行，但是在处理每个特征列时可以做到并行。
4）按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存
的不连续访问，严重时会导致 cache miss，降低算法效率。paper 中提到，可先将数据收集
到线程内部的 buffer，然后再计算，提高算法的效率。
5）xgboost 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线
程、数据压缩、分片的方法，尽可能的提高算法的效率。
适用场景：分类回归问题都可以。
Rf：
优点：
2）随机森林能处理很高维度的数据（也就是很多特征的数据），并且不用做特征选择。
3）在训练完之后，随机森林能给出哪些特征比较重要。
4）训练速度快，容易做成并行化方法(训练时，树与树之间是相互独立的)。5）在训练过
程中，能够检测到 feature 之间的影响。
6）对于不平衡数据集来说，随机森林可以平衡误差。当存在分类不平衡的情况时，随机森
林能提供平衡数据集误差的有效方法。
7）如果有很大一部分的特征遗失，用 RF 算法仍然可以维持准确度。
8）随机森林算法有很强的抗干扰能力（具体体现在 6,7 点）。所以当数据存在大量的数据
缺失，用 RF 也是不错的。
9）随机森林抗过拟合能力比较强（虽然理论上说随机森林不会产生过拟合现象，但是在现
实中噪声是不能忽略的，增加树虽然能够减小过拟合，但没有办法完全消除过拟合，无论
怎么增加树都不行，再说树的数目也不可能无限增加的）。
10）随机森林能够解决分类与回归两种类型的问题，并在这两方面都有相当好的估计表现 。
（虽然 RF 能做回归问题，但通常都用 RF 来解决分类问题）。11）在创建随机森林时候，
对 generlization error(泛化误差)使用的是无偏估计模型，泛化能力强。
缺点：1）随机森林在解决回归问题时，并没有像它在分类中表现的那么好，这是因为它并
不能给出一个连续的输出。当进行回归时，随机森林不能够做出超越训练集数据范围的预
测，这可能导致在某些特定噪声的数据进行建模时出现过度拟合。2）对于许多统计建模者
来说，随机森林给人的感觉就像一个黑盒子，你无法控制模型内部的运行。只能在不同的
参数和随机种子之间进行尝试。4）对于小数据或者低维数据（特征较少的数据），可能不
能产生很好的分类。（处理高维数据，处理特征遗失数据，处理不平衡数据是随机森林的
长处）。5）执行数据虽然比 boosting 等快（随机森林属于 bagging），但比单只决策树慢
多了。
适用场景：数据维度相对低（几十维），同时对准确性有较高要求时。因为不需要很多参
数调整就可以达到不错的效果，基本上不知道用什么方法的时候都可以先试一下随机森林。
Lr：
优点：实现简单，广泛的应用于工业问题上；
分类时计算量非常小，速度很快，存储资源低；
便利的观测样本概率分数；
缺点：当特征空间很大时，逻辑回归的性能不是很好；容易欠拟合，一般准确度不太高
不能很好地处理大量多类特征或变量；只能处理两分类问题（在此基础上衍生出来的
softmax 可以用于多分类），且必须线性可分；对于非线性特征，需要进行转换。
适用场景：LR 同样是很多分类算法的基础组件，它的好处是输出值自然地落在 0 到 1 之间，
并且有概率意义。因为它本质上是一个线性的分类器，所以处理不好特征之间相关的情况
虽然效果一般，却胜在模型清晰，背后的概率学经得住推敲。它拟合出来的参数就代表了
每一个特征(feature)对结果的影响。也是一个理解数据的好工具。
65xgboost 特征并行化怎么做的
决策树的学习最耗时的一个步骤就是对特征值进行排序,在进行节点分裂时需要计算每个特
征的增益,最终选增益大的特征做分裂,各个特征的增益计算就可开启多线程进行。而且可以
采用并行化的近似直方图算法进行节点分裂。
66xgboost 和 lightgbm 的区别和适用场景
（1）xgboost 采用的是 level-wise 的分裂策略，而 lightGBM 采用了 leaf-wise 的策略，区别是
xgboost 对每一层所有节点做无差别分裂，可能有些节点的增益非常小，对结果影响不大，
但是 xgboost 也进行了分裂，带来了无必要的开销。 leaf-wise 的做法是在当前所有叶子节
点中选择分裂收益最大的节点进行分裂，如此递归进行，很明显 leaf-wise 这种做法容易过
拟合，因为容易陷入比较高的深度中，因此需要对最大深度做限制，从而避免过拟合。
（2）lightgbm 使用了基于 histogram 的决策树算法，这一点不同与 xgboost 中的 exact 算法，
histogram 算法在内存和计算代价上都有不小优势。1）内存上优势：很明显，直方图算法
的内存消耗为(#data* #features * 1Bytes)(因为对特征分桶后只需保存特征离散化之后的值)，
而 xgboost 的 exact 算法内存消耗为：(2 * #data * #features* 4Bytes)，因为 xgboost 既要保存
原始 feature 的值，也要保存这个值的顺序索引，这些值需要 32 位的浮点数来保存。2）计
算上的优势，预排序算法在选择好分裂特征计算分裂收益时需要遍历所有样本的特征值，
时间为(#data),而直方图算法只需要遍历桶就行了，时间为(#bin)
（3）直方图做差加速，一个子节点的直方图可以通过父节点的直方图减去兄弟节点的直方
图得到，从而加速计算。
（4）lightgbm 支持直接输入 categorical 的 feature，在对离散特征分裂时，每个取值都当作
一个桶，分裂时的增益算的是”是否属于某个 category“的 gain。类似于 one-hot 编码。
（5）xgboost 在每一层都动态构建直方图，因为 xgboost 的直方图算法不是针对某个特定的
feature，而是所有 feature 共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新
构建直方图，而 lightgbm 中对每个特征都有一个直方图，所以构建一次直方图就够了。
67HMM 隐马尔可夫模型的参数估计方法是？
期望最大化（Expectation-Maximum,EM）算法
68Bootstrap 方法是什么？
从一个数据集中有放回的抽取 N 次，每次抽 M 个。Bagging 算法基于 bootstrap。面试时结
合 Bagging 算法讲述会更好。
69 如何防止过拟合？
1.早停法；2.l1 和 l2 正则化；3.神经网络的 dropout；4.决策树剪枝；5.SVM 的松弛变量；6.
集成学习，扩增数据集,特征的筛选,
在训练和建立模型的时候，从相对简单的模型开始，不要一开始就把特征做的非常多，模
型参数跳的非常复杂。
70EM 算法推导
EM 算法是否一定收敛？EM 算法可以保证收敛到一个稳定点，即 EM 算法是一定收敛的。
————————————————