機(jī)器學(xué)習(xí)之旅—決策樹(shù)(3)

dt_cover.png

從 ID3 到 C4.5

ID3 定義

ID3 算法的核心是在決策樹(shù)各個(gè)子節(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則選擇特征，遞歸的構(gòu)建決策樹(shù)，具體方法是:從根節(jié)點(diǎn)開(kāi)始，對(duì)節(jié)點(diǎn)計(jì)算所有可能的特征的信息增益，選擇信息增益最大的特征作為節(jié)點(diǎn)的特征，由該特征的不同取值建立子節(jié)點(diǎn)；再對(duì)子節(jié)點(diǎn)遞歸調(diào)用以上方法，構(gòu)建決策樹(shù)。

我們通過(guò)一個(gè)具體實(shí)例來(lái)講解如何通過(guò) ID3 算法來(lái)選擇節(jié)點(diǎn)。

求職問(wèn)題

dt_015.jpg
  • 第一列表示待遇高低 1 表示高 0 表示低
  • 標(biāo)準(zhǔn)第二列表示崗位是否有五險(xiǎn)一金 1 表示有五險(xiǎn)一金 0 如果沒(méi)有公積金只有五險(xiǎn)用 2 來(lái)表示
  • 1 表示接受 offer 0 表示沒(méi)有接受 offer
1. 1 1 => 1
2. 1 2 => 1
3. 0 0 => 0
4. 0 0 => 0
5. 1 1 => 1
6. 0 0 => 0
7. 1 2 => 1
8. 1 1 => 1
9. 0 2 => 0
10. 1 0 => 0

先復(fù)習(xí)一下什么是信息熵

  • 熵概念: 信息熵是用來(lái)描述信息的混亂程度或者信息的不確定度。信息熵是可以反映集合的純度

我們要計(jì)算純度也就是計(jì)算其不確定度，不確定度大其純度就低。例如 A 和 B 兩個(gè)事件的概率都是 30% 50%，A 事件的不確定性(也就是信息熵) 要大 。算法目的通過(guò)不斷決策樹(shù)來(lái)將信息熵降低下來(lái)
我們先將公式推出。

Ent(D) = \sum_{k=1}^m p_k \log_2 \frac{1}{p_k} = - \sum_{k=1}^m p_k \log_2 p_k

  • 信息增益 Gain(D,C) = Ent(D) - Ent(D|C) = Ent(D) - \sum_{i=1}^n \frac{N(D_i)}{N} Ent(D_i)

  • 信息增益率
    Gain(D,C) = Ent(D) - Ent(D|C) = Ent(D) - \sum_{i=1}^n \frac{N(D_i)}{N} Ent(D_i)

分析實(shí)例

我們以招聘為例，從樣本看接受 offer 和沒(méi)有接受 offer 各占 50% 所以他們概率分別是

\begin{cases} P_{recive} = \frac{1}{2} \\ P_{refuse} = \frac{1}{2} \end{cases}
- ( \frac{1}{2} \log_2 \frac{1}{2} + \frac{1}{2} \log_2 \frac{1}{2}) = 1

-(0.5 * math.log(0.5,2) + 0.5 * math.log(0.5,2))

劃分條件為待遇情況

我們希望分支之后信息熵是降低的，我么選擇條件 C 后這兩個(gè)節(jié)點(diǎn)，我們回去查表看看高薪崗位的有幾個(gè)，一共有 6 個(gè)崗位。那么是高薪招聘到人是 5

招聘到人 沒(méi)有招聘到人
D1 \frac{5}{6} \frac{1}{6}
D2 0 1

Ent(D_1) = - (\frac{5}{6} \log \frac{5}{6} + \frac{1}{6} \log \frac{1}{6} ) \approx 0.65

-(5/6.0* math.log((5/6.0),2)) - 1/6.0 * math.log((1/6.0),2)

Ent(D_2) = 1 * \log_2^1 + 0 * \log_2^0 = 0

1 - (\frac{6}{10} * 0.65 + \frac{4}{10} * 0) = 0.61

分類 數(shù)量 比例
0 \frac{4}{10} 0 \rightarrow 4, 1 \rightarrow 0
1 \frac{3}{10} 0 \rightarrow 0, 1 \rightarrow 3
2 \frac{3}{10} 0 \rightarrow 1, 1 \rightarrow 2

信息增益越大越好
\frac{3}{10} \times \left( -\frac{1}{3} \log \frac{1}{3} - \frac{2}{3} \log \frac{2}{3} \right) = 0.27

1 - 0.27 = 0.73

>>> -1/3.0 * math.log(1/3.0,2) - 2/3.0 * math.log(2/3.0,2)
0.9182958340544896
>>> 0.9182958340544896 * 0.3
0.27548875021634683
>>> 1 - 0.28
0.72

在 ID3 我們根據(jù)信息增益(越大越好)來(lái)選擇劃分條件，但是有一個(gè)問(wèn)題有關(guān)是否高薪我們有兩種結(jié)果為是高薪或者不是高薪，而對(duì)于待遇我們是有三種結(jié)果0 代表沒(méi)有五險(xiǎn)一金待遇，1 代表有五險(xiǎn)沒(méi)有一金，2 代表五險(xiǎn)一金俱全的。

也就是劃分后條件，我們?cè)贅O端點(diǎn)按 id 進(jìn)行劃分那么每一都是確定所以所有信息熵都是 0 然后 1 - 0 就是 1 ，那么按 id 劃分信息增益最高但是沒(méi)有任何作用，使用信息熵天生對(duì)多路分類進(jìn)行偏好所以。新來(lái)一個(gè)數(shù)據(jù)我們按 id 劃分是無(wú)法預(yù)測(cè)新數(shù)據(jù)類別的，而且按 id 進(jìn)行劃分說(shuō)明我們的模型比較復(fù)雜。復(fù)雜模型就很容易出現(xiàn)過(guò)擬合現(xiàn)象。為了解決這個(gè)問(wèn)題引入信息增益率*

