機器學習面試幹貨精講

序言

本文盡可能的不涉及到繁雜的數學公式，把面試中常問的模型核心點，用比較通俗易懂但又不是專業性的語言進行描述。

希望可以幫助大家在找工作時提綱挈領的複習最核心的内容，或是在準備的過程中抓住每個模型的重點。

實戰環境說明：

Python 2.7；
Sklearn 0.19.0；
graphviz 0.8.1 決策樹可視化。

一、決策樹

▌1.1 原理

顧名思義，決策樹就是用一棵樹來表示我們的整個決策過程。這棵樹可以是二叉樹（比如 CART 隻能是二叉樹），也可以是多叉樹（比如 ID3、C4.5 可以是多叉樹或二叉樹）。

根節點包含整個樣本集，每個葉節都對應一個決策結果（注意，不同的葉節點可能對應同一個決策結果），每一個内部節點都對應一次決策過程或者說是一次屬性測試。從根節點到每個葉節點的路徑對應一個判定測試序列。

舉個例子：

就像上面這個例子，訓練集由三個特征：outlook(天氣)，humidity（濕度），windy（是否有風）。

那麼我們該如何選擇特征對訓練集進行劃分那？連續型特征（比如濕度）劃分的門檻值又是如何确定的？

決策樹的生成就是不斷的選擇最優的特征對訓練集進行劃分，是一個遞歸的過程。遞歸傳回的條件有三種：

（1）目前節點包含的樣本屬于同一類别，無需劃分；

（2）目前屬性集為空，或所有樣本在屬性集上取值相同，無法劃分；

（3）目前節點包含樣本集合為空，無法劃分。

1.2 ID3、C4.5、CART

這三個是非常著名的決策樹算法。簡單粗暴來說，ID3 使用資訊增益作為選擇特征的準則；C4.5 使用資訊增益比作為選擇特征的準則；CART 使用 Gini 指數作為選擇特征的準則。

ID3

熵表示的是資料中包含的資訊量大小。熵越小，資料的純度越高，也就是說資料越趨于一緻，這是我們希望的劃分之後每個子節點的樣子。

資訊增益 = 劃分前熵 - 劃分後熵

。資訊增益越大，則意味着使用屬性 a 來進行劃分所獲得的 “純度提升” 越大 **。也就是說，用屬性 a 來劃分訓練集，得到的結果中純度比較高。

ID3 僅僅适用于二分類問題。ID3 僅僅能夠處理離散屬性。

C4.5

C4.5 克服了 ID3 僅僅能夠處理離散屬性的問題，以及資訊增益偏向選擇取值較多特征的問題，使用資訊增益比來選擇特征。

資訊增益比 = 資訊增益 / 劃分前熵

選擇資訊增益比最大的作為最優特征。

C4.5 處理連續特征是先将特征取值排序，以連續兩個值中間值作為劃分标準。嘗試每一種劃分，并計算修正後的資訊增益，選擇資訊增益最大的分裂點作為該屬性的分裂點。

CART

CART 與 ID3，C4.5 不同之處在于 CART 生成的樹必須是二叉樹。也就是說，無論是回歸還是分類問題，無論特征是離散的還是連續的，無論屬性取值有多個還是兩個，内部節點隻能根據屬性值進行二分。

CART 的全稱是分類與回歸樹。從這個名字中就應該知道，CART 既可以用于分類問題，也可以用于回歸問題。

回歸樹中，使用平方誤差最小化準則來選擇特征并進行劃分。每一個葉子節點給出的預測值，是劃分到該葉子節點的所有樣本目标值的均值，這樣隻是在給定劃分的情況下最小化了平方誤差。

要确定最優化分，還需要周遊所有屬性，以及其所有的取值來分别嘗試劃分并計算在此種劃分情況下的最小平方誤差，選取最小的作為此次劃分的依據。由于回歸樹生成使用平方誤差最小化準則，是以又叫做最小二乘回歸樹。

分類樹種，使用 Gini 指數最小化準則來選擇特征并進行劃分；

