Day11~13 第五章 決策樹(shù)

1?決策樹(shù)模型與學(xué)習(xí)

1.1?決策樹(shù)模型

??定義 5.1 (決策樹(shù))?分類決策樹(shù)模型是描述對(duì)實(shí)例進(jìn)行分類的樹(shù)形結(jié)構(gòu)。決策樹(shù)由 結(jié)點(diǎn) (node) 和 有向邊(directed edge) 組成加匈。結(jié)點(diǎn)有兩種類型：內(nèi)部結(jié)點(diǎn)與外部結(jié)點(diǎn)凳宙。內(nèi)部結(jié)點(diǎn)表示一個(gè)特征或?qū)傩?/strong>，外部結(jié)點(diǎn)表示一個(gè)類。

1.2?決策樹(shù)與 if-then 規(guī)則

??可以將決策樹(shù)看做一個(gè) if-then 規(guī)則的集合挑宠。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑都可以看做是一個(gè)規(guī)則：
??(1) 內(nèi)部節(jié)點(diǎn)的特征對(duì)應(yīng)著規(guī)則的條件；
??(2) 葉節(jié)點(diǎn)的類對(duì)應(yīng)著規(guī)則的結(jié)論颓影。
??這樣的規(guī)則具有互斥性和完備性各淀，即每一個(gè)實(shí)例都由一條路徑覆蓋，并且這個(gè)實(shí)例只能被這條路徑覆蓋诡挂。

?? k 近鄰算法可以完成很多分類任務(wù)碎浇，但是其最大的缺點(diǎn)是無(wú)法給出數(shù)據(jù)的內(nèi)在含義。決策樹(shù)由于采用 if-then 規(guī)則從而具有較好的可解釋性璃俗。

1.3?決策樹(shù)與條件概率分布

??決策樹(shù)還表示給定特征條件下類的條件概率分布奴璃。這一條件概率分布定義在特則空間的一個(gè)劃分上。將特征空間劃分為互不相交的單元或區(qū)域旧找，并在每個(gè)單元定義一個(gè)類的概率分布就構(gòu)成了一個(gè)條件概率分布。決策樹(shù)的一條路徑對(duì)應(yīng)于劃分中的一個(gè)單元麦牺。決策樹(shù)所表示的條件概率分布由各個(gè)單元給定條件下類的條件概率分布組成钮蛛。

1.4?決策樹(shù)學(xué)習(xí)

??給定訓(xùn)練數(shù)據(jù)集D=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}其中鞭缭，x_i=(x_i^{(1)},x_i^{(2)},\dots,x_i^{(n)})^T 為輸入實(shí)例，n 為特征個(gè)數(shù)魏颓，y_i\in\{1,2,\dots,K\} 為類標(biāo)記岭辣，i=1,2,\dots,N，N 為樣本容量甸饱。
??● 決策樹(shù)的目標(biāo)：根據(jù)給定數(shù)據(jù)集構(gòu)建一個(gè)決策樹(shù)模型沦童，使它能夠?qū)?shí)例進(jìn)行正確的分類；
??● 決策樹(shù)學(xué)習(xí)的本質(zhì)：從訓(xùn)練集中歸納出一組分類規(guī)則叹话，或者說(shuō)是由訓(xùn)練數(shù)據(jù)集估計(jì)條件概率模型偷遗；
??● 決策樹(shù)學(xué)習(xí)的損失函數(shù)：正則化的極大似然函數(shù)；
??● 決策樹(shù)的學(xué)習(xí)算法包含特征選擇驼壶、決策樹(shù)的生成與決策樹(shù)的剪枝三個(gè)過(guò)程氏豌；
??● 決策樹(shù)學(xué)習(xí)常用的算法有 ID3、C4.5 與 CART热凹。

2?特征選擇

??特征選擇在于選取對(duì)訓(xùn)練數(shù)據(jù)集具有分類能力的特征泵喘，這樣可以提高決策樹(shù)學(xué)習(xí)的效率。通常特征選擇的準(zhǔn)則是信息增熵或信息增益比般妙。

