亚洲精品粉嫩久久,午夜日韩在线

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

1.1?決策樹模型

??定義 5.1 (決策樹)?分類決策樹模型是描述對(duì)實(shí)例進(jìn)行分類的樹形結(jié)構(gòu)。決策樹由 結(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?決策樹與 if-then 規(guī)則

??可以將決策樹看做一個(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)是無法給出數(shù)據(jù)的內(nèi)在含義。決策樹由于采用 if-then 規(guī)則從而具有較好的可解釋性。

1.3?決策樹與條件概率分布

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

1.4?決策樹學(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$ 為樣本容量。
??● 決策樹的目標(biāo)：根據(jù)給定數(shù)據(jù)集構(gòu)建一個(gè)決策樹模型，使它能夠?qū)?shí)例進(jìn)行正確的分類；
??● 決策樹學(xué)習(xí)的本質(zhì)：從訓(xùn)練集中歸納出一組分類規(guī)則，或者說是由訓(xùn)練數(shù)據(jù)集估計(jì)條件概率模型；
??● 決策樹學(xué)習(xí)的損失函數(shù)：正則化的極大似然函數(shù)；
??● 決策樹的學(xué)習(xí)算法包含特征選擇、決策樹的生成與決策樹的剪枝三個(gè)過程；
??● 決策樹學(xué)習(xí)常用的算法有 ID3、C4.5 與 CART。

2?特征選擇

??特征選擇在于選取對(duì)訓(xùn)練數(shù)據(jù)集具有分類能力的特征，這樣可以提高決策樹學(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$ 的取值無關(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)。
??決策樹學(xué)習(xí)應(yīng)用信息增益準(zhǔn)則選擇特征。由于信息增益表示一個(gè)特征對(duì)數(shù)據(jù)集的分類的不確定性減少的程度，故信息增益越大的特征往往具有更強(qiáng)的分類能力。

更多有關(guān)熵、條件熵、信息增益的數(shù)學(xué)性質(zhì)可參考：熵、條件熵和互信息的性質(zhì)

如果不理解熵、條件熵、信息增益的概念可參考：通俗理解信息增益

2.2?信息增益比

??以信息增益作為劃分訓(xùn)練數(shù)據(jù)集的特征，存在偏向于選擇取值較多的特征的問題。使用信息增益比 (information gain ratio) 可以對(duì)這一問題進(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?決策樹的生成

3.1?ID3 算法與 C4.5 算法

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

從 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 算法來進(jìn)行決策樹的生成；
??(2) 對(duì)于無法處理連續(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?決策樹的剪枝

??決策樹的剪枝處理——從已經(jīng)生成的決策樹上裁掉一些子樹或者葉節(jié)點(diǎn)，并將其根節(jié)點(diǎn)或者父節(jié)點(diǎn)作為新的葉節(jié)點(diǎn)，從而簡(jiǎn)化分類樹模型。
??決策樹的剪枝往往通過極小化決策樹整體的損失函數(shù)來實(shí)現(xiàn)。設(shè)樹 $T$ 的葉結(jié)點(diǎn)個(gè)數(shù)為 $|T|$ ， $t$ 是樹 $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ù)，則決策樹學(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)：分類與回歸樹，可以用于分類與回歸。
??CART 是在給定輸入隨機(jī)變量 $X$ 條件下輸出隨機(jī)變量 $Y$ 的條件概率分布的學(xué)習(xí)方法。CART 假設(shè)決策樹是二叉樹，這樣的決策樹等價(jià)于遞歸地二分每個(gè)特征，將輸入空間即特征空間劃分為有限個(gè)單元，并在這些單元上確定預(yù)測(cè)的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。

5.1?CART 生成

??決策樹的生成就是遞歸地構(gòu)建二叉樹的過程，對(duì)回歸樹用平方誤差最小準(zhǔn)則，對(duì)分類樹用基尼指數(shù)最小化準(zhǔn)則。
??1. 回歸樹的生成
??算法 5.5 (最小二乘回歸樹生成算法)
??輸入：訓(xùn)練數(shù)據(jù)集 $D$ ；
??輸出：回歸樹 $f(x)$ ；
??在訓(xùn)練數(shù)據(jù)集所在的輸入空間中，遞歸地將每個(gè)區(qū)域劃分為兩個(gè)子區(qū)域并決定每個(gè)子區(qū)域的輸出值，構(gòu)建二叉決策樹：
??(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$ ，生成決策樹： $f(x)=\sum\limits_{m=1}^M \hat{c}_m I(x\in R_m)$
??2. 分類樹的生成
??定義 5.4 (基尼指數(shù))?分類問題中，假設(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ì)于二分類問題，若樣本點(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)過 $A=a$ 分割后的不確定性。基尼指數(shù)越越大，表示樣本集合的不確定性也就越大。

??算法 5.6 (CART 生成算法)
??輸入：訓(xùn)練數(shù)據(jù)集 $D$ ，停止計(jì)算的條件；
??輸出：CART 決策樹；
??(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 決策樹
??算法的停止條件是節(jié)點(diǎn)中的樣本個(gè)數(shù)小于閾值，或樣本集的基尼指數(shù)小于預(yù)定閾值，或者沒有更多的特征。

5.2?CART 剪枝

??算法 5.7 (CART 剪枝算法)
??輸入：CART 算法生成的決策樹；
??輸出：最優(yōu)決策樹 $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)的子樹， $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ù)表決法決定其類，得到樹 $T$ ；
??(5) 設(shè) $k=k+1$ ， $\alpha_k = \alpha$ ， $T_k=T$ ；
??(6) 若 $T_k$ 不是由根節(jié)點(diǎn)及兩個(gè)葉結(jié)點(diǎn)構(gòu)成的樹，則回到步驟 (2)；否則令 $T_k=T_n$
??(7) 采用交叉驗(yàn)證法在子樹數(shù)列 $T_0,T_1,\dots,T_n$ 中選取最優(yōu)子樹 $T_\alpha$ 。

6?習(xí)題

習(xí)題6.1?根據(jù)表 5.1 所給訓(xùn)練集，運(yùn)用 C4.5 算法生成決策樹。
解：
(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è)決策樹，這個(gè)決策樹只用了兩個(gè)特征。

|--- 有自己的房子 | |--- class: 否 | | |--- 有工作 | | | |--- class: 否 | | |--- 有工作 | | | |--- class: 是 |--- 有自己的房子 | |--- class: 是