面试机器学习、数据挖掘等大数据岗位必备

part1—-面试常见内容及面试技巧

机器学习、大数据相关岗位的职责

自己参与面试的提供算法岗位的公司有 BAT、小米、360、飞维美地、宜信、猿题库 等,根据业务的不同,岗位职责大概分为:

平台搭建类

数据计算平台搭建,基础算法实现,当然,要求支持大样本量、高维度数据,所以可能还需要底层开发、并行计算、分布式计算等方面的知识;


算法研究类

1.文本挖掘,如领域知识图谱构建、垃圾短信过滤等;

2.推荐,广告推荐、APP 推荐、题目推荐、新闻推荐等;

3.排序,搜索结果排序、广告排序等;

4.广告投放效果分析;

5.互联网信用评价;

6图像识别、理解。


数据挖掘类

商业智能,如统计报表;

用户体验分析,预测流失用户。


以上是根据本人求职季有限的接触所做的总结。有的应用方向比较成熟,业界有足够的技术积累,比如搜索、推荐,也有的方向还有很多开放性问题等待探索,比如互联网金融、互联网教育。在面试的过程中,一方面要尽力向企业展现自己的能力,另一方面也是在增进对行业发展现状与未来趋势的理解,特别是可以从一些刚起步的企业和团队那里,了解到一些有价值的一手问题。

以下首先介绍面试中遇到的一些真实问题,然后谈一谈答题和面试准备上的建议。


面试问题

你在研究/项目/实习经历中主要用过哪些机器学习/数据挖掘的算法?

你熟悉的机器学习/数据挖掘算法主要有哪些?

你用过哪些机器学习/数据挖掘工具或框架?


基础知识

无监督和有监督算法的区别?

SVM 的推导,特性?多分类怎么处理?

LR 的推导,特性?

决策树的特性?

SVM、LR、决策树的对比?

GBDT 和 决策森林 的区别?

如何判断函数凸或非凸?

解释对偶的概念。

如何进行特征选择?

为什么会产生过拟合,有哪些方法可以预防或克服过拟合?

介绍卷积神经网络,和 DBN 有什么区别?

采用 EM 算法求解的模型有哪些,为什么不用牛顿法或梯度下降法?

用 EM 算法推导解释 Kmeans。

用过哪些聚类算法,解释密度聚类算法。

聚类算法中的距离度量有哪些?

如何进行实体识别?

解释贝叶斯公式和朴素贝叶斯分类。

写一个 Hadoop 版本的 wordcount。

……


开放问题

给你公司内部群组的聊天记录,怎样区分出主管和员工?

如何评估网站内容的真实性(针对代刷、作弊类)?

深度学习在推荐系统上可能有怎样的发挥?

路段平均车速反映了路况,在道路上布控采集车辆速度,如何对路况做出合理估计?采集数据中的异常值如何处理?

如何根据语料计算两个词词义的相似度?

在百度贴吧里发布 APP 广告,问推荐策略?

如何判断自己实现的 LR、Kmeans 算法是否正确?

100亿数字,怎么统计前100大的?

……


答题思路


用过什么算法?

最好是在项目/实习的大数据场景里用过,比如推荐里用过 CF、LR,分类里用过 SVM、GBDT;

一般用法是什么,是不是自己实现的,有什么比较知名的实现,使用过程中踩过哪些坑;

优缺点分析。


熟悉的算法有哪些?

基础算法要多说,其它算法要挑熟悉程度高的说,不光列举算法,也适当说说应用场合;

面试官和你的研究方向可能不匹配,不过在基础算法上你们还是有很多共同语言的,你说得太高大上可能效果并不好,一方面面试官还是要问基础的,另一方面一旦面试官突发奇想让你给他讲解高大上的内容,而你只是泛泛的了解,那就傻叉了。


用过哪些框架/算法包?

主流的分布式框架如 Hadoop,Spark,Graphlab,Parameter Server 等择一或多使用了解;

通用算法包,如 mahout,scikit,weka 等;

专用算法包,如 opencv,theano,torch7,ICTCLAS 等。


基础知识

对知识进行结构化整理,比如撰写自己的 cheet sheet,我觉得面试是在有限时间内向面试官输出自己知识的过程,如果仅仅是在面试现场才开始调动知识、组织表达,总还是不如系统的梳理准备;