2.1?信息增益
  • 信息熵
    ??信息熵 (entropy) 是表示隨機(jī)變量不確定性的度量纪铺。熵越大，則隨機(jī)變量的不確定性就越大碟渺。設(shè) X 是一個(gè)取有限值的離散隨機(jī)變量鲜锚，其概率分布為P(X=x_i)=p_i,\quad i=1,2,\dots,n則隨機(jī)變量 X 的熵定義為：H(X)=-\sum\limits_{i=1}^n p_i\log p_i若有 0 概率，則定義 0\log 0 = 0止状。 通常烹棉，式中的對(duì)數(shù)以 2 為底或以 e 為底，這是熵的單位分別稱為比特 (bit)或納特 (nat)怯疤。由于熵只依賴于 X 的分布浆洗，而與 X 的取值無(wú)關(guān)，故也可將 X 的熵記作 H(p)集峦。從定義驗(yàn)可驗(yàn)證 0\leqslant H(p)\leqslant \log n伏社。

這里給出 0\leqslant H(p)\leqslant \log n 的證明：
證明：
??信息熵的非負(fù)性是顯然的，這里只證明H(p)\leqslant \log n塔淤。這個(gè)證明是容易的：不妨設(shè) \log 以自然對(duì)數(shù)為底摘昌，那么\begin{align}\log n-H(p) &=\log n - \sum\limits_{i=1}^n -p_i\log p_i \\ & =\sum\limits_{i=1}^n p_i \log n -\sum\limits_{i=1}^n -p_i\log p_i\\ & =\sum\limits_{i=1}^n p_i \log (n p_i)\\ & \geqslant \sum\limits_{i=1}^n p_i \big(1-\frac{1}{n p_i}\big)\qquad(\text{對(duì)數(shù)不等式})\\ & =\sum\limits_{i=1}^n p_i-\sum\limits_{i=1}^n\frac{1}{n}\\ & =1-1=0 \end{align}??因此，根據(jù)對(duì)數(shù)不等式取等號(hào)的條件高蜂，\log n-H(p)\geqslant 0聪黎，即 \log n\geqslant H(p)當(dāng)且僅當(dāng) p_i = 1/n，i=1,2,\dots, n 時(shí)备恤，等號(hào)成立稿饰。Q.E.D.

  • 條件信息熵
    ??設(shè)有隨機(jī)變量 (X,Y)锦秒，其聯(lián)合概率分布為P(X=x_i,Y=y_i)=p_{ij},\quad i=1,2,\dots,n;\quad j=1,2,\dots,n??條件熵 (conditional entropy) H(Y|X) 表示在已知隨機(jī)變量 X 的條件下隨機(jī)變量 Y 的不確定性，定義為 X 給定條件 Y 的條件概率分布的熵對(duì) X 的數(shù)學(xué)期望H(Y|X) = \sum\limits_{i=1}^n p_i H(Y|X=x_i)這里 p_i=P(X=x_i)喉镰，i=1,2,\dots,n旅择。若有 0 概率，則定義 0\log 0 = 0侣姆。

??當(dāng)熵和條件熵中的概率由數(shù)據(jù)估計(jì)（尤其是極大似然估計(jì)）得到時(shí)生真，所對(duì)應(yīng)的熵與條件熵分別稱為經(jīng)驗(yàn)熵和經(jīng)驗(yàn)條件熵。

  • 信息增益
    ??信息增益 (information gain) 表示得知特征 X 的信息而使得類 Y 的信息的不確定性減少的程度捺宗。
    ??定義 5.2 (信息增益)?特征 A 對(duì)訓(xùn)練數(shù)據(jù)集 D 的信息增益 g(D,A)柱蟀，定義為集合 D 對(duì)經(jīng)驗(yàn)熵 H(D) 與特征 A 給定條件下 D 的經(jīng)驗(yàn)條件熵 H(D|A) 之差，即g(D,A) = H(D)-H(D|A)??一般的偿凭，熵 H(Y) 與條件熵 H(Y|X) 之差稱為互信息 (mutual information)产弹。
    ??決策樹(shù)學(xué)習(xí)應(yīng)用信息增益準(zhǔn)則選擇特征。由于信息增益表示一個(gè)特征對(duì)數(shù)據(jù)集的分類的不確定性減少的程度弯囊，故信息增益越大的特征往往具有更強(qiáng)的分類能力痰哨。
