決策樹(shù)實(shí)際上是特征選擇，決策樹(shù)的生成和剪枝過(guò)程

5.1決策樹(shù)模型與學(xué)習(xí)

5.1.1 決策樹(shù)模型

決策樹(shù)模型定義分類(lèi)鞠策書(shū)模型是一種描述對(duì)實(shí)例進(jìn)行分類(lèi)的樹(shù)形結(jié)構(gòu)，決策樹(shù)由節(jié)點(diǎn)和有向邊組成，節(jié)點(diǎn)有兩種類(lèi)型：內(nèi)部節(jié)點(diǎn)和葉節(jié)點(diǎn)。內(nèi)部節(jié)點(diǎn)標(biāo)識(shí)一個(gè)特征或?qū)傩?，葉節(jié)點(diǎn)標(biāo)識(shí)一個(gè)類(lèi)。

5.2特征選擇

選取對(duì)訓(xùn)練數(shù)據(jù)有分類(lèi)能力的特征，從而提高決策樹(shù)的學(xué)習(xí)效率。
如果利用一個(gè)特征進(jìn)行分類(lèi)的結(jié)果和隨機(jī)分類(lèi)結(jié)果沒(méi)有很大差別，則這個(gè)特征沒(méi)有分類(lèi)能力。
特征選擇的準(zhǔn)則是信息增益或信息增益比

1.1信息增益

熵（entropy）是標(biāo)識(shí)隨機(jī)變量不確定性的度量。設(shè)X是一個(gè)取有限個(gè)值的隨機(jī)離散變量，概率分布為：

              P(X = xi) = pi i=1,2,...n

隨機(jī)變量X的熵為：

              H(X) = -∑pi*logpi

• 當(dāng)對(duì)數(shù)以2為底或者e為底，這是熵的單位分別稱(chēng)作比特(bit)和納特(nat)

由定義可知，熵和X的分布有關(guān)，和X的取值無(wú)關(guān)，所以也可以將X的熵記作H(p)，即

              H(p) = -∑pi*logpi

熵越大，隨機(jī)變量的不確定性就越大，從定義可驗(yàn)證

              0 <= H(p) <= logn

條件熵H(Y|X)表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性，隨機(jī)變量X給定的條件下隨機(jī)變量Y的條件熵(conditional entropy) H(Y|X)，定義為X給定條件下Y的條件概率分布的熵對(duì)X的數(shù)學(xué)期望

              H (Y|X) = ∑pi*H(Y|X = xi)
              這里，pi = P(X = xi), i = 1, 2, ...n

當(dāng)條件熵中的概率有數(shù)據(jù)估計(jì)（特別是最大似然估計(jì)）得到時(shí)，所對(duì)應(yīng)的熵與條件熵分別稱(chēng)為經(jīng)驗(yàn)熵（empirical entropy） 和經(jīng)驗(yàn)條件熵（empirical conditional entropy）.此時(shí)，如果有0概率，令0log0=0.

信息增益（information gain）表示得知特征X的信息而使得類(lèi)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)，定義為集合D的經(jīng)驗(yàn)熵H(D)與特征A給定條件下D的經(jīng)驗(yàn)條件熵H(D|A)之差，即

          g(D,A) = H(D) - H(D|A)

一般的，熵H(Y)與條件熵H(Y|X)之差稱(chēng)為互信息（mutual information），決策樹(shù)學(xué)習(xí)中的信息增益等價(jià)于訓(xùn)練數(shù)據(jù)集中類(lèi)與特征的互信息。

信息增益的算法
輸入：訓(xùn)練數(shù)據(jù)集D和特征
輸出：特征A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益g（D，A）

• （1）計(jì)算數(shù)據(jù)集D的經(jīng)驗(yàn)熵H(D)

          H(D) = ∑pi*logpi
          H(D) = ∑|Ck|/|D|*log|Ck|/|D|
  

