數(shù)據(jù)挖掘 決策樹系列

決策樹系列（一）一一基礎(chǔ)知識回顧與總結(jié)

1■.決策樹的定義

樹想必大家都會比較熟悉，是由節(jié)點和邊兩種元素組成的結(jié)構(gòu)。理解樹，就需要理解

幾個關(guān)鍵詞：根節(jié)點、父節(jié)點、子節(jié)點和葉子節(jié)點。

父節(jié)點和子節(jié)點是相對的，說白了子節(jié)點由父節(jié)點根據(jù)某一規(guī)則分裂而來，然后子節(jié)

點作為新的父親節(jié)點繼續(xù)分裂，直至不能分裂為止。而根節(jié)點是沒有父節(jié)點的節(jié)點，即初始

分裂節(jié)點，葉子節(jié)點是沒有子節(jié)點的節(jié)點，如下圖所示：

葉子節(jié)點葉子節(jié)點葉子節(jié)點

圖1.1樹的結(jié)構(gòu)示意圖

決策樹利用如上圖所示的樹結(jié)構(gòu)進(jìn)行決策，每一個非葉子節(jié)點是一個判斷條件，每一

個葉子節(jié)點是結(jié)論。從跟節(jié)點開始，經(jīng)過多次判斷得出結(jié)論。

2.決策樹如何做決策

從一個分類例子說起：

銀行希望能夠通過一個人的信息（包括職業(yè)、年齡、收入、學(xué)歷）去判斷他是否有貸

款的意向，從而更有針對性地完成工作。下表是銀行現(xiàn)在能夠掌握的信息，我們的目標(biāo)是通

過對下面的數(shù)據(jù)進(jìn)行分析建立一個預(yù)測用戶貸款一下的模型。

表2.1銀行用戶信息表

職業(yè)年齡收入學(xué)歷是否貸款

自由職業(yè)285000高中是

工人365500高中否

工人422800初中是

白領(lǐng)453300小學(xué)是

白領(lǐng)2510000本科是

白領(lǐng)328000碩士否

白領(lǐng)2813000博士是

自由職業(yè)214000本科否

自由職業(yè)223200小學(xué)否

工人333000高中否

工人484200小學(xué)否

（注：上表中的數(shù)據(jù)都由本人捏造，不具有任何實際的意義）

上邊中有4個客戶的屬性，如何綜合利用這些屬性去判斷用戶的貸款意向？決策樹的

做法是每次選擇一個屬性進(jìn)行判斷，如果不能得出結(jié)論，繼續(xù)選擇其他屬性進(jìn)行判斷，直到

能夠''肯定地"判斷出用戶的類型或者是上述屬性都已經(jīng)使用完畢。比如說我們要判斷一個客

戶的貸款意向，我們可以先根據(jù)客戶的職業(yè)進(jìn)行判斷，如果不能得出結(jié)論，再根據(jù)年齡作判

斷，這樣以此類推，直到可以得出結(jié)論為止。

決策樹用樹結(jié)構(gòu)實現(xiàn)上述的判斷流程，如圖2.1所示:

無貸款意向有貸款意向有貸款意向無貸款意向

圖2.1銀行貸款意向分析決策樹示意圖

通過圖2.1的訓(xùn)練數(shù)據(jù)，我們可以建議圖2.1所示的決策樹，其輸入是用戶的信息，

輸出是用戶的貸款意向。如果要判斷某一客戶是否有貸款的意向，直接根據(jù)用戶的職業(yè)、收

入、年齡以及學(xué)歷就可以分析得出用戶的類型。如某客戶的信息為：（職業(yè)、年齡，收入,

學(xué)歷｝=｛工人、39,1800,小學(xué)）,將信息輸入上述決策樹，可以得到下列的分析步驟和

結(jié)論。

工人

第二步：根據(jù)客戶的年齡進(jìn)行選擇，選擇年齡"<=40"這一分支:

年齡

第三步：根據(jù)客戶的學(xué)歷進(jìn)行選擇，選擇"小學(xué)”這一分支，得出該客戶無貸款意向的結(jié)論。

有貸款意向無貸款意向

3.決策樹的構(gòu)建

那么問題就來了，如何構(gòu)建如圖2.1所示一棵決策樹呢？決策樹的構(gòu)建是數(shù)據(jù)逐步分

裂的過程，構(gòu)建的步驟如下：

步驟L將所有的數(shù)據(jù)看成是一個節(jié)點，進(jìn)入步驟2；

步驟2：從所有的數(shù)據(jù)特征中挑選一個數(shù)據(jù)特征對節(jié)點進(jìn)行分割，進(jìn)入步驟3；

步驟3：生成若干孩子節(jié)點，對每一個孩子節(jié)點進(jìn)行判斷，如果滿足停止分裂的條件，進(jìn)入