从面试官的角度多问自己一些问题,通过查找资料总结出全面的解答,比如如何预防或克服过拟合。

产生背景,适用场合(数据规模,特征维度,是否有 Online 算法,离散/连续特征处理等角度);

原理推导(最大间隔,软间隔,对偶);

求解方法(随机梯度下降、拟牛顿法等优化算法);

优缺点,相关改进;

和其他基本方法的对比;

个人感觉高频话题是 SVM、LR、决策树(决策森林)和聚类算法,要重点准备;

算法要从以下几个方面来掌握:

产生背景,适用场合(数据规模,特征维度,是否有 Online 算法,离散/连续特征处理等角度);

原理推导(最大间隔,软间隔,对偶);

求解方法(随机梯度下降、拟牛顿法等优化算法);

优缺点,相关改进;

和其他基本方法的对比;

不能停留在能看懂的程度,还要:

对知识进行结构化整理,比如撰写自己的 cheet sheet,我觉得面试是在有限时间内向面试官输出自己知识的过程,如果仅仅是在面试现场才开始调动知识、组织表达,总还是不如系统的梳理准备;

从面试官的角度多问自己一些问题,通过查找资料总结出全面的解答,比如如何预防或克服过拟合。


开放问题

由于问题具有综合性和开放性,所以不仅仅考察对算法的了解,还需要足够的实战经验作基础;

先不要考虑完善性或可实现性,调动你的一切知识储备和经验储备去设计,有多少说多少,想到什么说什么,方案都是在你和面试官讨论的过程里逐步完善的,不过面试官有两种风格:引导你思考考虑不周之处 or 指责你没有考虑到某些情况,遇到后者的话还请注意灵活调整答题策略;

和同学朋友开展讨论,可以从上一节列出的问题开始。


准备建议

基础算法复习两条线

1.材料阅读 包括经典教材(比如 PRML,模式分类)、网上系列博客,系统梳理基础算法知识;

2.面试反馈 面试过程中会让你发现自己的薄弱环节和知识盲区,把这些问题记录下来,在下一次面试前搞懂搞透。

除算法知识,还应适当掌握一些系统架构方面的知识,可以从网上分享的阿里、京东、新浪微博等的架构介绍 PPT 入手,也可以从 Hadoop、Spark 等的设计实现切入。

如果真的是以就业为导向就要在平时注意实战经验的积累,在科研项目、实习、比赛(Kaggle,阿里大数据竞赛等)中摸清算法特性、熟悉相关工具与模块的使用。

总结

如今,好多机器学习、数据挖掘的知识都逐渐成为常识,要想在竞争中脱颖而出,就必须做到

1.保持学习热情,关心热点;

2.深入学习,会用,也要理解;

3.在实战中历练总结;

4.积极参加学术界、业界的讲座分享,向牛人学习,与他人讨论。

作者:@太极儒

原文链接



part2—笔试题及答案


2013百度校园招聘数据挖掘工程师

一、简答题(30分) 1、简述数据库操作的步骤(10分)

步骤:建立数据库连接、打开数据库连接、建立数据库命令、运行数据库命令、保存数据库命令、关闭数据库连接。

经萍萍提醒,了解到应该把preparedStatement预处理也考虑在数据库的操作步骤中。此外,对实时性要求不强时,可以使用数据库缓存。

2、TCP/IP的四层结构(10分)

3、什么是MVC结构,简要介绍各层结构的作用(10分)

Model、view、control。

我之前有写过一篇《MVC层次的划分》

二、算法与程序设计(45分) 1、由a-z、0-9组成3位的字符密码,设计一个算法,列出并打印所有可能的密码组合(可用伪代码、C、C++、Java实现)(15分)

把a-z,0-9共(26+10)个字符做成一个数组,然后用三个for循环遍历即可。每一层的遍历都是从数组的第0位开始。

2、实现字符串反转函数(15分)(可用伪代码、C、C++、Java实现)

C++

#include <iostream> 
#include <string> 
using namespace std; 
void main(){     
   string s = "abcdefghijklm";    
   cout <<  s << endl;    
   int len = s.length();    
   char temp = 'a';     
   for(int i = 0; i < len/2; i++)
      { 
        temp = s[i];         
        s[i] = s[len - 1 - i];         
        s[len - 1 - i] = temp;   
       }          
        cout << s; 
 }

