文章目錄

• 決策樹
• 1. 特征選擇
• • 1.1 熵
  • 1.2 條件熵
  • 1.3 信息增益
  • 1.4 信息增益率
• 2. 決策樹生成
• • 算法1 信息增益及信息增益率的算法
  • 2.1 ID3 算法
  • 2.2 C4.5 算法
• 3. 決策樹剪枝
• • 3.1 預(yù)剪枝
  • 3.2 后剪枝
  • • 算法2 樹的剪枝算法
• 參考文獻(xiàn)

相關(guān)文章：

機(jī)器學(xué)習(xí) | 目錄

監(jiān)督學(xué)習(xí) | ID3 決策樹原理及Python實(shí)現(xiàn)

監(jiān)督學(xué)習(xí) | CART 分類回歸樹原理

監(jiān)督學(xué)習(xí) | 決策樹之Sklearn實(shí)現(xiàn)

監(jiān)督學(xué)習(xí) | 決策樹之網(wǎng)絡(luò)搜索

本文大部分內(nèi)容搬運(yùn)自李航老師的《統(tǒng)計(jì)學(xué)習(xí)方法》^[1]，以給出決策樹算法較為完整的定義，關(guān)于 ID3 算法的更多推到過程以及例子、Python實(shí)現(xiàn)，可以參考這篇文章，關(guān)于決策樹算法的 Sklearn 實(shí)現(xiàn)，可以參考這篇文章。

決策樹

決策樹是一種基本的分類與回歸方法。在分類問題中，表示基于特征對(duì)實(shí)例進(jìn)行分類的過程。它可以認(rèn)為是 if-then 規(guī)則的集合，也可以認(rèn)為是定義在特征空間與類空間上的條件概率分布。

決策樹學(xué)習(xí)通常包括 3 個(gè)步驟：特征選擇、決策樹的生成和決策樹的修剪。這些決策樹學(xué)習(xí)的思想主要來源于由 Quinlan 在 1986 年提出的 ID3 算法和 1993 年提出的 C4.5 算法，以及由 Breiman 等人在 1984 年提出的 CART 算法。這三個(gè)算法最大的不同在于特征選擇的指標(biāo)上，三者分別使用：信息增益、信息增益率以及基尼指數(shù)作為特征選擇指標(biāo)。本文將介紹 ID3 以及 C4.5 算法，并在下一篇文章中介紹 CART 算法。

1. 特征選擇

特征選擇在于選取對(duì)訓(xùn)練數(shù)據(jù)具有分類能力的特征，這樣可以提高決策樹學(xué)習(xí)的效率。如果利用一個(gè)特征進(jìn)行分類的結(jié)果與隨機(jī)分類的結(jié)果沒有很大差別，則稱這個(gè)特征是沒有分類能力的。

通常特征選擇的準(zhǔn)則是信息增益或信息增益率。

1.1 熵

熵（entropy）是表示隨機(jī)變量不確定性的度量。設(shè) $X$ 是一個(gè)取有限個(gè)值的離散隨機(jī)變量，其概率分布為：

$$P(X=x_i)=p_i,i=1,2,...,n$$

則隨機(jī)變量 $X$ 的熵定義為：

$$H(X)=?\sum _{i=1}^n{p}_i\log p_i\text{\hspace{1em}(1)}$$

若 $p_i=0$，則定義 $0?\log 0=0$，通常式 (1) 中的對(duì)數(shù)以 2 或 e 為底，單位為比特（bit）或納特（nat）。由此可知，熵只依賴于 $X$ 的分布，而與 $X$ 的取值無關(guān)，所以也可以將 $X$ 的熵記做 $H(p)$，即：

$$H(p)=?\sum _{i=1}^n{p}_i\log p_i\text{\hspace{1em}(2)}$$

熵越大，隨機(jī)變量的不確定性就越大，由此可以驗(yàn)證：

$$0\le H(p)\le \log n\text{\hspace{1em}(3)}$$

1.2 條件熵

設(shè)由隨機(jī)變量 $(X,Y)$，其聯(lián)合概率分布為：

$$P(X=x_i,Y=y_j)=p_{ij},i=1,2,...,n;j=1,2,...,m$$

條件熵 $H(Y|X)$ 表示在已知隨機(jī)變量 $X$ 的條件下隨機(jī)變量 $Y$ 的不確定性，其定義為 $X$ 給定條件下 $Y$ 的條件概率分布的熵的 $X$ 的數(shù)學(xué)期望：

$$H(Y|X)=\sum _{i=1}^n{p}_{i}H(Y|X=x_i)\text{\hspace{1em}(4)}$$

其中 $p_i=P(X=x_i),i=1,2,...,n$。