Gini 指數表示集合的不确定性，或者是不純度。基尼指數越大，集合不确定性越高，不純度也越大。這一點和熵類似。另一種了解基尼指數的思路是，基尼指數是為了最小化誤分類的機率。

▌1.3 資訊增益 vs 資訊增益比

之是以引入了資訊增益比，是由于資訊增益的一個缺點。那就是：資訊增益總是偏向于選擇取值較多的屬性。資訊增益比在此基礎上增加了一個罰項，解決了這個問題。

▌1.4 Gini 指數 vs 熵

既然這兩個都可以表示資料的不确定性，不純度。那麼這兩個有什麼差別那？

Gini 指數的計算不需要對數運算，更加高效；
Gini 指數更偏向于連續屬性，熵更偏向于離散屬性。

▌1.5 剪枝

決策樹算法很容易過拟合（overfitting），剪枝算法就是用來防止決策樹過拟合，提高泛華性能的方法。

剪枝分為預剪枝與後剪枝。

預剪枝是指在決策樹的生成過程中，對每個節點在劃分前先進行評估，若目前的劃分不能帶來泛化性能的提升，則停止劃分，并将目前節點标記為葉節點。

後剪枝是指先從訓練集生成一顆完整的決策樹，然後自底向上對非葉節點進行考察，若将該節點對應的子樹替換為葉節點，能帶來泛化性能的提升，則将該子樹替換為葉節點。

那麼怎麼來判斷是否帶來泛化性能的提升那？最簡單的就是留出法，即預留一部分資料作為驗證集來進行性能評估。

▌1.6 總結

決策樹算法主要包括三個部分：特征選擇、樹的生成、樹的剪枝。常用算法有 ID3、C4.5、CART。

特征選擇。特征選擇的目的是選取能夠對訓練集分類的特征。特征選擇的關鍵是準則：資訊增益、資訊增益比、Gini 指數；
決策樹的生成。通常是利用資訊增益最大、資訊增益比最大、Gini 指數最小作為特征選擇的準則。從根節點開始，遞歸的生成決策樹。相當于是不斷選取局部最優特征，或将訓練集分割為基本能夠正确分類的子集；
決策樹的剪枝。決策樹的剪枝是為了防止樹的過拟合，增強其泛化能力。包括預剪枝和後剪枝。

二、随機森林（Random Forest）

要說随機森林就要先說 Bagging，要說 Bagging 就要先說內建學習。

▌2.1 內建學習方法

內建學習（ensemble learning）通過建構并組合多個學習器來完成學習任務。內建學習通過将多個學習器進行結合，常獲得比單一學習器顯著優越的泛化性能。

根據個體學習器是否是同類型的學習器（由同一個算法生成，比如 C4.5,BP 等），分為同質和異質。同質的個體學習器又叫做基學習器，而異質的個體學習器則直接成為個體學習器。

原則：要獲得比單一學習器更好的性能，個體學習器應該好而不同。即個體學習器應該具有一定的準确性，不能差于弱學習器，并且具有多樣性，即學習器之間有差異。

根據個體學習器的生成方式，目前內建學習分為兩大類：

個體學習器之間存在強依賴關系、必須串行生成的序列化方法。代表是 Boosting；
個體學習器之間不存在強依賴關系、可同時生成的并行化方法。代表是 Bagging 和随機森林（Random Forest）。

▌2.2 Bagging

前面提到，想要內建算法獲得性能的提升，個體學習器應該具有獨立性。雖然 “獨立” 在現實生活中往往無法做到，但是可以設法讓基學習器盡可能的有較大的差異。

Bagging 給出的做法就是對訓練集進行采樣，産生出若幹個不同的子集，再從每個訓練子集中訓練一個基學習器。由于訓練資料不同，我們的基學習器可望具有較大的差異。

Bagging 是并行式內建學習方法的代表，采樣方法是自助采樣法，用的是有放回的采樣。初始訓練集中大約有 63.2% 的資料出現在采樣集中。

Bagging 在預測輸出進行結合時，對于分類問題，采用簡單投票法；對于回歸問題，采用簡單平均法。

