更多文章可以訪問(wèn)我的博客Aengus | Blog

決策樹(shù)的概念比較簡(jiǎn)單，可以將決策樹(shù)看做一個(gè)if-then集合：如果“條件1”，那么...。決策樹(shù)學(xué)習(xí)的損失函數(shù)通常是正則化后極大似然函數(shù)，學(xué)習(xí)的算法通常是一個(gè)遞歸的選擇最優(yōu)特征，并根據(jù)該特征對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行分割，使得對(duì)各個(gè)子數(shù)據(jù)集有一個(gè)最好的分類(lèi)的過(guò)程。可以看出，決策樹(shù)算法一般包含特征選擇，決策樹(shù)的生成與決策樹(shù)的剪枝過(guò)程。

特征選擇

信息增益

熵和條件熵

在了解信息增益之前需先給出熵和條件熵的定義。

熵代表隨機(jī)變量不確定性的度量，設(shè)在一個(gè)有限個(gè)值的離散隨機(jī)變量，其概率分布為
$P(X=x_i) = p_i, i=1,2,\cdots,n$
則隨便變量 $X$ 的熵定義為
$H(X) = - \sum^n_{i=1}p_i \log p_i$
如果 $p_i=0$ ，則定義 $0\log 0=0$ ；對(duì)數(shù)一般取以2為底或者以 $e$ 為底，這時(shí)候熵的單位分別稱(chēng)作比特（bit）和納特（nat）。由定義可知，熵只依賴于 $X$ 的分布，而和 $X$ 的取值無(wú)關(guān)，因此也可以將 $X$ 的熵記作 $H(p)$ ，即：
$H(p) = - \sum^n_{i=1}p_i \log p_i$
熵越大，隨機(jī)變量的不確定性就越大，根據(jù)定義可以得到：
$0 \leq H(p) \leq \log n$
條件熵 $H(Y|X)$ 表示在已知隨機(jī)變量 $X$ 的條件下，隨機(jī)變量 $Y$ 的不確定性。隨機(jī)變量 $X$ 給定的條件下隨機(jī)變量 $Y$ 的條件熵 $H(Y|X)$ ，定義為 $X$ 給定條件下 $Y$ 的條件概率分布的熵對(duì) $X$ 的數(shù)學(xué)期望：
$H(Y|X) = \sum^n_{i=1}p_iH(Y|X=x_i)$
其中， $p_i=P(X=x_i), i=1,2, \cdots, n$ 。

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

定義

信息增益表示得知特征 $X$ 的信息而使得類(lèi) $Y$ 的信息的不確定性減少的程度。

特征 $A$ 對(duì)訓(xùn)練集 $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)$
一般來(lái)說(shuō)，熵 $H(Y)$ 與條件熵 $H(Y|X)$ 之差稱(chēng)作互信息。

根據(jù)信息增益選擇特征的方法是選擇信息增益最大的特征。

信息增益算法

對(duì)于給定的訓(xùn)練集 $D$ 和特征 $A$ ，計(jì)算特征 $A$ 對(duì)于訓(xùn)練集 $D$ 的信息增益 $g(D,A)$ 一般有以下步驟：

（1）計(jì)算數(shù)據(jù)集 $D$ 的經(jīng)驗(yàn)熵 $H(D)$ ：
$H(D) = - \sum^K_{k=1} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}$
（2）計(jì)算特征 $A$ 對(duì)數(shù)據(jù)集 $D$ 的經(jīng)驗(yàn)條件熵 $H(D|A)$ ：
$H(D|A)=\sum^n_{i=1}\frac{|D_i|}{|D|}H(D_i)=- \sum^n_{i=1}\frac{|D_i|}{|D|}\sum^K_{k=1}\frac{|D_{ik}|}{|D_i|} \log_2 \frac{|D_{ik}|}{|D_i|}$
（3）計(jì)算信息增益
$g(D,A)=H(D)-H(D|A)$

信息增益比

