文章目錄

• 基礎概念
• • 熵
  • 條件熵
• 信息增益
• 信息增益比
• 決策樹生成
• • ID3生成算法
  • 決策樹剪枝
  • C4.5生成算法

基礎概念

熵

離散型變量X的概率分布是P(X)。它的熵$H(X)orH(P)$越大，代表越均勻、越混亂、越不確定。熵的公式如下：
$$H(P)=?\sum _{x\in X}P(x)\log P(x)$$
定義$0\log 0=0$，熵是非負的。熵只與$X$的分布有關，與$X$取值無關。當X服從均勻分布時，熵最大。

假設隨機變量X只取兩個值，如0和1。此時X的分布為：
$$H(p)=?plo{g}_{2}p?(1?p)log2(1?p)$$
此時，H§隨著概率p的變換曲線如下圖所示：

當p=0或者1時，隨機變量完全是個確定值。所以熵達到了最小值，即$H(p)=0$。但是當$p_0=p_1=0.5$時，不確定性最大，熵達到了最大值1。

條件熵

條件熵H(Y|X)類似于條件概率，它度量了我們的Y在知道X以后剩下的不確定性，即給定X的條件下，Y的條件概率分布的熵對X的數學期望。表達式如下：
$$H(Y|X)=\sum _{j=1}^{n}p(x_j)H(Y|x_j)=?\sum _{i=1}^{n}p(x_i,y_i)logp(y_i|x_i)$$
當熵和條件熵中的概率p由數據估計(常見的是用極大似然估計)得到的時，對應的熵和條件熵成為經驗熵和經驗條件熵。

信息增益

特征A對數據集D的信息增益g(D|A)定義為：集合D的經驗熵H(D)與特征A給定的條件下$D$的經驗條件熵$H(D|A)$之差：
$$g(D,A)=H(D)?H(D|A)$$
一般的熵與條件熵的差也稱為互信息。表示給定特征A使得數據集D不確定性減少的程度。顯然不同的特征有不同的信息增益，使得信息增益最大的特征具有更強的分類能力。

信息增益算法：

輸入：訓練數據集$D$和特征$A$

輸出：特征$A$對訓練數據集$D$的信息增益$g(D,A)$

數據集$D$的經驗熵$H(D)=?{\sum }_{k=1}^K\frac{|C_k|}{|D|}{\log }_2\frac{|C_k|}{|D|}$

特征$A$對數據集$D$的經驗條件熵$H(D|A)={\sum }_{i=1}^n\frac{|D_i|}{|D|}H(D_i)=?{\sum }_{i=1}^n\frac{|D_i|}{|D|}{\sum }_{k=1}^K\frac{|D_{ik}|}{|D_i|}{\log }_2\frac{|D_{ik}|}{|D_i|}$

信息增益$g(D,A)=H(D)?H(D|A)$

其中，|D|表示樣本個數。假設有K個類，每個類用$C_k$表示，|$C_k$|表示屬于第k個類別的樣本個數。特征A有n個不同的取值{${\alpha }_1,{\alpha }_2,...,{\alpha }_n$}，那么用$D_i$表示特征A取第i個值的樣本集合，$D_{ik}$用于表示$D_i$中屬于第k個類別的樣本集合。

舉個例子：

