這里開始機(jī)器學(xué)習(xí)的筆記記錄。今天的這篇是一個(gè)分類方法--決策樹。

決策樹
優(yōu)點(diǎn)：計(jì)算復(fù)雜度不高，輸出結(jié)果易于理解，對(duì)中間值的缺失不敏感，可以處理不相關(guān)特征數(shù)據(jù)。
缺點(diǎn)：可能會(huì)產(chǎn)生過擬合的問題。
適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型

本文內(nèi)容大部分來自于《統(tǒng)計(jì)學(xué)習(xí)方法》。

先來看看決策樹是什么？

決策樹模型就是個(gè)樹形結(jié)構(gòu)。由結(jié)點(diǎn)（node）和有向邊（directed edge）組成。結(jié)點(diǎn)分內(nèi)部結(jié)點(diǎn)和葉結(jié)點(diǎn)。內(nèi)部結(jié)點(diǎn)是一個(gè)特征，葉結(jié)點(diǎn)是類別。如圖5-1：

決策樹模型

決策樹可以看做一個(gè)if-then規(guī)則的集合，即如上圖的由根結(jié)點(diǎn)到葉結(jié)點(diǎn)的每一條路徑構(gòu)建一條規(guī)則，特征對(duì)應(yīng)規(guī)則的條件，葉結(jié)點(diǎn)就是結(jié)論。每個(gè)實(shí)例都被一條路徑或規(guī)則所覆蓋，而且只被一條路徑或規(guī)則覆蓋。即實(shí)例的特征與那條路徑上的特征表現(xiàn)一致。

決策樹葉可以看成給定特征條件下類的條件概率分布。將特征空間進(jìn)行劃分成很多個(gè)單元，每個(gè)單元定義一個(gè)類的概率分布。

決策樹的本質(zhì)上是從訓(xùn)練樣本中歸納出一組分類規(guī)則，也是估計(jì)條件概率模型。（所以說是判別模型）

先看書上的一道例題：

在用決策樹做分類的過程中，我們需要一步一步的選取特征來劃分?？墒?，比如說在例題當(dāng)中，有4個(gè)特征，選擇任意一個(gè)都能進(jìn)行決策樹的劃分，比如年齡和是否有工作兩個(gè)特征，分別選取都可以讓決策樹進(jìn)行下去：

特征選擇不同，分支不同

那么我們首先選擇哪個(gè)特征來進(jìn)行劃分呢？

當(dāng)然是該選擇一個(gè)好的特征。怎樣才算好呢？直觀上，如果一個(gè)特征具有更好的分類能力（能將訓(xùn)練集分割成子類，使得各個(gè)子類在當(dāng)前條件下有更好的分類），那么這個(gè)特征就可以當(dāng)做好特征。

那么如何評(píng)判某特征是個(gè)好特征呢？

書上給出的是一種叫信息增益和基尼系數(shù)的指標(biāo)。下面就分別來看看。

1.信息增益

什么是信息增益呢？這與信息論中的熵和條件熵有關(guān)。也就是通過信息論的一套來劃分?jǐn)?shù)據(jù)集。

首先一個(gè)概念：信息熵是表示隨機(jī)變不確定性的度量。熵越大，信息量越大，也就是越不確定。

熵的定義如下：

熵的定義

p(x)表示的是概率分布，對(duì)數(shù)可以以2或者e為底都可以，這時(shí)只是熵的單位不同，并沒有什么區(qū)別。（以2為底叫比特，以e為底叫納特）

不過熵為什么要這樣定義呢？
可以試著解釋下，先看看“越不確定”是什么意思？可以看成發(fā)生的概率越小。因此事件發(fā)生的概率越小，信息量就越大。比如說本來認(rèn)為不可能的事發(fā)生了，給人的信息量就很大。

如果兩個(gè)事件是獨(dú)立的，則

如果在這里設(shè)置表示兩個(gè)事件信息量的函數(shù)為h(x1)和h(x2),那么二者同時(shí)發(fā)生的信息量可以這樣表示:

(因?yàn)橛眉臃ǜ庇^方便)

