應(yīng)用及介紹

是一個(gè)預(yù)測(cè)模型，分為回歸決策樹(shù)和分類決策樹(shù)，根據(jù)已知樣本訓(xùn)練出一個(gè)樹(shù)模型，從而根據(jù)該模型對(duì)新樣本因變量進(jìn)行預(yù)測(cè)，得到預(yù)測(cè)值或預(yù)測(cè)的分類

從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條規(guī)則．整棵決策樹(shù)就對(duì)應(yīng)著一組表達(dá)式規(guī)則。葉節(jié)點(diǎn)就代表該規(guī)則下得到的預(yù)測(cè)值。如下圖決策樹(shù)模型則是根據(jù)房產(chǎn)、結(jié)婚、月收入三個(gè)屬性得到是否可以償還貸款的規(guī)則。

image.png

決策樹(shù)的構(gòu)建

核心是如何從眾多屬性中挑選出具有代表性的屬性作為決策樹(shù)的分支節(jié)點(diǎn)。

最基本的有三種度量方法來(lái)選擇屬性

1. 信息增益（ID3算法）

信息熵

一個(gè)信源發(fā)送出什么符號(hào)是不確定的，衡量它可以根據(jù)其出現(xiàn)的概率來(lái)度量。概率大，出現(xiàn)機(jī)會(huì)多，不確定性小；反之不確定性就大。不確定性函數(shù)f是概率P的減函數(shù)。兩個(gè)獨(dú)立符號(hào)所產(chǎn)生的不確定性應(yīng)等于各自不確定性之和，即f(P1,P2)=f(P1)+f(P2)，這稱為可加性。同時(shí)滿足這兩個(gè)條件的函數(shù)f是對(duì)數(shù)函數(shù)，即

信息

在信源中，考慮的不是某一單個(gè)符號(hào)發(fā)生的不確定性，而是要考慮這個(gè)信源所有可能發(fā)生情況的平均不確定性。因此，信息熵被定義為

信息熵公式

決策樹(shù)分類過(guò)程

• 首先，假設(shè)數(shù)據(jù)集D中需要預(yù)測(cè)的標(biāo)記類分為類A和類B，根據(jù)總體類A,B的出現(xiàn)概率計(jì)算信息熵G1。
• 依次選擇每一個(gè)屬性，如果該屬性為離散型，計(jì)算該屬性取每個(gè)值的類A,B概率，得出該屬性的信息熵Gi；若為連續(xù)值屬性，則依次排序后選每?jī)蓚€(gè)相鄰值的中點(diǎn)，每個(gè)中點(diǎn)得到2個(gè)分區(qū)類似離散屬性的2個(gè)類別，選擇信息熵最小的那個(gè)中點(diǎn)作為該屬性的分裂點(diǎn)。計(jì)算該屬性的信息熵。
• 計(jì)算屬性i的信息增益，也就是G1 - Gi，選擇信息增益最大的屬性作為分裂節(jié)點(diǎn)，依次遞歸

2、增益率（C4.5算法）
由于信息增益的缺點(diǎn)是：傾向于選擇具有大量值的屬性，因?yàn)榫哂写罅恐档膶傩悦總€(gè)屬性對(duì)應(yīng)數(shù)據(jù)量少，傾向于具有較高的信息純度。因此增益率使用【信息增益/以該屬性代替的系統(tǒng)熵（類似于前面第一步將play換為該屬性計(jì)算的系統(tǒng)熵】這個(gè)比率，試圖克服這種缺點(diǎn)。
g(D,A)代表D數(shù)據(jù)集A屬性的信息增益，

3. 基尼指數(shù)（CART算法）

基尼指數(shù)：

表示在樣本集合中一個(gè)隨機(jī)選中的樣本被分錯(cuò)的概率。越小表示集合中被選中的樣本被分錯(cuò)的概率越小，也就是說(shuō)集合的純度越高。

假設(shè)集合中有K個(gè)類別，則：

基尼系數(shù)

說(shuō)明:

1. pk表示選中的樣本屬于k類別的概率，則這個(gè)樣本被分錯(cuò)的概率是(1-pk)

2. 樣本集合中有K個(gè)類別，一個(gè)隨機(jī)選中的樣本可以屬于這k個(gè)類別中的任意一個(gè)，因而對(duì)類別就加和

3. 當(dāng)為二分類是，Gini(P) = 2p(1-p)

基尼指數(shù)是將屬性A做二元?jiǎng)澐?，所以得到的是二叉?shù)。當(dāng)為離散屬性時(shí)，則會(huì)將離散屬性的類別兩兩組合，計(jì)算基尼指數(shù)。

舉個(gè)例子：

如上面的特征Temperature，此特征有三個(gè)特征取值： “Hot”，“Mild”， “Cool”，
當(dāng)使用“學(xué)歷”這個(gè)特征對(duì)樣本集合D進(jìn)行劃分時(shí)，劃分值分別有三個(gè)，因而有三種劃分的可能集合，劃分后的子集如下：

1. 劃分點(diǎn)： “Hot”，劃分后的子集合 ： {Hot}，{Mild，Cool}
2. 劃分點(diǎn)： “Mild”，劃分后的子集合 ： {Mild}，{Cool，Hot}
3. 劃分點(diǎn)： “Cool”，劃分后的子集合 ： {Cool}，{Mild，Hot}

對(duì)于上述的每一種劃分，都可以計(jì)算出基于 劃分特征= 某個(gè)特征值 將樣本集合D劃分為兩個(gè)子集的純度：

決策數(shù)分類過(guò)程

