基于決策數(shù)的分類方法是一種非常直觀的锉桑，非常好解釋的排霉，初中生都可以看得懂的分類算法，所以今天就給大家寫寫這個(gè)簡(jiǎn)單實(shí)用的分類算法民轴。

決策樹的基本流程就是通過一系列只能回答是否的問題將數(shù)據(jù)進(jìn)行分類攻柠，這種方法還可以很直觀地出圖，非常適合初學(xué)者后裸。

遞歸分類算法

先看一個(gè)概念瑰钮，遞歸，今天要寫的決策樹就是遞歸分類算法（recursive partitioning algorithm）的一種轻抱，所謂遞歸就是重復(fù)飞涂，把一個(gè)大問題化成可以重復(fù)的小問題從而達(dá)到問題的解決，決策樹就是把一個(gè)大問題化成很多個(gè)回答是否的小問題祈搜，重復(fù)重復(fù)就把大問題解決了较店。

其實(shí)自己是很不愿意在文章中整過多的專業(yè)名詞的，但是如果你想深入了解某個(gè)領(lǐng)域容燕，想進(jìn)一步提高姿勢(shì)水平梁呈，這些專業(yè)名詞肯定得學(xué)，所以大家見諒蘸秘，我盡量會(huì)寫的非常淺顯易懂官卡。

想象一下，人們的通勤工具的分類情形醋虏，我們會(huì)通過這個(gè)工具有幾個(gè)輪子寻咒，有沒有發(fā)動(dòng)機(jī)，多重等信息來判斷工具的類型颈嚼，知道了這些特征信息毛秘，你自己就會(huì)在腦海里形成一系列是否問題，達(dá)到對(duì)交通工具分類的目的，比如你的腦海里形成了像下圖一樣的流程：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

先回答這個(gè)工具有沒有發(fā)動(dòng)機(jī)叫挟，如果有艰匙，再回答多重，如果小于3噸抹恳，就是小汽車员凝，大于3噸就是坦克；如果沒有發(fā)動(dòng)機(jī)奋献，再回答有多少輪子健霹，小于2的話就是獨(dú)輪車，大于2的話再回答有沒有踏板秽荞，有則是自行車骤公，無則是小摩托，就是這么一個(gè)流程扬跋。這就是我們判斷交通工具時(shí)我們都會(huì)用的一個(gè)流程阶捆，也就是一個(gè)決策樹，也是你自己的思維的一個(gè)過程钦听。

在上面的流程中洒试，問題叫做節(jié)點(diǎn)node，最終的分類結(jié)局叫做葉leave朴上，那么整個(gè)決策樹畫出來就像一個(gè)倒立的樹一樣垒棋，所以叫做決策樹，就是這么簡(jiǎn)單痪宰。

對(duì)于我們來說叼架，決策樹的整個(gè)流程中，先問哪個(gè)問題至關(guān)重要衣撬。

你想想乖订，先通過交通工具的重量分類和先通過交通工具的輪子分類肯定是不一樣的嘛。

那么機(jī)器學(xué)習(xí)中具练，遞歸分類算法是如何選擇這個(gè)順序的呢乍构？

At each stage of the tree-building process, the rpart algorithm considers all of the predictor variables and selects the predictor that does the best job of discriminating the classes.

一個(gè)總的原則就是優(yōu)先用可以將數(shù)據(jù)劃分為最純的類的問題作為節(jié)點(diǎn)

這個(gè)純度可以用兩個(gè)指標(biāo)來衡量，一個(gè)是entropy扛点，另一個(gè)是Gini index哥遮，本文重點(diǎn)介紹Gini index。

用Gini index對(duì)樹進(jìn)行劃分

所謂最純就是說通過某個(gè)問題劃分出的兩類陵究，也就是樹分叉過后形成的兩類眠饮，這兩類內(nèi)部的一致性越大越好。Gini index就是純度的一個(gè)指標(biāo)铜邮，在形成樹的過程中君仆，我們希望每個(gè)節(jié)點(diǎn)的Gini index都是最大的。

