2008年 3月
March 2008
计 算 机 工 程
Computer Engineering
第 34卷 第 6期
·博士论文· 文章编号：1000—3428(2008)06—0022—03 文献标识码：A 中图分类号：TP391
决策信息系统中挖掘全部决策规则的算法
王树锋，吴耿锋，潘建国
(上海大学计算机学院，上海 200072)
摘 要：在粗糙集理论的基础上，对决策信息系统中边界区域的数据进行研究，提出一种从边界区域数据中挖掘决策规则的算法——近似
序列决策规则挖掘算法。在 16个 UCI数据集上的测试表明，该算法在规则的准确度和平均前件长度 2个指标上优于 ID3算法，能简洁、
高效地挖掘出决策信息系统中的全部决策规则，为挖掘未知知识提供了新的思路。针对挖掘出的全部决策规则，提出新的确定性度量和一
致性度量指标，用以准确地反映决策规则的性能。
关键词：决策信息系统；粗糙集边界区域；决策规则；规则度量指标
Algorithm for Extracting All Decision Rules from Decision
Information Systems
WANG Shu-feng, WU Geng-feng, PAN Jian-guo
(School of Computer, Shanghai University, Shanghai 200072)
【Abstract】Extraction Algorithm of Approximate Sequence Decision Rules (EAASDR) extracting decision rule from border region of rough set is
proposed. It can extract all knowledge from decision information systems. Comparison tests between EAASDR and ID3 in 16 UCI data sets show
that the algorithm is prior to ID3 in the accuracy of rule set and the average condition number of rule sets. A new rule measure criterion of certainty
and consistency is proposed in order to accurately reflect the performance of all decision rules extracted from decision table.
【Key words】decision information system; border region of rough set; decision rule; rule measure criterion
粗糙集理论 [1-3]处理的对象是一个具有对象和属性关系
的数据表，称为决策信息系统。该理论建立在分类的基础上，
将知识(决策规则)理解为对数据的划分，由在特定空间上的
上近似集和下近似集构成。上下近似集之间的差集被认为是
无法确认的数据，称为边界区域。对于海量数据，为了更加
精确地描述知识，边界区域的数据一般不应忽略。基本的思
路是先求出原决策信息系统的某个约简，将该约简下的数据
从系统中删除，得到一个新系统。对该新决策信息系统再求
得新约简，将该新约简下的数据从新系统中删除，得到一个
新的决策信息系统，重复上述过程，直到系统不能有其他约
简或系统中的数据全部能分类为止。本文提出一个近似序列
决策规则挖掘算法 (Extraction Algorithm of Approximate
Sequence Decision Rules, EAASDR)，处理粗糙集边界中的数
据，给出了新的决策规则度量标准，用来评价挖掘出的全部
决策规则。
1 粗糙集中边界数据的处理
给定决策信息系统 ，对于任意 ，有
一个满足偏序关系
( , )S U C D= ∪ X U⊆
1 2 (n i )R R R R ∈; ;"; R 的等价关系族
1 2{ , , , }nP R R R= " 。定义 iPX R X=
JG ，称为 的X P 上近似集。
定义
1
n
i i
i
PX R X
=
= ∪JG ，其中， 11
1
;
i
i k
k
kX X R X
−
=
= = − ∪X X ，称为 的X
P 下近似集。集合 称为 的( )Pbn X PX PX= −
JG
JG X P 边界域。由
P 形成的近似分类结果和 的协调度定义为X ( , ) PXH P X
X
= JG ，
其中，• 表示集合的基数，显然 。当( , ) [0,1]H P X ∈ ( , ) 0H P X =
时，表示近似分类结果和待分类对象最不协调；当 ( , ) 1H P X =
时，表示近似分类结果和待分类对象完全协调，即现有的知
识完全可以精确地描述待分类对象，在进行近似分类时能把
待分类对象完整地分类。
采用近似分类方案的结果，把先验知识 分解为不同近
似分类(处在不同粒度层次)的子类的并集 ，
第 次已能够最为精确地表示先验类 ，每一个子集都具有
不同的粒度(约简属性)，是在相应粒度下能够精确表达知识
的最大子集。
X
1 2 kX X X X= ∪ ∪"∪
k X
2 近似序列决策规则挖掘算法
一般描述
算法的一般描述如下：
输入 决策信息系统 ( , )S U C D= ∪
输出 分类结果规则集
(1) 给 定 决 策 信 息 系 统 ， 计 算 出 相 对 核
；/*通过计算各条件属性对决策属性的重要性 ，
得到相对核*/
( , )S U C D= ∪
( )DCORE C
'( )CD Cσ
(2)If ( )DCORE C φ≠ ，Then 初始属性集 1 ( )DP CORE C= and
集合 1E P=
Else 初始属性集 1 1{ }P c= and 1E P= ；/*对 ，计算
和
c C∀ ∈ c
D 之间的依赖度 [ ]( )c Dγ ，选择 ，作为初始
属性集*/
1[ ] [ ]
max{ ( ), }c cr D c Cγ = ∈
}(3)计算决策分类 ； 1 2/ { , , , dU D Y Y Y= "
基金项目：上海市科委重点攻关基金资助项目(035115028)
作者简介：王树锋(1968－)，男，博士研究生，主研方向：人工智能，
知识管理；吴耿锋，教授、博士生导师；潘建国，博士研究生
收稿日期：2007-04-23 E-mail：xueaimin7000@
—22—
(4)等价关系族 1{ }P P= , , ，动态分类结果 1i = *U U= B φ= ，
决策规则集 Rule φ= ；
(5)计算 ； * 1 2/ ( ) { , , ,i i i iU IND P X X X= " }k
}}(6) ,' *{ / ( ) | , / , {1,2, ,k i k j jB X U IND P X Y whereY U D j d= ∈ ⊆ ∈ ∈ "
'Rule φ= , 。输出决策规则'kX B∀ ∈ ' { ( ) ( )iP k D j }Rule des X des Y= → ，其
中， 且 ；/jY U D∈ j kY X⊇ 'Rule Rule Rule= ∪ ； 'B B B= ∪ ；
(7) *
X B
B x
∈
= ∪ ；
If *B U= Then goto (8)
Else { ；i i ；对 ，计算 关于* * *U U B= − 1= + c C E∀ ∈ − c E
对 D 的 重 要 性 ， 令({ } ) ({ })c E D cσ ∪ 2({ } ) 2({ })c E D cσ =∪
，则({ } )max{ ({ }), }c E D c c C Eσ ∈ −∪ 1 2{ }i iP P c−= ∪ ，并将 iP 归入 P 中
成为其中的一个等价关系，goto (5);}
(8) B 即为动态分类结果， Rule 即为决策规则。算法结束。
算法分析
该算法通过计算决策表的相对核或条件属性对决策属性
的依赖度，找到初始属性集(步骤(1)、步骤(2))，根据初始属
性集，计算决策表的等价类，形成信息系统的一个约简(步
骤(5))，得到相应的决策规则(步骤(6))。如果决策规则没有覆
盖信息系统中的全部样本，就将规则中已经包含的样本及其
属性从原信息系统中删除(步骤(7))，形成一个新的信息系统，
在新信息系统下继续进行同样的规则抽取过程，直到所抽取
的规则中包含了信息系统的全部样本和属性。
在粗糙集理论中，信息系统的一个约简就是寻找样本集
合中无矛盾的样本，进行属性约简时，每一个属性的增减都
会影响知识粒度的变化及其近似分类的结果。从信息系统中
抽取知识，就是从复杂知识表示中删除例外的知识，得到“不
同简洁程度”的知识，也就是不同粒度的知识[4]。该算法包
含了粒度计算的思想，让知识粒度在动态变化中逐渐细化[5]。
实际上，知识就是“规则＋例外”，知识粒度依赖于例外
的数量，例外越少，知识越精确，知识粒度的动态细化意味
着知识的简洁程度(精度)在变化，因此，该算法具有变精度
粗糙集模型[6-7]的思想，突破了Pawlak模型分类是完全确定的
限制，使分类具有某种程度的“包含”和“属于”特性。
Pawlak模型处理的对象是已知的，从模型中得到的结论
仅适用于这些对象，基于变精度粗糙集模型的思想，可以将
小规模对象集中得到的结论应用到大规模数据集中去，因此，
该算法具有一定的泛化能力，它不像使用变精度粗糙集模型
那样，需要做大量的计算工作。
示例验证
用关于肺炎诊断的例子来表示算法的执行，抽取该决策
信息系统中的全部决策规则。肺炎诊断表如表 1所示。
表 1 肺炎诊断表
病例号 发烧 咳嗽 X光成像 血沉 听诊 诊断
1 高 剧烈 片状 正常 水泡声 肺炎
2 中 剧烈 片状 正常 水泡声 肺炎
3 低 轻微 点状 正常 干鸣声 肺炎
4 高 中度 片状 正常 水泡声 肺炎
5 中 轻微 片状 正常 水泡声 肺炎
6 无 轻微 索条状 正常 正常 肺结核
7 高 剧烈 空洞 快 干鸣声 肺结核
8 低 轻微 索条状 正常 正常 肺结核
9 中 轻微 点状 快 干鸣声 肺结核
10 低 中度 片状 快 正常 肺结核
11 低 轻微 点状 正常 干鸣声 肺炎
12 高 剧烈 空洞 快 干鸣声 肺结核
条件属性集 ，其中， a代表发烧； b代表
咳嗽； 代表 光成像； 代表血沉； 代表听诊；决策属
性集
{ , , , , }C a b c d e=
c X d e
{ }D f= ， f 代表诊断。 , / {{1,2,3,4,5,11},{6,7,8,9,10,12}}U D =
/ {{1},{2},{ 。 3,11},{4},{5},{6},{7,12},{8},{9},{10}}U C =
算法执行过程如下：
(1)求相对核 ，其计算公式为( )DCORE C '( ) ( )CD CC Dσ γ= −
，其中， 。经计算， , ' ( )C C Dγ − 'C C⊆ ({ }) 0CD aσ = ({ }) 0CD bσ = ,
({ }) 0CD cσ = , ({ }) 0CD dσ = , ，因此，({ }) 0CD eσ = ( )DCORE C φ= 。
(2) 计 算 各 属 性 和 D 间 的 依 赖 度 。 其 计 算 公 式 为
，其中， 。经计算， , ' '{ }( ) | ( ) | / | |C CD pos D Uγ = 'C C⊆ { }( ) 1/12a Dγ =
{ }( ) 0b Dγ = , , , 。 , { }( ) 4 /12c Dγ = { }( ) 4/12d Dγ = { }( ) 7 /12e Dγ = 1 { }P e=
1E P= 。
(3) / {{1,2,3,4,5,11},{6,7,8,9,10,12}}U D = 。
(4) 1{ }P P= , 1i = , *U U= , B φ= , Rule φ= 。
(5) 。 1/ {{1,2,4,5},{3,7,9,11},{6,8,10}U P = }
(6)可得 {{1,2,4,5,},{6,8,10}}B = ，决策规则
{ }{ ({1,2,4,5}) ({1,2,3,4,5,11})e DRule des des= →
{ }({6,8,10}) ({6,7,8,9,10,12})}e Ddes des→
如果只用粗糙集的上、下近似，只能抽取出这 2条规则，
采用本算法，还可在边界区域中继续抽取规则，直到抽取出
全部规则。
(7) {1,2,4,5,6,8,10}
x B
x U
∈
= ≠∪ ，执行 else 语句，计算剩下的属
性 a,b,c,d关于 e对 D 的重要度。经计算，
({ } { } { , } { }({ }) ( ) ( ) 5 /12a e D a e ea D Dσ γ γ= − =∪
({ } { } { , } { }({ }) ( ) ( ) 2 /12b e D b e ea D Dσ γ γ= − =∪
({ } { } { , } { }({ }) ( ) ( ) 2 /12c e D c e ea D Dσ γ γ= − =∪
({ } { } { , } { }({ }) ( ) ( ) 5 /12d e D d e ea D Dσ γ γ= − =∪
由于 a,d 关于 e 对 D 的重要度相等，因此任意选择其中
一个属性 a进行计算。 2 { , }P a e= , 1 2{ , }P P P= ，转到步骤(5)。
重复执行可得
{{1,2,4,5},{3,11},{6,8,10},{7,12},{9}}B =
{ }
{ }
{ , }
{ , }
{ , }
{1: ({1,2,4,5}) ({1,2,3,4,5,11}),
2 : ({6,8,10}) ({6,7,8,9,10,12}),
3 : ({3,11}) ({1,2,3,4,5,11}),
4 : ({7,12}) ({6,7,8,9,10,12}),
5 : ({9}) ({6,7,8,9,1
e D
e D
a e D
a e D
a e D
Rule des des
des des
des des
des des
des des
= →
→
→
→
→ 0,12})}
由于此时
x B
x U
∈
=∪ ，因此算法结束。最终抽取出的全部
规则集 Rule如表 2所示。
表 2 抽取出的全部决策规则
规则号 发烧 听诊 诊断
1 水泡声 肺炎
2 干鸣声 肺炎
3
低
低
低 正常 肺结核
4 高 干鸣声 肺结核
5 中 干鸣声 肺结核
按照上述步骤，抽取得到了全部决策规则。对表 1 中的
数据，采用属性约简和值约简结合的方法可以抽取出相同的
规则，表明该算法运行的结果是正确可信的。该算法将属性
约简和值约简方法统一起来，是挖掘全部规则的新思路。
模拟实验
模拟实验在 UCI的 16个数据集上进行，用 EAASDR和
ID3 算法作对比实验。对每一个数据集，75%的数据用于训
练算法产生规则，其余 25%用作测试。规则集的准确度和复
—23—
杂度 2 个指标作为标准评价算法。准确度用测试集实验得到
的规则的准确度来描述，复杂度包括规则的个数和每个规则
的平均前件(条件)个数这 2个指标。
表 3 列出了 2 个算法在准确度和平均数 2 个指标上的数
据。结果表明，EAASDR 算法在 11 个数据集上的性能优于
ID3。对于抽取的规则集的数量，ASDREA算法要比 ID3多，
这是因为用 EAASDR抽取出了数据集中的全部规则，而 ID3
算法则进行了一定的修剪。表 4列出了 EAASDR在训练集、
测试集上规则的平均前件个数和 ID3 平均前件个数。虽然在
某些数据集上，EAASDR算法抽取的规则前件比 ID3要多，
但其平均值优于 ID3。
表 3 规则平均准确度和规则平均数的比较
Average accuracy/(%) Average no. of rules Data set
EAASDR ID3 EAASDR ID3
Arrhythmia ± ± ± ±
Breast-cancer ± ± ± ±
Breast-W ± ± ± ±
Dermatology ± ± ± ±
Echocardiogram ± ± ± ±
Heart-C ± ± ± ±
Heart-H ± ± ± ±
Hepatitis ± ± ± ±
Horse-colic ± ± ± ±
Hypothyroid ± ± ± ±
Liver-disorders ± ± ± ±
lymphography ± ± ± ±
Pima-Indians ± ± ± ±
Primary-tumors ± ± ± ±
Sick ± ± ± ±
Thyroid-benchmark ± ± ± ±
average ± ± ± ±
表 4 规则前件平均长度的比较
Average no. of condition accuracy Data set
EAASDR (training) EAASDR (test) ID3
Arrhythmia
Breast-cancer
Breast-W
Dermatology
Echocardiogram
Heart-C
Heart-H
Hepatitis
Horse-colic
Hypothyroid
Liver-disorders
lymphography
Pima-Indians
Primary-tumors
Sick
Thyroid-benchmark
average
3 度量全部决策规则性能的新指标
利用 EAASDR 算法可以抽取出决策信息系统中的全部
决策规则，对这些决策规则如何度量和评价是要研究的另外
一个问题。本文将传统的决策规则确信度和支撑度进行扩充，
形成了度量全部决策规则的 2 个新指标：总体确信度度量 C
和总体支撑度度量 A。
修正决策规则评价指标的依据[1,8]
设 是 一 个 决 策 信 息 系 统 ， , ( , )S U A= A C D= ∪
C D φ=∩ ，其中，C 为条件属性集；D 为决策属性集。令 iX
和 分别代表 与 中的各个等价类， 和
分别表示等价类
jY /U C /U D ( )ides X
( )jdes Y iX 和等价类 的描述。决策规则定
义为
jY
: ( ) des( ),ij i j j ir des X Y Y X φ→ ≠∩
1X Yµ<
，规则的确信度定义为
, 。规则的支撑度定
义为
( , ) | | / | |i j i j iX Y X Y Xµ = ∩ 0 ( , )i j ≤
( , ) | | / | |i j i js X Y X Y U= ∩ , 。 0 ( , )i js X Y< ≤
在决策信息系统 ( , )S U A= 中，全体决策规则是由
{ | : ( ) ( ), }ij ij i j i jZ Z des X des Y X Y φ→ ∩ ≠ 所 构 成 的 。 如 果
1 2{ , , , }sZ Z Zψ = " 是一个规则簇，那么ψ 的确信度定义为
1
1( ) ( )
s
k
k
Z
s
µ ψ µ
=
= ∑ ，它是规则簇的整体确信度度量。决策信息
系统的规则生成的方法很多，对同一问题可能得到不同的结
果。如果 Z 是决策表 中的一条决策规则，经过
将条件属性集
( , )S U C D= ∪
P C⊆ 的取值细化为规则簇 1 2{ , , , }sZ Z Zψ = " ，
这个变化使得 ( ) ( )Zµ ψ µ≥ ；经过将决策属性集 的取
值 细 化 为 规 则 簇
Q D⊆
1 2{ , , , }sZ Z Zψ = " ， 这 个 变 化 使 得
( ) ( )Zµ ψ µ≤ 。经典的度量规则方法都是针对某一具体规则，
没有给出决策信息系统整体决策效果的度量。虽然可以将定
义
1
1( ) ( )
s
k
k
Z
s
µ ψ µ
=
= ∑ 推广为整个决策信息系统决策性能评价
参数，但是这个度量仅仅反映了整体决策规则的简单平均度
量，忽略了规则本身的权重、支撑度以及规则之间的一致性
问题，因此，有必要给出度量决策信息系统整体决策性能评
价的新评价指标。
新指标
设 ( , )S U A= 是 一 个 决 策 信 息 系 统 ， , A C D= ∪
C D φ=∩ , ， 全 体 规 则 由1 2/ ( ) { , , , mU IND C X X X= " }
{ | : ( ) ( ), }ij ij i j i jZ Z des X des Y X Y φ→ ∩ ≠ 构成，决策表 ( , )S U A=
的总体确信度度量 C定义为
1 1
| || |1( ) ( )
| | | |
m Ni iji
ij
i ji
ZXC S Z
U N U
µ
= =
= ∑ ∑
其中， 为等价类iN iX 对应的决策规则个数； | || |
ijZ
U
表示规则
ijZ 在论域U 中的支撑度，其中， | | |ij i j |Z X Y= ∩ ； ( )ijZµ 表示
ijZ 的规则确信度。
决策信息系统 ( , )S U A= 的总体支撑度度量 A定义为
1 1
| |( ) [1 ( )(1 ( ))]
| |
m Ni
i
ij ij
i j
XA S Z Z
U
µ µ
= =
= − −∑ ∑
其中， 为等价类iN iX 对应的决策规则个数； ( )(1 ( ))ij ijZ Zµ µ−
表示规则 ijZ 的不一致性； ( )ijZµ 表示 ijZ 的规则确信度。
新指标的性质
总体确信度度量 C不仅反映了决策信息系统的整体决策
的支撑效果，也反映了决策信息系统整体决策的确信度情况。
利用该指标得出结论：在条件分类不变的情况下，决策分类
越细，决策信息系统的整体决策效果越差；在决策分类不变
的情况下，条件分类越细，决策信息系统的整体决策效果
越差。
总体支撑度度量 A 给出了决策表整体决策的一致性度
量。在决策表中，如果决策粒度不变，条件粒度越细，评价
参数 A越小，决策表整体决策的一致性效果越差。
4 结束语
用粗糙集处理海量信息时，粗糙边界中的数据规模可能
很大，本文提出的近似序列决策规则挖掘算法利用粗糙集的
上下近似，逐步从粗糙边界中获取规则，直到挖掘出海量信
息中全部决策规则或挖掘出满足用户需求的规则为止。该算
法使规则在动态变化中逐步细化，包含了粒度计算的思路，
同时也体现了变精度粗糙集的思想，具有一定的泛化能力。
该算法稍加改造，就可用于本体的自动构建中。
1
(下转第 27页)
—24—