以信息增益作為劃分訓(xùn)練數(shù)據(jù)集的特征，存在偏向于選擇取值較多的特征的問(wèn)題。使用信息增益比可以校正這一問(wèn)題。

定義

對(duì)于給定的訓(xùn)練集 $D$ 和特征 $A$ ，特征 $A$ 對(duì)于訓(xùn)練集 $D$ 的信息增益比 $g_R(D,A)$ 定義為其信息增益 $g(D,A)$ 與訓(xùn)練數(shù)據(jù)集 $D$ 關(guān)于特征 $A$ 的值的熵 $H_A(D)$ 之比，即：
$g_R(D,A) = \frac{g(D,A)}{H_A(D)}$
其中， $H_A(D)=- \sum^n_{i=1} \frac{|D_i|}{|D|} \log_2\frac{|D_i|}{|D|}$ ， $n$ 是特征 $A$ 取值的個(gè)數(shù)。

決策樹(shù)的生成

ID3算法

ID3算法的核心是在決策樹(shù)各個(gè)結(jié)點(diǎn)上應(yīng)用信息增益選擇特征，遞歸的構(gòu)建決策樹(shù)。ID3相當(dāng)于用極大似然法進(jìn)行概率模型的選擇。

假設(shè)輸入訓(xùn)練數(shù)據(jù)集 $D$ ，特征集 $A$ 和閾值 $\varepsilon$ ，按照以下步驟求得決策樹(shù) $T$ ：

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

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

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

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

