牛客笔试题之机器学习

痛定思痛。 2022-02-27 18:12 788阅读 0赞

昨天做完了[牛客网][Link 1]上的机器学习试题，下面是对一些错题的分析，并简要总结了一些机器学习中应该注意的知识点，过段时间会对其中的一些方法进行更加详细的分析介绍。题中**打问号？**代表该题答案存在争议，不一定准确。

### 过拟合问题 ###

![1.png][]  
**解析：**  
**造成过拟合的原因主要有：**

1.  训练数据不足
2.  训练模型过度导致模型非常复杂，泛化能力差
3.  样本里的噪音数据干扰过大，大到模型过分记住了噪音特征，反而忽略了真实的输入输出间的关系；
4.  权值学习迭代次数足够多(Overtraining)，拟合了训练数据中的噪声和训练样例中没有代表性的特征

>  *  选项A增加训练集可以解决训练数据不足的问题，防止过拟合
>  *  选项B对应使得模型的复杂度降低，防止过拟合
>  *  选项C类似主成分分析，降低数据的特征维度，使得模型复杂度降低，防止过拟合
>  *  选项D使得模型更加复杂化，会充分训练数据导致过拟合

### 条件概率 ###

![2.png][]  
**解析：**  
由条件概率公式可知：  
![100.png][]  
![3.png][]

### 先验概率未知 ###

![4.png][]  
**解析：**  
![5.png][]

### 朴素贝叶斯（NB） ###

![6.png][]  
**NB的核心在于它假设向量的所有分量之间是独立的。**  
在贝叶斯理论系统中，都有一个重要的条件独立性假设：假设所有特征之间相互独立，这样才能将联合概率拆分。

### 分支定界法（branch and bound） ###

![7.png][]  
**解析：**  
![8.png][]

### 基于核的机器学习算法 ###

![9.png][]  
**解析：**

*  A EM算法，聚类算法
 *  B 径向基核函数
 *  C 线性判别分析
 *  D 支持向量机  
    **核函数的本质就是将一个空间转化为另一个空间的变化，线性判别分析是把高纬空间利用特征值和特征向量转化到一维空间，核化的LDA模型是KFDA。**

### L1和L2范数 ###

![10.png][]  
**解析：**

1.  **L1范数**是指向量中各个元素的绝对值之和，也叫”系数规则算子（`Lasso regularization`）。它可以实现稀疏，通过将无用特征对应的参数W置为零实现。
2.  **L2范数**是指向量各元素的平方和然后开方，用在回归模型中也称为岭回归（`Ridge regression`）。L2避免过拟合的原理是：让L2范数的规则项`||W||2` 尽可能小，可以使得W每个元素都很小，接近于零，但是与L1不同的是，不会等于0；这样得到的模型抗干扰能力强，参数很小时，即使样本数据x发生很大的变化，模型预测值y的变化也会很有限。

### 准确率、召回率及F1值 ###

![11.png][]  
**解析：**  
![12.png][]  
**精准度和召回率是一对矛盾的度量，一般来说，精准度越高，召回率越低；召回率越高，精准度越低**。

### 生成式模型和判别式模型 ###

\*\*生成式模型(Generative Model)与判别式模型(Discrimitive Model)\*\*是分类器常遇到的概念，它们的区别在于：

对于输入x，类别标签y：  
　　生成式模型估计它们的联合概率分布P(x,y)  
　　判别式模型估计条件概率分布P(y|x)

**生成式模型可以根据贝叶斯公式得到判别式模型**，但反过来不行。

**公式上看**  
**生成模型**： 学习时先得到 P(x,y)，继而得到 P(y|x)。预测时应用最大后验概率法（MAP）得到预测类别 y。  
**判别模型**： 直接学习得到P(y|x)，利用MAP得到 y。或者直接学得一个映射函数 y=f(x)。

**直观上看**  
**生成模型**： 关注数据是如何生成的  
**判别模型**： 关注类别之间的差别  
例子：  
假如你的任务是识别一个语音属于哪种语言。例如对面一个人走过来，和你说了一句话，你需要识别出她说的到底是汉语、英语还是法语等。那么你可以有两种方法达到这个目的：