步驟4；否則，進(jìn)入步驟2；

步驟4：設(shè)置該節(jié)點是子節(jié)點，其輸出的結(jié)果為該節(jié)點數(shù)量占比最大的類別。

從上述步驟可以看出，決策生成過程中有兩個重要的問題：

（1）數(shù)據(jù)如何分割

（2）如何選擇分裂的屬性

（3）什么時候停止分裂

3.1數(shù)據(jù)分割

假如我們已經(jīng)選擇了一個分裂的屬性，那怎樣對數(shù)據(jù)進(jìn)行分裂呢？

分裂屬性的數(shù)據(jù)類型分為離散型和連續(xù)性兩種情況，對于離散型的數(shù)據(jù)，按照屬性值進(jìn)

行分裂，每個屬性值對應(yīng)一個分裂節(jié)點；對于連續(xù)性屬性，一般性的做法是對數(shù)據(jù)按照該屬

性進(jìn)行排序，再將數(shù)據(jù)分成若干區(qū)間，如［0,10］、［10,20］、［20,30］…，一個區(qū)間對應(yīng)一

個節(jié)點，若數(shù)據(jù)的屬性值落入某一區(qū)間則該數(shù)據(jù)就屬于其對應(yīng)的節(jié)點。

例：

表3.1分類信息表

職業(yè)年齡是否貸款

白領(lǐng)30否

工人40否

工人20否

學(xué)生15否

學(xué)生18是

白領(lǐng)42是

（1）屬性1''職業(yè)''是離散型變量，有三個取值，分別為白領(lǐng)、工人和學(xué)生，根據(jù)三個取值

對原始的數(shù)據(jù)進(jìn)行分割，如下表所示：

表3.2屬性1數(shù)據(jù)分割表

取值貸款不貸款

白領(lǐng)11

工人02

學(xué)生11

表3.2可以表示成如下的決策樹結(jié)構(gòu):

貸款：4

職業(yè)不貸款：2

貸款：1

不貸款：1

(2)屬性2是連續(xù)性變量，這里將數(shù)據(jù)分成三個區(qū)間，分別是［10,20］、［20,30］、［30,40］,

則每一個區(qū)間的分裂結(jié)果如下：

表3.3屬性2數(shù)據(jù)分害表

區(qū)間貸款不貸款

[0,20]12

(20,40]02

(40,—]10

表3.3可以表示成如下的決策樹結(jié)構(gòu):

貸款：1貸款：0貸款：1

不貸款：2不貸款：2不貸款：0

3.2分裂屬性的選擇

我們知道了分裂屬性是如何對數(shù)據(jù)進(jìn)行分割的，那么我們怎樣選擇分裂的屬性呢？

決策樹采用貪婪思想進(jìn)行分裂，即選擇可以得到最優(yōu)分裂結(jié)果的屬性進(jìn)行分裂。那么怎

樣才算是最優(yōu)的分裂結(jié)果？最理想的情況當(dāng)然是能找到一個屬性剛好能夠?qū)⒉煌悇e分開，

但是大多數(shù)情況下分裂很難一步到位，我們希望每一次分裂之后孩子節(jié)點的數(shù)據(jù)盡量“純”,

以下圖為例：

圖3.1按屬性1進(jìn)行分裂圖3.2按屬性2進(jìn)行分裂

從圖3.1和圖3.2可以明顯看出，屬性2分裂后的孩子節(jié)點比屬性1分裂后的孩子節(jié)

點更純：屬性1分裂后每個節(jié)點的兩類的數(shù)量還是相同，跟根節(jié)點的分類結(jié)果相比完全沒

有提高；按照屬性2分裂后每個節(jié)點各類的數(shù)量相差比較大，可以很大概率認(rèn)為第一個孩

子節(jié)點的輸出結(jié)果為類1,第2個孩子節(jié)點的輸出結(jié)果為2。

選擇分裂屬性是要找出能夠使所有孩子節(jié)點數(shù)據(jù)最純的屬性，決策樹使用信息增益或

者信息增益率作為選擇屬性的依據(jù)。

(1)信息增益

用信息增益表示分裂前后跟的數(shù)據(jù)復(fù)雜度和分裂節(jié)點數(shù)據(jù)復(fù)雜度的變化值，計算公式

表示為：

n

Info_Gain—Gain-工Gain,

J=I

其中Gain表示節(jié)點的復(fù)雜度，Gain越高，說明復(fù)雜度越高。信息增益說白了就是分

裂前的數(shù)據(jù)復(fù)雜度減去孩子節(jié)點的數(shù)據(jù)復(fù)雜度的和，信息增益越大，分裂后的復(fù)雜度減小得

越多，分類的效果越明顯。

節(jié)點的復(fù)雜度可以用以下兩種不同的計算方式：