（5）否則，對(duì) $A_g$ 的每一個(gè)可能值 $a_i$ ，依 $A_g=a_i$ 將 $D$ 分割為若干非空子集 $D_i$ ，將 $D_i$ 中實(shí)例數(shù)最大的類(lèi)作為標(biāo)記，構(gòu)建子結(jié)點(diǎn)，由結(jié)點(diǎn)及其子結(jié)點(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）步，得到子樹(shù) $T_i$ 并返回；

C4.5算法

C4.5算法和ID3算法類(lèi)似，不過(guò)是用信息增益比替換掉了信息增益；

假設(shè)輸入訓(xùn)練數(shù)據(jù)集 $D$ ，特征集 $A$ 和閾值 $\varepsilon$ ，按照以下步驟求得決策樹(shù) $T$ ：

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

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

可以看到兩個(gè)算法除了加粗的部分，其他部分都一樣。

決策樹(shù)的剪枝

決策樹(shù)生成算法遞歸的產(chǎn)生決策樹(shù)直到不能繼續(xù)下去為止，這樣的樹(shù)往往對(duì)訓(xùn)練數(shù)據(jù)分類(lèi)比較準(zhǔn)確，但是對(duì)未知的測(cè)試數(shù)據(jù)往往沒(méi)那么精準(zhǔn)，即出現(xiàn)過(guò)擬合現(xiàn)象。對(duì)于這種情況可以將決策樹(shù)進(jìn)行簡(jiǎn)化，也被稱(chēng)為決策樹(shù)的剪枝。

決策樹(shù)的剪枝往往通過(guò)極小化決策樹(shù)整體的損失函數(shù)或代價(jià)函數(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_t$ 個(gè)樣本點(diǎn)，其中 $k$ 類(lèi)的樣本點(diǎn)有 $N_{tk}$ 個(gè)， $k=1, 2, \cdots, K$ ， $H_t(T)$ 為葉結(jié)點(diǎn) $t$ 上的經(jīng)驗(yàn)熵， $\alpha \geq0$ 為參數(shù)，則決策樹(shù)學(xué)習(xí)的損失函數(shù)可以定義為：
$C_\alpha (T) = \sum^{|T|}_{t=1}N_t H_t(T)+\alpha |T|$
其中經(jīng)驗(yàn)熵為：
$H_t(T) = -\sum_k \frac{N_{tk}}{N_t} \log \frac{N_{tk}}{N_t}$
在損失函數(shù)中，將損失函數(shù)右端的第一項(xiàng)記作
$C(T) = \sum^{|T|}_{t=1}N_t H_t(T) = -\sum^{|T|}_{t=1} \sum^K_{k=1}N_{tk} \log \frac{N_{tk}}{N_t}$
這時(shí)有
$C_\alpha(T) = C(T)+\alpha|T|$
剪枝就意味著當(dāng) $\alpha$ 確定時(shí)，選擇損失函數(shù)最小的模型，即損失函數(shù)最小的子樹(shù)（ $\alpha$ 較大時(shí)促使選擇比較簡(jiǎn)單的模型，較小時(shí)促進(jìn)選擇復(fù)雜的模型）。

剪枝算法

輸入生成的決策樹(shù) $T$ 以及參數(shù) $\alpha$ ，輸出剪枝后的子樹(shù) $T_\alpha$ ：

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

（2）遞歸地從樹(shù)的葉結(jié)點(diǎn)向上回縮，設(shè)一組葉結(jié)點(diǎn)回縮到其父結(jié)點(diǎn)之前與之后的整體樹(shù)分別為 $T_B$ 與 $T_A$ ，其對(duì)應(yīng)的損失函數(shù)值分別是 $C_\alpha(T_B)$ 與 $C_\alpha(T_A)$ ，如果
$C_\alpha(T_A) \leq C_\alpha(T_B)$
則進(jìn)行剪枝，即將父結(jié)點(diǎn)變?yōu)樾碌娜~結(jié)點(diǎn)；

（3）重復(fù)步驟（2），直至不能繼續(xù)為止，得到損失函數(shù)最小的子樹(shù) $T_\alpha$ ；

CART算法

分類(lèi)與回歸樹(shù)（classification and regression tree, CART）模型是應(yīng)用廣泛的決策樹(shù)學(xué)習(xí)方法，CART同樣由特征選擇、樹(shù)的生成以及剪枝組成，既可以用于分類(lèi)也可以用于回歸。

CART是在給定輸入隨機(jī)變量 $X$ 的條件下輸出隨機(jī)變量 $Y$ 的條件概率分布的學(xué)習(xí)方法。CART假設(shè)決策樹(shù)是二叉樹(shù)，內(nèi)部結(jié)點(diǎn)特征的取值是“是”或“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。CART算法由以下兩步組成：

（1）決策樹(shù)生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹(shù)，生成的決策樹(shù)要盡量大；

（2）決策樹(shù)剪枝：用驗(yàn)證數(shù)據(jù)集對(duì)已生成的樹(shù)進(jìn)行剪枝并選擇最優(yōu)子樹(shù)，這時(shí)用損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)；

CART生成

對(duì)于回歸樹(shù)用平方誤差最小化準(zhǔn)則，對(duì)分類(lèi)樹(shù)用基尼指數(shù)最小化準(zhǔn)則進(jìn)行特征選擇，生成二叉樹(shù)。

回歸樹(shù)的生成

一顆回歸樹(shù)對(duì)應(yīng)著輸入空間的一個(gè)劃分以及在劃分單元上的輸出值。假設(shè)將輸入空間劃分為 $M$ 個(gè)單元 $R_1,R_2,\cdots,R_M$ ，并且在每個(gè)單元 $R_m$ 上有一個(gè)固定的輸出值 $c_m$ ，于是回歸樹(shù)模型可表示為：
$f(x) = \sum^M_{m=1}c_m I(x \in R_m)$
當(dāng)輸入空間的劃分確定時(shí)，可以用用平方誤差 $\sum_{x_i \in R_m} (y_i - f(x_i))^2$ 來(lái)表示回歸樹(shù)對(duì)于訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差，用平方誤差最小的準(zhǔn)則求解每個(gè)單元上的最優(yōu)輸出值。易知單元 $R_m$ 上的 $c_m$ 的最優(yōu)值 $\hat{c}_m$ 是 $R_m$ 上所有輸入實(shí)例 $x_i$ 對(duì)應(yīng)的輸出 $y_i$ 的均值，即
$\hat{c}_m = ave(y_i|x_i \in R_m)$
問(wèn)題是怎樣對(duì)輸入空間進(jìn)行劃分，也就是如何選擇劃分結(jié)點(diǎn)：

