《Rough Sets理论概述》由会员分享，可在线阅读，更多相关《Rough Sets理论概述（47页珍藏版）》请在金锄头文库上搜索。
1、Rough Sets理论概述理论概述赵素云机器学习研究中心2004年11月24日1主要内容vRough Sets理论产生背景vRough Sets基本理论vRough Sets理论的应用领域vRough Sets理论的局限及其改进vRough Sets发展前景展望2Rough Sets的产生背景v边界问题的提出现实生活：存在许多含糊的现象，并不能简单地用真、假值来表示。在1904年，谓词逻辑的创始人 G.frege 提出了含糊(vague) 一词，他把含糊现象归结到边界线上。全域上存在一些个体不能在其某个子集上分类，也不能在该子集的补集上分类。经典逻辑：只有真、假二值之分。3Rough Set
2、s的产生背景v应运而生的理论1965年，L. A. Zadeh提出Fuzzy Sets 的概念，试图通过这一理论解决G.frege的含糊概念。FSFS方法：利用隶属函数描述边界上的不确定对象。1982年，波兰华沙理工大学 Z.Pawlak 教授针对G. frege的边界线区域思想提出了Rough Sets理论。RSRS方法：把无法确认的个体都归属于边界区域，把边界区域定义为上近似集和下近似集的差集。4Rough Sets和Fuzzy Sets比较 错误认识：两者是相互竞争的。错误认识：两者是相互竞争的。 正确观点：是描述知识不精确性与不确定性的两个不正确观点：是描述知识不精确性与不确定性的两个
3、不同的概念，二者相互补充，有望显示出更强的功能。同的概念，二者相互补充，有望显示出更强的功能。 相同点：都是处理不确定信息的理论。相同点：都是处理不确定信息的理论。 不同点不同点5Rough Sets和Fuzzy Sets比较研究对象： FS研究人类语言产生的集合边界的病态定义，即边界的不分明性； RS研究认知能力产生的集合对象之间的不可分辨性。研究方法： FS通过隶属函数描述对象关于集合的不确定性；RS引入一对上下近似集合，用它们的差集来描述不确定的对象。需指出的一点：FS的隶属函数带有很强的主观意志；RS通过客观存在的结构（上下近似的差集）来处理边界上的不确定性，即知识的含糊度是可以用公式
4、来计算的。 6 Rough Sets基础理论vRS知识表示方法vRS约简理论7 RS理论的几个基本概念v不可分辨关系(Indiscernibility Relation)v下近似集(lower approximation)v上近似集(upper approximation)8不可分辨关系nRS理论是基于不可分辨关系的（等价关系）。玩具集合颜色形状J=1红色圆的圆的J=2红色圆的圆的J=3红色方的J=4红色方的J=5黄色圆的圆的J=6黄色圆的圆的J=7黄色方的J=8黄色方的9划分的图示1 2 3 4 7 8 5 6 属性集属性集 等价关系等价关系 划分划分 知识知识10Rough Sets示意图
5、深色深色浅粉色浅粉色11Rough Sets示意图Rough set上近似上近似下近似下近似12RS的约简理论vRS理论的核心内容。v主要思想：保持相对分类能力不变的条件下，删除冗余的、不必要的属性或属性值，达到知识简化的目的。v基本概念：约简（Reduct）、核（Core） 相对约简（Relative Reduct）、相对核(Relative Core)等。13RS的约简理论论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色
6、小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定表一：儿童对玩具的喜好情况14示例的不一致论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定表一：儿童对玩具的喜好情况15属性集的相对核v是属性集的核心部分v合适唯一的，确定的。16属性集的相对核论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有
7、毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定表一：儿童对玩具的喜好情况17属性集的相对核论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定表一：儿童对玩具的喜好情况18属性集的相对核论
8、域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定表一：儿童对玩具的喜好情况19属性集的相对核论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材
9、肯定J=9黄色小软有毛的长毛绒肯定表一：儿童对玩具的喜好情况20属性集的相对核论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定表一：儿童对玩具的喜好情况21论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬
10、粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定表一：儿童对玩具的喜好情况属性集的相对核22属性集的相对核论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定表一：儿童对玩具的喜好情况23属性集的相对约简v属性集的相对约简即是保持条件属性相对于决策属性分类能力不变的最小条件属性子集。v相对约简不是唯一的
11、。v相对约简与相对核之间的关系： 所有相对约简的交等于相对核。24属性集的相对约简论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定25属性集的相对约简论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的
12、金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定26属性集的相对约简论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定27属性集的相对约简论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光
13、滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8黄色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定28属性集的相对约简论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定29属性集的相对约简论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适
14、中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定30属性集的相对约简论域颜色尺寸手感质感制作材料喜爱与否J=1蓝色大硬粗糙的塑料否定J=2蓝色中适中有毛的木材否定J=3绿色中适中光滑的塑料中立J=4红色中适中有毛的木材中立J=5绿色大硬光滑的木材中立J=6黄色小硬粗糙的金属肯定J=7黄色小软粗糙的塑料肯定J=8绿色大硬光滑的木材肯定J=9黄色小软有毛的长毛绒肯定31简化“儿童玩具”信息表v删除信息表中的列（删除多余的属性）v合并重复的行v删除信息表中的点（删除不必要的属性值）32“玩具
15、喜好”信息表的简化结果论域颜色喜爱与否1（2）蓝色否定2（2）绿色中立3（1）红色中立4（3）黄色肯定5（1）绿色肯定语言描述：语言描述：如果玩具是蓝色，则儿童不喜欢。如果玩具是黄色，则儿童喜欢。如果玩具是红色，则儿童持中立态度。如果是绿色，则儿童持中立或肯定态度。33“脊椎动物”信息表的简化实例集实例集群居群居会飞会飞产卵产卵哺乳哺乳会游泳会游泳肺呼吸肺呼吸热血动物热血动物食物食物鸟类鸟类1NYYNNYY1Y2NYYNNYY2Y3YYYNNYY1Y4YYYNYYY0Y5YYYNYYY1Y6YYYNYYY2Y7NYYNNYY2Y8NNNYNYY1N9NNNYYYY1N10NNYNYYN1N11
16、NNYNYYY1N12NNYNNYN1N13NNYNYNN1N14NNYNYYN2N15NNNYNYY0N16YNNNYYY1N17YNYNYNN1N34最小规则集规则规则群居群居会飞会飞产卵产卵肺呼吸肺呼吸鸟类鸟类1（7）#YY#Y2（4）#N#N3（5）NN#N4（1）#NN语言描述：语言描述：会飞而且可以产卵的动物是鸟类；不用肺会飞而且可以产卵的动物是鸟类；不用肺呼吸的或不能产卵的动物不是鸟类；既不呼吸的或不能产卵的动物不是鸟类；既不群居也不会飞的动物也不是鸟类。群居也不会飞的动物也不是鸟类。35Rough Sets理论的应用领域v人工智能，专家系统v决策支持系统v知识与数据发现v模式识
17、别与分类v故障检测，开关电路v信息系统分析，归纳推理详见 Z. Pawlak, Rough Sets: Theoretical Aspects of Reasoning about Data M. Dordrecht: Kluwer Academic Publishers, 1991. 36Rough Sets理论的局限及其改进vv缺乏对噪音数据的适应能力，对于数据的扰缺乏对噪音数据的适应能力，对于数据的扰动较敏感。动较敏感。vv在计算在计算 reduct reduct 过程中，易产生组合爆炸。计过程中，易产生组合爆炸。计算出所有约简的时间复杂度是指数的。算出所有约简的时间复杂度是指数的。vv
18、适用于符号型数据库，对于原始模糊数据处适用于符号型数据库，对于原始模糊数据处理能力较弱。理能力较弱。37变精度Rough Sets模型vPawlak 提出的 RS 模型的一个局限是它所处里的分类是完全的、肯定的，严格按等价类来分类的。没有某种程度上的“灵活性”，对于噪音较敏感。v另一个局限是从模型中得到的结论仅适用于这些对象集。但实际应用中, 需要将小规模的对象集中得到的结论应用于大规模的对象集中去。38变精度Rough Sets模型39变精度Rough Sets模型下近似下近似上近似上近似分类错误分类错误率不大于率不大于给定阈值给定阈值a时时分类错误分类错误率大于给率大于给定值定值1-a时时
19、40O(m n2): mn差别矩阵方法Skowron .A 1991 O(m2 n): mn树表示方法赵岷中科院自动化所博士论文2004从计算效率考虑，需要两类算法，以满足不同需求计算Reduct的算法的改进两类信息系统两类信息系统两类算法两类算法41模糊Rough Sets模型vPawlak 提出的 RS 模型是针对于符号值提出的，而实际生活中，经常会遇到模糊数据或连续型数据。v目前，模糊粗糙集模型粗略上可以分为两大类：基于RS的模糊知识表示模型，这类模型无法用于处理实际问题中的模糊知识简化问题；另一类是基于RS的模糊知识简化模型。相比较而言，对后者所做的工作较少。42模糊Rough Set
20、s模型等价关系划 分约简、核最小算法：一组产生式规则模糊相似关系模糊相似矩阵模糊约简、模糊核最小算法：一组模糊产生式规则43模糊Rough Sets模型 优点： 知识简化的过程中没有将模糊数据离散化或模糊离散化。知识简化的过程中没有将模糊数据离散化或模糊离散化。 采用动态过程简化原始模糊数据，所得结果有一定的抗干扰采用动态过程简化原始模糊数据，所得结果有一定的抗干扰能力。能力。 知识简化的结果是模糊产生式规则，可以根据实际问题的需知识简化的结果是模糊产生式规则，可以根据实际问题的需要作出相应的决策，具有较强的适应性。要作出相应的决策，具有较强的适应性。 当阈值取值为当阈值取值为1 1，该模型退
21、化为经典的，该模型退化为经典的RSRS模型。模型。44模糊Rough Sets模型有待解决的问题：阈值如何选取，才能使得学习得到的结果最佳？该模型应用于处理连续型数据，是否可行？是否比先离散化，再进行知识简化的方法好？如果好的话，其优势又体现在哪里？将该模型改进，用于处理连续值不完备信息系统，是否可行？ 45Rough Sets发展前景展望vRS理论虽然在实际生活中得到了广泛应用，但仍有许多问题尚待解决，如RS对大规模数据集处理能力较弱；只能处理静态数据库，不能实时（on line）动态处理数据等。v基于RS哲学的不精确推理的逻辑，是重要的课题之一。v基于RS对神经网络和遗传算法方法的开发也很重要。vRough控制，即基于RS理论的控制也是一个很有前途的应用领域。vRS理论与非标准分析、非参数统计学及定性物理学之间的关系是另一项重要课题。46谢 谢！47