Bagging 優點：

高效。Bagging 內建與直接訓練基學習器的複雜度同階；
Bagging 能不經修改的适用于多分類、回歸任務；
包外估計。使用剩下的樣本作為驗證集進行包外估計（out-of-bag estimate）。

Bagging 主要關注降低方差。（low variance）

▌2.3 随機森林（Random Forest）

2.3.1 原理

随機森林（Random Forest）是 Bagging 的一個變體。Ramdon Forest 在以決策樹為基學習器建構 Bagging 內建的基礎上，進一步在決策樹的訓練過程中引入随機屬性選擇。

原來決策樹從所有屬性中，選擇最優屬性。Ramdom Forest 的每一顆決策樹中的每一個節點，先從該節點的屬性集中随機選擇 K 個屬性的子集，然後從這個屬性子集中選擇最優屬性進行劃分。

K 控制了随機性的引入程度，是一個重要的超參數。

預測：

分類：簡單投票法；
回歸：簡單平均法。

2.3.2 優缺點

優點：

由于每次不再考慮全部的屬性，而是一個屬性子集，是以相比于 Bagging 計算開銷更小，訓練效率更高；
由于增加了屬性的擾動，随機森林中基學習器的性能降低，使得在随機森林在起始時候性能較差，但是随着基學習器的增多，随機森林通常會收斂于更低的泛化誤差，相比于 Bagging；
兩個随機性的引入，使得随機森林不容易陷入過拟合，具有很好的抗噪聲能力；
對資料的适應能力強，可以處理離散和連續的，無需要規範化；
可以得到變量的重要性，基于 oob 誤分類率和基于 Gini 系數的變化。

缺點：

在噪聲較大的時候容易過拟合。

三、AdaBoost

AdaBoost 是 Boosting 的代表，前面我們提到 Boosting 是內建學習中非常重要的一類串行化學習方法。

▌3.1 Boosting

Boosting 是指個體學習器之間存在強依賴關系，必須串行序列化生成的內建學習方法。他的思想來源是三個臭皮匠頂個諸葛亮。Boosting 意為提升，意思是希望将每個弱學習器提升為強學習器。

工作機制如下：

先從初始訓練集中學習一個基學習器；
根據基學習器的表現對訓練樣本分布進行調整，使得先前基學習器做錯的訓練樣本在後續收到更多關注；
基于調整後的樣本分布來訓練下一個基學習器；
如此反複，直到基學習器數目達到 T，最終将這 T 個基學習器進行權重結合。

對訓練樣本分布調整，主要是通過增加誤分類樣本的權重，降低正确分類樣本的權重。

Boosting 關注的主要是降低偏差。（low bias）

▌3.2 AdaBoost 原理

面臨兩個問題：

（1）在每一輪，如何改變訓練資料的機率分布或者權值分布。（也可以重采樣，但是 AdaBoost 沒這麼做）；

（2）如何将弱分類器組合成強分類器。

AdaBoost 的做法：

（1）提高那些被前一輪弱分類器錯誤分類樣本的權值，降低那些被正确分類的樣本的權值。這樣一來，那些沒有得到正确分類的資料，由于其權值的加大而受到後一輪弱分類器的關注；

（2）采用權重多數表決。具體的，加大分類錯誤率低的分類器的權值，使其在表決中起較大作用，減少分類誤差率大的弱分類器的權值，使其在表決中起較小作用。

弱分類器被線性組合成為一個強分類器。

訓練目标：

最小化指數損失函數。

三部分組成：

（1）分類器權重更新公式；

（2）樣本分布（也就是樣本權重）更新公式；

（3）加性模型。最小化指數損失函數。

▌3.3 AdaBoost 優缺點

不改變所給的訓練資料，而不斷改變訓練資料的權值分布，使得訓練資料在基本分類器的學習中起不同的作用。這是 AdaBoost 的一個特點；
利用基本分類器的權重線性組合建構最終分類器，是 AdaBoost 的另一個特點；
AdaBoost 被實踐證明是一種很好的防止過拟合的方法，但至今為什麼至今沒從理論上證明。

