（计算机软件与理论专业论文）基于粗糙集的规则获取方法的研究.pdf

摘要 摘要 姐糙集理论是一秘研究不完整、不确定知识和数据的表达、学习、归 纳的理论方法，近年来在理论较型、算法研究、_ ：1 一程应用中取得了好的成 果和应用。基于粗糙集理论的知识获取是粗糙集理论研究的核心问题，也 是糨糙集从理论到应1 目j 的一个关键过程，而增量式规则获敬耱不完备信息 系统的规则获取则是这一问题中的难点。 本文蓄先分析比较了基于翔糙集理论的各种属性约麓的算法，在引入 信息向量表示信息系统中的对象后，提出了求粗糙集理论中等价类、不可 分辨关系、上f 近似集、届性约简、楣对正域、相对属性约簏的算法，用 简单易懂的方法系统地表示，粗糙集理论巾的若干基本概念。 同时本文针对增量式规则获取算法中当新数据加入时分类不完备，不 严密的问题，结合信怠向量的表示方法，提出了”种基于粗糙集理论舱增 量式规则获取算法。当新数据加入时，提出把新数据按条件向量和决策向 量与原始条件向量集和决黄向量集的关蓉分为4 大类，6 ，l 、类，每一类用不 同的方法更新规则集及其参数，从而实现增量式规则获取。 最后本文还分析比较了现有不完备信息系统的规则获取算法的问题和 不足，提出了种基i j _ 粗糙集瑚论的不先备信息系统的靓则凝取算法，其 基本原理是：遵循数据一致化和简约化的原理，对不完备信息表中的部分 数据进行弥补，从阳删除冗余数据和冲突数据，然后对直接提取自“屣规姗 方法的不规范处进行修订，用修订后的方法提取扩展规则，用可信度酌概 念瘦壤不确定褫尉的正确性，强只傈霪可信度满足要求的规则，以保证提 取规则的正确性利实用性。 关键词粗糙集：规则获取；属性约简；增罱式学习；不完备信息系统 燕山大学工学硕士学位论文 a b s t r a c t r o u g h s e tt h e o r yi sas e to fm e t h o d st os t u d yt h ee x p r e s s i o n ，t h el e a r n i n g ， t h ei n d u c t i o no f i n c o m p l e t ed a t aa n dv a g u ek n o w l e d g e t h e r ea r em a n yg o o d a p p l i c a t i o n s i n t h e o r ym o d e l ，a l g o r i t h mr e s e a r c ha n de n g i n e e r i n gb a s e do n r o u g h s e tt h e o r y k n o w l e d g ea c q u i s h i o ni st h em a i np r o b l e mo f t h er e s e a r c ho f r o u g h s e tt h e o r ya n dt h ek e y p r o c e s st oa p p l yr o u g hs e tt h e o r yi n t oe n g i n e e r i n g i n c r e m e n t a lr u l ea c q u i s i t i o na n dr u l ea c q u i s i t i o nf r o mi n c o m p l e t ei n f c ) r m a t i o n s y s t e ma r et w od i f f i c u l tp o i n t s f i r s t ，a l g o r i t h m so fa t t r i b u t er e d u c t i o n a l - e a n a l y z e di n t h e p a p e r t h e n o b j e c t so f i n f o r m a t i o ns y s t e ma r ed e n o t e d b yi n f o r m a t i o nv e c t o ra n da l g o r i t h m s o fc l a s s e s o f e q u i v a l e n c er e l a t i o n s ，i n d i s c e r n a b i l i t yr e l a t i o n s ，t h eu p p e r a p p r o x i m a t i o n ，t h el o w e ra p p r o x i m a t i o na n da t t r i b u t er e d u c t i o na r eg i v e ni nt h i s p a p e r s e c o n d ，a c c o r d i n g t ot h ew e a k n e s so fi n c r e m e n t a lr u l e a c q u i s i t i o n a l g o r i t h m s ，u s i n gi n f o r m a t i o nv e c t o r , a na l g o r i t h mo fr u l ea c q u i s i t i o nb a s e do n r o u g hs e tt h e o r yi sg i v e n w h e nn e wd a t ai sa d d e di n , i ti sc l a s s i f i e di n t of o u r b i gc l a s s e s a n ds i xs m a l lc l a s s e sr u l es e ta n di t s p a r a m e t e r sa r eu p d a t e d a c c o r d i n g t ot h ec l a s s i f i c a t i o n ， f i n a l l y , a f t e rf i n d i n go u tt h ew e a k n e s so fa l g o r i t h m so fr u l ea c q u i s i t i o n f r o mi n c o m p l e t ei n f o r m a t i o ns y s t e m ，a n a l g o r i t h mi sg i v e ni nt h i sp a p e r i t s m a i ni d e ai st h a ta s s u m p t i o n sa r em a d eo nt h eu n k n o w nv a l u e ss ot h a ti ti sg o o d f o rt h ee l i m i n a t i o no fr e d u n d a n t d a t aa n d c o n f l i c t i n g d a t a ，t h em o d i f i e d e x t e n s i v er u l e a c q u i s i t i o na l g o r i t h mg e n e r a t e s t h ee x t e n s i v er u l e sa n d c o n f i d e n c ef a c t o ri su s e dt om e a s u r et h ev a l i d i t yo fu n c e r t a i nr u l e si no r d e rt o e n s u r et h ev a l i d i t ya n dp r a c t i b i l i t yo ft h er u l e s e t ，o n l yh i g h l yb e l i e v a b l er u l e s a r e k e p t ， k e yw o r d sr o u g hs e t ，r u l e a c q u i s i t i o n , a t t r i b u t er e d u c t i o n ，i n c r e m e n t a l l e a r n i n g ，i n c o m p l e t ei n f o r m a t i o ns y s t e m 第l 章绪论 1 1引言 第1 章绪论 关于知识的理论研究非常丰富，其历史也非常悠久。目前，研究者们正 在广泛而深入地研究知识的各个方面。在有关如何理解、表达和处理知识 方面，已经形成了各种各样的观点和方法。直观地，知识可以被认为是与 现实中的一部分有关的信息的集合，而这里所说的现实中的一部分就组成 了人们所感兴趣的领域。可是，这个定义不精确且有多义性。 知识产生于对现实中的认知对象的分类能力。这里，认知对象指任何 我们可以想象得到的东西，例如：实际物体、客观事物、抽象概念、状态、 过程、时刻等。知识是与现实或抽象世界的特定部分有关的不同分类模式 联系在一起，而这里把现实或抽象世界的特定部分称之为论域( u n i v e r s e ) 。 知识是由我们感兴趣的领域中的分类模式组成。 粗糙集( r o u g ns e t ，r s ) 理论是一种刻划不完整性和不确定性的数学工 具，能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并 从中发现隐含的知识，揭示潜在的规律。r s 理论是由波兰学者p a w l a kz 在】9 8 2 年【2 】提出的。1 9 9 1 年p a w l a kz 出版了专著，系统全面地阐述了r s 理论，奠定了严密的数学基础。该书与在1 9 9 2 年出版的r s 理论应用专集 较好地总结了这一时期r s 理论与实践的研究成果，促进了它的进一步发 展，现已成为学习和应用r s 理论的重要文献。从1 9 9 2 年至今，每年都召 开以r s 为主题的国际会议，推动了r s 理论的拓展和应用。国际上成立了 粗糙集学术研究会，参加的成员来自波兰、美国、加拿大、日本、挪威、 俄罗斯、乌克兰和印度等国家。目前r s 理论已成为人工智能领域中一个较 新的学术热点，引起了越来越多的科研人员的关注。 1 ，2 课题研究的现状和发展趋势 r s 理论的生命力在于它具有较强的实用性，从诞生到现在虽然只有十 燕山大学工学硕士学位论文 几年的时间，但已经在许多领域取得了令人鼓舞的成果。 ( 1 ) 股票数据分析。文献【3 应用r s 方法分析了十年问股票的历史数据， 研究了股票价格与经济指数之间的依赖关系，获得的预测规则得到了华尔 街证券交易专家的认可。 ( 2 ) 模式识别。文献 4 应用r s 方法研究了手写字符识别问题，提取出 了特征属性。 ( 3 ) 地震预报。文献 5 研究了地震前的地质和气象数据与里氏地震级别 的依赖关系。 ( 4 ) 冲突分析。文献6 应用r s 方法建立了反映以色列、巴勒斯垣、约 旦、埃及、叙利亚和沙特阿拉伯等六国关于中东和平问题各自立场的谈判 模型。 ( 5 ) 从数据库中知识发现( k n o w l e d g ed i s c o v e r y i nt h ed a t a b a s e ，k d d ) 7 ，8 】。 k d d 又称数据发掘( d a t am i n i n g ) ，是当前人工智能和数据库技术交叉学科的 研究热点之。r s 方法现已成为k d d 的一种重要方法，其导出的知识精 练且更便于存储和使用。 ( 6 ) 粗糙控s o ( r o u g hc o n t r 0 1 ) 9 - 1 4 。r s 根据观测数据获得控制策略的方 法被称为从范例中学习f l e a r n i n gf r o me x a m p l e s ) ，属于智能控制的范畴。基 本步骤是：把控制过程中的一些有代表性的状态以及操作人员在这些状态 下所采取的控制策略都记录下来，形成决策表，然后对其分析化简，总结 出控制规贝j 1 1 9 1 。形式为：i fc o n d i t i o n ：；n 满足t h e n 采取d e c i s i o n = m 。r s 方法是一类符号化分析方法，需要将连续的控制变量离散化，为此p a w l a kz 提出了粗糙函数( r o u g hf u n c t i o n ) 的概念( 1 0 ，为粗糙控制打下了理论基础。 文献 1 1 ，1 2 应用粗糙控制研究了“小车倒立摆系统”这一经典控制问题， 取得r 较好的结果。在过程控制领域，文献 1 3 应用r s 方法成功地提取出 了水泥窑炉的控制规则。粗糙控制的优点是简单迅速、实现容易，不需要 象f u z z y 控制那样进行模橱化和去模猢化。因此在特别要求控制器结构与 算法简单的场合，采取粗糙控制较为合适。另外，由于控制算法完全来自 观测数据本身，其决策和推理过程可以很容易被检验和证实。一一种新的有 吸引力的控制策略“模糊一粗糙控肯r l ( f u z z y - r o u g hc o n t r 0 1 ) ”正悄然兴起，其 第1 章绪论 主要思路是利用r s 获取模糊控制规则。 ( 7 1 医疗诊断。r s 方法根据以往的病例归纳出诊断规则，用来指导新的 病例。现有的人工预测早产的准确率只有1 7 3 8 ，应用粗糙集理论则 可提高到6 8 9 0 。 ( 8 ) 专家系统( e s ) 。r s 抽取规则的特点，为构造e s 知识库提供了一条 崭新的途径。 ( 9 ) 人二神经元网络( a n n ) 。训练时间过于漫长的固有缺点是制约a n n 实用化的冈索之一。文献【1 6 】应用r s 化简神经网络训练样本数据集，在保 留重要信息的前提下消除了多余的数据，使训练速度提高了47 7 倍，获得 了较好的效果。文献 1 7 ，1 8 】将r s 与a n n 结合起来，充分利用r s 处理不 确定性的特长以增强a n n 的信息处理能力。 ( 1 0 ) 决策分析”划】。r s 的决策规则是在分析以往经验数据的基础上得 到的。r s 允许决策对象中存在一些不太明确、不太完整的属性，弥补了常 规决策方法的不足。希腊工业发展银行e t e v a 应用r s 理论协助制订信贷 政策，是r s 多准测决策方法的一个成功范例。 r s 理论的应用领域还包括；近似推理 2 2 , 2 3 1 、软件工程数据分析【2 4 1 、图 象处理f ”1 、材料科学中的晶体结构分析2 6 i 、预测建模1 2 7 , 2 8 、结构建模”1 、 投票分析”1 、电力系统【3 ”3 1 等。r s 在我国的研究刚刚起步，有关文献还不 多d 4 3 5 1 。 在肯定r s t 在人工智能和认知科学取得成就的同时，j , w g u a n 等人系 统而全面地阐述了信息系统上基于r s t 的r o u 【g h 计算方法和r o u g h 分析， 并给出了主要包括计算核属性、给出一( 多) 个属性的等价分类算法、讨论函 数依赖( f u n c t i o n a ld e p e n d e n c y ) 等近2 0 个算法，最后指出某些在知识表达过 程中对于人数据集的处理和分析的问题是n p 难度的，还迸一步给出改进和 优化的算法。文中系统化的阐述，透彻的算法分析和清晰的实例说明令初 学者信心倍增、受益非浅，也是其成为r s t 领域的研究者不可多得的学习 和参考资料。 众所周知，一种理论工具的发展，离不开其坚实数学基础。r s t 也是 如此，由于已有的粗集公理在表示形式、极小化以及可靠性证明中，尚未 燕山大学工学硕士学位论文 完善，在已有若干组粗集公理上研究了粗集公理组的极小化，孙辉等人得 到了更为精练的两组粗集公理，证明了它们的可靠性，并且定义了极小粗 集公理组概念，还证明了所给出的两组粗集公理是极小的 3 6 1 。文献【3 6 是对 粗集理论化和公式化的研究，为本课题中的研究提供了更为可靠的保障， 同时为r s t 的迸一步发展打下了牢固的理论基础。 在课题的凋研过程中得到的很多有价值的文献资料，更好地解决理论 和实际的问题，它们将r s t 与其它理论或技术相融合，为本课题提供了很 好的典范，启发了作者的研究思路。其中有的文献将r s t 与v a g u e 相结合， 提出了基于概率测度的粗糙集模型，定义了概率近似空问上的上下近似， 给出概率粗糙近似算子，讨论了其上的近似操作的性质，并且给出此类模 型的近似精度、属性依赖性和约筒等粗集理论中一些重要概念，最后将概 率粗糙近似算子与p a w l a k 近似算子进行了比较【3 1 1 。文中提出的模型是经典 粗糙集模型的推广，其应用相当广泛。有的文献在叙述有关粗糙集的基本 概念基础上，重点介绍用模糊测度来度量粗糙质量的基本方法【3 引，该研究 对本课题的选择提供了思路，具有一定的参考价值。易树鸿等人提出r 一 种基于粗集的文本数据特征信息的挖掘方法【3 9 l ，为知识工程研究和i n t e r n e t 内容检索提供j ，有效的方法，启发了作者的思路。 b t h e r e s a 等人提出了粗糙关系数据库模型( r r d m ) ，并对它进行了定 义，对粗糙( r o u g h ) 关系操作，包括并、差、选择、投影、连接，及相关性 质进行了研究f 4 。s u i ，y f 等人对r r d b 的r o u g h 关系的上下近似给出了几 种定义，并对熵规则进行了分析f 4 ”，t y l i n 则研究了粗糙集与数据库的关 系i 4 “。从目前k e , d m ( 和r r d 8 ) 的研究来看，大多还停留在起步和理论阶 段，而进一步深入研究则比较少在此基础上，作者又参考了r o u g h 关系 数据库模型及其关系操作 4 3 1 和基于粗糙关系数据库的粗糙数据查询( 4 4 1 等相 关研究内容，由此确定课题的研究方向和内容，即基于r s t 理论事务处理 方法的研究，对r r d m 领域进行深入的探讨，如解决r r d m 中属性值的 语义等价问题等，并将这一研究成果应用到课题其它的部分中。 目前，知识获取方法大多是基于机器学习，模式识别以及统计学等的。 例如，决策树方法( 如i d 3 和c 4 5 ) ，主要是对数据库中的某类数据寻找出 4 第l 章绪论 关于该类数据的描述和模型。非线形同归分析与分类方法是利用回归分析 的方法产生一个将数据项映射到个实值预测变量的函数，发现变量或属 性间的依赖关系。聚类分析方法根据识别出的一组聚类规则，将数据分成 若干类，其主要采用可能性稠密度估计法。依赖关系学习模型法是要构造 一一个描述变量之间函数依赖关系或相关关系的模型，例如信念网络。变化 和偏差分析方法，偏差包括很大类潜在有用的知识，如分类中的异常实 例，模式例外，观察结果对期望的偏离以及量值随时间的变化等等，该方 法的基本思想是寻找观察结果与参照量之间有意义的差别。观察可以是一 组变量值的某个模式，参照可以是给定模型的预测，外界提供的标准量或 另一个观察。f a y y a d 等对数据库知识获取作了如下定义；知识获取是识别 出存在于数据库中有效的，新颖的，具有潜在效用的乃至最终可理解的模 式的非平凡过程。 近几年在粗糙集理论研究中对求解属性的最小约简和较小约简以及求 取最简规则集的算法己经进行了些研究，但这些研究都是针对静态数据 的。而数据库是动态的，因此许多研究者建议，数据库知识发现算法应该 是增量式的。属性最小约简的增量式算法以及增量式更新概念格的算法已 经开始被研究，但对于增量式知识获取算法的研究工作还比较少。在以： 工作的基础上，研究了增量式知识获取问题。 当粗糙集理论应用于数据挖掘或在线学习时，其增量式学习能力显得 非常重要。这主要有两个原因：首先，在实际应用中数据量往往是逐渐增 加的；其次，对一个训练好的系统进行修改的时间代价通常低于重新训练 一个包含新增数据的系统所花的代价，系统每增加一个新的数据就进行一 次规则集的重新计算显然会浪费更多的时间和空间资源。 增量式获取知识的主要目标是在动态环境中保持知识库。般的，对粗 糙集方法来说，就是指当新对象加入决策表时，以增量式的方式接受新对 象，更改现存的规则或约简，而不是对整个决策表重新计算得出。在增量 式学习算法研究方面，有许多学者已经做了不少研究工作。但是，大多数 已有的增量式推理学习系统存在以下两个问题：这些系统性能并不优r 普 通的非增量式的学习系统，比如：a q l 5 ，c 4 5 和c n 2 等：这些增量式的 燕山大学工学硕士学位论文 学习系统主要是推导确定性的规则，而对于非确定性规则缺乏有效的处理。 为此，本文提出一种新的基于粗糙集的增量式规则学习的算法，同时给出 了非确定性规则的置信度定义，这样在一定程度上提高了算法的实用性。 在数据挖掘研究中，最主要的研究是规则提取。基于完备信息系统 ( c o m p l e t e i n f o r m a t i o ns y s t e m ，简记为c i s1 的规则提取方法已很成熟，而基 于不完备信息系统( i n c o m p l e t ei n f o r m a t i o ns y s t e m ，简记为s ) 的规则提取 方法是目前国际上研究的热点。有关n i s 规则提取的文献目前国内还没有， 国际上也很少。作为处理不确定知识的优秀工具，粗集理论是研究n i s 的 主要方法。到2 0 世纪9 0 年代初，n i s 的规则提取理论还很不成熟，比如： 按照相似性度量方法把不完备信息转化为完备信息，然后进行规则提取的 方法；把不完备信息系统中的不完备信息从系统中删除，转变为完备信息 系统再提取规则的方法。 目前，从不完备信息系统中提取规则主要有三种方法：预测缺失值的 同时提取规则”i ；先扩展再提取确定规则的方法【4 6 4 v ；直接提取扩展规则 的方法1 4 7 i 。文献 4 5 】给出了规则提取算法一u e d r 算法。该方法的优点在于 它可以在预测表中缺失数据的同时提取确定规则，把不完备表转换成完备 表。其中，数据预测所遵循的原理是数据一致化和屏蔽数据冲突。即在数 据预测过程中，运用粗集理论的近似集原理，最大限度地使预测值满足信 息表一致化的要求。然而，u e d r 算法实用性较差，对于大型数据库的海 量数据，该方法并不能预测出所有的缺失信息。第二种方法先对不完全信 息表进行扩展，然后提取规则。该方法可以提取到满足不完备信息表的确 定规则的最大集合，但是和u e d r 算法一样并不可行。现实世界中数据量 巨大，该方法的效率很低，时间复杂度呈指数级增长。文献 4 7 在文献 4 6 的基础上做了进一步的工作，该方法的规则提取效率很高，但是提取的规 则中包含不确定规则。对于不确定规则的正确性度量，文献 4 7 】没有给出解 决办法。 本文提出的方法是预测缺失数据同时提取规则和直接提取扩展规则两 种方法的折中，弥补了前者不能预测大量缺失数据导致规则无法提取的缺 陷，同时对按照直接提取扩展规则方法提取的不确定规则给出了正确性度 第l 章绪论 量方法。实际应用中，只对正确性较高的不确定规则感兴趣，因此，本文 的方法只提取正确性满足应用需求的不确定规则。 1 3 本文主要研究内容 本文研究的内容是基于粗糙集理论的知识获取，侧重点在基于粗糙集 理论的增量式的知识获取和基于粗糙集理论的不完备系统的知识获取上。 本论文主要框架和结构如下： 第一章对与学位论文有关的重要文献资料进行了综述，分析讨论1 厂前 人及他人的研究成果、水平和知识空白，存在的主要问题以及急待解决和 完善的问题。 第二章是全文基础，介绍了经典的集合理论和由之发展而来的粗糙集 理论。 第三章介绍了知识获取的概念并阐述了如何利用粗糙集理论来进行知 识获取，接着还介绍r 用粗糙集理论进行知识获取的核心问题及有关算法。 第四章介绍利用粗糙集理论来进：，厅增量式的规则获取和相关算法并给 出了实例验证。 第五章介绍利用粗糙集理论对不完备信息系统进行规则获取并给出了 有关算法和实例验证。 最后总结全文，阐述了课题研究的结论，并给出了今后本课题主要研 究的内容和方向。 7 壅生查耋三兰至圭兰丝堕苎 第2 章粗糙集及其相关理论 21 引言 粗糙集理论是p a w l a k 等提出的研究小完整数据耳口不精确知识的表达、 学习，归纳的一种数学方法，特点是不需要预先给定某些特征或属性的数 量描述，如统计学中的概率分布、模糊集理论中的隶属度或隶属函数等， 而是直接从给定问题的描述集合出友，通过不可分辨关系和不可分辨类来 确定给定问题的近似域，从而拽出该问题中的内在规律。 近年米，粗糙集理论和应用的研究取得了很快发展，其涉及的钡域很 广，包括模式识别、机器学习、决策分析和决策支持、知识获取、知识发 现等。粗糙集理沦同模糊集、神经网络、证据理论一起，称为不确定性计 算的个重要分支。 经典集合理论是粗糙集理论的基础，故本章在介绍粗糙集理论之前将 简要回顾经典集合理论。 2 2 经典集合理论 2 21 集合论的基本概念及运算 集合l 删是现代数学和逻辑学的基本概念之一。本世纪以来，关于集合 的理论一集合论，对现代数学和逻辑学的发展产生了巨大影响，今天它已 成为数学和逻辑学的一种基础理论。 2 2 1 1集合论的基本概念崩集舍论的创始入康托尔增笄解释避的话来 说；所谓集合，可以理解为由人的知觉或思维确定的、能明确区分开的对 象m 聚集成的个整体m ，返些对象帆叫做m 的“元素”。 一般地说，集合是一个不加精确定义的基本概念。把具有某种属陛的 ”一些对暮汇集成一个整体，就形成了个集合，包含在该集合中的对象称 作该集合中的元素”。 第2 章粗糙集及其相关理论 2 21 2 集合代数运算正如数学中两数之间可以进行加、减、乘、除等运 算一样，两集合之间也有类似的运算【4 ”。 定义21 ：设a 和b 是集合，则 ( 1 1 a 和b 的并是集合，记为a u b ，且a u b = 扣i x a v x b j ； ( 2 ) a 和b 的交是集合，记为a n b ，且a n b = 扛i z a a y b ) ； ( 3 ) a 和b 的差是集合，记为a b ，且爿一b = x l r a a x 仨毋a 定义2 2 ：设a 和b 是集合，如果4 n b = o ，那么称a 和b 是不相交 的。 集合的代数运算满足如下定律： ( 1 ) 幂等律 f 2 ) 交换律 ( 3 ) 结合律 ( 4 ) 分配律 ( 5 ) 恒等律： a u a = a 。a n a = l ： 爿u b = b u a ，a n b = b n a ； ( a u b ) u c = a u ( b u c ) ，( a n b ) n c = a n ( b n c ) ； a u ( b f i c ) = ( a u b ) n ( a u c ) ， 4 n ( b u c ) = ( 爿a b ) u ( 一n c ) ； a u a = a ，a n q = a ； 4 u q = q ，a n o = ( 弓； ( 6 ) 互补律：4 u j = q ，a n a = g ； ( 7 ) 德么根律：a u b = a n b ，a n b = a u b ( 8 ) 吸收律：a u ( a n b ) = a ，a n ( a u b ) = a ( 9 ) 双否律：a = a 。 2 2 2等价关系及等价类 在集合理论和关系概念的基础上，才能给出等价关系的定义。等价关 系是所有被讨论的关系中f 如相容关系、序关系等) 最重要的一种。由等价关 系所确定的等价类，是对论域的精确：划分，同时也被认为足人工智能的基 础。 2 2 2 1关系这里简要给出以下相关定义删： 定义2 3 ：a x b 的子集叫做a 到b 的一个二元关系；4 4 4 的了 集叫做4 a 4 上的一个三元：关系：4 4 4 的子集叫做 燕山大学工学硕士学位论文 a a a 。上的一个n 元关系；a 4 的子集叫做a 上的r l 元关系。 因为关系足由n 元序偶( 一般为2 元序偶) 构成的，序偶不仅能够表达集 合a 中客体( 元素) 之间的任意关系，还可以被看作单个的元素进行处理， 因此，从本质上讲，关系也是一个集合。 定义2 4 ：设r 是_ ) ( 4 的子集，如果r = o ，则称r 是空关系；如果 r = 4 ，则称r 为全关系。 定义25 ：设r 是a 上的二元关系，定义 ( 1 ) 如果对a 中每一个元素z 都有地，则称r 是自反的。 ( 2 ) 如果对a 中每一个元素x ，y 都有x r y 蕴n y r x ，则称r 是对称的。 ( 3 ) 如果对a 中每一个元素z ，y ，z ，x r y 1 y r z 蕴涵着x r z ，则称r 是传递的。 2 22 2 等价关系及等价类这里简要给出以下相关定义【4 ”。 定义2 6 ：设r 是集合a 到a 的二元关系，如果对v a a 有( 口，口) r ， 则称r 是a 上的自反关系。 定义2 7 ：设r 是集合a 上的二元关系，如果对v a ，b a ，有( ，6 ) r ， 也必有( b ，口) r ，则称r 是a 上的剐称关系。 定义28 ：设r 是集合a 上的二元关系，对v a ，b ，c a ，如果无论什么 时候有( d ，b ) r 和( 6 ，c ) r ，必有( a ，c ) r ，则称r 是a 上的传递关系。 定义2 9 ：设r 是集合j ：的二元关系，如果它是自反、对称和传递的， 则它是a 上的等价关系。 定义21 0 ：设r 为集合a 上等价关系，对口a ，集合 陋k = f x i z a ，0 t r x ) 称为元素口形成的r 等价类。 定理2l ：设r 是集合a 上的等价关系，m 。m ，是a 中所有等价 类，于是a = m ，u m ：u ，并且m n m ，= o ，j j 。亦即，集合a 上的等 价关系把a 分成了互不相交的等价类。 定理2 2 ：设r 是集合s 的一个等价关系，那么r 的等价类形成s 的一 个划分。因此，给定集合s 的一个划分 4 】，) ，存在一个等价关系r 使 第2 章粗糙集及其相关理论 得每个丘，i ，作为它的等价类。 2 3 粗糙集的基本理论 2 3 1 知识与知识库 假定给定对象全域u ( 非空) ，x c u 称为u 上的一个概念。概念的族集 就是ui 二的知识。u 上分类的族集( 即等价关系的族集) 称为u 上的一。个知 识库，记u p - 为u 上等价关系r 的所有等价类( 或者u 上的分类) 构成的集 合，【x 。为等价关系r 上x 的等价类集合，并且不加区分地使用等价关系 和分类( 划分) 的概念。 定义21 1 ：一个知识库是一个关系系统k = ( u ，f ) ，其中u o 为有限集 合，称为全域，f 是u 上的等价关系族。 若p c f ，且p o ，则np ( p 中所有等价关系的交集) 也是一个等价关 系，称为p 上的不可区分( i n d i s c e r n i b i l i t y ) 关系，记为i n d ( p ) ，且有 叫。= = n r k 这样，u i n d p ) ( 即等价关系i n d ( p ) 的所有等价类) 表示与等价关系族p 相关 的知识，称为k 中关于u 的p 基本知识( p 基本集) 。为简单起见，用u p 代替u i n d ( p ) ，i n d ( p ) 的等价类称为知识p 的基本概念或基本范畴。特别地， 如果q f ，则称q 为k 中关于u 的q 初等知识，q 的等价类为知识f 的 q 初等概念或q 初等范畴。 2 3 2 近似与粗糙集 令x u ，r 为u 上的一个等价关系。当x 能表达成某些r 基本范畴 的并时，称x 是r 可定义的；否则称x 为r 不可定义的。 r 可定义集是论域的子集，它可在知识库k 中精确地定义，而r 不可 定义集不能在这个知识库中定义。r 可定义集也称作r 精确集，而r 不可 定义集也称为r 非精确集或r 粗糙集( r o u g hs e t ) 。 当存在等价关系r e i n d ( k ) 且x 为r 精确集时，集合x u 称为k 中 燕山大学工学硕士学位论文 的精确集；当对于任何r e i n d ( k ) ，x 都为r 粗糙集，则x 称为k 中的粗 糙集。 对于粗糙集可以近似地定义，在粗糙集理论中使用两个精确集，即粗 糙集的上近似( u p p e ra p p r o x i m a t i o n ) $ 1 下近似( 1 0 w e ra p p r o x i m a t i o n ) 来描述。 定义21 2 ：给定知识库k = 姒f ) ，对于每个子集x c u 和一个等价关系 r e i n d 眯) ，定义两个子集： a p = l 、y _ f f _ r r xu ( yyu r a p t r x = u ( y l y u r ，y n x o 分别称它们为x 的r 下近似集和r 上近似集。 下近似、上近似也可用下面的等式表达： 肇r 。x = u x x u ， x r 董x j a p r x = u x x u ，i x 月n x o 集合6 豫( x ) = 印k ( x ) 一q 妙，( x ) 称为x 的r 边界域；p o & ( x ) = 妒r 。( x ) 称为x 的r 正域；n e g r ( x ) = ua p r 。( x ) 称为x 的负域。 a p g r ( x ) 或p o s a x l 是由那些根据知识r 判断肯定属于x 的u 中元素 组成的集合；a p r 。( ) 是那些根据知识r 判断可能属于x 的u 中元素组成 的集合；6 ( z ) 是那些根据知识r 既不能判断肯定属于x 又不能判断旨定 属于x ( 即u - x ) 的u 中元素组成的集合；n e g r ( x ) 是那些根据知识r 判断 肯定不属于x 的u 中元组组成的集台。 下列性质是显而易见的。 定理2 3 ：x 为r 可定义集当且仅当( 矿。( 鼻) = a p r 。( ) 。x 为r 粗糙 集当且仅当缈。( z ) 玩( x ) 1 。 2 - 3 3 知识约简和核 知识约简是粗糙集理论的核心内容之一。知识库中知识( 属性) 并不是同 等重要的，甚至其中某些知识是冗余的。所谓知识约简，就是在保持知识 库分类能力不变的条件下，删除其中不相关或不重要的知识。 知识约简中有两个基本概念：约简( r e d u c t ) 和核( c o r e ) 。介绍这两个概念 之前，先作如下定义： 1 2 第2 章粗糙集及其相关理论 p 为知识库k = ( u ，f ) 上的一族等价关系，r p ，如果i n d ( p ) = i n d ( p 一 r ) ， 则称r 为p 中不必要的；否则称r 为p 中不重要的。如果每一个r e p 都 为p 中必要的，则称p 为独它的，否则称p 为依赖的。 定义21 3 ：令p 为知识库k = ( u ，i ：) 上的一族等价关系，q _ c p ，如果q 是独立的，且i n d ( q ) = i n d ( p ) ，则称q 为p 的一个约简。显然，p 有多种约 简。p 中所有必要关系组成的集合称为p 的核，记作c o r e ( p ) 。 定理2 4 ：令p 为知识库k = ( u ，f ) 上的一族等价关系为 c o r e ( p ) = nr e d ( p ) 其中r e d ( p ) 表示p 的所有约简1 4 ”。 2 3 4 知识的相对约简和相对核 在应用中，一个分类相对于另一个分类的关系十分重要，因此本节将 介绍知识的相对约简( r e l a t i v er e d u c t ) 和相对核( r e l a t i v ec o r e ) 的概念。 令p 和q 为u 中的等价关系，q 的p 正域记为p o s p ( q ) ，即 p o s p ( q ) = ua p r 。 令p 和q 为等价关系族，r p ，如果 p o s m d ( p ) ( i n d ( q ) ) 2p o s m 邮 r ) ( i n d ( q ) ) 则称r 为p 中q 不必要的；否则r 为p 中q 必要的。 为简单起见，本文也用p o s p ( q ) 代替p o s i 。d ( p ) ( i n d ( q ) ) 。 如果p 中的每个r 都为q 必要的，则称p 为q 独立的( 或p 相对于q 独立1 。 设s g p ，s 为p 的q 约简当且仅当s 是p 的q 独立子族且p o s s ( q ) = p o s p ( q ) 。p 的q 约简简称为相对约简。 p 中所有q 必要的原始关系构成的集合称为p 的q 核，简称为相对核， 记为c o r e q ( p ) 。 定理2 5 ：c o r e q ( p ) = nr e d q ( p 】，其中r e d q ( p ) 是所有p 的q 约简构成的 集合 4 9 1 。 燕山大学工学硕士学位论文 2 3 5 信息系统 定义21 4 ：信息系统是指一个四元组s = f u av 毋，其中u = x l ，k 2 ，x n j 是一个有限的对象集合，a 是个有限的属性集合。v = u 圪，屹是属性a 口a 的值域。信息函数f ：u a a 满足i l x ，a ) e v ，a e a ，x e u 。进一步，a 中 的属性可划分为两个不相交的子集，条件属性集c 和决策属性集d 。a = c u d 。这种特殊的信息系统被称为决策表，记为 u ，c u d ，v ，f ) 。 2 4 粗糙集理论的扩展模型 经典粗糙集理论用于数据分析时，会遇到噪音、数据缺失、大数据量 等一系列问题，而用经典粗糙集理论来处理这些问题往往不够理想。因此， 在近几年的研究中，出现了许多粗糙集的扩展模型。其中典型的有概率粗 糙集模型、模糊粗糙集模型、基于随机集的粗糙集模型、可变精度模型幂u 相似关系模型，也称相容关系模型。本文的工作主要用到相似关系模型和 模糊粗糙集模型，因此本节主要介绍这两种模型。 2 4 1 不完备信息系统 在许多情况下，从现实中获取的数据并不是完整的，其面临的信息系 统也是不完备的，主要问题之一是属性的缺失值。不完备信息系统是对信 息系统的扩展定义，用来描述不完备的信息。 s = ( u a t ) 是信息系统，其中u 是对象的非空集合，a t 是属性的非空有 限集合，对f 每个a a t 有f u v 。，其中v 。称为a 的值域。 每个属性子集a _ c a t 决定了一个不可区分关系i n d ( a ) ： i n d ( a ) = ( x ，y ) l ( x ，y ) u u ，va 气f a ( x ) = ( y ) ) 关系i n d ( a ) ( a c a t ) 构成了u 的划分，用u i n d ( ：a ) 来表示。 对f 一个对象，一些属性值可能是缺失或不确定的，为了表明这种情 况，通常给定一一个区分值( 即空值n u l lv a l u e ) 给这些属性。 如果至少有一个属性a a t 使得v a 含有空值，则称s 为一个不完备倩 息系统，否则它是完备的，用+ 表示空值。 1 4 第2 章粗糙集及其相关理论 2 4 2 相似关系模型 定义2 1 5 ：令s = f u ，a t ) 是不完备信息系统，a c _ a t ，定义相似关系如 卜- ： s i m ( a ) = f ( x ，y ) i ( x ，y ) u u v a a ( x ) = ( y ) o r ( x ) 2 + o r f o ( y ) 2 + 令s a ( x ) 表示对象集 y i y u ，( x ，y ) e is l m ( a ) ) ，对于a 而言，s a ( x ) 是与x 可能不可区分的对象的最大集合。 令d a ( x ) 表示对象集 y | y u ，( x ，y ) 诺s i m ( a ) ) ，对于a 而言，d a ( x ) 是与x 可能可区分的对象的最大集合。 对任意x eu ，s a ( x ) m d a ( x ) = 且s a ( x ) ud “x ) = u 。 令u s i m ( a ) = f s “x ) 忸u ) 表示分类，u s i t ( a ) 中的任何元素称为相容 类。u s i m ( a ) 中的相容类一般不构成u 的划分，但是它们构成u 的覆盖， u u s i m ( a ) = u 。 定义2 1 6 ：s = ( u ，a t ) 为一个不完备信息系统，b c a ，x _ c u ，x 基于 b 的上、下近似为： b s r h x = x lx u ，( z ) n x o 垦w x = x l z u ，品( x ) x ) 与完备信息系统相似，旦。z 是肯定属于x 的对象的集合，而宣。j 足可能属于x 的对象的集合。 2 4 3 模糊粗糙集模型 论域u 上的一个模糊集合( f u z z ys e t ) a 是由u 上的一个隶属函数 a ：u 一， 0 ，1 来表示，其中a ( x ) ( 有时用。( x ) 表示) 表示元素x 隶属于模糊集合a 的程度。 这样，对于论域u 的一个对象x 和u 上的一个模糊集合a ，我们不能 简单地问x 足“绝对”属r 还是不属于a ，而只能问x 在多大程度上属于a 。 隶属度a ( x ) 正是x 属于a 的程度的数量指标。若a ( x ) = o ，则认为x 完全不 属于a 若a ( x ) = i ，刚认为x 完全属于a ；若o a ( x ) 墨a ( x 。) 如果论域u 是无限不可数集合，那么可以表示为： a = f x ，4 ( 芏) 在p a w l a k 粗糙集模型中，论域u 上的任意一个经典集合a 不一定能 用知识库( u ，r