> 1.  学习每一种语言，你花了大量精力把汉语、英语和法语等都学会了，我指的学会是你知道什么样的语音对应什么样的语言。然后再有人过来对你说，你就可以知道他说的是什么语音.
> 2.  不去学习每一种语言，你只学习这些语言之间的差别，然后再判断（分类）。意思是指我学会了汉语和英语等语言的发音是有差别的，我学会这种差别就好了。  
>     **那么第一种方法就是生成方法，第二种方法是判别方法**。

**常见的判别式模型：**

> 1.  逻辑回归 　　Logistic Regression
> 2.  支持向量机 　　SVM
> 3.  神经网络 　　NN
> 4.  传统神经网络 　　Traditional Neural Networks
> 5.  邻近取样 　　Nearest Neighbor
> 6.  条件随机场 　　CRF
> 7.  线性判别分析 　　Linear Discriminant Analysis
> 8.  提升算法 　　Boosting
> 9.  线性回归 　　Linear Regression
> 10. 高斯过程　　 　　Gaussian Process
> 11. 分类回归树　　　　Classification and Regression Tree (CART)
> 12. 区分度训练

**常见的生成式模型：**

> 1.  高斯　　 　　　　Gaussians
> 2.  朴素贝叶斯　　 　 Naive Bayes
> 3.  混合多项式　　　　Mixtures of Multinomials
> 4.  混合高斯模型　　 Mixtures of Gaussians
> 5.  多专家模型　　　　Mixtures of Experts
> 6.  隐马尔科夫模型　　HMM
> 7.  S型信念网络　　　 Sigmoidal Belief Networks
> 8.  贝叶斯网络　　　　 Bayesian Networks
> 9.  马尔科夫随机场　　 Markov Random Fields
> 10. 潜在狄利克雷分配　 Latent Dirichlet Allocation(LDA)
> 11. 判别式分析
> 12. K近邻　　　　　　 KNN
> 13. 深度信念网络　　　 DBN

### 聚类算法影响因素 ###

![13.png][]  
**解析：**  
**聚类的目标是使同一类对象的相似度尽可能地大，不同类对象之间的相似度尽可能的小。**  
聚类分析算法主要可以分为：

> 1.  划分法（Partitioning Methods）
> 2.  层次法（Hierarchical Me thods）
> 3.  基于密度的方法（Density-Based Methods）
> 4.  基于网格的方法（Grid-Based M ethods）
> 5.  基于模型的方法（Model-Based Methods）
> 6.  谱聚类（Spectral Clustering）

C大约说的是度量方式，例如KMeans 可以用欧式距离啊，也可用其他的距离，这也是分类准则。（C正确）\*\* 不过个人觉得C有歧义\*\*；  
特征选取的差异会影响聚类效果（A正 确）。  
聚类的目标是使同一类对象的相似度尽可能地大，因此不同的相似度测度方法对聚类结 果有着重要影响（B正确）。  
由于聚类算法是无监督方法，不存在带类别标签的样本，因此， D选项不是聚类算法的输入数据。

### 隐马尔科夫模型 ###

![14.png][]  
**解析：**

1.  **前向后向算法**解决的是一个**评估问题**，即给定一个模型，求某些特定观测序列的概率，用于评估该序列最匹配的模型。
2.  **Baum-Welch算法**解决的是一个**模型训练问题（学习）**，即参数估计，是一种**无监督**的训练方法，主要通过EM迭代实现。
3.  **维特比算法**解决的是一个**预测问题，通信中的解码问题**，即给定一个模型和某个特定的输出序列，求最可能产生这个输出的状态序列。比如通过海藻变化（输出序列）来观测天气（状态序列）。

### AdaBoost及SVM ###

![15.png][]  
**解析：**  
![16.png][]

### 卷积大小计算 ###

![17.png][]  
**解析：**  
![18.png][]

### 特征选择方法 ###

![19.png][]  
**解析：**  
![20.png][]

### 缺失值处理方法 ###

![21.png][]  
**解析：**  
由于**调查、编码和录入误差**，数据中可能存在一些无效值和缺失值，需要给予适当的处理。常用的处理方法有：**估算，整例删除，变量删除和成对删除**。

