数据挖掘 决策树系列

决策树系列（一）一一基础知识回顾与总结

1■.决策树的定义

树想必大家都会比较熟悉，是由节点和边两种元素组成的结构。理解树，就需要理解

几个关键词：根节点、父节点、子节点和叶子节点。

父节点和子节点是相对的，说白了子节点由父节点根据某一规则分裂而来，然后子节

点作为新的父亲节点继续分裂，直至不能分裂为止。而根节点是没有父节点的节点，即初始

分裂节点，叶子节点是没有子节点的节点，如下图所示：

叶子节点叶子节点叶子节点

图1.1树的结构示意图

决策树利用如上图所示的树结构进行决策，每一个非叶子节点是一个判断条件，每一

个叶子节点是结论。从跟节点开始，经过多次判断得出结论。

2.决策树如何做决策

从一个分类例子说起：

银行希望能够通过一个人的信息（包括职业、年龄、收入、学历）去判断他是否有贷

款的意向，从而更有针对性地完成工作。下表是银行现在能够掌握的信息，我们的目标是通

过对下面的数据进行分析建立一个预测用户贷款一下的模型。

表2.1银行用户信息表

职业年龄收入学历是否贷款

自由职业285000高中是

工人365500高中否

工人422800初中是

白领453300小学是

白领2510000本科是

白领328000硕士否

白领2813000博士是

自由职业214000本科否

自由职业223200小学否

工人333000高中否

工人484200小学否

（注：上表中的数据都由本人捏造，不具有任何实际的意义）

上边中有4个客户的属性，如何综合利用这些属性去判断用户的贷款意向？决策树的

做法是每次选择一个属性进行判断，如果不能得出结论，继续选择其他属性进行判断，直到

能够''肯定地"判断出用户的类型或者是上述属性都已经使用完毕。比如说我们要判断一个客

户的贷款意向，我们可以先根据客户的职业进行判断，如果不能得出结论，再根据年龄作判

断，这样以此类推，直到可以得出结论为止。

决策树用树结构实现上述的判断流程，如图2.1所示:

无贷款意向有贷款意向有贷款意向无贷款意向

图2.1银行贷款意向分析决策树示意图

通过图2.1的训练数据，我们可以建议图2.1所示的决策树，其输入是用户的信息，

输出是用户的贷款意向。如果要判断某一客户是否有贷款的意向，直接根据用户的职业、收

入、年龄以及学历就可以分析得出用户的类型。如某客户的信息为：（职业、年龄，收入,

学历｝=｛工人、39,1800,小学）,将信息输入上述决策树，可以得到下列的分析步骤和

结论。

工人

第二步：根据客户的年龄进行选择，选择年龄"<=40"这一分支:

年龄

第三步：根据客户的学历进行选择，选择"小学”这一分支，得出该客户无贷款意向的结论。

有贷款意向无贷款意向

3.决策树的构建

那么问题就来了，如何构建如图2.1所示一棵决策树呢？决策树的构建是数据逐步分

裂的过程，构建的步骤如下：

步骤L将所有的数据看成是一个节点，进入步骤2；

步骤2：从所有的数据特征中挑选一个数据特征对节点进行分割，进入步骤3；

步骤3：生成若干孩子节点，对每一个孩子节点进行判断，如果满足停止分裂的条件，进入

步骤4；否则，进入步骤2；

步骤4：设置该节点是子节点，其输出的结果为该节点数量占比最大的类别。

从上述步骤可以看出，决策生成过程中有两个重要的问题：

（1）数据如何分割

（2）如何选择分裂的属性

（3）什么时候停止分裂

3.1数据分割

假如我们已经选择了一个分裂的属性，那怎样对数据进行分裂呢？

分裂属性的数据类型分为离散型和连续性两种情况，对于离散型的数据，按照属性值进

行分裂，每个属性值对应一个分裂节点；对于连续性属性，一般性的做法是对数据按照该属

性进行排序，再将数据分成若干区间，如［0,10］、［10,20］、［20,30］…，一个区间对应一

个节点，若数据的属性值落入某一区间则该数据就属于其对应的节点。

例：

表3.1分类信息表

职业年龄是否贷款

白领30否

工人40否

工人20否

学生15否

学生18是

白领42是

（1）属性1''职业''是离散型变量，有三个取值，分别为白领、工人和学生，根据三个取值

对原始的数据进行分割，如下表所示：

表3.2属性1数据分割表

取值贷款不贷款

白领11

工人02

学生11

表3.2可以表示成如下的决策树结构:

贷款：4

职业不贷款：2

贷款：1

不贷款：1

