2009-8-20 高级人工智能 史忠植 1
第九章 知识发现粗糙集史忠植中科院计算所
2009-8-20 高级人工智能 史忠植 2
内容一、概述二、知识分类三、知识的约简四、决策表的约简五、粗糙集的扩展模型六、粗糙集的实验系统
2009-8-20 高级人工智能 史忠植 3
一,概述现实生活中有许多含糊现象并不能简单地用真、假值来表示 ﹐ 如何表示和处理这些现象就成为一个研究领域。早在 1904年谓词逻辑的创始人 G.Frege就提出了含糊 (Vague)
一词,他把它归结到边界线上,也就是说在全域上存在一些个体既不能在其某个子集上分类,也不能在该子集的补集上分类。
2009-8-20 高级人工智能 史忠植 4
模糊集
1965年,Zadeh提出了模糊集,不少理论计算机科学家和逻辑学家试图通过这一理论解决 G.Frege的含糊概念,但模糊集理论采用隶属度函数来处理模糊性,而基本的隶属度是凭经验或者由领域专家给出,所以具有相当的主观性。
2009-8-20 高级人工智能 史忠植 5
粗糙集的提出
20世纪 80年代初,波兰的 Pawlak针对
G.Frege的边界线区域思想提出了粗糙集
( Rough Set) ﹐ 他把那些无法确认的个体都归属于边界线区域,而这种边界线区域被定义为上近似集和下近似集之差集。由于它有确定的数学公式描述,完全由数据决定,,
所以更有客观性 。
2009-8-20 高级人工智能 史忠植 6
粗糙集的研究粗糙集理论的主要优势之一是它不需要任何预备的或额外的有关数据信息。自提出以来,许多计算机科学家和数学家对粗糙集理论及其应用进行了坚持不懈的研究,使之在理论上日趋完善,特别是由于 20世纪 80年代末和 90年代初在知识发现等领域得到了成功的应用而越来越受到国际上的广泛关注。
2009-8-20 高级人工智能 史忠植 7
粗糙集的研究
1991年波兰 Pawlak教授的第一本关于粗糙集的专著,Rough Sets,Theoretical
Aspects of Reasoning about Data,和
1992年 R.Slowinski主编的关于粗糙集应用及其与相关方法比较研究的论文集的出版,
推动了国际上对粗糙集理论与应用的深入研究。 1992年在波兰 Kiekrz召开了第 1届国际粗糙集讨论会。从此每年召开一次与粗糙集理论为主题的国际研讨会。
2009-8-20 高级人工智能 史忠植 8
研究现状分析
史忠植,知识发现,北京,清华大学出版社,2002
刘清,Rough Set及 Rough推理,北京,科学出版社,
2001
张文修等,Rough Set理论与方法,北京,科学出版社,
2001
王国胤,Rough Set理论与知识获取,西安,西安交通大学出版社,2001
曾黄麟,粗集理论及其应用 (修订版 ),重庆,重庆大学出版社,1998
2009-8-20 高级人工智能 史忠植 9
研究现状分析
2001年 5月在重庆召开了“第 1届中国 Rough集与软计算学术研讨会”,邀请了创始人 Z,Pawlak教授做大会报告;
2002年 10月在苏州 第 2届
2003年 5月在重庆 第 3届,同时举办“第 9届粗糙集、
模糊集、数据挖掘和粒度 -软计算的国际会议” 因非典推迟到 10月
中科院计算所、中科院自动化所、北京工业大学、
西安交通大学、重庆邮电学院、山西大学、合肥工业大学、上海大学、南昌大学
2009-8-20 高级人工智能 史忠植 10
二,知识分类基本粗糙集理论认为知识就是人类和其他物种所固有的分类能力。例如,
在现实世界中关于环境的知识主要表明了生物根据其生存观来对各种各样的情形进行分类区别的能力。每种生物根据其传感器信号形成复杂的分类模式,就是这种生物的基本机制。分类是推理、学习与决策中的关键问题。因此,粗糙集理论假定知识是一种对对象进行分类的能力。这里的,对象,是指我们所能言及的任何事物,比如实物、状态、抽象概念、过程和时刻等等。即知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起,这种特定部分称之为所讨论的 全域 或 论域
(universe)。对于全域及知识的特性并没有任何特别假设。事实上,知识构成了某一感兴趣领域中各种分类模式的一个族集 (family),这个族集提供了关于现实的显事实,以及能够从这些显事实中推导出隐事实的推理能力。
2009-8-20 高级人工智能 史忠植 11
二,知识分类为数学处理方便起见,在下面的定义中用等价关系来代替分类。
一个 近似空间 (approximate space)( 或 知识库 ) 定义为一个关系系统 ( 或二元组 )
K=(U,R)
其中 U?( 为空集 ) 是一个被称为全域或论域 (universe)
的所有要讨论的个体的集合,R是 U上等价关系的一个族集 。
2009-8-20 高级人工智能 史忠植 12
二,知识分类设 P?R,且 P,P中所有等价关系的交集称为 P上的一种难区分关系 (indiscernbility relation)
(或称难区分关系),记作 IND(P),即
[x]IND(p)= I [x]R
R?P
注意,IND(P)也是等价关系且是唯一的。
2009-8-20 高级人工智能 史忠植 13
二,知识分类给定近似空间 K=(U,R),子集 X?U称为 U上的一个 概念
(concept),形式上,空集也视为一个概念;非空子族集
P?R所产生的不分明关系 IND(P)的所有等价类关系的集合即
U/IND(P),称为 基本知识 (basic knowledge),相应的等价类称为 基本概念 (basic concept);特别地,若关系 Q?R,
则关系 Q就称为 初等知识 (elementary knowledge),相应的等价类就称为 初等概念 (elementary concept)。
一般用大写字母 P,Q,R等表示一个关系,用大写黑体字母
P,Q,R等表示关系的族集; [x]R或 R(x)表示关系 R中包含元素
x?U的概念或等价类 。 为了简便起见,有时用 P代替 IND(P)。
根据上述定义可知,概念即对象的集合,概念的族集
(分类)就是 U上的知识,U上分类的族集可以认为是 U上的一个知识库,或说知识库即是分类方法的集合。
2009-8-20 高级人工智能 史忠植 14
二,知识分类粗糙集理论与传统的集合理论有着相似之处,但是它们的出发点完全不同。传统集合论认为,一个集合完全是由其元素所决定,一个元素要么属于这个集合,要么不属于这个集合,即它的隶属函数?X(x)?{0,1}。模糊集合对此做了拓广,它给成员赋予一个隶属度,即?X(x)?[0,1],使得模糊集合能够处理一定的模糊和不确定数据,但是其模糊隶属度的确定往往具有人为因素,这给其应用带来了一定的不便。而且,传统集合论和模糊集合论都是把隶属关系作为原始概念来处理,集合的并和交就建立在其元素的隶属度 max和 min操作上,因此其隶属度必须事先给定(传统集合默认隶属度为 1或 0)。在粗糙集中,隶属关系不再是一个原始概念,因此无需人为给元素指定一个隶属度,从而避免了主观因素的影响。
2009-8-20 高级人工智能 史忠植 15
Information Systems/Tables
IS is a pair (U,A)
U is a non-empty
finite set of objects.
A is a non-empty finite
set of attributes such
that for
every
is called the value
set of a.
aVUa?:
.Aa?
aV
Age LEMS
x1 16-30 50
x2 16-30 0
x3 31-45 1-25
x4 31-45 1-25
x5 46-60 26-49
x6 16-30 26-49
x7 46-60 26-49
2009-8-20 高级人工智能 史忠植 16
Decision Systems/Tables
DS,
is the decision
attribute (instead of one
we can consider more
decision attributes).
The elements of A are
called the condition
attributes.
Age LEMS Walk
x1 16-30 50 yes
x2 16-30 0 no
x3 31-45 1-25 no
x4 31-45 1-25 yes
x5 46-60 26-49 no
x6 16-30 26-49 yes
x7 46-60 26-49 no
}){,( dAUT
Ad?
2009-8-20 高级人工智能 史忠植 17
Issues in the Decision Table
The same or indiscernible objects may be
represented several times.
Some of the attributes may be superfluous.
2009-8-20 高级人工智能 史忠植 18
难区分性 Indiscernibility
The equivalence relation
A binary relation which is
reflexive (xRx for any object x),
symmetric (if xRy then yRx),and
transitive (if xRy and yRz then xRz),
The equivalence class of an element
consists of all objects such that
xRy.
XXR
Xx? Xy?
Rx][
2009-8-20 高级人工智能 史忠植 19
难区分性 Indiscernibility (2)
Let IS = (U,A) be an information system,then
with any there is an associated equivalence
relation:
where is called the B-indiscernibility
relation.
If then objects x and x’ are
indiscernible from each other by attributes from B.
The equivalence classes of the B-indiscernibility
relation are denoted by
AB?
)}'()(,|)',{()( 2 xaxaBaUxxBI N D IS
)( BI N D IS
),()',( BI N Dxx IS?
.][ Bx
2009-8-20 高级人工智能 史忠植 20
难区分性实例 Indiscernibility
The non-empty subsets of
the condition attributes
are {Age},{LEMS},and
{Age,LEMS}.
IND({Age}) = {{x1,x2,x6},
{x3,x4},{x5,x7}}
IND({LEMS}) = {{x1},
{x2},{x3,x4},{x5,x6,x7}}
IND({Age,LEMS}) =
{{x1},{x2},{x3,x4},
{x5,x7},{x6}},
Age LEMS Walk
x1 16-30 50 yes
x2 16-30 0 no
x3 31-45 1-25 no
x4 31-45 1-25 yes
x5 46-60 26-49 no
x6 16-30 26-49 yes
x7 46-60 26-49 no
2009-8-20 高级人工智能 史忠植 21
概念的边界知识的粒度性是造成使用已有知识不能精确地表示某些概念的原因。这就产生了所谓的关于不精确的
,边界,思想。著名哲学家 Frege认为,概念必须有明确的边界。没有明确边界的概念,将对应于一个在周围没有明确界线的区域,。粗糙集理论中的模糊性就是一种基于边界的概念,即一个不精确的概念具有模糊的不可被明确划分的边界。为刻画模糊性,每个不精确概念由一对称为上近似与下近似的精确概念来表示,它们可用隶属函数定义
2009-8-20 高级人工智能 史忠植 22
粗糙集的基本定义
知识的分类观点粗糙集理论假定知识是一种对对象进行分类的能力。而知识必须与具体或抽象世界的特定部分相关的各种分类模式联系在一起,
这种特定部分称之为所讨论的 全域 或 论域
(universe)。
为数学处理方便起见,在下面的定义中用等价关系来代替分类。
2009-8-20 高级人工智能 史忠植 23
粗糙集的基本定义定义 1 一个 近似空间 (approximate space)(或 知识库 )定义为一个关系系统 (或二元组 )K=(U,R),
其中 U(?为空集 )是一个被称为全域或论域
(universe)的所有要讨论的个体的集合,R是 U上等价关系的一个族集 。
定义 2 设 P?R,且 P,P中所有等价关系的交集称为 P上的一种不分明关系 (indiscernbility
relation)( 或称不可区分关系 ),记作 IND(P)
PP?
R R
][][ )( xx I N D
2009-8-20 高级人工智能 史忠植 24
粗糙集的基本定义定义 3 给定近似空间 K=(U,R),子集 X?U称为 U上的一个 概念 (concept),形式上,空集也视为一个概念;非空子族集 P?R所产生的不分明关系 IND(P)
的所有等价类关系的集合即 U/IND(P),称为 基本知识 (basic knowledge),相应的等价类称为 基本概念 (basic concept);特别地,若关系 Q?R,则关系 Q就称为 初等知识 (elementary knowledge),
相应的等价类就 称为 初 等 概念 (elementary
concept)。
2009-8-20 高级人工智能 史忠植 25
上近似、下近似和边界区域定义 5:
X的下近似,R*(X)={x:(x?U)?([x]R?X )}
X的上近似,R*(X)={x:(x?U)?([x]R?X )}
X的边界区域,BNR(X)=R*(X)–R*(X)
若 BNR(X),则集合 X就是一个粗糙概念。下近似包含了所有使用知识 R可确切分类到 X的元素,上近似则包含了所有那些可能是属于 X的元素。概念的边界区域由不能肯定分类到这个概念或其补集中的所有元素组成。
POSR(X)=R*(X)称为集合 X的 R-正区域,
NEGR(X)=U–R*(X)称为集合 X的 R-反区域 。
2009-8-20 高级人工智能 史忠植 26
Lower & Upper Approximations
(2)
}:/{ XYRUYXR
}:/{ XYRUYXR?
Lower Approximation:
Upper Approximation:
2009-8-20 高级人工智能 史忠植 27
新型的隶属关系传统集合论中,一个元素的隶属函数?X(x)?{0,1}。
而粗糙集理论中,?X(x)?[0,1]
定义 4 设 X?U且 x?U,集合 X的 粗糙隶属函数 (rough
membership function)定义为
))((
))(()(
xRc a r d
xRXc a r dxR
X

其中 R是不分明关系,R(x)=[x]R={y:(y?U)?(yRx)}
)(xRX? =1当且仅当 [x]R?X )(xRX? >0当且仅当 [x]R?X
)(xRX? =0当且仅当 [x]R?X=?
2009-8-20 高级人工智能 史忠植 28
隶属关系根据上面的定义,可以得到以下性质
(1) (x)=1当且仅当 [x]R?X;
(2) (x)>0当且仅当 [x]R?X?;
(3) (x)=0当且仅当 [x]R?X=。
显然有 (x)?[0,1]。我们可以看到,这里的隶属关系是根据已有的分类知识客观计算出来的,可以被解释为一种条件概率,能够从全域上的个体加以计算,
而不是主观给定的。
2009-8-20 高级人工智能 史忠植 29
集近似 Set Approximation
Let T = (U,A) and let and
We can approximate X using only the
information contained in B by constructing
the B-lower and B-upper approximations of
X,denoted and respectively,where
AB?,UX?
XB XB
},][|{ XxxXB B
}.][|{ XxxXB B
2009-8-20 高级人工智能 史忠植 30
集近似 Set Approximation (2)
B-boundary region of X,
consists of those objects that we cannot decisively
classify into X in B.
B-outside region of X,
consists of those objects that can be with certainty
classified as not belonging to X.
A set is said to be rough if its boundary region is
non-empty,otherwise the set is crisp.
,)( XBXBXBN B
,XBU?
2009-8-20 高级人工智能 史忠植 31
集近似实例 Set Approximation
Let W = {x | Walk(x) = yes},
The decision class,Walk,is
rough since the boundary
region is not empty.
Age LEMS Walk
x1 16-30 50 yes
x2 16-30 0 no
x3 31-45 1-25 no
x4 31-45 1-25 yes
x5 46-60 26-49 no
x6 16-30 26-49 yes
x7 46-60 26-49 no
}.7,5,2{
},4,3{)(
},6,4,3,1{
},6,1{
xxxWAU
xxWBN
xxxxWA
xxWA
A

2009-8-20 高级人工智能 史忠植 32
集近似实例
Set Approximation (2)
yes
yes/no
no
{{x1},{x6}}
{{x3,x4}}
{{x2},{x5,x7}}
AW
WA
2009-8-20 高级人工智能 史忠植 33
U
setX
U/R
R,subset of
attributes
XR
XXR?
Lower & 集近似图示 ns
2009-8-20 高级人工智能 史忠植 34
Lower & Upper Approximations
(3)
X1 = {u | Flu(u) = yes}
= {u2,u3,u6,u7}
RX1 = {u2,u3}
= {u2,u3,u6,u7,u8,u5}
X2 = {u | Flu(u) = no}
= {u1,u4,u5,u8}
RX2 = {u1,u4}
= {u1,u4,u5,u8,u7,u6}X1R X2R
U He adac h e T e m p,Fl u
U1 Y e s N o r m a l No
U2 Y e s H ig h Y e s
U3 Y e s V e r y - hi g h Y e s
U4 No N o r m a l No
U5 N o H i g h N o
U6 No V e ry - h igh Y e s
U7 N o H i g h Y e s
U8 No V e ry - h igh No
The indiscernibility classes defined by
R = {Headache,Temp.} are
{u1},{u2},{u3},{u4},{u5,u7},{u6,u8}.
2009-8-20 高级人工智能 史忠植 35
Lower & Upper Approximations
(4)
R = {Headache,Temp.}
U/R = { {u1},{u2},{u3},{u4},{u5,u7},{u6,u8}}
X1 = {u | Flu(u) = yes} = {u2,u3,u6,u7}
X2 = {u | Flu(u) = no} = {u1,u4,u5,u8}
RX1 = {u2,u3}
= {u2,u3,u6,u7,u8,u5}
RX2 = {u1,u4}
= {u1,u4,u5,u8,u7,u6}
X1R
X2R
u1
u4u3
X1 X2
u5u7u2
u6 u8
2009-8-20 高级人工智能 史忠植 36
例 1:
设有一知识库 K={U,{p,q,r}}﹐ 其中
U={x1,x2,x3,x4,x5,x6,x7,x8}﹐ 且
U/p={{x1,x4,x5},{x2,x8},{x3},{x6,x7}}
U/q={{x1,x3,x5},{x6},{x2,x4,x7,x8}}
U/r={{x1,x5},{x6},{x2,x7,x8},{x3,x4}}
则 [x1]p={x1,x4,x5}﹐[x 1]q= {x1,x3,x5} 。
若 P={p,q,r}﹐
则 IND(P)= {{x1,x5},{x2,x8},{x3},{x4},{x6},{x7}}
对于 U上的子集 X1={x1,x4,x7}﹐ 可得到
P* X1={x4}∪{x 7}={x4,x7}
P* X1={x1,x5}∪{x 4}∪{x 7}={x1,x4,x5,x7}
2009-8-20 高级人工智能 史忠植 37
近似度
Accuracy of Approximation
where |X| denotes the cardinality of
Obviously
If X is crisp with respect to B.
If X is rough with respect to B.
|)(|
|)(|)(
XB
XBX
B
.X
.10 B?
,1)(?XB?
,1)(?XB?
2009-8-20 高级人工智能 史忠植 38
近似性质 Properties of
Approximations
YX
YBXBYXB
YBXBYXB
UUBUB BB
XBXXB

)()()(
)()()(
)()(,)()(
)(

)()( YBXB? )()( YBXB?implies and
2009-8-20 高级人工智能 史忠植 39
近似性质 Properties of
Approximations (2)
)())(())((
)())(())((
)()(
)()(
)()()(
)()()(
XBXBBXBB
XBXBBXBB
XBXB
XBXB
YBXBYXB
YBXBYXB

where -X denotes U - X.
2009-8-20 高级人工智能 史忠植 40
三,知识的约简
一般约简定义 6 设 R是等价关系的一个族集,且设 R?R。若
IND(R)=IND(R–R),则称关系 R在族集 R之中是 可省 的
(dispensable)﹐ 否则就是 不可省 的。若族集 R中的每个关系 R都是不可省的 ﹐ 则称族集 R是 独立的 (independent)﹐ 否则就是 依赖的 或 非独立 的。
定义 7 若 Q?P是独立的 ﹐ 并且 IND(Q)=IND(P)﹐ 则称 Q是关系族集 P的一个 约简 (reduct) 。在族集 P中所有不可省的关系的集合称为 P的 核 (core) ﹐ 以 CORE(P)来表示。
显然,族集 P有多个约简(约简的不唯一性)。
定理 1 族集 P的核等于 P的所有约简的交集。即
CORE(P)=∩ RED(P)
2009-8-20 高级人工智能 史忠植 41
例 2:
取 前面 的例 1﹐ 若 P={p,q,r}﹐ 则
IND(P)={{x1,x5},{x2,x8},{x3},{x4},{x6},{x7}}﹐
IND(P-p})={{x1,x5},{x2,x7,x8},{x3},{x4},{x6}}?IND(P)
所以 p是不可省的 ﹐ 同理可得 q,r是可省的。这样 ﹐ 由
{p,q,r}三个等价关系组成的集合和 {p,q},{p,r}定义了相同的不分明关系。
又 IND({p,q})?IND({p})﹐ IND({p﹐q})?IND({q})﹐ 则
{p,q}和 {p,r}就是 P的 约简 ﹐ 而且 {p}是 P的核 ﹐ 也就是说 p
是绝对不能省的
2009-8-20 高级人工智能 史忠植 42
相对约简定义 8 设 P和 Q是全域 U上的等价关系的族集,所谓族集 Q的
P-正区域 (P-positive region of Q),记作
POSP(Q)=?
Q/UX?
P*(X)
族集 Q的 P-正区域 是全域 U的所有那些使用分类 U/P所表达的知识,能够正确地分类于 U/Q的等价类之中的对象的集合。
定义 9 设 P和 Q是全域 U上的等价关系的族集,R?P。 若
POSIND(P)(IND(Q))=POSIND(P-{R})(IND(Q)) 则称关系 R在族集 P中是
Q-可省的 ﹐ 否则称为 Q-不可省的 ﹔ 如果在族集 P中的每个关系 R都是 Q-不可省的 ﹐ 则称 P关于 Q是 独立的 ﹐ 否则就称为是依赖的 。
2009-8-20 高级人工智能 史忠植 43
相对约简定义 10 S?P称为 P的 Q-约简 (Q-reduct)﹐ 当且仅当 S是 P的 Q-
独立的子族集 ﹐ 且 POSS(Q)=POSP(Q);族集 P中的所有 Q-不可省的初等关系的集合 ﹐ 称为族集 P的 Q-核 (Q-core)﹐ 记作
COREQ(P) 。
下面的定理是 定理 1的拓广 。
定理 2族集 P的 Q-核等于族集 P的所有 Q-约简的交集 。 即
COREQ(P)=?REDQ(P)
其中 REDQ(P)是族集 P的所有 Q-约简的族集 。
2009-8-20 高级人工智能 史忠植 44
知识的依赖性知识的依赖性可形式定义如下:
定义 11 设 K=(U,R)是一个近似空间,P,Q?R。
1) 知识 Q依赖于 知识 P或知识 P可推导出 知识 Q,当且仅当
IND(P)?IND(Q)﹐ 记作 P?Q;
2) 知识 P和知识 Q是 等价的 ﹐ 当且仅当 P?Q且 Q?P﹐ 即
IND(P)=IND(Q)﹐ 记作 P= Q,明显地,P=Q当且仅当
IND(P)=IND(Q);
3) 知识 P和知识 Q是 独立的,当且仅当 P?Q且 Q?P均不成立,
记作 P?Q。
2009-8-20 高级人工智能 史忠植 45
知识的依赖性依赖性也可以是部分成立的 ﹐ 也就是从知识 P能推导出知识
Q的一部分知识,或者说知识 Q只有一部分依赖于知识 P的。
部分依赖性(部分可推导性)可以由知识的正区域来定义。
现在我们形式地定义部分依赖性。
定义 12 设 K=(U,R)是一个知识库 ﹐ P,Q?R﹐ 我们称 知识 Q以依赖度 k(0?k? 1)依赖于知识 P﹐ 记作 P?kQ﹐ 当且仅当
k=?P(Q)=card(POSP(Q))/card(U) (6.8)
(1) 若 k=1﹐ 则称知识 Q完全依赖于 知识 P,P?1Q也记成 P?Q;
(2) 若 0?k?1﹐ 则称知识 Q部分依赖于 知识 P;
(3) 若 k=0﹐ 则称知识 Q完全独立于 与知识 P。
2009-8-20 高级人工智能 史忠植 46
四,决策表的约简
决策表决策表是一类特殊而重要的知识表达系统,它指当满足某些条件时,决策 ( 行为 ) 应当怎样进行 。 多数决策问题都可以用决策表形式来表示,这一工具在决策应用中起着重要的作用 。
决策表可以定义如下:
S=(U,A)为一信息系统,且 C,D?A是两个属性子集,分别称为条件属性和决策属性,且 C?D=A,C?D=?,则该信息系统称为 决策表,记作 T=(U,A,C,D)或简称 CD决策表。
关系 IND(C)和关系 IND(D)的等价类分别称为条件类和决策类。
2009-8-20 高级人工智能 史忠植 47
身高 性别 视力 录取
e1 高 男 差 否
e2 高 女 一般 是
e3 高 男 好 是
e4 矮 男 差 否
e5 矮 女 一般 是
e6 矮 男 好 是表 1 一决策表身高、性别、视力为条件属性,录取为决策属性
2009-8-20 高级人工智能 史忠植 48
决策规则决策表中的每一行对应诸如形式的决策规则,
和?分别称为决策规则的前驱和后继 。
当决策表 S中决策规则为真时,我们说该决策规则是 S中一致的,否则说该决策规则是 S中不一致的 。 若决策规则是 S中一致的,相同的前驱必导致相同的后继;但同一种后继不一定必需是同一前驱产生的 。
如表 1第一行对应决策规则:
身高 (高 )?性别 (男 )?视力 (差 )? 录取 (否 )
2009-8-20 高级人工智能 史忠植 49
决策表的一致性命题 1
当且仅当 C?D,决策表 T=(U,A,C,D)是一致的 。
由命题 1,很容易通过计算条件属性和决策属性间的依赖程度来检查一致性 。 当依赖程度等于 1
时,我们说决策表是一致的,否则不一致 。
2009-8-20 高级人工智能 史忠植 50
决策表的分解命题 2
每个决策表 T=(U,A,C,D)都可以唯一分解为两个决策表
T1=(U1,A,C,D)和 T2=(U2,A,C,D),这样使得表 T1中
C?1D 和 T2 中 C?0D 。 这里 U1=POSC(D),U2=?BNC(X),
X?U|IND(D)。
由命题 2可见,假设我们已计算出条件属性的依赖度,若表的结果不一致,即依赖度小于 1,则由命题 2可以将表分解成两个子表:其中一个表完全不一致,依赖度为 0;另一个表则完全一致,依赖度为 1。 当然,只有依赖度大于 0
且不等于 1时,这一分解才能进行 。
2009-8-20 高级人工智能 史忠植 51
表 2 不一致决策表
a,b,c为条件属性,d,e为决策属性
1,5产生不一致
U a b c d e
1
2
3
4
5
6
7
8
1 0 2 2 0
0 1 1 1 2
2 0 0 1 1
1 1 0 2 2
1 0 2 0 1
2 2 0 1 1
2 1 1 1 2
0 1 1 0 1
2009-8-20 高级人工智能 史忠植 52
表 3 完全一致的决策表
U a b c d e
3
4
6
7
2 0 0 1 1
1 1 0 2 2
2 2 0 1 1
2 1 1 1 2
表 4 完全不一致的决策表
U a b c d e
1
2
5
8
1 0 2 2 0
0 1 1 1 2
1 0 2 0 1
0 1 1 0 1
2009-8-20 高级人工智能 史忠植 53
一致决策表的约简在我们制定决策时是否需要全部的条件属性,能否进行决策表的约简。约简后的决策表具有与约简前的决策表相同的功能,但是约简后的决策表具有更少的条件属性。
一致决策表的约简步骤如下:
(1) 对决策表进行条件属性的约简,即从决策表中消去某一列; (主要研究点 )
(2) 消去重复的行;
(3) 消去每一决策规则中属性的冗余值。
2009-8-20 高级人工智能 史忠植 54
条件属性的约简
A.Skowron提出了差别矩阵,使核与约简等概念的计算较为简单,主要思想:
设 S=(U,A)为一个知识表示系统,其中 U
={x1,x2,…,xn},xi为所讨论的个体,i=1,2,…,n,
A ={a1,a2,…,am},aj为个体所具有的属性,
j=1,2,…,m。
知识表达系统 S的差别矩阵 M(S)=[cij]n× n,其中矩阵项定义如下:
cij={a∈ A,a(xi)≠a(xj),i,j=1,2,…,n}
因此 cij是个体 xi与 xj有区别的所有属性的集合
2009-8-20 高级人工智能 史忠植 55
差别矩阵对应的核与约简核就可以定义为差别矩阵中所有只有一个元素的矩阵项的集合,即
CORE(A)={a∈A,cij=(a),对一些 i,j}
相对于集合包含关系运算而言,若属性集合 B?A是满足下列条件
B∩cij≠?,对于 M(S)中的任一非空项 cij≠?
的一个最小属性子集,则称属性集合 B?A是 A的一个约简。
换言之,约简是这样的最小属性子集,它能够区分用整个属性集合 A可区分的所有对象。
2009-8-20 高级人工智能 史忠植 56
Skowron的约简方法对于每一个差别矩阵 M(S)对应唯一的差别函数
fM(S)﹙ Discernibility Function﹚,它的定义如下:
信息系统 S的差别函数 fM(S)是一个有 m-元变量 a1,…,
am(ai∈ A,i=1,…,m)的布尔函数,它是 ∨ cij的合取,
∨ cij是矩阵项 cij中的各元素的析取,1≤j<i≤n且 cij≠Φ。
根据差别函数与约简的对应关系,A.Skowron提出了计算信息系统 S的约简 RED(S)的方法:
1) 计算信息系统 S的差别矩阵 M(S)
2) 计算与差别矩阵 M(S)对应的差别函数 fM(S)
3) 计算差别函数 fM(S)的最小析取范式,其中每个析取分量对应一个约简
2009-8-20 高级人工智能 史忠植 57
为了对决策表进行约简,可以采用差别矩阵的方法对条件属性进行约简,对决策属性相同的个体不予比较。考虑下面的决策表 5,条件属性为 a,b,c,d,决策属性为 e
U/A a b c d e
u1 1 0 2 1 0
u2 0 0 1 2 1
u3 2 0 2 1 0
u4 0 0 2 2 2
u5 1 1 2 1 0
表 5
2009-8-20 高级人工智能 史忠植 58
表 5对应的差别矩阵
u u1 u2 u3 u4 u5
u1
u2 a,c,d
u3 a,c,d
u4 a,d c a,d
u5 a,b,c,
d a,b,d
由下面的差别矩阵很容易得到核为 {c},差别函数 fM(S)为
c∧( a∨ d),即 (a∧ c)∨( c∧ d),得到两个约简 {a,c}
和 {c,d}
2009-8-20 高级人工智能 史忠植 59
表 6
根据得到的两个约简,表 5可以简化为表 6和表 7
U\A a c e
u1 1 2 0
u2 0 1 1
u3 2 2 0
u4 0 2 2
u5 1 2 0
U\A c d e
u1 2 1 0
u2 1 2 1
u3 2 1 0
u4 2 2 2
U5 2 1 0
表 7
2009-8-20 高级人工智能 史忠植 60
求最优或次优约简所有约简的计算是 NP-hard问题,因此运用启发信息来简化计算以找出最优或次优约简是必要的。
现在在求最优或次优约简的算法一般都使用核作为计算约简的出发点,计算一个最好的或者用户指定的最小约简。算法将属性的重要性作为启发规则,按照属性的重要度从大到小逐个加入属性,直到该集合是一个约简为止。
2009-8-20 高级人工智能 史忠植 61
行的约简对决策表中的重复的行要删除,因为它们的条件属性和决策属性都相同,都表示同一条决策规则 。 另外,
决策规则的列表顺序不是本质性的,所以表 6,表 7都可进行约简,如表 6可简化为下表:
U\A a c e
u1 1 2 0
u2 0 1 1
u3 2 2 0
u4 0 2 2
表 8
2009-8-20 高级人工智能 史忠植 62
属性值的约简对于决策表而言,属性值的约简就是决策规则的约简 。 决策规则的约简是利用决策逻辑消去每个决策规则的不必要条件,它不是整体上约简属性,而是针对每个决策规则,去掉表达该规则时的冗余属性值,
即要计算每条决策规则的核与约简 。
2009-8-20 高级人工智能 史忠植 63
非一致决策表的约简对于一致的决策表比较容易处理,在进行约简时,
只要判断去掉某个属性或某个属性值时是否会导致不一致规则的产生 。
而对不一致表进行约简时就不能再使用这种方法了,
一般采用下面的方法:一种是考虑正域的变化,另外一种是将不一致表分成完全一致表和完全不一致表两个子表 。
非一致决策表的约简步骤与一致决策表的约简步骤类似 。
2009-8-20 高级人工智能 史忠植 64
五,粗糙集的扩展模型基本粗糙集理论的主要存在的问题是:
1) 对原始数据本身的模糊性缺乏相应的处理能力;
2) 对于粗糙集的边界区域的刻画过于简单;
3) 粗糙集理论的方法在可用信息不完全的情况下将对象们归类于某一具体的类,通常分类是确定的,但并未提供数理统计中所常用的在一个给定错误率的条件下将尽可能多的对象进行分类的方法,而实际中常常遇到这类问题。
2009-8-20 高级人工智能 史忠植 65
可变精度粗糙集模型
W.Ziarko提出了一种称之为可变精度粗糙集模型,该模型给出了错误率低于预先给定值的分类策略,定义了该精度下的正区域,边界区域和负区域 。 下面扼要地介绍其思想:
一般地,集合 X包含于 Y并未反映出集合 X的元素属于集合 Y
的,多少,。 为此,VPRS定义了它的量度:
C(X,Y)=1–card(X?Y)/card(X) 当 card(x)>0,
C(X,Y)=0 当 card(x)=0。
C(X,Y)表示把集合 X归类于集合 Y的误分类度,即有 C(X,
Y)?100%的元素归类错误 。 显然,C(X,Y)=0时有 X?Y。 如此,可事先给定一错误分类率?(0<0.5),基于上述定义,我们有 XY,当且仅当 C(X,Y)。
2009-8-20 高级人工智能 史忠植 66
可变精度粗糙集模型在此基础上,设 U为论域且 R为 U上的等价关系,U/R=A={X1,
X2,…,Xk },这样,可定义集合 X的?-下近似 为
R?X=?Xi (XiX,i=1,2,…,k)
或 R?X=?Xi (C(Xi,X),i=1,2,…,k),
并且 R?X称为集合 X的?-正区域,集合 X的?-上近似 为
R?X=?Xi (C(Xi,X)<1–?,i=1,2,…,k),
这样,?-边界区域 就定义为:
BNR?X=?Xi (?<C(Xi,X)<1–?);
-负区域 为,NEGR?X=?Xi (C(Xi,X)?1–?)。
以此类推,我们还可以定义?-依赖,?-约简 等与传统粗糙集模型相对应的概念 。
2009-8-20 高级人工智能 史忠植 67
相似模型在数据中存在缺失的属性值的时候 ( 在数据库中很普遍 ),
不分明关系或等价关系无法处理这种情形 。 为扩展粗糙集的能力,有许多作者提出了用相似关系来代替不分明关系作为粗糙集的基础 。
在使用相似关系代替粗糙集的不分明关系后,最重要的变化就是相似类不再形成对集合的划分了,它们之间是相互重叠的 。 类似于等价类,可以定义相似集,即所有和某各元素 x在属性集合 B上相似的集合 SIMb(x)。 值得注意的是
SIMb(x)中的元素不一定属于同一决策类,因此还需要定义相似决策类,即相似集对应的决策类集合 。
2009-8-20 高级人工智能 史忠植 68
基于粗糙集的非单调逻辑自粗糙集理论提出以来,粗糙集理论的研究者都很重视它的逻辑研究,试图通过粗糙集建立粗糙逻辑,也相应地发表了一系列的粗糙逻辑方面的论文 。
2009-8-20 高级人工智能 史忠植 69
与其它数学工具的结合
D.Dudios和 H.Prade由此提出了 Rough Fuzzy Set
和 Fuzzy Rough Set的概念
A.Skowron和 J.Grazymala-Buss认为,粗糙集理论可以看作证据理论的基础 。 并在粗糙集理论的框架上重新解释了证据理论的基本概念,特别是用上近似和下近似的术语解释了信念 (belief)和似然
(plausibility)函数,进而讨论了两者之间的互补问题 。
2009-8-20 高级人工智能 史忠植 70
六、粗糙集的实验系统在过去几年中,建立了不少基于粗糙集的 KDD系统,其中最有代表性的有 LERS,ROSE,KDD-R等 。
1,LERS
LERS(Learning from examples based on Rough Set)
系统是美国 Kansas大学开发的基于粗糙集的实例学习系统 。 它是用 Common Lisp在 VAX9000上实现的 。 LERS已经为 NASA的 Johnson空间中心应用了两年 。 此外,LERS还被广泛地用于环境保护,气候研究和医疗研究
2009-8-20 高级人工智能 史忠植 71
六、粗糙集的实验系统
2,ROSE
波兰 Poznan科技大学基于粗糙集开发了 ROSE(Rough Set
data Explorer),用于决策分析 。 它是 Rough Das &
Rough Class系统的新版,其中 RoughDas执行信息系统数据分析任务,RoughClass支持新对象的分类,这两个系统已经在许多实际领域中得到应用 。
3,KDD— R
KDD-R是由加拿大的 Regina大学开发的基于可变精度粗糙集模型,采用知识发现的决策矩阵方法开发了 KDD-R
系统,这个系统被用来对医学数据分析,以此产生症状与病证之间新的联系,另外它还支持电信工业的市场研究 。
2009-8-20 高级人工智能 史忠植 72
可以在
http://www.cs.uregina.ca/~roughset
的 Electronic Bulletin of the
Rough Set Community中看到粗糙集研究的进展。