數(shù)據(jù)挖掘算法（logistic回歸，隨機(jī)森林，GBDT和xgboost）

面網(wǎng)易數(shù)據(jù)挖掘工程師崗位，第一次面數(shù)據(jù)挖掘的崗位，只想著能夠去多準(zhǔn)備一些，體驗(yàn)面這個(gè)崗位的感覺(jué)，雖然最好心有不甘告終，不過(guò)繼續(xù)加油。

不過(guò)總的來(lái)看，面試前有準(zhǔn)備永遠(yuǎn)比你沒(méi)有準(zhǔn)備要強(qiáng)好幾倍。

因?yàn)槊嬖囘^(guò)程看重的不僅是你的實(shí)習(xí)經(jīng)歷多久怎樣，更多的是看重你對(duì)基礎(chǔ)知識(shí)的掌握（即學(xué)習(xí)能力和邏輯），實(shí)際項(xiàng)目中解決問(wèn)題的能力（做了什么貢獻(xiàn)）。

先提一下奧卡姆剃刀：給定兩個(gè)具有相同泛化誤差的模型，較簡(jiǎn)單的模型比較復(fù)雜的模型更可取。以免模型過(guò)于復(fù)雜，出現(xiàn)過(guò)擬合的問(wèn)題。

如果你想面數(shù)據(jù)挖掘崗必須先了解下面這部分的基本算法理論：

我們知道，在做數(shù)學(xué)題的時(shí)候，解未知數(shù)的方法，是給定自變量和函數(shù)，通過(guò)函數(shù)處理自變量，以獲得解。而機(jī)器學(xué)習(xí)就相當(dāng)于，給定自變量和函數(shù)的解，求函數(shù)。

類(lèi)似于：這樣：function（x）=y
機(jī)器學(xué)習(xí)就是樣本中有大量的x（特征量）和y（目標(biāo)變量）然后求這個(gè)function。

求函數(shù)的方法，基于理論上來(lái)說(shuō)，大部分函數(shù)都能找到一個(gè)近似的泰勒展開(kāi)式。而機(jī)器學(xué)習(xí)，就是用數(shù)據(jù)去擬合這個(gè)所謂的“近似的泰勒展開(kāi)式”。

實(shí)際面試時(shí)很看重和考察你的理論基礎(chǔ)，所以一定一定要重視各個(gè)算法推導(dǎo)過(guò)程中的細(xì)節(jié)問(wèn)題。這里主要介紹：logistic回歸，隨機(jī)森林，GBDT和Adaboost

1.邏輯回歸

邏輯回歸從統(tǒng)計(jì)學(xué)的角度看屬于非線性回歸中的一種，它實(shí)際上是一種分類(lèi)方法，主要用于兩分類(lèi)問(wèn)題

Regression問(wèn)題的常規(guī)步驟為：
 尋找h函數(shù)（即假設(shè)估計(jì)的函數(shù)）；
 構(gòu)造J函數(shù)（損失函數(shù)）；
 想辦法使得J函數(shù)最小并求得回歸參數(shù)（θ）；
 數(shù)據(jù)擬合問(wèn)題

1）利用了Logistic函數(shù)（或稱(chēng)為Sigmoid函數(shù)），函數(shù)形式為最常見(jiàn)的

1.png

2）代價(jià)函數(shù)J
下面的代價(jià)函數(shù)J之所有前面加上1/m是為了后面”梯度下降求參數(shù)θ時(shí)更方便“，也即這里不加1/m也可以。

2.png

3.png

4.png

5.png

3）使得J函數(shù)最小并求得回歸參數(shù)（θ）
如何調(diào)整θ以使得J(θ)取得最小值有很多方法，比如最小二乘法，梯度下降也是一種，這里介紹一下梯度下降。