(2)属性2是连续性变量，这里将数据分成三个区间，分别是［10,20］、［20,30］、［30,40］,

则每一个区间的分裂结果如下：

表3.3属性2数据分害表

区间贷款不贷款

[0,20]12

(20,40]02

(40,—]10

表3.3可以表示成如下的决策树结构:

贷款：1贷款：0贷款：1

不贷款：2不贷款：2不贷款：0

3.2分裂属性的选择

我们知道了分裂属性是如何对数据进行分割的，那么我们怎样选择分裂的属性呢？

决策树采用贪婪思想进行分裂，即选择可以得到最优分裂结果的属性进行分裂。那么怎

样才算是最优的分裂结果？最理想的情况当然是能找到一个属性刚好能够将不同类别分开，

但是大多数情况下分裂很难一步到位，我们希望每一次分裂之后孩子节点的数据尽量“纯”,

以下图为例：

图3.1按属性1进行分裂图3.2按属性2进行分裂

从图3.1和图3.2可以明显看出，属性2分裂后的孩子节点比属性1分裂后的孩子节

点更纯：属性1分裂后每个节点的两类的数量还是相同，跟根节点的分类结果相比完全没

有提高；按照属性2分裂后每个节点各类的数量相差比较大，可以很大概率认为第一个孩

子节点的输出结果为类1,第2个孩子节点的输出结果为2。

选择分裂属性是要找出能够使所有孩子节点数据最纯的属性，决策树使用信息增益或

者信息增益率作为选择属性的依据。

(1)信息增益

用信息增益表示分裂前后跟的数据复杂度和分裂节点数据复杂度的变化值，计算公式

表示为：

n

Info_Gain—Gain-工Gain,

J=I

其中Gain表示节点的复杂度，Gain越高，说明复杂度越高。信息增益说白了就是分

裂前的数据复杂度减去孩子节点的数据复杂度的和，信息增益越大，分裂后的复杂度减小得

越多，分类的效果越明显。

节点的复杂度可以用以下两种不同的计算方式：

a)燧

嫡描述了数据的混乱程度，烯越大，混乱程度越高，也就是纯度越低；反之，端越小，

混乱程度越低，纯度越高。端的计算公式如下所示：

n

Entropy=p.■log(py)

2=1

其中Pi表示类i的数量占比。以二分类问题为例，如果两类的数量相同，此时分类节点的

纯度最低，焙等于1；如果节点的数据属于同一类时，此时节点的纯度最高，嫡等于0。

b）基尼值

基尼值计算公式如下:

n

Gini=1-Zp：

2=1

其中Pi表示类i的数量占比。其同样以上述端的二分类例子为例，当两类数量相等时,

基尼值等于0.5；当节点数据属于同一类时，基尼值等于0。基尼值越大，数据越不纯。

例：

以燧作为节点复杂度的统计量，分别求出下面例子的信息增益，图3.1表示节点选择

属性1进行分裂的结果，图3.2表示节点选择属性2进行分裂的结果，通过计算两个属性

分裂后的信息增益，选择最优的分裂属性。

类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相比是更优的分裂属性，故选择属性1作

为分裂的属性。

(2)信息增益率

使用信息增益作为选择分裂的条件有一个不可避免的缺点：倾向选择分支比较多的属

性进行分裂。为了解决这个问题，引入了信息增益率这个概念。信息增益率是在信息增益的

基础上除以分裂节点数据量的信息增益(听起来很拗口)，其计算公式如下：

InGam

Info_Ratio=f°-

Instrinsichifo

其中Info-Galn表示信息增益，成协,表示分裂子节点数据量的信息

增益，其计算公式为：

Instrinsiclnfo=

A

其中m表示子节点的数量，A才表示第i个子节点的数据量，N表示父节点数据量，说白了，

其实/mmnszc/g是分裂节点的琉如果节点的数据链越接近，/何"4硫,越大，

如果子节点越大，加壮族越大，而/硫-就会越小，能够降低节点分裂时

选择子节点多的分裂属性的倾向性。信息增益率越高，说明分裂的效果越好。

还是信息增益中提及的例子为例：

类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停止分裂的条件

决策树不可能不限制地生长，总有停止分裂的时候，最极端的情况是当节点分裂到只剩

下一个数据点时自动结束分裂，但这种情况下树过于复杂，而且预测的经度不高。一般情况

下为了降低决策树复杂度和提高预测的经度，会适当提前终止节点的分裂。

以下是决策树节点停止分裂的一般性条件：

(1)最小节点数

当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，

再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有

利于降低过拟合的影响。

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