Gini index的計(jì)算公式如下：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

其中p(A) p(B)是兩類在劃分過后的數(shù)據(jù)中的占比。從這兒式子大家也可以悟出來Gini index越大就說明純度越大返咱。

看下面的例子，比如我們父節(jié)點(diǎn)有20個(gè)個(gè)案牍鞠，2個(gè)類別AB咖摹，那么我們先進(jìn)行隨意劃分形成左右兩類，比如我們得到：左邊14個(gè)其中11個(gè)A3個(gè)B难述，右邊6個(gè)其中1個(gè)A5個(gè)B萤晴，這個(gè)時(shí)候我們的Gini index算法就如下圖：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

上面算出來每個(gè)節(jié)點(diǎn)的Gini index，我們還需要算出劃分后的Gini index胁后，算法如下：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

那么上面其實(shí)是數(shù)據(jù)通過了決策樹的一個(gè)節(jié)點(diǎn)店读，通過前后我們的數(shù)據(jù)純度怎么變的呢？

在前面已經(jīng)寫了攀芯，每一次劃分我們期望的結(jié)果都是越純?cè)胶猛投希晕覀兪窍Ｍ覀兊淖庸?jié)點(diǎn)的Gini index越小越好，因?yàn)槲覀兛梢杂貌煌膯栴}來劃分我們的數(shù)據(jù)侣诺，所以整個(gè)過程就等價(jià)于我們希望劃分之前和劃分之后的Gini index的差（這個(gè)叫做Gini gain）越大越好殖演。

所以就是哪個(gè)問題（也就是變量）帶來的Gini gain越大，我們就越先使用哪個(gè)問題來劃分?jǐn)?shù)據(jù)年鸳。

在我們上面這個(gè)例子中我們父節(jié)點(diǎn)的Gini index是0.48趴久，劃分后是0.32，我們的Gini gain就是0.16搔确。就是說如果你能找到別的變量彼棍，用別的變量形成的問題來劃分得到的Gini gain大于0.16的話我們就會(huì)先用那個(gè)別的變量來劃分。

連續(xù)變量和多分類變量怎么辦膳算？

之前寫的都是用是否回答的問題進(jìn)行樹的劃分座硕，那么遇到連續(xù)或者多分類的特征，決策樹還能不能行呢畦幢？

可以的

看下圖坎吻，下圖中的數(shù)據(jù)有3類，有兩個(gè)連續(xù)的特征宇葱，variable1和variable2瘦真，我們?cè)谶@兩個(gè)連續(xù)特征形成的平面上可以畫出兩條線，這兩條線形成的問題就可以作為節(jié)點(diǎn)黍瞧，比如我們先看variable1诸尽，如果一個(gè)個(gè)案variable1大于等于20我們化成一個(gè)分支，小于20化成另一個(gè)分支印颤，再用variable2您机，如果一個(gè)個(gè)案在variable1大于等于20的情況下，variable2小于10000則為一個(gè)分支，否則為另一個(gè)分支际看，這樣咸产，我們就得到了下圖右邊的決策樹：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

但是進(jìn)一步想想，有些同學(xué)就要問了仲闽，這個(gè)20和10000又是如何確定的啊

依然是通過GIni gain確定的.

算法會(huì)首先將個(gè)案按照連續(xù)特征進(jìn)行排序脑溢，然后先以相鄰兩個(gè)個(gè)案中點(diǎn)進(jìn)行劃分，并計(jì)算Gini gain赖欣，如果恰好這個(gè)點(diǎn)就是最好的點(diǎn)屑彻，那么就選它，如果不是顶吮，那就這樣挨著挨著試直到找到最好的哪一個(gè)：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