1.  **估算(estimation)**。最简单的办法就是用某个变量的样本均值、中位数或众数代替无效值和缺失值。这种办法简单，但没有充分考虑数据中已有的信息，误差可能较大。
2.  \*\*整例删除(casewise deletion)\*\*是剔除含有缺失值的样本。由于很多问卷都可能存在缺失值，这种做法的结果可能导致有效样本量大大减少，无法充分利用已经收集到的数据。因此，只适合关键变量缺失，或者含有无效值或缺失值的样本比重很小的情况。
3.  **变量删除(variable deletion)**。如果某一变量的无效值和缺失值很多，而且该变量对于所研究的问题不是特别重要，则可以考虑将该变量删除。这种做法减少了供分析用的变量数目，但没有改变样本量。
4.  \*\*成对删除(pairwise deletion)\*\*是用一个特殊码(通常是9、99、999等)代表无效值和缺失值，同时保留数据集中的全部变量和样本。但是，在具体计算时只采用有完整答案的样本，因而不同的分析因涉及的变量不同，其有效样本量也会有所不同。

### 信息增益 ###

![22.png][]  
**解析：**  
本题主要考察信息增益的计算方式，具体可参考我之前[博客决策树][Link 2]：  
 G a i n ( A ) = I n f o ( D ) − I n f o A ( D ) Gain(A) = Info(D) - InfoA(D) Gain(A)=Info(D)−InfoA(D)  
其中Info表示信息熵，计算公式如下：  
![24.png][]  
所以可以计算出各特征的信息增益如下所示：  
![23.png][]

### 置信度及支持度 ###

![25.png][]  
**解析：**  
**置信度计算规则为**： 同时购买商品A和商品B的交易次数\*\*/**购买了商品A的次数  
支持度计算规则为： 同时购买了商品A和商品B的交易次数**/\*\*总的交易次数

### 求解线性不可分方法 ###

![26.png][]  
**解析：**  
**伪逆法：** 径向基（RBF）神经网络的训练算法，径向基解决的就是线性不可分的情况。  
**感知器算法：** 线性分类模型。  
**H-K算法：** 在最小均方误差准则下求得权矢量，二次准则解决非线性问题。  
**势函数法：** 势函数非线性。

### 时间序列模型 ###

![27.png][]  
**解析：**  
\*\*AR模型：\*\*自回归模型，是一种线性模型  
\*\*MA模型：\*\*移动平均法模型，其中使用趋势移动平均法建立直线趋势的预测模型  
\*\*ARMA模型：\*\*自回归滑动平均模型，拟合较高阶模型  
\*\*GARCH模型：\*\*广义回归模型，对误差的方差建模，适用于波动性的分析和预测

### PMF PDF CDF ###

![28.png][]  
**解析：**  
![29.png][]

### CRF（条件随机场） ###

![30.png][]  
**解析：**

1.  **HMM（隐马尔科夫模型）**：HMM是一种产生式模型，定义了联合概率分布p(x,y) ，其中x和y分别表示观察序列和相对应的标注序列的随机变量。它包含2个基本假设：

>  *  后一个隐藏状态只依赖于前一个隐藏状态。
>  *  观测值之间相互独立，观测值只依赖于该时刻的马尔科夫链的隐状态。  
>     **缺点**：1. HMM只依赖于每一个状态和它对应的观察对象：2、目标函数和预测目标函数不匹配：

1.  **MEMM（最大熵马尔科夫模型）**：最大熵马尔科夫模型把HMM模型和`Maximum Entropy模型`的优点集合成一种生成模型（Generative Model）。克服了观察值之间严格独立产生的问题，但仍存在**标注偏置问题（Label bias problem）**。
2.  **CRF（条件随机场）**：CRF模型解决了标注偏置问题，去除了HMM中两个不合理的假设，当然，模型相应得也变复杂了。MEMM是局部归一化，CRF是全局归一化。  
    **CRF 的优点**：特征灵活，可以容纳较多的上下文信息，能够做到全局最优  
    **CRF 的缺点**：速度慢  
    \*\*总结：\*\*三者都是NLP（自然语言处理）中的基础语言模型。

### 线性回归描述 ###

![31.png][]  
**解析：**  
![32.png][]  
![33.png][]  
![34.png][]

### K-L与PCA ###

![35.png][]  
**解析：**  
**K-L变换**与**PCA变换**是不同的概念，**PCA**的变换矩阵是**协方差矩阵**，**K-L变换**的变换矩阵可以有很多种（二阶矩阵、协方差矩阵、总类内离散度矩阵等等）。**当K-L变换矩阵为协方差矩阵时，等同于PCA**。