3、百度凤巢系统,广告客户购买一系列关键词,数据结构如下:(15分) User1 手机 智能手机 iphone 台式机 … User2 手机 iphone 笔记本电脑 三星手机 … User3 htc 平板电脑 手机 … (1)根据以上数据结构对关键词进行KMeans聚类,请列出关键词的向量表示、距离公式和KMeans算法的整体步骤

KMeans方法一个很重要的部分就是如何定义距离,而距离又牵扯到特征向量的定义,毕竟距离是对两个特征向量进行衡量。

本题中,我们建立一个table。

只要两个关键词在同一个user的描述中出现,我们就将它在相应的表格的位置加1.

这样我们就有了每个关键词的特征向量。

例如:

<手机>=(1,1,2,1,1,1,0,0)

<智能手机> = (1,1,1,1,0,0,0,0)

我们使用夹角余弦公式来计算这两个向量的距离。

夹角余弦公式:

设有两个向量a和b,

所以,cos<手机,智能机>=(1+1+2+1)/(sqrt(7+2^2)*sqrt(4))=0.75

cos<手机,iphone>=(2+1+2+1+1+1)/(sqrt(7+2^2)*sqrt(2^2+5))=0.80

夹角余弦值越大说明两者之间的夹角越小,夹角越小说明相关度越高。

通过夹角余弦值我们可以计算出每两个关键词之间的距离。

特征向量和距离计算公式的选择(还有其他很多种距离计算方式,各有其适应的应用场所)完成后,就可以进入KMeans算法。

KMeans算法有两个主要步骤:1、确定k个中心点;2、计算各个点与中心点的距离,然后贴上类标,然后针对各个类,重新计算其中心点的位置。

初始化时,可以设定k个中心点的位置为随机值,也可以全赋值为0。

KMeans的实现代码有很多,这里就不写了。

不过值得一提的是MapReduce模型并不适合计算KMeans这类递归型的算法,MR最拿手的还是流水型的算法。KMeans可以使用MPI模型很方便的计算(庆幸的是YARN中似乎开始支持MPI模型了),所以hadoop上现在也可以方便的写高效算法了(但是要是MRv2哦)。

(2)计算给定关键词与客户关键词的文字相关性,请列出关键词与客户的表达符号和计算公式

这边的文字相关性不知道是不是指非语义的相关性,而只是词频统计上的相关性?如果是语义相关的,可能还需要引入topic model来做辅助(可以看一下百度搜索研发部官方博客的这篇【语义主题计算】)……

如果是指词频统计的话,个人认为可以使用Jaccard系数来计算。

通过第一问中的表格,我们可以知道某个关键词的向量,现在将这个向量做一个简单的变化:如果某个分量不为0则记为1,表示包含这个分量元素,这样某个关键词就可以变成一些词语的集合,记为A。

客户输入的关键词列表也可以表示为一个集合,记为B

Jaccard系数的计算方法是:

所以,假设某个用户userX的关键词表达为:{三星手机,手机,平板电脑}

那么,关键词“手机”与userX的关键词之间的相关性为:

J(“手机”,“userX关键词”)=|{三星手机,手机,平板电脑}|/|{手机,智能手机,iphone,台式机,笔记本电脑,三星手机,HTC,平板电脑}| = 3/8

关键词“三星手机”与用户userX的关键词之间的相关性为:

J(“三星手机”,“userX关键词”)=|{手机,三星手机}|/|{手机,三星手机,iphone,笔记本电脑,平板电脑}| = 2/5

三、系统设计题(25分) 一维数据的拟合,给定数据集{xi,yi}(i=1,…,n),xi是训练数据,yi是对应的预期值。拟使用线性、二次、高次等函数进行拟合 线性:f(x)=ax+b 二次:f(x)=ax^2+bx+c 三次:f(x)=ax^3+bx^2+cx+d (1)请依次列出线性、二次、三次拟合的误差函数表达式(2分)

误差函数的计算公式为:

系数1/2只是为了之后求导的时候方便约掉而已。

那分别将线性、二次、三次函数带入至公式中f(xi)的位置,就可以得到它们的误差函数表达式了 (2)按照梯度下降法进行拟合,请给出具体的推导过程。(7分)

假设我们样本集的大小为m,每个样本的特征向量为X1=(x11,x12, …, x1n)。

那么整个样本集可以表示为一个矩阵:

其中每一行为一个样本向量。

