# 決策樹算法

• • 1 決策樹算法的引入
  • • 1.1樹的概念
    • 1.2算法思路
    • 1.3構(gòu)建決策樹的三個(gè)步驟
  • 2 特征分類的評(píng)價(jià)指標(biāo)
  • • 2.1熵的概念
    • 2.2信息熵的概念
    • 2.3Gini系數(shù)
  • 3 ID3算法
  • 4 C4.5
  • • 4.1決策樹對(duì)連續(xù)屬性的處理
    • 4.2決策樹對(duì)離散屬性的處理
  • 5 CART分類回歸樹
  • • 5.1CART分類回歸樹簡(jiǎn)介
    • 5.2CART分類樹---待預(yù)測(cè)結(jié)果為離散型數(shù)據(jù)
    • 5.3CART回歸樹--待預(yù)測(cè)結(jié)果為連續(xù)型數(shù)據(jù)
    • 5.4CART回歸樹示例
    • 5.5 CART樹與GBDT的區(qū)別
  • 6 sklearn庫的應(yīng)用

1 決策樹算法的引入

決策樹算法:非參數(shù)(不限制接收數(shù)據(jù)的結(jié)構(gòu)和類型)的監(jiān)督模型,可決策分類與回歸的問題.

1.1樹的概念

樹分為根節(jié)點(diǎn),分支節(jié)點(diǎn),葉子節(jié)點(diǎn).
根節(jié)點(diǎn):存儲(chǔ)著所有樣本數(shù)據(jù)
分支節(jié)點(diǎn):決策樹算法會(huì)利用當(dāng)前節(jié)點(diǎn)中的樣本來決策選擇哪個(gè)特征做分支
葉子節(jié)點(diǎn):最后不再分支的節(jié)點(diǎn)
分支節(jié)點(diǎn)與葉子節(jié)點(diǎn)都有其所屬的類別標(biāo)簽,當(dāng)類別標(biāo)簽是離散的(分類問題),節(jié)點(diǎn)的label標(biāo)簽為當(dāng)前節(jié)點(diǎn)中樣本所屬label最多的作為當(dāng)前節(jié)點(diǎn)的label.當(dāng)類別標(biāo)簽是連續(xù)的(回歸問題),節(jié)點(diǎn)的label標(biāo)簽為當(dāng)前節(jié)點(diǎn)中所有樣本label的均值.

對(duì)樣本特征的幾種編碼思路
LabelEncoder編碼:對(duì)樣本中特征的取值的編碼(如對(duì)年齡特征的取值為青年,中年,老年,編碼為0,1,2)

one-hot編碼:也是對(duì)樣本中的特征的取值編碼

機(jī)器學(xué)習(xí)的處理問題流程:
1.數(shù)據(jù)角度—有標(biāo)簽數(shù)據(jù)(無監(jiān)督,有監(jiān)督)
2.業(yè)務(wù)角度—是否有預(yù)測(cè)—有預(yù)測(cè)—>監(jiān)督學(xué)習(xí)—>根據(jù)預(yù)測(cè)值是否連續(xù)或離散—>分類或回歸
—無預(yù)測(cè)—>非監(jiān)督學(xué)習(xí)

1.2算法思路

利用樹的結(jié)構(gòu),將數(shù)據(jù)集根據(jù)樣本中的特征(屬性)劃分為樹中的分支節(jié)點(diǎn),并最終分到葉子節(jié)點(diǎn)

決策樹算法的核心是要解決兩個(gè)問題:
1.如何從數(shù)據(jù)集表中找到最佳節(jié)點(diǎn)和最佳分支
2.如何讓決策樹停止生長(zhǎng),防止過擬合

1.3構(gòu)建決策樹的三個(gè)步驟