由上述可知，燧和基尼值的大小表示数据的复杂程度，当婚或者基尼值过小时，表示

数据的纯度比较大，如果焙或者基尼值小于一定程度数，节点停止分裂。

(3)决策树的深度达到指定的条件

节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1，因

为这些节点与跟节点的距离为1，子节点的深度要比父节点的深度大1。决策树的深度是所

有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。

(4)所有特征已经使用完毕，不能继续进行分裂。

被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点。

3.4决策树的构建方法

根据决策树的输出结果，决策树可以分为分类树和回归树，分类树输出的结果为具体

的类别，而回归树输出的结果为一个确定的数值。

决策树的构建算法主要有ID3、C4.5、CART三种，其中ID3和C4.5是分类树，CART

是分类回归树，将在本系列的山史、C4.5和CART中分别讲述。

其中ID3是决策树最基本的构建算法，而C4.5和CART是在ID3的基础上进行优化

的算法。

4.决策树的优化

一棵过于复杂的决策树很可能出现过拟合的情况，如果完全按照3中生成一个完整的

决策树可能会出现预测不准确的情况,因此需要对决策树进行优化，优化的方法主要有两种，

一是剪枝，二是组合树，将在本系列的剪枝和组合树中分别讲述。

决策树系列(二)剪枝

什么是剪枝？

剪枝是指将一颗子树的子节点全部删掉，根节点作为叶子节点，以下图为例:

为甚么要剪枝？

决策树是充分考虑了所有的数据点而生成的复杂树，有可能出现过拟合的情况，决策

树越复杂，过拟合的程度会越高。

考虑极端的情况，如果我们令所有的叶子节点都只含有一个数据点，那么我们能够保

证所有的训练数据都能准确分类，但是很有可能得到高的预测误差，原因是将训练数据中所

有的噪声数据都"准确划分”了，强化了噪声数据的作用。

剪枝修剪分裂前后分类误差相差不大的子树，能够降低决策树的复杂度，降低过拟合

出现的概率。

怎样剪枝？

两种方案：先剪枝和后剪枝

先剪枝说白了就是提前结束决策树的增长，跟上述决策树停止生长的方法一样。

后剪枝是指在决策树生长完成之后再进行剪枝的过程。这里介绍三种后剪枝方案：

(1)REP一错误率降低剪枝

顾名思义，该剪枝方法是根据错误率进行剪枝，如果一棵子树修剪前后错误率没有下

降，就可以认为该子树是可以修剪的。

REP剪枝需要用新的数据集，原因是如果用旧的数据集，不可能出现分裂后的错误率

比分裂前错误率要高的情况。由于使用新的数据集没有参与决策树的构建，能够降低训练数

据的影响，降低过拟合的程度，提高预测的准确率。

(2)PEP一悲观剪枝

悲观剪枝认为如果决策树的精度在剪枝前后没有影响的话，则进行剪枝。怎样才算是

没有影响？如果剪枝后的误差小于剪枝前经度的上限，则说明剪枝后的效果与剪枝前的效果

一致，此时要进行剪枝。

进行剪枝必须满足的条件：

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

其中：

E即表示剪枝前子树的误差；

表示剪枝后节点的误差；

两者的计算公式如下：

石.=£3+。§

%=2+05

m

令子树误差的经度满足二项分布，根据二项分布的性质，石必，“=3（4+°§,

________瓦加

S（耳s«）=J"pQ-p），其中0一N,N为子树的数据量；同样，叶子节点的误

差石W=e+0.5。

上述公式中，0.5表示修正因子。由于子节点是父节点进行分裂的结果，从理论上讲，

子节点的分类效果总比父节点好，分类的误差更小，如果单纯通过比较子节点和父节点的误

差进行剪枝就完全没有意义了，因此对节点的误差计算方法进行修正。修正的方法是给每一

个节点都加上误差修正因子0.5,在计算误差的时候，子节点由于加上了误差修正因子，就

无法保证总误差低于父节点。

算例:

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一代价复杂度剪枝

代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右

子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最

多的非叶子节点进行剪枝。

可描述如下：

令决策树的非叶子节点为｛4石，4,……。

a）计算所有非叶子节点的表面误差率增益值

b）选择表面误差率增益值最小的非叶子节点（若多个非叶子节点具有相同小的表面

误差率增益值，选择节点数最多的非叶子节点）。

O对选中的非叶子节点进行剪枝

表面误差率增益值的计算公式:

N(T)-1

其中:

即）表示叶子节点的误差代价，和）=顶了（”，心为节点的错误率，P（）为

节点数据量的占比；

m

