-1-
一种不确定多变量决策树生成算法1
邵良杉 1，邱云飞 2，孙韶光 1
1辽宁工程技术大学系统工程研究所，辽宁阜新（123000）
2辽宁工程技术大学软件学院，辽宁葫芦岛（125100）
摘 要：针对常规多变量决策树算法不能有效处理噪声数据影响的问题，将 粗糙
集(rough set，RS)模型中相对核的概念推广到变精度粗糙集(variable precision rough set，VPRS)
模型中，并利用其进行决策树初始变量选择；将两个等价关系相对泛化的概念推广为两个等
价关系多数包含情况下的相对泛化，并利用其进行决策树初始属性检验；最后，给出一种能
够有效消除噪声数据干扰的多变量决策树构造算法。
关键词：决策树；噪声数据；变精度粗糙集；相对核
中图分类号：TP 181 文献标识码：A
决策树作为分类和预测的重要工具，为确定某一事例类别的序贯决策方法提供了清晰的
陈述。决策树主要有单变量决策树和多变量决策树两种。由于单变量决策树在每个节点上只
检验一个属性（如ID3[1]，AQ11[2]，ASSISTANT[3]和GREEDY3&GROVE[4]等），从而造
成了对很多复杂概念的表达困难或无法表达[5]，为了解决这个问题人们提出了许多多变量
决策树构造算法（如Brodley C E[6]等人采用初始属性的线性组合来构造多变量决策树，苗
夺谦、王珏[5]利用粗糙集的相对核的概念构造多变量决策树），即在树的结点上可以同时检
验多个属性。然而，这些算法都是在理想的环境下进行推导的，没有考虑现实中噪声数据对
分类的影响。
Ziarko[7]等人提出的变精度粗糙集(variable precision rough set，VPRS)模型是对
的粗糙集(rough set，RS)模型的一种推广。VPRS 通过设置阈值参数 )( ≤< β ，放松了
RS 理论对近似边界的严格定义，即允许一定程度的错误分类率的存在。随着 β 变大，VPRS
模型的近似边界区域变窄，即变精度粗糙集意义下的不确定区域变小。当 =β 1 时，VPRS
模型就变成了 RS 模型，因此 RS 模型是 VPRS 模型的一个特例。相对 RS 模型来说 VPRS
模型对数据的不确定性有一定的容忍度。
构造不确定多变量决策树的关键问题是如何消除噪声数据对分类的影响，本文基于变精
度粗糙集模型提出了一种不确定多变量决策树构造算法。本文第 1 节将 Pawlak 粗糙集模型
中相对核的概念引入变精度粗糙集模型中，给出了变精度粗糙集模型下相对核的定义，解决
了有噪声数据干扰下的初始属性选择问题；从容忍数据中存在一定不确定性现象的角度出
发，将[5]中两个等价关系相对泛化的概念，推广为两个等价关系多数包含情况下的相对泛
化，进而进行多变量初始属性检验；第 2 节给出了不确定信息下的多变量决策树生成算法；
第 3 节给出了本文的结论。
1. 属性的选择及相对泛化
变精度粗糙集模型的相对核及属性的选择
变精度粗糙集模型是对Pawlak粗糙集模型的扩充。设 X 和Y 表示有限论域U 的非空子
集，令 ≤< β ，定义多数包含关系(majority inclusion relation)[7]：
1 本课题得到教育部博士点基金（20041047006）和国家自然科学基金（70572070）的资助。
-2-
ββ ≥⇔⊇ )|( XYDXY
其中，
⎩⎨
⎧
=
>=
0|| ,0
0|| |,|/||
)|(
X
XXYX
XYD
I
（1）
|| X 表示集合 X 的基数。称 )|( XYD 为集合Y 关于集合 X 的相对包含度。即只要 X
中被包含于Y 中的元素占到 X 的比例不小于 β 时，即可认为Y 包含 X 。特别的，当 1=β
时， 变精度粗糙集模型就退化为 Pawlak 粗糙集模型。
设 ),,,( fVAUS = 是一个信息系统； AQP ⊆, 为条件属性集和决策属性集。 ),(Pind
)(Qind 表示由 QP, 决定的不可区分关系，关系 )(Pind 的等价类的集合称为条件类，用
PU / 表示，关系 )(Qind 的等价类的集合称为决策类，用 QU / 表示。
设 },,,,,{ 21 ni XXXX ⋅⋅⋅⋅⋅⋅ 是 论 域 U 在 等 价 关 系 )(Pind 上 的 划 分 ， 则 满 足 ，
jiXXUniPUXX jiii ≠∅==⋅⋅⋅∈∈ ,,},,2,1,/|{ IU 且 。 },,,,,{ 21 mj YYYY ⋅⋅⋅⋅⋅⋅ 是论域U
在等价关系 )(Dind 上的划分。我们称 jY 为一个概念，是我们要描述的对象；称 iX 为已知
的知识块，用来近似描述 jY ；而用 iX 对 jY 的描述则称为规则。
对于决策等价类 jY 在阈值参数 β 时的上下近似集分别定义为：
},,2,1,)|(|/{)( niXYDPUXYR ijijP ⋅⋅⋅=≥∈= ββ U （2）
},,2,1,1)|(|/{)( niXYDPUXYR ijijP ⋅⋅⋅=−>∈= ββ U (3)
)( jP YR
β 是由U 中那些在现有知识 P下在正确分类水平 β 时属于概念 jY 的元素组成的
集合； )( jP YR
β 是在正确分类水平 β−1 时属于概念 jY 的元素组成的集合。
对于条件属性集P和决策属性集Q，有Q的P -正区域定义为
},......2,1,,,2,1,)|(|/{)(
/
mjniXYDPUXQPOS iji
QUY
P
j
=⋅⋅⋅=≥∈=
∈
ββ U （4）
设U 是一个论域， P和Q是定义在U 上的2个等价关系族，称一个等价关系 PR∈ 是
−Q 不必要的（或多余的），如果式
)()( }){( QPOSQPOS RPP
ββ
−= （5）
成立。否则，R在P中是 −Q 必要的。其中 PPind I=)( （所有属于P的等价关系的
交）也是一个等价关系，并且称为P上的一个不可区分关系。
P中所有 −Q 必要的等价关系组成的集合，称为P的 −Q 核，记作 )(PCOREQβ 。
当 QP, 分别表示信息系统的条件属性集和决策属性集时，若一个属性 PR∈ 是 −Q 不
必要的，则从 P中去掉属性 R不会改变原来信息系统的决策，而去掉P的 −Q 核中的属性
将改变原信息系统的决策。所以， P的 −Q 核中的属性对于决策来说是至关重要的。我们
将选择相对核中的属性作为构造多变量检验的属性。
相对泛化的定义
如何用所选的属性来构造多变量检验呢？通过分析，我们知道用所选属性的简单合取作
为多变量检验，可能会导致对数据的过拟合问题。为此,我们定义了两个等价关系在多数包
-3-
含情况下的泛化的概念。
定义1.设P和Q是U 上的两个等价关系组，且
},......,,{/ 21 nXXXPU = ， },......,,{/ 21 mYYYQU =
令 .,.......2,1,,......2,1},:{
/
minjYXXUZ ijjPUXi j
==⊆=
∈
β
（6）
},,......2,1,:{
/1
injYXXUZ ijjPUXm j
∀=⊄=
∈+
β
（7）
则称 },......,,{ 121 +mZZZ 在 U 上确定的等价关系为 P 相对于 Q 的泛化，记作
)(PGENQ
β 。
命题1. },......,,{ 121 +mZZZ 构成了U 上的一个划分，其中 iZ ，i=1,2,……,m+1,由（6）
（7）定义。
证明：参见[5]。
2. 不确定多变量决策树生成算法
决策树作为一种示例学习算法，是从标有类别信息的示例中，采用自顶向下的递归方式
构造决策树的。在决策树的内部节点进行属性值的比较并根据不同的属性值判断从该节点向
下的分支，在决策树的叶结点得到结论。
一个自顶向下的决策树算法是，首先根据某种划分度量准则选择最佳检验，然后，用选
择的检验去划分训练集，并且，相应于该检验的每一个结果产生一个分支，这一过程递归的
应用到该检验导出的每一个分类上，如果某一分类中的所有事例都来自一个类别，那么就产
生一个标有该类别名的叶结点。在决策树的构造过程中，人们希望在每个节点上都选择能把
事例划分到他们类中的最佳检验。
本文使用条件属性对应于决策属性的区分能力作为度量标准，利用变精度粗糙集模型的
相对核的概念给出构造不确定决策树的步骤如下：
（1）在变精度粗糙集模型的概念下删除冗余属性，进而计算条件属性集P相对于决策
属性集 Q 的核，即 )(PCOREQβ 。若 φβ =)(PCOREQ ，则转（ 2）；否则，不妨设
},......,,{)( 21 kQ aaaPCORE =β ,转（3）。
（2）用ID3的方法选择一个最佳属性，作为该节点的检验。
（3）令 321 ...... aaaP ∧∧∧= ，计算 P相对于Q的泛化 )(PGENQβ ，将它作为该节
点的检验。
3. 结论
本文提出了一种不确定多变量决策树生成算法，我们利用变精度粗糙集理论允许一定程
度的错误分类率存在的性质，消除了多变量决策树生成过程中噪声数据的影响，在此基础上
构造了变精度粗糙集理论中条件属性集相对于决策属性集的核的概念，解决了不确定多变量
检验中属性的选择问题，进而定义了两个等价关系在多数包含情况下的泛化的概念。利用这
一概念，使得多变量检验并不是被选属性的简单合取，而是由其导出的一个新属性，由于使
用了属性的不可区分性作为划分度量标准，这一方法避免了在决策树的一条路径上多次检验
某一属性的问题。
-4-
参考文献
[1]Quinlan J of decision trees[J].Machine Learning,1986,1:81～106.
[2]Michalski R S,Larson J of the most representative training examples and incremental generation of
VL 1 hypotheses[J].,Urbana-Champaign: Department of Computer Science,University of
Illinois,1978.
[3]Cestnik B, Kononenko I, Bratko I. ASSISTAN T 86:a know ledge elicitation tool for sophisticated
users[J].In:Proceedings of EW SL-87,Bled,Yugo slavia,～45
[4] Pagallo G, Haussler D. Boolean feature discovery in empirical learning[J].Machine Learning,1990,5:71～99.
[5]苗夺谦，王珏。基于粗糙集的多变量决策树构造方法[J]。,:425～431
[6]Brodley C E, U tgoff P E. Multivariate decision trees[J].Machine Learning, 1995,19:45～ 77.
[7]Ziarko. Variable precision rough set model[J].Journal of Computer and System Sciences，1993，46(1)：39-59．
An uncertainty algorithm for multivariate decision tree
construction
Shao Liangshan1, Qiu Yunfei2, Sun Shaoguang1
1 System Engineering Institute, Liaoning Technical University, Fuxin (123000)
2 School of Software, Liaoning Technical University, Huludao (125100)
Abstract
Aimed at the problem of the inability for multivariate decision tree algorithm to effectively deal with
noisy data, the paper extends the relative core of attributes in rough sets theory to variable precision
rough set(VPRS), and uses it for selection of attributes in multivariate tests. Under the condition of
majority inclusion relation the paper extends the concept of generalization of one equivalence relation
with respect to another one, and uses it for construction of multivariate tests. Finally, we propose an
algorithm for multivariate decision tree that can avoid disturbance of noisy data.
Keywords: Decision tree; noisy data; variable precision rough set; relative core of attributes
作者简介：
邵良杉，男，汉族，辽宁凌源人，教授，主要研究方向为决策支持系统、数据挖掘理论及其
应用；
邱云飞，男，蒙古族，辽宁阜新人，硕士/讲师，主要研究方向为数据挖掘理论及其应用。
