機器學習面試題精講（一）

作者：de,light

環境說明：

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

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：克服了 ID3 僅僅能夠處理離散屬性的問題，以及信息增益偏向選擇取值較多特徵的問題，使用信息增益比來選擇特徵。信息增益比 = 信息增益 / 劃分前熵 選擇信息增益比最大的作為最優特徵。

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

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 指數最小作為特徵選擇的準則。從根節點開始，遞歸的生成決策樹。相當於是不斷選取局部最優特徵，或將訓練集分割為基本能夠正確分類的子集；
• 決策樹的剪枝。決策樹的剪枝是為了防止樹的過擬合，增強其泛化能力。包括預剪枝和後剪枝。

2. 隨機森林（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 係數的變化。

缺點：在雜訊較大的時候容易過擬合。

3. 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 只適用於二分類問題。

推薦閱讀：