• （2）計(jì)算特征A對(duì)數(shù)據(jù)集D的經(jīng)驗(yàn)條件熵H(D,A)

          H(D|A) = ∑|Di|/|D|*H(D)
  

• （3）計(jì)算信息增益

          g(D,A) = H(D) - H(D|A)
  

根據(jù)信息增益選擇最優(yōu)的特征

• （1）首先計(jì)算經(jīng)驗(yàn)熵H(D)

              H(D) = -∑pi*logpi
  

• （2）計(jì)算各特征對(duì)數(shù)據(jù)集D的信息增益

          g(D,A) = H(D) - H(D|A)
  

信息增益比

信息增益值的大小是相對(duì)于訓(xùn)練數(shù)據(jù)集而言的，并沒(méi)有絕對(duì)意義，在分類(lèi)問(wèn)題困難時(shí)，也就是說(shuō)在訓(xùn)練數(shù)據(jù)集的經(jīng)驗(yàn)熵大的時(shí)候，信息增益值會(huì)偏大，反之信息增益值會(huì)偏小，使用信息增益比（information gain ratio）可以對(duì)這一問(wèn)題進(jìn)行校正，這是特征選擇的另一個(gè)準(zhǔn)則。

信息增益比定義特征A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益比gr(D,A)定義為其信息增益g(D，A)與訓(xùn)練數(shù)據(jù)集D的經(jīng)驗(yàn)熵H(D)之比：
gr(D,A) = g(D，A) / H(D)

5.3決策樹(shù)的生成

5.3.1 ID3算法