梯度下降是最基礎(chǔ)的一個(gè)優(yōu)化算法，學(xué)習(xí)因子就是梯度下降里的學(xué)習(xí)率，一個(gè)參數(shù)。 梯度方向表示了函數(shù)增長(zhǎng)速度最快的方向，那么和它相反的方向就是函數(shù)減少速度最快的方向了。對(duì)于機(jī)器學(xué)習(xí)模型優(yōu)化的問(wèn)題，當(dāng)我們需要求解最小值的時(shí)候，朝著梯度下降的方向走，就能找到最優(yōu)值了。 學(xué)習(xí)因子即步長(zhǎng)α的選擇對(duì)梯度下降算法來(lái)說(shuō)很重要，α過(guò)小會(huì)導(dǎo)致收斂太慢；若α太大，可能跳過(guò)最優(yōu)，從而找不到最優(yōu)解。 1）當(dāng)梯度下降到一定數(shù)值后，每次迭代的變化很小，這時(shí)可以設(shè)定一個(gè)閾值，**只要變化小于該閾值，就停止迭代，而得到的結(jié)果也近似于最優(yōu)解。** 2）若損失函數(shù)的值不斷變大，則有可能是步長(zhǎng)速率a太大，導(dǎo)致算法不收斂，這時(shí)可適當(dāng)調(diào)整a值 對(duì)于樣本數(shù)量額非常之多的情況，普通的**批量梯度下降**算法（Batch gradient descent ）會(huì)非常耗時(shí)，靠近極小值時(shí)收斂速度減慢，因?yàn)槊看蔚家憷袠颖荆@時(shí)可以選擇**隨機(jī)梯度下降算法**（Stochastic gradient descent）梯度下降**需要把m個(gè)樣本全部帶入計(jì)算**，迭代一次計(jì)算量為m\\*n^2；隨機(jī)梯度下降每次只使用一個(gè)樣本，迭代一次計(jì)算量為n^2，當(dāng)m很大的時(shí)候，隨機(jī)梯度下降迭代一次的速度要遠(yuǎn)高于梯度下降，雖然不是每次迭代得到的損失函數(shù)都向著全局最優(yōu)方向，** 但是大的整體的方向是向全局最優(yōu)解的，最終的結(jié)果往往是在全局最優(yōu)解附近。**

6.png

4）數(shù)據(jù)的擬合問(wèn)題
第一種是欠擬合，通常是因?yàn)?a href='/map/tezheng/' style='color:#000;font-size:inherit;'>特征量選少了。
第二種是我們想要的。
第三個(gè)是過(guò)擬合，通常是因?yàn)?a href='/map/tezheng/' style='color:#000;font-size:inherit;'>特征量選多了。

欠擬合的解決方法是增加特征量。
過(guò)擬合的解決方法是減少特征量或者正則化。

但是一般情況下我們又不能確定哪些特征量該去掉，所以我們就選擇正則化的方式解決過(guò)擬合。

7.png

2.決策樹(shù)

決策樹(shù)這種算法有著很多良好的特性，比如說(shuō)訓(xùn)練時(shí)間復(fù)雜度較低，預(yù)測(cè)的過(guò)程比較快速，模型容易展示。單決策樹(shù)又有一些不好的地方，比如說(shuō)容易o(hù)ver-fitting

這里首先介紹如何構(gòu)造決策樹(shù)：
（1）如何分割某一結(jié)點(diǎn)，方法有很多，分別針對(duì)二元屬性、序數(shù)屬性、連續(xù)屬性等進(jìn)行劃分。
（2）在有多個(gè)特征時(shí)，如何確定最佳的分割特征。
這里就涉及到純度的概念，若分割后的子結(jié)點(diǎn)都更偏向于一個(gè)類(lèi)，那么純度越高。

但實(shí)際中我們通常對(duì)不純度進(jìn)行度量，即不純度越小，則認(rèn)為該特征的區(qū)分度越高。
不純度的度量方式有三種：

8.png
具體的計(jì)算方法如下：