1.特征選擇:選取有較強(qiáng)分類能力的特征
通過信息熵增益/信息熵增益率/gini系數(shù)/分類錯(cuò)誤率來判斷特征的分類能力
2.決策樹生成
典型算法:ID3,C4.5,他們生成決策樹過程相似, ID3采用信息熵增益作為特征選擇度量,C4.5采用信息熵增益比率,CART樹采用gini系數(shù)
3.決策樹剪枝
決策樹產(chǎn)生了過擬合現(xiàn)象(模型對(duì)訓(xùn)練集效果很好,對(duì)位置數(shù)據(jù)效果很差)
注意:決策樹構(gòu)建直到?jīng)]有特征可選或者信息增益很小時(shí)停止,這就導(dǎo)致了構(gòu)建的決策樹模型過于復(fù)雜.
發(fā)生過擬合是由于決策樹太復(fù)雜,解決辦法是控制模型的復(fù)雜度對(duì)于決策樹來說就是簡(jiǎn)化模型:剪枝(又分為先剪枝與后剪枝)

2 特征分類的評(píng)價(jià)指標(biāo)

2.1熵的概念

信息:信息就是對(duì)不確定性的消除(把信息理解為一種不確定性)
熵定義為信息(不確定性)的期望值
一個(gè)可以分類為n個(gè)label的數(shù)據(jù)集S,它的信息熵為隨機(jī)得到的一個(gè)label包含的信息量(不確定性)的期望值.
不確定性公式:I(X)=-log( p )
信息熵公式:E(S)=

上述若對(duì)數(shù)的底數(shù)取值為2,就是我們平常所說的信息單位bit(比特)

pi為取得對(duì)應(yīng)label的概率.
數(shù)據(jù)集的信息熵代表了這個(gè)數(shù)據(jù)集的混亂程度,信息熵越大,越混亂.

2.2信息熵的概念

若按照某種特定方式,例如按照某一屬性的值對(duì)S進(jìn)行劃分,得到n個(gè)子集,新的子集們都有自己的信息熵(子集內(nèi)部討論),屬性所有子集的(子集所占比例*子集的信息熵)的和與原S的熵的差值就是這個(gè)劃分操作帶來的信息熵增益.

總結(jié):
變量的不確定性越大,熵也就越大.熵越小,信息的純度越高.在構(gòu)建我們的決策樹的過程中,希望選擇信息熵比較小的,因?yàn)樾畔㈧匦?duì)應(yīng)的信息純度越高

基于信息熵和信息增益來建立決策樹
如何根據(jù)熵建立一顆決策樹?
選擇熵比較小的特征或者屬性作為分支節(jié)點(diǎn)
原因:因?yàn)殪匦?信息純度越高

2.3Gini系數(shù)

Gini系數(shù)是一種與信息熵類似的做特征選擇的方式,可以用來表征數(shù)據(jù)集樣本的不純度.在CART(Classifier and Regression Tree)算法中利用Gini系數(shù)構(gòu)造二叉分類回歸樹.
Gini系數(shù)的計(jì)算方式如下:

其中,D表示數(shù)據(jù)集全體樣本,pi表示每種類別出現(xiàn)的概率,取個(gè)極端情況,如果數(shù)據(jù)集中所有的樣本都為同一類,那么有p0=1,Gini(D)=0,顯然此時(shí)數(shù)據(jù)的不純度最低.
如果樣本集合D根據(jù)某個(gè)特征A被分割為D1,D2兩個(gè)部分,那么在特征A作為劃分的條件下,集合D的Gini系數(shù)定義為:

Gini(D,A)表示特征A不同分組的數(shù)據(jù)集D的不確定性,Gini指數(shù)越大,樣本集合的不確定性也就越大,這一點(diǎn)與熵的概念比較類似.
Gini(D1)/Gini(D2)的解釋:
特征A有兩個(gè)取值,根據(jù)取值可以把數(shù)據(jù)集D分為兩個(gè)子集D1,D2.在子集中討論各自的Gini系數(shù).
所以數(shù)據(jù)不純度減小程度:
△Gini(A)=Gini(D)-Gini(D,A)
顯然,在做特征選擇的時(shí)候,我們選取△Gini(A)最大的那個(gè)