ID3算法的核心是在鞠策書(shū)各個(gè)節(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則選擇特征，遞歸的構(gòu)建決策樹(shù)，具體方法是：從根節(jié)點(diǎn)開(kāi)始，對(duì)節(jié)點(diǎn)計(jì)算所有可能得特征的信息增益，選擇信息增益最大的特征作為節(jié)點(diǎn)的特征，由該特征的不同取值建立子節(jié)點(diǎn)；再對(duì)自己點(diǎn)遞歸的調(diào)用以上方法，構(gòu)建決策樹(shù)；直到所有的特征的信息增益均很小或沒(méi)有特征可以選擇位置。最后得到一個(gè)決策樹(shù)。ID3相當(dāng)于用極大似然法進(jìn)行概率模型的選擇

ID3算法
輸入：訓(xùn)練數(shù)據(jù)集D，特征集A，閾值e；
輸出：決策樹(shù)T

• （1）若D中所有實(shí)例屬于同一類(lèi)Ck，則T為單節(jié)點(diǎn)數(shù)，并將Ck作為該節(jié)點(diǎn)的類(lèi)標(biāo)記，返回T
• （2）若A=?，則T為單節(jié)點(diǎn)樹(shù)，并將D中實(shí)例數(shù)最大的類(lèi)Ck作為該節(jié)點(diǎn)的類(lèi)標(biāo)記，返回T
• （3）否則，按算法5.1計(jì)算A中各特征對(duì)D的信息增益，選擇信息增益最大得到特征Ag；
• （4）如果Ag的信息增益小于閾值e，則置T為單節(jié)點(diǎn)樹(shù)，并將D中實(shí)力書(shū)最大的類(lèi)Ck作為該節(jié)點(diǎn)的類(lèi)標(biāo)記，返回T；
• （5）否則，對(duì)Ag的每一可能值a1，依Ag = ai 將D分割為若干非空子集Di，將Di中實(shí)例數(shù)最大的類(lèi)作為標(biāo)記，構(gòu)建子節(jié)點(diǎn)，由節(jié)點(diǎn)及其子節(jié)點(diǎn)構(gòu)成樹(shù)T，返回T；
• （6）對(duì)第i個(gè)子節(jié)點(diǎn)，以Di為訓(xùn)練集，以A-{Ag}為特征集，遞歸的調(diào)用步驟（1）-（5），得到子樹(shù)Ti，返回Ti

C4.5的生成算法

C4.5與ID3算法相似，C4.5在生成過(guò)程中，用信息增益比來(lái)選擇特征。可以平衡經(jīng)驗(yàn)熵偏大或者偏小導(dǎo)致信息增益偏大偏小的問(wèn)題。

5.4 決策樹(shù)的剪枝

決策樹(shù)生成算法遞歸的產(chǎn)生決策樹(shù)，直到不能繼續(xù)下去為止，這樣產(chǎn)生的樹(shù)往往對(duì)訓(xùn)練數(shù)據(jù)的分類(lèi)很準(zhǔn)確，但對(duì)于未知的測(cè)試數(shù)據(jù)的分類(lèi)確沒(méi)有那么準(zhǔn)確，即出現(xiàn)過(guò)擬合現(xiàn)象。過(guò)擬合的原因在于學(xué)習(xí)時(shí)過(guò)多的考慮如何提高對(duì)訓(xùn)練數(shù)據(jù)的正確分類(lèi)，從而構(gòu)建出過(guò)于復(fù)雜的決策樹(shù)。解決這個(gè)問(wèn)題的辦法是考慮決策樹(shù)的復(fù)雜度，對(duì)已生成的決策樹(shù)進(jìn)行簡(jiǎn)化。

在決策樹(shù)學(xué)習(xí)中將已生成的樹(shù)進(jìn)行簡(jiǎn)化的過(guò)程稱(chēng)為剪枝（pruning）。

降低模型復(fù)雜度，從而提升模型在未知數(shù)據(jù)上的預(yù)測(cè)準(zhǔn)確率

5.4.1決策樹(shù)的剪枝算法

決策樹(shù)的剪枝往往通過(guò)極小化決策樹(shù)整體的損失函數(shù)（loss function）或代價(jià)函數(shù)（cost function）來(lái)實(shí)現(xiàn)，設(shè)樹(shù)T的葉節(jié)點(diǎn)個(gè)數(shù)為|T|，t是樹(shù)T的葉節(jié)點(diǎn)，該葉節(jié)點(diǎn)有Ni個(gè)樣本點(diǎn)，其中k類(lèi)的樣本點(diǎn)有Ntk個(gè)，k=1,2....，K，H(T)為葉節(jié)點(diǎn)t上的經(jīng)驗(yàn)熵，a>=0為參數(shù)，決策樹(shù)的損失函數(shù)為

          Ca(T) = ∑NtHt(T) + a|T|

其中經(jīng)驗(yàn)熵為

          Ht(T) = -∑Ntk/Nt * logNtk/Nt

損失函數(shù)

          Ca(T) = C(T) + a|T|

C(T)表示模型對(duì)訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差，即模型與訓(xùn)練數(shù)據(jù)的擬合程度，|T|表示模型的復(fù)雜度，參數(shù)a>=0控制兩者之間的影響，較大的a促使選擇較簡(jiǎn)單的模型（樹(shù)），較小的a促使選擇較復(fù)雜的模型，a=0意味著只考慮模型與訓(xùn)練數(shù)據(jù)的擬合程度，不考慮模型復(fù)雜度。損失函數(shù)正好表示了對(duì)兩者的平衡。

決策樹(shù)生成只考慮了通過(guò)提高信息增益對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行更好的擬合，而決策樹(shù)剪枝通過(guò)優(yōu)化損失函數(shù)還考慮了減小模型復(fù)雜度，決策樹(shù)生成學(xué)習(xí)局部的模型，而決策樹(shù)剪枝學(xué)習(xí)整體的模型。

5.5 CART算法

CART算法有兩個(gè)組成：

• 決策樹(shù)生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹(shù)，生成的決策樹(shù)要盡量大；
• 決策樹(shù)剪枝：用驗(yàn)證數(shù)據(jù)集對(duì)已生成的樹(shù)進(jìn)行剪枝并選擇最優(yōu)子樹(shù)，這時(shí)用損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。