BAT面试必考算法题之专项题目(11-20)

浏览: 1738

值此秋招之际,特推出BAT面试必考算法系列,助力大家步入互联网大厂。今天是专项题目11道到20道

本文是天善智能签约讲师 张龙祥老师的课程Hellobi Live | 数据分析岗位面试经验分享 课件,未经允许,禁止转载。

推荐课程:

Hellobi Live | 数据分析岗位面试经验分享


11关于 logit 回归和 SVM 不正确的是()

Logit回归目标函数是最小化后验概率

Logit回归可以用于预测事件发生概率的大小

SVM目标是经验风险最小化

SVM可以有效避免模型过拟合

 

12深度学习是当前很热门的机器学习算法,在深度学习中,涉及到大量的矩阵相乘,现在需要计算三个稠密矩阵A,B,C的乘积ABC,假设三个矩阵的尺寸分别为m*nn*pp*q,且m<n<p<q,以下计算顺序效率最高的是()

(AB)C

AC(B)

A(BC)

所以效率都相同

首先,根据简单的矩阵知识,因为 A*B , A 的列数必须和 B 的行数相等。因此,可以排除 B 选项,

然后,再看 A 、 C 选项。在 A 选项中, m*n 的矩阵 A 和 n*p 的矩阵 B 的乘积,得到 m*p 的矩阵 A*B ,而 A*B 的每个元素需要 n 次乘法和 n-1 次加法,忽略加法,共需要 m*n*p 次乘法运算。同样情况分析 A*B 之后再乘以 C 时的情况,共需要 m*p*q 次乘法运算。因此,A 选项 (AB)C 需要的乘法次数是 m*n*p+m*p*q 。同理分析, C 选项 A (BC) 需要的乘法次数是 n*p*q+m*n*q 。

由于 m*n*p<m*n*q , m*p*q<n*p*q ,显然 A 运算次数更少,故选 A 。

 

13解决隐马模型中预测问题的算法是?

前向算法

后向算法

Baum-Welch算法

维特比算法

A、B:前向、后向算法解决的是一个评估问题,即给定一个模型,求某特定观测序列的概率,用于评估该序列最匹配的模型。

C:Baum-Welch算法解决的是一个模型训练问题,即参数估计,是一种无监督的训练方法,主要通过EM迭代实现;

D:维特比算法解决的是给定 一个模型和某个特定的输出序列,求最可能产生这个输出的状态序列。如通过海藻变化(输出序列)来观测天气(状态序列),是预测问题,通信中的解码问题。

 

14已知一组数据的协方差矩阵P,下面关于主分量说法错误的是()

主分量分析的最佳准则是对一组数据进行按一组正交基分解, 在只取相同数量分量的条件下,以均方误差计算截尾误差最小

在经主分量分解后,协方差矩阵成为对角矩阵

主分量分析就是K-L变换

主分量是通过求协方差矩阵的特征值得到

K-L变换与PCA变换是不同的概念,PCA的变换矩阵是协方差矩阵,K-L变换的变换矩阵可以有很多种(二阶矩阵、协方差矩阵、总类内离散度矩阵等等)。K-L变换矩阵为协方差矩阵时,等同于PCA

 

15以下关于PMF(概率质量函数),PDF(概率密度函数),CDF(累积分布函数)描述错误的是()

PDF描述的是连续型随机变量在特定取值区间的概率

CDF是PDF在特定区间上的积分

PMF描述的是离散型随机变量在特定取值点的概率

有一个分布的CDF函数H(x),则H(a)等于P(X<=a)

概率质量函数 (probability mass functionPMF)离散随机变量在各特定取值上的概率。

概率密度函数(p robability density functionPDF )是对 连续随机变量 定义的,本身不是概率,只有对连续随机变量的取值进行积分后才是概率。

累积分布函数(cumulativedistribution function,CDF) 能完整描述一个实数随机变量X的概率分布,是概率密度函数的积分。对於所有实数x ,与pdf相对。

在数学中, 连续型随机变量  概率密度函数 (在不至于混淆时可以简称为 密度函数 )是一个描述这个随机变量的输出值,在某个确定的取值点附近的可能性的函数。probability density function,简称PDF

 

16机器学习中L1正则化和L2正则化的区别是?

使用L1可以得到稀疏的权值

使用L2可以得到平滑的权值

 

17下列不是SVM核函数的是:

多项式核函数

logistic核函数

径向基核函数

Sigmoid核函数

支持向量机是建立在统计学习理论基础之上的新一代机器学习算法,支持向量机的优势主要体现在解决线性不可分问题,它通过引入核函数,巧妙地解决了在高维空间中的内积运算,从而很好地解决了非线性分类问题。

构造出一个具有良好性能的SVM,核函数的选择是关键.核函数的选择包括两部分工作:一是核函数类型的选择,二是确定核函数类型后相关参数的选择.因此如何根据具体的数据选择恰当的核函数是SVM应用领域遇到的一个重大难题,也成为科研工作者所关注的焦点,即便如此,却依然没有得到具体的理论或方法来指导核函数的选取.

1、经常使用的核函数

核函数的定义并不困难,根据泛函的有关理论,只要一种函数 K ( x i , x j ) 满足Mercer条件,它就对应某一变换空间的内积.对于判断哪些函数是核函数到目前为止也取得了重要的突破,得到Mercer定理和以下常用的核函数类型:

(1)线性核函数

K ( x , x i ) = x ⋅ x i

(2)多项式核

K ( x , x i ) = ( ( x ⋅ x i ) + 1 ) d

