第三节 粗糙集(Rough Set,RS)
如果我们将研究对象看成是现象,那么我们可以将这些现象分类。现象被分为确定现象与不确定现象。不确定现象有分为随机现象,模糊现象和信息不全的粗糙现象。如下所示:
相对于前两种现象的处理,粗糙现象是基于不完全的信息或知识去处理不分明的现象,因此需要基于观测或者测量到的部分信息对数据进行分类,这就需要与概率统计和模糊数学不同的处理手段,这就是粗糙集理论。直观地讲,粗糙集是基于一系列既不知道多了还是少了,也不知道有用还是没用的不确定、不完整乃至于部分信息相互矛盾的数据或者描述来对数据进行
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
、推测未知信息。下面我们对粗糙集的基本特征、以及数学符号进行简述。
1.粗糙集的特点
粗糙集的特点是利用不精确、不确定、部分真实的信息来得到易于处理、鲁棒性强、成本低廉的决策
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。因此更适合于解决某些现实系统,比如,中医诊断,统计报表的综合处理等。粗糙集的另一个重要特点就是它只依赖于数据本身,不需要样本之外的先验知识或者附加信息,因此挑选出来的决策属性可以避免主观性,有英雄不问出身的意味。用粗糙集来处理的数据类型包括确定性的、非确定性的、不精确的、不完整的、多变量的、数值的、非数值的。粗糙集使用上、下近似来刻画不确定性,使得边界有了清晰的数学意义并且降低了算法设计的随意性。
3.粗糙集的基本概念
粗糙集要涉及论域
(这与模糊系统相似),还要涉及属性集合
(这被认为是知识,或者知识库)。当然,也要有属性值域
,以及从
到
的信息函数
。因此,一个信息系统
可以表示为一个四元组
。在不混淆的情况下,简记为
,也称为知识库。
等价关系(通常用来代替分类)是不可或缺的概念,根据等价关系可以划论域中样本为等价类。而每个等价类被称为同一个对象。但是,等价关系又是建立在不可分辨概念之上的,为了便于描述这里的等价关系,我们首先介绍不可分辨性。
设
为一个非空子集,如果
,均有
成立,那么,我们称
关于属性子集
不可分辨。
不可分辨关系,简记为
,是一种等价关系(易验证它满足等价关系的数学公理),于是
可以将论域
中的元素分成若干等价类,每一个等价类称为知识库的知识颗粒。全体等价类组成的集合记为
,称之为基本集合。若集合X可以表示成某些基本集的并时,则称X是B精确集,否则称为B粗糙集。
粗糙集中的“粗糙” 主要体现在边界域的存在,而边界又是由下、上近似来刻画的。对于任意
,
关于现有知识
的下、上近似分别定义为:
,
。
的确定域
,是指论域
中那些在现有知识
之下能够确定地归入集合
的元素的集合。反之,
被称为否定域。边界域是某种意义上论域的不确定域,即在现有知识
之下
中那些既不能肯定在
中,又不能肯定归入
中的元素的集合,记为
。
样本子集X的不确定性程度可以用粗糙度
来刻画,粗糙度的定义为:
式中
表示集合的基数(集合中元素的个数)。显然,
,如果
,则称集合X关于R是确定的;如果
,则称集合X关于R是粗糙的,
可认为是在等价关系R下逼近集合X的精度。
为了使得上述概念具体化,下面我们举一个例子说明如何理解和计算以上相应的概念和对应量。
例. 针对一下医学信息表我们来理解前面所提到的概念。
表1 某医疗信息表
属性
对象
条件属性C
决策属性D
头疼r1
肌肉疼r2
体温r3
流感
是
是
正常
否
是
是
高
是
是
是
很高
是
否
是
正常
否
否
否
高
否
否
是
很高
是
依据此表,如果取属性子集
,
。 那么我们下面给出
的上近似集、下近似集、确定域、边界域、粗糙度。
解:①计算论域U的所有R基本集:
令
②确定样本子集
与基本集的关系
③计算
、
、
:
④计算近似精确度:
与粗糙度类似,在给出了两个知识集(特征属性)的相对肯定域的概念
之后,我们也可以一个量来刻画两个知识集的依赖度。设
为一个知识库,
为两个知识集。令
,称为知识
依赖于知识
的依赖度。特别,当
时称为完全依赖;
时,部分依赖;
时,
完全独立于知识
。
3.知识约简
知识约简是粗糙集的核心
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
之一,它是研究知识库中哪些知识是必要的,以及在保持分类能力不变的前提下,删除冗余的知识。在粗糙集应用中,约简与核是两个最重要的基本概念。
(1)一般约简
设
是属性集,
中的每一个属性都是不可省略的。如果
且
,则称
是
的一个约简(Reduce),记为
。另外,若以
记
中所有不可省略的属性集合称为
的核(Core),那么所有约简
的交正好等于
的核,即
。该式的意义在于,不仅体现了核与所有约简的关系直接由约简得到,而且也表明了核是知识库中最重要的部分,是进行知识约简的过程中不能删除的知识。
(2)相对约简
一般地,考虑一个分类相对于另一个分类的关系,这就导出了相对约简与相对核的概念。在粗糙集中,相对约简的概念是条件属性相对决策属性的约简。我们需要给出如下的概念:
设
和
为论域
上的两个等价关系,定义
关于
的相对肯定域,记为
,为论域
中的所有那些对象构成的集合,它们可以在分类
的知识指导下,被正确地划入到
的等价类之中。即
其中,
是集合X的下近似。
设
和
为论域
上的两个等价关系,
。 如果
那么称
关于
可省略,否则称为
不可省略。特别,当
为
中的独立子集(即它的每个元素都再不可省略),且
。 那么称
为
的关于
的相对约简,记为
。
的所有关于
的相对约简之交称为
的关于
的核,记为
。此时有
。
比较相对约简与一般约简的定义,我们能够发现,前者是在不改变决策属性
的前提下对特征属性集
的约简,而后者是不改变对于论域中对象的分辨能力的前提下对于特征属性集的约简。
(3)决策表的约简
决策表约简的重要内容之一是简化决策表中的条件属性使得约简前后的决策表具有相同的功能。同样的决策可以通过基于更少量的条件,便于我们借助一些简单的手段就能获得同样要求的结果,这是事半功倍的好事。
(1)分辨矩阵和分辨函数
分辩矩阵是粗糙集中又一个重要概念,它将决策表中关于属性区分的信息浓缩进一个矩阵当中,可用于决策表的属性约简。
一信息系统
中,
为论域,
是属性集合,
与
分别为条件属性集和决策属性集,
是样本
在属性
上的取值。该系统的分辨矩阵定义为一个
阶矩阵
,其中第i行j行处元素
也即,分辨矩阵中元素
是能够区别对象
和
的所有属性的集合。但若
和
属于同一个决策类时,则分辨矩阵中元素
的取值为空集
。由定义可见,
是一个对称矩阵, 主对角线上的元素是空集。因此只要考虑上半或者下半三角部分足亦。
每一个分辨矩阵M(S),可以诱导出一个分辨函数
如下:
它实际上是一个具有
元变量
的布尔函数,它是
的合取,而
是矩阵项
中的各元素的析取。
根据分辨函数与约简的对应关系,可以得到计算信息系统S约简Red(S)的
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
为:
下面举例说明如何利用分辨矩阵及分辨函数求约简及核。
设有信息系统
其数据
表格
关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载
如下表所示。
表 信息系统数据表
U/R
a
b
c
d
U/R
a
b
c
d
0
0
0
0
1
2
1
2
0
2
1
1
1
0
0
1
0
1
0
0
1
2
1
2
解:根据式(1-11),分辨矩阵M(S)为:
表1-5 分辨矩阵
U
b,c,d
b
b,c,d
a,b,c,d
a,d
a,b,c,d
a,d
a,b,c
a,b,d
b,c,d
a,b,c,d
a,b
a,b,c,d
—
b,c,d
再根据式(1-12),分辨函数为
因此,该信息系统有两个约简
。
由此得到两个约简的数据表格,如表1-6所示。
表1-6 两个约简数据表
U
a
b
U
b
d
0
0
0
0
0
2
2
1
0
1
1
0
1
2
2
2
1
0
0
1
1
2
2
2
(2) 决策表
决策表是一类特殊而重要的知识表达系统,它是指当满足某些条件时,决策应该怎样进行,多数决策问题都可以用决策表形式来表达,决策表根据知识表达系统定义如下:
为一知识表达系统,若R可划分为条件属性集C和决策属性集D,即
。则称为
决策表, 改记为
。Ind(C)的等价类称为条件类,Ind(D)的等价类称为决策类。
决策表可分为一致决策表和非一致决策表。当D完全依赖于C(
)时,称为一致的;当部分依赖(
)时,称决策表是不一致的。
特别指出,决策表是否能够约简,取决于它是否为一致决策表。这是因为不同原因可以产生相同结果,但同一个原因则不允许导致多种结果。对于一个决策表,一般首先将其分解为一个一致决策表与一个不一致的决策表,然后再对一致决策表进行约简。约简的方法还是使用分辨矩阵的方法。此时,属性特征集
相对于决策属性集
的核
恰为分辨矩阵中所有
为单元素集决定。也即
特别,如果
是满足条件
, 且
是最小的,
那么称
为
相对于决策属性集
的约简。
约简之后的决策表具有更少的条件属性,但却没有损失知识含量。同样对于决策属性也可以约简。但是约简后的决策表还是不能直接看出条件与决策属性之间的关系,因此还需要挖掘出决策生成规则。为此我们引入另外一个量来刻画条件属性子集
与决策属性子集
之间关联强度。令
分别称为属性子集
与决策属性子集
的描述集。此时,
与
同在空间
中,于是可以作如下两件事:
1. 当
时, 定义
到
的映射
。
2. 当
时,定义确定因子度
特别, 当
时,
是确定的规则;当
时,
是不确定的规则。
的大小反映的是满足属性子集
的对象中又能够满足决策属性子集
的对象所占的比例。
5.基于分辨矩阵的启发式最小约简算法
以上介绍的约简的理论方法虽然简单,但只有通过计算机程序实现才有应用意义。对于决策表比较复杂,条件属性较多的情况下,由于对存储空间的要求过大,单纯使用分辨矩阵很难实现。下面建立一种基于分辨矩阵的启发式最小约简算法,可以较好地解决这个问题。
基于约简是必须能够区分所有对象的最小属性集合可以推出:一个约简与分辨矩阵的每一项的交都不空(加入与
不相交,那么对象
与
关于该约简是不可分辨的)。 于是得出如下“准约简”算法:
输入:决策表(U,C∪D),其中
1. 选取初始约简
。
2. 对于所有
检查分辨矩阵的每一项
和候选约简集合
的交
,判断:
a) 如果
为空集,随机从
中选择一个属性,加到候选约简集合
中;
b) 若不空,检查下一项。
3. 重复这一过程,直到分辨矩阵中的每一项都检查过了。
输出:准约简。
程序完成之后,我们可以得到
中的一个条件属性子集
。但是,一般
仅仅是一个“准约简”。因为上面的算法没有考虑它的最小性。为了使之变成真的约简,我们需要如下的启发知识。
一个简单而有效的方法是根据|
|来对条件属性进行排序。我们知道,如果
中只有一个属性,该属性一定是约简的成员。从分辨矩阵的定义可以看出,分辨矩阵中某项的长度越短,该项就对分类所起的作用越大。而且该项出现的越频繁,该项越重要。因此,我们对分辨矩阵排序时,除了按长度外,在长度相同的情况下,出现频率高的属性更重要。归结为两个重要的启发式思想:
1)属性在分辨矩阵中出现的次数越多,属性的重要性越大;
2)属性出现在分辨矩阵中的项越短,属性的重要性越大。
于是提出了一种新的基于分辨矩阵的计算属性重要性的方法。对于一个分辨矩阵
,相应的属性a的重要性计算公式为: