- 相關推薦
百度校園招聘數據挖掘工程師面試題集錦
一、簡答題(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循環(huán)遍歷即可。每一層的遍歷都是從數組的第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來做輔助(可以看一下百度搜索研發(fā)部官方博客的這篇【語義主題計算】)……
如果是指詞頻統計的話，個人認為可以使用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的位置移動了一些。
這就是梯度下降最本質的思想。
那么到底一次該移動多少呢?就是又導數前面的系數α來決定的。
現在我們再來看梯度下降的式子，如果寫成矩陣計算的形式(使用隱式循環(huán)來實現)，那么就有：
這邊會有點棘手，因為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次)進行設定。
梯度下降的有點是：
不像矩陣解法那么需要空間(因為矩陣解法需要求矩陣的逆)
缺點是：如果遇上非凸函數，可能會陷入局部最優(yōu)解中。對于這種情況，可以嘗試幾次隨機的初始θ，看最后convergence時，得到的向量是否是相似的。
(3)下圖給出了線性、二次和七次擬合的效果圖。請說明進行數據擬合時，需要考慮哪些問題。在本例中，你選擇哪種擬合函數。(8分)
因為是在網上找的題目，沒有看到圖片是長什么樣。大致可能有如下幾種情況。
如果是如上三幅圖的話，當然是選擇中間的模型。
欠擬合的發(fā)生一般是因為假設的模型過于簡單。而過擬合的原因則是模型過于復雜且訓練數據量太少。
對于欠擬合，可以增加模型的復雜性，例如引入更多的特征向量，或者高次方模型。
對于過擬合，可以增加訓練的數據，又或者增加一個L2 penalty，用以約束變量的系數以實現降低模型復雜度的目的。
L2 penalty就是：
(注意不要把常數項系數也包括進來，這里假設常數項是θ0)
另外常見的penalty還有L1型的：
(L1型的主要是做稀疏化，即sparsity)
兩者為什么會有這樣作用上的區(qū)別可以找一下【統計之都】上的相關文章看一下。我也還沒弄懂底層的原因是什么。
(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