### 数据不均衡 ###

![36.png][]  
**解析：**

1.  重采样。  
    A可视作重采样的变形。改变数据分布消除不平衡，可能导致过拟合。
2.  欠采样。  
    C的方案 提高少数类的分类性能，可能丢失多数类的重要信息。
3.  权值调整。  
    D方案也是其中一种方式。

### HK算法与感知器 ###

![37.png][]  
**解析：**  
![38.png][]

### 时间序列算法模型 ###

![39.png][]  
**解析：**  
常见的时间序列算法模型有

*  移动平均法 (MA) 简单移动平均法
 *  自回归模型(AR)
 *  自回归滑动平均模型(ARMA)
 *  GARCH模型 指数平滑法  
    ABD都是一些关于股票涨跌的分析方法。

### SVM核函数 ###

![40.png][]  
**解析：**  
SVM核函数包括：  
**线性核函数、多项式核函数、径向基核函数（RBF）、高斯核函数**、幂指数核函数、**拉普拉斯核函数**、ANOVA核函数、二次有理核函数、多元二次核函数、逆多元二次核函数以及**Sigmoid核函数**。

### Logit与SVM ###

![41.png][]  
**解析：**  
A. Logit回归本质上是**一种根据样本对权值进行极大似然估计的方法**，而后验概率正比于先验概率和似然函数的乘积。**logit仅仅是最大化似然函数，并没有最大化后验概率**，更谈不上最小化后验概率。A错误  
B. Logit回归的输出就是样本属于正类别的几率，可以计算出概率，正确  
C. SVM的目标是找到使得训练数据尽可能分开且分类间隔最大的超平面，应该属于结构风险最小化，正确。  
D. SVM可以通过正则化系数控制模型的复杂度，避免过拟合。（**个人觉得但最好是加上正则项吧**）

### LDA与PCA ###

\*\*LDA（线性判别分析）**用于降维，和**PCA（主成分分析）\*\*有很多相同，也有很多不同的地方，因此值得好好的比较一下两者的降维异同点。  
**相同点：**

> 1.  两者均可以对数据进行降维。
> 2.  两者在降维时均使用了矩阵特征分解的思想。
> 3.  两者都假设数据符合高斯分布。

**不同点：**

> 1.  **LDA是有监督**的降维方法，而**PCA是无监督**的降维方法
> 2.  LDA降维最多降到类别数**k-1**的维数，而PCA没有这个限制。
> 3.  LDA除了可以用于降维，还可以**用于分类**。
> 4.  LDA选择分类性能最好的投影方向，而PCA选择样本点投影具有最大方差的方向

### 常见的数据降维方法 ###

**线性**

> 1.  LDA（线性判别分析）
> 2.  PCA（主成分分析）

**非线性**

> 1.  核方法（KPCA、KFDA等）
> 2.  二维化
> 3.  流行学习（LLE、LPP、ISOMap等）

**其他方法：**

> 1.  神经网络（自编码）
> 2.  聚类  
>     3.小波分析
> 3.  LASSO（参数压缩）
> 4.  SVD奇异值分解

### 线性分类器准则 ###

![42.png][]  
**解析：**  
线性分类器有三大类：**感知器准则函数、SVM、Fisher准则**，而贝叶斯分类器不是线性分类器。

> 1.  **感知器准则函数：代价函数`J=-(W*X+w0)`，分类的准则是最小化代价函数**。感知器是神经网络（NN）的基础。
> 2.  **SVM：支持向量机也是很经典的算法，优化目标是最大化间隔（margin），又称最大间隔分类器，是一种典型的线性分类器**。（使用核函数可解决非线性问题）
> 3.  **Fisher准则：更广泛的称呼是线性判别分析（LDA）**，将所有样本投影到一条远点出发的直线，使得同类样本距离尽可能小，不同类样本距离尽可能大，**具体为最大化“广义瑞利商”**。  
>     **贝叶斯分类器：一种基于统计方法**的分类器，要求先了解样本的分布特点（高斯、指数等），所以使用起来限制很多。在满足一些特定条件下，其优化目标与线性分类器有相同结构（同方差高斯分布等），其余条件下不是线性分类。