假設(shè)輸入訓(xùn)練集 $D$ ，在訓(xùn)練數(shù)據(jù)集所在的輸入空間中，遞歸地將每個(gè)區(qū)域劃分為兩個(gè)子區(qū)域并決定每個(gè)子區(qū)域上的輸出值，構(gòu)建二叉決策樹(shù)。具體步驟為：

（1）選擇第 $j$ 個(gè)變量 $x^{(j)}$ 和它取的值 $s$ 作為劃分變量和劃分點(diǎn)，并定義兩個(gè)區(qū)域：
$R_1(j,s) = \{ x|x^{(j)} \leq s \},R_2(j,s)=\{ x|x > s \}$
然后尋找最優(yōu)劃分變量 $j$ 和最優(yōu)劃分點(diǎn) $s$ ，具體的，求解：
$\min_{j,s} \left[ \min_{c_1}\sum_{x_i \in R_1(j,s)}(y_i -c_1)^2 + \min_{c_2}\sum_{x_i \in R_2(j,s)}(y_i - c_2)^2 \right]$
遍歷變量 $j$ ，對(duì)固定的劃分變量 $j$ 掃描切分點(diǎn) $s$ ，選擇式上式達(dá)到最小值的 $(j,s)$ ；

（2）用選定的 $(j,s)$ 劃分區(qū)域 $R_1,R_2$ 并決定相應(yīng)的輸出值：
$R_1(j,s) = \{ x|x^{(j)} \leq s \},R_2(j,s)=\{x|x^{(j)} > s\}$

$\hat{c}_m = \frac{1}{N_m} \sum_{x_i \in R_m(j,s)}y_i, x \in R_m,m=1,2$

（3）繼續(xù)對(duì) $R_1,R_2$ 兩個(gè)子區(qū)域調(diào)用步驟（1），（2），直到滿足停止條件；

（4）將輸入空間劃分為 $M$ 個(gè)區(qū)域 $R_1,R_2,\cdots,R_M$ ，生成決策樹(shù)：
$f(x) = \sum^M_{m=1}\hat{c}_m I(x \in R_m)$

分類(lèi)樹(shù)的生成

基尼指數(shù)：在分類(lèi)問(wèn)題中，假設(shè)有 $k$ 個(gè)類(lèi)，樣本點(diǎn)屬于第 $k$ 類(lèi)的概率是 $p_k$ ，則概率分布的基尼指數(shù)定義為：
$Gini(p) = \sum^K_{k=1}p_k(1-p_k) = 1 - \sum^K_{k=1}p_k^2$
對(duì)于二分類(lèi)問(wèn)題，若樣本點(diǎn)屬于第一個(gè)分類(lèi)的概率為 $p$ ，則概率分布的基尼指數(shù)為：
$Gini(p) = 2p(1-p)$
對(duì)于給定的樣本集合 $D$ ，其基尼指數(shù)為：
$Gini(D) = 1-\sum^K_{k=1}(\frac{|C_k|}{|D|})^2$
這里， $C_k$ 是 $D$ 中屬于第 $k$ 類(lèi)的樣本子集， $K$ 是類(lèi)的個(gè)數(shù)。

如果樣本集合 $D$ 根據(jù)特征 $A$ 是否取值 $\alpha$ 被分割成 $D_1$ 和 $D_2$ 兩部分，即：
$D_1 = \{ (x,y) \in D|A(x)=\alpha \},D_2 = D - D_1$
那么在特征 $A$ 的條件下，集合 $D$ 的基尼指數(shù)定義為：
$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$
基尼指數(shù) $Gini(D)$ 代表集合 $D$ 的不確定性，基尼指數(shù) $Gini(D,A)$ 表示經(jīng) $A=\alpha$ 分割后集合 $D$ 的不確定性?；嶂笖?shù)越大代表不確定性程度越大。