(3)径向基核(RBF

K ( x , x i ) = exp ( − ∥ x − x i ∥ 2 σ 2 )

Gauss径向基函数则是局部性强的核函数,其外推能力随着参数 σ 的增大而减弱。多项式形式的核函数具有良好的全局性质。局部性较差。

(4)傅里叶核

K ( x , x i ) = 1 − q 2 2 ( 1 − 2 q cos ( x − x i ) + q 2 )

(5)样条核

K ( x , x i ) = B 2 n + 1 ( x − x i )

(6)Sigmoid核函数

K ( x , x i ) = tanh ( κ ( x , x i ) − δ )

采用Sigmoid函数作为核函数时,支持向量机实现的就是一种多层感知器神经网络,应用SVM方法,隐含层节点数目(它确定神经网络的结构)、隐含层节点对输入节点的权值都是在设计(训练)的过程中自动确定的。而且支持向量机的理论基础决定了它最终求得的是全局最优值而不是局部最小值,也保证了它对于未知样本的良好泛化能力而不会出现过学习现象。

2、核函数的选择

在选取核函数解决实际问题时,通常采用的方法有:一是利用专家的先验知识预先选定核函数;二是采用Cross-Validation方法,即在进行核函数选取时,分别试用不同的核函数,归纳误差最小的核函数就是最好的核函数.如针对傅立叶核、RBF核,结合信号处理问题中的函数回归问题,通过仿真实验,对比分析了在相同数据条件下,采用傅立叶核的SVM要比采用RBF核
的SVM误差小很多.三是采用由Smits等人提出的混合核函数方法,该方法较之前两者是目前选取核函数的主流方法,也是关于如何构造核函数的又一开创性的工作.将不同的核函数结合起来后会有更好的特性,这是混合核函数方法的基本思想.

 

18下面有关序列模式挖掘算法的描述,错误的是?

AprioriAll算法和GSP算法都属于Apriori类算法,都要产生大量的候选序列

FreeSpan算法和PrefixSpan算法不生成大量的候选序列以及不需要反复扫描原数据库

在时空的执行效率上,FreeSpanPrefixSpan更优

和AprioriAll相比,GSP的执行效率比较高

1. Apriori算法 :关联分析原始算法,用于从候选项集中发现频繁项集。两个步骤:进行自连接、进行剪枝。缺点:无时序先后性。

AprioriAll算法:AprioriAll算法与Apriori算法的执行过程是一样的,不同点在于候选集的产生,需要区分最后两个元素的前后。

AprioriSome算法:可以看做是AprioriAll算法的改进

AprioriAll算法和AprioriSome算法的比较:

(1)AprioriAll用 去计算出所有的候选Ck,而AprioriSome会直接用 去计算所有的候选 ,因为 包含 ,所以AprioriSome会产生比较多的候选。

(2)虽然AprioriSome跳跃式计算候选,但因为它所产生的候选比较多,可能在回溯阶段前就占满内存。

(3)如果内存占满了,AprioriSome就会被迫去计算最后一组的候选。

(4)对于较低的支持度,有较长的大序列,AprioriSome算法要好些。

2. GPS算法:类Apriori算法。用于从候选项集中发现具有时序先后性的频繁项集。两个步骤:进行自连接、进行剪枝。缺点:每次计算支持度,都需要扫描全部数据集;对序列模式很长的情况,由于其对应的短的序列模式规模太大,算法很难处理。

3. SPADE算法:改进的GPS算法,规避多次对数据集D进行全表扫描的问题。与GSP算法大体相同,多了一个ID_LIST记录,使得每一次的ID_LIST根据上一次的ID_LIST得到(从而得到支持度)。而ID_LIST的规模是随着剪枝的不断进行而缩小的。所以也就解决了GSP算法多次扫描数据集D问题。

4.  FreeSpan算法:即频繁模式投影的序列模式挖掘。核心思想是分治算法。基本思想为:利用频繁项递归地将序列数据库投影到更小的投影数据库集中,在每个投影数据库中生成子序列片断。这一过程对数据和待检验的频繁模式集进行了分割,并且将每一次检验限制在与其相符合的更小的投影数据库中。

优点:减少产生候选序列所需的开销。缺点:可能会产生许多投影数据库,开销很大,会产生很多的

5. PrefixSpan 算法:从FreeSpan中推导演化而来的。收缩速度比FreeSpan还要更快些。

 

19 类域界面方程法中,不能求线性不可分情况下分类问题近似或精确解的方法是?

伪逆法

感知器算法

基于二次准则的H-K算法

势函数法

伪逆法:径向基(RBF)神经网络的训练算法,径向基解决的就是线性不可分的情况。

感知器算法:线性分类模型。

H-K算法:在最小均方误差准则下求得权矢量,二次准则解决非线性问题。

势函数法:势函数非线性。

 

20 下面有关分类算法的准确率,召回率,F1 值的描述,错误的是?

准确率是检索出相关文档数与检索出的文档总数的比率,衡量的是检索系统的查准率

召回率是指检索出的相关文档数和文档库中所有的相关文档数的比率,衡量的是检索系统的查全率

正确率、召回率和 F 值取值都在01之间,数值越接近0,查准率或查全率就越高

为了解决准确率和召回率冲突问题,引入了F1分数

 

假设一共有10篇文章,里面4篇是你要找的。根据你某个算法,你认为其中有5篇是你要找的,但是实际上在这5篇里面,只有3篇是真正你要找的。那么你的这个算法的precision3/5=60%,也就是,你找的这5篇,有3篇是真正对的。这个算法的recall3/4=75%,也就是,一共有用的这4篇里面,你找到了其中三篇。

推荐 0
本文由 天善智能 创作,采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。
转载、引用前需联系作者,并署名作者且注明文章出处。
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台,并不用于任何商业目的,如果有任何问题,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

0 个评论

要回复文章请先登录注册