[Link 1]: https://www.nowcoder.com
[1.png]: /images/20220227/c01ec6178a594ebdb2c5a030fb7b2f7f.png
[2.png]: /images/20220227/5a6965c888c04164be557597851c0f9c.png
[100.png]: /images/20220227/d715690018404bcc82d657a225c5fe40.png
[3.png]: /images/20220227/e340c74c41114fb09ced7f83e93e01d8.png
[4.png]: /images/20220227/780bda99021f4e6593de6a9feb744dd0.png
[5.png]: /images/20220227/6964283ecabb4e88a07925d659833189.png
[6.png]: /images/20220227/3022fc2a734648378e838418ebd04061.png
[7.png]: /images/20220227/d1a773ef917d47358e3b743e500a6b6c.png
[8.png]: /images/20220227/47929e66547749d5a0a08ebc5977c0ab.png
[9.png]: /images/20220227/f54e1b767af144868a6e0c4fed57bd87.png
[10.png]: /images/20220227/f99e70c29307426bb3ad5005bac715a3.png
[11.png]: /images/20220227/f3ae82d603924e59a7191ce54bf52ea1.png
[12.png]: /images/20220227/1624a1e927e84c5eae8768542bb67b38.png
[13.png]: /images/20220227/97829b13fe3d4f5daf76d1ff5ca0b535.png
[14.png]: /images/20220227/6107e3f52ecf49998bbfb4893cc19fec.png
[15.png]: /images/20220227/84398ac4136a4bcea136860652a93e2f.png
[16.png]: /images/20220227/c3114b8fd25e449faa419d216ba9162b.png
[17.png]: /images/20220227/f2426ae1fb1245b28e906abd95cc6ecd.png
[18.png]: /images/20220227/312c61090bf4403ab4e8563404e2a39f.png
[19.png]: /images/20220227/92d5c574955c478a95cb5cd26ca0c45b.png
[20.png]: /images/20220227/82d60faacd5647deb5517ab3dbf16065.png
[21.png]: /images/20220227/3e783f642fc14582af6a06b015f98756.png
[22.png]: /images/20220227/b954b722b8a24d2db3faf927077fb317.png
[Link 2]: http://liufan.vip/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/2019-3-6-%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E6%96%B9%E6%B3%95%E4%B9%8B%E5%86%B3%E7%AD%96%E6%A0%91/
[24.png]: /images/20220227/47dbc15898704998b8ecd1337c225dc8.png
[23.png]: /images/20220227/1e0e507135594f48b1e44994ba1bf16b.png
[25.png]: /images/20220227/5fa495181824448882c2dfbb1bdb481d.png
[26.png]: /images/20220227/caa9194354d14bed88d2ac3c5fb4777e.png
[27.png]: /images/20220227/3ddc5a814ad7415f87c0b1db56f34801.png
[28.png]: /images/20220227/7549a697f95e4713ac2c6e32051e5ded.png
[29.png]: /images/20220227/d81fb923f034439b84880990ad00b1ba.png
[30.png]: /images/20220227/c0272a857d7e47f686c4b92cf794cdde.png
[31.png]: /images/20220227/6c99306bc42a46fe99449ab07d9f4ecb.png
[32.png]: /images/20220227/2819ed804c9a432fb8b4bfb937063015.png
[33.png]: /images/20220227/8662256ea1014bdeb3d07742f9beb9ea.png
[34.png]: /images/20220227/15e380aaf0eb4d44b079f050d787e99f.png
[35.png]: /images/20220227/8f0436e3d72e417e9ef3b8c308579e93.png
[36.png]: /images/20220227/98eb10de0a0946fcacbcfd8517500da5.png
[37.png]: /images/20220227/ed0a27dfbaa14bf1a327e30450f51f50.png
[38.png]: /images/20220227/c7d71d1c26fb43ebb553c4ad21bb5332.png
[39.png]: /images/20220227/b149cd93087e43dea0653268a36c3ced.png
[40.png]: /images/20220227/06eeba86e95246d08db62d77859d5edb.png
[41.png]: /images/20220227/943fcbf3d3664689b19faf24ca0d47e6.png
[42.png]: /images/20220227/e7fc42c749e041e08d7a3ea9dfc60693.png