- 1 * \ln 1 = 0
\sum_{i=1}^n (-ln1) = 0

C4.5 算法

  • 信息增益率
    信息增益率是在信息增益基礎(chǔ)上除以信息熵，也就是給我們?cè)黾臃诸愖芳恿艘粋€(gè)代價(jià)。也就是分類多了其分母就會(huì)變大從而將數(shù)值降低下來(lái)。
    Gain_ratio(D,C) = \frac{Gain(D,C)}{Ent(C)}

Ent(C) = - \sum_{i=1}^k \frac{N(D_i)}{N} \log_2 \frac{N(D_i)}{N}

我們回頭從新整理一下公式

  • 劃分條件為薪資
    Gain(D C_1) = 0.61
    Ent(C_1) = - (\frac{6}{10} \log \frac{6}{10} + \frac{4}{10} \log \frac{4}{10}) = 0.971 
- (6/10.0 * math.log(6/10.0,2) + 4/10.0 * math.log(4/10.0,2))

Gain_{ratio}(C_1) = 0.61 \div 0.971 = 0.63

  • 劃分條件為福利待遇
    Gain(D C_2) = 0.72
    Ent(C_2) = - (\frac{3}{10} \log \frac{3}{10} + \frac{3}{10} \log \frac{3}{10} + \frac{4}{10} \log \frac{4}{10}) = 1.571 
-(3/10.0 * math.log(3/10.0,2) + 3/10.0*math.log(3/10.0,2)+4/10.0*math.log(4/10.0,2))

Gain_{ratio}(C_2) = 0.72 \div 1.571 = 0.46

