9.25r早上面網(wǎng)易數(shù)據(jù)挖掘工程師崗位，第一次面數(shù)據(jù)挖掘的崗位，只想著能夠去多準(zhǔn)備一些，體驗(yàn)面這個崗位的感覺，雖然最好心有不甘告終，不過繼續(xù)加油。
不過總的來看，面試前有準(zhǔn)備永遠(yuǎn)比你沒有準(zhǔn)備要強(qiáng)好幾倍。
因?yàn)槊嬖囘^程看重的不僅是你的實(shí)習(xí)經(jīng)歷多久怎樣，更多的是看重你對基礎(chǔ)知識的掌握（即學(xué)習(xí)能力和邏輯），實(shí)際項(xiàng)目中解決問題的能力（做了什么貢獻(xiàn)）。
先提一下奧卡姆剃刀：給定兩個具有相同泛化誤差的模型，較簡單的模型比較復(fù)雜的模型更可取。以免模型過于復(fù)雜，出現(xiàn)過擬合的問題。
如果你想面數(shù)據(jù)挖掘崗必須先了解下面這部分的基本算法理論：
我們知道，在做數(shù)學(xué)題的時候，解未知數(shù)的方法，是給定自變量和函數(shù)，通過函數(shù)處理自變量，以獲得解。而機(jī)器學(xué)習(xí)就相當(dāng)于，給定自變量和函數(shù)的解，求函數(shù)。
類似于：這樣：function（x）=y
機(jī)器學(xué)習(xí)就是樣本中有大量的x（特征量）和y（目標(biāo)變量）然后求這個function。（了解更多可以看： https://zhuanlan.zhihu.com/p/21340974?refer=mlearn ）
求函數(shù)的方法，基于理論上來說，大部分函數(shù)都能找到一個近似的泰勒展開式。而機(jī)器學(xué)習(xí)，就是用數(shù)據(jù)去擬合這個所謂的“近似的泰勒展開式”。
實(shí)際面試時很看重和考察你的理論基礎(chǔ)，所以一定一定要重視各個算法推導(dǎo)過程中的細(xì)節(jié)問題。這里主要介紹：logistic回歸，隨機(jī)森林，GBDT和Adaboost
1.邏輯回歸
邏輯回歸從統(tǒng)計(jì)學(xué)的角度看屬于非線性回歸中的一種，它實(shí)際上是一種分類方法，主要用于兩分類問題
Regression問題的常規(guī)步驟為：
尋找h函數(shù)（即假設(shè)估計(jì)的函數(shù)）；
構(gòu)造J函數(shù)（損失函數(shù)）；
想辦法使得J函數(shù)最小并求得回歸參數(shù)（θ）；
數(shù)據(jù)擬合問題
1）利用了Logistic函數(shù)（或稱為Sigmoid函數(shù)），函數(shù)形式為最常見的
2）代價函數(shù)J
下面的代價函數(shù)J之所有前面加上1/m是為了后面”梯度下降求參數(shù)θ時更方便“，也即這里不加1/m也可以。
3）使得J函數(shù)最小并求得回歸參數(shù)（θ）
如何調(diào)整θ以使得J(θ)取得最小值有很多方法，比如最小二乘法，梯度下降也是一種，這里介紹一下梯度下降。
梯度下降是最基礎(chǔ)的一個優(yōu)化算法，學(xué)習(xí)因子就是梯度下降里的學(xué)習(xí)率，一個參數(shù)。
梯度方向表示了函數(shù)增長速度最快的方向，那么和它相反的方向就是函數(shù)減少速度最快的方向了。對于機(jī)器學(xué)習(xí)模型優(yōu)化的問題，當(dāng)我們需要求解最小值的時候，朝著梯度下降的方向走，就能找到最優(yōu)值了。
學(xué)習(xí)因子即步長α的選擇對梯度下降算法來說很重要，α過小會導(dǎo)致收斂太慢；若α太大，可能跳過最優(yōu)，從而找不到最優(yōu)解。
1）當(dāng)梯度下降到一定數(shù)值后，每次迭代的變化很小，這時可以設(shè)定一個閾值，**只要變化小于該閾值，就停止迭代，而得到的結(jié)果也近似于最優(yōu)解。**
2）若損失函數(shù)的值不斷變大，則有可能是步長速率a太大，導(dǎo)致算法不收斂，這時可適當(dāng)調(diào)整a值
對于樣本數(shù)量額非常之多的情況，普通的**批量梯度下降**算法（Batch gradient descent ）會非常耗時，靠近極小值時收斂速度減慢，因?yàn)槊看蔚家憷袠颖?，這時可以選擇**隨機(jī)梯度下降算法**（Stochastic gradient descent）
梯度下降**需要把m個樣本全部帶入計(jì)算**，迭代一次計(jì)算量為m\\*n^2；隨機(jī)梯度下降每次只使用一個樣本，迭代一次計(jì)算量為n^2，當(dāng)m很大的時候，隨機(jī)梯度下降迭代一次的速度要遠(yuǎn)高于梯度下降，雖然不是每次迭代得到的損失函數(shù)都向著全局最優(yōu)方向，** 但是大的整體的方向是向全局最優(yōu)解的，最終的結(jié)果往往是在全局最優(yōu)解附近。**
4）數(shù)據(jù)的擬合問題
第一種是欠擬合，通常是因?yàn)樘卣髁窟x少了。
第二種是我們想要的。
第三個是過擬合，通常是因?yàn)樘卣髁窟x多了。
欠擬合的解決方法是增加特征量。
過擬合的解決方法是減少特征量或者正則化。
但是一般情況下我們又不能確定哪些特征量該去掉，所以我們就選擇正則化的方式解決過擬合。
2.決策樹
決策樹這種算法有著很多良好的特性，比如說訓(xùn)練時間復(fù)雜度較低，預(yù)測的過程比較快速，模型容易展示。單決策樹又有一些不好的地方，比如說容易o(hù)ver-fitting
這里首先介紹如何構(gòu)造決策樹：
（1）如何分割某一結(jié)點(diǎn)，方法有很多，分別針對二元屬性、序數(shù)屬性、連續(xù)屬性等進(jìn)行劃分。
（2）在有多個特征時，如何確定最佳的分割特征。
這里就涉及到純度的概念，若分割后的子結(jié)點(diǎn)都更偏向于一個類，那么純度越高。
但實(shí)際中我們通常對不純度進(jìn)行度量，即不純度越小，則認(rèn)為該特征的區(qū)分度越高。
不純度的度量方式有三種：
具體的計(jì)算方法如下：
上圖10中得到多個子結(jié)點(diǎn)M1，M2的GINI或者熵后，一般通過加權(quán)平均的方法求M12;
那么增益就可以用M0-M12來表示
在決策樹算法中，通過比較劃分前后的不純度值，來確定如何分裂。ID3使用信息增益作為不純度，C4.5使用信息增益比作為不純度，CART使用基尼指數(shù)作為不純度。
信息增益為：父結(jié)點(diǎn)與所有子結(jié)點(diǎn)不純程度的差值，差越大，則增益越大，表示特征的效果越好。
-
有時候并不是分割的越多越好，如果某個特征產(chǎn)生了大量的劃分，它的劃分信息將會很大，此時采用信息增益率
以ID3為例，使用訓(xùn)練樣本建立決策樹時，在每一個內(nèi)部節(jié)點(diǎn)依據(jù)信息論來評估選擇哪一個屬性作為分割 的依據(jù)。對于過擬合的問題，一般要對決策樹進(jìn)行剪枝，剪枝有兩種方法：先剪枝，后剪枝。 先剪枝說白了就是提前結(jié)束決策樹的增長，跟上述決策樹停止生長的方法一樣。 后剪枝是指在決策樹生長完成之后再進(jìn)行剪枝的過程。
（3）何時停止劃分。
3.隨機(jī)森林
隨機(jī)森林是一個包含多個決策樹的分類器，構(gòu)建過程如下：
1）決策樹相當(dāng)于一個大師，通過自己在數(shù)據(jù)集中學(xué)到的知識對于新的數(shù)據(jù)進(jìn)行分類。但是俗話說得好，一個諸葛亮，玩不過三個臭皮匠。隨機(jī)森林就是希望構(gòu)建多個臭皮匠，希望最終的分類效果能夠超過單個大師的一種算法。
2）那隨機(jī)森林具體如何構(gòu)建呢？有兩個方面：數(shù)據(jù)的隨機(jī)性選取，以及待選特征的隨機(jī)選取。
-
數(shù)據(jù)的隨機(jī)選?。?/strong>
第一，從原始的數(shù)據(jù)集中采取有放回的抽樣，構(gòu)造子數(shù)據(jù)集，子數(shù)據(jù)集的數(shù)據(jù)量是和原始數(shù)據(jù)集相同的。不同子數(shù)據(jù)集的元素可以重復(fù)，同一個子數(shù)據(jù)集中的元素也可以重復(fù)。
第二，利用子數(shù)據(jù)集來構(gòu)建子決策樹，將這個數(shù)據(jù)放到每個子決策樹中，每個子決策樹輸出一個結(jié)果。最后，如果有了新的數(shù)據(jù)需要通過隨機(jī)森林得到分類結(jié)果，就可以通過對子決策樹的判斷結(jié)果的投票，得到隨機(jī)森林的輸出結(jié)果了。如下圖，假設(shè)隨機(jī)森林中有3棵子決策樹，2棵子樹的分類結(jié)果是A類，1棵子樹的分類結(jié)果是B類，那么隨機(jī)森林的分類結(jié)果就是A類。
-
待選特征的隨機(jī)選?。?/strong>
與數(shù)據(jù)集的隨機(jī)選取類似，隨機(jī)森林中的子樹的每一個分裂過程并未用到所有的待選特征，而是從所有的待選特征中隨機(jī)選取一定的特征，之后再在隨機(jī)選取的特征中選取最優(yōu)的特征。這樣能夠使得隨機(jī)森林中的決策樹都能夠彼此不同，提升系統(tǒng)的多樣性，從而提升分類性能。
此外，以決策樹為基函數(shù)的提升方法稱為提升樹（boosting tree)，包括GBDT,xgboost,adaboost，這里只主要介紹GBDT和xgboost。
先說說bootstrap, bagging，boosting 的含義。
Bootstrap是一種有放回的抽樣方法思想。
該思想的應(yīng)用有兩方面：bagging和boosting
雖然都是有放回的抽樣，但二者的區(qū)別在于：Bagging采用有放回的均勻取樣，而Boosting根據(jù)錯誤率來取樣（Boosting初始化時對每一個訓(xùn)練例賦相等的權(quán)重1／n，然后用該學(xué)算法對訓(xùn)練集訓(xùn)練t輪，每次訓(xùn)練后，對訓(xùn)練失敗的訓(xùn)練例賦以較大的權(quán)重），因此Boosting的分類精度要優(yōu)于Bagging。Bagging的訓(xùn)練集的選擇是隨機(jī)的，各輪訓(xùn)練集之間相互獨(dú)立，而Boostlng的各輪訓(xùn)練集的選擇與前面各輪的學(xué)習(xí)結(jié)果有關(guān)。
4.GBDT(Gradient Boost Decision Tree 梯度提升決策樹)
GBDT是以決策樹（CART）為基學(xué)習(xí)器的GB算法，是迭代樹，而不是分類樹。
Boost是"提升"的意思，一般Boosting算法都是一個迭代的過程，每一次新的訓(xùn)練都是為了改進(jìn)上一次的結(jié)果。
GBDT的核心就在于：每一棵樹學(xué)的是之前所有樹結(jié)論和的殘差，這個殘差就是一個加預(yù)測值后能得真實(shí)值的累加量。比如A的真實(shí)年齡是18歲，但第一棵樹的預(yù)測年齡是12歲，差了6歲，即殘差為6歲。那么在第二棵樹里我們把A的年齡設(shè)為6歲去學(xué)習(xí)，如果第二棵樹真的能把A分到6歲的葉子節(jié)點(diǎn)，那累加兩棵樹的結(jié)論就是A的真實(shí)年齡；如果第二棵樹的結(jié)論是5歲，則A仍然存在1歲的殘差，第三棵樹里A的年齡就變成1歲，繼續(xù)學(xué)習(xí)。
5.xgboost
xgboos也是以（CART）為基學(xué)習(xí)器的GB算法**，但是擴(kuò)展和改進(jìn)了GDBT。相比GBDT的優(yōu)點(diǎn)有：
（1）xgboost在代價函數(shù)里自帶加入了正則項(xiàng)，用于控制模型的復(fù)雜度。
（2）xgboost在進(jìn)行節(jié)點(diǎn)的分裂時，支持各個特征多線程進(jìn)行增益計(jì)算，因此算法更快，準(zhǔn)確率也相對高一些。