同樣的社牲，對(duì)于多分類特征也是如此，我們先按照分類變量的水平的Gini index進(jìn)行排序悴了，然后在每個(gè)相鄰水平進(jìn)行劃分搏恤，找最大的gini gain的點(diǎn)作為我們最佳的劃分點(diǎn)：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

決策樹算法的超參

想象一下，如果我們的數(shù)據(jù)特征非常多让禀，然后每個(gè)變量一個(gè)節(jié)點(diǎn)挑社，那么最終形成的樹肯定非常“茂盛”巡揍，太茂盛也不是好事痛阻，不僅耗費(fèi)算力，還容易過擬合腮敌，所以我們得認(rèn)為控制這個(gè)樹的茂盛程度阱当，方法有2：

• 先生成全樹，然后修剪
• 設(shè)定標(biāo)準(zhǔn)糜工，不讓樹長(zhǎng)那么茂盛

具體地弊添，第一種方法只用設(shè)置你想剪掉的枝葉就行，對(duì)于第二種方法我們可以設(shè)定的標(biāo)準(zhǔn)就多了捌木，比如你可以設(shè)定每個(gè)節(jié)點(diǎn)的最小個(gè)案數(shù)量油坝，設(shè)定樹的深度，設(shè)定最小擬合優(yōu)度增加值等等刨裆。

看下圖：左上就是設(shè)定不同個(gè)案數(shù)量的情況澈圈，右上是設(shè)定樹的深度，左下是設(shè)定擬合優(yōu)度帆啃，右下是設(shè)定最小個(gè)案：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

這兒給大家講講這個(gè)cp指標(biāo)瞬女，這個(gè)指標(biāo)的英文全稱是complexity parameter，是用來評(píng)價(jià)樹的優(yōu)度的努潘，這個(gè)值計(jì)算方法如下：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

由上面的式子可以看出诽偷，cp值越大表面該節(jié)點(diǎn)相對(duì)于上節(jié)點(diǎn)表現(xiàn)越差坤学。

上面介紹的4個(gè)超參都是我們?cè)谟?xùn)練決策樹模型時(shí)需要調(diào)試的，接著我們看實(shí)例

決策樹實(shí)例操練

現(xiàn)在有一個(gè)關(guān)于動(dòng)物特征的數(shù)據(jù)集报慕，我希望訓(xùn)練一個(gè)決策樹模型深浮，通過這些特征將我們的個(gè)案劃分為不同的類型的動(dòng)物，數(shù)據(jù)集大概長(zhǎng)這樣：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

我們的響應(yīng)變量是type卖子，其余的變量全是預(yù)測(cè)變量略号，模型的訓(xùn)練依然是3步，第一定義任務(wù)洋闽，第二定義學(xué)習(xí)器，第三訓(xùn)練突梦，前兩步的代碼如下：

zooTask <- makeClassifTask(data = zooTib, target = "type")
tree <- makeLearner("classif.rpart")

接下來就是超參調(diào)試诫舅，前面也給大家寫了，我們主要需要調(diào)試的超參為minsplit, minbucket, cp, 和maxdepth這4個(gè)超參數(shù)宫患，我們定義超參空間刊懈，搜索方法和驗(yàn)證方法的代碼如下：

treeParamSpace <- makeParamSet(
  makeIntegerParam("minsplit", lower = 5, upper = 20),
  makeIntegerParam("minbucket", lower = 3, upper = 10),
  makeNumericParam("cp", lower = 0.01, upper = 0.1),
  makeIntegerParam("maxdepth", lower = 3, upper = 10))
randSearch <- makeTuneControlRandom(maxit = 200)
cvForTuning <- makeResampleDesc("CV", iters = 5)

定義好相應(yīng)的參數(shù)之后，接下來我們就可以來進(jìn)行調(diào)試了：

tunedTreePars <- tuneParams(tree, task = zooTask,
resampling = cvForTuning,
par.set = treeParamSpace,
control = randSearch)
parallelStop()

運(yùn)行上面的代碼我們得到的最優(yōu)超參組合如下圖所示：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

