- 1 -
中国科技论文在线
一种基于分类规则树和信息熵的决策树构
造方法#
刘宁*
基金项目：重庆市科委项目(2009BB2082)；重庆市教委项目(KJ080510)
作者简介：刘宁（l984-），男，硕士，主要研究方向：数据挖掘
（重庆邮电大学计算机科学与技术研究所，重庆 400065） 5
摘要：随着网络技术和硬件技术的发展，面临数据的海量增长，数据规模由于过于庞大不便
于存储，这对传统分类算法提出了挑战。为此，文中提出了一种基于分类规则树和信息熵相
结合的决策树构建新方法 DTC_IE算法，并通过实验证明，DTC_IE 算法在处理规模较大数
据时，运行时效率优于传统决策树分类算法 ID3。
关键词：大规模数据；决策树；信息熵；分类 10
中图分类号：TP391
A Decision Tree Construction Method Based On RS_Tree
and Information Entropy
LIU Ning 15
(Institute of Computer Science and Technology，Chongqing University of Posts and
Telecommunications，Chongqing 400065)
Abstract: With the development of network technology and hardware technology，some datas are too
large to be stored，which poses a challenge for the traditional classification algorithms. In this paper, it
propose a decision tree construction method based on rs_tree and information entropy. The results of 20
experiments show that the time efficiency of the new algorithm is much better than the classification
algorithm ID3 when dealing with the massive data sets.
Key words: Massive data；Decision Tree；Information Entropy；Classificationword
0 引言 25
随着网络技术和硬件技术的发展，我们面临数据的海量增长，如股票交易所的股票价格
信息，环境温度的监测数据，电信部门的通话记录等等。这些数据是连续的、无限的、快速
的、随时间变化的，被称为数据流，并由此产生出数据流挖掘技术 [1,2,3]。与数据挖掘一样，
分类预测方法同样也成为数据流挖掘技术中一项重要的分析方法。决策树[4,5]是一种常用、
直观的分类算法，与其他分类算法相比，该算法构造出的决策树分类模型易于理解和解释，30
具有较高应用价值。
传统决策树算法分类大都需要对数据集进行多次扫描，从而造成代价越来越高，且构造
效率日趋降低，严重影响了后期分类预测效率。如 ID3，算法，它们从静态训练元组数
据集以及与它们相关联的类标号开始，采用自顶向下递归的分治方法通过多次扫描数据集构
造决策树，带来分类效率的下降。CART[6]算法同样通过多次扫描数据集构造决策树，采用35
的是计算 GINI系数。IBM研究人员提出的一种决速可伸缩的适合处理较大规模数据的决策
树分类算法 SLIQ(Supervised Learning In Quest)[7]，在算法中运用一些特殊数据结构如属性表
和类表，但面临着主存容量的限制。Agrawal 等[8]提出了 SPRINT(Scalable parallelizable
Induction of Classification Tee)算法, 其目的是解决主存容量的受限问题，但在样本少量的情
- 2 -
中国科技论文在线
况下 SPRINT却比 SLQI执行得慢。 40
因此，如何提高决策树模型的构造效率便成为当前分类方法研究中急需解决的问题[9]。
本文借用了文献[10,11]中分类规则树 RS_Tree模型通过单次扫描获得数据的统计信息，避免
了反复扫描带来的代价。信息熵[12]是信息论中广泛用于度量信息量的一个概念。信息熵的
引入，可以有效地解决信息的量化度量及冗余信息处理等问题。基于上述思想，本文提出一
种基于 RS_Tree 和信息熵相结合的决策树构建新方法 DTC_IE（Decision Tree Construction 45
Method based on RS_Tree and Information Entropy）。该方法有效解决了数据流分类技术中如
何通过单遍扫描大规模训练元组数据构造决策树问题，提高决策树构建效率，为决策树构造
算法提供了改进思路。实验表明，在少量样本情况下，DTC_IE与 ID3算法所用时间基本相
同；但随着样本数目的增多，DTC_IE比 ID3优势越来越明显。
1 相关理论基础 50
本节将简介决策表、规则树 RS_Tree和信息熵的一些基本概念。
定义 一个决策表是一个由四元组 ( , , , )S U A V f= 构成的知识表达系统,其中U
是对象的集合,也称为论域，A C D= ∪ 是属性的集合,子集C和D分别被称为条件属性集和
决策属性集，D φ≠ ，V 是属性值集合, :f U A V× → 是信息函数,它指定U 中每一个对
象各个属性的取值。 55
分类规则树 RS_Tree[8,13]是根据规则集生成的树型结构，它类似于判定树，不同的是它
的每一层分枝除了属性的确定取值外，还添加了一个任意值分枝。文献[10,11]主要用
RS_Tree来存储我们已经得到的规则集，在本文中它主要用于存储训练元组数据，其中每个
节点不仅包括确定的属性值，还包括对该值出现次数的一个统计。它可以进行如下定义：
(1) 由一个根结点，若干叶结点和若干非叶结点构成； 60
(2) 根结点对应于整个训练元组数据；
(3) 每个从根结点到叶结点的分枝都表示一条元组数据；
(4) 每个节点不仅包括确定的属性值，还包括对该值出现次数的一个统计。
RS_Tree只需要访问一次训练元组数据。在进行一次扫描后，我们统计每个分枝下属性
值的出现次数。 65
根据文献[14]，给定一决策表 S＝（U, DCA ∪= ），U 是论域，C和D分别为决策
表的条件属性和决策属性，设 ,P Q A⊆ ， P和Q在U 上的两个划分 1 2{ , ,..., }nX X X ，
1 2{ , ,..., }mY Y Y ，分别记为 | ( )U IND P 和 | ( )U IND Q ，其上的概率分布为：
[ ] 1 2
1 2
...
:
( ) ( ) ... ( )
n
n
X X X
X p
p X p X p X
⎡ ⎤= ⎢ ⎥⎣ ⎦，[ ]
1 2
1 2
...
:
( ) ( ) ... ( )
m
m
Y Y Y
Y p
p Y p Y p Y
⎡ ⎤= ⎢ ⎥⎣ ⎦
其中 | |( ) , 1, 2,...,| |
i
i
Xp X i nU= = ； | |( ) , 1,2,...,| |ii Yp Y i mU= = 。符号 | |E 表示集合70
E的基或势（cardinality）。
有了上述的表述，根据信息论就可以定义信息熵和条件信息熵的概念[14,15]。
定义 知识（属性集合）P的熵 ( )H P 定义为 ：
))(log()()(
1
∑
=
−=
n
i
XipXipPH （1）
定义 知识（属性集合） 1 2( | ( ) { , ,..., })mQ U IND Q Y Y Y= 相对于知识（属性集合）75
- 3 -
中国科技论文在线
1 2( | ( ) { , ,..., })nP U IND P X X X= 的条件熵 ( | )H Q P 定义为：
))|(log()|()()|(
1 1
∑ ∑
= =
−=
n
i
m
j
ijiji XYpXYpXpPQH ， （2）
其中 ||/||)|( iijij XXYXYp ∩= , 1,2,..., , 1, 2,...i n j m= = 。
2 基于分类规则树和信息熵的决策树构造方法
构造原理 80
基于分类规则树RS_Tree和信息熵的决策树构造方法DTC_IE算法先对训练元组数据集
构造 RS_Tree，得到各属性和类别标号的一个组合，并统计出每个节点包含的属性值的出现
次数，根据统计结果计算出各属性及其分枝属性下的信息熵，选择信息熵最小的属性及其值
作为各层节点，从而避免了对训练元组数据集的多次扫描。DTC_IE不仅使用单次扫描数据
集，提高了决策树构建效率，而且使用 RS_Tree对样本属性值进行统计，从而避免了当新数85
据到来时，为了提高分类精度，对原始数据进行重新扫描，有效处理新增数据（当新样本数
据到来时，我们只需更新统计信息，不需对原始数据进行重新扫描）。
算法描述
首先定义一个结构体 TREENODE，它包含四个成员变量。
struct TREENODE //定义一个树的结构体 90
{int nAttrvaule; //定义节点的一个变量，用于保存各属性下的属性值信息
int count;//定义节点变量，用于统计各属性下属性值出现的次数
TREENODE *Lchild,*Rsibling ;} //定义*Lchild指向孩子节点指针，*Rsibling指向其兄
弟节点指针
基于 RS_Tree和信息熵的决策树构造算法描述如下： 95
输入：决策表 ( , )S U A C D= = ∪ ，其中 1 2{ , ,..., }mC a a a= ， 1 2{ , ,..., }nU x x x= ，
D d= 。
输出：一棵决策树T
步骤：
（1）创建一个树根节点 RT=φ ，TREENODE *firstchild，Firstchild=，RT. 100
nAttrvalue=NULL， =NULL, =NULL,=1;CN=RT;//初始化树
T :RT和 RS_Tree:CN
（2）依次读取U 中数据，构造 RS_Tree，统计出U 中各属性下的属性值出现次数。
（3）根据上述统计结果，对 RS_Tree进行剪枝处理，删除每条规则路径下的冗余值信
息，具体分三种情况处理： 105
（一）IF d in RS_Tree取值唯一，则 取为该值。
（二）IF C φ⊆ ，选择 D中出现最多的类别作为叶子节点。
（三）ELSE FOR EACH ia in RS_Tree 中的条件属性 ia 计算出其相对于决策属性
集 d（即叶子节点）的条件信息熵 ( | )iH d a ，选择条件信息熵最小的属性作为 RT
所对应的孩子节点，并以该节点为父节点且根据 RS_Tree中分裂出的路径据计算其110
它属性相对于d 的信息熵，选择最小信息熵属性最佳分裂属性。（1 i m≤ ≤ ）依
- 4 -
中国科技论文在线
次循环计算下去，直到属性所分裂的路径对应的d 值唯一或者没有待分裂的属性
（选择最多类别作为叶子节点）时结束。
（4）输出决策树T
算法分析 115
基于 RS_Tree 和信息熵的决策树构造方法产生的决策树模型与经典 ID3 算法的结果一
致，且具有以下优点：
（1）本文方法的计算量远小于 ID3算法
ID3 算法用训练元组数据计算信息增益，设训练元组数量为N ，条件属性数量为V ，
算法效率与训练元组的数据量大小和属性数量正相关，则算法的计算量为 1G N V= × 。 120
本文方法采用 RS_Tree 统计结果来代替训练元组计算信息熵，由于执行效率主要与
RS_Tree路径数相关，因此得到极大提高，具体分析如下：
1)假设训练元组数量为N ，RS_Tree路径数量为M ，有M N≤ 。
2)设训练元组有V 个属性，每个属性具有 1 2{ , , , }Vd d d⋅ ⋅ ⋅ 个不同值，则 ∏
=
≤
v
i
dvM
1
。
本文方法的计算量根据下式计算： 125
2G N M V= + × (3)
两种算法的计算量比较如下式所示：
2 1/ ( ) / ( ) 1/ /G G N M V N V V M N= + × × = + （4）
由式(4)可以看出，当训练元组规模较大时，数据有一定规律，路径数量相比训练元组
数量将极大减少，即M N<< 。此时， 2 1/ 1G G << ，即本文方法的计算量远小于 ID3算法。 130
（2）基于 RS_Tree和信息熵的决策树构造方法只需要对数据集进行一次扫描，获得统
计结果，从而计算出信息熵，而金典 ID3算法需多次扫描数据集计算出相应的信息增益值，
利用 RS_Tree和信息熵构造决策树更适合于不便于存储的数据流模型数据的处理。
3 实验结果和分析
实例分析 135
为了说明本文方法，下面给出一个实例分析。表 1 是一个决策表， { , , }C a b c= 表示决
策表的条件属性， { }D d= 表示决策属性（类标签），括号里面数据表示该元组数据在U 中
出现的次数。
具体步骤如下：
（1）根据表 1所示的数据构造出 RS_Tree,如图 1所示。比如，节点（1）（ 3:90a = ）140
表示在属性a下值为 3的样本出现次数为 90，其它节点同理。
表 1 决策表 1
a b c d
X1 3 2 1 1(50)
X2 1 2 1 2(5)
X3 3 2 2 2(30)
X4 3 3 2 2(10)
X5 1 5 3 3(4)
X6 1 5 3 4(1)
- 5 -
中国科技论文在线
图 1 决策表 1的分类规则树
145
（2）通过上述统计，计算出各层及其分裂路径的属性信息熵，选择信息熵最小的作为
该节点的最佳属性,下面描述分裂属性选择步骤。
根据公式（2），可计算出 , ,a b c相对于决策属性d 的条件熵分别为：
))|(log()|()(}){|}({
1 1
∑ ∑
= =
−=
n
i
n
j
ijiji XYpXYpXpadH
2 2 2 2 2
90 50 50 40 40 10 5 5 4 4 1 1( log log ) ( log log log )
100 90 90 90 90 100 10 10 10 10 10 10
⎡ ⎤= − × + + × + + =⎢ ⎥⎣ ⎦150
({ } |{ }) d b = ； ({ } |{ }) d c = 。
熵越小，说明该属性区分训练样例能力越强，划分纯度越高，选择该属性可能性越大，
可知c为最佳分裂属性节点。当 1c = 时，我们可得出 1d = 或 2d = ，为此我们需要引入其
它属性加以区分样本，在 1c = 下分裂出其它的属性； 2 2c d= → = ， 3 3c d= → = (节点
唯一，选择出现类别数最多的类作为叶子节点)。 155
设 '{ }B a B= ∪ ， 'B C⊆ ，B在U 上的 aa V= 条件划分记为 | ( )aVU IND B ，D在U 上
的划分记为 | ({ })U IND d ，则 ( | )
aV
H d B 为 | ({ })U IND d 相对于 | ( )
aV
U IND B 的条件熵。
则：
1 2 2
50 50 5 5({ } |{ , } ) log log
55 55 55 55c
H d c b =
⎡ ⎤= − + =⎢ ⎥⎣ ⎦
1 2 2
50 50 5 5({ } |{ , } ) log log 0
55 50 55 5c
H d a c =
⎡ ⎤= − + =⎢ ⎥⎣ ⎦ 160
由此可得出在 1c = 时分裂出的属性选择为a，此时，在a下对应的d 值唯一，由此可
得出最终的分类规则集为：
1 3 1c a d= ∧ = → = ； 1 1 2c a d= ∧ = → = ； 2 2c d= → = ； 3 3c d= → = 。
（3）最终得到的决策树如图 2所示。
- 6 -
中国科技论文在线
165
图 2 决策表 1的决策树
本文最终构造方式和 ID3算法得到的规则结果是一致的，说明我们的方法是正确的。
实验结果
为了验证算法的有效性以及算法处理数据的能力，我们分别对 DTC_IE和 ID3规则树算170
法在 下编制代码，并对这两种算法进行了比较，实验采用来自 UCI数据集中的
TIC-TAC-TOE（10个属性），VOTING（17个属性），ZOO（17个属性）和 SPLICE-JXN
（60个属性）数据集。
实验 1：样本规模（数目）对 DTC_IE和 ID3的影响
实验步骤如下： 175
(1)把原始数据集作为测试样本，分别把 TIC-TAC-TOE，VOTING，ZOO数据集扩大 N
倍（N为自然数）作为测试样本；
(2)运行 DTC_IE和 ID3算法，生成规则树，并记录运行时间，比较结果见表 2。
表 2 DTC_IE和 ID3算法比较测试 180
运行时间（S） 数据集 样本数目（N）
DTC_IE ID3
958 1
1916 2 TIC-TAC-TOE
2874 3
435 1
8700 20 VOTING
41760 96
101 1
1010 10 ZOO
2020 20
通过以上的测试，我们可以看出，随着样本数目的增多，DTC_IE算法由于采取单次扫
描数据集，其运行速度越来越快，运行效率大于 ID3算法，尤其是针对数据量大的情况。
实验 2：样本属性数目对 DTC_IE和 ID3的影响
实验步骤如下： 185
(1)为了测试样本属性数目对 DTC_IE和 ID3的影响，我们选择 UCI中的 SPLICE-JXN
- 7 -
中国科技论文在线
数据集，它包括 3190个样本和 60个离散属性，分别选择前 10，20，30，40个属性作为测
试属性；
(2)运行 DTC_IE和 ID3算法，生成规则树，并记录运行时间，比较结果见表 3。
190
表 3 DTC_IE和 ID3算法比较测试
属性数目
SPLICE-JXN
10 20 30 40
DTC_IE
ID3
通过以上的测试，我们可以看出，随着样本属性数目的增多，DTC_IE算法由于采用
RS_Tree对数据集单次扫描，导致树中信息量冗余，搜索效率低下，在属性过多的情况下，
运算时间远高于 ID3算法。 195
综上分析，可得出 DTC_IE在处理较大规模数据的情况下，效率远远高于 ID3算法；在
处理属性数较多的数据时，统计信息量过于冗余，从而导致效率低下。
4 结论
数据流挖掘已成为我们现在研究的热点，本文针对数据流的特点对传统决策树分类算法
进行改进，提出了 DTC_IE算法，并通过实验证明该算法的优缺性，在处理规模较大数据时200
效率远远高于 ID3算法。因此，如何对数据流中新到达数据进行增量式学习将是我们下一步
研究的重点。
[参考文献] (References)
[1]王 涛，李舟军，颜跃进等.数据流挖掘分类技术综述[J].计算机研究与发展 44(11)：l809～1815，2007 205
[2] Zhu Y，Shasha D. StatStream：statistical monitoring of thousands of data streams in real time[C]．Proc 28th
Int．Conf．on Very Large Data Bases，2002
[3]张天成，岳德君，于 戈，林树宽，谷 峪.数据流挖掘研究及其进展[J].小型微型计算机系统 2008 年 12
月第 12期
[4]鲁为，王枞.决策树算法的优化与比较[J].计算机工程 33(161)：189-190，2007 210
[5]Tom . Machine Learning(ISBN 0-07-115467-1)[M].Copyright 1997 by The McGRaw-Hill
companies，Inc
[6]， and . Classification and Regression Trees [M]. Belmont，CA: Wadsworth
International Group，1984
[7] ， and . SLIQ: A fast scalable classification for data Proc. of the Fifth 215
Int’1 Conference on Extending Database Technology Avignon,France,1996
[8].， and . SPRINT :Ascable Parallel classification for data mining. Research center，
IBM Almaden Research center，SanJose，California，1996
[9] 徐林章，赵强，张艳宁. 一种基于 FP-Tree算法的决策树构造方法[J].计算机工程，2009年 4月
[10]Peng Wang，Haixun Wang，Xiaochen Xu. On Reducing Granularity in Mining Concept-Drifting Data 220
Stream[C].Proceeding of the Fifth IEEE International Conference on Data Mining, 2005
[11], . Wang. RRIA: A Rough Set and Rule Tree Based Incremental Knowledge Acquisition
Algorithm[J]. Fundamental Information, 2004, 59(2-3): 299-313
[12] 吴伯修等.信息论与编码[J].电子工业出版社，1986
[13]陈小云，陈袆，李荣陆，胡运发.基于分类规则树的频繁模式文本分类[J].软件学报 2006年第 17卷第 5225
期
[14]于洪. Rough Set理论及其在数据挖掘中的应用研究[M].重庆大学博士论文，2003年 9月
[15]Ivo Düntsch，Gunther Gediga. Uncertainty measures of rough set prediction. Artificial Intelligence
106(1998),109~137
230