火⑶法示子树的误差代价，""一斗S’⑺，力）：为子节点i的错误率，Pi⑺表

示节点i的数据节点占比；

-"（刀:表示子树节点个数。

算例：

下图是决策树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）什么时候停止分裂

从上述三个问题出发，以实际的例子对ID3算法进行阐述。

例：通过当天的天气、温度、湿度和季节预测明天的天气

表1原始数据

当天天气温度湿度季节明天天气

晴2550春天晴

阴2148春天阴

阴1870春天雨

晴2841夏天晴

雨865冬天阴

晴1843夏天晴

阴2456秋天晴

雨1876秋天阴

雨3161夏天晴

阴643冬天雨

晴1555秋天阴

雨458冬天雨

1.数据分割

对于离散型数据，直接按照离散数据的取值进行分裂，每一个取值对应一个子节点,

以''当前天气”为例对数据进行分割，如图1所示。

%31%1

Hff叫:

112

m:

02m.:1

m:m:m:

图1按照“今天天气”属性进行划分

对于连续型数据，ID3原本是没有处理能力的，只有通过离散化将连续性数据转化成

离散型数据再进行处理。

连续数据离散化是另外一个课题，本文不深入阐述，这里直接采用等距离数据划分的

李算话方法。该方法先对数据进行排序，然后将连续型数据划分为多个区间，并使每一个区

间的数据量基本相同，以温度为例对数据进行分割，如图2所示。

温度

252118288182418316154

按温度的高低进行排序

468151818182124252831

1喷1n

端11z

468151818182124252831lwM:

1防n1

曲z

1^±

和

11

zn

M:^iw:1±

图2按照“温度”属性进行划分

2.选择最优分裂属性

ID3采用信息增益作为选择最优的分裂属性的方法,选择焙作为衡量节点纯度的标准，

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

Info_Gain-Entropy-Z2「Entropy

其中，少表示父节点的嫡；石〃〃•尔匕表示节点i的帽，嫡越大，节点的

信息量越多，越不纯；夕表示子节点i的数据量与父节点数据量之比。力g_Ga为越

大，表示分裂后的端越小，子节点变得越纯，分类的效果越好，因此选择I?於_Gain最

大的属性作为分裂属性。

对上述的例子的跟节点进行分裂，分别计算每一个属性的信息增益，选择信息增益最

大的属性进行分裂。

天气属性：(数据分割如上图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

季节:

端

11喻1

IW:叫

叫202

孙

020

M:ffi:m:

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

333333

=0.973

由于Info_Gai%最大，所以选择属性''季节"作为根节点的分裂属性。

3.停止分裂的条件

停止分裂的条件已经在决策树中阐述，这里不再进行阐述。

(1)最小节点数

当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，

再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有

利于降低过拟合的影响。

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

由上述可知，端和基尼值的大小表示数据的复杂程度，当嫡或者基尼值过小时，表示

数据的纯度比较大，如果嫡或者基尼值小于一定程度时，节点停止分裂。

(3)决策树的深度达到指定的条件

节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1,因

为这些节点与跟节点的距离为L子节点的深度要比父节点的深度大1。决策树的深度是所

有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。

(4)所有特征已经使用完毕，不能继续进行分裂。

被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点。

(1)数据处理

用二维数组存储原始的数据，每一行表示一条记录，前n-1列表示数据的属性，第n

列表示分类的标签。

为了方便后面的处理，对离散属性进行数字化处理，将离散值表示成数字，并用一个

链表数组进行存储，数组的第一个元素表示属性1的离散值。

staticList<String>[]featurevalues;

那么经过处理后的表1数据可以转化为如表2所示的数据：

表2初始化后的数据

当天天气温度湿度季节明天天气

1255011

2214812

2187013

1284121

386532

1184321

2245641

3187642

3316121

264333

1155542

345833

其中，对于当天天气属性，数字｛1,2,3｝分别表示｛晴，阴，雨｝;对于季节属性

｛1,2,3,4）分别表示｛春天、夏天、冬天、秋天）;对于明天天气｛1,2,3｝分别表示｛晴、

阴、雨｝。

（2）两个类：节点类和分裂信息

a）节点类Node

该类存储了节点的信息，包括节点的数据量、节点选择的分裂属性、节点输出类、子

节点的个数、子节点的分类误差等。

田ViewCode

b）分裂信息类Splitinfo

该类存储节点进行分裂的信息，包括各个子节点的行坐标、子节点各个类的数目、该

节点分裂的属性、属性的类型等。

田ViewCode

（3）节点分裂方法findBestSplit（Nodenode,List<int>numszint[]isllsed）,

该方法对节点进行分裂，返回值Node

其中：

node表示即将进行分裂的节点；

nums表示节点数据对应的行坐标列表；

isUsed表示到该节点位置所有属性的使用情况（1：表示该属性不能再次使用，0：表

示该属性可以使用）；

findBestSplit主要有以下几个组成部分：

1）节点分裂停止的判定

判断节点是否需要继续分裂，分裂判断条件如上文所述。源代码如下：

2）寻找最优的分裂属性

寻找最优的分裂属性需要计算每一个分裂属性分裂后的信息增益，计算公式上文已给出.

3）进行分裂，同时子节点也执行相同的分类步骤

其实就是递归的过程，对每一个子节点执行findBestSplit方法进行分裂。

（注：上述代码只是ID3的核心代码，数据预处理的代码并没有给出，只要将预处理后的

数据输入到主方法findBestSplit中，就可以得到最终的结果）

总结

ID3是基本的决策树构建算法，作为决策树经典的构建算法，其具有结构简单、清晰

易懂的特点。虽然ID3比较灵活方便，但是有以下几个缺点：

（1）采用信息增益进行分裂，分裂的精确度可能没有采用信息增益率进行分裂高

（2）不能处理连续型数据，只能通过离散化将连续性数据转化为离散型数据

（3）不能处理缺省值

（4）没有对决策树进行剪枝处理，很可能会出现过拟合的问题

决策树系列（四）一一C4.5

如上一篇文章所述，ID3方法主要有几个缺点：一是采用信息增益进行数据分裂，准

确性不如信息增益率；二是不能对连续数据进行处理，只能通过连续数据离散化进行处理:

三是没有采用剪枝的策略，决策树的结构可能会过于复杂，可能会出现过拟合的情况。

C4.5在ID3的基础上对上述三个方面进行了相应的改进：

a)C4.5对节点进行分裂时采用信息增益率作为分裂的依据；