AdaBoost 隻适用于二分類問題。

四、GBDT

GBDT（Gradient Boosting Decision Tree）又叫 MART（Multiple Additive Regression Tree）。是一種疊代的決策樹算法。

本文從以下幾個方面進行闡述：

Regression Decision Tree(DT)；

Gradient Boosting(GB)；

Shrinkage(算法的一個重要演進分支，目前大部分源碼都是基于該版本實作)；

GBDT 适用範圍；

與随機森林的對比。

▌4.1 DT：回歸樹 Regression Decision Tree

GDBT 中的樹全部都是回歸樹，核心就是累加所有樹的結果作為最終結果。隻有回歸樹的結果累加起來才是有意義的，分類的結果加是沒有意義的。

GDBT 調整之後可以用于分類問題，但是内部還是回歸樹。

這部分和決策樹中的是一樣的，無非就是特征選擇。回歸樹用的是最小化均方誤差，分類樹是用的是最小化基尼指數（CART）

▌4.2 GB：梯度疊代 Gradient Boosting

首先 Boosting 是一種內建方法。通過對弱分類器的組合得到強分類器，他是串行的，幾個弱分類器之間是依次訓練的。GBDT 的核心就在于，每一顆樹學習的是之前所有樹結論和的殘差。

Gradient 展現在：無論前面一顆樹的 cost function 是什麼，是均方差還是均差，隻要它以誤差作為衡量标準，那麼殘差向量都是它的全局最優方向，這就是 Gradient。

▌4.3 Shrinkage

Shrinkage（縮減）是 GBDT 算法的一個重要演進分支，目前大部分的源碼都是基于這個版本的。

核心思想在于：Shrinkage 認為每次走一小步來逼近結果的效果，要比每次邁一大步很快逼近結果的方式更容易防止過拟合。

也就是說，它不信任每次學習到的殘差，它認為每棵樹隻學習到了真理的一小部分，累加的時候隻累加一小部分，通過多學習幾棵樹來彌補不足。

具體的做法就是：仍然以殘差作為學習目标，但是對于殘差學習出來的結果，隻累加一小部分（step* 殘差）逐漸逼近目标，step 一般都比較小 0.01-0.001, 導緻各個樹的殘差是漸變而不是陡變的。

本質上，Shrinkage 為每一顆樹設定了一個 weight，累加時要乘以這個 weight，但和 Gradient 沒有關系。

這個 weight 就是 step。跟 AdaBoost 一樣，Shrinkage 能減少過拟合也是經驗證明的，目前還沒有理論證明。

▌4.4 GBDT 适用範圍

GBDT 可以适用于回歸問題（線性和非線性），相對于 logistic regression 僅能用于線性回歸，GBDT 适用面更廣；

GBDT 也可用于二分類問題（設定門檻值，大于為正，否則為負）和多分類問題。

▌4.5 GBDT 和随機森林

GBDT 和随機森林的相同點：

都是由多棵樹組成；

最終的結果都由多棵樹共同決定。

GBDT 和随機森林的不同點：

組成随機森林的可以是分類樹、回歸樹；組成 GBDT 隻能是回歸樹；

組成随機森林的樹可以并行生成（Bagging）；GBDT 隻能串行生成（Boosting）；

對于最終的輸出結果而言，随機森林使用多數投票或者簡單平均；而 GBDT 則是将所有結果累加起來，或者權重累加起來；

随機森林對異常值不敏感，GBDT 對異常值非常敏感；

随機森林對訓練集一視同仁權值一樣，GBDT 是基于權值的弱分類器的內建；

随機森林通過減小模型的方差提高性能，GBDT 通過減少模型偏差提高性能。

TIP

1. GBDT 相比于決策樹有什麼優點

泛化性能更好！GBDT 的最大好處在于，每一步的殘差計算其實變相的增大了分錯樣本的權重，而已經分對的樣本則都趨向于 0。這樣後面就更加專注于那些分錯的樣本。

2. Gradient 展現在哪裡？

