決策樹問題
1）各種熵的計(jì)算
熵、聯(lián)合熵、條件熵土至、交叉熵、KL散度（相對(duì)熵）
熵用于衡量不確定性猾昆，所以均分的時(shí)候熵最大
熵的理解:熵其實(shí)定義了一個(gè)函數(shù)(概率分布函數(shù))到一個(gè)值(信息熵)的映射:P(x)->H(函數(shù)->值)
條件熵：在隨機(jī)變量X發(fā)生的前提下陶因，隨機(jī)變量Y發(fā)生所新帶來的熵定義為Y的條件熵，用H(Y|X)表示垂蜗，用來衡量在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性, 用H(X|Y)表示
KL散度用于度量兩個(gè)分布的不相似性坑赡，KL(p||q)等于交叉熵H(p,q)-熵H(p)。交叉熵可以看成是用q編碼P所需的bit數(shù)么抗，減去p本身需要的bit數(shù)，KL散度相當(dāng)于用q編碼p需要的額外bits亚铁。
交互信息Mutual information ：I(x,y) = H(x)-H(x|y) = H(y)-H(y|x) 表示觀察到x后蝇刀，y的熵會(huì)減少多少。
（2）常用的樹搭建方法：ID3徘溢、C4.5吞琐、CART
上述幾種樹分別利用信息增益捆探、信息增益率、Gini指數(shù)作為數(shù)據(jù)分割標(biāo)準(zhǔn)站粟。
其中信息增益衡量按照某個(gè)特征分割前后熵的減少程度黍图，其實(shí)就是上面說的交互信息。
用上述信息增益會(huì)出現(xiàn)優(yōu)先選擇具有較多屬性的特征奴烙，畢竟分的越細(xì)的屬性確定性越高助被。所以提出了信息增益率的概念，讓含有較多屬性的特征的作用降低切诀。
CART樹在分類過程中使用的基尼指數(shù)Gini揩环，只能用于切分二叉樹，而且和ID3幅虑、C4.5樹不同丰滑，Cart樹不會(huì)在每一個(gè)步驟刪除所用特征。
（3）防止過擬合：剪枝
剪枝分為前剪枝和后剪枝倒庵，前剪枝本質(zhì)就是早停止褒墨，后剪枝通常是通過衡量剪枝后損失函數(shù)變化來決定是否剪枝。后剪枝有：錯(cuò)誤率降低剪枝擎宝、悲觀剪枝郁妈、代價(jià)復(fù)雜度剪枝
（4）前剪枝的幾種停止條件
節(jié)點(diǎn)中樣本為同一類
特征不足返回多類
如果某個(gè)分支沒有值則返回父節(jié)點(diǎn)中的多類
樣本個(gè)數(shù)小于閾值返回多類