當(dāng)熵和條件熵中的概率由數(shù)據(jù)估計(jì)得到時(shí)，所對(duì)應(yīng)的熵與條件熵分別稱為經(jīng)驗(yàn)熵（emprical entropy）和經(jīng)驗(yàn)條件熵（empirical conditional emtropy）。

1.3 信息增益

信息增益（information gain）表示得知特征 $X$ 的信息而使類 $Y$ 的信息不確定性減少的程度。

特征 $A$ 對(duì)訓(xùn)練數(shù)據(jù)集 $D$ 的信息增益 $g(D,A)$，定義為集合 $D$ 的經(jīng)驗(yàn)熵 $H(D)$ 與特征 $A$ 給定條件下 $D$ 的經(jīng)驗(yàn)條件熵 $H(D|A)$ 之差，即：

$$g(D,A)=H(D)?H(D|A)\text{\hspace{1em}(5)}$$

一般地，熵 $H(Y)$ 與條件熵 $H(D|A)$ 之差稱為 互信息（mutual information）。決策樹學(xué)習(xí)中的信息增益等價(jià)于訓(xùn)練數(shù)據(jù)集中類與特征的互信息。

1.4 信息增益率

信息增益率的大小時(shí)相對(duì)于訓(xùn)練數(shù)據(jù)集而言的，在分類問題困難時(shí)，也就是說在訓(xùn)練數(shù)據(jù)集的經(jīng)驗(yàn)熵大的時(shí)候，信息增益值會(huì)偏大，信息增益值會(huì)偏大。反之，信息增益值會(huì)偏小。使用信息增益比（information gain ratio）可以對(duì)這一問題進(jìn)行校正，這是特征選擇的另一準(zhǔn)則。

特征 $A$ 對(duì)訓(xùn)練數(shù)據(jù)集 $D$ 的信息增益率 $g_R(D,A)$ 定義為其信息增益 $g(D,A)$ 與訓(xùn)練數(shù)據(jù)集 $D$ 的經(jīng)驗(yàn)熵 $H(D)$ 之比：

$$g_R(D,A)=\frac{g(D,A)}{H(D)}\text{\hspace{1em}(6)}$$

2. 決策樹生成

---

設(shè)訓(xùn)練集數(shù)據(jù)為 $D$，$|D|$ 表示其樣本容量，即樣本個(gè)數(shù)。

設(shè)有 $K$ 個(gè)類 $C_k,k=1,2,...,K$，$|C_k|$ 為屬于類 $C_k$ 的樣本個(gè)數(shù)，因此 ${\sum }_{k=1}^K|C_k|=|D|$。

設(shè)特征 $A$ 有 $n$ 個(gè)不同的取值 $\{a_1,a_2,...,a_n\}$，根據(jù)特征 $A$ 的取值將 $D$ 劃分為 $n$ 個(gè)子集 $D_1,D_2,...,D_n$，$|D_i|$ 為 $D_i$ 的樣本個(gè)數(shù)，${\sum }_{i=1}^n|D_i|=D$。

記子集 $D_i$ 中屬于類 $C_k$ 的樣本的集合為 $D_{ik}$，即 $D_{ik}=D?C_k$，$|D_{ik}|$ 為 $D_{ik}$ 的樣本個(gè)數(shù)。

因此，信息增益以及信息增益率計(jì)算如下：

算法1 信息增益及信息增益率的算法

輸入：訓(xùn)練數(shù)據(jù)集 $D$ 和特征 $A$；

輸出：特征 $A$ 對(duì)訓(xùn)練數(shù)據(jù)集 $D$ 的信息增益 $g(D,A)$ 以及信息增益率 $g_R(D,A)$。

（1）計(jì)算數(shù)據(jù)集 $D$ 的經(jīng)驗(yàn)熵 $H(D)$：

$$H(D)=?\sum _{i=1}^n\frac{|C_k|}{|D|}lo{g}_2\frac{|D_k|}{|D|}\text{\hspace{1em}(7)}$$

（2）計(jì)算特征 $A$ 對(duì)數(shù)據(jù)集 $D$ 的經(jīng)驗(yàn)條件熵 $H(D|A)$：

$$\begin{array}{rl}H(D|A)& =\sum _{i=1}^n\frac{|D_i|}{|D|}H(D_i)\\ & =?\sum _{i=1}^n\frac{|D_i|}{|D|}\sum _{i=1}^n\frac{|D_{ik}|}{|D_i|}lo{g}_2\frac{|D_{ik}|}{|D_i|}\end{array}\text{\hspace{1em}(8)}$$

（3）計(jì)算信息增益：

