《粗糙集理论介绍》PPT课件

点之
若rij＝1, 且 i≠j, 则rji＝0
对M2中1所 在位置,M 中相应位置 都是1
假如两 假如顶
点之
点xi
间有边, 到xj有边,
一定
xj
13
4、等价关系
等价关系旳定义：设R是非空集合A上旳关系，假如满足 ⑴ R是自反旳; ⑵ R是对称旳; ⑶ R是传递旳; 则称R是A上旳等价关系。
21
内容提要
一、概述 二、知识分类 三、知识旳约简 四、决策表旳约简 五、粗糙集旳扩展模型 六、粗糙集旳试验系统 七、粒度计算简介
22
一、 概述
现实生活中有许多模糊现象并不能简朴地 用真、假值来表达﹐怎样表达和处理这些现 象就成为一种研究领域。早在1923年谓词逻 辑旳创始人G.Frege就提出了模糊(Vague)一 词，他把它归结到边界线上，也就是说在全 域上存在某些个体既不能在其某个子集上分 类，也不能在该子集旳补集上分类。
自反性 反自反性 对称性 反对称性 传递性
12
关系性质旳三种等价条件
体 现 式
关系 矩阵
关系图
自反性 IAR
主对角 线元素 全是1
每个顶 点都有 环
反自反性 R∩IA=
主对角线 元素全是 0
每个顶点 都没有环
对称性 R=R1
反对称性 R∩R1 IA
传递性 RRR
矩阵是对称 矩阵
假如 两个 顶
定义 假如一种集合满足下列条件之一： （1）集合非空, 且它旳元素都是有序对 （2）集合是空集 则称该集合为一种二元关系, 简称为关系，记作R. 如<x,y>∈R, 可记作 xRy；假如<x,y>R, 则记作xRy
实例：R={<1,2>,<a,b>}, S={<1,2>,a,b}. R是二元关系, 当a, b不是有序对时，S不是二元关系 根据上面旳记法，能够写1R2, aRb, aSb等.

（3）粗糙集理论不是万能的，它不可能解决 一切含糊的、模糊的不确定性问题。
（4） 需要其它方法的补充。
一般地，将粗糙集理论与模糊集理论、 Dempster-Shafer证据理论等其它相关的不确定性 处理方法构成互补，是一种非常自然而又可行的 方法。
1.2 粗糙集理论的发展简况
（1）20世纪70年代，Pawlak和一些波兰科学院、华 沙大学的逻辑学家，诞生以来，经过许多数学家和 计算机科学家的努力，其理论上日趋成熟，特别 是在20世纪80年代末和90年代初，由于粗糙集理 论在数据挖掘、知识发现等领域得到了成功的应 用，它受到了国际上的广泛关注。
相对于其它处理不确定和模糊性的理论工具 （如模糊集理论、Dempster-Shafer证据理论等）
可分为两大类：有决策的分析和无决策的分析。 （1）有决策的分析，主要包括：监督学习与决策 分析；（2）对无决策的分析，主要是数据压缩、 化简、聚类、模式发现、机器发现等。
Jelonek等人成功地应用粗糙集理论对神经网 络的输入属性及属性域进行约简。用粗糙集理论 获取知识和进行机器学习的有代表性的应用实例 是，Kansas大学开发的“基于粗糙集方法的学习 系统”（LERS）。这个系统的规则发现能力能帮 助那些用不完全知识进行工作的专家系统建立知 识库。
粗糙集理论认为，“概念”就是对象的集合， “知识”就是将对象进行分类的能力。将概念看
成是“对象的集合”的思想，实质上是一种强调
概念的“外延”的表达方式。假设我们对全域中 的对象具有必要的“信息”或“知识”，这些 “知识”可以被认为是关于对象的内涵（如属性、 特征或描述）的某种刻划。通过这些知识就能够
研究生《人工智能》课件
粗糙集理论及其应用
Rough Set Theory and its Applications