首先計算經驗熵H(D)：
$$H(D)=?(\frac{9}{15}lo{g}_2\frac{9}{15}+\frac{6}{15}lo{g}_2\frac{6}{15})=0.971$$
分別用$A_1,A_2,A_3,A_4$表示年齡、有工作、有房子、貸款情況4個特征，則有：
$$\begin{array}{rl}H(D|A_1)& =\frac{5}{15}H(D1)+\frac{5}{15}H(D2)+\frac{5}{15}H(D3)\\ & =?\frac{5}{15}(\frac{3}{5}lo{g}_2\frac{3}{5}+\frac{2}{5}lo{g}_2\frac{2}{5})?\frac{5}{15}(\frac{2}{5}lo{g}_2\frac{2}{5}\\ & +\frac{3}{5}lo{g}_2\frac{3}{5})?\frac{5}{15}(\frac{4}{5}lo{g}_2\frac{4}{5}+\frac{1}{5}lo{g}_2\frac{1}{5})\\ & =0.888\end{array}$$
于是得到特征$A_1$的信息增益為：
$$g(D|A_1)=H(D)?H(D|A_1)=0.083$$
同理可以得到：
$$\begin{gathered} g(D|A_2)=H(D)?H(D|A_2)=0.324 \\ g(D|A_3)=H(D)?H(D|A_3)=0.420 \\ g(D|A_4)=H(D)?H(D|A_4)=0.363 \end{gathered}$$
發現$A_3$的信息增益最大，因此$A_3$為最優特征。

信息增益比

以信息增益來篩選最優特征，會導致取值個數多的特征信息增益很大。例如我們把每條記錄的唯一標識ID作為特征的話，那么每個ID的值都能唯一區分一條記錄的類別，這樣肯定會造成過擬合從而達不到我們預期的效果。

為此，我們引入了信息增益比來校正這一問題，用$g_R(D,A)$表示：
$$\begin{gathered} g_R(D,A)=\frac{g(D,A)}{H_A(D)} \\ {H}_A(D)=?\sum _{i=1}^n\frac{|D_i|}{|D|}lo{g}_2\frac{|D_i|}{|D|} \end{gathered}$$
即信息增益比為 特征A的信息增益 與 D關于特征A各個取值的熵 之比。

決策樹生成

前面提到的信息增益和信息增益比，可以用來衡量某個特征對樣本的劃分能力。基于之前講到的內容，接下來介紹的ID3生成算法和C4.5生成算法。

ID3生成算法

輸入：訓練數據集$D$, 特征集$A$，閾值$?$
輸出：決策樹$T$

如果$D$屬于同一類$C_k$，$T$為單節點樹，類$C_k$作為該節點的類標記，返回$T$

如果$A$是空集，置$T$為單節點樹，實例數最多的類作為該節點類標記，返回$T$

計算$g$, 選擇信息增益最大的特征$A_g$

如果$A_g$的信息增益小于$?$，$T$為單節點樹，$D$中實例數最大的類$C_k$作為類標記，返回$T$

$A_g$的不同特征取值可以劃分出若干非空子集$D_i$，

$D_i$訓練集，$A?A_g$為特征集，遞歸調用前面步驟，得到$T_i$，返回$T_i$

舉個例子，由于特征$A_3$的信息增益最大，所以選擇對應的特征“有房子”作為決策樹的根節點。根據$A_3$取值的不同，導致樹形成了“是”($D_1$)與“否”(D2)兩個分支。對于兩個分支，還需要繼續對分支后的數據$D_1,D_2$分別找新的劃分特征。對于$D_1$中的樣本而言，他們都是一個類別，所以作為葉節點。

例如對$D_2$而言，需要從年齡、有工作、貸款情況中選擇新特征：
$$\begin{gathered} g(D_2|A_1)=H(D_2)?H(D_2|A_1)=0.251 \\ g(D_2|A_2)=H(D_2)?H(D_2|A_2)=0.918 \\ g(D_2|A_3)=H(D_2)?H(D_2|A_3)=0.474 \end{gathered}$$
于是，選擇$A_2$對應的特征“有工作”來繼續劃分數據集，由于“是”有工作的子集有3個樣本，且這三個樣本都屬于同一個類別，于是這是一個葉節點。對于標記為“否”的分支的6個樣本也都屬于一個類別，所以也是一個葉節點。最終得到的決策樹為：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Eweq9C8L-1589329455836)(F:\CSDN\樹模型\決策樹\assets\1589181996988.png)]

ID3算法不足之處：

容易過擬合

沒有考慮連續特征的處理

沒有考慮缺失值處理

偏好于將特征取值個數多的作為重要特征

決策樹剪枝