$$g(D,A)=H(D)?H(D|A)\text{\hspace{1em}(9)}$$

（4）計(jì)算信息增益率：

$$g_R(D,A)=\frac{g(D,A)}{H(D)}\text{\hspace{1em}(10)}$$

2.1 ID3 算法

輸入：訓(xùn)練數(shù)據(jù)集 $D$，特征集 $A$，閾值 $\epsilon$；

輸出：決策樹 $T$。

（1）若 $D$ 中所有實(shí)例屬于同一類 $C_k$，則 $T$ 為單節(jié)點(diǎn)樹，并將類 $C_k$ 作為該節(jié)點(diǎn)的類標(biāo)記，返回 $T$；

（2）若 $A=?$，則 $T$ 為單節(jié)點(diǎn)樹，并將 $D$ 中實(shí)例數(shù)最大的類 $C_k$ 作為該節(jié)點(diǎn)的類標(biāo)記，返回 $T$；

（3）否則，按算法1（1-3）計(jì)算 $A$ 中各特征對(duì) $D$ 的信息增益，選擇信息增益最大的特征 $A_g$；

（4）如果 $A_g$ 的信息增益小于閾值 $\epsilon$，則置 $T$ 為單節(jié)點(diǎn)樹，并將 $D$ 中實(shí)例數(shù)最大的類 $C_K$ 作為該節(jié)點(diǎn)的類標(biāo)記，返回 $T$；

（5）否則，對(duì) $A_g$ 的每一可能值 $a_i$，依 $A_g=a_i$ 將 $D$ 分隔為若干非空子集 $D_i$，將 $D_i$ 中實(shí)例數(shù)最大的類作為標(biāo)記，構(gòu)建子節(jié)點(diǎn)，由節(jié)點(diǎn)及其自己點(diǎn)構(gòu)造數(shù) $T$，返回 $T$；

（6）對(duì)第 $i$ 個(gè)子節(jié)點(diǎn)，以 $D_i$ 為訓(xùn)練集，以 $A?\{A_g\}$ 為特征集，遞歸地調(diào)用步(1)～步(5)，得到子樹 $T_i$，返回 $T_i$。

2.2 C4.5 算法

C4.5 與 ID3 相比，只是將 ID3 算法中的信息增益換成了信息增益率，因此有：

輸入：訓(xùn)練數(shù)據(jù)集 $D$，特征集 $A$，閾值 $\epsilon$；

輸出：決策樹 $T$。

（1）若 $D$ 中所有實(shí)例屬于同一類 $C_k$，則 $T$ 為單節(jié)點(diǎn)樹，并將類 $C_k$ 作為該節(jié)點(diǎn)的類標(biāo)記，返回 $T$；

（2）若 $A=?$，則 $T$ 為單節(jié)點(diǎn)樹，并將 $D$ 中實(shí)例數(shù)最大的類 $C_k$ 作為該節(jié)點(diǎn)的類標(biāo)記，返回 $T$；

（3）否則，按算法1（1-4）計(jì)算 $A$ 中各特征對(duì) $D$ 的信息增益，選擇信息增益最大的特征 $A_g$；

（4）如果 $A_g$ 的信息增益小于閾值 $\epsilon$，則置 $T$ 為單節(jié)點(diǎn)樹，并將 $D$ 中實(shí)例數(shù)最大的類 $C_K$ 作為該節(jié)點(diǎn)的類標(biāo)記，返回 $T$；

（5）否則，對(duì) $A_g$ 的每一可能值 $a_i$，依 $A_g=a_i$ 將 $D$ 分隔為若干非空子集 $D_i$，將 $D_i$ 中實(shí)例數(shù)最大的類作為標(biāo)記，構(gòu)建子節(jié)點(diǎn)，由節(jié)點(diǎn)及其自己點(diǎn)構(gòu)造數(shù) $T$，返回 $T$；

（6）對(duì)第 $i$ 個(gè)子節(jié)點(diǎn)，以 $D_i$ 為訓(xùn)練集，以 $A?\{A_g\}$ 為特征集，遞歸地調(diào)用步(1)～步(5)，得到子樹 $T_i$，返回 $T_i$。

3. 決策樹剪枝

3.1 預(yù)剪枝

預(yù)剪枝是在決策樹生成之前通過限制條件，來防止樹過度生長而造成過擬合，常見的有：

最大深度 max_depth

每片葉子的最小樣本數(shù) min_samples_leaf

每次分裂的最小樣本數(shù) min_samples_split

最大特征數(shù) max_features

關(guān)于這些參數(shù)的詳細(xì)介紹，可以參考這篇文章。

3.2 后剪枝