2.2?信息增益比

??以信息增益作為劃分訓(xùn)練數(shù)據(jù)集的特征撬讽，存在偏向于選擇取值較多的特征的問(wèn)題。使用信息增益比 (information gain ratio) 可以對(duì)這一問(wèn)題進(jìn)行校正悬垃。這是特征選擇的另一準(zhǔn)則游昼。
??定義 5.2 (信息增益比)?特征 A 對(duì)訓(xùn)練數(shù)據(jù)集 D 的信息增益比 g_R(D,A)，定義為信息增益 g(D,A) 與訓(xùn)練數(shù)據(jù)集 D 關(guān)于特征 A 的值的熵 H_A(D)之比尝蠕，即g(D,A) = \frac{g(D,A)}{H_A(D)}其中烘豌，H_A(D)=-\sum\limits_{i=1}^n \frac{|D_i|}{|D|}\log_2 \frac{|D_i|}{|D|}，n 為特征 A 的取值的個(gè)數(shù)看彼。

3?決策樹(shù)的生成

3.1?ID3 算法與 C4.5 算法

??從第 2 小節(jié)信息論相關(guān)的知識(shí)中我們知道：信息熵越大廊佩，從而樣本純度越低。ID3 算法的核心思想就是在決策樹(shù)的各個(gè)結(jié)點(diǎn)以信息增益準(zhǔn)則來(lái)進(jìn)行特征選擇靖榕，遞歸地構(gòu)建決策樹(shù)标锄。 其大致步驟為：
??(1) 從根結(jié)點(diǎn)開(kāi)始，對(duì)結(jié)點(diǎn)計(jì)算所有可能的特征的信息增益茁计；
??(2) 選擇信息增益最大的特征作為該結(jié)點(diǎn)的特征料皇；
??(3) 根據(jù)步驟 (2) 所選取特征的不同取值建立子節(jié)點(diǎn)（即按照特征的取值來(lái)劃分不同分支的數(shù)據(jù)集合)，再對(duì)子節(jié)點(diǎn)遞歸地調(diào)用步驟 (1)；
??(4) 重復(fù)上述步驟践剂，若子集只包含單一特征或子集中的信息增熵小于閾值毒返，則設(shè)為單節(jié)點(diǎn)。直至生成最后一棵單節(jié)點(diǎn)決策樹(shù)舷手。

從 ID3 算法的具體步驟我們分析不難發(fā)現(xiàn)其可能具有如下缺點(diǎn)：

  • 采用信息增益準(zhǔn)則對(duì)可取值數(shù)目較多的特征有所偏好 (如類似“編號(hào)”的特征)；
  • 只能用于處理離散分布的特征 (這是因?yàn)檫B續(xù)分布的特征取值數(shù)目會(huì)很大)劲绪；

??為了克服 ID3 的上述缺點(diǎn)男窟，我們可以采取如下方法：
??(1) 對(duì)于特征取值數(shù)目的偏重這一缺點(diǎn)，采用引入信息增益比作為分類標(biāo)準(zhǔn)的 C4.5 算法來(lái)進(jìn)行決策樹(shù)的生成贾富；
??(2) 對(duì)于無(wú)法處理連續(xù)分布的特征歉眷，可以將連續(xù)特征離散化，C4.5 算法中采用的方法如下：先將特征取值排序颤枪，以連續(xù)兩個(gè)值中間值作為劃分標(biāo)準(zhǔn)汗捡。嘗試每一種劃分，并計(jì)算修正后的信息增益畏纲，選擇信息增益最大的分裂點(diǎn)作為該屬性的分類點(diǎn)扇住。