然后我們要做的就是用最優(yōu)超參重新訓(xùn)練我們的模型并進(jìn)行模型的交叉驗(yàn)證娃闲，用最優(yōu)超參訓(xùn)練模型的代碼如下：

tunedTree <- setHyperPars(tree, par.vals = tunedTreePars$x)
tunedTreeModel <- train(tunedTree, zooTask)

運(yùn)行上面的代碼我們就訓(xùn)練好了我們決策樹模型tunedTreeModel虚汛，我們還可以通過以下代碼將決策樹可視化出來：

treeModelData <- getLearnerModel(tunedTreeModel)
rpart.plot(treeModelData, roundint = FALSE,
           box.palette = "BuBn",
           type = 5)
printcp(treeModelData, digits = 3)

樹的樣子如下：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

可以看到?jīng)Q策樹這個(gè)算法的可解釋性是真的好，對(duì)于我們的例子皇帮，我們首先用milk變量形成一個(gè)問題卷哩，再用feathers變量形成另外一個(gè)問題等等，然后根據(jù)問題的答案一直這么順下去就達(dá)到了我們給數(shù)據(jù)分類的目的属拾。

不止上面的信息将谊，代碼還會(huì)給我們輸出每一次劃分的cp值，如下圖：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

模型的交叉驗(yàn)證

交叉驗(yàn)證的部分依然從兩個(gè)方面理解渐白，首先是外部尊浓，就是我們?nèi)绾坞S機(jī)抽不同的數(shù)據(jù)進(jìn)行預(yù)測(cè)，另一面就是內(nèi)部驗(yàn)證纯衍，就是我在訓(xùn)練模型的時(shí)候如何調(diào)試超參栋齿，從而使得模型對(duì)訓(xùn)練集擬合的更好，內(nèi)外部代碼如下：

outer <- makeResampleDesc("CV", iters = 5)
treeWrapper <- makeTuneWrapper("classif.rpart", resampling = cvForTuning,
                               par.set = treeParamSpace,
                               control = randSearch)
parallelStartSocket(cpus = detectCores())
cvWithTuning <- resample(treeWrapper, zooTask, resampling = outer)
parallelStop()
cvWithTuning

運(yùn)行上面代碼然后看驗(yàn)證結(jié)果：

R機(jī)器學(xué)習(xí)：基于樹的分類算法的原理及實(shí)現(xiàn)

可以看到襟诸，模型的mean misclassification error (MMCE)挺高的瓦堵，甚至比我們調(diào)試超參的時(shí)候得到的0.078還大，這個(gè)其實(shí)是可以理解的励堡，我們調(diào)試超參只是為了讓模型更好擬合我們的訓(xùn)練集谷丸，通過交叉驗(yàn)證雖然擬合降低了，但是外推性更好了应结，可以很好地避免模型的過擬合問題刨疼。

好了泉唁，今天的文章就到這兒。最近微信粉絲增加的有點(diǎn)猛哈揩慕，很多同學(xué)私信發(fā)來了感謝和鼓勵(lì)亭畜，真的謝謝大家啦，嘿嘿迎卤。

小結(jié)

今天給大家寫了決策樹的原理和實(shí)現(xiàn)方法拴鸵，感謝大家耐心看完，自己的文章都寫的很細(xì)蜗搔，代碼都在原文中劲藐，希望大家都可以自己做一做，請(qǐng)關(guān)注后私信回復(fù)“數(shù)據(jù)鏈接”獲取所有數(shù)據(jù)和本人收集的學(xué)習(xí)資料樟凄。如果對(duì)您有用請(qǐng)先收藏聘芜，再點(diǎn)贊轉(zhuǎn)發(fā)。

也歡迎大家的意見和建議缝龄，大家想了解什么統(tǒng)計(jì)方法都可以在文章下留言汰现，說不定我看見了就會(huì)給你寫教程哦，另叔壤，咨詢代做請(qǐng)私信瞎饲。