決策樹算法十問及經典面試問題

簡介和 算法

決策樹是機器學習最常用的算法之一，它將算法組織成一顆樹的形式。其實這就是將平時所說的if-then語句構建成了樹的形式。這個決策樹主要包括三個部分：內部節點、葉節點和邊。內部節點是劃分的屬性，邊代表劃分的條件，葉節點表示類別。構建決策樹 就是一個遞歸的選擇內部節點，計算劃分條件的邊，最後到達葉子節點的過程。

偽代碼: 輸入: 訓練數據集D，特徵集A，閾值. 輸出: 決策樹T.

1. 如果D中所有實例屬於同一類,則置T為單結點樹，並將作為該結點的類，返回T.
2. 如果, 則置T為單結點樹，並將D中最多的類作為該節點的類，返回T.
3. 否則，根據相應公式計算A中各個特徵對D的(信息增益、信息增益比、基尼指數等)，選擇最合適的特徵.
4. 如果的得分小於,則置T為單結點樹，並將作為該結點的類，返回T.
5. 否則，根據特徵取值，對數據D進行劃分，繼續遞歸構造決策樹, 返回T.

核心公式

信息熵:

則隨機變量X的熵定義為:熵越大，隨機變量的不確定性就越大，當時，隨機變量的熵最大等於logn，故. 常見的決策樹由三種: ID3、C4.5、CART. 其中, , ,

.

modelfeature select樹的類型ID3{分類:信息增益}多叉樹C4.5{分類:信息增益比}多叉樹CART{分類:基尼指數}二叉樹CART{迴歸:平方誤差}二叉樹

算法十問

1.決策樹和條件概率分佈的關係？

決策樹可以表示成給定條件下類的條件概率分佈. 決策樹中的每一條路徑都對應是劃分的一個條件概率分佈. 每一個葉子節點都是通過多個條件之後的劃分空間，在葉子節點中計算每個類的條件概率，必然會傾向於某一個類，即這個類的概率最大.

2.ID3和C4.5算法可以處理實數特徵嗎？如果可以應該怎麼處理？如果不可以請給出理由？

ID3和C4.5使用劃分節點的方法分別是信息增益和信息增益比，從這個公式中我們可以看到 這是處理類別特徵的方法，實數特徵能夠計算信息增益嗎？我們可以定義X是實數特徵的信息增益是，.其中,則. 對於每一個實數可以使用這種方式進行分割. 除此之外,我們還可以使用特徵的分桶，將實數特徵映射到有限個桶中，可以直接使用ID3和C4.5算法.

3.既然信息增益可以計算，為什麼C4.5還使用信息增益比？

在使用信息增益的時候，如果某個特徵有很多取值，使用這個取值多的特徵會的大的信息增益，這個問題是出現很多分支，將數據劃分更細，模型複雜度高，出現過擬合的機率更大。使用信息增益比就是為了解決偏向於選擇取值較多的特徵的問題. 使用信息增益比對取值多的特徵加上的懲罰，對這個問題進行了校正.

4.基尼指數可以表示數據不確定性，信息熵也可以表示數據的不確定性. 為什麼CART使用基尼指數？

信息熵0, logK都是值越大，數據的不確定性越大. 信息熵需要計算對數，計算量大；信息熵是可以處理多個類別，基尼指數就是針對兩個類計算的，由於CART樹是一個二叉樹，每次都是選擇yes or no進行劃分，從這個角度也是應該選擇簡單的基尼指數進行計算.

5.決策樹怎麼剪枝？

一般算法在構造決策樹的都是儘可能的細分，直到數據不可劃分才會到達葉子節點，停止劃分. 因為給訓練數據巨大的信任，這種形式形式很容易造成過擬合，為了防止過擬合需要進行決策樹剪枝. 一般分為預剪枝和後剪枝，預剪枝是在決策樹的構建過程中加入限制，比如控制葉子節點最少的樣本個數，提前停止. 後剪枝是在決策樹構建完成之後，根據加上正則項的結構風險最小化自下向上進行的剪枝操作. 剪枝的目的就是防止過擬合，是模型在測試數據上變現良好，更加魯棒.

6.ID3算法，為什麼不選擇具有最高預測精度的屬性特徵，而不是使用信息增益？

7.為什麼使用貪心和其發生搜索建立決策樹，為什麼不直接使用暴力搜索建立最優的決策樹？

決策樹目的是構建一個與訓練數據擬合很好，並且複雜度小的決策樹. 因為從所有可能的決策樹中直接選擇最優的決策樹是NP完全問題，在使用中一般使用啟發式方法學習相對最優的決策樹.

8.如果特徵很多，決策樹中最後沒有用到的特徵一定是無用嗎？

不是無用的，從兩個角度考慮，一是特徵替代性，如果可以已經使用的特徵A和特徵B可以提點特徵C，特徵C可能就沒有被使用，但是如果把特徵C單獨拿出來進行訓練，依然有效. 其二，決策樹的每一條路徑就是計算條件概率的條件，前面的條件如果包含了後面的條件，只是這個條件在這棵樹中是無用的，如果把這個條件拿出來也是可以幫助分析數據.

9.決策樹的優點？

優點: 決策樹模型可讀性好，具有描述性，有助於人工分析；效率高，決策樹只需要一次性構建，反覆使用，每一次預測的最大計算次數不超過決策樹的深度。缺點: 對中間值的缺失敏感；可能產生過度匹配的問題，即過擬合。

10.基尼係數存在的問題?

基尼指數偏向於多值屬性;當類數較大時，基尼指數求解比較困難;基尼指數傾向於支持在兩個分區中生成大小相同的測試。

面試真題

1. 決策樹如何防止過擬合？
2. 信息增益比相對信息增益有什麼好處？
3. 如果由異常值或者數據分佈不均勻，會對決策樹有什麼影響？
4. 手動構建CART的迴歸樹的前兩個節點，給出公式每一步的公式推到？
5. 決策樹和其他模型相比有什麼優點？
6. 決策樹的目標函數是什麼？