（计算机软件与理论专业论文）基于序关系的rough集模型及知识发现.pdf

基于序关系的r o u g l l 集模型及知识发现 基于序关系的r o u g h 集模型及知识发现 专业：计算机软件与理论 硕士生：蒋贻铨 指导教师：叶小平副教授 摘要 r o t i g l l 集是一种处理含糊和不精确性问题的新型数学 _ 具。其特征是将知识 理解为对论域的划分，将含糊或不精确的知识用已有知识来近似描述刻画。由于 r o u 曲集方法具有突出的数据处理能力，因而被广泛应用于数据挖掘、机器学习、 决策支持与分析、模糊控制等领域，成为软计算的基础理论之一。经典r o u g h 集理论及其已有的多种扩展模型，其本质都是建立在属性值“相同”或近似相等 基础之上，而相等只是信息系统中属性值间的基本关系之一，由此得到的r o u g h 集模型有着一定的局限性。 序关系是属性值域上的另外一种基本关系。基于序关系的r o u g h 集模型与基 于等价关系的经典r o u g h 集或其扩展模型有较大不同，其关系类、近似集、属 性约筒、决策规则获取都有自身的特点。本文讨论了基于序关系的r o u 曲集模 型及相关课题，并将该模型应用于信息系统的知识发现。 本文首先建立了信息系统中属性值域和对象域上的序关系，讨论了基于序关 系的r o u g h 集模型及其基本性质。然后以此为基础，研究了基于该模型的属性 约简、属性值约简和决策规则获取等基本问题，得到了一些不同于经典信息系统 的结果。最后我们设计了一个实验系统来展示该模型应用于信息系统知识发现的 可行性，并介绍了两个使用该模型来进行知识发现的应用实例。 关键词：r 0 u 曲集，序关系，信息系统，知识发现 基于序关系的r o u g h 集模型及知识发现 r o u g h s e tm o d e la n dk n o w l e d g ed i s c o v e r yb a s e do i l o r d e rl k l a f i o n m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：j i a n gy i q u a n s u p e r v i s o r ：y ex i a o p i n g a s s o c i a t ep r o f e s s o r a b s t r a c t r o u g h s e tt h e o r yi sau e wm a t h e m a t i c a lt o o lt od e a lw i t hv a g u e n e s sa n d u n c e r t a i n t y i tr e g a r d st h ek n o w l e d g ea st h ep a r t i t i o no f u n i v e r s e ，a n du s et h ek n o w n k n o w l e d g et od e s c r i p tt h ev a g u eo ru n c e r t a i no r e sa p p r o x i m a t i v e l y b e c a u s eo fi t s e x c e l l e n td a t ap r o c e s s i n ga b i l i t y , r o u 曲s e tt h e o r yh a sb e e no n eo ft h eb a s i ct h e o r i e so f s o f tc o m p u t i n ga n dw i d e l ya p p l i e di nv a r i o u sf i e l d s ，s u c ha sd a t am i n i n g ，m a c h i n e l e a r n i n g ，d e c i s i o ns u p p o r ta n da n a l y s i sa n dv a g u ec o n t r 0 1 t h ec h a r a c t e r i s t i co fc l a s s i c r o u g hs e tt h e o r ya n dm o d e l se x t e n d e df r o mr o u g hs e ti sb a s e do nt h ee q u a lo r a p p r o x i m a t i v ee q u a l ，h o w e v e r , t h ee q u a l i t yi so n l yo n eo ft h eb a s i cr e l a t i o n sb e t w e e n a t t r i b u t ev a l u e si ni n f o r m a t i o ns y s t e m ，t h e r ea l es o m ec e r t a i nl i m i t a t i o n si nt h o s e r o u g hs e tm o d e l o r d e ri sa n o t h e rb a s i cr e l a t i o no na t t r i b u t ev a l u ed o m a i n t h er e l a t i o nc l a s s e s ， a p p r o x i m a t i o ns e t s ，a t t r i b u t e sr e d u c t i o na n dd e c i s i o nr o l e so b t a i n m e n to fr o u g hs e t m o d e lb a s e do no r d g ir e | a l t o na r eu n i q u et ot h ec h s s i cr o u g hs e tm o d e la n d i t s e x t e n d e dm o d e l s ，i nt h i sp a p e r , w ee s t a b l i s ht h er o u g hs e tm o d e lb a s e do no r d e r r e l a t i o n ，d i s c u s si t sb a s i cc h a r a c t e r s , a n da p p l yi ti nt h ek n o w l e d g ed i s c o v e r yo f i n f o r m a t i o ns y s t e m t h i sp a p e rf i r s t l yp u t sf o r w a r dt h eo r d e rr e l a t i o no na t t r i b u t ev a l u ed o 瑚i na n d o b j e c td o m a i n ，a n dt h e ne s t a b l i s h e st h er o u g hs e tm o d e lb a s e do no r d e rr e l a t i o n ，a n d d i s c u s s e st h eb a s i cc h a r a c t e r so ft h em o d e l s e c o n d l y , s e v e r a lb a s i cp r o b l e m sa b o u t a t t r i b u t er e d u c t i o n ，a t t r m u t ev a l u er e d u c t i o na n dd e c i s i o n r u l eo b t a 妇e n ta r e d i s c u s s e d ，w i t hs o m er e s u l t sc o m eo u t ，w h i c ha r ed i f f e r e n tt ot h o s eg e n e r a t e df r o m 丌 茎主壁差墨堕些! 鲤塞堡型垦塑望茎翌 c l a s s i ci n f o r m a t i o ns y s t e m s l a s t l y , i no r d e rt ot e s tf e a s i b i l i t yo fa p p l y i n go u rm o d e l i n t oi n f o r m a t i o ns y s t e mk n o w l e d g ed i s c o v e r y , as o f t w a r ee x p e r i m e n ts y s t e mi sb u i l t a n dt w oc a s e sa r es h o w n k e y w o r d s ：r o u g hs e t ，o r d e rr e l a t i o n ，i n f o r m a t i o ns y s t e m ，k n o w l e d g ed i s c o v e r y 1 1 1 基于序关系的r o u g h 集模型及知识发现 第1 章绪论 经典r o u g h 集( 粗糙集) 理论是本论文的理论基础及立足点。本章首先对 r o u g h 集进行了简单的介绍，然后讨论了r o u g h 集相关领域的研究现状和最新进 展，本章的最后介绍了论文的研究思路以及全文章节结构的安排。 1 1 引言 十八世纪，德国数学家g w l e i b n i z 倡导用通用符号语言和逻辑演算改革形 式逻辑学。十九世纪，德国数学家g f r e g e 等人建立了命题演算和一阶谓词演算 系统，最终形成了数理逻辑学体系。但是，这种经典逻辑学只有真、假值之分。 在现实生活中，有许多含糊现象并不能简单地用真、假值来表示。例如，“秃子” 是个我们很熟悉的名词，但麻该怎样定义它呢? 按照经典集合的观点，具有n 根 头发的人是秃子。那么有n + l 根头发的人就不是秃子，这显然与事实不符。退一 步说，如果我们承认头发加减一根丁：此人是否是秃子无关，并且显然没有头发的 人是秃子，那么根据数学归纳法，我们可以得到结论：天下所有的人都是秃子。 这是不是很荒谬呢? 因此，“秃子”是个模糊概念，而对于此类模糊现象经典集 合理论是无能为力的。 1 9 6 5 年，美国的控制论专家l a z a d e h 提出了模糊集理论，- - f 用以描述模 糊现象的理论诞生了。尽管模糊集己被广泛应用，但是令人遗憾的是，模糊集是 不可计算的。模糊集理论也一直受到数学界尖锐的批评，焦点在于“模糊集没有 数学基础”。在模糊集理论中，没有给出数学公式来描述诸如“秃子”这类的模 糊概念，故无法计算出概念边界上具体的含糊元素数目。 1 9 8 2 年，波兰学者z p a w l a k 教授提出了r o u g h 集的概念【1 l o 他把那些无法 确认的个体都归属于边界区域，而这种边界区域被定义为上近似集和下近似集之 差集。对于模糊的现象，r o u g h 集有确定的数学公式来进行描述，也可计算其含 糊度。之后，许多学者对r o u g h 集理论及其应用进行了深入的研究，r o u g h 集的 理论体系也逐渐建立了起来。 r o u g h 集是一种处理含糊和不精确性问题的新型数学工具f 2 l 。它建立在分类 基于序关系的r o u g h 集模型及知识发现 机制的基础上，将知识理解为对属性值数据的划分。r o u g h 集理论的主要思想是 利用已知的知识库，用知识库中已有知识来近似描述与刻画不确定或不精确的知 识。该理论与其他处理不确定和不精确问题理论的最显著的区别是它无需提供问 题所需处理的数据集合之外的任何先验信息f 3 】。 由于具有出色的数据处理能力，r o u g h 集在数据挖掘i ”、机器学习与知识发 现口1 、人工智能1 6 l 、决策支持与分析、专家系统n 模糊控制等诸多领域都得到 了广泛的应用。模糊数学的创始人l a z a d e h 对r o u g h 集给予了很高的评价，并将 其列为他新提倡的软计算的基础理论之一。 1 2r o u g h 集的研究现状 p a w l a k 教授提出r o u g h 集的概念之后，在1 9 9 1 年出版了第一本关t - r o u g h 集的专著【8 】，全面阐述了该理论，为该理论奠定了严密的数学基础。1 9 9 2 年， r s l o w i n s k i 主编的关于r o u g h 集应用与相关方法比较研究的论文集的出版，推 动了对r o u g h 集理论的深入研究。从1 9 9 2 年至今，每年都召开以r o u g h 集为主 题的国际会议，r o u g h 集理论得到迅速发展。 r o u g l l 集是信息科学的热点研究领域，当前该领域的研究t 作主要集中在 r o u g h 集相关理论的研究和相关应用研究这两方面。 1 2 1 理论研究 近年来对r o u g h 集的理论研究多集中在r o u g h 逻辑、r o u g h 集的扩展模型、 r o u g h 集的算法研究等方面。 ( 1 ) r o u g h 逻辑和r o u g h 推理 z p a w l a k 给出了r o u g h 逻辑的5 个真值：真、假、粗糙真、粗糙假和粗糙不 一致，定义了r o u g h 逻辑和决策逻辑吼a s k o w r o n 研究了r o u g h 概念逻辑和近 似逻辑，强调这种逻辑的完备性。m k c h a t a b o r y 提出了带粗糙量词的r o u g h 逻 辑，并建立了一套近似推理的逻辑丁具。a n a k a m u r a 定义了一种粗糙层次模态 性i ”l ，把5 种模态逻辑分别对应于5 种模糊和粗糙性，并把r o u g h 逻辑、模糊 逻辑和摸态逻辑融为一体。这些研究为经典逻辑在近似推理中的应用开辟了新的 途径。 基于序关系的r o u g h 集模型及知识发现 ( 2 ) r o u g h 集扩展模型 经典的r o u g h 集以完备信息系统为研究对象，缺乏对不完备信息系统的处理 机制。然而，现实处理的信息系统大多是不完各的。基于这种考虑，z i a r k o 提出 了可变精度的r o u g h 集删( v p r s ) i “】。该模型通过引入集合的两种相对误 分度，对集合包含运算进行了推广，主要是为了在不确定信息情况下使用。可变 精度的r o u g h 集模型继承了经典r o u g h 集模型的所有基本数学特性，但是其使 用范闱更广。k r y s z k i e w i c z 建立了基丁| 容差关系的r o u g h 集模型【1 2 , 1 3 ，最主要的 一个概念足赋予信息表中没有值的元素个“n u l l ”值，“n u l l ”值是一种任何值 都有可能的值。s t e f a n o w s k i 等人提出了基于相似关系r o u g h 集模型【“i ，认为对 象可能被不完全描述的原因不仅可能是由于知识不精确，还可能是由于干脆就不 可能用所有的属性来描述它们。因此，不认为未知值是不确定的，而是当前不存 在的，不允许比较未知值。王国胤在对基于容差关系、相似关系和量化容差关系 等的r o u g h 集扩展模型研究的基础上，提出了一种基于限制容差关系的扩展 r o u g h 集模型【1 5 l 。 ( 3 ) 算法研究 r o u g h 集理论中算法研究主要集中在导出规则的增量式算法、约简的启发式 算法、r o u g h 集基本并行算法、与r o u g h 集有关的神经网络与遗传算法等方面。 c h a l 【r a b o n y 研究了运用r o u g h 集从大数据集中提取规则的算法【1 6 】，l i n g r a s 和 d a v i e s + i ) t 究t r o u g h 集和遗传算法的集合提出了一种粗糙遗传算法i ”1 ，何明等 提出了基于增量式遗传算法的r o u g h 集分类规则挖掘1 1 8 】，n s h 柚讨论了基于 r o u g h 集的从数据中发现规则的增量自适应算法i ”1 ，该算法将决策规则和约简的 计算转化为一组相关联的布尔表达式的化简和修改，而无需搜索算法来寻找与修 改规则。 1 2 2 应用研究 ( 1 ) r o t i g h 集应用于数据挖掘 m o l l e s t a d 等提出了基于r o u g h 集理论的缺省规则的挖掘方法【2 0 l ，该方法把 r o u g h 集理论与默认推理结合起来，从而实现信息不完备的情况下仍能根据缺省 规则进行推理，得出当前合理的决策。x ，h h u 等提出了一种将基于属性的归纳 3 基于序关系的r o u g h 集模型及知识发现 法和r o u g h 集相结合的方法。该方法使用概念树爬升技术对属性进行泛化，然 后使用r o u g h 集方法计算约简并生成规则。 ( 2 ) r o u g h 集应用 二粗糙控制 粗糙控制是根据r o u g h 集理论从观测数据中获取控制策略的一种智能控制方 法。k h a s n a b i s 等用r o u g h 集方法实施城市铁路通道控制【”1 ，将铁路沿线同定站点 的交通控制看作一个决羡属性表，通过r o u g h 集从现有数据中获取行驶方案的决 策规则。文献【2 2 】设计了逼近时间粗糙控制器，将r o u g h 集方法与传统p i d 控制相 结合，对卫星姿态角控制系统中的仰角进行了成功的控制。 ( 3 ) r o u g h 集应用于专家系统 美国k _ a n s a s ：；k ：学开发t 基于r o u g h 集的学习系统l e r s ( l e a r n i n gf r o m e x a m p l e sb a s e do nr o u g hs e t s ) 。l e r s 被n a s a sj o h n s o n 空间中心多年应用， 充分显示了它在丌发专家系统进行全球气候变化的研究中起的作用。 ( 4 ) r o u g h 集应用于决策分析 在决策分析中，通常运用r o u g h 集分析以往经验数据以得到决策规则。意大 利 f 塔亚大学学者s a l v a t o r eg r e c o 和波兰波兹纳特大学的r o m a ns l o w i n s h i 提出 可以将r o u g h 集应用于多标准决策分析【”1 。希腊发展银行e t e v a 也应用r o t i g h 集理论协助制订信贷政策，成为r o u g h 集理论多准则决策方法的一个成功范例。 ( 5 ) r o u g h 集应用于信息检索 b e a u b o u e f 等提出了种基t r o u g h 集理论的r o u g h 关系数据库模型l “1 ，并定 义了各种r o u g h 关系算子。该模型将r o u g h 集的重要性质引入到关系模型中，使 之具有更好的检索能力和适应性。 1 3r o u g h 集研究的新进展 r o u g l l 集理论因为其独特的优势吸引着越来越多的研究者关注，然而这仍是 一门年轻的学科，还有很多值得研究的问题。今后研究的主要热点在以下几个方 面： ( 1 ) r o u g h 逻辑 基丁二r o 时集的不精确推理是r o u g h 集应用研究中最重要的课题之一，有必要 对r o u g h 逻辑理论进一步系统化和形式化。 基于序关系的r o u g h 集模型及知识发现 ( 2 ) 不完备信息系统的处理 信息系统往往会因为各种原因而丢失数据，或包含不确定的数据，含有丢失 数据或不确定数据的信息系统是不完备的信息系统。造成数据丢失的原因很多， 如对数据测量的误差、数据理解和数据获取的限制等等。经典r o u g h 集理论是基 于完备信息系统的，不适用于处理不完备信息系统。为了使这一理论适合丁不完 备信息系统的处理，需要建立处理不完备信息系统的扩) 畏r o u g h 集模型。 ( 3 ) 商效的约简算法。 约简的求解是n p 问题，导致其成为n p i h 题的主要原因是属性的组合爆炸。 高效的约简算、法是r o u g h 集应用于知识发现的基础，通常做法是使用基于启发式 知识的约简。但现在还没有一种非常有效的方法，因此寻求快速、高效的约简算 法仍是r o u g h 集理论的研究热点之一。 ( 4 ) 多方法融合 目前，r o u g h 集理论已经与其他理论相结合来解决诸如知识发现之类的问题， 但多方法融合方面的研究工作还有待于进一步展开。 1 4 本论文研究思路和内容安排 1 4 1 研究思路 经典的r o u g h 集理论建立在不可分辩关系的基础上，以完备信息系统为研究 对象，条件较为苛刻。现实世界中，信息系统多为不完备信息系统，如何用r o u g h 集这个有效的数据处理工具来处理不完备信息系统就成为r o u g h 集研究的一个 迫切而重要的课题。为了使r o u g 集能应用于不完备信息系统的发现知识，很多 学者建立了r o u g h 集的扩展模型，如基于容差关系的r o u g h 集扩展模型、基于 相似关系的r o u g h 集扩展模型等。 目前，虽然已经存在多个r o u g h 集的扩展模型，但它们的本质仍然是建立在 基于属性值的相等关系之上，即通过属性值域中对应属性值相等与否将论域中对 象进行分类( 划分) 。一般情况下，这样划分能发现信息系统中的部分知识和处 理相应问题，但也存在着一些问题( 详见第3 章分析) ，因而有必要对基于其他 关系的r o u g h 集扩展模型进行探讨。 苎! 壁差墨箜墨竺韭叁堡型墨塑望垄翌 本文研究基于序关系的r o u g h 集模型及以该模型为基础的知识发现。为了实 现研究目标，本文的研究路线如图1 - 1 所示。 例i 篓f 刎i 鬻鬻j jl_1一一 建屯信息系统l 圭塑曼鲞! l _ j 理论研究 医习l i j ! 匝i 理论验证： 为了建立基于序关系的r o u g h 集模型，对于给定信息系统，本文首先由属性 值域上的偏序关系建立系统对象域及论域e 的序关系，然后讨论了基于这个关系 的r o u g h 集的基本性质。建立起基于序关系r o u g h 集模型后，比较深入的研究 了该模型的属性约简、属性值约简、决策规则获取等基本课题。接着，建立了不 完备信息系统的序关系，并应用本文建立的模型对其上的知识发现进行探讨。文 中设计了一个实验系统来展示该模型应用于信息系统知识发现的可行性，最后介 绍了两个使用该模型来进行知识发现的应用实例。 1 4 2 论文结构安排 论文后续章节的安排如下： 第二章是本文所涉及到理论与技术的基础性介绍，对经典的r o u g h 集理论和 相关技术作概要性的阐述。主要介绍了不可分辩关系、近似集概念，以及r o u g h 集粗糙度的刻画；然后描述了信息系统以及其上的属性约简，属性值约简；最后 介绍了决策系统与决策规则的获取。 第三章是本文的基本，t 作，主要是把经典r o u g 】1 集理论扩展到基于偏序关系 的非经典情形。首先讨论了其他r o u g h 集模型存在的问题，定义了信息系统中 属性值域上的偏序关系，由此偏序关系导出了对象域上的一个拟序关系：然后给 等 基于序关系的r o u g h 集模型及知识发现 出了基于拟序关系的关系类和建立在这些关系类基础之上的近似集的概念，提出 _ 关系类的计算算法；接着讨论了基于偏序关系的属性约简问题，并给出了属性 约简的算法；本章最后建立了不完备信息系统中的序关系，并将基于序关系的 r o u g h 集模型应用于其上。 第四章是本文结果的一个试验模型，主要介绍了一个基丁偏序关系信息系统 的实验系统。该系统使用基于序关系r o u g h 集关系类划分、属性约简、决策规 则获取方法，对给定的数据表作属性约简和规则获取。 第五荜介绍了两个应用实例，用以说明本文的基本结果。 第六章是对论文所做工作的总结，展望可进一步进行的研究工作。 基于序关系的r o u g h 集模型及知识发现 第2 章r o u g h 集基础理论 r o u g h 集理论自提出以来，已经建立起了一套比较完整的理论体系。而建立 在经典r o u g h 集理论之上的应用研究和软件系统开发，都取得了很多的成果。 这说明，r o u g h 集理论不但具有重要的理论意义，也具有很强的实用价值。 本章中，我们首先通过对知识分类的讨论引出r o u g h 集；进而介绍了与r o u g h 集相关的不分明关系、近似集、正域、负域、边界域等概念：接着讨论了近似集 的性质，以及近似精度和隶属函数的概念；最后，介绍了如何在信息系统中进行 属性约简及决策规则获取。 2 1 知识分类 知识是人类通过实践而认识到的关于客观世界的规律性的东西，是人类实践 经验的总结提炼。假定集合u 中的对象具有必要的信息或知识，称之为论域。u 上的知识分类可以理解为一个等价关系，这个等价关系将u 划分成概念族，从 而得至论域u 上的知识。若两个对象具有相同的信息，则他们属于同一概念族， 是不可区分的【4 ，捌。 定义2 1 设u 为论域，r 为u 上的等价关系。称二元组a s = ( u ，r ) 为近似空 间。 近似空间形成了论域u 上的一个分类。 定义2 2 对论域u 上的任何子集x ( x u ) ，称x 为u 上的范畴或概念， 约定g 也是一个概念。u 中的任何概念族称为关于u 的抽象知识，简称知识。u 上知识( 分类) 的族集构成关于u 的知识库。 因此，u 上的一个等价关系就是u 的一个分类方法，它代表了对u 中个体 的分类，形成u 上的知识。u 上的等价关系族则是知识( 分类) 的族集，也即u 的知识库。 关于u 的一个知识库也可以理解为一个关系系统。其中u 为论域，r ( r = r 1 ，r 2 ，r n ) ，其中r - ，r z ，r 。都是等价关系) 是u 上的等价关系簇，这 些等价关系对u 进行不同的分类，每种划分将把u 分为不同的子集( 概念) 。 苎王壁菱墨墼婴业塞堡型墨塑望茎翌 定义2 3 设u 为论域，r 为u 上的等价关系族，p r 且p 柏，则p 中所有 等价关系的交集称为p 上的不可分辨关系，记作 n d 口) 。 由不可分辨关系的定义可知，不可分辨关系也足等价关系，且有： x i n d ( p ) = u x g 其中， x 】i n d c p ) 和 x r 分别表示x 在等价关系i n d ( p ) ； 1 1 r 下的等价类。 定义2 4 设u 为论域，r 为u 上的等价关系族，p c r 且p o ，则不可分辨 关系i n d ( p ) 的所有等价类的集合u i n d ( p ) 称为u 的p 基本知识，相应等价类称 为知识p 的基本概念。由于在r 中所选不同子集p 就能得到u 上的不同知识， 故称k = ( u ，r ) 为知识库。 对于给定的知识库k = ( u ，r ) ，知识的粒度可通过i n d ( g ) 的等价类来反映， 且有： p r ，则i n d ( r ) i n d ( p ) 例2 1 现有笔记本电脑的集合u ，笔记本电脑的基本情况见表2 - 1 。 表2 - 1 笔记本电脑描述 c p u m e m o r y h a r d d i s k w e i g h t x 1 i n t e lp e m t i u m1 3 g1 2 8 m2 0 g轻 x 2 a m dm o b i l e2 0 0 0 +2 5 6 m2 0 g轻 x 3 i n t e lc e l e r o n1 2 g2 5 6 m4 0 g重 x 4 i n t e lp e m t i u m1 3 g5 1 2 m6 0 g轻 如 a m dm o b i l e2 0 0 0 - f5 1 2 m 6 0 g重 x 6 i n t e lc e l e m n1 2 g1 2 8 m2 0 g 轻 设有集合u 上的等价关系族r = r i ，r 2 ，r 3 ) 。r 1 ，r 2 ，r 3 分别为 r l = l x 与y c p u 相同 r 2 = i x 与y m e m o r y 相同 r 3 = ix 与yh a r d d i s k 相同) r 4 = i x 与y w e i g h t 相同 p = r 2 ，r 3 ，r 4 ) 基于序关系的r o u g h 集模型及知识发现 则 u r 1 = “x 1 ，) 【4 ， x 2 ，x 5 x 3 ，x 0 为关于c p u 的初等概念 u r 2 = x l ，x 6 ) ， x 2 ，x 3 ) x 4 ，x 5 ) 为关于m e m o r y 的初等概念 u 瓜3 = “x l ，x 2 ，x 6 ) ， x 3 ， x 4 ，x 5 ) ) 为关于h a r d d i s k 的初等概念 u l h = x i ，x 2 ，殛， ， x 3 ，x 5 ) 为关于w e i g h t 的初等概念 u i n d ( p ) = “x l ，x 6 ， x 2 ， x 3 ) ， 鞠) ， x 5 ) u i n d ( p ) 为笔记本电脑相关的m e m o r y 、h a r d d i s k 和w e i g h t 的知识，是初等 概念u r 2 、u r 3 和u r 4 的交集。以不同的标准来对论域进行分类，将得到不同 的知识。其中有些知识是我们需要的，而另外一些知识可能是没有价值的。知识 获取就是要搜寻出隐藏在数据中的知识，而这正足r o u g h 集理论的用武之地。 2 2r o u g h 集的基本概念和性质 2 2 1r o u g h 集的基本概念 r o u g h 集理论是建立在论域u 的不可分辨关系之上。对应论域u 上的对象集 x ，x 可由不可分辨关系i n d ( p ) 确定的知识来划分。这时有三种可能性： ( 1 ) e i n d ( p ) ，且e _ x ，即x 一定包含概念e 。 ( 2 ) e i n d ( p ) ，e c x 且e n x o ，即x 包含概念e 的一部分。 ( 3 ) e e i n d ( p ) ，且e n x _ a ；即x 肯定不包含概念e 。 若对象集x 能完全表示为知识e 的集合，称x 是可定义的；若x 不能完全 表示为知识e 的集合，则称x 是不可定义的。 定义2 5 给定近似空间a s = ( u ，r ) ，x c _ u ，定义 墨g ) = x lx u 且【x 】r x ) r ( x ) = 叫x u 且【x 】r n x a b n r ( x ) = 墨( x ) 一r ( x ) p o s r ( x ) = _ r ( ) ( ) n e g r ( x ) = u r ( 冯 基于序关系的r o u g h 集模型及知识发现 分别称星( x ) 为x 的r - 下近似集，r ( x ) 为x 的r - 上近似集，b n n ( x ) 为x 的r - 边界域，p o s r ( x ) 为x 的r 正区域，n e g r ( x ) 为x 的r - 负区域。 r ( ) ( ) 是所有被包含在x 中的等价类的并集，是必定属于x 的对象组成的集 合；rf x ) 是所有与x 有交的等价类的并集，足可能属于x 的对象组成的集合； b n r ( x ) 是那些不能明确判断是否属于x 的对象组成的集合；n e g r ( x ) 是那些一 定不属于x 的对象组成的集合。各部分的关系如图2 - 1 所示。 翻2 - 1r o u g h 集示意图 定义2 6 给定近似空间a s = ( u ，r ) ，x c _ u ，则 ( 1 ) 若墨( x ) = 画( x ) ，即b n r ( x ) = a ，称x 是精确集( 或可定义集) ； ( 2 ) 若墨( x ) r i x ) ，即b n r ( x ) - # o ，称x 是r o u g h 集( 或不可定义集) 。 x 是r o u g h 集，则x 对应一个r o u g h 的概念，只能通过x 的上近似集和下 近似集来“近似”地描述。 例2 2 设有近似空间a s = ( u ，r ) ，u = x l ，x 2 ，x 3 ，x 4 ，x 5 ，x 6 ，x 7 ，】【8 ) ，等价关系r 在 u 上划分的等价类分别为e x = x d ，e 2 = x 2 ，x 5 ) ，e 3 = x 3 ，】【4 ，x 7 ) ，e 4 = x 6 ，) 。现有 x 1 = 1 l ，x 2 ，x s ，x 2 = x 1 ，x 3 ，x 4 ，x 5 ，x 7 ，x d 。分别求x 1 ，x 2 的上近似集、下近似集、边 界域、正区域、负区域。 解：对x 1 ，有 星( x 1 ) = e 1 u e 2 = x 1 ，x 2 ，x 5 ) 尺( x 1 ) = e 1 u e z = x 1 ，x 2 ，x s 基于序关系的r o u g h 集模型及知识发现 b n r ( x 1 ) = r ( x 1 ) - 星( x 1 ) = g p o s r ( x 0 = 8 ( x 0 = f x l ，x 2 ，x s n e g r ( x 0 = u - r ( x i ) = x 3 ，x 4 ，粕，x 7 ，x 8 对x 2 ，有 _ r ( x 2 ) = e 1 u e 3 = x l ，x 3 ，x 4 ，x 7 r ( x 2 ) = e 1 ue 2ue 3u e 4 = x l ，x 2 ，x 3 ，x 4 ，x 5 ，x 6 ，x 7 ，x 8 ) b n r ( x 2 ) = r ( x 2 ) 一旦( x 2 ) = x 2 ，x 5 ，x 6 ，x 8 ， p o sr ( x 2 ) = r ( x 2 ) = x x ，x 3 ，x 4 ，x 7 ) n e g r ( x 2 ) = u - r ( x 2 ) = 庐 从例2 2 可知，在近似空间a s = ( u ，r ) 上，x l 是精确集，x 2 是r o u g h 集。 2 2 2r o u g h 集的基本性质 定理2 1r - 上近似集和r 下近似集具有下述性质 ( 1 ) 星( x ) c x _ c r ( 2 ) 墨( g ) - 瓦( o ) = 彩 ( 3 ) 星( u ) = 面( u ) = u ( 4 ) 墨( x n y ) = 星( ) o n 墨( y ) ( 5 ) r ( x u = 尺( x ) ur ( y ) ( 6 ) r ( x u y ) 三旦( x ) u 宣( y ) ( 7 ) r ( x n y ) 尺( x ) nr ( ( 8 ) x y 墨( x ) 星( y ) ( 9 ) x c y r ( x ) _ c r ( y ) ( 1 0 ) 墨( x ) = i ( x ) ( 1 1 ) r ( x ) = - 8 ( x ) 1 2 基于穿关系的r o u g h 集模型及知识发现 ( 1 2 ) 星( 星( x ) ) = r ( 旦( x ) ) = 星( x ) ( 1 3 ) i ( 页( x ”= 星( 蠢( x ) ) = 再( x ) 2 3r o u g h 集的刻画 2 3 1 近似精度 例2 , 2 中，x 2 相对于近似空间a s = ( u ，r ) 是r o u g h 集，即属于边界域上的元 素不能在近似空问的子集上被完全划分，但是能不能在数学上说明x 2 相对于近 似空间a s 的r o u g h 程度? r o u g h 集的个优点就是能够用数学公式来对这种r o u g h 程度进行刻画。通 常可以用近似精度来刻画r o u g h 集的r o u g h 程度，近似精度刻画了r o u g h 集边 界域的相对大小。 定义2 7 给定近似空间a s = ( u ，r 1 ，x _ c u ，则称 n r ( x ) = 矧“聊 为x 相对于近似空间a s 的近似精度，其中i s l 表示集合s 的基数。 定理2 2 近似精度ar ( x ) 具有下列性质： ( 1 ) 船or ( 均s 1 ( 2 ) 墨( x ) = r ( x ) ar ( x ) = 1 b n r ( x ) = g ( 3 ) 基( x ) c r ( x ) qr ( 玛 l b n r ( x ) ：1 2 1 因此，若nn ( x ) = l ，则x 相对于近似空间a s 是可定义的；反之，若nr ( x ) o ) 基于序关系的r o u g h 集模型及知识发现 b n r ( x ) = x i x e u 且0 p x r ( x ) ) ；v = uv 。 d 为属性集a 的值区域，其中v 。为属性a 的值域；f ：u x a v 是一个信息函数， 对v x e u a a 有f ( x ，a ) e v , 。 信息系统可用二维表的形式表示出来，表2 - 1 所示就是一个信息系统。 对于信息系统s = ( u ，a ) ，若p _ c a 且p g ，则由p 导出的二元关系i n d ( p ) 足 等价关系。若x ，y u 为论域u 中的两个对象，如果有v a m p ，f ( x ，a ) = y ，a ) ，那么 仅仅根据属性集p 提供的信息，无法将x ，y 区别开来，这时我们称x ，y 在属性集 p 上是不可分辨的。 属性a 的任意子集可形成论域u 上的一个划分，形成了信息系统s 上的知 识。信息系统和知识库是相对应的，一个信息系统可以看成一个知识库。 定义2 1 7 设s f ( u ，a ) 是一个信息系统，c ，d c a 是属性a 的子集，且c u d = a ，c m d = o ，分别称c 和d 为a 的条件属性和决策属性，称信息系统s 为 一个决策表，记作t = ( u ，a ，c ，d ) 。 定义2 1 8 设t ：= ( u ，acd ) 是- - 个决策表，函数d ；：c ( x ) 一d ( 对称为t 上的一 条决策规则，d l c 称为决策规则的条件部分，dx i c 称为决策规则的结论部分。 定义2 1 9 决策规则d x 是一致的，当且仅当对v y u ，y 扛，若c ( x ) = c ( y ) 则 d ( x ) = d ( y ) ；如果决策表中所有的决策规则都是一致的，称该决策表为一致决策 表，否则称不一致决策表。 决策规则是一致的，表明若决策规则的条件值相同，则必定有相同的决策值。 基于序关系的r o u g h 集模型及知识发现 决策表是一致的，表明在决策表中没有相互矛盾的决策规则。 推论2 2 决策表t = ( u ，气c ，d ) 是- - 致决策表，当且仅当i n d ( c ) _ i n d ( d ) 。 2 4 3 属性约简 属性约简和属性值约简是决策表简化的鼹种方法。属性约简是从决策表中消 去不必要的属性，属性值约简是从决策表中消去那些无关紧要的属性值。通过属 性约简和属性值约简，可以得到简化的决策规则。 由丁信息系统和知识库是等价的，因此知识约简的相关概念同样适用丁- 属性 约简。 定义2 2 0 令s = ( u ， v , 0 是- - 个信息系统，a e a ，对v x ，y e u ，若f ( a x ) h a y ) 且f ( a - a ，x ) f ( a - a ) ，y ) ，则称属性a 是可约去的，否则称a 是不可约去的；若 p _ a ，且p 中的所有属性都是不可约去的，则称p 是属性a 的一个约简；a 中 所有不可约去的属性称为属性集a 的核。 同知识约简，所有约简的集合记作i 砸d ( a ) ，核的集合记作c o x ( a ) ，且有 c o r e ( a ) = nr e d ( a ) 。 定义2 2 1 令s = ( u ，a ) 为信息系统，b a ，有 ( 1 ) 若属性b 在所有约简中都不能消去，称b 为绝对必要属性。 ( 2 ) 若属性b 在所有约简中都不出现，称b 为绝对不必要属性。 ( 3 ) 属性b 在有些约简中出现，而在有些约简中则不出现，称b 为相对必 要属性。 定义2 2 2 令1 ( u ，a , c ，d ) 是一个决策表，若p o s c 。 ( d ) = p o s c ( d ) ，则称属 性a 是d 可约去的，否则称a 是d 不可约去的；若p _ c ，且p 中的所有属性都 足d 不可约去的，则称p 为d 一约简。 属性约简可使用分辩矩阵方法来进行。 定义2 2 3 令s = ( u ，a ) 为一信息系统，u = x l ，x 2 ，x n ，定义分辫矩阵为 m ( s ) = ( 1 l l i j ) mx | u i 其中m i j = a i ( v a ) ( a e ；a , a ( x i ) a ( x j ) ) 。 定义2 2 4 令m ( s ) 为信息系统s = ( u ，a ) 的分辫矩阵，分辩函数f m 被定义为 基于序关系的r o u g h 集模型及知识发现 h f 鼬= a v m l j 其中，v m u 为m i j 中所有元素的析取， v m 日 为m ( s ) 中析取式的合取。 分辩函数f m 的每个极小析取范式中合取范式为属性集的一个约简，这些合 取范式的交集即为属性集的核集。 使用分辩矩阵来进行属