如何把概率和信息量聯(lián)系起來呢？看公式的話，可以看到乘法取個(gè)對(duì)數(shù)就能變成加法，因此我們可以假定h(x)=log(p(x))，但p(x)是小于1的，這樣取出來是負(fù)數(shù)，為了讓它是正數(shù)形式上好看些，那就取個(gè)負(fù)吧。這樣，信息量的表示就成了：

單個(gè)事件的信息量就這樣表示了出來。。而熵呢？熵就是所有信息量相加了:

為什么要乘以概率，因?yàn)殪貞?yīng)該表示總事件的信息期望（平均），因此要乘以單獨(dú)事件發(fā)生的概率。

那么條件熵又是什么呢？
條件熵是表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性。

而信息增益就是在集合D的經(jīng)驗(yàn)熵H(D)與特征A給定條件下D的經(jīng)驗(yàn)條件熵之差：

在決策樹中，經(jīng)驗(yàn)熵H(D)表示對(duì)數(shù)據(jù)集D進(jìn)行分類的不確定性；而H(D|A)表示在特征A給定的條件下對(duì)數(shù)據(jù)集D進(jìn)行分類的不確定性；它們的差就表示由于特征A而使對(duì)數(shù)據(jù)集D的分類的不確定性減少的程度，即信息增益。（就是劃分?jǐn)?shù)據(jù)之前之后信息熵發(fā)生的變化叫信息增益。）

如此定義后，我們就認(rèn)為信息增益大的那個(gè)特征是好特征了。信息增益大的那個(gè)特征就是在劃分?jǐn)?shù)據(jù)時(shí)起決定性作用的那個(gè)特征。

那么如何計(jì)算信息增益？在書上給了公式（簡(jiǎn)書不支持Latex，公式真的挺難弄，只能截圖了）:

看到信息增益的公式，其實(shí)信息增益就是互信息。

另外，在信息增益的基礎(chǔ)上，還可以使用信息增益比來表示特征選擇的準(zhǔn)則。

信息增益比

2.基尼系數(shù)

前面說了除信息增益外，還可以用基尼系數(shù)來表示特征選擇的準(zhǔn)則。

那基尼系數(shù)又表示的是什么呢？

基尼系數(shù)同樣可以表示樣本集合的不確定性。

在分類問題中，假設(shè)有K個(gè)類，樣本點(diǎn)屬于第k類的概率是P_k，則概率分布的基尼系數(shù)定義為:

基尼指數(shù)

從公式看就是被分對(duì)的概率乘以被分錯(cuò)的概率，然后整個(gè)的和就是基尼系數(shù)。

其實(shí)和熵比起來似乎就是定義概念不一樣，公式感覺是差不多的啊:

熵

都是概率乘以一個(gè)東西，然后求和。也就是求期望?；嵯禂?shù)也就是把log(p)改為了1-p。熵前面加個(gè)負(fù)號(hào)只是為了讓值成為正數(shù)而已。

如果是二分類的話(概率p₁=(1-p₂))，那么基尼系數(shù)化簡(jiǎn)就是：

二分類基尼系數(shù)公式

在特征A的條件下，集合D的基尼系數(shù)表示法也和條件熵的表示法蠻像的，也就是條件基尼系數(shù)。如果都以二分類來做對(duì)比的話，公式分別如下：

看上去形式簡(jiǎn)直就是一模一樣啊。這里書上介紹基尼指數(shù)值越大，就表示不確定性越大，所以應(yīng)選擇基尼系數(shù)最小的特征及對(duì)應(yīng)切分點(diǎn)作為最優(yōu)特征。

那么為什么基尼系數(shù)和熵一樣能夠表示不確定性呢？《統(tǒng)計(jì)學(xué)習(xí)方法》書上有這樣一幅圖：

基尼系數(shù)和熵之半(也就是熵的一半值)的曲線比較近似。

曾經(jīng)看到過一個(gè)解釋，熵的公式中有一個(gè)log對(duì)數(shù)，而f(x)=-lnx在x=1處一階泰勒展開，忽略掉高次項(xiàng)，可以得到f(x)≈1-x。這樣p_klogp_k≈p_k(1-p_k)了，就更可以看到基尼指數(shù)與熵很近似了。

