百度校園招聘數(shù)據(jù)挖掘工程師面試題集錦

百度校園招聘數(shù)據(jù)挖掘工程師面試題集錦 2015013 手機版 一、簡答題 (30 分 ) 1、簡述數(shù)據(jù)庫操作的步驟 (10 分 ) 步驟：建立數(shù)據(jù)庫連接、打開數(shù)據(jù)庫連接、建立數(shù)據(jù)庫命令、運行數(shù)據(jù)庫命令、保存數(shù)據(jù)庫命令、關(guān)閉數(shù)據(jù)庫連接。 經(jīng)萍萍提醒，了解到應(yīng)該把 處理也考慮在數(shù)據(jù)庫的操作步驟中。此外，對實時性要 求不強時，可以使用數(shù)據(jù)庫緩存。 2、 P 的四層結(jié)構(gòu) (10 分 ) 3、什么是 構(gòu)，簡要介紹各層結(jié)構(gòu)的作用 (10 分 ) 我之前有寫過一篇 次的劃分 二、算法與程序設(shè)計 (45 分 ) 1、由 0成 3 位的字符密碼，設(shè)計一個算法，列出并打印所有可能的密碼組合(可用偽代碼、 C、 C+、 現(xiàn) )(15 分 ) 把 (26+10)個字符做成一個數(shù)組，然后用三個 環(huán)遍歷即可。每一層的遍歷都是從數(shù)組的第 0 位開始 。 2、實現(xiàn)字符串反轉(zhuǎn)函數(shù) (15 分 ) # s = (1,1,2,1,1,1,0,0) = (1,1,1,1,0,0,0,0) 我們使用夾角余弦公式來計算這兩個向量的距離。 夾角余弦公式： 設(shè)有兩個向量 a 和 b， 所以， 1+1+2+1)/(+22)*)= 2+1+2+1+1+1)/(+22)*2+5)=角余弦值越大說明兩者之間的夾角越小，夾角越小說明相關(guān)度越高。 通過夾角余弦值我們可以計算出每兩個關(guān)鍵詞之間的距離。 特征向量和距離計算公式的選擇 (還有其他很多種距離計算方式，各有其適應(yīng)的應(yīng)用場所 )完成后，就可以進入 法。 法有兩個主要步驟： 1、確定 k 個中心點 ;2、計算各個點與中心點的距離，然后貼上類標，然后針對各個類，重新計算其中心點的位置。 初始 化時，可以設(shè)定 k 個中心點的位置為隨機值，也可以全賦值為 0。 實現(xiàn)代碼有很多，這里就不寫了。 不過值得一提的是 型并不適合計算 類遞歸型的算法， 拿手的還是流水型的算法。 以使用 型很方便的計算 (慶幸的是 似乎開始支持 型了 )，所以 現(xiàn)在也可以方便的寫高效算法了 (但是要是 。 (2)計算給定關(guān)鍵詞與客戶關(guān)鍵詞的文字相關(guān)性，請列出關(guān)鍵詞與客戶的表達符號和計算公式 這邊的文字相關(guān)性不知道是不是指非 語義的相關(guān)性，而只是詞頻統(tǒng)計上的相關(guān)性 ?如果是語義相關(guān)的，可能還需要引入 做輔助 (可以看一下百度搜索研發(fā)部官方博客的這篇【語義主題計算】 ) 如果是指詞頻統(tǒng)計的話，個人認為可以使用 數(shù)來計算。 通過第一問中的表格，我們可以知道某個關(guān)鍵詞的向量，現(xiàn)在將這個向量做一個簡單的變化：如果某個分量不為 0 則記為 1，表示包含這個分量元素，這樣某個關(guān)鍵詞就可以變成一些詞語的集合，記為 A。 客戶輸入的關(guān)鍵詞列表也可以表示為一個集合，記為 B 數(shù)的計算方法是： 所以，假設(shè)某個用戶 關(guān)鍵詞表達為： 三星手機，手機，平板電腦 那么，關(guān)鍵詞 “手機 ”與 關(guān)鍵詞之間的相關(guān)性為： J(手機 ， “)=|三星手機，手機，平板電腦 |/|手機，智能手機， 式機，筆記本電腦，三星手機， 板電腦 | = 3/8 關(guān)鍵詞 “三星手機 ”與用戶 關(guān)鍵詞之間的相關(guān)性為： J(三星手機 ， “)=|手機，三星手機 |/|手機，三星手機， 記本電腦，平板電腦 | = 2/5 三、系統(tǒng)設(shè)計題 (25 分 ) 一維數(shù)據(jù)的擬合，給定數(shù)據(jù)集 xi,i=1,n) ， 訓練數(shù)據(jù)， 對應(yīng)的預期值。擬使用線性、二次、高次等函數(shù)進行擬合 線性： f(x)=ax+b 二次： f(x)=+bx+c 三次： f(x)=+cx+d (1)請依次列出線性、二次、三次擬合的誤差函數(shù)表達式 (2 分 ) 誤差函數(shù)的計算公式為： 系數(shù) 1/2 只是為了之后求導的時候方便約掉而已。 那分別將線性、二次、三次函數(shù)帶入至公式中 f(位置，就可以 得到它們的誤差函數(shù)表達式了。 (2)按照梯度下降法進行擬合，請給出具體的推導過程。 (7 分 ) 假設(shè)我們樣本集的大小為 m，每個樣本的特征向量為 ., 那么整個樣本集可以表示為一個矩陣： 其中每一行為一個樣本向量。 我們假設(shè)系數(shù)為 ，則有系數(shù)向量： 對于第 i 個樣本，我們定義誤差變量為 我們可以計算 由于 是一個 n 維向量，所以對每一個分量求偏導： 梯度下降的精華就在于下面這個式子： 這個式子是什么意思呢 ?是將系數(shù)減去導數(shù) (導數(shù)前的系數(shù)先暫時不用理會 )，為什么是減去導數(shù) ?我們看一個二維的例子。 假設(shè)有一個曲線如圖所示： 假設(shè)我們處在紅色的點上，那么得到的導數(shù)是個負值。此時，我在當前位置 (x 軸 )的基礎(chǔ)上減去一個負值，就相當于加上了一個正值，那么就朝導數(shù)為 0 的位置移動了一些。 如果當前所處的位置是在最低點的右邊，那么就是減去一個正值 (導數(shù)為正 )，相當于往左移動了一些距離，也是朝著導數(shù)為 0 的位置移動了一些。 這就是梯度下降最本質(zhì)的思想。 那么到底一次該移動多少呢 ?就是又導數(shù)前面的系數(shù) 來決定的。 現(xiàn)在我們再來看梯度下降的式子，如果寫成矩陣計算的形式 (使用隱式循環(huán)來實現(xiàn) )，那么就有： 這邊會有點棘手，因為 j 確定時， 一個數(shù)值 (即，樣本的第 j 個分量 )， 一個m*1 維的列向量 (暫時稱作 “誤差向量 ”)。 括號里面的部分就相當于： 第 1 個樣本第 j 個分量 *誤差向量 + 第 2 個樣本第 j 個分量 *誤差向量 + . + 第 m 個樣本第 j 個分量 *誤差向量 我們來考察一下式子中各個部分的矩陣形式。 當 j 固定時，相當于對樣本空間做了一個縱向切片，即： 那么此時的 是 m*1 向 量，所以為了得到 1*1 的形式，我們需要拼湊 (1*m)*(m*1)的矩陣運算，因此有： 如果把 向量的每個分量統(tǒng)一考慮，則有： 關(guān)于 向量的不斷更新的終止條件，一般以誤差范圍 (如 95%)或者迭代次數(shù) (如 5000次 )進行設(shè)定。 梯度下降的有點是： 不像矩陣解法那么需要空間 (因為矩陣解法需要求矩陣的逆 ) 缺點是：如果遇上非凸函數(shù)，可能會陷入局部最優(yōu)解中。對于這種情況，可以嘗試幾次隨機的初始 ，看最后 ，得到的向量是否是相似的。 (3)下圖給出了線性、二次和七次擬合的 效果圖。請說明進行數(shù)據(jù)擬合時，需要考慮哪些問題。在本例中，你選擇哪種擬合函數(shù)。 (8 分 ) 因為是在網(wǎng)上找的題目，沒有看到圖片是長什么樣。大致可能有如下幾種情況。 如果是如上三幅圖的話，當然是選擇中間的模型。 欠擬合的發(fā)生一般是因為假設(shè)的模型過于簡單。而過擬合的原因則是模型過于復雜且訓練數(shù)據(jù)量太少。 對于欠擬合，可以增加模型的復雜性，例如引入更多的特征向量，或者高次方模型。 對于過擬合，可以增加訓練的數(shù)據(jù)，又或者增加一個 L2 以約束變量