我们假设系数为θ,则有系数向量:

对于第 i 个样本,我们定义误差变量为

我们可以计算cost function:

由于θ是一个n维向量,所以对每一个分量求偏导:

梯度下降的精华就在于下面这个式子:

这个式子是什么意思呢?是将系数减去导数(导数前的系数先暂时不用理会),为什么是减去导数?我们看一个二维的例子。

假设有一个曲线如图所示:

假设我们处在红色的点上,那么得到的导数是个负值。此时,我在当前位置(x轴)的基础上减去一个负值,就相当于加上了一个正值,那么就朝导数为0的位置移动了一些。

如果当前所处的位置是在最低点的右边,那么就是减去一个正值(导数为正),相当于往左移动了一些距离,也是朝着导数为0的位置移动了一些。

这就是梯度下降最本质的思想。

那么到底一次该移动多少呢?就是又导数前面的系数α来决定的。

现在我们再来看梯度下降的式子,如果写成矩阵计算的形式(使用隐式循环来实现),那么就有:

这边会有点棘手,因为j确定时,xij为一个数值(即,样本的第j个分量),Xθ-Y为一个m*1维的列向量(暂时称作“误差向量”)。

括号里面的部分就相当于:

第1个样本第j个分量*误差向量 + 第2个样本第j个分量*误差向量 + … + 第m个样本第j个分量*误差向量

我们来考察一下式子中各个部分的矩阵形式。

当j固定时,相当于对样本空间做了一个纵向切片,即:

那么此时的xij就是m*1向量,所以为了得到1*1的形式,我们需要拼凑 (1*m)*(m*1)的矩阵运算,因此有:

如果把θ向量的每个分量统一考虑,则有:

关于θ向量的不断更新的终止条件,一般以误差范围(如95%)或者迭代次数(如5000次)进行设定。

梯度下降的有点是:

不像矩阵解法那么需要空间(因为矩阵解法需要求矩阵的逆)

缺点是:如果遇上非凸函数,可能会陷入局部最优解中。对于这种情况,可以尝试几次随机的初始θ,看最后convergence时,得到的向量是否是相似的。

(3)下图给出了线性、二次和七次拟合的效果图。请说明进行数据拟合时,需要考虑哪些问题。在本例中,你选择哪种拟合函数。(8分)

因为是在网上找的题目,没有看到图片是长什么样。大致可能有如下几种情况。

如果是如上三幅图的话,当然是选择中间的模型。

欠拟合的发生一般是因为假设的模型过于简单。而过拟合的原因则是模型过于复杂且训练数据量太少。

对于欠拟合,可以增加模型的复杂性,例如引入更多的特征向量,或者高次方模型。

对于过拟合,可以增加训练的数据,又或者增加一个L2 penalty,用以约束变量的系数以实现降低模型复杂度的目的。

L2 penalty就是:

(注意不要把常数项系数也包括进来,这里假设常数项是θ0)

另外常见的penalty还有L1型的:

(L1型的主要是做稀疏化,即sparsity)

两者为什么会有这样作用上的区别可以找一下【统计之都】上的相关文章看一下。我也还没弄懂底层的原因是什么。

(4)给出实验方案(8分)

2013网易实习生招聘 岗位:数据挖掘工程师 一、问答题 a) 欠拟合和过拟合的原因分别有哪些?如何避免?

欠拟合:模型过于简单;过拟合:模型过于复杂,且训练数据太少。 b) 决策树的父节点和子节点的熵的大小?请解释原因。

父节点的熵>子节点的熵

c) 衡量分类算法的准确率,召回率,F1值。

d) 举例序列模式挖掘算法有哪些?以及他们的应用场景。

DTW(动态事件规整算法):语音识别领域,判断两端序列是否是同一个单词。

Holt-Winters(三次指数平滑法):对时间序列进行预测。时间序列的趋势、季节性。

Apriori

Generalized Sequential Pattern(广义序贯模式)

PrefixSpan

二、计算题 1) 给你一组向量a,b a) 计算二者欧氏距离

(a-b)(a-b)T

即:

b) 计算二者曼哈顿距离

2) 给你一组向量a,b,c,d a) 计算a,b的Jaccard相似系数

b) 计算c,d的向量空间余弦相似度

c) 计算c、d的皮尔森相关系数

即线性相关系数。

或者