假設(shè)輸入訓(xùn)練數(shù)據(jù)集 $D$ 以及停止計(jì)算的條件，根據(jù)訓(xùn)練集，從根結(jié)點(diǎn)開(kāi)始，遞歸地對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行以下操作，構(gòu)建決策樹(shù)：

（1）計(jì)算現(xiàn)有特征對(duì)訓(xùn)練數(shù)據(jù)集的基尼指數(shù)。此時(shí)，對(duì)每一個(gè)特征 $A$ ，對(duì)其可能取的每個(gè)值 $\alpha$ ，根據(jù)樣本點(diǎn)對(duì) $A=\alpha$ 的測(cè)試為“是”或“否”，將 $D$ 分為 $D_1$ 和 $D_2$ 兩部分，利用上式計(jì)算 $A=\alpha$ 的基尼指數(shù)；

（2）對(duì)所有可能的特征 $A$ 以及他，他們所有可能的切分點(diǎn) $\alpha$ 中，選擇基尼指數(shù)最小的特征及其對(duì)應(yīng)的切分點(diǎn)作為最優(yōu)特征與最優(yōu)切分點(diǎn)。依最優(yōu)特征與最優(yōu)切分點(diǎn)，從現(xiàn)結(jié)點(diǎn)生成兩個(gè)子結(jié)點(diǎn)，將訓(xùn)練集依特征分配到兩個(gè)子結(jié)點(diǎn)去；

（3）對(duì)兩個(gè)子結(jié)點(diǎn)遞歸調(diào)用（1）和（2）步驟，直至滿足停止條件；

（4）生成CART決策樹(shù)；

算法停止的條件是結(jié)點(diǎn)中樣本個(gè)數(shù)小于預(yù)定閾值或者樣本的基尼指數(shù)小于預(yù)定閾值（此時(shí)此結(jié)點(diǎn)上的樣本基本屬于同一類(lèi)），或者沒(méi)有更多特征。

CART剪枝

輸入為CART算法生成的決策樹(shù) $T_0$ ，輸出為最優(yōu)決策樹(shù) $T_\alpha$ ，步驟如下：

（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} \\ \alpha = \min (\alpha, g(t))$
這里， $T_t$ 表示以 $t$ 為根結(jié)點(diǎn)的子樹(shù)， $C(T_t)$ 是對(duì)訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差， $|T_t|$ 是 $T_t$ 的葉結(jié)點(diǎn)個(gè)數(shù)；

（4）對(duì) $g(t)=\alpha$ 的內(nèi)部結(jié)點(diǎn) $t$ 進(jìn)行剪枝，并對(duì)葉結(jié)點(diǎn) $t$ 以多數(shù)表決法決定其類(lèi)，得到樹(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ù)序列 $T_0,T_1,\cdots,T_n$ 中選取最優(yōu)子樹(shù) $T_\alpha$ ；

參考

李航《統(tǒng)計(jì)學(xué)習(xí)方法（第二版）》第五章

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

統(tǒng)計(jì)學(xué)習(xí)方法筆記之決策樹(shù)

統(tǒng)計(jì)學(xué)習(xí)方法筆記之決策樹(shù)

特征選擇

信息增益

熵和條件熵

定義

信息增益算法

信息增益比

定義

決策樹(shù)的生成

ID3算法

C4.5算法

決策樹(shù)的剪枝

剪枝算法

CART算法

CART生成

回歸樹(shù)的生成

分類(lèi)樹(shù)的生成

CART剪枝

參考

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

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

統(tǒng)計(jì)學(xué)習(xí)方法筆記之決策樹(shù)

特征選擇

信息增益

熵和條件熵

定義

信息增益算法

信息增益比

定義

決策樹(shù)的生成

ID3算法

C4.5算法

決策樹(shù)的剪枝

剪枝算法

CART算法

CART生成

回歸樹(shù)的生成

分類(lèi)樹(shù)的生成

CART剪枝

參考

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

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av