机器学习算法岗：常见面试问题及解答整理，持续更新

妖狐艹你老母 2022-11-10 01:24 655阅读 0赞

### 机器学习算法岗：常见面试问题及解答整理，持续更新 ###

*   *  一、决策树ID3和C4.5的差别？各自优点？
     *   *  ID3算法：
         *  C4.5算法：
         *  差异：
     *  二、过拟合的原因及如何防止
     *  三、几种模型（ SVM，LR，GBDT，EM ）的原理以及公式推导
     *   *  1、SVM原理
         *  2、LR（线性回归）原理
         *  2.5、SVM与LR异同点
         *  3、GBDT原理
         *  4、EM（期望最大）原理
         *  5、XGBoost原理
         *  6、RF（随机森林）原理
     *  四、K-means 的原理，优缺点以及改进
     *  五、Bagging和Boosting
     *  To Be Continued。。。。。。

## 一、决策树ID3和C4.5的差别？各自优点？ ##

首先，要知道 ID3和C4.5 是什么，他们和CART算法都是决策树的启发方法。

> 注：CART利用基尼指数来划分训练子集。分类回归树 CART(Classification and Regression Trees)：二元划分(二叉树)。分类时度量指标为Gini指标(最小化基尼指数)、 Towing；回归问题时，度量指标以为最小平方残差。  
> 基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。

因为从所有可能的决策树中选取最优决策树，这是一个NP完全问题，很难在多项式时间内求解（或者根本不存在这样的解）。所以现实中决策树学习算法采用启发式方法，近似求解这一最优化问题。所谓的启发式方法就是递归的选择最优特征，并根据该特征对训练数据进行分割。

### ID3算法： ###

利用信息增益进行特征的选择，信息增益反映的是给定条件后不确定性减少的程度。每一次对决策树进行分叉选取属性的时候，我们会选取信息增益最高的属性来作为分裂属性，只有这样，决策树的不纯度才会降低的越快。

缺点：信息增益偏向取值较多的特征

原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较 偏向取值较多的特征。  
所以要用到下面的信息增益比。

### C4.5算法： ###

C4.5算法与ID3相似，局部进行了改进，C4.5算法在决策树生成的过程中，用信息增益比来选择特征。

信息增益比：信息增益比 = 惩罚参数 \* 信息增益

信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。

