數據挖掘 決策樹系列

決策樹系列（一）一一基礎知識回顧與總結

1■.決策樹的定義

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

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

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

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

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

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

圖1.1樹的結構示意圖

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

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

2.決策樹如何做決策

從一個分類例子說起：

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

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

過對下面的數據進行分析建立一個預測用戶貸款一下的模型。

表2.1銀行用戶信息表

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

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

工人365500高中否

工人422800初中是

白領453300小學是

白領2510000本科是

白領328000碩士否

白領2813000博士是

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

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

工人333000高中否

工人484200小學否

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

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

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

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

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

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

決策樹用樹結構實現上述的判斷流程，如圖2.1所示:

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

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

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

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

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

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

結論。

工人

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

年齡

第三步：根據客戶的學歷進行選擇，選擇"小學”這一分支，得出該客戶無貸款意向的結論。

有貸款意向無貸款意向

3.決策樹的構建

那么問題就來了，如何構建如圖2.1所示一棵決策樹呢？決策樹的構建是數據逐步分

裂的過程，構建的步驟如下：

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

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

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

步驟4；否則，進入步驟2；

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

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

（1）數據如何分割

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

（3）什么時候停止分裂

3.1數據分割

假如我們已經選擇了一個分裂的屬性，那怎樣對數據進行分裂呢？

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

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

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

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

例：

表3.1分類信息表

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

白領30否

工人40否

工人20否

學生15否

學生18是

白領42是

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

對原始的數據進行分割，如下表所示：

表3.2屬性1數據分割表

取值貸款不貸款

白領11

工人02

學生11

表3.2可以表示成如下的決策樹結構:

貸款：4

職業(yè)不貸款：2

貸款：1

不貸款：1

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

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

表3.3屬性2數據分害表

區(qū)間貸款不貸款

[0,20]12

(20,40]02

(40,—]10

表3.3可以表示成如下的決策樹結構:

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

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

3.2分裂屬性的選擇

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

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

樣才算是最優(yōu)的分裂結果？最理想的情況當然是能找到一個屬性剛好能夠將不同類別分開，

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

以下圖為例：

圖3.1按屬性1進行分裂圖3.2按屬性2進行分裂

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

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

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

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

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

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

(1)信息增益

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

表示為：

n

Info_Gain—Gain-工Gain,

J=I

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

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

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

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

a)燧

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

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

n

Entropy=p.■log(py)

2=1

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

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

b）基尼值

基尼值計算公式如下:

n

Gini=1-Zp：

2=1

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

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

例：

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

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

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

類1:20

類2:14

圖3.3根據屬性1分裂圖3.4根據屬性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)信息增益率

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

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

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

InGam

Info_Ratio=f°-

Instrinsichifo

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

增益，其計算公式為：

Instrinsiclnfo=

A

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

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

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

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

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

類1:20

類2:14

圖3.3根據屬性1分裂圖3.4根據屬性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停止分裂的條件

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

下一個數據點時自動結束分裂，但這種情況下樹過于復雜，而且預測的經度不高。一般情況

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

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

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

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

再做分裂容易強化噪聲數據的作用；二是降低樹生長的復雜性。提前結束分裂一定程度上有

利于降低過擬合的影響。

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

由上述可知，燧和基尼值的大小表示數據的復雜程度，當婚或者基尼值過小時，表示

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

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

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

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

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

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

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

3.4決策樹的構建方法

根據決策樹的輸出結果，決策樹可以分為分類樹和回歸樹，分類樹輸出的結果為具體

的類別，而回歸樹輸出的結果為一個確定的數值。

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

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

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

的算法。

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

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

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

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

決策樹系列(二)剪枝

什么是剪枝？

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

為甚么要剪枝？

決策樹是充分考慮了所有的數據點而生成的復雜樹，有可能出現過擬合的情況，決策

樹越復雜，過擬合的程度會越高。

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

證所有的訓練數據都能準確分類，但是很有可能得到高的預測誤差，原因是將訓練數據中所

有的噪聲數據都"準確劃分”了，強化了噪聲數據的作用。

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

出現的概率。

怎樣剪枝？

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

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

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

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

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

降，就可以認為該子樹是可以修剪的。

REP剪枝需要用新的數據集，原因是如果用舊的數據集，不可能出現分裂后的錯誤率

比分裂前錯誤率要高的情況。由于使用新的數據集沒有參與決策樹的構建，能夠降低訓練數

據的影響，降低過擬合的程度，提高預測的準確率。

(2)PEP一悲觀剪枝

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

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

一致，此時要進行剪枝。

進行剪枝必須滿足的條件：

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

其中：

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

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

兩者的計算公式如下：

石.=￡3+。§

%=2+05

m

令子樹誤差的經度滿足二項分布，根據二項分布的性質，石必，“=3（4+°§,

________瓦加

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

差石W=e+0.5。

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

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

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

