rough

1

第三节粗糙集（RoughSet，RS）

如果我们将研究对象看成是现象，那么我们可以将这些现象分类。现象被

分为确定现象与不确定现象。不确定现象有分为随机现象，模糊现象和信息不

全的粗糙现象。如下所示：



































确定现象

随机现象，0－1律，多种可能性满足分布规律。

现象

不确定现象模糊现象，律属度Î(0，1），不是非此即彼。

粗糙现象，研究那些因为信息不充分而导致的不确定性

相对于前两种现象的处理，粗糙现象是基于不完全的信息或知识去处理不分明

的现象，因此需要基于观测或者测量到的部分信息对数据进行分类，这就需要

与概率统计和模糊数学不同的处理手段，这就是粗糙集理论。直观地讲，粗糙

集是基于一系列既不知道多了还是少了，也不知道有用还是没用的不确定、不

完整乃至于部分信息相互矛盾的数据或者描述来对数据进行分析、推测未知信

息。下面我们对粗糙集的基本特征、以及数学符号进行简述。

1．粗糙集的特点

粗糙集的特点是利用不精确、不确定、部分真实的信息来得到易于处理、

鲁棒性强、成本低廉的决策方案。因此更适合于解决某些现实系统，比如，中

医诊断，统计报表的综合处理等。粗糙集的另一个重要特点就是它只依赖于数

据本身，不需要样本之外的先验知识或者附加信息，因此挑选出来的决策属性

可以避免主观性，有英雄不问出身的意味。用粗糙集来处理的数据类型包括确

定性的、非确定性的、不精确的、不完整的、多变量的、数值的、非数值的。

粗糙集使用上、下近似来刻画不确定性，使得边界有了清晰的数学意义并且降

低了算法设计的随意性。

3．粗糙集的基本概念

粗糙集要涉及论域U（这与模糊系统相似），还要涉及属性集合

RCD

2

（这被认为是知识，或者知识库）。当然，也要有属性值域V，以及从UR到V

的信息函数

f

。因此，一个信息系统

S

可以表示为一个四元组,,,SURVf。

在不混淆的情况下，简记为

(,)SUR

，也称为知识库。

等价关系（通常用来代替分类）是不可或缺的概念，根据等价关系可以划

论域中样本为等价类。而每个等价类被称为同一个对象。但是，等价关系又是

建立在不可分辨概念之上的，为了便于描述这里的等价关系，我们首先介绍不

可分辨性。

设BR为一个非空子集，如果,

ij

xxU，均有(,)(,),

ij

fxrfxrrB成

立，那么，我们称

ij

xx和关于属性子集B不可分辨。B不可分辨关系，简记为

()IndB

，是一种等价关系（易验证它满足等价关系的数学公理），于是

()IndB

可

以将论域

U

中的元素分成若干等价类，每一个等价类称为知识库的知识颗粒。

全体等价类组成的集合记为

/()UIndB

，称之为基本集合。若集合X可以表示成

某些基本集的并时，则称X是B精确集，否则称为B粗糙集。

粗糙集中的“粗糙”主要体现在边界域的存在，而边界又是由下、上近似

来刻画的。对于任意

XU

，X关于现有知识R的下、上近似分别定义为：

_(){,[]}

R

RXxUxX，(){,[]}

R

RxxUxX。

X的确定域PosXRX



，是指论域

U

中那些在现有知识R之下能够确定地

归入集合X的元素的集合。反之，NegXURX



被称为否定域。边界域

是某种意义上论域的不确定域，即在现有知识R之下U中那些既不能肯定在X

中，又不能肯定归入XUX中的元素的集合，记为

R

BndX。

样本子集X的不确定性程度可以用粗糙度

R

aX来刻画，粗糙度的定义为：





R

CardRX

aX

CardRX







式中

Card

表示集合的基数（集合中元素的个数）。显然，01

R

aX，如果

1

R

aX，则称集合X关于R是确定的；如果1

R

aX，则称集合X关于R

是粗糙的，

R

aX可认为是在等价关系R下逼近集合X的精度。

为了使得上述概念具体化，下面我们举一个例子说明如何理解和计算以上

相应的概念和对应量。

3

例.针对一下医学信息表我们来理解前面所提到的概念。

表1某医疗信息表

属性

对象

条件属性C决策属性D

头疼r1肌肉疼r2体温r3流感

1

x

是是正常否

2

x

是是高是

3

x

是是很高是

4

x

否是正常否

5

x

否否高否

6

x

否是很高是

依据此表，如果取属性子集

12

,,Rrr头疼肌肉疼，

123

,,Xxxx。那么

我们下面给出X的上近似集、下近似集、确定域、边界域、粗糙度。

解：①计算论域U的所有R基本集：

123465

/,,,,,UIndRxxxxxx

令

112324635

,,,RxxxRxxRx

②确定样本子集X与基本集的关系

112235

{,}{}XRxxXRXRx；；

③计算RX、RX



、PosXBndX和：





13123535

5123

{,,}{}

{}{,,}

RXRRxxxxRXRx

PosXRXxBndXRXRXxxx













；

；

④计算近似精确度：





1/40.25

R

CardRX

aZ

CardRX







与粗糙度类似，在给出了两个知识集（特征属性）的相对肯定域的概念

()

P

PosQ之后，我们也可以一个量来刻画两个知识集的依赖度。设(,)KUR为

一个知识库，,PQR为两个知识集。令()(())/()

PP

krQCardPosQCardU，

4

称为知识

Q

依赖于知识P的依赖度。特别，当

1k

时称为完全依赖；

01k

时，

部分依赖；

0k

时，

Q

完全独立于知识P。

3．知识约简

知识约简是粗糙集的核心内容之一，它是研究知识库中哪些知识是必要的，

以及在保持分类能力不变的前提下，删除冗余的知识。在粗糙集应用中，约简

与核是两个最重要的基本概念。

（1）一般约简

设

,PQ

是属性集，

Q

中的每一个属性都是不可省略的。如果

QP

且

()()IndQIndP

，则称

Q

是P的一个约简（Reduce）,记为

Re()dP

。另外，若

以

()CoreP

记P中所有不可省略的属性集合称为P的核（Core），那么所有约简

RedP的交正好等于P的核，即ReCorePdP。该式的意义在于，不仅

体现了核与所有约简的关系直接由约简得到，而且也表明了核是知识库中最重

要的部分，是进行知识约简的过程中不能删除的知识。

（2）相对约简

一般地，考虑一个分类相对于另一个分类的关系，这就导出了相对约简与

相对核的概念。在粗糙集中，相对约简的概念是条件属性相对决策属性的约简。

我们需要给出如下的概念：

设P和

Q

为论域

U

上的两个等价关系，定义

Q

关于P的相对肯定域，记为



P

PosQ，为论域

U

中的所有那些对象构成的集合，它们可以在分类

/UP

的知

识指导下，被正确地划入到

/UQ

的等价类之中。即

/

P

PosQPXXUQ





其中，PX



是集合X的下近似。

设P和Q为论域U上的两个等价关系，rP。如果



({})PPr

PosQPosQ





5

那么称r关于

Q

可省略，否则称为

Q

不可省略。特别，当

{}Pr

为P中的独立子

集（即它的每个元素都再不可省略），且

({})PPr

PosQPosQ



。那么称

{}Pr

为P的关于

Q

的相对约简，记为()

Q

IndP。P的所有关于

Q

的相对约简之交称为

P的关于

Q

的核，记为()

Q

CoreP。此时有()()

QQ

CorePIndP。

比较相对约简与一般约简的定义，我们能够发现，前者是在不改变决策属

性

Q

的前提下对特征属性集P的约简，而后者是不改变对于论域中对象的分辨

能力的前提下对于特征属性集的约简。

（3）决策表的约简

决策表约简的重要内容之一是简化决策表中的条件属性使得约简前后的决

策表具有相同的功能。同样的决策可以通过基于更少量的条件，便于我们借助

一些简单的手段就能获得同样要求的结果，这是事半功倍的好事。

（1）分辨矩阵和分辨函数

分辩矩阵是粗糙集中又一个重要概念，它将决策表中关于属性区分的信息

浓缩进一个矩阵当中，可用于决策表的属性约简。

一信息系统,,,SURVf中，

12

{,,...,}

n

Uxxx为论域，RCD是属性

集合，{,1,2,...,}

i

Caim与{,1,2,...,}

j

Ddjl分别为条件属性集和决策属性

集，

j

ax

k

是样本

j

x在属性a

k

上的取值。该系统的分辨矩阵定义为一个nn阶

矩阵[]

nnij

m



MS，其中第i行j行处元素





,

,1,2,...,

kkikjii

ij

aCaxaxDxDx

DxDxijn

















ij

m

，

也即，分辨矩阵中元素

ij

m是能够区别对象

i

x和

j

x的所有属性的集合。但若

i

x和

j

x属于同一个决策类时，则分辨矩阵中元素

ij

m的取值为空集。由定义可见，

[]

ijnn

m



MS是一个对称矩阵，主对角线上的元素是空集。因此只要考虑上半

6

或者下半三角部分足亦。

每一个分辨矩阵M(S)，可以诱导出一个分辨函数

Ms

f如下：





12

,,...,{1}

mijij

Ms

faaamjinm，，

它实际上是一个具有m元变量

12

,,...,,,1,2,...,

mi

aaaaCim的布尔函数，它是

ij

m

的合取，而ij

m

是矩阵项

ij

m中的各元素的析取。

根据分辨函数与约简的对应关系，可以得到计算信息系统S约简Red(S)的方法

为：







;

2);