缺点：信息增益比偏向取值较少的特征  
原因： 当特征取值较少时HA(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。

使用信息增益比：基于以上缺点，并不是直接选择信息增益率最大的特征，而是先在候选特征中找出 **信息增益** 高于平均水平的特征，然后在这些特征中再选择 **信息增益率** 最高的特征。

### 差异： ###

ID3算法利用信息增益进行特征的选择，信息增益反映的是给定条件后不确定性减少的程度，特征取值越多就以为这确定性更高，所以这种方法存在优先选择取值较多的特征的趋势，泛化性差。

C4.5算法利用信息增益比进行特征的选择，一定程度上对取值较多的特征进行惩罚，但存在优先选择取值较少的特征的趋势。

ID3只能处理离散型变量，另外两种都可以处理连续性变量。C4.5处理连续变量时，通过对数据排序之后找到类别不同的分割线作为切分点，根据切分点把连续属性转为布尔型，从而将连续性变量转换多个取值空间的离散型变脸。CART由于其构建时都会对特征进行二值划分也就是二值切割法，因此可以很好的适用于连续型变量。

ID3和C4.5可以在每个节点上产生出多叉分支，且每个特征在层级之间不会复用，而CART每个节点只会产生两个分支因此最后会形成一棵二叉树，且每个特征可以被重复使用。

ID3和C4.5通过剪枝来权衡树的准确性和泛化能力，CART直接利用全部数据发现所有可能的树结构进行对比。

ID3和C4.5只能用于分类，CART也可以用于回归（回归树使用最小平方误差准则）。

## 二、过拟合的原因及如何防止 ##

以决策树为例：

对于过拟合现象产生的**原因**，有以下几个方面，

第一：在决策树构建的过程中，对决策树的生长没有进行合理的限制（剪枝）；  
第二：在建模过程中使用了较多的输出变量，变量较多也容易产生过拟合；  
第三：样本中有一些噪声数据，噪声数据对决策树的构建的干扰很多，没有对噪声数据进行有效的剔除。

对于过拟合现象的**预防**措施，有以下一些方法，

第一：选择合理的参数进行剪枝，可以分为预剪枝后剪枝，我们一般用后剪枝的方法来做；  
第二：K-folds交叉验证，将训练集分为K份，然后进行K次的交叉验证，每次使用K-1份作为训练样本数据集，另外的一份作为测试集合；  
第三：减少特征，计算每一个特征和相应变量的相关性，常见的为皮尔逊相关系数，将相关性较小的变量剔除，当然还有一些其他的方法来进行特征筛选，比如基于决策树的特征筛选，通过正则化的方式来进行特征选取等。

## 三、几种模型（ SVM，LR，GBDT，EM ）的原理以及公式推导 ##

### 1、SVM原理 ###

SVM的目标在数据特征空间寻找一个最优超平面将数据分成两类，这个最优化超平面使得离其最近的点到其的距离最大化，这些点被称为支持向量。SVM可以用于解决二分类或者多分类问题。

> 具体的公式推导：  
> [https://blog.csdn.net/qq\_22613769/article/details/106723679][https_blog.csdn.net_qq_22613769_article_details_106723679]

### 2、LR（线性回归）原理 ###

线性回归核心思想是获得最能够拟合数据的直线。

> 公式推导：  
> [https://www.cnblogs.com/mantch/p/10135708.html][https_www.cnblogs.com_mantch_p_10135708.html]

### 2.5、SVM与LR异同点 ###

相同点：

1.  SVM和LR都属于分类算法
2.  不使用核函数的时候都是线性分类器
3.  都是监督学习算法
4.  都是判别模型

不同点：

1.  最大的区别是损失函数的不同（SVM：最大化支持向量的几何间隔；LR：极大化似然估计）
2.  考虑数据的不同（SVM：只考虑超平面附近的支持向量；LR：考虑全部数据）
3.  对于非线性问题（SVM：核函数；LR：不使用核函数）
4.  数据标准化（SVM：因为要计算距离，所以需要；LR：不需要）
5.  正则项（SVM：自带正则项；LR：需要另外加正则项），这就是为什么SVM是结构风险最小化算法的原因！所谓结构风险最小化，意思就是在训练误差和模型复杂度之间寻求平衡，防止过拟合，从而达到真实误差的最小化。

### 3、GBDT原理 ###

Gradient Boosting Decision Tree（GBDT）是梯度提升决策树。  
GBDT模型所输出的结果是由其包含的若干棵决策树累加而成，每一棵决策树都是对之前决策树组合预测残差的拟合，是对之前模型结果的一种“修正”。是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。梯度提升树既可以用于回归问题（此时被称为CART回归树），也可以被用于解决分类问题（此时被称为分类树）。

算法步骤：

1.  初始化，估计使损失函数极小化的常数值，它是只有一个根节点的树，即ganma是一个常数值。
2.  （a）计算损失函数的负梯度在当前模型的值，将它作为残差的估计  
    （b）估计回归树叶节点区域，以拟合残差的近似值  
    （c）利用线性搜索估计叶节点区域的值，使损失函数极小化  
    （d）更新回归树
3.  得到输出的最终模型 f(x)

> 公式推导：[https://www.jianshu.com/p/005a4e6ac775][https_www.jianshu.com_p_005a4e6ac775]

### 4、EM（期望最大）原理 ###

EM 算法，全称 Expectation Maximization Algorithm。期望最大算法是一种迭代算法，用于含有隐变量（Hidden Variable）的概率参数模型的最大似然估计或极大后验概率估计。

EM 算法的核心思想非常简单，分为两步：Expection-Step 和 Maximization-Step。E-Step 主要通过观察数据和现有模型来估计参数，然后用这个估计的参数值来计算似然函数的期望值；而 M-Step 是寻找似然函数最大化时对应的参数。由于算法会保证在每次迭代之后似然函数都会增加，所以函数最终会收敛。

> 公式推导：[https://zhuanlan.zhihu.com/p/78311644][https_zhuanlan.zhihu.com_p_78311644]

### 5、XGBoost原理 ###

XGBoost是对梯度提升算法的改进，求解损失函数极值时使用了牛顿法，将损失函数泰勒展开到二阶，另外损失函数中加入了正则化项。训练时的目标函数由两部分构成，第一部分为梯度提升算法损失，第二部分为正则化项。

XGBoost本质上还是一个GBDT，但是力争把速度和效率发挥到极致。

**XGBoost的核心算法思想是：**

1.  不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数f(x)，去拟合上次预测的残差。
2.  当我们训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数
3.  最后只需要将每棵树对应的分数加起来就是该样本的预测值。

**XGBoost与GBDT有什么不同?**

除了算法上与传统的GBDT有一些不同外，XGBoost还在工程实现上做了大量的优化。总的来说，两者之间的区别和联系可以总结成以下几个方面：

1.  GBDT是机器学习算法，XGBoost是该算法的工程实现。
2.  在使用CART作为基分类器时，XGBoost显式地加入了（**叶子节点个数+叶子节点权重的L2正则化**）正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。
3.  GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代 价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。
4.  传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类 器，比如线性分类器。
5.  传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机 森林相似的策略，支持对数据进行采样。
6.  传统的GBDT没有设计对缺失值进行处理，XGBoost能够自动学习出缺 失值的处理策略。

> 具体见：[https://www.cnblogs.com/mantch/p/11164221.html][https_www.cnblogs.com_mantch_p_11164221.html]

### 6、RF（随机森林）原理 ###

随机森林顾名思义，是用随机的方式建立一个森林，森林里面有很多的决策树组成，随机森林的每一棵决策树之间是没有关联的。在得到森林之后，当有一个新的输入样本进入的时候，就让森林中的每一棵决策树分别进行一下判断，看看这个样本应该属于哪一类（对于分类算法），然后看看哪一类被选择最多，就预测这个样本为那一类。

**随机森林的两个随机：**

1.  随机采样(bootstrap)：应用 bootstrap 法有放回地随机抽取 k个新的自助样本集(bootstrap)，并由此构建 k 棵分类树(ID3 、 C4.5 、 CART)，属于**样本扰动**。注意到这和GBDT的子采样是不同的。**GBDT的子采样是无放回采样，而Bagging的子采样是有放回采样**。
2.  随机属性：随机选择属性子集，个数为k，然后再从这个子集中选择一个最优属性用于划分。属于**属性扰动**。

## 四、K-means 的原理，优缺点以及改进 ##

**原理：**  
K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。

如果用数据表达式表示，假设簇划分为，则我们的目标是最小化平方误差E：

**K-Means的主要优点有：**

1）原理比较简单，实现也是很容易，收敛速度快。

2）聚类效果较优。

3）算法的可解释度比较强。

4）主要需要调参的参数仅仅是簇数k。

**K-Means的主要缺点有：**

1）K值的选取不好把握(改进：可以通过在一开始给定一个适合的数值给k，通过一次K-means算法得到一次聚类中心。对于得到的聚类中心，根据得到的k个聚类的距离情况，合并距离最近的类，因此聚类中心数减小，当将其用于下次聚类时，相应的聚类数目也减小了，最终得到合适数目的聚类数。可以通过一个评判值E来确定聚类数得到一个合适的位置停下来，而不继续合并聚类中心。重复上述循环，直至评判函数收敛为止，最终得到较优聚类数的聚类结果)。

2）对于不是凸的数据集比较难收敛(改进：基于密度的聚类算法更加适合，比如DESCAN算法)

3）如果各隐含类别的数据不平衡，比如各隐含类别的数据量严重失衡，或者各隐含类别的方差不同，则聚类效果不佳。

4） 采用迭代方法，得到的结果只是局部最优。

5） 对噪音和异常点比较的敏感(改进1：离群点检测的LOF算法，通过去除离群点后再聚类，可以减少离群点和孤立点对于聚类效果的影响；改进2：改成求点的中位数，这种聚类方式即K-Mediods聚类（K中值）)。

6）初始聚类中心的选择(改进1：k-means++;改进2：二分K-means，相关知识详见这里和这里)。

> 具体见：[https://blog.csdn.net/u014465639/article/details/71342072][https_blog.csdn.net_u014465639_article_details_71342072]

## 五、Bagging和Boosting ##

Baggging 和Boosting都是模型融合的方法，可以将弱分类器融合之后形成一个强分类器，而且融合之后的效果会比最好的弱分类器更好。

**1、Bagging**

Bagging即套袋法，其算法过程如下：

1.  从原始样本集中抽取训练集。每轮从原始样本集中使用 Bootstraping 的方法 **有放回的抽取** n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）
2.  每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
3.  对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

**2、Boosting**

**AdaBoosting**方式每次使用的是全部的样本，每轮训练改变样本的权重。下一轮训练的目标是找到一个函数 f 来拟合上一轮的残差。当残差足够小或者达到设置的最大迭代次数则停止。Boosting会减小在上一轮训练正确的样本的权重，增大错误样本的权重。（对的残差小，错的残差大）

**梯度提升的Boosting**方式是使用代价函数对上一轮训练出的模型函数 f 的偏导来拟合残差。

> Bagging，Boosting二者之间的区别：[https://blog.csdn.net/qq\_24753293/article/details/81067692][https_blog.csdn.net_qq_24753293_article_details_81067692]

## To Be Continued。。。。。。 ##

[https_blog.csdn.net_qq_22613769_article_details_106723679]: https://blog.csdn.net/qq_22613769/article/details/106723679
[https_www.cnblogs.com_mantch_p_10135708.html]: https://www.cnblogs.com/mantch/p/10135708.html
[https_www.jianshu.com_p_005a4e6ac775]: https://www.jianshu.com/p/005a4e6ac775
[https_zhuanlan.zhihu.com_p_78311644]: https://zhuanlan.zhihu.com/p/78311644
[https_www.cnblogs.com_mantch_p_11164221.html]: https://www.cnblogs.com/mantch/p/11164221.html
[https_blog.csdn.net_u014465639_article_details_71342072]: https://blog.csdn.net/u014465639/article/details/71342072
[https_blog.csdn.net_qq_24753293_article_details_81067692]: https://blog.csdn.net/qq_24753293/article/details/81067692