決策樹(shù)模型時(shí)一種描述對(duì)實(shí)例進(jìn)行分類的樹(shù)形結(jié)構(gòu)垢乙。決策樹(shù)可以分成ID3查近、C4.5和CART眉踱。
1、基于信息增益（用于ID3和ID4.5）
只能用于離散的特征集霜威，用做分類谈喳。
熵 （注：熵越大，隨機(jī)變量的不確定性越大）
條件熵
信息熵增益 （特征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)之差)
信息增益比: （特征A的信息增益g(D,A)與訓(xùn)練數(shù)據(jù)集D關(guān)于特征A的值的熵
之比）
基于信息增益算法的算法
當(dāng)前數(shù)據(jù)的熵婿禽，D表示數(shù)據(jù)總數(shù)赏僧，表示數(shù)據(jù)集的k分類：
對(duì)于特征A的條件熵是：
（其中
表示特征A中的特征取值i，
表示特征取值i下的分類情況）
于是特征A的信息增益比是：
（1）ID3算法
選擇信息增益最大的特征作為結(jié)點(diǎn)的特征扭倾。
（2）ID4.5算法
選擇信息增益比最大特征作為結(jié)點(diǎn)的特征淀零。
決策樹(shù)剪枝
剪枝類型：預(yù)剪枝、后剪枝
?預(yù)剪枝：在構(gòu)造決策樹(shù)的同時(shí)進(jìn)行剪枝膛壹。所有決策樹(shù)的構(gòu)建方法驾中，都是在無(wú)法進(jìn)一步降低熵的情況下才會(huì)停止創(chuàng)建分支的過(guò)程，為了避免過(guò)擬合模聋，可以設(shè)定一個(gè)閾值肩民，熵減小的數(shù)量小于這個(gè)閾值，即使還可以繼續(xù)降低熵链方，也停止繼續(xù)創(chuàng)建分支持痰。但是這種方法實(shí)際中的效果并不好。
?后剪枝：是在決策樹(shù)生長(zhǎng)完成之后侄柔，對(duì)樹(shù)進(jìn)行剪枝共啃，得到簡(jiǎn)化版的決策樹(shù)。剪枝的過(guò)程是對(duì)擁有同樣父節(jié)點(diǎn)的一組節(jié)點(diǎn)進(jìn)行檢查暂题，判斷如果將其合并移剪，熵的增加量是否小于某一閾值。如果確實(shí)小薪者，則這一組節(jié)點(diǎn)可以合并一個(gè)節(jié)點(diǎn)纵苛，其中包含了所有可能的結(jié)果。后剪枝是目前最普遍的做法言津。
?后剪枝的剪枝過(guò)程是刪除一些子樹(shù)攻人，然后用其葉子節(jié)點(diǎn)代替，這個(gè)葉子節(jié)點(diǎn)所標(biāo)識(shí)的類別通過(guò)大多數(shù)原則(majority class criterion)確定悬槽。所謂大多數(shù)原則怀吻，是指剪枝過(guò)程中, 將一些子樹(shù)刪除而用葉節(jié)點(diǎn)代替,這個(gè)葉節(jié)點(diǎn)所標(biāo)識(shí)的類別用這棵子樹(shù)中大多數(shù)訓(xùn)練樣本所屬的類別來(lái)標(biāo)識(shí),所標(biāo)識(shí)的類稱為majority class ，（majority class 在很多英文文獻(xiàn)中也多次出現(xiàn)）初婆。
2蓬坡、CART算法
用于回歸和分類。創(chuàng)建的是二叉決策樹(shù)磅叛。
1屑咳、回歸樹(shù)的生成
X與Y分別為輸入和輸出變量，并且Y為連續(xù)變量弊琴，給定數(shù)據(jù)集
(1).選擇最優(yōu)切分j與切分點(diǎn)S（j為特征兆龙，s為特征的且分點(diǎn)，即二叉樹(shù)的分類點(diǎn)）使得：
其中c1表示集合的平均值敲董，c2表示集合
的平均值紫皇，即：
(2).這樣就找到了一個(gè)最優(yōu)切分點(diǎn)慰安，然后調(diào)用步驟(1)
(3).最后生成決策樹(shù):
2、分類樹(shù)的生成
基尼系數(shù)：
二分類的基尼系數(shù)：
樣本集合D：
特征A條件下坝橡，集合D的基尼系數(shù)：
基尼指數(shù)越大泻帮，不確定性越大，選擇基尼系數(shù)最小的特征點(diǎn)计寇。
算法的過(guò)程和回歸樹(shù)的生成相似锣杂，也是遍歷特征和特征值的可能的二分點(diǎn)。