可以了解為殘差是全局最優的絕對方向，類似于求梯度。

3. re-sample

GBDT 也可以在使用殘差的同時引入 Bootstrap re-sampling，GBDT 多數實作版本中引入了這個選項，但是是否一定使用有不同的看法。

原因在于 re-sample 導緻的随機性，使得模型不可複現，對于評估提出一定的挑戰，比如很難确定性能的提升是由于 feature 的原因還是 sample 的随機因素。

五、Logistic 回歸

LR 原理；

參數估計；

LR 的正則化；

為什麼 LR 能比線性回歸好？

LR 與 MaxEnt 的關系。

▌5.1 LR 模型原理

首先必須給出 Logistic 分布：

u 是位置參數，r 是形狀參數。對稱點是 (u,1/2)，r 越小，函數在 u 附近越陡峭。

然後，二分類 LR 模型，是參數化的 logistic 分布，使用條件機率來表示：

然後，一個事件的幾率（odds）：指該事件發生與不發生的機率比值：

對數幾率：

那麼對于邏輯回歸而言，Y=1 的對數幾率就是：

最終，輸出 Y=1 的對數幾率是輸入 x 的線性函數表示的模型，這就是邏輯回歸模型。

▌5.2 參數估計

在統計學中，常常使用極大似然估計法來估計參數。即找到一組參數，使得在這組參數下，我們資料的似然度（機率）最大。

似然函數：

對數似然函數：

對應的損失函數：

▌5.3 最優化方法

邏輯回歸模型的參數估計中，最後就是對 J(W) 求最小值。這種不帶限制條件的最優化問題，常用梯度下降或牛頓法來解決。

使用梯度下降法求解邏輯回歸參數估計

求 J(W) 梯度：g(w):

更新 Wk：

$$
W_{k+1} = W_k - \lambda*g(W_k)
$$

▌5.4 正則化

正則化為了解決過拟合問題。分為 L1 和 L2 正則化。主要通過修正損失函數，加入模型複雜性評估；

正則化是符合奧卡姆剃刀原理：在所有可能的模型中，能夠很好的解釋已知資料并且十分簡單的才是最好的模型。

p 表示範數，p=1 和 p=2 分别應用 L1 和 L2 正則。

L1 正則化。向量中各元素絕對值之和。又叫做稀疏規則算子（Lasso regularization）。關鍵在于能夠實作特征的自動選擇，參數稀疏可以避免非必要的特征引入的噪聲；

L2 正則化。使得每個元素都盡可能的小，但是都不為零。在回歸裡面，有人把他的回歸叫做嶺回歸（Ridge Regression），也有人叫他 “權值衰減”（weight decay）。

一句話總結就是：L1 會趨向于産生少量的特征，而其他的特征都是 0，而 L2 會選擇更多的特征，這些特征都會接近于 0.

▌5.5 邏輯回歸 vs 線性回歸

首先，邏輯回歸比線性回歸要好。

兩者都屬于廣義線性模型。

線性回歸優化目标函數用的最小二乘法，而邏輯回歸用的是最大似然估計。邏輯回歸隻是線上性回歸的基礎上，将權重和通過 sigmoid 函數，映射到 0-1 範圍内空間。

線性回歸在整個實數範圍内進行預測，敏感度一緻，而分類範圍，需要在 [0,1]。而邏輯回歸就是一種減小預測範圍，将預測值限定為 [0,1] 間的一種回歸模型。

邏輯曲線在 z=0 時，十分敏感，在 z>>0 或 z<<0 處，都不敏感，将預測值限定為 (0,1)。邏輯回歸的魯棒性比線性回歸要好。

▌5.6 邏輯回歸模型 vs 最大熵模型 MaxEnt

簡單粗暴的說：邏輯回歸跟最大熵模型沒有本質差別。邏輯回歸是最大熵對應為二類時的特殊情況，也就是說，當邏輯回歸擴充為多類别的時候，就是最大熵模型。

最大熵原理：學習機率模型的時候，在所有可能的機率模型（分布）中，熵最大的模型是最好的模型。