• 首先，假設(shè)數(shù)據(jù)集D中需要預(yù)測(cè)的標(biāo)記類分為類A和類B，根據(jù)總體類A,B的出現(xiàn)概率計(jì)算基尼指數(shù)G1。
• 依次選擇每一個(gè)屬性，如果該屬性為離散型，按上面的方法將離散屬性的類別兩兩組合，計(jì)算基尼指數(shù)；若為連續(xù)值屬性，類似信息增益的方法。計(jì)算該屬性的基尼指數(shù)Gi。
• 計(jì)算屬性i的基尼指數(shù)降低值，也就是G1 - Gi，選擇降低最大的屬性作為分裂節(jié)點(diǎn)，依次遞歸

總結(jié)：以上時(shí)分類決策樹(shù)最常用的三種屬性選擇度量，信息增益傾向于選擇多值屬性；增益率傾向于產(chǎn)生不平衡的劃分，一個(gè)分區(qū)比其他分區(qū)小得多；基尼指數(shù)偏向于多值屬性，并且在類的數(shù)量很大時(shí)會(huì)有困難.其它屬性選擇度量如基于統(tǒng)計(jì)卡方檢驗(yàn)的屬性度量、最小描述長(zhǎng)度(MDL，基本思想是首選最簡(jiǎn)單的解）

剪枝

先剪枝：提前停止樹(shù)的構(gòu)建對(duì)樹(shù)剪枝，構(gòu)造樹(shù)時(shí)，利用信息增益、統(tǒng)計(jì)顯著性等，當(dāng)一個(gè)節(jié)點(diǎn)的劃分導(dǎo)致低于上述度量的預(yù)定義閾值時(shí)，則停止進(jìn)一步劃分。但閾值的確定比較困難。
后剪枝：更為常用，先得到完全生長(zhǎng)的樹(shù)，再自底向上，用最下面的節(jié)點(diǎn)的樹(shù)葉代替該節(jié)點(diǎn)
CART使用代價(jià)復(fù)雜度剪枝算法：計(jì)算每個(gè)節(jié)點(diǎn)剪枝后與剪枝前的代價(jià)復(fù)雜度，如果剪去該節(jié)點(diǎn)，代價(jià)復(fù)雜度較?。◤?fù)雜度是樹(shù)的結(jié)點(diǎn)與樹(shù)的錯(cuò)誤率也就是誤分類比率的函數(shù)），則剪去。
C4.5采用悲觀剪枝：類似代價(jià)復(fù)雜度，但CART是利用剪枝集評(píng)估代價(jià)復(fù)雜度，C4.5是采用訓(xùn)練集加上一個(gè)懲罰評(píng)估錯(cuò)誤率

拓展

決策樹(shù)的可伸縮性

ID3\C4.5\CART都是為較小的數(shù)據(jù)集設(shè)計(jì)，都限制訓(xùn)練元祖停留再內(nèi)存中，為了解決可伸縮性，提出了其它算法如
RainForest(雨林）：對(duì)每個(gè)屬性維護(hù)一個(gè)AVC集，描述該結(jié)點(diǎn)的訓(xùn)練元組，所以只要將AVC集放在內(nèi)存即可
BOAT自助樂(lè)觀算法：利用統(tǒng)計(jì)學(xué)，創(chuàng)造給定訓(xùn)練數(shù)據(jù)的較小樣本，每個(gè)樣本構(gòu)造一個(gè)樹(shù)，導(dǎo)致多顆樹(shù)，再利用它們構(gòu)造1顆新樹(shù)。優(yōu)點(diǎn)是可以增量的更新，當(dāng)插入或刪除數(shù)據(jù)，只需決策樹(shù)更新，而不用重新構(gòu)造。

決策樹(shù)的可視化挖掘
PBC系統(tǒng)可允許用戶指定多個(gè)分裂點(diǎn)，導(dǎo)致多個(gè)分支，傳統(tǒng)決策樹(shù)算法數(shù)值屬性都是二元?jiǎng)澐?。并且可以?shí)現(xiàn)交互地構(gòu)建樹(shù)。

R語(yǔ)言構(gòu)建決策樹(shù)

rpart是采用cart算法，連續(xù)型“anova”;離散型“class”;

library(rpart)
rtmodel <- rpart(review_Count~.,data=highdata,method="anova")
#繪制決策樹(shù)
library(rpart.plot)
prp(rtmodel,extra=101,box.col="orange",split.box.col="grey")
printcp(rtmodel)

data$neighborhood <- lapply(data$neighborhood,foo)
data$neighborhood <- as.factor(unlist(data$neighborhood))
maindata <- data[,-c(1:5,10,11)]

2）進(jìn)行剪枝的函數(shù)：prune()

prune(tree, cp, ...)

主要參數(shù)說(shuō)明:

tree：一個(gè)回歸樹(shù)對(duì)象,常是rpart()的結(jié)果對(duì)象。

cp：復(fù)雜性參量,指定剪枝采用的閾值。cp全稱為complexity parameter，指某個(gè)點(diǎn)的復(fù)雜度，對(duì)每一步拆分,模型的擬合優(yōu)度必須提高的程度，用來(lái)節(jié)省剪枝浪費(fèi)的不必要的時(shí)間。

3）計(jì)算MAE評(píng)估回歸樹(shù)模型誤差，這里將樣本劃分成了訓(xùn)練集和測(cè)試集，testdata為測(cè)試集
rt.mae為根據(jù)訓(xùn)練集得到的決策樹(shù)模型對(duì)測(cè)試集因變量預(yù)測(cè)的結(jié)果與測(cè)試集因變量實(shí)際值得到平均絕對(duì)誤差

rt.predictions.arpu <-
    predict(rtmodel, testdata)
rt.mae <- mean(abs(rt.predictions.arpu
    - testdata[["oddreview"]]))
rt.mae