越是復雜的決策樹，越是容易過擬合，解決這個問題的辦法是考慮決策樹的復雜度，對已生成的決策樹進行簡化，這個過程稱為剪枝。

剪枝往往通過極小化決策樹整體的損失函數或者代價函數來實現。

樹$T$的葉結點個數為$|T|$，$t$是樹$T$的葉結點，該結點有$N_t$個樣本點，其中$k$類的樣本點有$N_{tk}$個，$H_t(T)$為葉結點$t$上的經驗熵， $\alpha ?0$為參數，決策樹學習的損失函數可以定義為
$$C_{\alpha }(T)=\sum _{i=1}^{|T|}{N}_t{H}_t(T)+\alpha |T|$$
其中
$$H_t(T)=?\sum _k\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}$$

$$C(T)=\sum _{t=1}^{|T|}{N}_t{H}_t(T)=?\sum _{t=1}^{|T|}\sum _{k=1}^K{N}_{tk}\log \frac{N_{tk}}{N_t}$$

這時有
$$C_{\alpha }(T)=C(T)+\alpha |T|$$
其中$C(T)$表示模型對訓練數據的誤差，$|T|$表示模型復雜度，參數$\alpha ?0$控制兩者之間的影響。

樹的剪枝算法如下：

輸入：生成算法生成的整個樹$T$，參數$\alpha$

輸出：修剪后的子樹$T_{\alpha }$

計算每個葉結點的經驗熵

遞歸的從樹的葉結點向上回溯
假設一組葉結點回溯到其父結點之前與之后的整體樹分別是$T_B$和$T_A$，其對應的損失函數分別是$C_{\alpha }(T_A)$和$C_{\alpha }(T_B)$，如果$C_{\alpha }(T_A)?C_{\alpha }(T_B)$則進行剪枝，即將父結點變為新的葉結點：

[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-gjC6Z4fY-1589329455839)(F:\CSDN\樹模型\決策樹\assets\1589188171003.png)]

返回2，直至不能繼續為止，得到損失函數最小的子樹$T_{\alpha }$

C4.5生成算法

對于ID3算法的第一個缺陷，C4.5算法可以通過剪枝的方式，增強了模型的泛化能力。

對于第二個缺陷：不能處理連續特征， C4.5的思路是將連續的特征離散化。比如特征A的連續特征值有n個，從小到大排列為$a_1,a_2,...,a_n$，則C4.5取相鄰兩樣本值的平均數，一共取得n-1個劃分點，其中第i個劃分點$T_i表示$為：$T_i=\frac{a_i+a_{i+1}}{2}$。對于這n-1個點，分別計算以該點作為二元分類點時的信息增益：
$$g(D,a)=H(D)?H(D|a)$$
選擇n-1個信息增益中最大的點作為該連續特征的二元離散分類點。比如取到的增益最大的點為$a_t$,則小于$a_t$的值為類別1，大于$a_t$的值為類別2，這樣我們就做到了連續特征的離散化。要注意的是，與離散屬性不同的是，如果當前節點為連續屬性，則該屬性后面還可以參與子節點的產生選擇過程。

對于第三個缺陷：沒有考慮對缺失值的處理。C4.5主要解決兩個問題：

（1）如何在屬性值缺失的情況下進行劃分屬性選擇？

（2）給定劃分屬性，若樣本在該屬性上缺失，如何對樣本進行劃分？

對于問題（1），給定訓練集D和屬性A，令$\hat{D}$ 表示D中在屬性A上沒有缺失值的樣本子集。假定A的取值有v個：$\{a_1,a_2,\dots ,a_v\}$，令${\hat{D}}^v$ 表示在屬性A上取值為$a_v$ 的樣本子集(如：是否有工作)。${\hat{D}}_k$ 表示$\hat{D}$ 中第k類樣本子集。為每一個樣本$x$賦予一個權重$w_x$，定義：