9.png

10.png

上圖10中得到多個(gè)子結(jié)點(diǎn)M1，M2的GINI或者熵后，一般通過(guò)加權(quán)平均的方法求M12;

那么增益就可以用M0-M12來(lái)表示

在決策樹(shù)算法中，通過(guò)比較劃分前后的不純度值，來(lái)確定如何分裂。ID3使用信息增益作為不純度，C4.5使用信息增益比作為不純度，CART使用基尼指數(shù)作為不純度。

信息增益為：父結(jié)點(diǎn)與所有子結(jié)點(diǎn)不純程度的差值，差越大，則增益越大，表示特征的效果越好。

有時(shí)候并不是分割的越多越好，如果某個(gè)特征產(chǎn)生了大量的劃分，它的劃分信息將會(huì)很大，此時(shí)采用信息增益率

以ID3為例，使用訓(xùn)練樣本建立決策樹(shù)時(shí)，在每一個(gè)內(nèi)部節(jié)點(diǎn)依據(jù)信息論來(lái)評(píng)估選擇哪一個(gè)屬性作為分割 的依據(jù)。對(duì)于過(guò)擬合的問(wèn)題，一般要對(duì)決策樹(shù)進(jìn)行剪枝，剪枝有兩種方法：先剪枝，后剪枝。 先剪枝說(shuō)白了就是提前結(jié)束決策樹(shù)的增長(zhǎng)，跟上述決策樹(shù)停止生長(zhǎng)的方法一樣。 后剪枝是指在決策樹(shù)生長(zhǎng)完成之后再進(jìn)行剪枝的過(guò)程。

（3）何時(shí)停止劃分。

11.png

3.隨機(jī)森林

隨機(jī)森林是一個(gè)包含多個(gè)決策樹(shù)的分類(lèi)器，構(gòu)建過(guò)程如下：
1）決策樹(shù)相當(dāng)于一個(gè)大師，通過(guò)自己在數(shù)據(jù)集中學(xué)到的知識(shí)對(duì)于新的數(shù)據(jù)進(jìn)行分類(lèi)。但是俗話(huà)說(shuō)得好，一個(gè)諸葛亮，玩不過(guò)三個(gè)臭皮匠。隨機(jī)森林就是希望構(gòu)建多個(gè)臭皮匠，希望最終的分類(lèi)效果能夠超過(guò)單個(gè)大師的一種算法。

2）那隨機(jī)森林具體如何構(gòu)建呢？有兩個(gè)方面：數(shù)據(jù)的隨機(jī)性選取，以及待選特征的隨機(jī)選取。

數(shù)據(jù)的隨機(jī)選?。?br /> 第一，從原始的數(shù)據(jù)集中采取有放回的抽樣，構(gòu)造子數(shù)據(jù)集，子數(shù)據(jù)集的數(shù)據(jù)量是和原始數(shù)據(jù)集相同的。不同子數(shù)據(jù)集的元素可以重復(fù)，同一個(gè)子數(shù)據(jù)集中的元素也可以重復(fù)。
第二，利用子數(shù)據(jù)集來(lái)構(gòu)建子決策樹(shù)，將這個(gè)數(shù)據(jù)放到每個(gè)子決策樹(shù)中，每個(gè)子決策樹(shù)輸出一個(gè)結(jié)果。最后，如果有了新的數(shù)據(jù)需要通過(guò)隨機(jī)森林得到分類(lèi)結(jié)果，就可以通過(guò)對(duì)子決策樹(shù)的判斷結(jié)果的投票，得到隨機(jī)森林的輸出結(jié)果了。如下圖，假設(shè)隨機(jī)森林中有3棵子決策樹(shù)，2棵子樹(shù)的分類(lèi)結(jié)果是A類(lèi)，1棵子樹(shù)的分類(lèi)結(jié)果是B類(lèi)，那么隨機(jī)森林的分類(lèi)結(jié)果就是A類(lèi)。