??信息增益率對(duì)可取值較少的特征有所偏好（分母越小，整體越大)盗胀，因此實(shí)際上 C4.5 算法可以采用一種類似于啟發(fā)式方法進(jìn)行改進(jìn)：先從特征中找到信息增益高于某一閾值（如平均值）的特征艘蹋，再?gòu)闹羞x擇信息增益率最高的。

4?決策樹(shù)的剪枝

??決策樹(shù)的剪枝處理——從已經(jīng)生成的決策樹(shù)上裁掉一些子樹(shù)或者葉節(jié)點(diǎn)票灰，并將其根節(jié)點(diǎn)或者父節(jié)點(diǎn)作為新的葉節(jié)點(diǎn)女阀，從而簡(jiǎn)化分類樹(shù)模型。
??決策樹(shù)的剪枝往往通過(guò)極小化決策樹(shù)整體的損失函數(shù)來(lái)實(shí)現(xiàn)屑迂。設(shè)樹(shù) T 的葉結(jié)點(diǎn)個(gè)數(shù)為 |T|浸策，t 是樹(shù) T 的葉結(jié)點(diǎn)，該葉結(jié)點(diǎn)有 N_i 個(gè)樣本點(diǎn)惹盼，其中 k 類樣本點(diǎn)有 N_{tk} 個(gè)庸汗，k=1,2,\dots,K，H_t(T) 為葉結(jié)點(diǎn) t 上的經(jīng)驗(yàn)熵逻锐，\alpha\geqslant 0 為參數(shù)夫晌，則決策樹(shù)學(xué)習(xí)的損失函數(shù)可以定義為C_\alpha(T)=\sum\limits_{t=1}^{|T|}N_t H_T(T)+\alpha |T|其中經(jīng)驗(yàn)熵為H_t(T)=-\sum\limits_{k}\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}??不難發(fā)現(xiàn)，上式定義的損失函數(shù)極小化等價(jià)于正則化的極大似然估計(jì)昧诱。

5?CART 算法

??CART (classification and regression tree)：分類與回歸樹(shù)晓淀，可以用于分類與回歸。
??CART 是在給定輸入隨機(jī)變量 X 條件下輸出隨機(jī)變量 Y 的條件概率分布的學(xué)習(xí)方法盏档。CART 假設(shè)決策樹(shù)是二叉樹(shù)凶掰，這樣的決策樹(shù)等價(jià)于遞歸地二分每個(gè)特征粉捻，將輸入空間即特征空間劃分為有限個(gè)單元，并在這些單元上確定預(yù)測(cè)的概率分布袄琳，也就是在輸入給定的條件下輸出的條件概率分布婶恼。

5.1?CART 生成

