《統(tǒng)計(jì)學(xué)習(xí)方法》讀書筆記——決策樹

（僅記錄自己的學(xué)習(xí)心得，默認(rèn)記錄自己之前不太清楚或者有新的心得的部分，所以可能并不全面。）

ID3 算法：依據(jù)信息增益選擇作為結(jié)點(diǎn)的特征，且不能重復(fù)選取。

C4.5 算法： 依據(jù)信息增益比選擇結(jié)點(diǎn)的特征，也不能重復(fù)選特征。

剪枝【重要的部分】：通過極小化決策樹整體的損失函數(shù)或代價(jià)函數(shù)實(shí)現(xiàn)。

【介紹損失函數(shù)】

一些概念：

經(jīng)驗(yàn)熵：H_{t}(T) = -\sum_{k} \frac{N_{tk} }{N_{t} }log\frac{N_{tk} }{N_{t} } ? ? ? ??

某個(gè)葉子的樣本個(gè)數(shù)為N_{t} , 其中屬于第k類的有N_{tk} 個(gè)。

這個(gè)形式跟熵的定義很像：H(X)=-\sum_{i=1}^np_{i}logp_{i} ,?p_{i} 為隨機(jī)變量X取不同值的概率。（如果僅有兩種取值，概率為0或1時(shí)熵的值最小是0，因?yàn)槭谴_定情況，0.5時(shí)熵的值最大，因?yàn)椴淮_定性最大，因此熵越大代表隨機(jī)變量取值不確定性越強(qiáng)，如下圖：）（我猜公式里取log也是因?yàn)樾枰谧宰兞繛?時(shí)需要為0，又因?yàn)閘og函數(shù)小于1時(shí)是負(fù)數(shù)，所以整個(gè)公式需要取負(fù)號(hào)）


繼續(xù)看經(jīng)驗(yàn)熵的公式，可以看出概率的位置為每個(gè)葉子里第k類樣本占整個(gè)葉子樣本的比例，也就可以將經(jīng)驗(yàn)熵理解為以類別為隨機(jī)變量的熵，而因?yàn)槭窃谕粋€(gè)葉子里，所以我們希望這個(gè)熵越小越好。因?yàn)橐粋€(gè)葉子的類別由里面大多數(shù)的類別決定，所以經(jīng)驗(yàn)熵越小，預(yù)測(cè)誤差越小。

損失函數(shù)的概念：

整個(gè)決策樹T的損失函數(shù)：\sum_{t=1}^TN_{t} H_{t}(T)+\alpha \vert T \vert ，? ? ? ??\vert T \vert 為葉結(jié)點(diǎn)的個(gè)數(shù)，t為葉結(jié)點(diǎn)

公式第一項(xiàng)為每個(gè)葉子的結(jié)點(diǎn)數(shù)*經(jīng)驗(yàn)熵，書中說這表明了模型對(duì)訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差。由此可以推測(cè)經(jīng)驗(yàn)熵表示了對(duì)每一個(gè)樣本的預(yù)測(cè)誤差，（因?yàn)槲依斫獾撵氐暮x一直是一個(gè)度量的概念，我不太清楚這是否是一個(gè)量化的值，所以這塊理解不是很透徹）

公式的第二項(xiàng)表示模型的復(fù)雜程度。

剪枝的過程就是在\alpha 確定時(shí)，選擇損失函數(shù)最小的子樹。因此：

\alpha 較大意味著會(huì)選擇復(fù)雜度低的子樹，簡(jiǎn)單的模型；\alpha 較小意味著選擇較復(fù)雜的子樹；\alpha =0意味著只考慮模型對(duì)訓(xùn)練數(shù)據(jù)的擬合程度，不考慮復(fù)雜度。因此損失函數(shù)平衡了擬合效果和復(fù)雜度兩種因素。

【CART算法】：分類與回歸樹，二叉樹，包括決策樹生成和剪枝過程。

1）生成樹：

回歸樹：依據(jù)平方誤差最小化準(zhǔn)則進(jìn)行最優(yōu)特征的最優(yōu)分割點(diǎn)。

尋找最優(yōu)特征的最優(yōu)分割點(diǎn)：對(duì)第j個(gè)特征（書里說是第j個(gè)變量，我理解就是特征），假設(shè)切分點(diǎn)為s，使得把該特征的所有取值分成兩個(gè)部分：R_{1} （j,s）=\left\{ x\vert x^j\leq s \right\} ,R_{1} （j,s）=\left\{ x\vert x^j > s \right\} 。根據(jù)平方誤差最小準(zhǔn)則，每個(gè)區(qū)域上的最優(yōu)輸出值應(yīng)為：

c_{1}=\frac{1}{N_{1} } \sum_{x_{i}\in N_{1} } y_{i} ,c_{2}=\frac{1}{N_{2} } \sum_{x_{i}\in N_{2} } y_{i} ?？傮w的平方誤差為：

m(s)=min[min_{c1} \sum_{x_{i} \in R_{1} }(y_{i} -c1)^2+min_{c2} \sum_{x_{i} \in R_{2} }(y_{i} -c2)^2 ]。

則選取的步驟是：將該特征的取值按大小排序，通常在兩個(gè)相鄰值之間取一個(gè)劃分點(diǎn)s，計(jì)算m(s),找到最小的對(duì)應(yīng)的s，就是該特征下的最優(yōu)劃分點(diǎn)；遍歷所有的特征，找到所有特征中最小的m(s)，構(gòu)成的(j,s)就是最優(yōu)切分變量的最優(yōu)劃分點(diǎn)。