头疼 是 是 是
肌肉疼 是 是 是
体温 正常 高 很高
流感 否 是 是
否
否 否
是
否 是
正常
高 很高
否
否 是
头疼
是 是
体温
正常 高
流感
否 是
是
否 否 否 否 否
很高
Байду номын сангаас正常 高 很高 高 很高
是
否 否 是 是 否
必然规则有哪些？可能规则有哪些？
RS理论概论
粗糙集(Rougn Set,RS)理论是由波兰学者 Pawlak Z在1982年提出的。粗糙集(Rougn Set, RS)理论是一种刻划不完整性和不确定性 的数学工具，能有效地分析和处理不精确、不 一致、不完整等各种不完备信息，并从中发现 隐含的知识，揭示潜在的规律。 该理论近年日益受到国际学术届的重视，已经 在模式识别、机器学习、决策支持、过程控制、 预测建模等许多科学与工程领域得到成功的应 用。
集合X关于R的上逼近(upper approximation) 定义为：
R*(X)是由所有与X相交非空的等效类［a］R 的并集，是那些可能属于X的对象组成的最 小集合.显然，R*(X)+NEG(X)=论域U
集合X的边界区(boundary region)定义为：
BN(X)为集合X的上逼近与下逼近之差. 如果BN(X)是空集，则称X关于R是清晰 的(crisp)；反之如果BN(X)不是空集，则 称集合X为关于R的粗糙集(rough set).
给定一个有限的非空集合U称为论域，R 为U上的一族等效关系.R将U划分为互不 相交的基本等效类，二元对K=(U，R)构 成一个近似空间(approximation space). 设X为U的一个子集，a为U中的一个对象， ［a］R表示所有与a不可分辨的对象所组 成的集合，即由a决定的等效类.当集合X 能表示成基本等效类组成的并集时，则 称集合X是可以精确定义的；否则，集合 X只能通过逼近的方式来刻划。

November 18, 2002第一稿 September 30, 2006第四次修改稿
2019年8月23
感谢你的观看
1
Outline
Rough sets理论的快速入门方法 Rough sets理论的发展概述 Rough sets理论的基本原理 计算举例 课后研读论文
2019年8月23
“模糊集”（Fuzzy Sets） 1965年美国数学家L. A. Zadeh首次提出 无法解决G. Frege提出的“含糊”问题 未给出计算含糊元素数目的数学公式
……
2019年8月23
感谢你的观看
6
粗糙集理论的提出（续2）
“粗糙集”（Rough Sets）
1982年波兰数学家Z. Pawlak首次提出 将边界线区域定义为“上近似集”与“下近似集”的差
2019年8月23
感谢你的观看
10
粗糙集理论的发展历程（续2）
1993和1994年，分别在加拿大、美国召开第二、三届 国际粗糙集与知识发现（或软计算）研讨会。
1995年，Pawlak等人在《ACM Communications》上 发表“Rough sets”，极大地扩大了该理论的国际影响。
评价某一分类（属性）的重要性
剔除冗余属性
数据集的降维
发现数据模式
挖掘决策规则
在其它领域的应用
金融商业
……
2019年8月23
感谢你的观看
18
6.3 粗糙集理论的基本原理
6.3.1 基本概念 “知识”的定义
使用等价关系集R对离散表示的空间U进行 划分，知识就是R对U划分的结果。
理论、Dempster-Shafer证据理论的关系和互补 粒度计算：粗糙集理论是其重要组成之一 高效算法：导出规则的增量式算法、简约的启发式

Then，there are:
I*(x)={x2，x4} 回 I*(x)={x1，x3，x7，x2，x4} 回
回24
近似的示意图
假定有一个信息系统, 有两个属性. 属性一有5个值, 属性二有6个值. 现在有一个要近似的集合(X), 在图
中用红色的圆表示.
仅使用第一个属性进行划分的情形. 正区域为空. 蓝色区域为负区域.
● 基本集：由论域中相互间不可区分的对象组成的 集合，是组成论域知识的颗粒。
返回
例1 一玩具积木的集合如下表描述（表1）
R1(颜色) R2(形状) R3(体积)
X1
红
圆形
小
X2
蓝
方形
大
X3
红
三角形
小
X4
蓝
三角形
小
X5
黄
圆形
小
X6
黄
方形
小
X7
红
三角形
大
X8
黄
三角形
大
取不同的属性组合,可得不同的等价关系（粒度)为： IND（R1）＝{{x1,x3,x7}, {x2,x4}, {x5,x6,x8}} IND（R1,R2）＝{{x1}, {x2}, {x3,x7}, {x4}, {x5}, {x6}, {x8}}
Step2. 针对各个属性下的初等集合寻找下近似和上近似。
以“头疼＋肌肉痛＋体温”为例，设集合X为患流感的 人的集合，I为3个属性构成的一个等效关系： {p1},{p2,p5},{p3},{p4},{p6}， 则
X={P1,P2,P3,P6} I={{p1},{p2,p5},{p3},{p4},{p6}}
知识判断肯定属于X的对象所组成的最大集合，有时也称为X的正 区（positive region），记做POS（X）