??決策樹(shù)的生成就是遞歸地構(gòu)建二叉樹(shù)的過(guò)程，對(duì)回歸樹(shù)用平方誤差最小準(zhǔn)則畅涂，對(duì)分類樹(shù)用基尼指數(shù)最小化準(zhǔn)則港华。
??1. 回歸樹(shù)的生成
??算法 5.5 (最小二乘回歸樹(shù)生成算法)
??輸入：訓(xùn)練數(shù)據(jù)集 D；
??輸出：回歸樹(shù) f(x)午衰；
??在訓(xùn)練數(shù)據(jù)集所在的輸入空間中立宜，遞歸地將每個(gè)區(qū)域劃分為兩個(gè)子區(qū)域并決定每個(gè)子區(qū)域的輸出值，構(gòu)建二叉決策樹(shù)：
??(1) 選擇最優(yōu)切分變量 j 與切分點(diǎn) s臊岸，求解\min\limits_{j,s}\left[\min_{c_1}\sum\limits_{x_i\in R_1(j,s)}(y_i-c_1)^2+\min_{c_2}\sum\limits_{x_i\in R_2(j,s)}(y_i-c_2)^2\right]??遍歷變量 j橙数，對(duì)固定的切分變量 j 掃描切分點(diǎn) s，選擇使上式達(dá)到最小的 (j,s)帅戒；
??(2) 對(duì)選定的 (j,s) 劃分區(qū)域并決定相應(yīng)的輸出值：R_1(j,s)=\{x|x^{(j)}\leqslant s\},\quad R_2(j,s)=\{x|x^{(j)}> s\} \hat{c}_m=\frac{1}{N_m}\sum\limits_{x_i\in R_m(j,s)} y_i,\quad x\in R_m,\quad m=1,2??(3) 繼續(xù)對(duì)兩個(gè)子區(qū)域調(diào)用步驟 (1)灯帮，(2)，直至滿足停止條件逻住；
??(4) 將輸入空間劃分為 M 個(gè)區(qū)域 R_1,R_2,\dots,R_M钟哥，生成決策樹(shù)：f(x)=\sum\limits_{m=1}^M \hat{c}_m I(x\in R_m)
??2. 分類樹(shù)的生成
??定義 5.4 (基尼指數(shù))?分類問(wèn)題中，假設(shè)有 K 個(gè)類瞎访，樣本點(diǎn)屬于第 k 類的概率為 p_k瞪醋，則概率分布的基尼指數(shù)定義為\text{Gini}(p)=\sum\limits_{k=1}^K p_k(1-p_k)=1-\sum\limits_{k=1}^K p_k^2對(duì)于二分類問(wèn)題，若樣本點(diǎn)屬于第一個(gè)類的概率是 p装诡，則概率分布的基尼指數(shù)為\text{Gini}(p)=2p(1-p)對(duì)于給定的樣本集合 D银受，其基尼指數(shù)為\text{Gini}(D)=1-\sum\limits_{k=1}^K\left(\frac{|C_k|}{|D|}\right)^2這里，C_k 是 D 中屬于第 k 類的樣本子集鸦采，K 是類的個(gè)數(shù)宾巍。
??若樣本集合 D 根據(jù)特征 A 是否取某一可能值 a 被分割成 D_1 和 D_2 兩個(gè)部分，即D_1=\{(x,y)\in D|A(x)=a\},\quad D_2=D-D_1則在特征 A 的條件下渔伯，集合 D 的基尼指數(shù)定義為\text{Gini}(D,A)=\frac{|D_1|}{|D|}\text{Gini}(D_1)+\frac{|D_2|}{|D|}\text{Gini}(D_2)基尼指數(shù) \text{Gini}(D) 表示集合 D 的不確定性顶霞，基尼指數(shù) \text{Gini}(D,A) 表示集合 D 經(jīng)過(guò) A=a 分割后的不確定性。基尼指數(shù)越越大锣吼，表示樣本集合的不確定性也就越大选浑。

??算法 5.6 (CART 生成算法)
??輸入：訓(xùn)練數(shù)據(jù)集 D，停止計(jì)算的條件玄叠；
??輸出：CART 決策樹(shù)古徒；
??(1) 計(jì)算現(xiàn)有特征對(duì)數(shù)據(jù)集的基尼指數(shù)，對(duì)每一個(gè)特征 A读恃，對(duì)其可能取的每個(gè)值 a隧膘，將 D 劃分成 D_1 與 D_2代态，計(jì)算 A=a 時(shí)的基尼指數(shù)。
??(2) 在所有可能的特征 A 以及它所有可能的切分點(diǎn) a 中疹吃，選擇基尼指數(shù)最小的特征及其對(duì)應(yīng)的切分點(diǎn)作為最優(yōu)特征與最優(yōu)切分點(diǎn)蹦疑。根據(jù)其將數(shù)據(jù)分配到兩個(gè)子節(jié)點(diǎn)中去。
??(3) 對(duì)兩個(gè)子節(jié)點(diǎn)遞歸地調(diào)用 (1)萨驶，(2)歉摧，直至滿足停止條件。
??(4) 生成 CART 決策樹(shù)
??算法的停止條件是節(jié)點(diǎn)中的樣本個(gè)數(shù)小于閾值腔呜，或樣本集的基尼指數(shù)小于預(yù)定閾值判莉，或者沒(méi)有更多的特征。