b)能够对连续数据进行处理；

c)C4.5采用剪枝的策略，对完全生长的决策树进行剪枝处理，一定程度上降低过

拟合的影响。

工.采用信息增益率作为分裂的依据

信息增益率的计算公式为：

,InfoGain

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

Imtrinsiclnfo

其中Info_Gai”表示信息增益，/您“历做表示分裂子节点数据量的

信息增益，计算公式为：

.n.n

Instnnsiclnfo=->—•log(—)

UNN

其中m表示节点的数量，Ni表示第i个节点的数据量，N表示父亲节点的数据量，

说白了，^trtnsiclnfo-其实是分裂节点的稀

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

以一个实际的例子说明C4.5如何通过信息增益率选择分裂的属性:

表1原始数据表

当天天气温度湿度日期逛街

晴2550工作日否

晴2148工作日是

晴1870周末是

晴2841周末是

阴865工作日是

阴1843工作日否

阴2456周末是

阴1876周末否

雨3161周末否

雨643周末是

雨1555工作日否

雨458工作日否

以当天天气为例：

一共有三个属性值，晴、阴、雨，一共分裂成三个子节点。

当天天气ARIK季节明天天气

Bff25SO工作日K

当天天气工度日期逛街晴2148工作日

晴2S50工作日S瞪1870是

晴2148工作日1Iff28419^

晴1870周末是

IX2841嘛是

当天天气1度18季节明天天气

明865工作日1

阴865工作日是

阳1843工作日S

阴1843工作日否

阴2456周末是

阴2456嘛是

阳1876却否

阴1876嘛S

雨3161周末否

雨643稣是

雨1555工作日否

雨458工作日S当天天气.8®季节朗天天气

雨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.对连续型属性进行处理

C4.5处理离散型属性的方式与ID3一致，新增对连续型属性的处理。处理方式是先

根据连续型属性进行排序，然后采用一刀切的方式将数据砍成两半。

那么如何选择切割点呢？很简单.，直接计算每一个切割点切割后的信息增益，然后选择使分

裂效果最优的切割点。以温度为例：

当天天气温度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个切割点，为了选取最优的切割垫，

要计算按每一次切割的信息增益，计算量是比较大的，那么有没有简化的方法呢？有，注意

到，其实有些切割点是很明显可以排除的。比如说上图右侧的第2条和第3条记录，两者

的类标签（逛街）都是''是"，如果从这里切割的话，就将两个本来相同的类分开了，肯定不

会比将他们归为一类的切分方法好，因此，可以通过去除前后两个类标签相同的切割点以简

化计算的复杂度，如下图所示：

当天天气星度漫度日期酒街当天天气18灌度日期逐街

否

IX2550工作日否