后剪枝先從訓(xùn)練集生成一顆完整決策樹，通過向損失函數(shù)中增加模型復(fù)雜度懲罰來對(duì)已生成的決策樹進(jìn)行簡(jiǎn)化。

設(shè)樹 $T$ 的葉節(jié)點(diǎn)個(gè)數(shù)為 $|T|$，$t$ 是樹 $T$ 的葉節(jié)點(diǎn)，該葉節(jié)點(diǎn)有 $N_t$ 個(gè)樣本點(diǎn)，其中 $k$ 類的樣本點(diǎn)有 $N_{tk}$ 個(gè)，$k=1,2,...,K$，$H_t(T)$ 為葉節(jié)點(diǎn) $t$ 上的經(jīng)驗(yàn)熵，$\alpha \geq 0 $ 為參數(shù)，則決策樹后剪枝的損失函數(shù)（Cost-Complexity Pruning）可以定義為：

$$C_{\alpha }(T)=\sum _{t=1}^{|T|}{N}_t{H}_t(T)+\alpha |T|\text{\hspace{1em}(11)}$$

其中經(jīng)驗(yàn)熵為：

$$H_t(T)=?\sum _k\frac{N_{ik}}{N_t}log\frac{N_{ik}}{N_t}\text{\hspace{1em}(12)}$$

令 (11) 式右端第一項(xiàng)為 $C(T)$：

$$\begin{array}{rl}C(T)& =\sum _{t=1}^{|T|}{N}_t{H}_t(T)\\ & =?\sum _{t=1}^{|T|}{N}_t\sum _k\frac{N_{ik}}{N_t}log\frac{N_{ik}}{N_t}\end{array}\text{\hspace{1em}(13)}$$

因此式 (11) 可以寫作：

$$C_{\alpha }(T)=C(T)+\alpha |T|\text{\hspace{1em}(14)}$$

其中，$C(T)$ 表示模型對(duì)訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差，即模型與訓(xùn)練數(shù)據(jù)的擬合程度；

$|T|$ 表示模型復(fù)雜度，參數(shù) $\alpha \ge 0$ 控制兩者之間的影響。較大的 $\alpha$ 促使選擇較簡(jiǎn)單的模型，較小的 $\alpha$ 促使選擇較復(fù)雜的模型， $\alpha =0$ 意味者只考慮模型與訓(xùn)練數(shù)據(jù)的擬合程度，不考慮模型的復(fù)雜度。

剪枝，就是當(dāng) $\alpha$ 確定時(shí)，選擇損失函數(shù)最小的模型，即損失函數(shù)最小的子樹。

當(dāng) $\alpha$ 確定時(shí)，子樹越大，往往與訓(xùn)練數(shù)據(jù)的擬合越好，但是模型的復(fù)雜度越高；相反，子樹越小，模型復(fù)雜度就越低，但是往往與訓(xùn)練數(shù)據(jù)的擬合不好，損失函數(shù)正好表示了對(duì)兩者的平衡。

可以看到，ID3 和 C4.5 決策樹生成只考慮了通過提高信息增益或信息增益率來對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行更好的擬合。而決策樹剪枝通過優(yōu)化損失函數(shù)還考慮了減小模型復(fù)雜度。

決策樹生成學(xué)習(xí)局部的模型，而決策樹剪枝學(xué)習(xí)整體的模型。

算法2 樹的剪枝算法

輸入：生成算法產(chǎn)生的整個(gè)樹 $T$，參數(shù) $\alpha$；

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

（1）計(jì)算每個(gè)節(jié)點(diǎn)的經(jīng)驗(yàn)熵；

（2）遞歸地從樹的葉節(jié)點(diǎn)向上回縮：

\quad \quad設(shè)一組葉節(jié)點(diǎn)回縮到其父節(jié)點(diǎn)之前與之后的整體樹分別為 $T_B$ 與 $T_A$，其對(duì)應(yīng)的損失函數(shù)值分別是 $C_{\alpha }(T_B)$ 與 $C_{\alpha }(T_A)$，如果：

$$C_{\alpha }(T_A)\le C_{\alpha }(T_B)\text{\hspace{1em}(15)}$$

\quad \quad 則進(jìn)行剪枝，即將父節(jié)點(diǎn)變?yōu)樾碌娜~節(jié)點(diǎn)。

（3）返回 (2) ，直到不能繼續(xù)為止，得到損失函數(shù)最小的子樹 $T_{\alpha }$。

參考文獻(xiàn)

[1] 李航. 統(tǒng)計(jì)學(xué)習(xí)方法[M]. 北京: 清華大學(xué)出版社, 2012: 55-66.

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的监督学习 | ID3 C4.5 决策树原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。