5.2?CART 剪枝

??算法 5.7 (CART 剪枝算法)
??輸入：CART 算法生成的決策樹(shù)育谬；
??輸出：最優(yōu)決策樹(shù) T_0；
??(1) 設(shè) k=0帮哈，T=T_0膛檀；
??(2) 設(shè) \alpha = +\infty；
??(3) 自下而上地對(duì)各內(nèi)部結(jié)點(diǎn) t 計(jì)算 C(T_t)娘侍，|T_t| 以及g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}\qquad\alpha=\min(\alpha,g(t))??其中咖刃，T_t 表示以 t 為根結(jié)點(diǎn)的子樹(shù)，C(T_t) 為預(yù)測(cè)誤差憾筏，|T_t| 為 T_t 的葉結(jié)點(diǎn)個(gè)數(shù)嚎杨；
??(4) 對(duì) g(t)=\alpha 的內(nèi)部結(jié)點(diǎn) t 進(jìn)行剪枝，并以多數(shù)表決法決定其類氧腰，得到樹(shù) T枫浙；
??(5) 設(shè) k=k+1，\alpha_k = \alpha古拴，T_k=T箩帚；
??(6) 若 T_k 不是由根節(jié)點(diǎn)及兩個(gè)葉結(jié)點(diǎn)構(gòu)成的樹(shù)，則回到步驟 (2)黄痪；否則令 T_k=T_n
??(7) 采用交叉驗(yàn)證法在子樹(shù)數(shù)列 T_0,T_1,\dots,T_n 中選取最優(yōu)子樹(shù) T_\alpha紧帕。

6?習(xí)題

習(xí)題6.1?根據(jù)表 5.1 所給訓(xùn)練集，運(yùn)用 C4.5 算法生成決策樹(shù)桅打。
解：
(1) 根據(jù)例題 5.2是嗜，我們得到：
數(shù)據(jù)集 D 的經(jīng)驗(yàn)熵： H(D) = 0.971
A_1 (年齡) 對(duì)數(shù)據(jù)集 D 的信息增益：g(D,A_1)=0.083
A_2 (有工作) 對(duì)數(shù)據(jù)集 D 的信息增益：g(D,A_2)=0.324
A_3 (有自己的房子) 對(duì)數(shù)據(jù)集 D 的信息增益：g(D,A_3)=0.420
A_4 (信貸情況) 對(duì)數(shù)據(jù)集 D 的信息增益：g(D,A_4)=0.363

(2) 計(jì)算數(shù)據(jù)集 D 關(guān)于各個(gè)特征 A_i，i=1,2,3,4 的值的熵：
\begin{align} & H_{A_1}(D)=-\frac{5}{15}\log_2\frac{5}{15}-\frac{5}{15}\log_2\frac{5}{15}-\frac{5}{15}\log_2\frac{5}{15}=\log_2 3\approx 1.585\\ & H_{A_2}(D)=-\frac{10}{15}\log_2\frac{10}{15}-\frac{5}{15}\log_2\frac{5}{15}=\log_2 3 - \frac{2}{3}\approx 0.918\\ & H_{A_3}(D)=-\frac{9}{15}\log_2\frac{9}{15}-\frac{6}{15}\log_2\frac{6}{15}=\log_2 5 - \frac{3}{5}\log_2 3 -\frac{2}{5}\approx 0.971\\ & H_{A_4}(D)=-\frac{5}{15}\log_2\frac{5}{15}-\frac{4}{15}\log_2\frac{4}{15}-\frac{6}{15}\log_2\frac{6}{15}\\ & \qquad\quad\ \, =\log_2 15 - \frac{1}{3}\log_2 5 - \frac{2}{5}\log_2 6-\frac{8}{15}\approx 1.566\\ \end{align}

