5.1 決策樹模型與學(xué)習(xí)
5.1.1 決策樹模型
決策樹：結(jié)點(diǎn)（內(nèi)部結(jié)點(diǎn)和葉結(jié)點(diǎn)）和有向邊。內(nèi)部結(jié)點(diǎn)表示一個(gè)特征或?qū)傩?，葉節(jié)點(diǎn)表示一個(gè)類。
5.1.2? 決策樹與if-then規(guī)則
決策樹轉(zhuǎn)換成if-then規(guī)則的過(guò)程：由決策樹的根結(jié)點(diǎn)到葉結(jié)點(diǎn)的每一條路徑構(gòu)建一條規(guī)則；路徑上內(nèi)部結(jié)點(diǎn)的特征對(duì)應(yīng)著規(guī)則的條件，而葉節(jié)點(diǎn)的類對(duì)應(yīng)著規(guī)則的結(jié)論。
決策樹的路徑或其對(duì)應(yīng)的if-then規(guī)則集合具有一個(gè)重要的性質(zhì)：互斥且完備。
5.1.3 決策樹與條件概率分布
決策樹還表示給定特征條件下類的條件概率分布。這一條件概率分布定義在特征空間的一個(gè)劃分上。將特征空間劃分為互不相交的單元或區(qū)域，并在每個(gè)單元定義一個(gè)類的概率分布就構(gòu)成了一個(gè)條件概率分布。
5.1.4 決策樹學(xué)習(xí)
本質(zhì)：從訓(xùn)練數(shù)據(jù)集中歸納出一組分類規(guī)則
損失函數(shù)：正則化的極大似然函數(shù)
策略：以損失函數(shù)為目標(biāo)函數(shù)的最小化
決策樹學(xué)習(xí)算法：特征選擇、決策樹的生成和決策樹的剪枝。決策樹的生成對(duì)應(yīng)于模型的局部選擇，只考慮局部最優(yōu)；決策樹的剪枝對(duì)應(yīng)于模型的全局選擇，考慮全局最優(yōu)。
5.2 特征選擇
5.2.1 特征選擇問題
選取對(duì)訓(xùn)練數(shù)據(jù)具有分類能力的特征，通常的準(zhǔn)則是信息增益或信息增益比。
5.2.2 信息增益
熵：隨機(jī)變量不確定性
熵只依賴于X的分布，而與X的取值無(wú)關(guān)。熵越大，隨機(jī)變量的不確定性就越大。
設(shè)有隨機(jī)變量(X,Y)條件熵H(Y|X)表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性。定義為X給定條件下Y的條件概率分布的熵對(duì)X的數(shù)學(xué)期望
當(dāng)熵和條件熵中的概率由數(shù)據(jù)估計(jì)得到時(shí)，所對(duì)應(yīng)的熵與條件熵分別稱為經(jīng)驗(yàn)熵和經(jīng)驗(yàn)條件熵。
信息增益表示得知特征X的信息而使得類Y的信息不確定性減少的程度。
信息增益：特征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)之差，即
熵H(Y)與條件熵H(Y|X)之差稱為互信息。決策樹學(xué)習(xí)中的信息增益等價(jià)于訓(xùn)練數(shù)據(jù)集中類與特征的互信息。
根據(jù)信息增益準(zhǔn)則的特征選擇方法：對(duì)訓(xùn)練數(shù)據(jù)集D，計(jì)算其每個(gè)特征的信息增益，并比較它們的大小，選擇信息增益最大的特征。
信息增益算法：
輸入：訓(xùn)練數(shù)據(jù)集D和特征A
輸出：特征A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A)
5.2.3 信息增益比
以信息增益作為劃分訓(xùn)練數(shù)據(jù)集的特征，存在偏向于選擇取值較多的特征的問題。使用信息增益比可以矯正。
信息增益比：
5.3 決策樹的生成
5.3.1 ID3算法
核心：在決策樹各個(gè)結(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則選擇特征，遞歸的構(gòu)建決策樹。
ID3算法只有樹的生成，所以容易過(guò)擬合。
5.3.2 C4.5的生成算法
用信息增益比來(lái)選特征
5.4 決策樹的剪枝
過(guò)擬合原因：學(xué)習(xí)時(shí)過(guò)多的考慮如何提高對(duì)訓(xùn)練數(shù)據(jù)的正確分類，從而構(gòu)建出過(guò)于復(fù)雜的決策樹。
決策樹的剪枝往往通過(guò)極小化決策樹整體的損失函數(shù)或代價(jià)函數(shù)來(lái)實(shí)現(xiàn)。
C(T)表示模型對(duì)訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差，即模型與訓(xùn)練數(shù)據(jù)的擬合程度，|T|表示模型復(fù)雜度，α>=0控制兩者之間的影響。
剪枝，當(dāng)α確定時(shí)，選擇損失函數(shù)最小的模型，即損失函數(shù)最小的子樹。
5.5 CART算法
分類與回歸樹（classification and regression tree,CART）
算法：
? ? ①?zèng)Q策樹生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹，生成的決策樹要盡量大
? ? ②決策樹剪枝：用驗(yàn)證數(shù)據(jù)集對(duì)已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹，用損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。
5.5.1 CART生成
對(duì)回歸樹用平方誤差最小化準(zhǔn)則，對(duì)分類樹用基尼指數(shù)(Gini index)最小化準(zhǔn)則，進(jìn)行特征選擇，生成二叉樹
1. 回歸樹的生成
2. 分類樹的生成
5.5.2 CART剪枝
①?gòu)纳伤惴óa(chǎn)生的決策樹T0底端開始不斷剪枝，直到T0的根節(jié)點(diǎn)，形成一個(gè)子樹序列{T0,T1,...,Tn}
②通過(guò)交叉驗(yàn)證法在獨(dú)立的驗(yàn)證數(shù)據(jù)集上對(duì)子樹序列進(jìn)行測(cè)試，從中選擇最優(yōu)子樹