對于屬性A,無缺失樣本所占的比例為：
$$\rho =\frac{{\sum }_{x\in \hat{D}}{w}_{\mathbf{x}}}{{\sum }_{x\in D}{w}_{\mathbf{x}}}$$
無缺失樣本中第k類所占的比例為：
$${\hat{p}}_k=\frac{{\sum }_{x\in {\hat{D}}_k}{w}_{\mathbf{x}}}{{\sum }_{x\in \hat{D}}{w}_{\mathbf{x}}}$$
無缺失樣本中在屬性A上取值為$a_v$ 的樣本所占的比例為：
$${\hat{r}}_v=\frac{{\sum }_{x\in {\hat{D}}^v}{w}_{\mathbf{x}}}{{\sum }_{x\in \hat{D}}{w}_{\mathbf{x}}}$$
樣本存在缺失值的情況下，采用以下的信息增益計算方式：
$$\begin{array}{rl}g(D,A)& =\rho \times g(\hat{D},A)\\ & =\rho \times \left(H(\hat{D})?H(\hat{D}|A)\right)\end{array}$$
其中：
$$\begin{gathered} H(\hat{D})=?\sum _{k=1}^k{\hat{p}}_k{\log }_2{\hat{p}}_k \\ H(\hat{D}|A)=\sum _{v=1}^v{\hat{r}}_{v}H({\hat{D}}^v) \end{gathered}$$
其實就是：第一步先計算無缺失值的樣本的各個特征的信息增益，然后乘以該特征的無缺失樣本的占比。再選擇信息增益最大的特征作為劃分特征。這也就回答了第一個問題。

對于問題（2），可以將缺失特征的樣本同時劃分入所有的子節點，不過將該樣本的權重按各個子節點樣本的數量比例來分配。比如缺失特征A的樣本a之前權重為1，特征A有3個特征值A1,A2,A3。 3個特征值對應的無缺失A特征的樣本個數為2,3,4.則a同時劃分入A1，A2，A3。對應權重調節為2/9,3/9, 4/9。

對于第四個缺陷：特征數越多的特征對應的特征熵越大，它作為分母，可以校正信息增益容易偏向于取值較多的特征的問題。即采用信息增益比來選擇特征:
$$\begin{gathered} g_R(D,A)=\frac{g(D,A)}{H_A(D)} \\ {H}_A(D)=?\sum _{i=1}^n\frac{D_i}{D}lo{g}_2\frac{D_i}{D} \end{gathered}$$
C4.5 算法流程如下：

輸入：訓練數據集$D$，特征集$A$，閾值$?$
輸出：決策樹$T$

如果$D$屬于同一類$C_k$，$T$為單節點樹，類$C_k$作為該節點的類標記，返回$T$

如果$A$是空集, 置$T$為單節點樹，實例數最多的作為該節點類標記，返回$T$

計算$g$, 選擇信息增益比最大的特征$A_g$

如果$A_g$的信息增益比小于$?$，$T$為單節點樹，$D$中實例數最大的類$C_k$作為類標記，返回$T$

$A_g$劃分若干非空子集$D_i$，

$D_i$訓練集，$A?A_g$為特征集，遞歸調用前面步驟，得到$T_i$，返回$T_i$

ID3和C4.5在生成上，差異只是準則不同。

C4.5 同樣具有局限性，仍然有優化的空間：

C4.5生成的是多叉樹，即一個父節點可以有多個節點。很多時候，在計算機中二叉樹模型會比多叉樹運算效率高。如果采用二叉樹，可以提高效率。

C4.5只能用于分類，如果能將決策樹用于回歸的話可以擴大它的使用范圍。

C4.5由于使用了熵模型，里面有大量的耗時的對數運算，如果是連續值還有大量的排序運算。如果能夠加以模型簡化可以減少運算強度但又不犧牲太多準確性的話，那就更好了。

下一篇介紹的使用CART算法生成的決策樹一定程度上解決了這些問題。

參考文章：

《統計學習方法 第二版》

決策樹算法原理(上)

決策樹算法原理(下)

總結

以上是生活随笔為你收集整理的基于ID3、C4.5算法的决策树相关知识的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。