決策樹的生成

算好了信息增益后，就可以進(jìn)行決策樹的生成了。通過應(yīng)用信息增益準(zhǔn)則來選取特征的這一種方法而進(jìn)行決策樹的構(gòu)建叫ID3算法。

ID3算法的核心是在決策樹各個(gè)結(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則來選擇特征，遞歸的構(gòu)建決策樹。

具體方法如下:

從根結(jié)點(diǎn)開始，對(duì)結(jié)點(diǎn)計(jì)算所有可能的特征的信息增益，選擇信息增益最大的特征作為結(jié)點(diǎn)的特征，由該特征的不同取值來建立子結(jié)點(diǎn)；再對(duì)子結(jié)點(diǎn)遞歸的調(diào)用以上方法，構(gòu)建決策樹；直到所有特征的信息增益均很小或沒有特征可以選擇為止。

ID3算法步驟：

另外，還可以用信息增益比的形式來選擇特征，這樣的算法叫做C4.5算法。

C4.5算法的步驟：

最后還有一種是通過樣本集合D的基尼系數(shù)來進(jìn)行特征選取，而依據(jù)這樣一種準(zhǔn)則的樹生成算法叫CART算法。

CART全稱叫分類與回歸樹（classification and regression tree），因此可以看到?jīng)Q策樹不僅可以做分類，還可以用于回歸呢。

CART假設(shè)決策樹是二叉樹，左邊的分支取值為“是”，右邊的分支取值為“否”。

CART生成算法步驟：

決策樹的剪枝

決策樹容易產(chǎn)生過擬合現(xiàn)象，這樣的話雖然對(duì)已知的訓(xùn)練數(shù)據(jù)分類很準(zhǔn)確，但對(duì)于未知的測(cè)試數(shù)據(jù)就沒那么準(zhǔn)確了。過擬合的原因是在學(xué)習(xí)時(shí)過多的考慮如何提高對(duì)訓(xùn)練樣本的正確分類，從而構(gòu)建了過于復(fù)雜的決策樹。因此，為了解決過擬合現(xiàn)象，可以對(duì)已生成的決策樹進(jìn)行簡(jiǎn)化，這就是剪枝。

上面所介紹的三種決策樹的剪枝過程是相同的，不同的僅僅是對(duì)于當(dāng)前樹所用的評(píng)價(jià)標(biāo)準(zhǔn)不同，也就是上面說過的信息增益、信息增益比或基尼系數(shù)。

剪枝的總體思路如下：

由完全樹T₀開始，剪枝部分結(jié)點(diǎn)得到T₁，再次剪枝部分結(jié)點(diǎn)得到T₂，直到剪枝到僅剩下樹根的那棵樹T_k。當(dāng)然這些樹都要保留{T₁,T₂,....,T_k}；

接著通過交叉驗(yàn)證法在驗(yàn)證數(shù)據(jù)集上對(duì)這k棵樹分別進(jìn)行測(cè)試評(píng)價(jià)，選擇損失函數(shù)最小的數(shù)T_α作為最優(yōu)子樹。

那么來看看決策樹的損失函數(shù)定義：

其中|T|為樹T的葉節(jié)點(diǎn)個(gè)數(shù)，t是數(shù)T的葉節(jié)點(diǎn)，該葉節(jié)點(diǎn)上有N_t個(gè)樣本，其中k類的樣本有N_tk個(gè)。H_t(T)就是葉節(jié)點(diǎn)t上的經(jīng)驗(yàn)熵：

將公式簡(jiǎn)化一下表示：

其中：

這樣，C(T)就表示模型對(duì)訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差，|T|就表示模型復(fù)雜度，也就是說葉結(jié)點(diǎn)越多，決策樹越復(fù)雜，損失就越大。α就是那個(gè)控制值了，其實(shí)后面就相當(dāng)于正則化的存在。當(dāng)α=0時(shí)，未剪枝的決策樹損失最小；當(dāng)α=+∞時(shí)，單根結(jié)點(diǎn)的決策樹損失最小。α越小，選擇的樹越復(fù)雜。因此，才說模型選擇就是用正則化的極大似然估計(jì)。