三、(题目记得不是很清楚) 一个文档-词矩阵,给你一个变换公式tfij’=tfij*log(m/dfi);其中tfij代表单词i在文档f中的频率,m代表文档数,dfi含有单词i的文档频率。 1) 只有一个单词只存在文档中,转换的结果?(具体问题忘记)

2) 有多个单词存在在多个文档中,转换的结果?(具体问题忘记)

3) 公式变换的目的?

四、推导朴素贝叶斯分类P(c|d),文档d(由若干word组成),求该文档属于类别c的概率, 并说明公式中哪些概率可以利用训练集计算得到。

五、给你五张人脸图片。 可以抽取哪些特征?按照列出的特征,写出第一个和最后一个用户的特征向量。

六、考查ID3算法,根据天气分类outlook/temperature/humidity/windy。(给你一张离散型 的图表数据,一般学过ID3的应该都知道)

a) 哪一个属性作为第一个分类属性?

b) 画出二层决策树。

七、购物篮事物(关联规则) 一个表格:事物ID/购买项。 1) 提取出关联规则的最大数量是多少?(包括0支持度的规则)

2) 提取的频繁项集的最大长度(最小支持>0)

3) 找出能提取出4-项集的最大数量表达式 4) 找出一个具有最大支持度的项集(长度为2或更大)

5) 找出一对项a,b,使得{a}->{b}和{b}->{a}有相同置信度。

八、一个发布优惠劵的网站,如何给用户做出合适的推荐?有哪些方法?设计一个合适的系 统(线下数据处理,存放,线上如何查询?)


原文发布于微信公众号 - PPV课数据科学社区(ppvke123)

原文发表时间:2016-09-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

学界 | 跟着大神回顾ACL 2018:大会亮点一览

很高兴看到很多论文都在从方法上研究现有模型以及它们捕获的内容,而不是一直在引入更新的模型。进行这样的研究最常用的办法是自动创建一个侧重于泛化行为的某个特定方面的...

13420
来自专栏机器之心

学界 | 多 GPU 加速学习,这是一份崭新的 XGBoost 库

梯度提升是一种可以获得当前最佳性能的监督学习方法,它在分类、回归和排序方面有很好的表现。XGBoost 是一般化梯度提升算法的实现,它在多核和分布式机器上有着高...

16130
来自专栏闪电gogogo的专栏

关于压缩感知的一些小原理

 压缩感知(CompressiveSensing, or Compressed Sensing)或译为压缩传感,或者称为压缩采样(Compressive...

28070
来自专栏AI科技评论

学界 | 一言不合就想斗图?快用深度学习帮你生成表情包

AI科技评论按:斯坦福大学的两个学生 Abel L Peirson V 和 Meltem Tolunay 发表了自己的 CS224n 结业论文—— 用深度神经网...

14450
来自专栏大数据文摘

欲取代CNN的Capsule Network究竟是什么来头?它能为AI界带来革命性转折么?

18950
来自专栏机器之心

NAACL | 评价端到端生成式聊天系统,哈工大提出新型数据集 LSDSCC

得益于深度学习的发展,端到端的生成式聊天系统在模型层面的研究工作在近两到三年中取得了长足的进步 [1-5]。与之相比,对于生成结果的合理评价方法的探索则极为滞后...

15230
来自专栏范传康的专栏

基于云计算的 CV 移动交互应用研究:头部姿态估计综述(2)

导语 随便说说,其一,项目的原名是“CV移动交互应用的前后台框架”,为了高大上,起了个“云计算”;其二,这是动手写的第一篇,不过在规划里面第二篇,第一篇项目概述...

563100
来自专栏机器之心

观点 | 三大特征选择策略,有效提升你的机器学习水准

28170
来自专栏机器之心

神经图灵机深度讲解:从图灵机基本概念到可微分神经计算机

选自Talla Blog 作者:Daniel Shank 机器之心编译 参与:马亚雄、吴攀 本文作者为 Talla 公司的高级数据科学家 Daniel Shan...

42080
来自专栏AI科技大本营的专栏

深度文本匹配在智能客服中的应用

文本匹配是自然语言理解中的一个核心问题,它可以应用于大量的自然语言处理任务中,例如信息检索、问答系统、复述问题、对话系统、机器翻译等等。这些自然语言处理任务在很...

35460

扫码关注云+社区

领取腾讯云代金券