a)燧

嫡描述了數(shù)據(jù)的混亂程度，烯越大，混亂程度越高，也就是純度越低；反之，端越小，

混亂程度越低，純度越高。端的計算公式如下所示：

n

Entropy=p.■log(py)

2=1

其中Pi表示類i的數(shù)量占比。以二分類問題為例，如果兩類的數(shù)量相同，此時分類節(jié)點的

純度最低，焙等于1；如果節(jié)點的數(shù)據(jù)屬于同一類時，此時節(jié)點的純度最高，嫡等于0。

b）基尼值

基尼值計算公式如下:

n

Gini=1-Zp：

2=1

其中Pi表示類i的數(shù)量占比。其同樣以上述端的二分類例子為例，當(dāng)兩類數(shù)量相等時,

基尼值等于0.5；當(dāng)節(jié)點數(shù)據(jù)屬于同一類時，基尼值等于0?；嶂翟酱?，數(shù)據(jù)越不純。

例：

以燧作為節(jié)點復(fù)雜度的統(tǒng)計量，分別求出下面例子的信息增益，圖3.1表示節(jié)點選擇

屬性1進(jìn)行分裂的結(jié)果，圖3.2表示節(jié)點選擇屬性2進(jìn)行分裂的結(jié)果，通過計算兩個屬性

分裂后的信息增益，選擇最優(yōu)的分裂屬性。

類1:20

類2:14

圖3.3根據(jù)屬性1分裂圖3.4根據(jù)屬性2分裂

屬性1：

Info.=Entropy-￡Entropy.=

162828

,1°g(28T16)+?log()=>Entropy

28+1628+1628+16

44