(3) 計(jì)算各特征對(duì)數(shù)據(jù)集 D 的信息增益比：
\begin{align} & g_R(D,A_1)=g(D,A_1)/H_{A_1}(D)=0.083/1.585\approx 0.052\\ & g_R(D,A_2)=g(D,A_2)/H_{A_2}(D)=0.324/0.918\approx 0.353\\ & g_R(D,A_3)=g(D,A_3)/H_{A_3}(D)=0.420/0.971\approx \color{red}{0.442}\\ & g_R(D,A_4)=g(D,A_4)/H_{A_4}(D)=0.363/1.566\approx 0.232\\ \end{align}

(4) 由于特征 A_3 (有自己的房子) 的信息增益比最大挺尾，所以選擇特征 A_3 作為根節(jié)點(diǎn)的特征鹅搪。它將訓(xùn)練數(shù)據(jù)集 D 劃分為兩個(gè)子集 D_1 (A_3 取值為“是”) 和 D_2 (A_3 取值為“否”)。由于 D_1 只有同一類的樣本點(diǎn)遭铺，所以它成為一個(gè)葉結(jié)點(diǎn)涩嚣，結(jié)點(diǎn)的類標(biāo)記為“是”崇众。

(5) 對(duì) D_2 則需從特征 A_1,A_2,A_4 中選擇新的特征。根據(jù)例題 5.3航厚，我們得到：
A_1 (年齡) 對(duì)數(shù)據(jù)集 D_2 的信息增益：g(D_2,A_1)=0.251
A_2 (有工作) 對(duì)數(shù)據(jù)集 D_2 的信息增益：g(D_2,A_2)=0.918
A_4 (信貸情況) 對(duì)數(shù)據(jù)集 D_2 的信息增益：g(D_2,A_4)=0.474

(6) 計(jì)算數(shù)據(jù)集 D_2 關(guān)于各個(gè)特征A_1,A_2,A_4 的值的熵：
\begin{align} & H_{A_1}(D_2)=-\frac{4}{9}\log_2\frac{4}{9}-\frac{2}{9}\log_2\frac{2}{9}-\frac{3}{9}\log_2\frac{3}{9}\approx 1.531\\ & H_{A_2}(D_2)=-\frac{6}{9}\log_2\frac{6}{9}-\frac{3}{9}\log_2\frac{3}{9}\approx 0.918\\ & H_{A_4}(D_2)=-\frac{4}{9}\log_2\frac{4}{9}-\frac{4}{9}\log_2\frac{4}{9}-\frac{1}{9}\log_2\frac{1}{9}\approx 1.392\\ \end{align}

(7) 計(jì)算各特征對(duì)數(shù)據(jù)集 D_2 的信息增益比：
\begin{align} & g_R(D_2,A_1)=g(D_2,A_1)/H_{A_1}(D_2)=0.251/1.531\approx 0.164\\ & g_R(D_2,A_2)=g(D_2,A_2)/H_{A_2}(D_2)=0.918/0.918\approx \color{red}{1.000}\\ & g_R(D_2,A_4)=g(D_2,A_4)/H_{A_4}(D_2)=0.474/1.392\approx 0.341\\ \end{align}

(8) 由于特征 A_2 (有工作) 的信息增益比最大顷歌，所以選擇特征 A_2 作為葉結(jié)點(diǎn)的特征。它將訓(xùn)練數(shù)據(jù)集 D 劃分為兩個(gè)子集 D_1 (A_2 取值為“是”) 和 D_2 (A_2 取值為“否”)幔睬。由于 D_1, D_2 都只有同一類的樣本點(diǎn)眯漩，所以它們分別成為一個(gè)葉結(jié)點(diǎn)，結(jié)點(diǎn)的類標(biāo)記分別為“是”和“否”麻顶。