12.png

待選特征的隨機(jī)選?。?br /> 與數(shù)據(jù)集的隨機(jī)選取類(lèi)似，隨機(jī)森林中的子樹(shù)的每一個(gè)分裂過(guò)程并未用到所有的待選特征，而是從所有的待選特征中隨機(jī)選取一定的特征，之后再在隨機(jī)選取的特征中選取最優(yōu)的特征。這樣能夠使得隨機(jī)森林中的決策樹(shù)都能夠彼此不同，提升系統(tǒng)的多樣性，從而提升分類(lèi)性能。

此外，以決策樹(shù)為基函數(shù)的提升方法稱(chēng)為提升樹(shù)（boosting tree)，包括GBDT,xgboost,adaboost，這里只主要介紹GBDT和xgboost。

先說(shuō)說(shuō)bootstrap, bagging，boosting 的含義。
Bootstrap是一種有放回的抽樣方法思想。

該思想的應(yīng)用有兩方面：bagging和boosting
雖然都是有放回的抽樣，但二者的區(qū)別在于：Bagging采用有放回的均勻取樣，而B(niǎo)oosting根據(jù)錯(cuò)誤率來(lái)取樣（Boosting初始化時(shí)對(duì)每一個(gè)訓(xùn)練例賦相等的權(quán)重1／n，然后用該學(xué)算法對(duì)訓(xùn)練集訓(xùn)練t輪，每次訓(xùn)練后，對(duì)訓(xùn)練失敗的訓(xùn)練例賦以較大的權(quán)重），因此Boosting的分類(lèi)精度要優(yōu)于Bagging。Bagging的訓(xùn)練集的選擇是隨機(jī)的，各輪訓(xùn)練集之間相互獨(dú)立，而B(niǎo)oostlng的各輪訓(xùn)練集的選擇與前面各輪的學(xué)習(xí)結(jié)果有關(guān)。

4.GBDT(Gradient Boost Decision Tree 梯度提升決策樹(shù))

GBDT是以決策樹(shù)（CART）為基學(xué)習(xí)器的GB算法，是迭代樹(shù)，而不是分類(lèi)樹(shù)。
Boost是"提升"的意思，一般Boosting算法都是一個(gè)迭代的過(guò)程，每一次新的訓(xùn)練都是為了改進(jìn)上一次的結(jié)果。

GBDT的核心就在于：每一棵樹(shù)學(xué)的是之前所有樹(shù)結(jié)論和的殘差，這個(gè)殘差就是一個(gè)加預(yù)測(cè)值后能得真實(shí)值的累加量。比如A的真實(shí)年齡是18歲，但第一棵樹(shù)的預(yù)測(cè)年齡是12歲，差了6歲，即殘差為6歲。那么在第二棵樹(shù)里我們把A的年齡設(shè)為6歲去學(xué)習(xí)，如果第二棵樹(shù)真的能把A分到6歲的葉子節(jié)點(diǎn)，那累加兩棵樹(shù)的結(jié)論就是A的真實(shí)年齡；如果第二棵樹(shù)的結(jié)論是5歲，則A仍然存在1歲的殘差，第三棵樹(shù)里A的年齡就變成1歲，繼續(xù)學(xué)習(xí)。

13.png

14.png

5.xgboost

xgboos也是以（CART）為基學(xué)習(xí)器的GB算法**，但是擴(kuò)展和改進(jìn)了GDBT。相比GBDT的優(yōu)點(diǎn)有：

（1）xgboost在代價(jià)函數(shù)里自帶加入了正則項(xiàng)，用于控制模型的復(fù)雜度。

（2）xgboost在進(jìn)行節(jié)點(diǎn)的分裂時(shí)，支持各個(gè)特征多線程進(jìn)行增益計(jì)算，因此算法更快，準(zhǔn)確率也相對(duì)高一些。