-(上?log(———)+-?log(------.)AEntropvt

14+414+414+414+4

14?log(141212

-()+-?-l--o-g-(---------)=>Entropv2

14+1214+1214+1214+12

=0.81

屬性2：

Info2=Entropy-Entropy.=

2=1

28

28T16-1°g（28T16）+-1°g（28T16）=>Entropy

28+16

89.9

-（■-1°g（8T2）+—=—?log（—=—）=>Entropy!

8+28+28+2

（2020）

1g（）

一（20+14?log（20+14）20Tl4-°20T14=>Entropy2

=0.75

由于＞Info2,所以屬性i與屬性2相比是更優(yōu)的分裂屬性，故選擇屬性1作

為分裂的屬性。

(2)信息增益率

使用信息增益作為選擇分裂的條件有一個不可避免的缺點：傾向選擇分支比較多的屬

性進(jìn)行分裂。為了解決這個問題，引入了信息增益率這個概念。信息增益率是在信息增益的

基礎(chǔ)上除以分裂節(jié)點數(shù)據(jù)量的信息增益(聽起來很拗口)，其計算公式如下：

InGam

Info_Ratio=f°-

Instrinsichifo

其中Info-Galn表示信息增益，成協(xié),表示分裂子節(jié)點數(shù)據(jù)量的信息

增益，其計算公式為：

Instrinsiclnfo=

A

其中m表示子節(jié)點的數(shù)量，A才表示第i個子節(jié)點的數(shù)據(jù)量，N表示父節(jié)點數(shù)據(jù)量，說白了，

其實/mmnszc/g是分裂節(jié)點的琉如果節(jié)點的數(shù)據(jù)鏈越接近，/何"4硫,越大，

如果子節(jié)點越大，加壯族越大，而/硫-就會越小，能夠降低節(jié)點分裂時

選擇子節(jié)點多的分裂屬性的傾向性。信息增益率越高，說明分裂的效果越好。

還是信息增益中提及的例子為例：

類1:20

類2:14

圖3.3根據(jù)屬性1分裂圖3.4根據(jù)屬性2分裂

屬性1的信息增益率:

Info_Gain.=0.81

26i/26

IntrinsicInfo.=1g()4----------log(---------

,°18T2618+2618+26

=0.97

_?.Info_Gain...

Irnfo_Ratio.=-----------------l=0.o84

Intrinsiclnfo.

屬性2的信息增益率:

Info_Gain2=0.75

10

T+?F(

Intrinsi?cl1nfo.=-(---------?liog(-/---1--°---.\)+----3-4----liog(，---3--4---)、)、

'10+3410+3410+3410+34

=0.77

-.Info_Gai%八

Irnfo_RDatio=---------=-----±-=0.97

2'Intrinsic工nf%

Info_Ratio.>Info_Ratio,

由于一'一，故選擇屬性2作為分裂的屬性。

3.3停止分裂的條件

決策樹不可能不限制地生長，總有停止分裂的時候，最極端的情況是當(dāng)節(jié)點分裂到只剩

下一個數(shù)據(jù)點時自動結(jié)束分裂，但這種情況下樹過于復(fù)雜，而且預(yù)測的經(jīng)度不高。一般情況

下為了降低決策樹復(fù)雜度和提高預(yù)測的經(jīng)度，會適當(dāng)提前終止節(jié)點的分裂。

以下是決策樹節(jié)點停止分裂的一般性條件：

(1)最小節(jié)點數(shù)

當(dāng)節(jié)點的數(shù)據(jù)量小于一個指定的數(shù)量時，不繼續(xù)分裂。兩個原因：一是數(shù)據(jù)量較少時，

再做分裂容易強(qiáng)化噪聲數(shù)據(jù)的作用；二是降低樹生長的復(fù)雜性。提前結(jié)束分裂一定程度上有

利于降低過擬合的影響。

(2)焙或者基尼值小于閥值。

由上述可知，燧和基尼值的大小表示數(shù)據(jù)的復(fù)雜程度，當(dāng)婚或者基尼值過小時，表示

數(shù)據(jù)的純度比較大，如果焙或者基尼值小于一定程度數(shù)，節(jié)點停止分裂。

(3)決策樹的深度達(dá)到指定的條件

節(jié)點的深度可以理解為節(jié)點與決策樹跟節(jié)點的距離，如根節(jié)點的子節(jié)點的深度為1，因

為這些節(jié)點與跟節(jié)點的距離為1，子節(jié)點的深度要比父節(jié)點的深度大1。決策樹的深度是所

有葉子節(jié)點的最大深度，當(dāng)深度到達(dá)指定的上限大小時，停止分裂。

(4)所有特征已經(jīng)使用完畢，不能繼續(xù)進(jìn)行分裂。

被動式停止分裂的條件，當(dāng)已經(jīng)沒有可分的屬性時，直接將當(dāng)前節(jié)點設(shè)置為葉子節(jié)點。

3.4決策樹的構(gòu)建方法

根據(jù)決策樹的輸出結(jié)果，決策樹可以分為分類樹和回歸樹，分類樹輸出的結(jié)果為具體

的類別，而回歸樹輸出的結(jié)果為一個確定的數(shù)值。

決策樹的構(gòu)建算法主要有ID3、C4.5、CART三種，其中ID3和C4.5是分類樹，CART

是分類回歸樹，將在本系列的山史、C4.5和CART中分別講述。

其中ID3是決策樹最基本的構(gòu)建算法，而C4.5和CART是在ID3的基礎(chǔ)上進(jìn)行優(yōu)化

的算法。

4.決策樹的優(yōu)化

一棵過于復(fù)雜的決策樹很可能出現(xiàn)過擬合的情況，如果完全按照3中生成一個完整的

決策樹可能會出現(xiàn)預(yù)測不準(zhǔn)確的情況,因此需要對決策樹進(jìn)行優(yōu)化，優(yōu)化的方法主要有兩種，

一是剪枝，二是組合樹，將在本系列的剪枝和組合樹中分別講述。

決策樹系列(二)剪枝

什么是剪枝？

剪枝是指將一顆子樹的子節(jié)點全部刪掉，根節(jié)點作為葉子節(jié)點，以下圖為例:

為甚么要剪枝？

決策樹是充分考慮了所有的數(shù)據(jù)點而生成的復(fù)雜樹，有可能出現(xiàn)過擬合的情況，決策

樹越復(fù)雜，過擬合的程度會越高。

考慮極端的情況，如果我們令所有的葉子節(jié)點都只含有一個數(shù)據(jù)點，那么我們能夠保

證所有的訓(xùn)練數(shù)據(jù)都能準(zhǔn)確分類，但是很有可能得到高的預(yù)測誤差，原因是將訓(xùn)練數(shù)據(jù)中所

有的噪聲數(shù)據(jù)都"準(zhǔn)確劃分”了，強(qiáng)化了噪聲數(shù)據(jù)的作用。

剪枝修剪分裂前后分類誤差相差不大的子樹，能夠降低決策樹的復(fù)雜度，降低過擬合

出現(xiàn)的概率。

怎樣剪枝？

兩種方案：先剪枝和后剪枝

先剪枝說白了就是提前結(jié)束決策樹的增長，跟上述決策樹停止生長的方法一樣。

后剪枝是指在決策樹生長完成之后再進(jìn)行剪枝的過程。這里介紹三種后剪枝方案：

(1)REP一錯誤率降低剪枝

顧名思義，該剪枝方法是根據(jù)錯誤率進(jìn)行剪枝，如果一棵子樹修剪前后錯誤率沒有下

降，就可以認(rèn)為該子樹是可以修剪的。

REP剪枝需要用新的數(shù)據(jù)集，原因是如果用舊的數(shù)據(jù)集，不可能出現(xiàn)分裂后的錯誤率

比分裂前錯誤率要高的情況。由于使用新的數(shù)據(jù)集沒有參與決策樹的構(gòu)建，能夠降低訓(xùn)練數(shù)

據(jù)的影響，降低過擬合的程度，提高預(yù)測的準(zhǔn)確率。

(2)PEP一悲觀剪枝

悲觀剪枝認(rèn)為如果決策樹的精度在剪枝前后沒有影響的話，則進(jìn)行剪枝。怎樣才算是

沒有影響？如果剪枝后的誤差小于剪枝前經(jīng)度的上限，則說明剪枝后的效果與剪枝前的效果

一致，此時要進(jìn)行剪枝。

進(jìn)行剪枝必須滿足的條件：

石工如“-+5（邑%”）

其中：

E即表示剪枝前子樹的誤差；

表示剪枝后節(jié)點的誤差；

兩者的計算公式如下：

石.=￡3+?！?/p>

%=2+05

m

令子樹誤差的經(jīng)度滿足二項分布，根據(jù)二項分布的性質(zhì)，石必，“=3（4+°§,

________瓦加

S（耳s?）=J"pQ-p），其中0一N,N為子樹的數(shù)據(jù)量；同樣，葉子節(jié)點的誤

差石W=e+0.5。

上述公式中，0.5表示修正因子。由于子節(jié)點是父節(jié)點進(jìn)行分裂的結(jié)果，從理論上講，

子節(jié)點的分類效果總比父節(jié)點好，分類的誤差更小，如果單純通過比較子節(jié)點和父節(jié)點的誤

差進(jìn)行剪枝就完全沒有意義了，因此對節(jié)點的誤差計算方法進(jìn)行修正。修正的方法是給每一

個節(jié)點都加上誤差修正因子0.5,在計算誤差的時候，子節(jié)點由于加上了誤差修正因子，就

無法保證總誤差低于父節(jié)點。

算例:

m

==2>+O-5)=(1+O.5)+(4+O.5)+Q+O.5)=7.5

1-1

S(ES3)==J7.5(l-^=2.09

E?=e+0.5=8.5

由于心如《＜%+s（4G,所以應(yīng)該進(jìn)行剪枝。

（3）CCP一代價復(fù)雜度剪枝

代價復(fù)雜度選擇節(jié)點表面誤差率增益值最小的非葉子節(jié)點，刪除該非葉子節(jié)點的左右

子節(jié)點，若有多個非葉子節(jié)點的表面誤差率增益值相同小，則選擇非葉子節(jié)點中子節(jié)點數(shù)最

多的非葉子節(jié)點進(jìn)行剪枝。

可描述如下：

令決策樹的非葉子節(jié)點為｛4石，4,……。

a）計算所有非葉子節(jié)點的表面誤差率增益值

b）選擇表面誤差率增益值最小的非葉子節(jié)點（若多個非葉子節(jié)點具有相同小的表面

誤差率增益值，選擇節(jié)點數(shù)最多的非葉子節(jié)點）。

O對選中的非葉子節(jié)點進(jìn)行剪枝

表面誤差率增益值的計算公式:

N(T)-1

其中:

即）表示葉子節(jié)點的誤差代價，和）=頂了（”，心為節(jié)點的錯誤率，P（）為

節(jié)點數(shù)據(jù)量的占比；

m

火⑶法示子樹的誤差代價，""一斗S’⑺，力）：為子節(jié)點i的錯誤率，Pi⑺表

示節(jié)點i的數(shù)據(jù)節(jié)點占比；

-"（刀:表示子樹節(jié)點個數(shù)。

算例：

下圖是決策樹A的其中一顆子樹，決策樹的總數(shù)據(jù)量為40。

該子樹的表面誤差率增益值可以計算如下：

即）=土竺」

18405

m1.349166

（）=2.p；⑴=----+------F

R'T'T彳（。340940-6-4-0=一4C

1_6

^)-7?(D_5_40_1

(JL=-----------------------=--------------=-----

N(T>-13-140

求出該子樹的表面錯誤覆蓋率為1/40,只要求出其他子樹的表面誤差率增益值就可以對決

策樹進(jìn)行剪枝.

決策樹系列（三）一一ID3

初識ID3

回顧決策樹的基本知識，其構(gòu)建過程主要有下述三個重要的問題:

（1）數(shù)據(jù)是怎么分裂的

（2）如何選擇分類的屬性

（3）什么時候停止分裂

從上述三個問題出發(fā)，以實際的例子對ID3算法進(jìn)行闡述。

例：通過當(dāng)天的天氣、溫度、濕度和季節(jié)預(yù)測明天的天氣

表1原始數(shù)據(jù)

當(dāng)天天氣溫度濕度季節(jié)明天天氣

晴2550春天晴

陰2148春天陰

陰1870春天雨

晴2841夏天晴

雨865冬天陰

晴1843夏天晴

陰2456秋天晴

雨1876秋天陰

雨3161夏天晴

陰643冬天雨

晴1555秋天陰

雨458冬天雨

1.數(shù)據(jù)分割

對于離散型數(shù)據(jù)，直接按照離散數(shù)據(jù)的取值進(jìn)行分裂，每一個取值對應(yīng)一個子節(jié)點,

以''當(dāng)前天氣”為例對數(shù)據(jù)進(jìn)行分割，如圖1所示。

%31%1

Hff叫:

112

m:

02m.:1

m:m:m:

圖1按照“今天天氣”屬性進(jìn)行劃分

對于連續(xù)型數(shù)據(jù)，ID3原本是沒有處理能力的，只有通過離散化將連續(xù)性數(shù)據(jù)轉(zhuǎn)化成

離散型數(shù)據(jù)再進(jìn)行處理。

連續(xù)數(shù)據(jù)離散化是另外一個課題，本文不深入闡述，這里直接采用等距離數(shù)據(jù)劃分的

李算話方法。該方法先對數(shù)據(jù)進(jìn)行排序，然后將連續(xù)型數(shù)據(jù)劃分為多個區(qū)間，并使每一個區(qū)

間的數(shù)據(jù)量基本相同，以溫度為例對數(shù)據(jù)進(jìn)行分割，如圖2所示。

溫度

252118288182418316154

按溫度的高低進(jìn)行排序

468151818182124252831

1噴1n

端11z

468151818182124252831lwM:

1防n1

曲z

1^±

和

11

zn

M:^iw:1±

圖2按照“溫度”屬性進(jìn)行劃分

2.選擇最優(yōu)分裂屬性

ID3采用信息增益作為選擇最優(yōu)的分裂屬性的方法,選擇焙作為衡量節(jié)點純度的標(biāo)準(zhǔn)，

信息增益的計算公式如下：

Info_Gain-Entropy-Z2「Entropy

其中，少表示父節(jié)點的嫡；石〃〃?爾匕表示節(jié)點i的帽，嫡越大，節(jié)點的

信息量越多，越不純；夕表示子節(jié)點i的數(shù)據(jù)量與父節(jié)點數(shù)據(jù)量之比。力g_Ga為越

大，表示分裂后的端越小，子節(jié)點變得越純，分類的效果越好，因此選擇I?於_Gain最

大的屬性作為分裂屬性。

對上述的例子的跟節(jié)點進(jìn)行分裂，分別計算每一個屬性的信息增益，選擇信息增益最

大的屬性進(jìn)行分裂。

天氣屬性：(數(shù)據(jù)分割如上圖1所示)

Inf°_Gain、=—3-?log(^)+(：?log(：)+[?log(：))-2二?(：?log(J)+:?log(J)+§-log(y))

3344442444444

=0.315

溫度：(數(shù)據(jù)分割如上圖2所示)

Z^_G^2=-3.-4og(-)+3.-.(-.log(-)+-.log(-)+-.log(-))

=0.084

季節(jié):

端

11喻1

IW:叫

叫202

孫

020

M:ffi:m:

Info_GainA--3---log(i)+4--(2-(--log(i)+—?

333333

=0.973

由于Info_Gai%最大，所以選擇屬性''季節(jié)"作為根節(jié)點的分裂屬性。

3.停止分裂的條件

停止分裂的條件已經(jīng)在決策樹中闡述，這里不再進(jìn)行闡述。

(1)最小節(jié)點數(shù)

當(dāng)節(jié)點的數(shù)據(jù)量小于一個指定的數(shù)量時，不繼續(xù)分裂。兩個原因：一是數(shù)據(jù)量較少時，

再做分裂容易強(qiáng)化噪聲數(shù)據(jù)的作用；二是降低樹生長的復(fù)雜性。提前結(jié)束分裂一定程度上有

利于降低過擬合的影響。

(2)端或者基尼值小于閥值。

由上述可知，端和基尼值的大小表示數(shù)據(jù)的復(fù)雜程度，當(dāng)?shù)栈蛘呋嶂颠^小時，表示

數(shù)據(jù)的純度比較大，如果嫡或者基尼值小于一定程度時，節(jié)點停止分裂。

(3)決策樹的深度達(dá)到指定的條件

節(jié)點的深度可以理解為節(jié)點與決策樹跟節(jié)點的距離，如根節(jié)點的子節(jié)點的深度為1,因

為這些節(jié)點與跟節(jié)點的距離為L子節(jié)點的深度要比父節(jié)點的深度大1。決策樹的深度是所

有葉子節(jié)點的最大深度，當(dāng)深度到達(dá)指定的上限大小時，停止分裂。

(4)所有特征已經(jīng)使用完畢，不能繼續(xù)進(jìn)行分裂。

被動式停止分裂的條件，當(dāng)已經(jīng)沒有可分的屬性時，直接將當(dāng)前節(jié)點設(shè)置為葉子節(jié)點。

(1)數(shù)據(jù)處理

用二維數(shù)組存儲原始的數(shù)據(jù)，每一行表示一條記錄，前n-1列表示數(shù)據(jù)的屬性，第n

列表示分類的標(biāo)簽。

為了方便后面的處理，對離散屬性進(jìn)行數(shù)字化處理，將離散值表示成數(shù)字，并用一個

鏈表數(shù)組進(jìn)行存儲，數(shù)組的第一個元素表示屬性1的離散值。

staticList<String>[]featurevalues;

那么經(jīng)過處理后的表1數(shù)據(jù)可以轉(zhuǎn)化為如表2所示的數(shù)據(jù)：

表2初始化后的數(shù)據(jù)

當(dāng)天天氣溫度濕度季節(jié)明天天氣

1255011

2214812

2187013

1284121

386532

1184321

2245641

3187642

3316121

264333

1155542

345833

其中，對于當(dāng)天天氣屬性，數(shù)字｛1,2,3｝分別表示｛晴，陰，雨｝;對于季節(jié)屬性

｛1,2,3,4）分別表示｛春天、夏天、冬天、秋天）;對于明天天氣｛1,2,3｝分別表示｛晴、

陰、雨｝。

（2）兩個類：節(jié)點類和分裂信息

a）節(jié)點類Node

該類存儲了節(jié)點的信息，包括節(jié)點的數(shù)據(jù)量、節(jié)點選擇的分裂屬性、節(jié)點輸出類、子

節(jié)點的個數(shù)、子節(jié)點的分類誤差等。

田ViewCode

b）分裂信息類Splitinfo

該類存儲節(jié)點進(jìn)行分裂的信息，包括各個子節(jié)點的行坐標(biāo)、子節(jié)點各個類的數(shù)目、該

節(jié)點分裂的屬性、屬性的類型等。

田ViewCode

（3）節(jié)點分裂方法findBestSplit（Nodenode,List<int>numszint[]isllsed）,

該方法對節(jié)點進(jìn)行分裂，返回值Node

其中：

node表示即將進(jìn)行分裂的節(jié)點；

nums表示節(jié)點數(shù)據(jù)對應(yīng)的行坐標(biāo)列表；

isUsed表示到該節(jié)點位置所有屬性的使用情況（1：表示該屬性不能再次使用，0：表

示該屬性可以使用）；

findBestSplit主要有以下幾個組成部分：

1）節(jié)點分裂停止的判定

判斷節(jié)點是否需要繼續(xù)分裂，分裂判斷條件如上文所述。源代碼如下：

2）尋找最優(yōu)的分裂屬性

尋找最優(yōu)的分裂屬性需要計算每一個分裂屬性分裂后的信息增益，計算公式上文已給出.

3）進(jìn)行分裂，同時子節(jié)點也執(zhí)行相同的分類步驟

其實就是遞歸的過程，對每一個子節(jié)點執(zhí)行findBestSplit方法進(jìn)行分裂。

（注：上述代碼只是ID3的核心代碼，數(shù)據(jù)預(yù)處理的代碼并沒有給出，只要將預(yù)處理后的

數(shù)據(jù)輸入到主方法findBestSplit中，就可以得到最終的結(jié)果）

總結(jié)

ID3是基本的決策樹構(gòu)建算法，作為決策樹經(jīng)典的構(gòu)建算法，其具有結(jié)構(gòu)簡單、清晰

易懂的特點。雖然ID3比較靈活方便，但是有以下幾個缺點：

（1）采用信息增益進(jìn)行分裂，分裂的精確度可能沒有采用信息增益率進(jìn)行分裂高

（2）不能處理連續(xù)型數(shù)據(jù)，只能通過離散化將連續(xù)性數(shù)據(jù)轉(zhuǎn)化為離散型數(shù)據(jù)

（3）不能處理缺省值

（4）沒有對決策樹進(jìn)行剪枝處理，很可能會出現(xiàn)過擬合的問題

決策樹系列（四）一一C4.5

如上一篇文章所述，ID3方法主要有幾個缺點：一是采用信息增益進(jìn)行數(shù)據(jù)分裂，準(zhǔn)

確性不如信息增益率；二是不能對連續(xù)數(shù)據(jù)進(jìn)行處理，只能通過連續(xù)數(shù)據(jù)離散化進(jìn)行處理:

三是沒有采用剪枝的策略，決策樹的結(jié)構(gòu)可能會過于復(fù)雜，可能會出現(xiàn)過擬合的情況。

C4.5在ID3的基礎(chǔ)上對上述三個方面進(jìn)行了相應(yīng)的改進(jìn)：

a)C4.5對節(jié)點進(jìn)行分裂時采用信息增益率作為分裂的依據(jù)；

b)能夠?qū)B續(xù)數(shù)據(jù)進(jìn)行處理；

c)C4.5采用剪枝的策略，對完全生長的決策樹進(jìn)行剪枝處理，一定程度上降低過

擬合的影響。

工.采用信息增益率作為分裂的依據(jù)

信息增益率的計算公式為：

,InfoGain

InfoRatio=--~=-------

Imtrinsiclnfo

其中Info_Gai”表示信息增益，/您“歷做表示分裂子節(jié)點數(shù)據(jù)量的

信息增益，計算公式為：

.n.n

Instnnsiclnfo=->—?log(—)

UNN

其中m表示節(jié)點的數(shù)量，Ni表示第i個節(jié)點的數(shù)據(jù)量，N表示父親節(jié)點的數(shù)據(jù)量，

說白了，^trtnsiclnfo-其實是分裂節(jié)點的稀

信息增益率越大，說明分裂的效果越好。

以一個實際的例子說明C4.5如何通過信息增益率選擇分裂的屬性:

表1原始數(shù)據(jù)表

當(dāng)天天氣溫度濕度日期逛街

晴2550工作日否

晴2148工作日是

晴1870周末是

晴2841周末是

陰865工作日是

陰1843工作日否

陰2456周末是

陰1876周末否

雨3161周末否

雨643周末是

雨1555工作日否

雨458工作日否

以當(dāng)天天氣為例：

一共有三個屬性值，晴、陰、雨，一共分裂成三個子節(jié)點。

當(dāng)天天氣ARIK季節(jié)明天天氣

Bff25SO工作日K

當(dāng)天天氣工度日期逛街晴2148工作日

晴2S50工作日S瞪1870是

晴2148工作日1Iff28419^

晴1870周末是

IX2841嘛是

當(dāng)天天氣1度18季節(jié)明天天氣

明865工作日1

陰865工作日是

陽1843工作日S

陰1843工作日否

陰2456周末是

陰2456嘛是

陽1876卻否

陰1876嘛S

雨3161周末否

雨643穌是

雨1555工作日否

雨458工作日S當(dāng)天天氣.8?季節(jié)朗天天氣

雨3161周末

雨643嘛是

雨1555工作日否

雨4S8工作日否

根據(jù)上述公式，可以計算信息增益率如下:

,u6,66,6、

IrgoGain=Entropy-gEntropy\=-(-log—+--log—)-

g.(一(："ogg)+:?log(：)+1，log(j)+1，log(j)+j，logg)+:，log(：)))=0.519

Instrinsiclnfo=-V爺?log(專)=-g-log(；)+1?log(^)+g-log(g))=1.09

,InfoGain0.481

Irfo_Ratio=-----=------=------=0.44

Instrinsiclnfb1.09

所以使用天氣屬性進(jìn)行分裂可以得到信息增益率0.44。

2.對連續(xù)型屬性進(jìn)行處理

C4.5處理離散型屬性的方式與ID3一致，新增對連續(xù)型屬性的處理。處理方式是先

根據(jù)連續(xù)型屬性進(jìn)行排序，然后采用一刀切的方式將數(shù)據(jù)砍成兩半。

那么如何選擇切割點呢？很簡單.，直接計算每一個切割點切割后的信息增益，然后選擇使分

裂效果最優(yōu)的切割點。以溫度為例：

當(dāng)天天氣溫度58日期逡街當(dāng)天天氣涅度日期出街

2550工作日否雨458工作日否

情2148工作日是雨643周末是

IX1870魅?明865工作日

II2841嘛是雨1$55工作日否

明865工作日是晴1870聊1

陰1843工作日否1843工作日3

陰2456取?明1876周東

用1876周末否明1876國：否

雨3161琳否晴2148工作日是

雨643麻是明2456周末是

雨1555工作日3II2841穌

雨458工作日S雨3161A麻

從上圖可以看出，理論上來講，N條數(shù)據(jù)就有N-1個切割點，為了選取最優(yōu)的切割墊，

要計算按每一次切割的信息增益，計算量是比較大的，那么有沒有簡化的方法呢？有，注意

到，其實有些切割點是很明顯可以排除的。比如說上圖右側(cè)的第2條和第3條記錄，兩者

的類標(biāo)簽（逛街）都是''是"，如果從這里切割的話，就將兩個本來相同的類分開了，肯定不

會比將他們歸為一類的切分方法好，因此，可以通過去除前后兩個類標(biāo)簽相同的切割點以簡

化計算的復(fù)雜度，如下圖所示：

當(dāng)天天氣星度漫度日期酒街當(dāng)天天氣18灌度日期逐街

否

IX2550工作日否