粗糙集理论能够处理不确定性和模糊性，而神经网络则能够通过学习过 程找到数据中的模式。将粗糙集与神经网络结合，可以利用粗糙集对数 据的不确定性进行建模，并通过神经网络进行分类或预测。
粗糙集可以用于提取数据中的决策规则，这些规则可以作为神经网络的 训练样本。通过训练，神经网络可以学习到决策规则，并用于分类或预 测。
边界区域
近似集合中的不确定性区 域，即既不属于正域也不 属于负域的元素集合。
粗糙集的度量
精确度
描述了集合中元素被近似集合 包含的程度，即属于近似集合
的元素比例。
覆盖度
描述了近似集合能够覆盖的元 素数量，即近似集合的大小。
粗糙度
描述了集合被近似程度，是精 确度和覆盖度的综合反映。
知识的不确定性
描述了知识表达系统中属性值 的不确定性程度，与粗糙度相
经典粗糙集理论
目录
• 粗糙集理论概述 • 粗糙集的基本概念 • 粗糙集的运算与性质 • 粗糙集的决策分析 • 粗糙集与其他方法的结合 • 经典粗糙集理论案例研究
01 粗糙集理论概述
定义与特点
定义
粗糙集理论是一种处理不确定性和模 糊性的数学工具，通过集合近似的方 式描述知识的不完全性和不确定性。
粗糙集理论中的属性约简可以用于简化神经网络的输入特征，降低输入 维度，提高分类或预测的准确率。
粗糙集与遗传算法
01
遗传算法是一种全局优化算法，能够通过模拟自然界的进化过程来寻找最优解 。将粗糙集与遗传算法结合，可以利用粗糙集对数据的分类能力，结合遗传算 法的全局搜索能力，寻找最优的分类规则或决策规则。
02
粗糙集可以用于生成初始的分类规则或决策规则，然后利用遗传算法对这些规 则进行优化，通过选择、交叉、变异等操作，寻找最优的规则组合。

