（计算机应用技术专业论文）基于粗糙集的粒度计算在数据挖掘中的应用研究.pdf

摘要 摘要 随着数据库技术的广泛应用，数据库中存储的数据量急剧增大。对如此庞大的 数据需要进行较高层次的处理，从中找出规律和模式，以帮助人们更好地利用这些 数据进行决策和研究，因而提出了知识发现和数据挖掘的概念。知识发现是从数据 集中识别出有效的、新颖的、潜在有用的，以及最终可理解的模式的非平凡过程。 数据挖掘是从数据库的大量数据中提取隐含的、未知的并有潜在价值的信息和知识 的过程。数据挖掘是知识发现中最关键的步骤，也是知识发现技术难点，是目前相 当活跃的研究领域。 粗糙集理论是波兰数学家p a w l a k 提出的一种分析模糊和不确定知识的强有力 的数学工具，能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并 从中发现隐含的知识，揭示潜在的规律，这个特点使得粗糙集理论非常适用于数据 挖掘。人们在思考和解决问题时，往往根据需要，或者是先整体后部分；或者是先 部分后整体；或者是交替使用以上两种方法。人们不仅能在不同粒度的世界上进行 问题求解，而且能够很快地从一个粒度世界跳到另一个粒度的世界，往返自如，毫 无困难。因此将粒度的概念引入到数据挖掘中去有着非常重要的意义。 本文主要研究将粒度思想应用于数据挖掘过程中，从粒度的概念和角度进行属 性约简和规则提取，用于从大型数据库中挖掘出有用和用户感兴趣的知识，解决信 息系统数据多而知识少的问题。本文综述了数据挖掘和粗糙集的相关理论及国内外 研究现状，探讨了粒度计算的研究领域和数据挖掘技术热点以及两者未来发展趋势。 深入研究了粗糙集理论的约简算法，约简算法包括属性约简和属性值约简。在目前 属性约简算法的基础上提出了一种基于条件信息熵的属性约简改进算法，同时将粒 度思想应用到规则提取中，在前人所作研究的基础上提出了基于搜索粒度，自顶向 下，建立多层次粒度模型的规则提取算法。针对传统的基于粗糙集理论的数据挖掘 模型存在不实用的特点，提出了一种改进的数据挖掘模型。该模型包括数据预处理、 属性约简和规则提取三个模块，并利用算例验证该模型的可行性。 关键词：粒度计算；数据挖掘；粗糙集；属性约简；规则提取 广东工业大学工学硕士学位论文 a b s tr a c t w i t ht h ee x t e n s i v ea p p l i c a t i o no fd a t a b a s et e c h n o l o g y , t h ea m o u n to fd a t ai nt h e d a t a b a s ei n c r e a s e sr a p i d l y p r o p o s e dt h ec o n c e p to fk n o w l e d g ed i s c o v e r ya n dd a t e m i i l i n g ，i no r d e rt op r o c e s st h eh u g ed a t a b a s ei nah i g h e rl e v e la n df i n do u tl a w sa n d m o d e l st oh e l pp e o p l em a k eb e t t e ru s eo ft h e s ed a t af o rd e c i s i o n - m a k i n g k n o w l e d g e d i s c o v e r yi st h en o n - t r i v i a lp r o c e s st h a td i s t i n g u i s he f f e c t i v e ，i n n o v a t i v ea n dp o t e n t i a l l y u s e f u l ，a n du l t i m a t e l yu n d e r s t a n d a b l ep a t t e mf r o mt h ea m o u n to fd a t a d a t am i n i n gi st h e p r o c e s st h a te x t r a c t sh i d d e n ，u n k n o w na n dt h ep o t e n t i a lv a l u eo fi n f o r m a t i o na n d k n o w l e d g ef o r ml a r g ea m o u n t so fd a t ao ft h ed a t a b a s e d a t am i n i n gi st h em o s tc r i t i c a l s t e p si nk n o w l e d g ed i s c o v e r y , b u ta l s ot h et e c h n i c a ld i f f i c u l t i e si nk n o w l e d g ed i s c o v e r y , i st h ev e r ya c t i v ea r e ao fr e s e a r c hn o w a d a y s t h et h e o r yo fr o u g hs e t s ，p r e s e n t e db yp o l i s hm a t h e m a t i c i a np a w l a kz ，i sa p o w e r f u lm a t h e m a t i c a lt o o lf o ra n a l y z i n gu n c e r t a i n ，f u z z yk n o w l e d g e r o u g hs e t s ，a sa n e wh o ts p o ti nt h ef i e l do fa r t i f i c i a li n t e l l i g e n c e ，c a ne f f e c t i v e l yd e a lw i t ht h ee x p r e s s i o n a n dd e d u c t i o no fi n c o m p l e t e ，u n c e r t a i nk n o w l e d g e t h et h e o r yo fr o u g hs e t si ss p e c i a l l y f i tf o rt h ea p p l i c a t i o nt od a t a - m i n i n gb e c a u s eo fi tf i e a 眦s w h e nt h i n k i n ga n ds o l v i n g p r o b l e m s ，p e o p l ec h o o s e p a r tt h e ne n t i r e t y 一, o r “e n t i r e t yt h e np a r t ，o ra l t e r n a t i v eu s eo f b o t h ，a c c o r d i n gt ot h en e e d t h ep e o p l ec a l ln o to n l yc a r r yo nt h eq u e s t i o ni nt h ed i f f e r e n t g r a n u l a r i t yw o r l d ，m o r e o v e rc a nj u m pv e r yq u i c k l yf r o mag r a n u l a r i t yw o r l dt oa n o t h e r g r a n u l a r i t y w o r l d t h er o u n d - t r i p f r e e l y , i sn o td i f f i c u l t t h e r e f o r e i n t r o d u c e st h e g r a n u l a r i t yc o n c e p ti nt h ed a t am i n i n gt oh a v et h i sv e r yi m p o r t a n ts i g n i f i c a n c e t h i sp a p e rw i l ls t u d yg r a n u l a r i t yt h o u g h ta n da p p l i e di tt od a t am i n i n gp r o c e s s ， a t t r i b u t i n gr e d u c t i o na n de x t r a c t i n gr u l e si nt h ec o n c e p ta n dg r a n u l a r i t yp e r s p e c t i v e ，u s e d i nm i n i n gu s e f u la n di n t e r e s t i n gk n o w l e d g ef r o ml a r g ed a t a b a s e s ，w h i c hc a nb et h e s o l u t i o no ft h ep r o b l e mt h a tm o r ed a t ab u tl e s sk n o w l e d g e f i r s t l y , t h i sp a p e rs u m m a r i z e d t h ed a t am i n i n ga n dt h er o u g hc o l l e c t i o n sc o r r e l a t i o nt h e o r i e sa n dt h ed o m e s t i ca n d f o r e i g nr e s e a r c hp r e s e n ts i t u a t i o n ，p r o b e d t h et e c h n o l o g yh o t s p o t s o fg r a n u l a r i t y i i a b s t r a c t c o m p u t i n ga n dd a t am i n i n ga n dt h et r e n dd e v e l o p m e n to fb o t h s e c o n d l y ；d i s c u s s e d r e d u c t i o na l g o r i t h mo fr o u g hs e tt h e o r yt h o r o u g h l y , w h i c hi n c l u d e dt h ea t t r i b u t er e d u c t i o n a n dt h ea t t r i b u t ev a l u er e d u c t i o n i nt h ep r e s e n ta t t r i b u t er e d u c t i o na l g o r i t h m sf o u n d a t i o n ， t h i sp a p e rp r o p o s e do n ek i n db a s e do nt h ec o n d i t i o n a li n f o r m a t i o ne n t r o p y sa t t r i b u t e r e d u c t i o ni m p r o v e m e n ta l g o r i t h m ，s i m u l t a n e o u s l y , a p p l i e st h eg r a n u l a r i t yt h o u g h ti nt h e r u l e e x t r a c t i o n ，p r o p o s e dt h e r u l ee x t r a c t i o na l g o r i t h mw h i c hb a s e do nt h es e a r c h g r a n u l a r i t y , f r o mt h et o p ，e s t a b l i s h e st h em u l t i - l e v e lg r a n u l a r i t ym o d e l s f i n a l l ya i m sa t t h et r a d i t i o nt oh a v et h ei m p r a c t i c a lc h a r a c t e r i s t i c ，p r o p o s e dd a t am i n i n gm o d e lb a s e do n t h er o u g hs e tt h e o r y t h i sm o d e li n c l u d i n gt h r e em o d u l e s ：t h ed a t ap r e t r e a t m e n t ，t h e a t t r i b u t er e d u c t i o na n dt h er u l ee x t r a c t i o n ，t h e nc o n f i r m st h i sm o d e l sf e a s i b i l i t yu s i n gt h e e x a m p l e k e yw o r d s ：g r a n u l a r i t yc o m p u t i n g ，d a t am i n i n g ，r o u g hs e t ，a t t r i b u t er e d u c t i o n ，r u l e e x t r a c t i o n i i i 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作过的同志对本研究所做的任何贡 献均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 指导教师签 论文作者签字 寻p 谢本 i 加8 年j 月巧日 第一章绪论 1 1 论文背景 第一章绪论 随着数据库技术的广泛应用，数据库中存储的数据量急剧增大。对如此庞大 的数据需要进行较高层次的处理，从中找出规律和模式，以帮助人们更好地利用 这些数据进行决策和研究。数据挖掘( d a t am i n i n g ) 口1 技术就是在这样一个背景下 产生的，它的宗旨就是在数据库中发现有用的知识。数据挖掘是从大量的、不完 全的、有噪声的、模糊的数据中，提取隐含在其中潜在有用的信息和知识的过程。 数据挖掘技术从一开始就是面向应用的，它对数据从微观到宏观的统计、分析、 综合和推理，指导实际问题的解决，发现事物之间的相互关联并做出预测，在科 学研究、市场营销、金融市场分析与预测、欺诈甄别、医疗保健、现代化教育和 通信网络管理等许多领域得到了广泛的应用。目前，数据挖掘已经成为计算机科 学与工程研究的一个热点。数据挖掘作为知识开发和创新的教学工具在国际上广 泛地应用于金融、市场开发、医疗诊断决策、交通管理和企业业绩评估等众多的 社会信息化领域，以此提高上述行业数据分析的可靠性和精确度，但数据挖掘在 国内各个领域的应用都不太成熟，目前达到理想状态的应用还很少，多数用户仍 处于摸索阶段。 粗糙集为数据挖掘提供了一种新的数学工具。粗糙集不仅可以挖掘知识，而 且可以和其他的数据挖掘技术结合起来，形成混合数据挖掘方法，丰富了数据挖 掘的工具乜1 。人们也在积极寻找粗糙集在数据挖掘中的应用。 1 2 论文写作的目的和意义 随着数据库中存储的数据量越来越大，同时信息系统中数据的不完备性更加 显著。海量杂乱的数据背后隐藏着许多重要的信息，目前的数据库系统虽然可以 高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规 则，无法根据现有的数据预测未来的发展趋势。这些信息无法从传统的信息系统 广东工业大学工学硕士学位论文 分析方法获得，一个新的研究领域知识发现( k n o w l e d g ed i s c o v e r y ) 应运而 生。人们迫切需要新的技术和工具对其进行深入分析，以便从海量的数据中智能 地、自动地抽取出有价值的知识或信息来帮助人们进行分析和研究。由于蕴涵知 识的信息大多数存储于数据库中，数据库知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ，k d d ) ，又称数据挖掘( d a t am i n i n g ，d m ) 成为当前知识发现的主要研 究课题，而粗糙集理论作为一种应用于数据挖掘中的数学工具有着它不可替代的 优点。因此研究基于粗糙集理论的数据挖掘有着极其重要的理论意义和现实意义。 1 3 国内外研究现状 1 3 1 粗糙集理论的研究现状 粗糙集理论1 是由波兰科学家z p a w l a k 教授于1 9 8 2 年提出的一种研究不完 整、不确定知识和数据的表达、学习、归纳的理论方法，这套方法与统计学方法 处理不确定性问题完全不同，同时与这一领域传统的模糊集合论处理不精确数据 的方法也不相同。所谓粗糙集方法，是基于一个机构( 或一组机构) 关于一些现实 和它分辨某些特点、过程、对象等的能力的知识，该方法以观察和测量所得数据 进行分类的能力为基础。它不仅为信息科学和认知科学提供了新的科学逻辑和研 究方法，而且为智能信息处理提供了有效的处理技术。 目前，对粗糙集研究主要集中在：粗糙集模型的推广，问题的不确定性研究， 与其它处理不确定性、模糊性问题的数学理论的关系，纯粹的数学理论方面的研 究，粗糙集的算法研究，与人工智能其它方向关系的研究等。 一、粗糙集数学性质方面的研究 粗糙集数学性质方面的研究主要是对粗糙集理论中知识的不确定性问题进 行理论研究，包括讨论粗糙集代数结构、拓扑结构、粗糙逻辑，以及粗糙集的收 敛性等问题。纯数学理论与粗糙集结合的研究导致了新的数学概念的出现，随着 粗糙结构与代数结构、拓扑结构、序结构等各种结构的不断整合，必将推动粗糙 集的快速发展。 二、粗糙集模型拓展方面的研究 粗糙集模型拓展方面的研究包括可变精度模型( v p r s ，v a r i a b l ep r e o i s i o n 2 第一章绪论 r o u g hs e t s ) 、相似模型( r s tb a s e do ns i m i l a r i t yr e l m i o n ) 和连续属性离散化模型。 主要解决粗糙集应用于数据分析时，遇到数据噪声、数据不完备和连续数据离散 化等问题。 三、粗糙集理论有效算法方面的研究 目前，粗糙集理论中有效算法研究是粗糙集在人工智能方向上研究的一个主 要方面，主要集中在粗糙集基本并行算法和高效算法的研究，与粗糙集有关的神 经网络与遗传算法，属性约简( 特征选择) 启发式算法，提取规则方法和增量式 规则提取算法，有些研究已经获得了商业价值。 四、粗糙集问题的不确定性研究 粗糙集理论中知识的不确定性主要由两个原因产生的h 1 ：一个原因是直接来 自于论域上的二元关系及其产生的知识模块，即近似空间本身，如果二元等价关 系产生的每一个等价类中只有一个元素，那么等价关系产生的划分不含有任何信 息。划分越粗，每一个知识模块越大，知识库中的知识越粗糙，相对于近似空间 的概念和知识就越不确定。针对这一情况，一些学者用香农信息熵来处理知识的 不确定性。知识的粗糙性与信息熵的关系比较密切，知识的粗糙性实质上是其所 含信息多少的更深层次的刻画引。单从这个角度来看，粗糙集理论与信息论的关 系就比较密切，不少学者开展了这方面的研究工作畸6 7 1 。粗糙集理论中知识不确 定性的另一个原因来自于给定论域里粗糙近似的边界，当边界为空集时知识是完 全确定的，边界越大知识就越粗糙或越模糊。至今，粗糙集理论刻画概念x 的不 确定性用正则条件熵h o ( x 拳i r 水) ( 其中x 木= x ， x ) 是x 产生的一个划分，r 宰= x l ， x 2 ，x n ) 是r 产生的一个划分) 3 和粗糙性测度pa ( x ) 来实现的。但是这两个度 量并没有提供那些完全属于x 的下近似区域中与不可分辨关系的知识粒度有关的 不确定性，于是有人引进了粗糙熵e r ( x ) 概念来刻画概念x 的不确定性1 7 1 。寻求一 个合适的度量来刻画知识的不确定性也是粗糙集理论研究的一个重要方向。 五、粗糙集与人工智能其它方向关系的研究 各种智能理论取长补短，相互结合，可以实现不同的应用目的；粗糙集同样 可以与模糊集理论、神经网络、遗传算法、概念格和证据理论等其它智能理论结 合，实现更强大和更优良的功能。在粗糙集理论与其它处理模糊性或不确定性理 论、方法的结合研究中，主要集中在它与概率统计、模糊数学、d s 证据理论和 信息论的相互渗透与补充。在信息系统中，知识库中知识的类型一般有两类：对 广东t 业大学t 学硕士学位论文 于第一类，所有对象的描述是完全已知的，p a w l a k 粗糙集模型和一般二元关系下 的粗糙集模型就面向这一类；对于第二类，对象的描述只有部分是已知的，即知 识库中的知识是不确定的，它只能通过训练样本所提供的信息来刻画概念，为了 使从训练样本获得的规则符合整个论域的对象，在抽取样本时应符合统计规律性， 概率统计作为研究自然界、人类社会及技术过程中大量随机现象的规律性的一门 学科就是面向第二类的。因此，概率统计与粗糙集理论的结合就显得非常自然。 1 3 2 数据挖掘方法的研究现状 数据挖掘，也叫数据库中发现知识( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ， k d d ) 。k d d 一词首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会 议上。随着k d d 在学术界和工业界的影响越来越大，国际k d d 组委会于1 9 9 5 年把 专题讨论会更名为国际会议。研究重点逐渐从发现方法转向系统应用，注重多种 发现策略和技术的集成，以及多种学科之间的相互渗透。 目前，数据挖掘面临的主要问题与挑战有以下几方面陋1 ：( 1 ) 噪音：可能由 于数据丢失，属性值为空值、测试错误等原因造成；( 2 ) 困难的训练集：无代表 性的数据，无边界的例子，有限的信息；( 3 ) 数据库：数据库是动态的，可能是 巨大的。数据挖掘的方法主要有：贝叶斯方法、i d 3 、粗糙集方法。数据挖掘的评 价标准是：学习集的消耗、学习期间时间和存储的限制、正确的预测、预测有噪 音的训练集、被学习知识的有效性、结论的句法及语法的简单性。 与国外相比，国内对数据挖掘的研究稍晚阳j0 | 。1 9 9 3 年国家自然科学基金首 次支持对该领域的研究项目。目前，国内的许多科研单位和高等院校竞相开展知 识发现的基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究 所、空军第三研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊 方法在知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体 代数的研究，华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学 研究所、吉林大学等单位开展了对关联规则开采算法的优化和改造：南京大学、四 川联合大学和上海交通大学等单位探讨、研究了非结构化数据的知识发现以及 w e b 数据挖掘。 4 第一章绪论 1 4 论文的主要工作及内容安排 1 4 1 论文的主要工作 目前，国内外针对信息系统数据挖掘的研究，尤其是在不改变原系统信息成 分的前提下进行挖掘还比较少。本文主要针对基于粒度计算思想的数据挖掘做了 一些研究，具体工作可归纳如下： ( 1 ) 综述了粗糙集和粒度计算及数据挖掘技术的研究现状，阐述了数据挖掘 中粒度计算理论的应用； ( 2 ) 分析和研究基于经典粗糙集理论的属性约简，探讨了粗糙集理论在信息 系统下的拓展； ( 3 ) 研究了不完备信息系统中的不确定性和信息粒度，建立了不完备信息系 统中信息熵与知识粒度、粒度度量与粗糙熵及组合熵与组合粒度之间的关系。 ( 4 ) 在相容关系的基础上，把条件信息熵应用到不完备信息系统，探讨了不 完备信息系统下基于条件信息熵的属性约简算法，并进行了实例分析。 ( 5 ) 基于粒度的思想，提出了基于搜索粒度，自顶向下，建立多层次粒度模 型的规则提取算法，并进行了实例分析。 ( 6 ) 设计了一个基于本文所提出的属性约简和规则提取方法的信息系统的数 据挖掘模型，并用实例验证了其可行性。 1 。4 2 论文的内容安排 如前所述，数据挖掘作为一门新兴的交叉学科提出了很多具有挑战性的研究 课题，其涉及的内容、研究方向非常广泛丰富。本文的研究工作主要围绕基于粗 糙集理论的数据挖掘，重点是从基于粗糙集理论的粒度思想在属性约简和规则提 取两个方面的应用展开。 第一章绪论部分主要介绍了本论文的研究背景和研究意义。 第二章相关理论综述部分主要介绍粒度计算和粗糙集的基础理论，数据挖掘 的基本知识，包括数据挖掘的主要方法和步骤。 第三章不完备信息系统中的粗糙集理论部分主要介绍粗糙集理论在不完备 信息系统中的应用。 广东工业大学工学硕士学位论文 第四章基于条件信息熵的信息系统的知识约简部分主要介绍基于条件信息 熵的属性约简算法。 第五章决策表中的知识粒度及规则提取部分主要研究了基于粒度概念的规 则提取改进算法。 第六章基于粗糙集理论的数据挖掘应用实例部分利用实例验证了本章构造 的数据挖掘模型。 6 第二章相关理论综述 第二章相关理论综述 2 1 粒度计算理论综述 人们在思考问题、解决问题时，往往根据需要，或者是先从总体进行初步分 析，然后再深入研究各部分的具体情况，即先整体后部分；或者是先研究各部分 的情况，然后再进行综合，即先部分后整体；或者是交替使用以上两种方法，即 根据问题的需要，时而从总体上把握问题，时而深入地研究某一部分的具体情况。 这是人类智能公认的特点，张钹和张铃在文n 中指出“人类智能的这种特点，就 是人们能从极不相同的粒度( g r a n u l a r i t y ) 上观察和分析同一问题。人们不仅能在 不同粒度的世界上进行问题求解，而且能够很快地从一个粒度世界跳到另一个粒 度的世界，往返自如，毫无困难。这种处理不同世界的能力，正是人类问题求解 的强有力的表现”。这正是粒度计算的基本思想，粒度计算就是对人类这种能力的 一种形式化。 为了说明粒度计算的基本思想和基本问题，我们可以想象一座办公楼，这座 大楼是由很多楼层组成的，每个楼层又包含了很多房间，每个房间又被分成小的 办公区域。相对于整个社区环境，这座大楼是一个整体，是一个粒，它的外墙及 外形设计就是它的外在属性，相对于更细小的组成部分，这座大楼是复杂的分层 结构，它的内部组成和划分就是它的内在属性。从各个局部来看，每个办公区域 的温度、湿度、人员密度不尽相同。因而显示了粒的内在属性的多样性。从总体 来看，整个办公楼形成一个相对稳定、相对封闭的内环境，从而区别于外环境。 但是，一旦我们需要重新考虑某个全局性问题时，我们又要以较粗的粒度来看问 题了。总之，在解决问题过程中，我们根据需要在不同的粒度世界之间转换。这 恰恰是粒度计算的思想。 目前有关粒度计算的模型主要有3 个，它们分别是：z a d e h 提出的模糊集模 型、波兰学者p a w l a k 提出的粗糙集模型以及我国学者张钹和张铃提出的商空间模 型。下面简单介绍这三个模型。 一、模糊集模型 7 广东工业大学工学硕士学位论文 模糊集模型是粒度计算中人们最熟悉的一个模型，它是z a d e h 根据模糊集理 论提出的。模糊集模型用模糊数学的方法进行有关粒度计算的方法和理论的研究。 粒度根据概念的归纳约束来定义和构造，粒度之间的关系由模糊图或者模糊 i f t h e n 规则来表示。与模糊集模型相应的粒度计算方法称为词计算，模糊集模 型自从提出以来已经在图像处理、模式识别、聚类分析、语音识别等领域得到了 广泛而深入的应用。 二、粗糙集模型 粗糙集模型是由波兰学者p a w l a k 在2 0 世纪8 0 年代初提出的一个分析数据 的数学理论。该理论将分类理解为等价关系，将等价关系对论域的划分理解为知 识。虽然粗糙集模型在2 0 世纪8 0 年代初就已经提出了，但是由于种种原因，在 当时它并未引起计算机研究者的重视。直到9 0 年代初，人们才逐渐认识到它的意 义。目前粗糙集理论已被广泛应用于机器学习、专家系统、决策支持与分析、数 据挖掘等领域，并获得了很大的成功。 三、商空间模型 商空间模型是由我国的张钹教授和张铃教授提出的。在商空间模型下，概念 用子集来表示，不同粒度的概念就体现为不同粒度的子集，一簇概念就构成空间 的一个划分，称为商空间。不同的概念簇就构成不同的商空间。商空间理论就是 研究各商空间之间的关系，各商空间的合成、综合、分解和在商空间中的推理。 商空间模型中有两条非常重要的性质：一是“保假原理或者称为“元解保持原 理”，二是“保真原理”。所谓“保假原理 是指若一命题在粗粒度空间中无解， 则该命题在比它细的商空间中一定也无解。所谓“保真原理”，是指若命题在两个 较粗粒度的商空间中是真的，则在其合成的商空间中对应的命题也是真的。 2 2 粗糙集基本理论综述 信息是决策的基础，如何从大量的、不确定的、模糊的甚至是不完整的信息 中获得有用的信息，即知识，是当前人工智能、数据挖掘及智能决策等领域研究 的热点。由波兰科学家z p a w l a k 于1 9 8 2 年提出的粗糙集理论为处理此类问题提 供了有力的数学工具。它能有效地对这些信息进行分析与处理，并从中发现隐含 的知识，揭示潜在的规律。近几年来，粗糙集理论己越来越受到人们的重视，并 第二章相关理论综述 已在控制理论、知识发现、决策支持与分析以及故障诊断等方面得到了广泛的应 用。 2 2 1 知识的含义与表示方法 知识是人工智能中一个非常重要的概念，解决复杂问题需要大量的知识以及 处理这些知识的机构。知识在不同的范畴中不同的含义。在粗糙集理论中，知识 被看作是关于论域的划分，是一种对对象进行分类的能力。例如医生给病人看病， 可以依据病人的征兆判断出属于哪一类病情。这种根据事务的特征将其分门别类 的台邑力，就是“失识 。 定义2 1 一个近似空间( 或知识库) 定义为一个关系系统( 或二元组) ： k = ( u ，r ) 。其中u 矽( 为空集) 是给定研究对象的有限集合，称为论域。r 是 u 上等价关系的一个族集，称为关于u 的知识。 定义2 2 设尸天，且p ，p 中所有等价关系的交集称为p 上的一种不可 区分关系，记作爪仍( 尸) ，即 x 】，d ( 尸) = n i x 天；表示的是包含元素x u 的r 等 r p 价类。i n d ( p ) 也是等价关系且是唯一的。 定义2 3 给定近似空间k = ( u ，尺) ，子集x u 称为u 上的一个概念，形式 上，空集矽也视为一个概念；非空子族集p r 所产生的不分明关系i n d ( p ) 的所 有等价类关系的集合即u i n d ( p ) ，称为基本知识，相应的等价类称为基本概念； 特别地，若关系q r ，则关系q 就称为初等知识，相应的等价类就称为初等概 念。 由此可知，概念即对象的集合，概念的族集( 分类) 就是u 上的知识，u 上 分类的族集可以认为是u 上的一个知识库，或说知识库即是分类方法的集合，知 识表示是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与 控制结构的统一体，既考虑知识的存储又考虑知识的使用。知识表示可看成是一 组描述事物的约定，以把人类知识表示成机器能处理的数据结构。主要有逻辑表 示法，产生式表示法，语义网络表示法，框架表示法等。 定义2 4 一个知识表达系统s 可表达为：s = ，其中s 为知识表 达系统，u 表示对象的非空有限集合，即论域；a 是属性的非空有限集合；y = u 圪 a m a 是属性值的集合，即属性的值域集，其中v a 是属性a e a 的值域；f 是信息函数， 9 广东工业大学工学硕士学位论文 f u a v ，即f ( x ，a ) v ，它指定了u 中每一对象x 的属性值。 通常知识表达系统也称为信息系统，通常也用s = ( u ，a ) 来代替 s = 。知识表达系统的数据以关系表的形式给出，关系表中的每一行 对应于要研究的对象，列则对应于对象的属性，对象的基本信息是通过指定对象 的各个属性的值来表达的。 下面给出一个例子，表2 1 用表格达标某些动物的特征的一知识表达系统。 表2 1 某些动物特征的知识表达系统 t a b l e 2 1k n o w l e d g ee x p r e s s i o ns y s t e mo fs o m ea n i m a l sc h a r a c t e r i s t i c s 物大小种类颜色 a 1 小熊黑 a 2 中熊黑 a 3 大狗棕 a 4 小猫 里 a 5中马 里 a 6 大马 里 a 7 大马棕 容易看出，一个属性对应一个等价关系，一个表可以看作是定义的一族等价 关系，即知识库。前面所讨论的知识约简就可以转化为属性约简。 决策表是一类特殊而重要的知识表达系统，它指当满足某些条件时，决策应 当怎样进行。多数决策问题都可以用决策表形式来表示，这一工具在决策应用中 起着重要的作用。 决策表可以根据知识表达系统定义如下： 定义2 5s = ( u ，a ) 为一知识表达系统，c ，dca 为两个属性子集，且 cud = a ，cna = 矽，c ，d 分别称为条件属性集和决策属性集，具有条件属性和 决策属性的知识表达系统称为决策表，记作t = ( u ，a ，c ，d ) ，或简称c d 决策 表。在决策表中，对于属性子集r a ，不可分辨关系i n d ( r ) 定义为：i n d ( r ) - - ( x ， y ) u u lr e r ，r ( x ) = r ( y ) ) 。显然，i n d ( r ) 是一个等价关系，x 在属性集r 上的 等价类 x i n d ( r ) 定义为：【x i n d ( r ) = y iy u ，yi n d ( r ) x ) 。 为方便起见，在不产生混淆的情况下用r 代替i n d ( r ) 。关系i n d ( c ) 和i n d ( d ) 的等价类分别称为条件类和决策类。 l o 第二章相关理论综述 定义2 6 信息系统中每一x i 及其所对应的属性值称为一个规则。在一个信息 系统中，当i j 时若存在f ( x i ，c ) = f ( x j ，c ) 但f ( x i ，d ) f ( x j ，d ) 则称该系统为不相容的， 此时x i 与x j 所对应的规则为不相容规则。 2 2 2 粗糙集 对于集合x ，一个对象x 是否属于集合x ，需要根据现有的知识来判断，可 分为三种情况，( 1 ) 对象x 肯定属于集合x ；( 2 ) 对象x 肯定不属于集合x ；( 3 ) 对象x 可能属于也可能不属于集合x 。 定义2 7 令x c _ u ，r 为u 上的一个等价关系。当x 能表达成某些r 基本范 畴的并时，称x 是r 可定义的；否则称x 为r 不可定义的。r 可定义集也称作r 精确集，而r 不可定义集也称为r 非精确集或r 粗糙集。为描述知识的粗糙程度， 粗糙集理论引入了近似集的概念，即粗集的上近似集( u p p e ra p p r o x i m a t i o n ) 和下 近似集( l o w e ra p p r o x i m a t i o n ) 来描述。 定义2 8 给定知识库k = ( u ，r ) ，对于每个子集x c _ u 和一个等价关系r i n d ( k ) ，定义两个子集： 星( x ) = u 】，u ri 】厂x r ( x ) = u i y c _ u g l r n x 矽 分别为的尺下近似集合和x 的尺上近似集合，称 为x 的r 粗糙集。对于x u 和给定的r ，若x r ( x ) ，则x 确定地属于z ，若x 萑r ( x ) 则 x 确定地不属于x ，若x r ( x ) r ( x ) ，则x 可能属于x ，也可能不属于x 。故 称r ( x ) 为x 的正域，u r ( x ) 为x 的负域，r ( x ) r ( x ) 为边界。 决策表可由其上的不可分辨关系生成一系列粗糙决策规则。设 q c ，x u q ，y u d ，定义q d u q xu d 为由q 到d 的粗糙规则集 合，有 q d x y o 。记q 旦乌d = qj dx y o 为 一致性规则集合。定义q d 的正域为： 广东t 业大学工学硕士学位论文 v o = u ( x u q ：了y u i d ， q 皇与刃，由此，可定义q d 的近似度 y = 长舛，其中，i i 表示集合包含的元素个数。 图2 - 1 清楚的表示出下近似和上近似以及边界域的概念。 p o s ( x ) 正区 2 2 3 属性约简 x 粗糙集 图2 1 粗糙集 在实际应用中，人们通常要考虑的一个重要问题是：信息系统中的各个属性 之间是否存在着某种依赖关系，即从一给定的知识中能否导出另一知识? 这就是 所谓的属性依赖问题。相应地，是否所有的属性及其取值在信息系统中均为必需? 能不能在保持原有信息系统分类能力的情况下，尽可能地消去冗余知识? 此类问 题为属性的约简问题。当了解一个论域中的样例的时候，我们可以通过知道其属 性值来对样例进行处理。但是在现实情况中，有时我们不知道一个样例的所有属 性值，只能根据部分属性值来进行判定；有时我们需要确定一个论域中是否每个 属性的重要程度是一样的，因为度量不同，属性值的代价可能不同。在专家系统 中，也会遇到类似的权重问题，重要性高的属性在作决策时被赋予大的权重。通 常我们只能根据经验来选择权重，这依赖于人的先验知识。 1 2 第二章相关理论综述 一、属性的依赖性 定义2 9 设有决策系统s = ( u ，cu d ，v ，f ) ，其中c ，d 分别表示条件属性和决 策属性，则决策属性在条件属性的正区域可定义为： p o s c ( d ) = uc ( x ) p o s c ( d ) 表明根据c 的知识所进行的划分u c ，能够确切地划入u d 类的对象 集合。 定义2 1 0 决策属性d 对条件属性c 的依赖度定义为： 拈咿) = 并 依赖度r c ( d ) 表示在条件属性c 下能够确切划入决策在u d 的对象占论域中 总对象的比率，表达了决策属性对条件属性的依赖程度，称决策属性d 是由条件 属性c 。度可导的( 0 k 1 ) ，记作c j 。d 。 当k = 1 时，称d 是c 完全可导的；当0 _ k - 1 时，称d 是c 部分可导的；当 k = 0 时，称d 是c 完全不可导的。如果cj 。d ，则也记为cjd 。 二、属性的重要性 针对某一具体问题，各属性的重要性是不同的。利用属性的依赖度可以定义 属性的重要程度。通常的做法是将某一属性a 从c 中去掉，看看它对由c 所产生 的正区域的影响程度。从定义2 1 0 可知，儿( d ) 表示决策属性d 和条件属性c 之 间的依赖程度，即用c 来描述u i n d ( d ) 的近似程度。因此可以通过a 从c 中除去 时，儿( d ) 的改变来衡量属性a 的重要性。 定义2 11 在决策系统s = ( u ，cud ，v ，f ) 中，a ec 的属性重要性定义为 如) = 幽焉艘小篙 可以将仃( c d ) ) 理解为属性a 被除去时，所发生的分类错误率。属性的重要 性也可以扩展到属性集p c c 的重要性度量。 定义2 1 2 在决策系统s = ( u ，cu d ，v ，f ) 中，p g c 的属性重要性定义为： 胁型意趔斗锗 三、约简与核 广东工业大学工学硕士学位论文 属性约简包括两个概念：约简和核。属性约简是指关系的最小不可省略子集， 而属性的核则是指最重要的关系集。 定义2 1 3 对于一给定的决策系统s = ( u ，c u d ，v ，厂) ，条件属性集合c 的约 简是c 的一个非空子集p 。它满足： ( 1 ) v a p ，a 都是d 不可省略的 ( 2 ) p o s p ( d ) 2 p o s c ( d ) 则称p 是c 的一个约简，c 中所有约简的集合记作r e d ( c ) 。 可以这样来理解，r 为论域中对象的属性集合，在近似表达中有一些属性的 特征作用不大，可以去掉它们而不影响对对象的表达，去除冗余属性后，剩余的 属性集仍然保持其等价关系。 2 2 4 决策规则 一个决策信息表系统一旦获得约简，就可以通过在约简属性集上的属性和其 属性值来构建规则。 一、决策规则和算法 定义2 1 4 蕴涵0 一妒称为决策逻辑语言中的决策规则，口和缈分别称为决策 规则的前件和后件。 定义2 1 5 形式化定义“，m ) 八( a 2 ，吃) 八瓴，) ，其中v ，锄，a 2 ，) e p ， 且pc _ a ，称为p 基本公式。 定义2 1 6 当口j 缈为一个决策规则，且p 和缈分别为c 基本公式和d 基本公 式，c ，dc a 时，则决策规则口一妒称为c d 基本决策规则，简称c d 规则。 定义2 1 7 当b 一伊，0 2 一缈，酿一伊均为基本决策规则时，决策规则 o lv0 2v v 吼专9 称为基本决策规则b 。妒，0 2jq o ，眈j 妒的组合， 简称为组合决策规则。 定义2 1 8 决策逻辑语言中任何有限决策规则集称为决策算法，而任