百度校园招聘数据挖掘工程师面试题集锦

百度校园招聘数据挖掘工程师面试题集锦 2015013 手机版 一、简答题 (30 分 ) 1、简述数据库操作的步骤 (10 分 ) 步骤：建立数据库连接、打开数据库连接、建立数据库命令、运行数据库命令、保存数据库命令、关闭数据库连接。 经萍萍提醒，了解到应该把 处理也考虑在数据库的操作步骤中。此外，对实时性要 求不强时，可以使用数据库缓存。 2、 P 的四层结构 (10 分 ) 3、什么是 构，简要介绍各层结构的作用 (10 分 ) 我之前有写过一篇 次的划分 二、算法与程序设计 (45 分 ) 1、由 0成 3 位的字符密码，设计一个算法，列出并打印所有可能的密码组合(可用伪代码、 C、 C+、 现 )(15 分 ) 把 (26+10)个字符做成一个数组，然后用三个 环遍历即可。每一层的遍历都是从数组的第 0 位开始 。 2、实现字符串反转函数 (15 分 ) # s = (1,1,2,1,1,1,0,0) = (1,1,1,1,0,0,0,0) 我们使用夹角余弦公式来计算这两个向量的距离。 夹角余弦公式： 设有两个向量 a 和 b， 所以， 1+1+2+1)/(+22)*)= 2+1+2+1+1+1)/(+22)*2+5)=角余弦值越大说明两者之间的夹角越小，夹角越小说明相关度越高。 通过夹角余弦值我们可以计算出每两个关键词之间的距离。 特征向量和距离计算公式的选择 (还有其他很多种距离计算方式，各有其适应的应用场所 )完成后，就可以进入 法。 法有两个主要步骤： 1、确定 k 个中心点 ;2、计算各个点与中心点的距离，然后贴上类标，然后针对各个类，重新计算其中心点的位置。 初始 化时，可以设定 k 个中心点的位置为随机值，也可以全赋值为 0。 实现代码有很多，这里就不写了。 不过值得一提的是 型并不适合计算 类递归型的算法， 拿手的还是流水型的算法。 以使用 型很方便的计算 (庆幸的是 似乎开始支持 型了 )，所以 现在也可以方便的写高效算法了 (但是要是 。 (2)计算给定关键词与客户关键词的文字相关性，请列出关键词与客户的表达符号和计算公式 这边的文字相关性不知道是不是指非 语义的相关性，而只是词频统计上的相关性 ?如果是语义相关的，可能还需要引入 做辅助 (可以看一下百度搜索研发部官方博客的这篇【语义主题计算】 ) 如果是指词频统计的话，个人认为可以使用 数来计算。 通过第一问中的表格，我们可以知道某个关键词的向量，现在将这个向量做一个简单的变化：如果某个分量不为 0 则记为 1，表示包含这个分量元素，这样某个关键词就可以变成一些词语的集合，记为 A。 客户输入的关键词列表也可以表示为一个集合，记为 B 数的计算方法是： 所以，假设某个用户 关键词表达为： 三星手机，手机，平板电脑 那么，关键词 “手机 ”与 关键词之间的相关性为： J(手机 ， “)=|三星手机，手机，平板电脑 |/|手机，智能手机， 式机，笔记本电脑，三星手机， 板电脑 | = 3/8 关键词 “三星手机 ”与用户 关键词之间的相关性为： J(三星手机 ， “)=|手机，三星手机 |/|手机，三星手机， 记本电脑，平板电脑 | = 2/5 三、系统设计题 (25 分 ) 一维数据的拟合，给定数据集 xi,i=1,n) ， 训练数据， 对应的预期值。拟使用线性、二次、高次等函数进行拟合 线性： f(x)=ax+b 二次： f(x)=+bx+c 三次： f(x)=+cx+d (1)请依次列出线性、二次、三次拟合的误差函数表达式 (2 分 ) 误差函数的计算公式为： 系数 1/2 只是为了之后求导的时候方便约掉而已。 那分别将线性、二次、三次函数带入至公式中 f(位置，就可以 得到它们的误差函数表达式了。 (2)按照梯度下降法进行拟合，请给出具体的推导过程。 (7 分 ) 假设我们样本集的大小为 m，每个样本的特征向量为 ., 那么整个样本集可以表示为一个矩阵： 其中每一行为一个样本向量。 我们假设系数为 ，则有系数向量： 对于第 i 个样本，我们定义误差变量为 我们可以计算 由于 是一个 n 维向量，所以对每一个分量求偏导： 梯度下降的精华就在于下面这个式子： 这个式子是什么意思呢 ?是将系数减去导数 (导数前的系数先暂时不用理会 )，为什么是减去导数 ?我们看一个二维的例子。 假设有一个曲线如图所示： 假设我们处在红色的点上，那么得到的导数是个负值。此时，我在当前位置 (x 轴 )的基础上减去一个负值，就相当于加上了一个正值，那么就朝导数为 0 的位置移动了一些。 如果当前所处的位置是在最低点的右边，那么就是减去一个正值 (导数为正 )，相当于往左移动了一些距离，也是朝着导数为 0 的位置移动了一些。 这就是梯度下降最本质的思想。 那么到底一次该移动多少呢 ?就是又导数前面的系数 来决定的。 现在我们再来看梯度下降的式子，如果写成矩阵计算的形式 (使用隐式循环来实现 )，那么就有： 这边会有点棘手，因为 j 确定时， 一个数值 (即，样本的第 j 个分量 )， 一个m*1 维的列向量 (暂时称作 “误差向量 ”)。 括号里面的部分就相当于： 第 1 个样本第 j 个分量 *误差向量 + 第 2 个样本第 j 个分量 *误差向量 + . + 第 m 个样本第 j 个分量 *误差向量 我们来考察一下式子中各个部分的矩阵形式。 当 j 固定时，相当于对样本空间做了一个纵向切片，即： 那么此时的 是 m*1 向 量，所以为了得到 1*1 的形式，我们需要拼凑 (1*m)*(m*1)的矩阵运算，因此有： 如果把 向量的每个分量统一考虑，则有： 关于 向量的不断更新的终止条件，一般以误差范围 (如 95%)或者迭代次数 (如 5000次 )进行设定。 梯度下降的有点是： 不像矩阵解法那么需要空间 (因为矩阵解法需要求矩阵的逆 ) 缺点是：如果遇上非凸函数，可能会陷入局部最优解中。对于这种情况，可以尝试几次随机的初始 ，看最后 ，得到的向量是否是相似的。 (3)下图给出了线性、二次和七次拟合的 效果图。请说明进行数据拟合时，需要考虑哪些问题。在本例中，你选择哪种拟合函数。 (8 分 ) 因为是在网上找的题目，没有看到图片是长什么样。大致可能有如下几种情况。 如果是如上三幅图的话，当然是选择中间的模型。 欠拟合的发生一般是因为假设的模型过于简单。而过拟合的原因则是模型过于复杂且训练数据量太少。 对于欠拟合，可以增加模型的复杂性，例如引入更多的特征向量，或者高次方模型。 对于过拟合，可以增加训练的数据，又或者增加一个 L2 以约束变量