p i,j {c C :c(,x i) d c(x x ij) () } d d (x ,x ji)) (d (x j)
21
差别矩阵
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
u1 u2 u3 u4 u5
3
Y
Y
Y
NY
8,9,15
N
N
N
Y
NY N
4
Y
Y
Y
NY
10,11,12,14
N
N
Y
Y
YY N
5
Y
Y
Y
NY
YY
13
N
N
Y
N
N
6
Y
Y
Y
NY
YY
16
Y
N
N
Y
N
7
N
Y
Y
NY
NY
17
Y
N
Y
N
N
8
N
N
N
YY
NN
9
N
N
N
YY
YN
实例集 10 群居 N 会飞 N 产卵 Y 肺呼吸NY 鸟类Y N
肺呼吸 热血动物 食物 鸟类
13
约简理论
主要思想：保持分类能力不变的条件下， 删除冗余的、不必要的属性或属性值，达 到知识简化的目的。
14
示例:一种动物是否是鸟类
实例集 群居 会飞 产卵 肺哺呼乳吸 会游鸟泳类
实例集
群居 会飞 产卵 肺呼吸 鸟类
1
N
Y
Y
NY

具有相同或相似信息的 对象不能被识别。
粗糙集概念示意图
粗糙集理论方法及其应用 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程
2 粗粗糙糙集集理理论论思思想想
粗糙集理论方法及其应用 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程
2.3 粗糙近似
定义 给定一个知识表示系统 S (U, A,V, f ) ， P A，X U ，x U ，集合 X 关于 I 的下近似、 上近似、负区及边界区分别为
apr (X ) {x U : I(x) X} p
aprP (X ) {x U : I(x) X }
neg p ( X ) {x U : I (x) X }
2.2 不可分辨关系 （Indiscribility relation)
❖ 不可分辨关系是一个等 价关系(自反 的、对称 的、传递的）。
❖ 包含对象x的等价类 记为I(x)。等价类与知 识粒度的表达相对应， 它是粗糙集主要概念， 如近似、依赖及约简等， 定义的基础
粗糙集理论方法及其应用 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程
决策属性(D)
U
a1
a2
a3
d
n1
High
Low
Low
Low
n2
Medium
High
Low
High
n3
High
High
High
High
粗糙集理论方法及其应用 病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程

此外，粗糙集的数字特征和粗糙集的拓扑特征之间存在一种关系。首先， 如果集合为内不可定义或全不可定义，则其精度为0；其次，当集合为外不可 定义或全不可定义时，则它的补集的精度为0。这样，即使知道了集合的近似 精度，我们也不能确定它的拓扑结构；反过来，集合的拓扑结构也不具备精度 的信息。
学习交流PPT
20
以用不同的属性集对论域的对象进行描述，以表达关于论域完全相同的知识。
如果IND(S1)IND(S2)，我们称知识库K1（知识S1）比知识库K1（知识S2）更精 细，或者说K2（知识S2）比K1（知识S1）更粗糙。当S1比S2更精细时，我们也 称S1为S2的转化，或S2为S1的泛化。泛化意味着将某些范畴组合在一起，而特化 则是将范畴分割成更小的概念。如果上述两种情形都不满足，则称两个知识库
R ( X ) { X | ( x U ) ([x]R X )} U{Y | ( Y U / R ) (Y X )}, (2.2)
R ( X ) { X | ( x U ) ([x]R I X )}
U{Y | ( Y U / R ) (Y I X )}, (2.3)
在粗糙集理论中，主要讨论的是那些能 够在论域U上形成划分或覆盖的知识。
学习交流PPT
2
我们知道U的划分{X1, X2,…, Xn}与U上
的等价关系R一一对应，即给定U的一个划
分{X1, X2,…, Xn}等同于给定U上的一个等
价关系R，从数学的角度讲，关系的表示和
处理比分类的表示和处理简单得多，因此，
n
U /R { X 1 ,X 2,...X n } (U U X i,n 1 )。如果 i 1
i1,2,..n.,，都有 R(Xi) U 成立，则对于任意
i1,2,...,n ，都有 R(Xi) .

红色的圆表示.
仅使用第一个属性进行划分的情形. 正区域为空. 蓝色区域为负区域.
使用两个属性进行划分的情况
加入第二个属性
负区域
正区域(下近似)
边界区域
上近似
综合表示
Rough Set 的应用
(一)知识发现
RD {(x, y); gk (x) gk (y)(k q)} 是按照决策集D产生的
X1
正常
是
否
x2
高
是
是
x3
高
是
是
x4
正常
否
否
x5
高
否
否
x6
高
否
是
x7
高
否
是
x8
正常
否
否
取B为各种属性组合, 则得到不同等价类取B=A,则等价 类为：{{x1},{x2,x3},{x4,x8},{x5,x6,x7}}
基本概念(三) 上下近似
X U 它在关系 RB下的上下近似集 RB(X ) {x;[x]B X} 为 X 的下近似集
粗糙集理论的基本概念
不可区分关系/等价类. 上近似和下近似.
基本概念(一) 信息系统
称为(U, A,F,D,G) 一个信息系统, 其中 为对象集, U {x1,x2,...xn} 为属性集, A {a1,a2,...ap} 为决策集, D {d1,d2,...dq} F 为U 和 A的关系集, F { f j : j p} G 为U 和 D的关系集, G {g j : j q}
求约简是属性选择问题. 约简有各种各样的标 准(保持属性集合分类能力不变,保证分布函数 不变, 保证决策上下近似不变.etc) 协调集与约简
RB(X ) {x;[x]B X }为 X 的上近似集 如果上下近似是相等的, 则这是一个精确集合, 否则它是一个粗糙集, 其中下近似称为该概念 的正区域, 上下近似的差称为边界.上近似以外 的区域称为负区域.