決策樹算法十問及經(jīng)典面試問題-魔扣目錄

決策樹算法十問及經(jīng)典面試問題

簡介和算法

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

偽代碼: 輸入: 訓(xùn)練數(shù)據(jù)集D，特征集A，閾值. 輸出: 決策樹T.

如果D中所有實例屬于同一類,則置T為單結(jié)點樹，并將作為該結(jié)點的類，返回T.
如果, 則置T為單結(jié)點樹，并將D中最多的類作為該節(jié)點的類，返回T.
否則，根據(jù)相應(yīng)公式計算A中各個特征對D的(信息增益、信息增益比、基尼指數(shù)等)，選擇最合適的特征.
如果的得分小于,則置T為單結(jié)點樹，并將作為該結(jié)點的類，返回T.
否則，根據(jù)特征取值，對數(shù)據(jù)D進行劃分，繼續(xù)遞歸構(gòu)造決策樹, 返回T.

核心公式

信息熵:

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

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

算法十問

1.決策樹和條件概率分布的關(guān)系？

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

2.ID3和C4.5算法可以處理實數(shù)特征嗎？如果可以應(yīng)該怎么處理？如果不可以請給出理由？

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

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

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

4.基尼指數(shù)可以表示數(shù)據(jù)不確定性，信息熵也可以表示數(shù)據(jù)的不確定性. 為什么CART使用基尼指數(shù)？

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

5.決策樹怎么剪枝？

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

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

7.為什么使用貪心和其發(fā)生搜索建立決策樹，為什么不直接使用暴力搜索建立最優(yōu)的決策樹？

決策樹目的是構(gòu)建一個與訓(xùn)練數(shù)據(jù)擬合很好，并且復(fù)雜度小的決策樹. 因為從所有可能的決策樹中直接選擇最優(yōu)的決策樹是NP完全問題，在使用中一般使用啟發(fā)式方法學(xué)習(xí)相對最優(yōu)的決策樹.

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

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

9.決策樹的優(yōu)點？

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

10.基尼系數(shù)存在的問題?

基尼指數(shù)偏向于多值屬性;當(dāng)類數(shù)較大時，基尼指數(shù)求解比較困難;基尼指數(shù)傾向于支持在兩個分區(qū)中生成大小相同的測試。

面試真題