2013百度校園招聘資料挖掘工程師
一、簡答題（30分）
1、簡述資料庫操作的步驟（10分）
步驟：建立資料庫連接配接、打開資料庫連接配接、建立資料庫指令、運作資料庫指令、儲存資料庫指令、關閉資料庫連接配接。
經萍萍提醒，了解到應該把preparedstatement預處理也考慮在資料庫的操作步驟中。此外，對實時性要求不強時，可以使用資料庫緩存。
2、tcp/ip的四層結構（10分）
3、什麼是mvc結構，簡要介紹各層結構的作用（10分）
model、view、control。
二、算法與程式設計（45分）
1、由a-z、0-9組成3位的字元密碼，設計一個算法，列出并列印所有可能的密碼組合（可用僞代碼、c、c++、java實作）（15分）
把a-z,0-9共（26+10）個字元做成一個數組，然後用三個for循環周遊即可。每一層的周遊都是從數組的第0位開始。
2、實作字元串反轉函數（15分）
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算法有兩個主要步驟：1、确定k個中心點；2、計算各個點與中心點的距離，然後貼上類标，然後針對各個類，重新計算其中心點的位置。
初始化時，可以設定k個中心點的位置為随機值，也可以全指派為0。
kmeans的實作代碼有很多，這裡就不寫了。
不過值得一提的是mapreduce模型并不适合計算kmeans這類遞歸型的算法，mr最拿手的還是流水型的算法。kmeans可以使用mpi模型很友善的計算（慶幸的是yarn中似乎開始支援mpi模型了），是以hadoop上現在也可以友善的寫高效算法了（但是要是mrv2哦）。
（2）計算給定關鍵詞與客戶關鍵詞的文字相關性，請列出關鍵詞與客戶的表達符号和計算公式
如果是指詞頻統計的話，個人認為可以使用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) 舉例序列模式挖掘算法有哪些？以及他們的應用場景。
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}有相同置信度。
八、一個釋出優惠劵的網站，如何給使用者做出合适的推薦？有哪些方法？設計一個合适的系
統（線下資料處理，存放，線上如何查詢？）