3),

ms

SMS

MS

f

mij

1)计算信息系统的分辨矩阵

计算分辨矩阵对应的分辨函数f

计算分辨函数的最小析取范式其中每个析取分量对应一个约简.

下面举例说明如何利用分辨矩阵及分辨函数求约简及核。

设有信息系统

126

,,{,,...,},{,,,}SURUxxxRabcd其数据表格如下

表所示。

表信息系统数据表

U/RabcdU/Rabcd

1

x

0000

4

x

1212

2

x

0211

5

x

1001

3

x

0100

6

x

1212

解：根据式（1-11），分辨矩阵M（S）为：

表1-5分辨矩阵

U

1

x

2

x

3

x

4

x

5

x

6

x

1

x

2

x

b,c,d

3

x

bb,c,d

7

4

x

a,b,c,da,da,b,c,d

5

x

a,da,b,ca,b,db,c,d

6

x

a,b,c,da,ba,b,c,d—b,c,d

再根据式（1-12），分辨函数为















,,,{)

ms

fabcdbcdbabcdad

abcdbcdad

abcdadabcd

abcdabcdbcd

bcd

badadbd













因此，该信息系统有两个约简{,}{,}{}abbdb和，核是。

由此得到两个约简的数据表格，如表1-6所示。

表1-6两个约简数据表