找到最優(yōu)劃分點(diǎn)后，分別對(duì)每一個(gè)區(qū)域重復(fù)上述步驟，直至平方誤差低于設(shè)定的閾值，整個(gè)樹構(gòu)建完畢。

（回歸樹這里參考了https://blog.csdn.net/aaa_aaa1sdf/article/details/81588382這篇里的例子，就很好懂了。）

分類樹：依據(jù)基尼指數(shù)選擇最優(yōu)劃分特征。

假設(shè)樣本為第k類的概率為p_{k} ,則基尼指數(shù)為：

Gini(p)=\sum_{k=1}^K p_{k} (1-p_{k}), 反應(yīng)了從一個(gè)數(shù)據(jù)集中隨機(jī)抽取兩個(gè)樣本，其類別不一致的概率。由此可知，基尼指數(shù)越小，說明數(shù)據(jù)集純度越高（與熵類似）。

CART分類樹選取特征不同于ID3等算法直接選某一個(gè)特征作為劃分點(diǎn)，它是根據(jù)某個(gè)特征是否取其中某個(gè)值劃分成兩個(gè)叉（因?yàn)槭嵌鏄洌?。所以它的步驟是：

對(duì)每個(gè)特征的每個(gè)取值，根據(jù)是否將數(shù)據(jù)集分成兩份，計(jì)算基尼指數(shù)：

Gini(D,A)=\frac{\vert D1 \vert }{\vert D \vert } Gini(D1)+\frac{\vert D2 \vert }{\vert D \vert } Gini(D2),

選擇基尼指數(shù)最小的特征及最優(yōu)劃分點(diǎn)，將數(shù)據(jù)集D分割到兩個(gè)子結(jié)點(diǎn)中，對(duì)每個(gè)結(jié)點(diǎn)重復(fù)上述步驟。

2）CART剪枝：

攏共分兩步：從底向上不斷剪枝，形成子樹序列；選擇損失函數(shù)值最小的子樹。

先說怎么生成子樹序列吧，我覺得他這個(gè)思考的過程很牛的：

從整體樹T_{0} 開始剪枝。對(duì)于T_{0} 內(nèi)部任意結(jié)點(diǎn)t，

以t為單結(jié)點(diǎn)樹的損失函數(shù)：C_{\alpha }（t）=C(t)+\alpha ,

以t為根結(jié)點(diǎn)的子樹T_{t} 的損失函數(shù)：C_{\alpha }（T_{t} ）=C(T_{t} )+\alpha\vert T_{t} \vert ,可知，

當(dāng)\alpha 等于0或者充分小時(shí)，C_{\alpha }（T_{t} ）< C_{\alpha }（t ）,

\alpha 增大，到某一值時(shí)，有，C_{\alpha }（T_{t} ）= C_{\alpha }（t ），

\alpha 繼續(xù)增大，有C_{\alpha }（T_{t} ）> C_{\alpha }（t ）。

即當(dāng)\alpha =\frac{C_{\alpha }（t ）-C_{\alpha }（T_{t} ）}{\vert T_{t} \vert-1 } 時(shí)，T_{t} 與t有相同的損失函數(shù)，而t比T_{t} 的結(jié)點(diǎn)少，所以可以剪枝。

因此我們?nèi)绻业揭恍┻@樣的\alpha 值，就可以剪枝了。

所以具體的步驟是：對(duì)T_{0} 的每一個(gè)內(nèi)部節(jié)點(diǎn)t，計(jì)算g(t) =\frac{C_{\alpha }（t ）-C_{\alpha }（T_{t} ）}{\vert T_{t} \vert-1 } ,先減去g(t)最小的T_{t} （從小到大一點(diǎn)一點(diǎn)剪），得到子樹T_{1} ，這個(gè)g(t)設(shè)為\alpha _{1} 。依次減去所有g(shù)(t)的T_{t} ，得到一個(gè)子樹序列\left\{ T_{0}，T_{1}，...，T_{n} \right\} 。

選擇最優(yōu)子樹：

使用驗(yàn)證集，計(jì)算子樹序列中各棵子樹的平方誤差或基尼指數(shù)，最小的子樹為最優(yōu)子樹，對(duì)應(yīng)的\alpha 也確定了。

本章完。

一點(diǎn)補(bǔ)充：

書中說，決策樹學(xué)習(xí)的損失函數(shù)通常是正則化的極大似然函數(shù)。不是很理解，看到有大佬推導(dǎo)出，經(jīng)驗(yàn)誤差函數(shù)（也就是損失函數(shù)的第一項(xiàng)）是通過對(duì)數(shù)極大似然函數(shù)取反得到的。在概率模型中，二者是相同的概念（只有符號(hào)不一樣）。其意義作者個(gè)人理解為：先對(duì)各葉節(jié)點(diǎn)之間進(jìn)行極大似然估計(jì)，再對(duì)各葉節(jié)點(diǎn)內(nèi)部進(jìn)行極大似然估計(jì)，由此得到?jīng)Q策樹模型中的極大似然函數(shù)。

媽耶，最后一句沒看懂，還要去補(bǔ)一補(bǔ)極大似然估計(jì)的概念……

大佬鏈接在這里https://blog.csdn.net/wzk1996/article/details/81941572

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

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