Gini系數(shù)相對(duì)于信息熵增益率的優(yōu)勢(shì):
熵的計(jì)算用到了大量的對(duì)數(shù)運(yùn)算,計(jì)算機(jī)中對(duì)數(shù)運(yùn)算相對(duì)于基本運(yùn)算需要的時(shí)間成本更多,這在模型較為復(fù)雜時(shí)會(huì)嚴(yán)重拖慢計(jì)算速度.所有采用Gini系數(shù)作為判斷標(biāo)準(zhǔn)可以在保證準(zhǔn)確率的同時(shí)加快計(jì)算速度.

3 ID3算法

信息增益概念的含義與本質(zhì)
含義:劃分訓(xùn)練數(shù)據(jù)集前后信息發(fā)生的變化
本質(zhì):衡量給定屬性對(duì)訓(xùn)練數(shù)據(jù)集的劃分能力.

我們使用信息增益來作為決策樹分支的劃分依據(jù),它也是決策樹分支上整個(gè)數(shù)據(jù)集信息熵與當(dāng)前節(jié)點(diǎn)(劃分節(jié)點(diǎn))信息熵的差值,通常用Gain(A)表示
Gain(A)=H(總) -H(A)
H(總)=

其中pi是類別標(biāo)簽i的概率,所以H(總)計(jì)算的是類別標(biāo)簽的不確定性的期望
H(A):以A為劃分條件的所有子集信息熵之和.
信息增益:總體的信息熵-以某個(gè)特征作為劃分標(biāo)準(zhǔn)的信息熵

假設(shè)在某個(gè)分支節(jié)點(diǎn)中:Gain(age)>Gian(income)>Gain(“sex”) --這里對(duì)所有特征的信息熵有一個(gè)排序的過程
那么在建立決策樹選擇特征age分支
ID3算法原理:
輸入:數(shù)據(jù)集
輸出:決策樹
算法:
1.計(jì)算所有特征的信息增益,選擇信息增益最大的特征作為劃分節(jié)點(diǎn)
2.把劃分節(jié)點(diǎn)從當(dāng)前特征集合中去除
TA=T-{a}
3.在特征集合中重新選擇信息增益最大的特征作為劃分節(jié)點(diǎn)
4.直到所有的樣本都劃分為葉子節(jié)點(diǎn)

注意:計(jì)算信息增益的時(shí)候,將所有特征或?qū)傩缘男畔⒃鲆嬗?jì)算出來了,只需要排序和選擇就可以了

4 C4.5

和ID3算法類似,只是在以下幾個(gè)點(diǎn)做了改進(jìn)
1.用信息增益率選擇屬性,避免了ID3偏向于選擇取值多的屬性 這一不足點(diǎn)

2.在樹構(gòu)造過程中進(jìn)行了剪枝
3.能夠完成連續(xù)屬性的離散化處理
4.能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理

4.1決策樹對(duì)連續(xù)屬性的處理

具體的劃分規(guī)則:采用的是一種遍歷的方式,找出所有已知連續(xù)值中最適合當(dāng)前屬性分裂的值作為二分類值.
CART樹中也是用的這種方式處理連續(xù)屬性

4.2決策樹對(duì)離散屬性的處理

決策樹與CART分類回歸樹對(duì)于屬性離散值的處理區(qū)別:與CART樹都是二叉樹不同,決策樹是可以有多分叉的,所以對(duì)屬性離散值不做處理.CART樹對(duì)屬性離散值的處理為雙化策略,生成多顆CART樹,選擇效果最好的一顆.

5 CART分類回歸樹

5.1CART分類回歸樹簡(jiǎn)介