UabUbd

1

x

00

1

x

00

2

x

02

2

x

21

3

x

01

3

x

10

4

x

12

4

x

22

5

x

10

5

x

01

6

x

12

6

x

22

（2）决策表

决策表是一类特殊而重要的知识表达系统，它是指当满足某些条件时，决

策应该怎样进行，多数决策问题都可以用决策表形式来表达，决策表根据知识

表达系统定义如下：

,SUR设为一知识表达系统，若R可划分为条件属性集C和决策属性集

D，即,CDRCD。则称为CD决策表，改记为,,,TURCD。Ind（C）

8

的等价类称为条件类，Ind(D)的等价类称为决策类。

决策表可分为一致决策表和非一致决策表。当D完全依赖于C（CD）时，

称为一致的；当部分依赖（01CkDk）时，称决策表是不一致的。

特别指出，决策表是否能够约简，取决于它是否为一致决策表。这是因为

不同原因可以产生相同结果，但同一个原因则不允许导致多种结果。对于一个

决策表，一般首先将其分解为一个一致决策表与一个不一致的决策表，然后再

对一致决策表进行约简。约简的方法还是使用分辨矩阵的方法。此时，属性特

征集

C

相对于决策属性集D的核()

D

CoreC恰为分辨矩阵中所有

ij

m为单元素集

决定。也即

()|..{},1,

Dkijijk

CoreCamstmaijn

特别，如果CC



是满足条件

,

ijij

Cmm

，且

C



是最小的，

那么称C



为C相对于决策属性集D的约简。

约简之后的决策表具有更少的条件属性，但却没有损失知识含量。同样对

于决策属性也可以约简。但是约简后的决策表还是不能直接看出条件与决策属

