（计算机应用技术专业论文）基于粗糙集的知识约简算法研究及应用.pdf

江苏大学硕士学位论文 摘要 研究如何从大量的数据中智能地抽取出有价值的知识和信息，已成为当前人 工智能研究中非常活跃的研究领域。目前，知识发现面临着不能有效地处理不完 备、不确定性数据以及知识的可解释性比较差的问题。而作为集合论的扩展，粗 糙集理论是一种新的软计算方法，可以有效处理模糊的、不确定性知识。它不需 要先验知识和外界参数，近年来已经被成功地应用于人工智能、数据挖掘、模式 识别等诸多领域。因此，研究基于粗糙集的知识发现方法具有十分重要的意义。 本文对粗糙集的基本理论和概念进行了分析和研究，在这些基本理论的框架 下，主要做了以下几个方面的研究： ( 1 ) 粗糙集属性离散化 粗糙集的属性离散化要求：离散化结果要保持决策系统的不可分辨关系，以 此来确保系统的分类能力不变；求得最小数目的断点集。针对这两点要求，本文 首先介绍目前文献中已有的一些连续属性离散化的算法，并对其进行研究与分 析，得出这些算法在上述两方面或其他方面的不足；然后，针对这些不足，提出 了基于改进遗传算法的数据离散化算法；最后通过实例验证，该算法具有较好的 离散化效果。 ( 2 ) 粗糙集属性约简 针对传统的粗糙集属性约简算法效率不高，速度不快的问题，本文提出基于 条件信息熵和相关系数的属性约简算法，把决策表的非核属性约简过程转化为相 关系数的运算，能减少对决策表的扫描次数，降低算法时间复杂度，降低算法冗 余，提高属性约简的效率。并利用k f o l d 轮换对比方法计算相关系数，较大幅 度的减少了计算量，同时能得到次优属性约简结果。文中结合实验对算法的性能 进行了验证。 ( 3 ) 基于粗糙集的柴油机燃油喷射智能故障诊断系统 本文最后将对卡h 糙集的相关研究应用在故障诊断方面。在对柴油机及其燃油 喷射系统进行了介绍之后，基于本文提出的算法构造了柴油机燃油喷射智能故障 诊断系统，以帮助工作人员更好地完成故障诊断工作。 关键词：粗糙集，离散化，属性约简，遗传算法，柴油机燃油喷射，故障诊断 江苏大学硕士学位论文 a b s t r a c t t h e s t u d yo nh o w t oa u t o m a t i c a l l ye x t r a c tv a l u a b l ei n f o r m a t i o na n dk n o w l e d g e f r o ml a r g es c a l eo fd a t ah a sb e c o m ev e r ya c t i v er e s e a r c ha r e ai nc u r r e n ta r t i f i c i a l i n t e l l i g e n c er e s e a r c h n o w a d a y s ，k n o w l e d g ed i s c o v e r yi sf a c i n gt h ep r o b l e m st h a t i n c o m p l e t ea n du n c e r t a i nd a t ai sn o tp r o c e s s e de f f e c t i v e l ya n di n t e r p r e t a b i l i t yo f k n o w l e d g ei sw e a k a san e ws o f tc o m p u t i n gm e t h o d ，r o u g hs e tt h e o r yi st h e e x t e n s i o no fs e tt h e o r y , a n di ti se f f i c i e n ti np r o c e s s i n gi n c o m p l e t ea n du n c e r t a i nd a t a w i t h o u tk n o w i n gp r i o rk n o w l e d g ea n de x t e r n a l p a r a m e t e r s a n di t h a sb e e n s u c c e s s f u l l yu s e di na r e a so fa r t i f i c i a li n t e l l i g e n c e ，d a t am i n i n g ，p a t t e r nr e c o g n i t i o n ， a n ds oo n t h e r e f o r e ，t h er e s e a r c ho fk n o w l e d g ed i s c o v e r yt e c h n o l o g yb a s e do nr o u g h s e tt h e o r yi so fg r e a tp r a c t i c a ls i g n i f i c a n c e i nt h i sd i s s e r t a t i o n ，b a s i ct h e o r i e sa n dc o n c e p t i o n so fr o u g hs e ta r ea n a l y z e da n d s t u d i e d a n di nt h ef r a m e w o r ko ft h e m ，t h e s er e s e a r c h e sa r ed o n e ： ( 1 ) d i s c r e t i z a t i o no f c o n t i n u o u sa t t r i b u t e si nr o u g hs e t d i s c r e t i z a t i o no fc o n t i n u o u sa t t r i b u t e si nr o u g hs e tr e q u i r e s ：t h ei n d i s c e m i b i l i t y o fd e c i s i o ns y s t e mc a nn o tb ec h a n g e db yr e s u l t so fd i s c r e t i z a t i o ns oa st om a k es u r e t h a tc l a s s i f i c a t i o nc a p a c i t yo ft h ed e c i s i o ns y s t e mi sn o tg o i n gt oc h a n g e ；a n dt h e n u m b e ro fb r e a k p o i n t si nb r e a k p o i n t ss e ti sa ss m a l la sp o s s i b l e a i m i n ga tt h e s et w o r e q u e s t s ，f i r s t l ys o m ed i s c r e t i z a t i o na l g o r i t h m so fc o n t i n u o u sa t t r i b u t e sa r ei n t r o d u c e d ， a n dt h e ya r es t u d i e da n da n a l y z e dt oe x p o s et h e i rd e f i c i e n c i e so nt h ea b o v ea s p e c t so r o t h e ro n e s ；a f t e rt h a t ，a i m i n ga tt h e s ed e f i c i e n c i e s ，am e wd a t ad i s c r e t i z a t i o n a l g o r i t h mb a s e do na d v a n c e dg e n e t i ca l g o r i t h mi sp r o p o s e d ；a tl a s t ，e x p e r i m e n t sa r e c a r r i e do u tt op r o v ei t sp e r f o r m a n c e ( 2 ) a t t r i b u t er e d u c t i o ni nr o u g hs e t a i m i n ga tt h ep r o b l e mo fi n e f f i c i e n c ya n dl o wv e l o c i t yw i t ht h et r a d i t i o n a l a t t r i b u t er e d u c t i o na l g o r i t h m ，a na t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nc o n d i t i o n a l i n f o r m a t i o ne n t r o p ya n dc o r r e l a t i o nc o e f f i c i e n ti sp r o p o s e d ，w h i c hc h a n g e sa t t r i b u t e r e d u c t i o np r o c e s so fn o nc o r ea t t r i b u t e si nt h ed e c i s i o nt a b l ei n t oc a l c u l a t i o no f i i i 江苏大学硕士学位论文 c o r r e l a t i o n c o e f f i c i e n t ，a n d r e d u c e st h en u m b e ro f s c a n n i n g d e c i s i o nt a b l e ， a l g o r i t h m i ct i m ec o m p l e x i t ya n dr e d u n d a n c yo ft h ea l g o r i t h m ，a n di m p r o v e st h e e f f i c i e n c yo fa t t r i b u t er e d u c t i o n t h e nt h ek f o l dr o t a t i o nc o m p a r i s o nm e t h o di su s e d t oc a l c u l a t ec o r r e l a t i o nc o e f f i c i e n t ，w h i c hl a r g e l yr e d u c e sc a l c u l a t i o na m o u n t ，a n d a t t a i n ss u bo p t i m a la t t r i b u t er e d u c t i o nr e s u l t t h ea l g o r i t h md e t a i l sa r eg i v e na n da i l e x p e r i m e n ti sc a r r i e do u t ，t h er e s u l to fw h i c hv e r i f i e st h ee f f i c i e n c yo ft h ea l g o r i t h m ( 3 ) i n t e l l i g e n tf a u l td i a g n o s i ss y s t e mo ff u e li n j e c t i o ns y s t e mi nd i e s e le n g i n e s b a s e do nr o u g hs e tt h e o r y r e l a t i v er e s e a r c h e so nr o u g hs e tt h e o r yi nt h i sd i s s e r t a t i o na r eu s e di nf a u l t d i a g n o s i s a f t e rt h ei n t r o d u c t i o no fd i e s e le n g i n ea n di t sf u e li n j e c t i o ns y s t e m ， t h e o r e t i cb a s i so ff a u l t d i a g n o s i sb a s e do nr o u g hs e tt h e o r yi sa n a l y z e d ，a n da l l i n t e l l i g e n tf a u l td i a g n o s i ss y s t e mo ff u e li n j e c t i o ns y s t e mi nd i e s e le n g i n e sb a s e do n r o u g hs e tt h e o r yi se s t a b l i s h e dt oh e l pt h es t a f ff i n i s hf a u l td i a g n o s i sj o bb e t t e r k e y w o r d s ：r o u g hs e t ，d i s c r e t i z a t i o n ，a t t r i b u t er e d u c t i o n ，g e n e t i ca l g o r i t h m ，d i e s e l f u e li n j e c t i o n ，f a u l td i a g n o s i s i v 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密日。 学位论文作者签名：甄字崞翩签名：猫肜之 签字日期：咄年f 月户日 签字日期：咖年月7 日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容以外，本论文 不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名：雪压字穹 日期：纠年彳月1 0 日 江苏大学硕士学位论文 1 1 研究背景及意义 第1 章绪论 2 l 世纪是信息化社会的时代，计算机与网络信息技术飞速发展，这使得人 们在自然科学、社会科学和工程技术的各个领域获取的数据和信息急剧膨胀， 并且由于人的参与，数据与信息中的不确定性和不完备性更加显著，信息与数 据中的关系更加复杂。面对如此丰富的可利用数据与信息资源，研究人员一直 在努力寻找科学地处理不完整性和不确定性的有效途径。模糊集和基于概率 方法的证据理论是处理不确定信息的两种方法，己应用于一些实际领域，但 这些方法有时需要一些数据的附加信息或先验知识，而这些信息有时并不容 易得到。由此可见目前我们仍然缺乏有效的、能够利用计算机及信息技术来帮 助人类从海量信息中获取有用的信息和知识的方法。因此，处理这些模糊的、不 精确的、不完整的海量信息，从中获取潜在的、新颖的、正确的、有利用价值的 知识，是对智能信息处理提出的严峻挑战。 粗i 糙集理论和方法能有效的处理复杂系统中的数据和信息，已成为处理不精 确和模糊问题的新的数学方法，被应用于人工智能和认知领域，如机器学习、知 识发现、智能控制、决策规则的约简和自动分类、认识的格式以及学习算法等。 利用粗糙集方法进行知识获取的基本思想是在保持信息系统分类和决策能力不 变的前提下，通过属性约简和值约简，获得精简的规则库来帮助人们做出正确、 简洁的决策。本课题对基于粗糙集的属性约简算法和属性约简之前的预处理( 即 离散化) 算法进行了研究。 粗糙集理论无需提供除解决问题所需处理的数据集合之外的任何先验信息， 可以通过对数据的约简获得决策或分类规则。利用这一特点可在故障诊断中利用 基于粗糙集理论的方法对数据进行分析，得到合理的模式划分，最终形成对故障 的分类。 随着航空、航天、核工业、机器人等高技术领域和各种民用工业领域技术的 迅速发展，机械设备越来越复杂，自动化水平越来越高。机械设备在现代工业生 产中的作用越来越重要，设备在运行过程中如果发生故障，轻则造成一定程度的 江苏大学硕士学位论文 经济损失，重则导致灾难性的人员伤亡和恶劣的社会影响。而一系列设备故障所 造成的重大事故都充分说明提高系统和设备的可靠性与安全性具有十分重要的 现实意义。故障检测与诊断技术的出现和发展，为提高设备的可靠性与安全性开 辟了一条新的途径。 故障检测与诊断技术是一门相对独立发展的技术，同时又是一门应用型边缘 学科，它起源于2 0 世纪中叶，其理论基础涉及现代控制理论、可靠性理论、信 号处理、模式识别、计算机工程、人工智能、电子技术、应用数学等学科，与容 错控制、鲁棒控制、自适应控制、智能控制等有密切的联系。 按照国际故障诊断权威德国的p m f r a n k 教授的观点，现有的故障诊断 方法分为：( 1 ) 基于动态数学模型的方法、( 2 ) 基于信号处理的方法和( 3 ) 基 于知识的方法。 ( 1 ) 基于动态数学模型的故障诊断方法是最早发展起来的瞳，3 i ，它需要建立 被诊断对象的较为精确的数学模型。所谓基于动态数学模型的故障诊断方法，就 是通过将被诊断对象的可测信息和由模型表达的系统先验信息进行比较，从而产 生残差，并对残差进行分析、处理，从而实现故障诊断的方法。基于动态数学模 型的故障诊断方法对于建模误差、参数摄动、噪声和干扰十分敏感，对于复杂非 线性系统的诊断显得无能为力。某些情况下，系统的数学模型难以建立，或者建 立一个精确的数学模型需要花费太大的代价，但是系统各个部位的信号比较容易 检测到，这时常会用到基于信号的故障诊断技术。 ( 2 ) 基于信号处理的故障诊断方法在故障状念识别中占有重要地位。复杂 系统内部发生的各种故障最终体现在其输出测量信号的异常变化上，因此通过对 测量的信号进行分析处理可以提取故障信息。通常利用信号处理，如相关函数、 频谱、自回归滑动平均等方法，直接分析可测信号，提取如方差、幅值、频率等 特征，从而进行故障检测。近年来出现了多种基于信号处理的方法，如主元分析 法1 、小波变换瞄1 等。基于信号处理的故障诊断的对象较为单一，通用性较差， 且对于隐蔽性强的故障无能为力，对故障产生的原因不能很好的解释，同样存在 着许多实际缺陷。 ( 3 ) 基于知识的故障诊断方法无需系统的定量数学模型，充分利用了专家 诊断知识和诊断对象的信息，特别适合于非线性系统和复杂的大型系统。该方法 2 江苏大学硕士学位论文 的内容最为丰富，也最有生命力。它的发展大致经历了两个阶段阳1 ：基于浅知识 ( 人类专家的经验知识) 的第一代故障诊断系统和基于深知识( 诊断对象的模型、 统计知识) 的第二代故障诊断系统。近期出现的混合结构的知识诊断系统，是将 上述两种方法综合使用，互补不足，相得益彰。它可分为基于症状的方法和基于 定性模型的方法。主要的方法有专家系统、模糊推理口1 、模式识别、神经网络碑1 、 多元统计方法、案例推理、基于定性模型的方法、灰色系统理论方法、p e t r i 网 方法、数据融合故障诊断方法( 含b a y e s 推理、a n n 网络、d s 证据理论方法等) 、 基于a g e n t 的故障诊断方法和故障树方法等。基于粗糙集理论的故障诊断方法便 是基于知识的故障诊断方法中的一种。 相比较于方法( 1 ) ，方法( 3 ) 无需系统的定量数学模型；相比较于方法( 2 ) ， 方法( 3 ) 可以处理更多故障信息( 例如用自然语言描述的信息) 。随着实际系统 的复杂性日益增加，基于知识的故障诊断方法已得到了广泛的关注和应用，然而 这些方法各有其优缺点。目前大多数基于知识的诊断方法均面临着一些固有的困 难或“瓶颈”，主要有：需要对测量到的故障特征数据进一步简化处理；故障珍 断知识难以获取；需要人工或专家经验的介入；对不完备的故障模式难以处理等， 其中故障特征的简化选择和诊断知识的提取是比较突出的两个问题。例如复杂机 械电子工程系统的故障诊断中，系统的特征信号( 如振动、噪声、频率等) 和运行 参数( 如压力、温度、电压、电流等) 很多，都能反映系统的运行状态。获得这些 信号和参数数据后，如何进行特征量的提取或简化，剔除不需要的特征量，从而 减少诊断信息融合过程的计算工作量? 同时由这些参数融合后形成的故障模式 往往是冗余的，有时甚至是相互矛盾的，那么，如何对这些模式数据进行简化， 提取出尽可能少而有效的规则诊断出系统真实的运行状态? 已有的技术很难得 到令人满意的结果，而且许多方法具有很大的经验性。粗糙集理论对这些问题的 解决提供了一种新的途径，它不需要任何先验信息和系统的数学模型，能有效地 分析和处理不精确、不一致、不完整等不完备性数据，通过发现数据l 日j 隐藏的关 系，揭示潜在的规律，从而提取有用信息，简化信息处理。利用该理论能够剔除 大量故障特征参数中具有冗余信息的特征，简化特征量的个数，同时又可以提取 出有效的故障模式规则，为系统的故障诊断提供了很大的便利。 江苏大学硕士学位论文 1 2 粗糙集的发展和研究现状 1 9 8 2 年，z p a w l a k 发表经典论文r o u g hs e t s 阻1 ，宣告了粗糙集理论的诞生。 这是一种新型的处理具有模糊性和不确定性的知识的数学工具，而且作为一种新 的知识获取方法，粗糙集理论能有效地分析不精确、不一致、不完全的各种信息。 粗糙集理论具有它的独特性，这是建立在分类机制的基础上的，其主要思想足利 用已知的知识库，将不精确或不确定的知识用已知的知识库中的知识来近似地刻 画。粗糙集理论与其他处理不确定和不精确问题的方法的区别是它无需提供解决 所需处理的数据集合之外的任何先验信息，对问题的不确定性的描述和处理比较 客观。 到了八十年代末，粗糙集理论引起了各国学术界的重视，许多数学家、逻辑 学家和计算机研究人员对粗糙集理论和应用产生了极大兴趣并做了大量研究工 作。特别是近十几年来，由于它在机器学习与知识发现、数据挖掘、决策支持与 分析等方面的广泛、成功的应用而成为当前计算机、人工智能、信息科学等领域 的研究热点之一。 1 9 9 1 年，z p a w l a k 教授的第一本关于粗糙集的专著r o u g hs e t s ： t h e o r e ti c a la s p e c t so fr e a s o n i n ga b o u td a t a n 训和1 9 9 2 年s l o w i n s k ir 主编的关于拳f i 糙集应用及其相关方法比较研究的论文集1 的出版，推动了国际上 对粗糙集理论与应用的深入研究。同年，第一届关于粗糙集理论的国际学术会议 在波兰召开，极大地推动了国际上对粗糙集理论与应用的深入研究。1 9 9 3 年在 加拿大召开了第二届国际粗糙集与知识发现研讨会，这次会议对推动国际上对粗 糙集应用的研究起到了非常积极的作用。1 9 9 5 年，a c mc o m m u n i c a t i o n 将其列 为新浮现的计算机科学的研究课题。1 9 9 6 年在日本召开了亚洲第一次粗糙集理 论大会。此后，广大中国学者积极投入到粗糙集理论的研究之中。目前，粗糙集 理论与知识发现也成为国内的研究热点，为此还形成了若干专门的研究机构。 2 0 0 0 年，在重庆召开了国内第一次粗糙集理论国际研讨大会。2 0 0 8 年5 月在中 国成都成功举办了第3 届粗糙集与知识获取国际会议。这些都大大加速了粗糙集 理论的交流与发展。 近几年来，粗糙集理论已被广泛地应用于机器学习、知识发现、决策支持与 分析、专家系统、智能控制、模式识别等领域。目前国际上已经开发出了一些基 4 江苏大学硕士学位论文 于粗糙集理论的k d d ( 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 ) 系统：( 1 ) 基于 粗糙集理论的学习系统l e r s u 刳( l e a r n i n gf r o me x a m p l e sb a s e do nr o u g hs e t ) 。 该系统由美国k a n s a s 大学开发，能够从大量经验数据中抽取规则，可以作为专 家系统的丌发工具。l e r s 在美国国家航空航天管理局( n a s a ) 的j o h n s o n 空间中 心应用多年，为“自由号”空问站提供医疗决策服务；l e r s 还应用于美国环境 保护署( u se n v i r o n m e n t a lp r o t e c t i o na g e n c y ) 资助的研究全球气候变化项目。 ( 2 ) r o s e t t a 。r o s e t t a 软件3 1 是一个粗糙集理论应用工具箱，由a l e k s a n d e ro h r n 博士在完成其博士论文期间开发。其计算内核的设计、界面的设计和开发在 n o r w e g i a nu n i v e r s it yo fs c i e n c ea n dt e c h n o l o g y 大学计算与信息科学系的 知识系统组( k n o w l e d g es y s t e m sg r o u p ) 完成；其部分计算内核( r s e s 早期版本) 的丌发则在波兰华沙大学( u n iv e r s it yo fw a r s a w ) 数学学院的逻辑组( g r o u po f l o g i c ) 完成。这两个项目组都以粗糙集理论研究而闻名。( 3 ) r s e s ( r o u g hs e t s e x p l o r a t i o ns y s t e m ) 。r s e s 钊是波兰华沙大学( u n i v e r s i t yo fw a r s a w ) 数学学 院逻辑组( g r o u po fl o g i c ) 开发的粗糙集理论工具箱。其开发始于1 9 9 4 年，开 发语言为c + + ；r s e s 包括用户界面和内核两部分，内核最新版本为r s e s2 0 。 r s e s 可以实现籽l 糙集理论计算的各个步骤。 目前，粗糙集的理论研究主要集中在数学性质、模型拓展、有效性算法及与 其它多种不确定智能分析方法的融合等方面。其中，在基于粗糙集的约简和分类 算法方面的研究取得了一些成果n 瓢1 6 1 ”：k h o o 提出了一个新方法，用于不连续 信息系统中的分类和规则抽取n 引，通过把基于统计的诱发学习算法和粗糙集理论 整合在一起来达到这个目的；还提出了基于粗糙集的原型分类系统( r - c l a s s ) 的框架。b a k e r 为寻找最小规模约筒而提出一个算法，这个算法基于粗糙集理论 和一个专门的决策相关的二进制整数规划( b i p ) 算法n 引，把从决策系统得到的 等价类转换为一个b i p 模型。h u 提出一个新方法，使用粗糙集理论和数据库操 作来构建一组优秀的分类器啪1 。q u e s t i e r 利用粗糙集理论构建约简，在受监督 的情况下约简不受监督的聚类中的特征比，该特征选择算法还与聚类算法组合在 一起。t h a n g a v e l 和p e t h a l a k s h m i 提出了一个加速的快速约简算法，从决策系 统中选择特征乜引，随后用c 4 5 进行规则抽耿，并与原有的快速约简算法进行了 对比研究。实验在u c i 机器学习知识库的公共领域数据集上进行，并利用实验结 江苏大学硕士学位论文 果分析了算法性能。从性能分析明显得出，加速快速约简生成最小约简，通过 c 4 5 算法抽取的规则显示对加速约简的性能很优秀。 总的来说，在从信息系统产生决策的规则生成过程中，约简扮演着至关重要 的角色。约简过程选择原属性集的属性子集，其目的足找出有鼋要意义的属性， 去除不相关的可有可无的属性并建立一个优秀的学习模型。约简的好处有两个： 极大的减少了诱发算法的计算时间，同时增加了导出模! 型的准确性。本文对于知 识约简算法的研究正是粗糙集领域中非常重要的课题。 1 3 论文内容及章节安排 粗糙集理论在处理不确定和不精确问题方面有无与伦比的优势，但同时也存 在着局限性。传统的粗糙集理论对处理的数据的离散化程度有着较高要求，无法 处理连续型数据和离散化程度不够的离散数据，而实际的数据库中大多同时包含 离散数据和连续数据。故本文首先对数据离散化算法进行了研究。 数据离散化是数据预处理过程中的重要组成部分，优秀的数据离散化算法可 以在减小数据规模的同时，还对数据进行净化，进而提高后续属性约简算法的效 率，降低属性约简算法的复杂度。为达到上述目的，本文首先提出了一种基于改 进的遗传算法的数据离散化算法( d i s c r e t i z a t i o na l g o r i t h mb a s e do na d v a n c e d g e n e t i ca l g o r i t h m ，简称d a b a g a 算法) 。 接下来，在属性约简方面，针对传统的粗糙集属性约简算法效率不高，速度 不快的问题，本文提出基于条件信息熵和相关系数的属性约简算法( a t t r i b u t e r e d u c t i o na l g o r i t h mb a s e do nc 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 ya n dr e l a t i o n c o e f f i c i e n t ，简称a r a b c r 算法) ，在利用基于条件信息熵的算法得到核属性后， 把决策表的非核属性约简过程转化为相关系数的运算，能减少对决策表的扫描次 数，降低a r a b c r 算法的时间复杂度和冗余，提高属性约简的效率。并利用k f o l d 轮换对比方法计算相关系数，较大的减少了计算量，同时能得到次优属性约简结 果。 最后把本文关于粗糙集理论的研究应用到故障诊断中，利用基于粗糙集理论 的的知识获取方法，抽取出故障诊断的规则，设计一个基于粗糙集的柴油机燃油 喷射智能故障诊断系统。 6 江苏大学硕士学位论文 本文余下章节的内容安排如下： 第2 章粗糙集理论基础知识 介绍了粗糙集理论的基础知识，如知识表达系统、上近似集、下近似集、粗 糙集、知识的依赖、知识约简和核等相关知识。 第3 章数据离散化 首先研究分析当前几种典型的离散化方法，然后针对这些算法的不足，提出 一种基于改进的遗传算法的数据离散化方法。 第4 章属性约简 针对传统的料l 糙集属性约简算法效率不高，速度不快的问题，提出基于相关 系数和条件信息熵的属性约简算法。 第5 章基于粗糙集的智能故障诊断系统 在前面算法研究的基础上，设计一个基于粗糙集的柴油机燃油喷射智能故障 诊断系统。 第6 章结束语 对全文进行总结，提出下一步的工作与展望。 7 江苏大学硕士学位论文 第2 章粗糙集理论基础 作为面向人类认识知识的数学学科，粗糙集理论认为知识是人类对对象进行 分类的能力，不可分辨关系是粗糙集理论中的最基本概念。在此基础上，粗糙集 理论引入上近似和下近似等概念来刻画知识的不确定性和模糊性；引入约简和求 核来进行知识的化简等计算。本章主要介绍知识约简中经常用到的一些基本概念 和理论，为后面章节对知识约简算法的介绍和研究做好铺垫。 2 1 知识表达和信息系统 2 1 1 知识表达 给定一个感兴趣的对象论域u ，对于任何子集x u 可称之为u 中的概念或 范畴，它们构成了特定论域u 的分类。 其中，x ，互u ，x ，o ，x fnx ，= 囝，当f j ，f ，j = l ，2 ，n ；且u x j = u 。 知识系统通常处理的是u 上的分类族。一个u 上的分类族，定义为一个u 上的 知识库；这样，知识库就是表达一个智能系统的各种基本分类方式的集合。常用 等价关系代管分类，因为这两个概念完全可以互相代替盯1 。 若r 是u 上的划分r = x 。，x ：，x 。) 表达的等价关系，( u ，r ) 称为近似 空间，u r 是r ( 或u 的分类) 的所有等价类族。用【x 】r 表示子集x 属于r 的一 个范畴，且r 包含元素x u 。 这样，一个知识库就可以表达为k = ( u ，r ) ，u r 中的集合称为基本概念、 初等范畴或者知识模块。 2 1 2 信息系统 为了处理智能数据，需要知识的符号表达，信息系统的基本成分是研究对象 的集合，关于这些对象的知识是通过指定对象的基本特征( 属性和属性值) 来描 述的。 一个知识表达系统阳1 s 可以表达为四元组s = ( u ，q ，v ，f ) 。其中，u 是对 8 江苏大学硕士学位论文 象的非空有限集合；q = cud 是属性集合，子集c 和d 分别称为条件属性集和 决策属性集；v = u 。屹是属性值的集合，v an # , t n 性口q 取值的范围； f ：u x q 。v 是一个信息函数，它指定u 中每一对象x 的属性值。 在粗糙集理论中，矢n t t , j , 表达系统又称为信息系统，可以表示成信息表的形式。 信息表的列表示属性，行表示对象，每个单元格表示对象的属性值。容易得知， 一个属性对应一个等价关系，一个信息表可以看作是对一族等价关系的定义，即 知识库。 2 2 决策系统 决策系统是一类特殊而重要的知识表达系统口引，它是指当满足某些条件属性 时，决策属性就获得相应的属性值。多数决策问题都可以用决策系统形式来表达。 决策系统可根据知识表达系统定义如下： 定义2 1 决策表是一个信息表知识表达系统s = ( u ，q ，v ，f ) ，其中u 是 对象集合，即论域；v = u ，v g 是属性q 的值域；其属性集q 2 c ud ，c 为 q e q 条件属性集，d 为决策属性集，d f 2 j ，对于v ，则j 圪) ，使得f ( x ， k ) ) = 。 决策表中也可能存在一定的不确定信息，决策表中所包含的不确定性主要是 指决策表中包含冲突( 矛盾) 样本的情况，即两个样本的条件属性值相同而决策 ( 分类) 属性值不同乜制。我们把这种含有冲突记录的决策表叫做不相容决策表。 这种不一致的产生，主要有3 种可能： ( 1 ) 条件属性不充分，根据所采用的条件属性不能对样本进行正确分类， 必须增加额外的条件属性才能够_ f 确区分样本； ( 2 ) 样本属性值的测量或记录不准确； ( 3 ) 在决策表的预处理过程中产生了冲突( 如在离散化过程中可能会产生 不精确的样本从而产生冲突) 。 9 江苏大学硕士学位论文 2 3 粗糙集 集合是由g e o r g c a n i o r 于1 8 8 3 年提出的，他是整个近代数学的基础性概念。 集合是由其中的元素来定义的，一旦集合中的全部元素都唯一确定，则集合本身 也就确定了。集合在数学中的定义是明确的，否则就不可能证明任何数学定理 1 0 2 5 】 o 粗糙集理论延拓了经典集合论，把用于分类的知识引入集合内，作为集合组 成的一部分。一个对象a 是否属于集合x ，需要根据拥有的关于论域的知识来做 出判断，可分为三种情况： ( 1 ) 对象a 肯定属于集合x ； ( 2 ) 对象a 肯定不属于集合x ； ( 3 ) 对象a 可能属于集合x ，也可能不属于集合x 。 因此，集合划分依赖于所掌握的关于论域的知识，是相对的而不是绝对的。 给定论域u ，等价关系r 将u 划分为互不相交的基本等价类u r 。设x 是论域u 上的一个集合，如果x 能表示成等价类组成的并集时，则称x 在u 上是r 可定义 的，否则x 为r 不可定义的。r 可定义是指可以在知识库k = ( u ，r ) 中被精确定 义；r 不可定义则不可能在这个知识库中被定义，只能通过近似的方法来刻化。 r 可定义集也称作r 精确集；对应地，r 不可定义集也可称为r 非精确集或者粗 糙集。 2 4 近似集 对于粗糙集，我们可以使用两个精确集合上、下近似集心3 1 来加以描述： 定义2 2 给定信息系统( 知识表达系统) s = ( u ，q ，v ，f ) ，对于每个子 集x u 和等价关系r ，x 的上近似集和下近似集分别可以由r 的基本定义如下： r 一( x ) = u y o rl y cx ) ( 2 1 ) i r ( x ) = u y u rf y n x ( 2 2 ) 上近似集和下近似集的概念也可以通过集合来定义： r 一( x ) = u x ui x 。x ) ( 2 3 ) r 一( x ) = u x u | x 。1 7 x 中 ( 2 4 ) l o 江苏大学硕士学位论文 定义2 3 一个集合x cu 的上、下近似集，将论域u 划分为三个不相较的 区域：正域( p o s ( x ) ) 、负域( n e g ( x ) ) 与边界域( b n d ( x ) ) 可定义如下： p o s ( x ) = r ( x ) ( 2 5 ) n e g ( x ) = u r 一( x ) ( 2 6 ) b n d ( x ) = r 一( x ) - - r ( x ) ( 2 7 ) 图2 1 表示一个集合x 的上、下近似集以及正、负域与边界域，其中每一个 小矩形表示一个等价类。 2 5 不可分辨关系 图2 1 粗糙集概念示意图 分类过程中，相差不大的个体被归于同一类，它们之间的关系就是不可分辨 关系。假定只用两种黑白颜色把空间中的物体分割为两类， 黑色物体 ， 白色 物体 ，那么同为黑色的两个物体就是不可分辨的，因为描述它们特征属性的信 息相同，都是黑色。如果再引入方、圆的属性，又可以将物体进一步分割为四类： 黑色方物体) ， 黑色圆物体 ， 白色方物体) ， 白色圆物体 。这时，如果两个 同为黑色方物体，则它们还是不可分辨的。不可分辨关系瞳3 1 也称为等效关系，两 个白色圆物体问的不可分辨关系可以理解为它们在白，圆两种属性下是等效的。 若集合u 上的二元关系r 是自反的、对称的和传递的，则称r 是等价关 系。设r 是u 上的一个等价关系集合，则u r 表示r 的所有等价类( 或u 上的 江苏大学硕士学位论文 划分) 构成的集合， x 。表示包含元素x u 的r 等价类，即 x 。中每一个对象 都与x 具有相同的特征属性。一个知识库就是一个关系系统k = ( u ，r ) ，其中u 为论域，r 是u 上的一簇等价关系。 如果u 上的两个元素x 和y 属于同一个等价类，则称x 和y 是不可分辨的。 由此可定义不可分辨关系如下： 定义2 4 在信息系统s = ( u ，q ，v ，f ) 中，对于每个属性子集b c _ q ， 定义一个不可分辨二元关系i n d ( b ) ，即： i n d ( b ) = ( x ，y ) l ( x ，y ) u 2 ：vb b ，f ( x ，b ) = f ( y ，b ) ； ( 2 8 ) 2 6 知识约简 对于一个给定的论域，能否使用较少的知识表达同样的概念，即知识库中是 否有些部分的知识足冗余的，是否可以通过其他知识或知识的组合来等价的表 示，这个问题涉及到知识的化简，在粗糙集理论中可以归结为从知识库中除去一 些冗余的等价关系，同时维持原有知识库的不可分辨关系n 仉剐。 定义2 5给定知识库k = ( u ，r ) 和u 的分类u n ，r r ，如果 i n d ( r ) = i n d ( r 一 r ) ，则称r 为r 中冗余的，否则r 为r 中非冗余的。 这个概念与分类相联系，可以这样理解，r 是论域中对象的属性集合，去除 冗余属性r 后，剩下的属性集r r 仍然保持原来的等价关系。 若vr r ，r 非冗余，则称族r 为独立的。如果r 是独立的，p _ cr ，则p 也 是独立的。在用属性集r 表达论域知识时，r 独立意味着属性集罩的每一个属性 都是必不可少的，可以独立的表达一组知识分类。 定义2 6 设u 是一个论域，r 是定义在u 上的一个等价关系，且r r 。如 果v r r 都为p 中绝对必要的，则称r 为独立的；否则称r 为相互依赖的。 对于相互依赖的关系族，其中包含有冗余关系，可以对其进行约简；而对于 独立的关系族，去掉其中任何一个关系都将破坏知识库的分类能力。 定义2 7当q 独立，o _ cp 且i n d ( q ) = i n d ( p ) ，则q 为p 的约简，用r e d ( p ) 表示。 约简q 是能够与p 表达同样的知识的最小等价关系集合，是p 中的重要部分。 虽然q 去除了部分多余的知识，仍然取得与原来的完整知识库一样的分类结果。 1 2 江苏大学硕士学位论文 定义2 8 若s 为p 的q 独立子族，且p o s s ( q ) ：p o s p ( q ) s ，呗0 族s p 称为q 相对于p 的约简。 当必须利用整个知识p 来划分对象到q 的初等范畴时，知识p 为相对于q 独 立的。 定义2 9 一组等价关系p 可能有多个约简，全部约简的交集定义为p 的核 ( c o r e ) ，记作c o r e ( p ) 。 c o r e ( p ) = n r e d ( p ) ( 2 9 ) c o r e ( p ) 含有p 的全部约简中共同的等价关系，是知 j 库p 中算的必不可少 的重要属性集，核的概念有