背景
決策樹(shù)??是一種基本的分類(lèi)和回歸的方法【以前總是下意識(shí)以為決策樹(shù)只能用于分類(lèi)谅阿，事實(shí)上還可以用于回歸】抗愁。在分類(lèi)問(wèn)題中闸餐，決策樹(shù)基于特征對(duì)實(shí)例進(jìn)行分類(lèi)茬高，這個(gè)分類(lèi)過(guò)程可以認(rèn)為是if-then的規(guī)則集合，也可以認(rèn)為是特征空間與類(lèi)空間上的條件概率分布吧凉。
NOTE:
if—then規(guī)則集合具有一個(gè)重要的特征：互斥且完備隧出，即每個(gè)實(shí)例都被一條路徑或者一條規(guī)則所覆蓋，而且只能被一條路徑或一條規(guī)則所覆蓋
優(yōu)點(diǎn)：簡(jiǎn)單易理解客燕、分類(lèi)速度快
過(guò)程：利用損失函數(shù)最小化原則對(duì)訓(xùn)練集進(jìn)行建模鸳劳，再利用建立好的模型進(jìn)行分類(lèi)。決策樹(shù)的學(xué)習(xí)算法通常是遞歸地選擇最優(yōu)特征也搓，并根據(jù)特征對(duì)訓(xùn)練集進(jìn)行分割赏廓，最終形成從【根結(jié)點(diǎn)->葉子結(jié)點(diǎn)】的樹(shù)模型，但是這樣生成的樹(shù)可以容易發(fā)生過(guò)擬合傍妒，所以需要自底向上修剪?
決策樹(shù)學(xué)習(xí)包括三個(gè)步驟：特征選擇幔摸、決策樹(shù)生成、決策樹(shù)修剪
1.當(dāng)特征數(shù)量較多時(shí)颤练，在學(xué)習(xí)之前先進(jìn)行特征選擇
2.決策樹(shù)生成對(duì)應(yīng)局部最優(yōu)
3.決策樹(shù)修剪對(duì)應(yīng)全局最優(yōu)
目標(biāo)：選擇一個(gè)與訓(xùn)練數(shù)據(jù)矛盾較小的決策樹(shù)既忆，同時(shí)具有很好的泛化能力。
特征選擇
通常嗦玖，特征選擇的準(zhǔn)則是信息增益或者信息增益比
先介紹基本概念：
熵
熵用來(lái)表示隨機(jī)變量不確定的程度患雇，熵越大，不確定程度越大宇挫。
設(shè)是一個(gè)取有限值的隨機(jī)變量苛吱，概率分布為
那么熵定義為：
NOTE:
熵只依賴(lài)翠储。
條件熵
條件熵表示在已知隨機(jī)變量
的不確定性。
定義為：經(jīng)驗(yàn)熵和經(jīng)驗(yàn)條件熵
當(dāng)熵和條件熵中的概率是由數(shù)據(jù)估計(jì)而得到的橡疼，所對(duì)應(yīng)的熵和條件熵被稱(chēng)為經(jīng)驗(yàn)熵和經(jīng)驗(yàn)條件熵信息增益
特征對(duì)訓(xùn)練集
的信息增益
,定義為集合
特征選擇過(guò)程：對(duì)訓(xùn)練集計(jì)算每個(gè)特征的信息增益，并比較信息增益的大小欣除，選擇信息增益最大是特征住拭。
算法：
INPUT:訓(xùn)練數(shù)據(jù)集
OUTPUT:特征
計(jì)算數(shù)據(jù)集
計(jì)算特征：**
計(jì)算信息增益**
信息增益比
由于以信息增益進(jìn)行選擇，那么會(huì)趨于選擇取值較多的特征历帚，所以提出使用信息增益比废酷。
信息增益比定義為：其信息增益,即
其中，
是特征值
決策樹(shù)生成
ID3算法
核心：在決策樹(shù)各個(gè)結(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則選擇特征澈蟆，然后遞歸地構(gòu)建決策樹(shù)。
過(guò)程：從根結(jié)點(diǎn)開(kāi)始卓研，對(duì)結(jié)點(diǎn)計(jì)算所有可能的特征的信息增益趴俘，選擇信息增益最大的特征作為結(jié)點(diǎn)的特征睹簇，由該特征的不同取值建立子結(jié)點(diǎn)，再對(duì)子結(jié)點(diǎn)遞歸地調(diào)用以上方法寥闪，構(gòu)建決策樹(shù)太惠，直到所有的特征信息增益均很小或者沒(méi)有特征可以選擇為止。
ID3相當(dāng)于用極大似然法進(jìn)行概率模型的選擇
NOTE:
由于ID3算法只有樹(shù)的生成疲憋，所以生成的樹(shù)模型容易產(chǎn)生過(guò)擬合現(xiàn)象凿渊。C4.5算法
過(guò)程與ID3相似，只是對(duì)ID3進(jìn)行了改進(jìn)缚柳，使用信息增益比來(lái)選擇特征埃脏。
決策樹(shù)剪枝
決策樹(shù)的生成過(guò)程僅考慮到對(duì)訓(xùn)練數(shù)據(jù)集分類(lèi)的準(zhǔn)確性，這樣生成的樹(shù)模型容易出現(xiàn)過(guò)擬合且構(gòu)建的樹(shù)過(guò)于復(fù)雜秋忙，所以有必要對(duì)其進(jìn)行剪枝彩掐。
剪枝：從已生成的樹(shù)上裁掉一些子樹(shù)或者葉結(jié)點(diǎn)，并將其根結(jié)點(diǎn)或者父結(jié)點(diǎn)作為新的葉結(jié)點(diǎn)灰追，從而簡(jiǎn)化分類(lèi)樹(shù)模型堵幽。剪枝往往是通過(guò)極小化決策樹(shù)的整體損失函數(shù)來(lái)實(shí)現(xiàn)的
定義損失函數(shù)：
設(shè)樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)為
,
是樹(shù)的葉結(jié)點(diǎn)，該葉結(jié)點(diǎn)有
個(gè)樣本點(diǎn)弹澎，其中
類(lèi)的樣本點(diǎn)有
朴下，其中
是葉子結(jié)點(diǎn)
的經(jīng)驗(yàn)熵，
為參數(shù)苦蒿，決策樹(shù)學(xué)習(xí)的損失函數(shù)為：
其中
所以最終的損失函數(shù)表示為：
公式解釋?zhuān)?img class="math-inline" src="https://math.jianshu.com/math?formula=-%5Csum_%7Bt%3D1%7D%5E%7B%7CT%7C%7D%5Csum_%7Bk%3D1%7D%5E%7BK%7DN_%7Btk%7Dlog%5Cfrac%7BN_%7Btk%7D%7D%7BN_t%7D" alt="-\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}" mathimg="1">是表示模型對(duì)訓(xùn)練集的預(yù)測(cè)誤差殴胧，即模型與訓(xùn)練集的擬合程度，表示模型的復(fù)雜度刽肠，葉子節(jié)點(diǎn)數(shù)越大模型越復(fù)雜，
是調(diào)節(jié)參數(shù)免胃，控制模型的擬合和復(fù)雜程度音五。
當(dāng)確定時(shí)，選擇損失函數(shù)最小的模型羔沙，這里定義的損失函數(shù)其實(shí)等價(jià)于正則化的極大似然估計(jì)躺涝。
算法：
INPUT: 生成算法產(chǎn)生的整個(gè)樹(shù)，參數(shù)
OUPUT: 修剪后的子樹(shù)
1.計(jì)算每個(gè)結(jié)點(diǎn)的經(jīng)驗(yàn)熵
2.遞歸地從樹(shù)的葉結(jié)點(diǎn)向上回縮
回縮前后整體樹(shù)的損失函數(shù)比較扼雏，如果回縮前的損失函數(shù)大于回縮后坚嗜，進(jìn)行剪枝。
3.重復(fù)2诗充，直到不能繼續(xù)為止苍蔬，得到損失函數(shù)最小的子樹(shù)
python 代碼實(shí)現(xiàn)
后期加入
總結(jié)：決策樹(shù)是一種簡(jiǎn)單快速的分類(lèi)算法，本文不僅把熵相關(guān)的概念給整理了一遍蝴蜓，文中信息增益和信息增益比也可以用于其他模型的特征選擇碟绑，而最后剪枝部分提到的決策樹(shù)的損失函數(shù)是我之前在專(zhuān)門(mén)寫(xiě)的《詳述機(jī)器學(xué)習(xí)中的損失函數(shù)》博客中沒(méi)有提到的俺猿，這里也是一個(gè)補(bǔ)充。