性之间的关系，因此还需要挖掘出决策生成规则。为此我们引入另外一个量来

刻画条件属性子集

i

XC与决策属性子集

j

YD之间关联强度。令

()(,)|,..(,),

ixxxi

DesXxvxUvVstfxavaX

()(,)|,..(,),

jxxxj

DesYxvxUvVstfxdvdY

分别称为属性子集

i

XC与决策属性子集

j

YD的描述集。此时，()

i

DesX与

()

j

DesY同在空间

UV

中，于是可以作如下两件事：

1.当()()

ij

DesXDesY时，定义()

i

DesX到()

j

DesY的映射

ij

T。

2.当()()

ij

DesXDesY时，定义确定因子度

(,)()()/(())

ijiji

XYCardDesXDesYCardDesX

9

特别，当(,)1

ij

XY时，

ij

T是确定的规则；当(,)1

ij

XY时，

ij

T是不确定的

规则。(,)

ij

XY

的大小反映的是满足属性子集

i

XC的对象中又能够满足决策

属性子集

j

YD的对象所占的比例。

5．基于分辨矩阵的启发式最小约简算法

以上介绍的约简的理论方法虽然简单，但只有通过计算机程序实现才有应

用意义。对于决策表比较复杂，条件属性较多的情况下，由于对存储空间的要

求过大，单纯使用分辨矩阵很难实现。下面建立一种基于分辨矩阵的启发式最

小约简算法，可以较好地解决这个问题。

基于约简是必须能够区分所有对象的最小属性集合可以推出：一个约简与

分辨矩阵的每一项的交都不空（加入与

ij

m不相交，那么对象i与j关于该约简是

不可分辨的）。于是得出如下“准约简”算法：

输入：决策表(U,C∪D)，其中,1,2,...,

i

Caim

1.选取初始约简

0

R。

2.对于所有,ij检查分辨矩阵的每一项

ij

m和候选约简集合

0

R的交

0ij

mR，判断：

a)如果

0ij

mR为空集，随机从

ij

m中选择一个属性，加到候选约简

集合

0

R中；

b)若不空，检查下一项。

3.重复这一过程，直到分辨矩阵中的每一项都检查过了。

输出：准约简。

程序完成之后，我们可以得到RCD中的一个条件属性子集R



。但是，一般

R



仅仅是一个“准约简”。因为上面的算法没有考虑它的最小性。为了使之变成

真的约简，我们需要如下的启发知识。

一个简单而有效的方法是根据|

ij

m|来对条件属性进行排序。我们知道，如

果

ij

m中只有一个属性，该属性一定是约简的成员。从分辨矩阵的定义可以看出，

分辨矩阵中某项的长度越短，该项就对分类所起的作用越大。而且该项出现的

越频繁，该项越重要。因此，我们对分辨矩阵排序时，除了按长度外，在长度

10

相同的情况下，出现频率高的属性更重要。归结为两个重要的启发式思想:

1)属性在分辨矩阵中出现的次数越多，属性的重要性越大；

2)属性出现在分辨矩阵中的项越短，属性的重要性越大。

于是提出了一种新的基于分辨矩阵的计算属性重要性的方法。对于一个分

辨矩阵)

ijnn

m



M=(，相应的属性a的重要性计算公式为:

11

0,

(),

1,

||

nn

ij

ij

ij

ij

ij

ij

am

fa

am

m

























式中|

ij

m|为

ij

m包含的属性的个数。由此得到了基于分辨矩阵的启发式约简算法

如下:

输入：决策表(U,C∪D)，其中,1,2,...,

i

Caim

输出：约简(Reduction)。

1）计算分辨矩阵M，并找出所有不包含核属性的属性组合S；

2）将所有不包含核属性的属性集合表示为析取范式的形式，即：

{,1,2,...,,1,2,...,}

ik

Paiskm

3）将P转化为析取范式的形式，并按（1-20）式计算属性的重要性；

4）取初始约简为R



（由准约简程序提供），对于重要性最小的属性a，令

(1)RRa



，

5）判断

((1))()IndRIndR





是否成立:

若成立，用

(1)R

代替R



，重复步骤4）－5)；

否则，以R



作为约简,结束程序。

6)以(1)()RiRia更新，重复4）－5)直到程序中止。