AI有道
一個(gè)有情懷的公眾號(hào)
上文我們主要介紹了 。演算法通過(guò)調(diào)整每筆資料的權(quán)重，得到不同的，然后將不同的乘以不同的系數(shù)α進(jìn)行線性組合。這種演算法的優(yōu)點(diǎn)是，即使底層的演算法g不是特別好（只要比亂選好點(diǎn)），經(jīng)過(guò)多次迭代后算法模型會(huì)越來(lái)越好，起到了boost提升的效果。本節(jié)課將在此基礎(chǔ)上介紹一種新的算法：決策樹(shù)（ Tree）。
1
Tree
從第7節(jié)課開(kāi)始，我們就一直在介紹 model。的核心就是將許多可供選擇使用的比較好的融合起來(lái)，利用集體的智慧組合成G，使其得到更好的機(jī)器學(xué)習(xí)預(yù)測(cè)模型。下面，我們先來(lái)看看已經(jīng)介紹過(guò)的 type有哪些。
type有三種：，non-，。它有兩種情況，一種是所有的g是已知的，即。對(duì)應(yīng)的三種類型分別是/，和。另外一種情況是所有g(shù)未知，只能通過(guò)手上的資料重構(gòu)g，即。其中和non-分別對(duì)應(yīng)的是和算法，而對(duì)應(yīng)的就是我們本節(jié)課將要介紹的 Tree算法。
決策樹(shù)（ Tree）模型是一種傳統(tǒng)的算法，它的處理方式與人類思維十分相似。例如下面這個(gè)例子，對(duì)下班時(shí)間、約會(huì)情況、提交截止時(shí)間這些條件進(jìn)行判斷，從而決定是否要進(jìn)行在線課程測(cè)試。如下圖所示，整個(gè)流程類似一個(gè)樹(shù)狀結(jié)構(gòu)。
圖中每個(gè)條件和選擇都決定了最終的結(jié)果，Y or N。藍(lán)色的圓圈表示樹(shù)的葉子，即最終的決定。
把這種樹(shù)狀結(jié)構(gòu)對(duì)應(yīng)到一個(gè) G(x)中，G(x)的表達(dá)式為：
G(x)由許多gt(x)組成，即的做法。每個(gè)gt(x)就代表上圖中的藍(lán)色圓圈（樹(shù)的葉子）。這里的gt(x)是常數(shù)，因?yàn)槭翘幚砗?jiǎn)單的問(wèn)題。我們把這些gt(x)稱為base 。qt(x)表示每個(gè)gt(x)成立的條件，代表上圖中橘色箭頭的部分。不同的gt(x)對(duì)應(yīng)于不同的qt(x)，即從樹(shù)的根部到頂端葉子的路徑不同。圖中中的菱形代表每個(gè)簡(jiǎn)單的節(jié)點(diǎn)。所以，這些base 和就構(gòu)成了整個(gè)G(x)的形式，就像一棵樹(shù)一樣，從根部到頂端所有的葉子都安全映射到上述公式上去了。
決策樹(shù)實(shí)際上就是在模仿人類做決策的過(guò)程。一直以來(lái)，決策樹(shù)的應(yīng)用十分廣泛而且分類預(yù)測(cè)效果都很不錯(cuò)，而它在數(shù)學(xué)上的理論完備性不充分，倒也不必在意。
如果從另外一個(gè)方面來(lái)看決策樹(shù)的形式，不同于上述G(x)的公式，我們可以利用條件分支的思想，將整體G(x)分成若干個(gè)Gc(x)，也就是把整個(gè)大樹(shù)分成若干個(gè)小樹(shù)，如下所示：
上式中，G(x)表示完整的大樹(shù)，即full-tree ，b(x)表示每個(gè)分支條件，即 ，Gc(x)表示第c個(gè)分支下的子樹(shù)，即sub-tree。這種結(jié)構(gòu)被稱為遞歸型的數(shù)據(jù)結(jié)構(gòu)，即將大樹(shù)分割成不同的小樹(shù)，再將小樹(shù)繼續(xù)分割成更小的子樹(shù)。所以，決策樹(shù)可以分為兩部分：root和sub-trees。
在詳細(xì)推導(dǎo)決策樹(shù)算法之前，我們先來(lái)看一看它的優(yōu)點(diǎn)和缺點(diǎn)。首先， tree的優(yōu)點(diǎn)有：
然而， tree也有相應(yīng)的缺點(diǎn)：
2
Tree
我們可以用遞歸形式將 tree表示出來(lái)，它的基本的算法可以寫成：
這個(gè)Basic Tree 的流程可以分成四個(gè)部分，首先學(xué)習(xí)設(shè)定劃分不同分支的標(biāo)準(zhǔn)和條件是什么；接著將整體數(shù)據(jù)集D根據(jù)分支個(gè)數(shù)C和條件，劃為不同分支下的子集Dc；然后對(duì)每個(gè)分支下的Dc進(jìn)行訓(xùn)練，得到相應(yīng)的機(jī)器學(xué)習(xí)模型Gc；最后將所有分支下的Gc合并到一起，組成大矩G(x)。但值得注意的是，這種遞歸的形式需要終止條件，否則程序?qū)⒁恢边M(jìn)行下去。當(dāng)滿足遞歸的終止條件之后，將會(huì)返回基本的(x)。
所以，決策樹(shù)的基本演算法包含了四個(gè)選擇：
下面我們來(lái)介紹一種常用的決策樹(shù)模型算法，叫做 and Tree(C&RT)。C&RT算法有兩個(gè)簡(jiǎn)單的設(shè)定，首先，分支的個(gè)數(shù)C=2，即二叉樹(shù)（ tree）的數(shù)據(jù)結(jié)構(gòu)；然后，每個(gè)分支最后的gt(x)（數(shù)的葉子）是一個(gè)常數(shù)。按照最小化Ein的目標(biāo)，對(duì)于/ (0/1 error)問(wèn)題，看正類和負(fù)類哪個(gè)更多，gt(x)取所占比例最多的那一類yn；對(duì)于( error)問(wèn)題，gt(x)則取所有yn的平均值。
對(duì)于決策樹(shù)的基本演算法流程，C&RT還有一些簡(jiǎn)單的設(shè)定。首先，C&RT分支個(gè)數(shù)C=2，一般采用上節(jié)課介紹過(guò)的 stump的方法進(jìn)行數(shù)據(jù)切割。也就是每次在一個(gè)維度上，只對(duì)一個(gè)特征將數(shù)據(jù)一分為二，左子樹(shù)和右子樹(shù)，分別代表不同的類別。然而，怎么切割才能讓數(shù)據(jù)劃分得最好呢（error最小）？C&RT中使用純凈度這個(gè)概念來(lái)選擇最好的 stump。的核心思想就是每次切割都盡可能讓左子樹(shù)和右子樹(shù)中同類樣本占得比例最大或者yn都很接近（），即錯(cuò)誤率最小。比如說(shuō)問(wèn)題中，如果左子樹(shù)全是正樣本，右子樹(shù)全是負(fù)樣本，那么它的純凈度就很大，說(shuō)明該分支效果很好。
根據(jù)C&RT中的思想，我們得到選擇合適的分支條件b(x)的表達(dá)式如上所示。最好的 stump重點(diǎn)包含兩個(gè)方面：一個(gè)是剛剛介紹的分支純凈度，越大越好，而這里使用相反的概念，則越小越好；另外一個(gè)是左右分支純凈度所占的權(quán)重，權(quán)重大小由該分支的數(shù)據(jù)量決定，分支包含的樣本個(gè)數(shù)越多，則所占權(quán)重越大，分支包含的樣本個(gè)數(shù)越少，則所占權(quán)重越小。上式中的||代表了分支c所占的權(quán)重。這里b(x)類似于error （這也是為什么使用代替的原因），選擇最好的 stump，讓所有分支的不純度最小化，使b(x)越小越好。
不純度如何用函數(shù)的形式量化？一種簡(jiǎn)單的方法就是類比于Ein，看預(yù)測(cè)值與真實(shí)值的誤差是多少。對(duì)于問(wèn)題，它的可表示為：
對(duì)應(yīng)問(wèn)題，它的可表示為：
其中，y?表示對(duì)應(yīng)分支下所占比例最大的那一類。
以上這些是基于原來(lái)的 error和 error直接推導(dǎo)的。進(jìn)一步來(lái)看的 ，如果某分支條件下，讓其中一個(gè)分支純度最大，那么就選擇對(duì)應(yīng)的 stump，即得到的 error為：
其中，K為分支個(gè)數(shù)。
上面這個(gè)式子只考慮純度最大的那個(gè)分支，更好的做法是將所有分支的純度都考慮并計(jì)算在內(nèi)，用基尼指數(shù)（Gini index）表示：
Gini index的優(yōu)點(diǎn)是將所有的class在數(shù)據(jù)集中的分布狀況和所占比例全都考慮了，這樣讓 stump的選擇更加準(zhǔn)確。
對(duì)于決策樹(shù)C&RT算法，通常來(lái)說(shuō)，上面介紹的各種 中，Gini index更適合求解問(wèn)題，而 error更適合求解問(wèn)題。
C&RT算法迭代終止條件有兩種情況，第一種情況是當(dāng)前各個(gè)分支下包含的所有樣本yn都是同類的，即不純度為0，表示該分支已經(jīng)達(dá)到了最佳分類程度。第二種情況是該特征下所有的xn相同，無(wú)法對(duì)其進(jìn)行區(qū)分，表示沒(méi)有 。遇到這兩種情況，C&RT算法就會(huì)停止迭代。
所以，C&RT算法遇到迭代終止條件后就成為完全長(zhǎng)成樹(shù)（fully-grown tree）。它每次分支為二，是二叉樹(shù)結(jié)構(gòu)，采用來(lái)選擇最佳的 stump來(lái)劃分，最終得到的葉子（gt(x)）是常數(shù)。
3
Tree in C&RT
現(xiàn)在我們已經(jīng)知道了C&RT算法的基本流程：
可以看到C&RT算法在處理 和問(wèn)題時(shí)非常簡(jiǎn)單實(shí)用，而且，處理muti-class 問(wèn)題也十分容易。
考慮這樣一個(gè)問(wèn)題，有N個(gè)樣本，如果我們每次只取一個(gè)樣本點(diǎn)作為分支，那么在經(jīng)過(guò)N-1次分支之后，所有的樣本點(diǎn)都能完全分類正確。最終每片葉子上只有一個(gè)樣本，有N片葉子，即必然能保證Ein=0。這樣看似是完美的分割，但是不可避免地造成VC 無(wú)限大，造成模型復(fù)雜度增加，從而出現(xiàn)過(guò)擬合現(xiàn)象。為了避免，我們需要在C&RT算法中引入正則化，來(lái)控制整個(gè)模型的復(fù)雜度。
考慮到避免模型過(guò)于復(fù)雜的方法是減少葉子（gt(x)）的數(shù)量，那么可以令就為決策樹(shù)中葉子的總數(shù)，記為Ω(G)。正則化的目的是盡可能減少Ω(G)的值。這樣， tree的形式就可以表示成：
我們把這種 tree稱為 tree。是修剪的意思，通過(guò)來(lái)修剪決策樹(shù)，去掉多余的葉子，更簡(jiǎn)潔化，從而達(dá)到避免過(guò)擬合的效果。
那么如何確定修剪多少葉子，修剪哪些葉子呢？假設(shè)由C&RT算法得到一棵完全長(zhǎng)成樹(shù)（fully-grown tree），總共10片葉子。首先分別減去其中一片葉子，剩下9片，將這10種情況比較，取Ein最小的那個(gè)模型；然后再?gòu)?片葉子的模型中分別減去一片，剩下8片，將這9種情況比較，取Ein最小的那個(gè)模型。以此類推，繼續(xù)修建葉子。這樣，最終得到包含不同葉子的幾種模型，將這幾個(gè)使用 tree的error 來(lái)進(jìn)行選擇，確定包含幾片葉子的模型誤差最小，就選擇該模型。另外，參數(shù)λ可以通過(guò)來(lái)確定最佳值。
我們一直討論決策樹(shù)上的葉子（）都是 ，而實(shí)際應(yīng)用中，決策樹(shù)的特征值可能不是數(shù)字量，而是類別（ ）。對(duì)于 ，我們直接使用 stump進(jìn)行數(shù)值切割；而對(duì)于 ，我們?nèi)匀豢梢允褂?，對(duì)不同類別進(jìn)行“左”和“右”，即是與不是（0和1）的劃分。 和 的具體區(qū)別如下圖所示：
在決策樹(shù)中預(yù)測(cè)中，還會(huì)遇到一種問(wèn)題，就是當(dāng)某些特征缺失的時(shí)候，沒(méi)有辦法進(jìn)行切割和分支選擇。一種常用的方法就是 ，即尋找與該特征相似的替代。如何確定是相似的呢？做法是在決策樹(shù)訓(xùn)練的時(shí)候，找出與該特征相似的，如果替代的與原切割的方式和結(jié)果是類似的，那么就表明二者是相似的，就把該替代的也存儲(chǔ)下來(lái)。當(dāng)預(yù)測(cè)時(shí)遇到原缺失的情況，就用替代進(jìn)行分支判斷和選擇。
4
Tree in
最后我們來(lái)舉個(gè)例子看看C&RT算法究竟是如何進(jìn)行計(jì)算的。例如下圖二維平面上分布著許多正負(fù)樣本，我們使用C&RT算法來(lái)對(duì)其進(jìn)行決策樹(shù)的分類。
第一步：
第二步：
第三步：
第四步：
在進(jìn)行第四步切割之后，我們發(fā)現(xiàn)每個(gè)分支都已經(jīng)非常純凈了決策樹(shù)模型的應(yīng)用特點(diǎn)決策樹(shù)模型的應(yīng)用特點(diǎn)，沒(méi)有辦法繼續(xù)往下切割。此時(shí)表明已經(jīng)滿足了迭代終止條件，這時(shí)候就可以回傳base ，構(gòu)成sub tree，然后每個(gè)sub tree再往上整合形成tree，最后形成我們需要的完全決策樹(shù)。如果將邊界添加上去，可得到下圖：
得到C&RT算法的切割方式之后，我們與-Stump算法進(jìn)行比較：
我們之前就介紹過(guò)，-Stump算法的切割線是橫跨整個(gè)平面的；而C&RT算法的切割線是基于某個(gè)條件的，所以一般不會(huì)橫跨整個(gè)平面。比較起來(lái)，雖然C&RT和-Stump都采用 stump方式進(jìn)行切割，但是二者在細(xì)節(jié)上還是有所區(qū)別。
再看一個(gè)數(shù)據(jù)集分布比較復(fù)雜的例子，C&RT和-Stump的切割方式對(duì)比效果如下圖所示：
通常來(lái)說(shuō)，由于C&RT是基于條件進(jìn)行切割的，所以C&RT比-Stump分類切割更有效率。總結(jié)一下，C&RT決策樹(shù)有以下特點(diǎn)：
5
本節(jié)課主要介紹了 Tree。首先將 tree 對(duì)應(yīng)到不同分支下的矩gt(x)。然后再介紹決策樹(shù)算法是如何通過(guò)遞歸的形式建立起來(lái)。接著詳細(xì)研究了決策樹(shù)C&RT算法對(duì)應(yīng)的數(shù)學(xué)模型和算法架構(gòu)流程。最后通過(guò)一個(gè)實(shí)際的例子來(lái)演示決策樹(shù)C&RT算法是如何一步一步進(jìn)行分類的。
往期回顧
【1】
【2】
【3】
【4】
【5】
【6】
【7】
【8】
【9】？
【10】
長(zhǎng)按二維碼
掃描關(guān)注
如果喜歡我的文章，就請(qǐng)點(diǎn)贊或轉(zhuǎn)發(fā)吧！