- 1 -
中国科技论文在线
基于相对粒度的决策表知识约简算法#
刘艳红，张静，谢刚**
基金项目：国家自然科学基金(60975032)
作者简介：刘艳红(1985-)，女，在读研究生，主要研究方向：智能控制，故障诊断
通信联系人：谢刚(1972- )，男，教授，主要研究方向：模式识别与智能信息处理，智能控制理论与应用
（太原理工大学信息工程学院，太原 030024）
摘要：本文基于知识粒度的定义，分析决策表中知识的不确定性，给出了决策属性集相对于
条件属性集的相对粒度以及属性重要性的概念，进而通过相对粒度定义了决策表的一致性。
在此基础上，设计了一种基于相对粒度的决策表知识约简算法，用于约简决策表中的冗余属
性和冗余属性值，从而得到决策表的最小知识约简。实例验证表明该算法时间复杂度相对较
低，能有效地处理不一致决策表，有利于提高系统的决策效率。
关键词：粒计算；决策表；相对粒度；知识约简
中图分类号：TP18，TP206
Knowledge Reduction Algorithm Based on Relative
Granularity in Decision tables
Liu Yanhong, Zhang Jing, Xie Gang
(College of Information Engineering, Taiyuan University of Technology, Taiyuan 030024)
Abstract: In this paper, the uncertainty of knowledge in decision tables based on theory of knowledge
granularity is analyzed. We introduced the concepts of importance of attribute and relative granularity
which is used for measuring the discernibility of decision attributes set relatives to condition attributes
set in the universe, and then definite consistent decision table by relative granularity. On the basis of
this theory, we propose a knowledge reduction algorithm based on relative granularity which is used to
reduce the redundant attribute and attribute value, and then attain the smallest knowledge reduction of
decision table. By analyzing the example, the algorithm is proved that it’s time complexity is relatively
low, it can effectively deal with inconsistent decision tables, and it help to improve the efficiency of the
system.
Keywords:Granular Computing (GrC);Decision tables;Relative granularity;Knowledge Reduction
0 引言
粒计算(Granular Computing, GrC)作为词计算理论、粗糙集理论和商空间理论的超集，
覆盖了所有有关粒度的理论、方法和技术，是当前计算机智能研究领域中模拟人类思维和解
决复杂问题的新方法，是复杂问题求解、海量数据挖掘、模糊信息处理的有效工具[1]。
属性约简是粗糙集理论的核心内容之一，然而寻求所有约简或最小约简已被证明是
NP-Hard 问题[2]，因此，寻求快速、高效、完备的属性约简算法仍是当前研究的核心领域之
一。现有的属性约简方法主要有基于区分矩阵的属性约简方法[3-8]、基于正域的属性约简方
法[9-13]以及基于信息熵的属性约简方法[14-18]。
基于区分矩阵的属性约简方法只是计算决策表的区分矩阵的时间复杂度和空间复杂度
就为 O(|C||U|2)，因此这种方法不仅耗时，而且要消耗大量的空间[8]；
文[13]采用基数排序的思想，设计了一个新的求划分 U/C 的算法，将其时间复杂度降为
O(|C||U|)，并基于正域提出了一个时间复杂度为 max(O(|C||U|), O(|C|2|U/C|))快速属性约简算
- 2 -
中国科技论文在线
法，通过实验表明了该算法不仅具有高效性而且能处理大型决策表。
文[18]通过引入简化决策表的定义，设计了一个基于信息熵的快速属性约简算法，其时
间复杂度降为 max(O(|C||U|), O(|C|2|U/C|))。结果表明算法具有高效性，且能处理大型决策表。
上述约简算法都是以属性重要性为启发式信息寻找决策表的最优或次优约简，各算法在
不同程度上对属性重要性的度量方法及约简方法进行了改进。但仍存在一定得不足之处：基
于区分矩阵的约简方法需要消耗大量的时间和空间；在处理不一致决策表时，基于正域和现
有的基于信息熵的约简方法无法等价的表示知识约简，不能保证决策表的分类能力不变。
针对以上问题，本文提出了一种基于相对粒度的决策表知识约简算法，进行属性约简和
属性值约简，旨在得到决策表的最小约简集合。
1 粒计算相关理论
粒计算中最基本的概念是粒、粒化和粒度。人类在处理和解决大量复杂信息的问题时，
会将大量复杂信息按其各自的特征和性能划分成若干较为简单的子块，这种子块称为信息
粒，这种处理的过程称为信息粒化。信息粒度是对信息和知识细化的不同层次的度量。粒计
算的知识约简就是保持原有的分类能力不变的前提下尽可能地删去不相关或冗余的属性和
属性值，并将约简后的信息重组，并产生新的决策表[19]。下面给出了粒计算中的相关知识。
定义 1：信息系统[20]
四元组 S=(U, A, V, f )是一个信息系统，其中 U 是论域，A 是属性集合，对属性 a∈A 有
a：U→Va，其中 Va被称为属性 a 的值集；V=∪a∈A Va是属性集 A 的值区域，f :U×A→V 是一
个信息函数，指定了 U 中每一个对象 x 的属性值。
定义 2：在信息系统 S=(U, A, V, f )中任意属性子集 P⊆A 决定了一个二元不可区分关系，
IND(P)={(x, y)∈(U×U) | ∀ p∈A, f(x, p)=f(y, p)}。关系 IND(P)确定了一个划分，用 U/IND(P)
表示，简记为 U/P。U/P 中任何元素[x]P={ y | f(x, a)=f(y, a),∀ a∈P }称为等价类。
性质 1：设 P, Q 为论域 U 上的两个属性集合，则有 U/(P∪Q)=U/P∩U/Q
性质 2：在信息系统 S=(U, A, V, f )中，P⊆ A，a∈A\P, 则有：
U/(P∪a)=∪{X/{a} | ∀X∈U/P}
性质 2 表明划分 U/(P∪a)可以由属性 a 对划分 U/P 中的每个等价块进行再划分得到。
定义 3：知识粒度[21]
给定信息系统S=(U, A, V, f )，R⊂A且U/R={X1, X2, …Xj, …, Xm }，则R的知识粒度GD(R)
定义为：
2
2
1
( )
m
i
i
X
GD R
U=
= ∑
显然，1/ ( ) 1U GD R≤ ≤ 。知识的粒度可以表示知识的分辨能力，GD(R)越小，知识
的分辨能力越强。
定理 1：在信息系统 S=(U, A, V, f )中，P⊆A，则 IND(P)=IND(A)的充分必要条件为
GD(P)=GD(A)。
定义 4：决策表
设 S=(U, A, V, f )是一个信息系统，如果C, D⊆A是A的两个子集，且A=C∪D, C∩D=Φ，
分别称 C 和 D 为 A 的条件属性和决策属性，如此的信息系统被称为决策表。记为 T=(U, A, C,
D)。不可分辨关系 IND(C)和 IND(D)的等价类分别称作条件类与决策类，IND(C)也可记作
- 3 -
中国科技论文在线
U/C，IND(D)也可记作 U/D。
定义 5：相对粒度[22]
设 U 是一个论域，P, Q 为定义在 U 上的两个等价关系簇，则知识 Q 相对于知识 P 的相
对粒度为定义为：
( | ) ( ) ( )GD Q P GD P GD P Q= − ∪
其中，GD(P)表示属性集 P 的知识粒度。
相对粒度 GD(Q|P)反映了知识 Q 相对于知识 P 在论域 U 上的分辨能力，即 GD(Q|P)越
小，表明 Q 相对于 P 对 U 中对象的分辨能力就越弱；反之，若 GD(Q|P)越大，表明 Q 相对
于 P 对 U 中对象的分辨能力就越强。
定理 2：设P1, P2, Q为论域U上的等价关系簇，且U/P1={X1, X2, …, Xn }, U/P2={X1, X2, …,
Xi-1, Xi+1, …, Xj-1, Xj+1, Xn , Xi∪Xj}, U/Q={Y1, Y2, …, Ym }，其中 U/P2是将 U/P1中的任意两个等
价块(Xi和 Xj)合并而得到的划分，则有 GD(Q | Pl)≤GD(Q | P2)。
定理 2 表明，在对 P1中任意两个等价块合并后，相对粒度单调增加。特别地，当 Xi∪
Xj 时，有 GD(Q | Pl)=GD(Q | P2)。
推论 ：在决策表 T=(U, A, C, D)中，对∀ ai∈C, i=1, 2, …, m(m=|C|)，则有：
1 1 2 1 2( |{ }) ( |{ } { }) ( |{ } { } { }) ( | )mGD D a GD D a a GD D a a a GD D C≥ ≥ ≥ =∪ ∪ ∪… …
定理 3：在决策表 T=(U, A, C, D)中，对∀ a∈C，若 GD(D|C)=GD(D|C\{a})，则称 a 是 C
相对于决策属性集 D 所不必要的，否则成 a 是必要的。
定义 6：属性重要性 1
在决策表 T=(U, A, C, D)中，对于∀ a∈C，定义属性 a 在 C 中相对于决策属性集 D 的重
要性为：
( , , ) ( | \{ }) ( | )Sig a C D GD D C a GD D C= −
定义 7：属性重要性 2
在决策表 T=(U, A, C, D)中，令 R⊆C，则定义∀ a∈C\R 关于属性集 R 对 D 的重要性为：
( , , ) ( | ) ( | )Sig a C D GD D R GD D R a= − ∪
Sig(a, R, D)表明属性 a 关于属性集 R 对 D 的重要性是由 R 中添加属性 a 后所引相对粒
度变化的大小来度量的，即 GD(D|R∪{a})越小，则 Sig(a, R, D)的值就越大明属性 a∈C\R 关
于属性集 R 对 D 就越重要。
性质 3：属性 a 为 C 中相对于 D 的必要属性，当且仅当 Sig(a, C, D)>0。
性质 4：条件属性 C 相对于决策属性 D 的核集 CoreC(D)={a∈C | Sig(a, C, D)>0}。
定义 8：设属性集 P⊆C，若∀ a∈P，有 Sig(a, P, D)>0，则称 P 为独立的。
定理 4：在决策表 T=(U, A, C, D)中，P⊆C，若 GD(D|P)=GD(D|C),且 P 独立，则称 P
为 C 的 D 相对约简。
定义 9：一致决策表
在决策表 T=(U, A, C, D)中，如果 GD(D|C)=0，即 GD(C)= GD(C∪D)时，决策表是一致
的（或称决策表是相容的）。
定理 5：若决策表 T=(U, A, C, D)是一致的，即 POSC(D)=U。若 P⊆C，则有：
POSP(D)= POSC(D)⇔ GD(D|C)=GD(D|P)
定理 6：假设在条件属性 C 中的两个属性 a, b。如果 U|(C-a)={Yi}且 U|D={Xj}且 Yi⊆ Xj，
那么 Yi中的条件属性 a 的值可以省去。同理，如果 U|(C-b)={Yk}且 U|D={Xj}，且 Yk⊆ Xj，那
- 4 -
中国科技论文在线
么 Yk中的条件属性 b 的值可以省去[22]。
2 基于相对粒度的决策表知识约简算法
输入：决策表 T=(U, A, C, D)，C 为条件属性集，D 为决策属性集；
输出：决策表的一个最小知识约简。
Step 1：合并相同的行，通过计算属性的重要性对条件属性 C 中的冗余属性进行约简，
得到条件属性相对于决策属性的核 C0；
①求条件属性 C 和决策属性 D 导出的条件类 U/C 和决策类 U/{C∪D}，计算 GD(D|C)；
②对每个属性 ci∈C，计算 GD(D|C-{ci})，进而计算属性 ci在 C 中相对于决策属性集 D
的重要性 Sig(ci, C, D)；
③如果 Sig(ci, C, D)>0，则 ci∈C0，令 R=C0；
Step 2：如果 GD(D|R)=GD(D|C)转到 Step 7，否则继续执行；
Step 3：B=C－R, 对每个属性 bj∈B，执行 Step 4~Step 5；
Step 4：根据划分 U/R 计算 U/{R∪{ bj }},U/{R∪{ bj }∪D}，进而计算 GD(D|R∪{ bj })；
Step 5：选择使 GD(D|R∪{bj})最小的属性 bj （若满足条件的属性有多个，则选择使 GD(R
∪{bj})最小的属性 bj，若使 GD(R∪{bj})最小的属性也不止一个，则将所有取值最小的）作
为扩展属性，令 R=R∪{bj}；
Step 6：转到 Step2；
Step 7：对每个属性 rk∈R，从 R 的尾部开始，从后往前进行判，看其是否可以消除：
①如果 rk∈C0，则 rk之前的属性都是不可消除的；
②否则，若 GD(D|R)=GD(D|R-rk)，则说明属性 rk是可以消除的，从 R 中把 rk删除；
Step 8：合并相同行，R 为条件属性集的最小属性集；
Step 9：进行属性值的约简。合并相同行，若某一行所有条件属性值均可约去，则删除
该行；若某行不可约简的条件属性值和另一行该属性属性值相同，则删除该行；
Step 10：输出 R 为决策表的一个最小知识约简。
该算法以相对核为起点， Step 5 确保一定能找到 C 的某个子集，满足
GD(D|R)=GD(D|C)，R 中排列在最前面的是核属性，然后是按照属性的重要度而选择的属性，
重要度越低的属性， 越靠近的末端。当决策表条件属性的数目越多，即决策表的规模越大
时，该步的优越性越明显。Step 7 通过一个后向删除的过程将 R 中可省的属性删除，重要度
越低的属性越早被处理，从而确保处理后的 R 中每个属性都是不可省的，故最后得到的 R
一定是约简， 所以该算法对于计算条件属性集的某个约简来说是完备的。该算法总的时间
复杂度为 O(|C||U|2)[22]。
3 实例分析
例 1：表 1 为一个不一致决策表 S=(U, C, D, V, f )，其中 U={x1, x2,…, x10}，条件属性 C={a,
b, c, d, e}, 决策属性 D={f}。
Step 1：①U/C={{x1}, {x2, x4},{x3, x9},{x5}, {x6},{x7, x10} {x8},}
U/{C∪D}={{x1},{x2}…{x10}}
GD(D|C)= GD(C)- GD(C∪D)=(1+4+4+1+1+4+1)/102-10/102=6/100
②U/{C/{a}}={{x1}, {x2, x4},{x3, x9},{x5}, {x6},{x7, x10} {x8},}
U/{C/{a}∪D}={{x1},{x2}…{x10}}
- 5 -
中国科技论文在线
GD(D|C-{a})= GD(C/{a})- GD(C/{a}∪D)= 16/102-10/102=6/100
Sig(a, C, D)= GD(D|C-{a})- GD(D|C)=0
同理得，GD(D|C-{b})=16/102-10/102=6/100; GD(D|C-{c})=18/102-12/102=6/100;
GD(D|C-{d})=16/102-10/102=6/100; GD(D|C-{e})=28/102-16/102=12/100;
Sig(b, C, D)=0; Sig(c, C, D)=0; Sig(d, C, D)=0; Sig(e, C, D)= 6/100;
③于是，得到条件属性相对于决策属性的核 C0={e}，令 R=C0={e}；
表 1 不一致决策表
条件属性 C 决策属性 D 论域
U a b c d e f
x1
x2
x3
x4
x5
x6
x7
x8
x9
x10
0
0
1
0
0
1
0
1
1
0
0
1
1
1
0
1
1
0
1
1
0
1
0
1
1
0
1
1
0
1
0
1
1
1
0
1
1
1
1
1
1
0
1
0
1
0
1
1
1
1
0
1
1
0
0
1
1
1
0
0
Step 2：计算 GD(D|R)=26/100≠GD(D|C)，继续执行；
Step 3：B=C－C0={a, b, c, d };
Step 4：根据性质 2，U/{R∪{bi}}=∪{X/{a}}，计算如下：
U/{R∪{a}}={{x1, x5, x7, x10}, {x2, x4},{x3, x8, x9},{x6}};
U/{R∪{a}∪D }={{x1, x5, x10}, {x2}, {x3, x8}, {x4},{x6},{x7},{x9}};
GD (D|R∪{a})= GD (R∪{a})-GD (D∪R∪{a})=12/100;
同理得，GD (D|R∪{b})=16/100; GD (D|R∪{c})=14/100; GD (D|R∪{d})=16/100;
Step 5：选择 GD(D|R∪{bi})最小的属性 a 作为扩展属性加入到 R 中，即 R=R∪a={a, e}；
Step 6：转到 Step 2，计算 GD(D|R)=12/100≠GD(D|C)，返回 Step 3；
B=C－C0={b, c, d }，计算如下：
GD (D|R∪{b})=6/100; GD (D|R∪{c})=8/100; GD (D|R∪{d})=8/100;
选择 GD(D|R∪{bi})最小的属性 b 作为扩展属性加入到 R 中，即 R=R∪b={a, e, b}；
计算 GD(D|R)=6/100=GD(D|C)；
Step 7：对每个属性 rk∈R，从 R 的尾部开始，从后往前进行判，看其是否可以消除：
b∉C0，计算 GD(D|R)≠GD(D|R-b)，属性 b 不可消除；
e∉C0，计算 GD(D|R)≠GD(D|R- e)，属性 e 不可消除；
a∈C0，属性 a 不可消除；
Step 8：约简决策表条件属性中的冗余属性值
根据定理 6：U/{R-{a}}={{x1, x7}, {x2, x4, x5}, {x3, x5, x8, x9}}={X1, X2, X3};
U/D={{x1, x4, x8, x9}, {x2, x3, x5, x6, x7}}={Y1,Y2};
Xi⊄Yj, 因此属性 a 对应的属性值都不可约简；
同理得，属性 b 中 x5对应的属性值可以约简；
属性 e 中 x1和 x7对应的属性值可以约去。
Step 9：输出最小知识约简，如表 2，其中*号表示约简的属性值。
- 6 -
中国科技论文在线
表 2 约简后的决策表
条件属性 C 论域
U a b e
决策属性 D
f
x1
x2
x3
x4
x5
x6
x7
x8
x9
0
0
1
0
1
0
1
1
0
0
1
1
1
*
1
0
1
1
*
0
1
0
0
1
*
1
1
0
1
1
0
1
1
1
0
0
根据基于正域的属性约简方法对决策表 1 进行约简得到的属性约简集为{ a, c, d, e}，而
根据相对粒度的约简方法得到的属性约简集合为{a, b, e}，通过比较，基于相对粒度的约简
方法可以有效地获得决策表的最小约简属性集。
例 2：表 3 是根据文[21]白天天气分类情况的决策表（一致决策表）
表 3 白天天气分类情况决策表
条件属性 C 决策属性 D 论域
U Outlook Temperature Humidity Windy 分类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
sunny
sunny
overcast
rain
rain
rain
overcast
sunny
sunny
rain
sunny
overcast
overcast
rain
hot
hot
hot
mild
cool
cool
cool
mild
cool
mild
mild
mild
hot
mild
high
high
high
high
normal
normal
normal
high
normal
normal
normal
high
normal
high
false
true
false
false
false
true
true
false
false
false
true
true
false
true
N
N
P
P
P
N
P
N
P
P
P
P
P
N
利用本文给出的算法对表 1 进行约简，得到最小知识约简，如表 2。
表 2 约简后的决策表
条件属性 C 决策属性 D论域
U Outlook Humidity Windy 分类
1
2
3
4
5
sunny
overcast
rain
rain
sunny
high
*
*
*
normal
*
*
false
true
*
N
P
P
N
P
采用本文提出的约简算法，对决策表 3 进行约简得到的属性约简集为{Outlook, Humidity,
Windy}，然后进一步进行属性值约简，约去冗余的属性值，从而保证了决策算法的最小化。
在约简的过程中，当出现两个及以上属性使得 GD(D|R∪{bi})和 GD(R∪{bj})都相等时，
将它们同时作为扩展属性加入到 R 中，这种处理方法在大型决策表中可以快速的得到约简
结果，虽然 Step 7 通过一个后向删除的过程将 R 中可省的属性删除，保证了 R 是唯一的最
- 7 -
中国科技论文在线
小约简。但是它仍然存在一定得不足之处，即出现这种情况时，可能导致约简后的属性集与
属性在决策表中的排列顺序有关。
4 结论
本文在知识粒度的基础上，基于相对粒度、属性重要性的定义以及属性值约简的定理，
针对相对粒度随知识粒度增大而单调增加的特点，设计了一种基于相对粒度的决策表知识约
简算法，用于约简条件属性中的冗余属性和冗余属性值。理论分析和实例验证表明该算法可
以弥补基于正域约简方法不能直接处理不一致决策表的不足，用于约简时无需区分一致决策
表和不一致决策表，有助于提高系统决策效率，时间复杂度较低。
[参考文献]
[1]苗夺谦,王国胤等.粒计算：过去、现在与展望[M].科学出版社. 2007.
[2]Wang S K M, Ziarko W. On optimal decision rules in decision tables [J]. Bullet in of Polish accademy of
Science, 1985, 333:693-696.
[3]Wang Jue, Miao Duoqian. Analysis on attribute reduction strategies of rough set[J].Journal of Computer
Science and Technology,1998,13(2):189-194.
[4]Wang Jue, Wang Ju. Reduction algorithms based on discernibility matrix: the ordered attributes method [J].
Journal of Computer Science and Technology, 2001, 16(6):489-504.
[5]陶志,刘庆拯,李卫民.一种基于改进区分矩阵的属性约简算法[J].计算机工程与应用,2007,43(32): 83-85.
[6]蒋瑜,王鹏,王燮等.基于差别矩阵的属性约简完备算法[J].计算机工程与应用 2007,43(19): 185-187.
[7]王柯,朱启兵.一种基于差别矩阵的启发式属性约简算法[J].计算机工程与科学,2008,30(6):73-75.
[8]徐章艳,杨炳儒,宋威等.一种快速计算 HU 差别矩阵的属性约简算法[J].小型微型计算机系统,
[9]Hu X H, Cercone N. Learning in relational databases: A rough set approach [J]. International Journal of
Computational Intelligence, 1995, 11(2):323-338.
[10]Jelonek J, Krawiec K, Slowinski R. Rough set reduction of attributes and their domains for neural networks [J].
International Journal of Computational Intelligence, 1995, 11(2):339-347
[11]Guan J W, Bell D A. Rough computational methods for information systems [J]. Artificial Intelligences, 1998,
105(1-2):77-103.
[12]刘少辉,盛秋戬,吴斌等.Rough 集高效算法的研究[J].计算机学报,2003,26(5):524-529.
[13]徐章艳,刘作鹏,杨炳儒等.一个复杂度为 max(O(|C||U|),O(|C|2|U/C|))的快速属性约简算法[J].计算机学报,
2006, 29(3):391-399.
[14]于洪,杨大春,吴中福等.基于信息熵的一种属性约简算法[J].计算机工程与应用,2001,37(17):22-23.
[15]王国胤,于洪,杨大春.基于条件信息熵的决策表约简[J].计算机学报,2002,25(7):759-766.
[16]刘启和, 李凡,闵帆等.一种基于新的条件信息熵的高效知识约简算法[J].控制与决策,2005,20(8):878-882.
[17]陈杰,蒋祖华,赵云松.基于扩展的信息熵的决策表属性约简算法[J].计算机工程与应用, 2007, 43(7):
167-169.
[18]徐章艳,侯伟等.一个有效的基于信息熵的启发式属性约简算法[J].小型微型计算机系统. 2009, 30(9): 5-6
[19]Pawlak Z. Rough sets[J]．International Journal of Information and Computer Sciences, 1982, 11(5): 341-356
[20]刘清. Rough 集及 Rough 推理[M].北京:科学出版社, 2001.
[21]苗夺谦,范世栋.知识粒度的计算及其应用[J].系统工程理论与实践, 2002(1):48-56
[22]史进玲. 基于粒计算的决策表属性约简与规则提取研究[D].河南师范大学, 2009.
[23]陈泽华.粒计算及人工选择算法理论研究[D].太原理工大学. 2007.