個節(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,所以應該進行剪枝。

（3）CCP一代價復雜度剪枝

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

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

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

可描述如下：

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

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

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

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

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

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

N(T)-1

其中:

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

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

m

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

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

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

算例：

下圖是決策樹A的其中一顆子樹，決策樹的總數據量為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,只要求出其他子樹的表面誤差率增益值就可以對決

策樹進行剪枝.

決策樹系列（三）一一ID3

初識ID3

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

（1）數據是怎么分裂的

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

（3）什么時候停止分裂

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

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

表1原始數據

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

晴2550春天晴

陰2148春天陰

陰1870春天雨

晴2841夏天晴

雨865冬天陰

晴1843夏天晴

陰2456秋天晴

雨1876秋天陰

雨3161夏天晴

陰643冬天雨

晴1555秋天陰

雨458冬天雨

1.數據分割

對于離散型數據，直接按照離散數據的取值進行分裂，每一個取值對應一個子節(jié)點,

以''當前天氣”為例對數據進行分割，如圖1所示。

%31%1

Hff叫:

112

m:

02m.:1

m:m:m:

圖1按照“今天天氣”屬性進行劃分

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

離散型數據再進行處理。

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

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

間的數據量基本相同，以溫度為例對數據進行分割，如圖2所示。

溫度

252118288182418316154

按溫度的高低進行排序

468151818182124252831

1噴1n

端11z

468151818182124252831lwM:

1防n1

曲z

1^±

和

11

zn

M:^iw:1±

圖2按照“溫度”屬性進行劃分

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

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

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

Info_Gain-Entropy-Z2「Entropy

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

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

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

大的屬性作為分裂屬性。

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

大的屬性進行分裂。

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

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

3344442444444

=0.315

溫度：(數據分割如上圖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.停止分裂的條件

停止分裂的條件已經在決策樹中闡述，這里不再進行闡述。

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

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

再做分裂容易強化噪聲數據的作用；二是降低樹生長的復雜性。提前結束分裂一定程度上有

利于降低過擬合的影響。

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

由上述可知，端和基尼值的大小表示數據的復雜程度，當嫡或者基尼值過小時，表示

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

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

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

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

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

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

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

(1)數據處理

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

列表示分類的標簽。

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

鏈表數組進行存儲，數組的第一個元素表示屬性1的離散值。

staticList<String>[]featurevalues;

那么經過處理后的表1數據可以轉化為如表2所示的數據：

表2初始化后的數據

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

1255011

2214812

2187013

1284121

386532

1184321

2245641

3187642

3316121

264333

1155542

345833

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

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

陰、雨｝。

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

a）節(jié)點類Node

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

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

田ViewCode

b）分裂信息類Splitinfo

該類存儲節(jié)點進行分裂的信息，包括各個子節(jié)點的行坐標、子節(jié)點各個類的數目、該

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

田ViewCode

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

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

其中：

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

nums表示節(jié)點數據對應的行坐標列表；

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

示該屬性可以使用）；

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

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

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

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

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

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

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

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

數據輸入到主方法findBestSplit中，就可以得到最終的結果）

總結

ID3是基本的決策樹構建算法，作為決策樹經典的構建算法，其具有結構簡單、清晰

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

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

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

（3）不能處理缺省值

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

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

如上一篇文章所述，ID3方法主要有幾個缺點：一是采用信息增益進行數據分裂，準

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

三是沒有采用剪枝的策略，決策樹的結構可能會過于復雜，可能會出現過擬合的情況。

C4.5在ID3的基礎上對上述三個方面進行了相應的改進：

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

b)能夠對連續(xù)數據進行處理；

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

擬合的影響。

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

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

,InfoGain

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

Imtrinsiclnfo

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

信息增益，計算公式為：

.n.n

Instnnsiclnfo=->—?log(—)

UNN

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

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

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

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

表1原始數據表

當天天氣溫度濕度日期逛街

晴2550工作日否

晴2148工作日是

晴1870周末是

晴2841周末是

陰865工作日是

陰1843工作日否

陰2456周末是

陰1876周末否

雨3161周末否

雨643周末是

雨1555工作日否

雨458工作日否

以當天天氣為例：

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

當天天氣ARIK季節(jié)明天天氣

Bff25SO工作日K

當天天氣工度日期逛街晴2148工作日

晴2S50工作日S瞪1870是

晴2148工作日1Iff28419^

晴1870周末是

IX2841嘛是

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

明865工作日1

陰865工作日是

陽1843工作日S

陰1843工作日否

陰2456周末是

陰2456嘛是

陽1876卻否

陰1876嘛S

雨3161周末否

雨643穌是

雨1555工作日否

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

雨3161周末

雨643嘛是

雨1555工作日否

雨4S8工作日否

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

,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

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

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

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

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

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

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

當天天氣溫度58日期逡街當天天氣涅度日期出街

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條數據就有N-1個切割點，為了選取最優(yōu)的切割墊，

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

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

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

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

化計算的復雜度，如下圖所示：

當天天氣星度漫度日期酒街當天天氣18灌度日期逐街

否

IX2550工作日否