CART分類回歸樹是一種典型的二叉決策樹,可以做分類或者回歸.如果待預(yù)測(cè)結(jié)果是離散型數(shù)據(jù),則CART生成分類決策樹;如果待預(yù)測(cè)結(jié)果是連續(xù)性數(shù)據(jù),則CART生成回歸決策樹.數(shù)據(jù)對(duì)象的屬性特征為離散型或連續(xù)型,并不是區(qū)別分類樹與回歸樹的標(biāo)準(zhǔn).例如表1中,數(shù)據(jù)對(duì)象xi的屬性A,B為離散型/連續(xù)型并不是區(qū)分分類樹與回歸樹的標(biāo)準(zhǔn).作為分類決策樹時(shí),待預(yù)測(cè)樣本落至某一葉子節(jié)點(diǎn),則輸出該葉子節(jié)點(diǎn)中所有樣本所屬類別最多的那一類(即葉子節(jié)點(diǎn)中的樣本可能不是屬于同一類別,則多數(shù)為主);作為回歸決策樹時(shí),待預(yù)測(cè)樣本落至某一葉子節(jié)點(diǎn),則輸出該葉子節(jié)點(diǎn)中所有樣本的均值.

5.2CART分類樹—待預(yù)測(cè)結(jié)果為離散型數(shù)據(jù)

選擇具有最大Gain_Gini的屬性及其屬性值,作為最優(yōu)分裂屬性以及最優(yōu)分裂屬性值.Gain_Gini值越大,說明二分之后的子樣本集的”純凈度”越高,即說明選擇該屬性(值)作為分裂屬性(值)的效果越好.
此處要選的有兩個(gè):最優(yōu)分裂屬性以及其對(duì)應(yīng)的屬性值
對(duì)于樣本集S,GINI計(jì)算如下:

其中,樣本集S中,Pk表示分類結(jié)果中第k個(gè)類別出現(xiàn)的頻率
對(duì)于含有N個(gè)樣本的樣本集S,根據(jù)屬性A的第i個(gè)屬性值,將數(shù)據(jù)集S劃分為兩部分,則劃分成兩部分之后,Gain_Gini計(jì)算如下:

其中,n1,n2分別為樣本S1,S2的樣本個(gè)數(shù)
對(duì)于屬性A,分別計(jì)算任意屬性值將數(shù)據(jù)集劃分成兩部分(是二叉樹,這也是為什么CART樹對(duì)離散屬性(非數(shù)值型 )采取雙化的原因,而對(duì)于連續(xù)屬性,采用遍歷所有已知連續(xù)值找到最好的劃分值)之后的Gain_Gini,選取其中的最小值,作為屬性A得到的最優(yōu)二分方案:

所以分類決策樹對(duì)于選取最優(yōu)分裂屬性值的方式是遍歷.(后面的回歸決策樹也是采用的這種方式)
對(duì)于樣本集S,計(jì)算所有屬性的最優(yōu)二分方案,選取其中的最小值,作為樣本集S的最優(yōu)二分方案.

所得到的屬性A及其第i屬性值,即為樣本集S的最優(yōu)分裂屬性以及最優(yōu)分裂屬性值

5.3CART回歸樹–待預(yù)測(cè)結(jié)果為連續(xù)型數(shù)據(jù)

區(qū)別于分類樹,回歸樹的預(yù)測(cè)結(jié)果為連續(xù)型數(shù)據(jù).同時(shí),區(qū)別于分類樹選取Gain_Gini為評(píng)價(jià)分裂屬性的指標(biāo),回歸樹選取Gain_σ為評(píng)價(jià)分裂屬性的指標(biāo).選擇具有最小Gain_σ的屬性及其屬性值,作為最優(yōu)分裂屬性以及最優(yōu)分裂屬性值.Gain_σ值越小,說明二分之后的子樣本集的”差異性”越小,說明選擇該屬性(值)作為分裂屬性(值)的效果越好.
針對(duì)含有連續(xù)型預(yù)測(cè)結(jié)果的樣本集S(理解成一個(gè)子節(jié)點(diǎn)),總方差計(jì)算如下:

其中,μ表示樣本集S(理解成一個(gè)子節(jié)點(diǎn))中預(yù)測(cè)結(jié)果(預(yù)測(cè)結(jié)果就是當(dāng)前子節(jié)點(diǎn)中所有樣本實(shí)際值的均值),yk表示第k個(gè)樣本預(yù)測(cè)結(jié)果
對(duì)于含有N個(gè)樣本的樣本集S,根據(jù)屬性A的第i個(gè)屬性值,將數(shù)據(jù)集S劃分為兩部分,則劃分成兩部分之后,Gain_σ計(jì)算如下:

對(duì)于屬性A,分別計(jì)算任意屬性值將數(shù)據(jù)集劃分成兩部分之后Gain_σ,選取其中的最小值,作為屬性A得到的最優(yōu)二分方案:

對(duì)于數(shù)據(jù)集S,計(jì)算所有屬性的最優(yōu)二分方案,選取其中的最小值,作為樣本集S的最優(yōu)二分方案:

所得到的屬性A及其第i屬性值,即為樣本集S的最優(yōu)分裂屬性以及最優(yōu)分裂屬性值.感覺CART分類樹與回歸樹的區(qū)別就在分裂的評(píng)價(jià)指標(biāo),一個(gè)是Gain_Gini/Gain_σ

5.4CART回歸樹示例

圖1,圖2其實(shí)描述是都是屬性j的Gain_σ.區(qū)別在于圖2計(jì)算的是將數(shù)據(jù)集S用最優(yōu)分裂屬性值s劃分為R1(j,s),R2(j,s)兩個(gè)子樣本集之后計(jì)算的Gain_σ.所以圖2是Gain_σ更為詳細(xì)的定義.c1,c2分別為R1,R2子樣本集中所有l(wèi)abel的均值.

N1,N2為子樣本集中樣本的個(gè)數(shù)
具體示例:
訓(xùn)練數(shù)據(jù)如下表,屬性x的取值范圍[0.5,10.5],y的取值范圍[5.0,10.0]學(xué)習(xí)這個(gè)回歸問題的最小二叉回歸樹

求解訓(xùn)練數(shù)據(jù)的切分點(diǎn)s

容易求得在R1,R2內(nèi)部使得平方損失誤差達(dá)到最小值的c1,c2為:

求訓(xùn)練數(shù)據(jù)的切分點(diǎn),根據(jù)所給數(shù)據(jù),考慮如下切分點(diǎn):
1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5
對(duì)各切分點(diǎn),不難求出相應(yīng)的R1,R2,c1,c2及
例如:當(dāng)s=1.5時(shí),R1={1},R2={2,3…10},c1=5.56,c2=7.50
現(xiàn)將s及m(s)的計(jì)算結(jié)果列表如下:
由上表知,當(dāng)x=6.5的時(shí)候達(dá)到最小值,此時(shí)R1={1,2…6},R2={7,8,9,10},c1=6.24,c2=8.91,所以回歸樹T1(x)為:


所以用的是均值作為預(yù)測(cè)結(jié)果

5.5 CART樹與GBDT的區(qū)別

CART:樹的根節(jié)點(diǎn)分成2支后,在分別在這2支上做分支,以此遞推,最終生成一顆完整的決策樹;后續(xù)再剪枝等;
GBDT:獲得一顆二叉樹后,利用殘差,再在完整的數(shù)據(jù)集上生成一顆二叉樹,最終將多顆二叉樹加權(quán)累加組成一個(gè)最終的函數(shù)
下面將用上述數(shù)據(jù)集詳解GBDT的過程:
用f1(x)擬合訓(xùn)練數(shù)據(jù)的殘差見下表,表中r2i=yi-f1(xi),i=1,2…10 ,r2=∑r2i,表示為第二顆決策樹要擬合的殘差.
第二步求T2(x)方法與T1(x)一樣,只是擬合的數(shù)據(jù)是上表的殘差,可以得到:


繼續(xù)求得:

可以用擬合訓(xùn)練數(shù)據(jù)的平方損失等來作為結(jié)束條件.此時(shí)

假設(shè)此時(shí)已經(jīng)滿足誤差要求,那么f(x)=f6(x)即為所求回歸樹

6 sklearn庫的應(yīng)用

此處代碼都是用的jupyter lab
這玩意代碼上傳屬實(shí)麻煩.留意一下別人代碼是怎么排版的

總結(jié)

以上是生活随笔為你收集整理的决策树基本原理与sklearn应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。