- 相关推荐
百度校园招聘数据挖掘工程师面试题集锦
一、简答题(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分)
#include
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分)
【百度校园招聘数据挖掘工程师面试题】相关文章：
百度校园招聘笔试题09-26
数据挖掘论文07-16
数据挖掘论文07-15
数据挖掘论文(精品)07-29
（实用）数据挖掘论文07-29
百度php面试题目09-25
数据挖掘论文常用15篇07-29
数据挖掘论文锦集(15篇)07-28
旅游管理下数据挖掘运用论文11-18
Oracle数据库DBA经典面试题02-02