六、SVM 支援向量機

雖然咱們的目标是盡可能的不涉及到公式，但是提到 SVM 就沒有辦法不涉及到公式推導，因為面試中隻要問到 SVM，最基本也是最難的問題就是：SVM 的對偶問題數學公式推導。

是以想學好機器學習，還是要塌下心來，不僅僅要把原理的核心思想掌握了，公式推導也要好好學習才行。

▌6.1 SVM 原理

簡單粗暴的說：SVM 的思路就是找到一個超平面将資料集進行正确的分類。對于在現有次元不可分的資料，利用核函數映射到高緯空間使其線性可分。

支援向量機 SVM 是一種二分類模型。它的基本模型是定義在特征空間上的間隔最大的線性分類器，間隔最大使它有别于感覺機。SVM 的學習政策是間隔最大化，可形式化為求解凸二次規劃問題。

SVM 分為：

線性可分支援向量機。當訓練資料線性可分時，通過硬間隔最大化，學習到的一個線性分類器；
線性支援向量機。當訓練資料近似線性可分時，通過軟間隔最大化，學習到的一個線性分類器；
非線性支援向量機。當訓練資料線性不可分，通過使用核技巧及軟間隔最大化，學習非線性支援向量機。

上圖中，X 表示負例，O 表示正例。此時的訓練資料可分，線性可分支援向量機對應着将兩類資料正确劃分并且間隔最大的直線。

6.1.1 支援向量與間隔

支援向量：線上性可分的情況下，訓練資料樣本集中的樣本點中與分離超平面距離最近的樣本點的執行個體稱為支援向量（support vector）。

函數間隔定義如下：

yi 表示目标值，取值為 +1、-1. 函數間隔雖然可以表示分類預測的準确性以及确信度。但是有個不好的性質：隻要成倍的改變 W 和 B，雖然此時的超平面并沒有改變，但是函數間隔會變大。

是以我們想到了對超平面的法向量 W 施加一些限制，比如規範化，使得間隔确定，這就引出了幾何間隔：

支援向量學習的基本思想就是求解能夠正确劃分訓練資料集并且幾何間隔最大的分類超平面。

6.1.2 對偶問題

為了求解線性可分支援向量機的最優化問題：

将它作為原始最優化問題，應用拉格朗日對偶性，通過求解對偶問題得到原始問題的最優解，這就是線性可分支援向量機的對偶算法。

本來的算法也可以求解 SVM，但是之是以要用對偶問題來求解，優點是：

一是對偶問題往往更容易求解；
二是自然引入核函數，進而推廣到非線性分類問題。

說點題外話，這也是面試中會被問到的一個問題：原始問題既然可以求解，為什麼還要轉換為對偶問題。

答案就是上述這兩點。由于篇幅的願意，此處就不在展開數學公式的推導了，大家可以參考《機器學習》與《統計學習方法》。

6.1.3 核函數

對于在原始空間中不可分的問題，在高維空間中是線性可分的。

對于線性不可分的問題，使用核函數可以從原始空間映射到高緯空間，使得問題變得線性可分。核函數還可以使得在高維空間計算的内積在低維空間中通過一個函數來完成。

常用的核函數有：高斯核、線性核、多項式核。

6.1.4 軟間隔

線性可分問題的支援向量機學習方法，對現行不可分訓練資料是不适用的。是以講間隔函數修改為軟間隔，對于函數間隔，在其上加上一個松弛變量，使其滿足大于等于 1。限制條件變為：

▌6.2 優缺點

時空開銷比較大，訓練時間長；
核函數的選取比較難，主要靠經驗。

在小訓練集上往往得到比較好的結果；
使用核函數避開了高緯空間的複雜性；
泛化能力強。

七、利用 sklearn 進行實戰

使用 sklearn 用決策樹來進行莺尾花資料集的劃分問題。代碼上沒有固定随機種子，是以每次運作的結果會稍有不同。

資料集三維可視化：

在 Sepal length 和 Sepal width 二維上的可視化：

運作結果：

Decision Tree 可視化，也就是生成的決策樹：