如果我們僅信息增益就會(huì)選擇C2(按待遇進(jìn)行劃分),而按信息增益率來(lái)計(jì)算我們就會(huì)選擇C1(按薪酬劃分）。

CART 算法(Classification And Regression Tree)

CART 算法不但可以處理分類問(wèn)題還可以處理回歸問(wèn)題。CART 算法與ID3 算法思路是相似的，但是具體實(shí)現(xiàn)上和應(yīng)用場(chǎng)景略有不同。
CART 算法采用基尼指數(shù)（分類樹(shù)）以及方差（回歸樹(shù)）作為純度的度量，而ID3 系列算法采用信息熵作為純度的度量。
CART 算法只能建立二叉樹(shù)，而ID3系列算法能夠建立多叉樹(shù)。

分類樹(shù)

Gini(D) = \sum_{k=1}^m p_k(1-p_k) = 1 - \sum_{k=1}^m p_k^2
基尼指數(shù)越小越好
\Delta Gini = Gini(D) - \sum_{i=1}^2 \frac{N(D_i)}{N} Gini(D_i)
我們用根節(jié)點(diǎn)的基尼指數(shù)減去按條件劃分后基尼指數(shù)，也就是結(jié)果越大那么說(shuō)明這個(gè)劃分條件越好。

回歸樹(shù)

對(duì)于連續(xù)型我們通過(guò)方差來(lái)考慮，方差越小純度越高
V(D) = \frac{1}{N-1} \sum_{i=1}^N(y_i(D) - \hat{y}(D))^2
同樣我們用根節(jié)點(diǎn)方差減去劃分后方差，結(jié)果越大說(shuō)明劃分條件越好
\Delta V = V(D) - \sum_{i=1}^2 \frac{N(D_i)}{N} V(D_i)

優(yōu)化以及總結(jié)

C5.0 系列 CART
是否支持多路劃分 多重(有多少類別數(shù)量就有多少) 二叉樹(shù)
連續(xù)目標(biāo) 否 是
決策樹(shù)分割標(biāo)準(zhǔn) 信息增益(ID3)/信息增益率(C4.5) Gini 系數(shù)(分類）/方差(回歸樹(shù))
剪枝 誤差估計(jì) 誤差代價(jià)——復(fù)雜度
代價(jià)敏感矩陣 支持 支持
Boosting 支持 支持

我們來(lái)思考一個(gè)問(wèn)題，我們通過(guò)不斷細(xì)分一定可以把數(shù)據(jù)劃分為我們想要結(jié)果。但是這個(gè)樹(shù)并不是我們想要的模樣，因?yàn)樯厦嫖覀円呀?jīng)知道了，復(fù)雜模型帶來(lái)就是過(guò)擬合問(wèn)題。那么我們?nèi)绾卧u(píng)估一個(gè)決策樹(shù)設(shè)計(jì)好壞呢?
所以我們就需要對(duì)決策樹(shù)進(jìn)行調(diào)整和刪減不必要節(jié)點(diǎn)，這個(gè)過(guò)程我們稱為剪枝，剪枝又分為預(yù)剪枝和后剪枝，在預(yù)剪枝很簡(jiǎn)單，必須保證分裂后節(jié)點(diǎn)必須保證有我們事先定義好的樣本量，如果節(jié)點(diǎn)樣本量少于指定的樣本量，我們就不進(jìn)行分支。這就是預(yù)剪枝，也就是生成節(jié)點(diǎn)如果不滿足一定條件我們就將其減掉，這個(gè)過(guò)程就是預(yù)剪枝，有了預(yù)剪枝當(dāng)然也就有后剪枝。

后剪枝

  • 我們用訓(xùn)練集構(gòu)建決策樹(shù)，然后我們用測(cè)試評(píng)估決策樹(shù)，通過(guò)測(cè)試集后，假如父節(jié)點(diǎn)的誤差大于分支后誤差就說(shuō)明劃分是對(duì)的，相反就會(huì)減掉這個(gè)分支
  • 而在C5.0會(huì)采用其他策略進(jìn)行評(píng)估，C5.0 會(huì)考慮代價(jià)。
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容