-
粗糙集 编辑
粗糙集理论,是继概率论、模糊集、证据理论之后的又一个处理不确定性的数学工具。作为一种较新的软计算方法,粗糙集近年来越来越受到重视,其有效性已在许多科学与工程领域的成功应用中得到证实,是当前国际上人工智能理论及其应用领域中的研究热点之一。1982年,波兰数学家Z.Pawlak发表了经典论文Rough Sets,意味着粗糙集理论的诞生。
多年来,研究人员一直在努力寻找科学地处理不完整性和不确定性的有效途径。模糊集和基于概率方法的证据理论是处理不确定信息的两种方法,已应用于一些实际领域。但这些方法有时需要一些数据的附加信息或先验知识,如模糊隶属函数、基本概率指派函数和有关统计概率分布等,而这些信息有时并不容易得到。
1982年波兰学者Z. Paw lak 提出了粗糙集理论——它是一种刻画不完整性和不确定性的数学工具,能有效地分析不精确,不一致(inconsistent)、不完整(incomplete) 等各种不完备的信息,还可以对数据进行分析和推理,从中发现隐含的知识,揭示潜在的规律。
粗糙集理论是建立在分类机制的基础上的,它将分类理解为在特定空间上的等价关系,而等价关系构成了对该空间的划分。粗糙集理论将知识理解为对数据的划分,每一被划分的集合称为概念。粗糙集理论的主要思想是利用已知的知识库,将不精确或不确定的知识用已知的知识库中的知识来(近似) 刻画。
该理论与其他处理不确定和不精确问题理论的最显著的区别是:它无需提供问题所需处理的数据集合之外的任何先验信息,所以对问题的不确定性的描述或处理可以说是比较客观的,由于这个理论未能包含处理不精确或不确定原始数据的机制,所以这个理论与概率论、模糊数学和证据理论等其他处理不确定或不精确问题的理论有很强的互补性.
粗糙集是一种较有前途的处理不确定性的方法,相信今后将会在更多的领域中得到应用. 但是,粗糙集理论还处在继续发展之中,正如粗糙集理论的创立人Z. Paw lak 所指出的那样,尚有一些理论上的问题需要解决,诸如用于不精确推理的粗糙逻辑(Rough logic) 方法,粗糙集理论与非标准分析(Nonstandard analysis) 和非参数化统计(Nonparametric statistics)等之间的关系等等. 将粗糙集与其它软计算方法(如模糊集,人工神经网络,遗传算法等) 相综合,发挥出各自的优点,可望设计出具有较高的机器智商(M IQ) 的混合智能系统(Hybrid Intelligent System),这是一个值得努力的方向.
知识
“知识”这个概念在不同的范畴内有多种不同的含义。在粗糙集理论中,“知识”被认为是一种分类能力。人们的行为是基于分辨现实的或抽象的对象的能力,如在远古时代,人们为了生存必须能分辨出什么可以食用,什么不可以食用;医生给病人诊断,必须辨别出患者得的是哪一种病。这些根据事物的特征差别将其分门别类的能力均可以看作是某种“知识”。
不可分辨关系
分类过程中,相差不大的个体被归于同一类,它们的关系就是不可分辨关系(indiscernibility relation). 假定只用两种黑白颜色把空间中的物体分割两类,{黑色物体},{白色物体},那么同为黑色的两个物体就是不可分辨的,因为描述它们特征属性的信息相同,都是黑色.
如果再引入方,圆的属性,又可以将物体进一步分割为四类: {黑色方物体},{黑色圆物体},{白色方物体},{白色圆物体}. 这时,如果两个同为黑色方物体,则它们还是不可分辨的. 不可分辨关系是一种等效关系(equivalence relationship),两个白色圆物体间的不可分辨关系可以理解为它们在白,圆两种属性下存在等效关系.
基本集
基本集(elementary set) 定义为由论域中相互间不可分辨的对象组成的集合,是组成论域知识的颗粒. 不可分辨关系这一概念在粗糙集理论中十分重要,它深刻地揭示出知识的颗粒状结构,是定义其它概念的基础. 知识可认为是一族 等效关系,它将论域分割成一系列的等效类。
集合
粗糙集理论延拓了经典的集合论,把用于分类的知识嵌入集合内,作为集合组成的一部分. 一个对象a 是否属于集合X 需根据现有的知识来判断,可分为三种情况:
⑴ 对象a 肯定属于集合X ;
⑵ 对象a 肯定不属于集X ;
⑶ 对象a 可能属于也可能不属于集合X 。
集合的划分密切依赖于我们所掌握的关于论域的知识,是相对的而不是绝对的.给定一个有限的非空集合U 称为论域,I 为U 中的一族等效关系,即关于U 的知识,则二元对 K = (U,I) 称为一个近似空间(approximation space). 设x 为U 中的一个对象,X为U 的一个子集,I (x) 表示所有与x 不可分辨的对象所组成的集合,换句话说,是由x 决定的等效类,即I (x) 中的每个对象都与x 有相同的特征属性(attribute)。
姓名 | 教育程度 | 是否找到了好工作 |
高中 | 否 | |
高中 | 是 | |
李得 | 小学 | 否 |
刘保 | 大学 | 是 |
博士 | 是 |
表格的数据描述了一些人的教育程度以及是否找到了较好工作,旨在说明两者之间的关系. 其中王治,马丽,赵凯等称为对象(objects),一行描述一个对象. 表中的列描述对象的属性. 粗糙集理论中有两种属性: 条件属性(condition attribute) 和决策属性(decision attribute). 本例中"教育程度"为条件属性;"是否找到了好工作"为决策属性。
设O 表示找到了好工作的人的集合,则O = {马丽,刘保,赵凯},设I 表示属性"教育 程度"所构成的一个等效关系,根据教育程度的不同,该论域被分割为四个等效类: {王治,马丽},{李得},{刘保},{赵凯}. 王治和马丽在 同一个等效类中,他们都为高中文化程度,是 不可分辨的. 则:
集合O 的下逼近(即正区) 为 I *(O) = PO S (O) = {刘保,赵凯}
集合O 的负区为 N EG (O) = {李得}
集合O 的边界区为 BND (O) = {王治,马丽}
集合O 的上逼近为 I 3 (O) = PO S (O) + BND (O) = {刘保,赵凯,王治,马丽}
根据表1,可以归纳出下面几条规则,揭示了教育程度与是否能找到好工作之间的关系.
RULE 1: IF (教育程度= 大学) OR (教育程度= 博士) THEN (可以找到好工作)
RULE 2: IF (教育程度= 小学) THEN (找不到好工作)
RULE 3: IF (教育程度= 高中) THEN (可能找到好工作)
从这个简单的例子中,我们还可以体会到粗糙集理论在数据分析,寻找规律方面的作用.
(1) 它能处理各种数据,包括不完整(incomplete) 的数据以及拥有众多变量的数据;
(2) 它能处理数据的不精确性和模棱两可(ambiguity),包括确定性和非确定性的情况;
(3) 它能求得知识的最小表达(reduct) 和知识的各种不同颗粒(granularity) 层次;
(4) 它能从数据中揭示出概念简单,易于操作的模式(pattern) ;
(5) 它能产生精确而又易于检查和证实的规则,特别适于智能控制中规则的自动生成。
1.不确定或不精确知识的表达;
2.经验学习并从经验中获取知识;
3.不一致信息的分析;
4.根据不确定,不完整的知识进行推理;
5.在保留信息的前提下进行数据化简;
6.识别并评估数据之间的依赖关系。
神经网络样本化简
人工神经网络具有并行处理,高度容错和泛化能力强的特点,适合应用在预测,复杂对象建模和控制等场合. 但是当神经网络规模较大,样本较多时,训练时间过于漫长,这个固有缺点是制约神经网络进一步实用化的一个主要因素. 虽然各种提高训练速度的算法不断出现,问题远未彻底解决。化简训练样本集,消除冗余数据是另一条提高训练速度的途径。
控制算法获取
实际系统中有很多复杂对象难于建立严格的数学模型,这样传统的基于数学模型的控制方法就难以奏效. 模糊控制模拟人的模糊推理和决策过程,将操作人员的控制经验总结为一系列语言控制规则,具有鲁棒性和简单性的特点,在工业控制等领域发展较快. 但是有些复杂对象的控制规则难以人工提取,这样就在一定程度上限制了模糊控制的应用.
粗糙集能够自动抽取控制规则的特点为解决这一难题提供了新的手段. 一种新的控制策略—模糊- 粗糙控制(fuzzy-rough control) 正悄然兴起,成为一个有吸引力的发展方向. 有学者应用这种控制方法研究了"小车—倒立摆系统"这一经典控制问题和水泥窑炉的过程控制问题,均取得了较好的控制效果. 应用粗糙集进行控制的基本思路是: 把控制过程的一些有代表性的状态以及操作人员在这些状态下所采取的控制策略都记录下来,然后利用粗糙集理论处理这些数据,分析操作人员在何种条件下采取何种控制策略,总结出一系列控制规则:
规则1 IF Condit ion 1 满足 THEN 采取decision 1
规则2 IF Condit ion 2 满足 THEN 采取decision 2
规则3 IF Condit ion 3 满足 THEN 采取decision 3
这种根据观测数据获得控制策略的方法通常被称为从范例中学习(learning from examples). 粗糙控制(rough control) 与模糊控制都是基于知识,基于规则的控制,但粗糙控制更加简单迅速,实现容易(因为粗糙控制有时可省却模糊化及去模糊化步骤);另一个优点在于控制算法可以完全来自数据本身,所以从软件工程的角度看,其决策和推理过程与模糊(或神经网络) 控制相比可以很容易被检验和证实(validate). 有研究指出在特别要求控制器结构与算法简单的场合,更适合采取粗糙控制。
决策支持系统
面对大量的信息以及各种不确定因素,要作出科学,合理的决策是非常困难的.决策支持系统是一组协助制定决策的工具,其重要特征就是能够执行IF THEN 规则进行判断分析. 粗糙集理论可以在分析以往大量经验数据的基础上找到这些规则,基于粗糙集的决策支持系统在这方面弥补了常规决策方法的不足,允许决策对象中存在一些不太明确,不太完整的属性,并经过推理得出基本上肯定的结论。
下面举一个例子,说明粗糙集理论可以根据以往的病例归纳出诊断规则,帮助医生作出判断。下表描述了八个病人的症状. 从下表中可以归纳出以下几条确定的规则:
病人编号 | 病理症状诊断结果 | ||
是否头痛 | 体温 | 是否感冒 | |
病人1 | 是 | 正常 | 否 |
病人2 | 是 | 高 | 是 |
病人3 | 是 | 很高 | 是 |
病人4 | 否 | 正常 | 否 |
病人5 | 否 | 高 | 否 |
病人6 | 否 | 很高 | 是 |
病人7 | 否 | 高 | 是 |
病人8 | 否 | 很高 | 否 |
1. IF (体温正常) THEN (没感冒)
⒉ IF (头痛) AND (体温高) THEN (感冒)
⒊ IF (头痛) AND (体温很高) THEN (感冒)
还有几条可能的规则:
⒋ IF (头不痛) THEN (可能没感冒)
⒌ IF (体温高) THEN (可能感冒了)
⒍ IF (体温很高) THEN (可能感冒了)
病人5 和病人7,病人6 和病人8,症状相同,但是一个感冒另一个却没感冒,这种情况称为不一致(inconsistent). 粗糙集就是靠这种IF THEN 规则的形式表示数据中蕴含的知识.
希腊工业发展银行ETEVA 用粗糙集理论协助制订信贷政策,从大量实例中抽取出的规则条理清晰,得到了金融专家的好评.
从数据库中知识发现
现代社会中,随着信息产业的迅速发展,大量来自金融,医疗,科研等不同领域的信息被存储在数据库中. 这些浩如烟海的数据间隐含着许多有价值的但鲜为人知的相关性,例如股票的价格和一些经济指数有什么关系; 手术前病人的病理指标可能与手术是否成功存在某种联系; 满足何种条件的夜空会出现彗星等天文现象等等. 由于数据库的庞大,人工处理这些数据几乎是不可能的,于是出现了一个新的研究方向—数据库中的知识发现(Knowledge Discovery in Databases,KDD),也叫做数据库(信息) 发掘(Mining),它是目前国际上人工智能领域中研究较为活跃的分支.粗糙集是其中的一种重要的研究方法,它采用的信息表与关系数据库中的关系数据模型很相似,这样就便于将基于粗糙集的算法嵌入数据库管理系统中. 粗糙集引入核(core),化简(reduct) 等有力的概念与方法,从数据中导出用IF THEN 规则形式描述的知识,这些精练的知识更便于存储和使用。
相关会议
相继召开的以粗糙集理论为主题的国际会议,促进了粗糙集理论的推广. 这些会议发表了大量的具有一定学术和应用价值的论文,方便了学术交流,推动了粗糙集在各个科学领域的拓展和应用. 下面列出了近年召开的一些会议:
1992 年第一届国际研讨会(Rough Set s: State of the A rt and Perspect ives) 在波兰Kiekrz 召开;
1993 年第二届国际研讨会(The Second In ternat ionalWo rk shop on Rough Set s and Know ledge D iscovery,RSKD'93)在加拿大Banff 召开;
1994 年第三届国际研讨会(The Th ird In ternat ionalWo rk shop on Rough Set s and Soft Computing,RSSC'94)在美国San Jose 召开;
1995 年在美国North Carolina 召开了题为"Rough Set Theory,RST'95"的国际会议;
1996 年第四届国际研讨会(The Fourth International Work shop on Rough Sets,Fuzzy Sets,and Machine Discovery,RSFD'96)在日本东京召开;
1997 年3 月在美国North Carolina 召开了第五届国际研讨会(The Fifth International Work shop on Rough Sets and Soft Computing,RSSC'97)。
相关软件
目前,国际上研究粗糙集的机构和个人开发了一些应用粗糙集的实用化软件,也出现了商业化的软件.
加拿大Reduct System Inc. 公司开发的用于数据库知识发现的软件DataLogic R 是用C 语言开发的,可安装在个人计算机上,为科研领域和工业界服务.
美国肯萨斯大学开发了一套基于粗糙集的经验学习系统,名为LERS (L earning from Examples based on Rough Sets),它能从大量经验数据中抽取出规则. LERS 已被美国国家航空航天管理局(NASA) 的约翰逊(John son) 空间中心采用,作为专家系统开发工具,为"自由号"(F reedom) 空间站上的医疗决策服务. 美国环境保护署(US Environmental Protection Agency) 资助的一个项目中也采用了LERS.
波兰波兹南工业大学(Poznan University of Technology) 开发的软件RoughDAS 和加拿大Regina 大学开发的KDD-R 是用C 编写的,在UNⅨ 环境下运行,KDD-R 基于变精度粗糙集模型 (Variable Precision Rough Set,VPRS),通过改变粗糙程度而使数据中隐含的模式更清楚的显示出来.
1、本站所有文本、信息、视频文件等,仅代表本站观点或作者本人观点,请网友谨慎参考使用。
2、本站信息均为作者提供和网友推荐收集整理而来,仅供学习和研究使用。
3、对任何由于使用本站内容而引起的诉讼、纠纷,本站不承担任何责任。
4、如有侵犯你版权的,请来信(邮箱:baike52199@gmail.com)指出,核实后,本站将立即删除。
下一篇 事业单位
上一篇 青岛科技大学信息科学技术学院