?這樣我們就采用 C4.5 算法構(gòu)建了一個(gè)決策樹(shù)赦抖，這個(gè)決策樹(shù)只用了兩個(gè)特征。

|--- 有自己的房子
|   |--- class: 否
|   |   |--- 有工作
|   |   |   |--- class: 否
|   |   |--- 有工作
|   |   |   |--- class: 是
|--- 有自己的房子
|   |--- class: 是
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末辅肾，一起剝皮案震驚了整個(gè)濱河市队萤，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌矫钓，老刑警劉巖要尔，帶你破解...
    沈念sama閱讀 206,482評(píng)論 6贊 481
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異新娜，居然都是意外死亡赵辕，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 88,377評(píng)論 2贊 382
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門(mén)概龄，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)还惠，“玉大人，你說(shuō)我怎么就攤上這事私杜〔霞” “怎么了？”我有些...
    開(kāi)封第一講書(shū)人閱讀 152,762評(píng)論 0贊 342
  • 道士緝兇錄：失蹤的賣(mài)姜人
    文/不壞的土叔 我叫張陵衰粹，是天一觀的道長(zhǎng)嚎幸。 經(jīng)常有香客問(wèn)我，道長(zhǎng)寄猩，這世上最難降的妖魔是什么嫉晶？ 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 55,273評(píng)論 1贊 279
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮田篇，結(jié)果婚禮上替废，老公的妹妹穿的比我還像新娘。我一直安慰自己泊柬，他們只是感情好椎镣，可當(dāng)我...
    茶點(diǎn)故事閱讀 64,289評(píng)論 5贊 373
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著兽赁，像睡著了一般状答。 火紅的嫁衣襯著肌膚如雪冷守。 梳的紋絲不亂的頭發(fā)上，一...
    開(kāi)封第一講書(shū)人閱讀 49,046評(píng)論 1贊 285
  • 城市分裂傳說(shuō)
    那天惊科，我揣著相機(jī)與錄音拍摇，去河邊找鬼。 笑死馆截，一個(gè)胖子當(dāng)著我的面吹牛充活，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播蜡娶，決...
    沈念sama閱讀 38,351評(píng)論 3贊 400
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開(kāi)眼混卵，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了窖张？” 一聲冷哼從身側(cè)響起幕随，我...
    開(kāi)封第一講書(shū)人閱讀 36,988評(píng)論 0贊 259
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎宿接，沒(méi)想到半個(gè)月后赘淮，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 43,476評(píng)論 1贊 300
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡澄阳，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 35,948評(píng)論 2贊 324
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了踏拜。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片碎赢。...
    茶點(diǎn)故事閱讀 38,064評(píng)論 1贊 333
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖速梗，靈堂內(nèi)的尸體忽然破棺而出肮塞，到底是詐尸還是另有隱情，我是刑警寧澤姻锁，帶...
    沈念sama閱讀 33,712評(píng)論 4贊 323
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布枕赵，位于F島的核電站，受9級(jí)特大地震影響位隶，放射性物質(zhì)發(fā)生泄漏拷窜。R本人自食惡果不足惜，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,261評(píng)論 3贊 307
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一涧黄、第九天 我趴在偏房一處隱蔽的房頂上張望篮昧。 院中可真熱鬧，春花似錦笋妥、人聲如沸懊昨。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,264評(píng)論 0贊 19
  • 一樁弒父案春宣，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)酵颁。三九已至嫉你，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間躏惋，已是汗流浹背幽污。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 31,486評(píng)論 1贊 262
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工， 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留其掂，地道東北人油挥。 一個(gè)月前我還...
    沈念sama閱讀 45,511評(píng)論 2贊 354
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長(zhǎng)得像款熬，于是被迫代替她去往敵國(guó)和親深寥。 傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 42,802評(píng)論 2贊 345

推薦閱讀更多精彩內(nèi)容