（管理科学与工程专业论文）基于遗传算法的粗糙集属性约简研究.pdf

基于遗传算法的粗糙集属性约简研究 摘要 粗糙集理论是继概率论、模糊集理论、证据理论之后的又一个处理含糊性 和不确定性的数学工具。属性约简算法是粗糙集理论的核心内容。粗糙集属性 约简的研究在知识获取、机器学习、模式识别、决策分析、模型建立等实际应 用中有重要的意义；但是，由于属性约简被证明是一个n p h a r d 问题，因此， 研究更为有效的属性约简算法，有效地获取较优的属性约简，降低算法的时间 复杂度，寻求快速的约简算法仍是粗糙集理论的主要研究课题之一。本文对基 于遗传算法的粗糙集属性约简算法进行了研究。 本文首先介绍了粗糙集理论的基本概念和遗传算法的相关知识。对粗糙集 理论中基于区分矩阵、属性重要度、属性依赖度的属性约简算法以及启发式遗 传约简算法进行了系统综述，并且对各种算法进行了比较分析。 在对粗糙集理论和遗传算法的研究基础上，通过分析比较现有的遗传约简 算法，吸收算法的优点，并且加以改进，提出了一种基于属性依赖度的遗传约 简算法的改进算法。本算法的主要特点在于：一是在适应度函数中引入了决策 属性对条件属性的依赖度，使算法在加强局部搜索能力的同时保持了该算法全 局寻优的特性，也保证了所求约简既含较少的属性又保证分类质量，能够获得 最佳的搜索效果。二是对传统遗传算法中随机产生的二进制初始种群加以改进， 用属性核加以限制，以增强遗传算法的局部搜索能力，缩短算法的计算时间， 并提高决策表属性约简结果的准确性。三是在遗传算法的遗传算子的基础上， 新算法进行了局部优化策略，增加了修正校验算子，采用了基于属性依赖度的 重要度修正策略，使得算法在局部空间能够得到一个较优解，保证遗传算法的 全局搜索在有效的可行解空间进行。该算法通过数据实验分析，证明是求解知 识约简问题的快速有效方法。 关键词：粗糙集理论：遗传算法；属性约简；属性依赖度；遗传属性约简 r o u g h s e ta 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 ng e n e t i c a l g o r i t h m a b s t r a c t r o u g hs e tt h e o r yh a sb e e np r o v e dt ob ea ne x c e l l e n tm a t h e m a t i c a lt o o ld e a l i n g 、 ，i t hu n c e r t a i na n dv a g u ed e s c r i p t i o no fo b j e c t sa f t e rv a g u et h e o r ya n de v i d e n c e t h e o r y f i n d i n gt h em i n i m a lr e d u c t i o ni so n eo ft h em o s ti m p o r t a n tw o r k si nt h e r e s e a r c ho fr o u g hs e tt h e o r y , a sa ni m p o r t a n tp a r to fs o f tc o m p u t i n g ，a t t r i b u t e r e d u c t i o np l a y sa p p l i c a t i o n sh a v ep l a y e da ni m p o r t a n tr o l e ，e s p e c i a l l yi nt h ea r e a s o fk n o w l e d g ea c q u i s i t i o n ，m a c h i n el e a n i n g ，p a t t e r nr e c o g n i t i o n ，d e c i s i o na n a l y s i s a n dm o d e l i n ge t c h o w e v e r , i th a sb e e np r o v e dt h a tf i n d i n gt h em i n i m a lr e d u c t i o n s i san p - h a r dp r o b l e m t h et h e s i ss t u d i e so nt h er o u g hs e ta t t r i b u t er e d u c t i o n a l g o r i t h mb a s e do ng e n e t i ca l g o r i t h m f i r s t l y , t h et h e s i sr e v i e w st h et h e o r i e sa n dm e t h o d so fr o u g hs e ta n dg e n e t i c a l g o r i t h ms y s t e m a t i c a l l y , a n da n a l y z e st h ea 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 nb a s e d o nd i s c e r n i b i l i t ym a t r i x ，a t t r i b u t es i g n i f i c a n c e ，d e p e n d a b i l i t ya n dg a t h e n ，b a s e do nt h ec h a r a c t e r i s t i co fr o u g hs e tt h e o r y , g e n e t i ca l g o r i t h ma sw e l l a sd e c i s i o nt a b l ea t t r i b u t er e d u c t i o n ，t h r o u g ha n a l y s i so ft h ee x i s t i n gp r i m a r y a l g o r i t h mo fa t t r i b u t er e d u c t i o nb a s e do nt h et r a d i t i o n a lg e n e t i ca l g o r i t h m ，a n i m p r o v e da l g o r i t h mo fr o u g hs e ta t t r i b u t er e d u c t i o nb a s e do nd e p e n d a b i l i t ya n d g e n e t i ca l g o r i t h mi sp r e s e n t e di nt h i st h e s i s t h e r ea r et h r e ec h a r a c t e r so ft h e a l g o r i t h m t h ef i r s to n ei st h a td e f i n et h ef i t n e s sf u n c t i o ni nt h ea l g o r i t h mb yt h e d e p e n d a b i l i t yo fa t t r i b u t e ，i no r d e rt od e c r e a s et h et i m ea n ds p a c ec o m p l e x i t y r e s p e c t i v e l y t h es e c o n do n ei s t h a tu s e sa t t r i b u t ec o r eo fd e c i s i o nt a b l ea sa r e s t r i c t i o nt o i m p r o v e t h eb i n a r yc o d ei n i t i a l p o p u l a t i o nw h i c h i sp r o d u c e d s t o c h a s t i c a l l yi nt h ep r i m a r yg e n e t i ca l g o r i t h m t h i si m p r o v e m e n tc a ns h o r t e nt h e c a l c u l a t i o nt i m eo ft h ea l g o r i t h ma n dr a i s et h ea c c u r a c yo ft h er e s u l t so ft h e a t t r i b u t er e d u c t i o n t h et h i r do n ei st h a ta d d sac o r r e c t i o no p e r a t o r i nt h i so p e r a t o r , t h ea l g o r i t h mu s e sa t t r i b u t es i g n i f i c a n c ea sh e u r i s t i ci n f o r m a t i o nw h i c hc a ng u i d e t h ea l g o r i t h mc a r r y i n go u ti nt h es p a c eo ff e a s i b l er e s u l t s ，a n dt h ea t t r i b u t e sw h i c h c a nm a k em o r ei m p o r t a n ti n f l u e n c ea r ep r e v e n t e dt ob el o s t l a s t ，a ne x p e r i m e n ti s s h o w nt op r o v et h a tt h ei m p r o v e da l g o r i t h mi sm o r ee x c e l l e n c et h a ns o m eo t h e r a 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 d0 ng e n e t i ca l g o r i t h m ，a n di ti sm o r ea c c u r a t e a n de f f i c i e n tt os o l v et h ep r o b l e mo fa t t r i b u t er e d u c t i o ni nd e c i s i o nt a b l e k e y w o r d s ：r o u g hs e t ；g e n e t i ca l g o r i t h m ；a t t r i b u t er e d u c t i o n ；d e p e n d a b i l i t yo f a t t r i b u t e ；a t t r i b u t er e d u c t i o nb a s e do ng a i i 图表清单 囤2 。l 典型的遗传算法运算过程示意图1 4 图4 i 局部优化策略流程图2 9 图4 2 遗传约简算法的流程图3 l 表4 1c t r 数据表l 3 3 表4 2c t r 数据表2 3 4 表4 3c t r 数据实验结果3 5 表4 4 经过遗传属性约简的c t r 表。3 5 表4 5 实验结果比较l 一3 6 表4 6 实验结果比较2 3 6 v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获褥金口墨王业太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字； 榔期：夕年埘日 学位论文版权使用授权书 本学位论文作者完全了解盒胆兰些盔堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阗。本人授权 金a 墨兰些 塞堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名： 搠期：夕年6 月妇 学位论文作者毕业后去向： 工作单位： 通讯地址： 一名；壶吖嘲 签字日期：。7 年6 月f 日 电话： 邮编： 致谢 本篇论文是在我的导师刘业政教授的悉心指导下完成的。三年以来，刘老 师在学业上一直对我严格要求，生活上给予我无微不至的关怀。我所取得的每 一点进步、每一点成绩都离不开刘老师的谆谆教诲。刘老师严谨的治学作风、 勤勉的工作方式、诲人不倦的教学态度以及广博的知识，都让我受益匪浅。值 此论文完成之际，我谨向导师刘业政教授表示最诚挚的感谢，并致以深深的敬 意。 感谢合肥工业大学管理学院和研究生院领导、老师们对我的关心和帮助。 感谢合肥工业大学电子商务研究所为本人提供的研究条件，感谢杨善林、赵慧 芳、梁昌勇、刘心报、倪志伟、李兴国、何建民、左春荣、张结魁、赵勇和魏 婧等老师对我的关心、指导和帮助。 感谢电子商务研究所的林文龙、王华娴、杨慧、姜元春、徐德鹏、王卫、 杨洁琼、马向辉、焦宁、钟扬、郑蕊、唐亮、徐建华、谢珩、余智学、鲁建敏 等师兄师姐、师弟师妹对我研究工作的指导帮助和生活上的支持鼓励，同时感 谢与我相处七年的同学们，他们在我的学习和生活中给予了极大的关怀和帮助， 在此向他们致以诚挚的谢意l 衷心感谢对本论文进行评审、提出宝贵意见的各位专家。 在此也向我的父母及家人表示深深的感激，感谢他们含辛茹苦的养育之恩， 感谢他们一直以来对我的支持、理解和关爱。 最后，感谢所有关心和帮助过我的人们。 i i l 作者：郭春根 2 0 0 7 年5 月 l - 1 问题的提出 第一章绪论 粗糙集理论是继概率论、模糊集理论、证据理论之后的又一个处理含糊性 和不确定性的数学工具。其主要思想就是在保持分类能力不变的前提下，通过 知识约简，导出问题的决策或分类规则。该理论不需要任何附加的信息或先验 知识，就能有效地分析和处理不精确、不完整和不一致的数据，并从中发现隐 含的知识，揭示潜在的规律。粗糙集理论的主要优势在于它不需要关于数据的 任何预备的或额外的信息。粗糙集理论已经在很多领域如数据挖掘、机器学习、 模式识别、决策分析和过程控制等取得了成功的应用。 粗糙集理论的要点是将分类与知识联系在一起，使用等价关系来形式化地 表示知识分类，知识被视为对研究对象的分类能力。不是所有的知识都是必需 的，因此就产生了知识约简问题。所谓知识约简( 包括属性约简和值约简) 就是 在保持信息系统分类能力不变的基础上，删除冗余或者可以忽略的知识。原始 的信息系统中的知识并不是同等重要的，甚至其中某些知识是冗余的。这些冗 余知识的存在一方面是对资源的浪费( 需要存储空间与处理时间) ；另一方面也 干扰人们做出正确而简洁的决策，影响了人们对于信息系统的认识和利用。 属性约简算法是粗糙集理论的核心内容。基于遗传算法的属性约筒算法是 启发式约简算法的一种。由于遗传算法本身具有全局优化和隐含并行性等优点， 用遗传算法求解属性约简，通常会减小计算的复杂性并得到最小约简或最小相 对约简。基于遗传算法的粗糙集属性约简可以利用各种启发式信息来求解，分 析国内外各种基于遗传算法的属性约简算法的不同之处，主要在于编码、遗传 算子和适应度函数的选择不同；但是，由于属性约简的n p h a r d 问题特征以及 遗传算法理论存在的局限性和不足之处，启发式遗传约简算法也有很多优化改 进的地方，例如启发式信息的选取，编码和种群的设计，各种遗传算子的选定 和修正算子的设计问题都是影响遗传约简算法的效果问题，是值得深入探讨研 究的方向。研究更加快速、更为有效的遗传约简算法是本论文的主要研究内容。 1 2 研究的意义 粗糙集属性约简的研究在实际应用中有重要的意义，化简冗余属性，保留 最佳决策，可以大大提高数据处理的效率。利用粗糙集理论及约简算法可以进 行知识获取、机器学习、图像处理、决策制定、模型建立等应用。高效的约简 算法是粗糙集理论应用于数据挖掘与知识发现领域的基础。但是，w o n gs k m 和z i a r k o 【1 1 在1 9 8 5 年已经证明找出一个信息系统或决策表的最小约简是一个 n p - h a r d 问题，这是由数据组合爆炸引起的，也不存在统一、规范的高效算法， 对大型数据库，最小约简事实上并不存在，人们通常得到的是近似约简，因此， 研究更为有效的简化算法，有效地获取较优的属性约简，降低算法的时间复杂 度，寻求快速的约简算法仍是粗糙集理论的主要研究课题之一。本文的选题是 针对粗糙集理论中属性约简问题的求解，利用遗传算法属性依赖度等启发式信 息求最小约简，与基于区分矩阵的约简算法相比，本论文算法的计算复杂度更 小，而且可以处理一些大数据集的问题，这对于最小规则集的生成以及通过得 到的规则进行决策分析具有很大的帮助，也有着很强的实用性。 1 3 粗糙集属性约简算法的国内外研究现状 1 9 8 2 年波兰数学家z p a w l a k 在研究不精确、不确定性及不完全知识表示 和分类的基础上发表r o u g hs e t s 2 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 t i 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 ) 【3 】以及 1 9 9 2 年s l o w i n s k ir 主编的关于粗糙集应用及其相关方法比较研究的论文集【4 1 的出版，标志着粗糙集理论及其应用的研究进入了活跃时期。1 9 9 2 年在波兰召 开了关于粗糙集理论的第一届国际学术会议，这次会议着重讨论了集合近似定 义的基本思想及其应用和粗糙集环境下的机器学习基础研究，1 9 9 5 年a c m c o m m u n i c a t i o n 将粗糙集列为新浮现的计算机科学的研究课题，从此每年召开 一次以粗糙集理论为主题的国际研讨会，推动了粗糙集理论的发展和应用。 经过2 0 多年的发展，在粗糙集理论及其应用方面都取得了丰硕的成果，得 到了快速的发展，每年都有与粗糙集理论相关的国际研讨会举行以及大量与粗 糙集理论相关的文章，并出版了很多租糙集理论及其应用的书籍【5 - 9 l 。 粗糙集理论中有效算法的研究是粗糙集理论在人工智能研究中的一个主要 方向。目前，粗糙集理论中有效算法研究主要集中在规则提取、属性约简算法 以及与粗糙集有关的神经网络和遗传算法研究等。属性约简是粗糙集理论的核 心问题之一。属性约简的任务就是在保持知识表达系统中分类能力不变的情况 下，删除其中不相关或不重要的属性。但是已经证明求解所有约简和求解最小 约简都是n p h a r d 问题。属性约简与核的求解一直就是粗糙集理论研究的熟点 与难点。现有的粗糙集属性约简算法大致可以分为三类： ( 1 ) p a w l a k 数据约简算法。这种方法按照属性约简的定义进行求解，需要 对条件属性集的幂集中的所有元素进行考察，因而具有指数型时间复杂度，该 算法具有很强的理论指导意义，但其计算速度慢，且不易于计算机实现，因此， 其实际应用的局限性较大。 ( 2 ) 区分矩阵属性约简方法。由波兰华沙大学的著名数学家s k o w r o n 1 0 】提 出来的区分矩阵是用来求最小约简的有利工具。通过区分矩阵得出核属性，根 据核属性求区分函数的最小析取范式，最后得到的每个折取分量对应着一 个约简，也因此可以得到最小约简。算法的时间复杂度为d ( 2 h * l a * l u l * l o g l u d ， 2 其中x 为条件属性的子集，a 为属性集合，i u i 为对象( 实例) 集合，比p a w l a k 数据约简算法的时间复杂度减少一半，并且可以求出信息系统的所有约简，因 此可以找到最小属性约简；但是该算法在处理海量数据的信息系统属性约简问 题上不是非常有效的。 ( 3 ) 启发式属性约简算法。目前，对这类约简算法的研究较多。主要有基 于遗传算法、通过属性重要度或区分矩阵中属性频度等启发信息来寻求信息系 统的约简。这类方法可以对大规模数据集进行处理。现有的关于属性约简的文 献大部分都是在基于属性重要度和基于区分矩阵两种算法的基础上提出，典型 的有由x ，h u 提出的基于属性重要度的约简算法【1 1 1 ，基于属性依赖度的约简方 法【呓l ，茁夺谦等人的基于属性互信息的约简方法 1 3 l ，基于区分矩阵属性频率【1 4 】 的约简算法和基于关联矩阵【”】等约简算法都各有优点。w r o b l e s w s k ij 等人【1 6 】 提出的基于遗传算法求最小属性约简的算法( 简称为遗传约简算法) 也得到比较 好的效果。文献 1 7 提出了一种在优化初始群体基础上提高算法性能的启发式 遗传算法，以属性重要度作为约简启发式信息；代建华等【1 3 】提出的算法是通过 信息论中互信息来定义的属性重要度为启发式信息进行遗传算法约简，具有较 好的约简效果和收敛速度。 1 4 研究内容及结构安排 本文系统综述了多种粗糙集属性约简算法，在分析比较多种启发式属性约 简算法之后，对基于遗传算法和属性依赖度的启发式属性约简算法进行了研究。 通过研究租糙集的属性约简算法，在适应度函数中引入属性依赖度，对遗传约 简算法的编码方法、种群初始化设计及遗传算子的分析设计进行了研究。分析 遗传约简算法的复杂度、算法的收敛性和约简效果等问题，并通过实验数据加 以分析，证明给出算法的有效性。本文的主要工作如下： 第一章是绪论。主要介绍了本文的研究目的和意义，属性约简算法的国内 外研究现状和本文研究的主要内容。 第二章是粗糙集理论与遗传算法的相关知识。在本章中详细介绍了粗糙集 理论的基础知识，包括租糙集的基本概念，上下近似集、属性核与约简、区分 矩阵和区分函数、属性依赖度和属性重要度等概念；对遗传算法理论的相关知 识进行了总结概述。 第三章是属性约简算法的研究与分析。对粗糙集属性约简的基本方法和启 发式属性约简算法进行了系统的综述，包括基于区分矩阵和区分函数的属性约 简算法，基于属性重要度约简算法和基于属性依赖度的约简算法，以及基于遗 传算法的启发式属性约简算法，深入研究了基于属性依赖度的遗传约简算法， 基于信息熵的属性重要度的遗传约简算法，通过分析比较各种遗传约简算法的 优劣，本文设计了一种基于属性依赖度的遗传约简的改进算法。 第四章是基于属性依赖度的遗传约简算法。对设计的基于属性依赖度的遗 传约简算法进行了详细介绍和分析。在本章中分析了算法的基本思想，并给出 了各类算子的设计和实现方法；在此基础上通过引用属性核来限制初始种群的 生成，避免了盲目随机产生种群，大大减少遗传算法的搜索空间，并提高属性 约简结果的准确性。同时提出了一种局部优化策略，对种群的个体进行局部优 化，保证了算法的可行性，使得搜索总在可行解的范围内进行，加强了局部搜 索能力。分析了算法的可行性和性能，算法不仅能对决策信息系统求得尽可能 多的约简，而且在时间复杂度上也大大降低。通过实验分析证明该算法能对大 多数测试数据集进行有效处理，并且更优于传统的遗传约简算法。 第五章是总结与展望。对本文的研究工作散了总结分析，并对进一步的研 究方向进行了分析和展望。 4 第二章粗糙集理论与遗传算法理论的相关知识 粗糙集理论( r o u g hs e tt h e o r y ，简称r s 理论) 是由波兰学者z p a w l a k 教授 在1 9 8 2 年提出的，它是一种处理含糊和不确定问题的新型数学工具，能有效的 分析和处理不确定、不一致的各种不完备信息，并从中发现隐含的知识，揭示 潜在的规律。利用租糙集理论处理的问题主要包括数据库中的数据约简、数据 相关性的发现、数据中范式的发现以及因果关系的发现。经过二十几年的研究 与发展，粗糙集理论已经在理论和实际应用上取得了长足的发展。目前，它已 经在医疗诊断、决策分析、信息检索、近似推理、机器学习、图像处理等领域 得到了较为成功的应用，成为数据挖掘与知识发现的重要工具。 遗传算法( g e n e t i c a l g o r i t h m s ，简称g a ) 是以自然选择和遗传理论为基础， 将生物进化过程中适者生存规则与群体内部染色体的随机信息交换机制相结合 的高效全局寻优搜索算法。遗传算法拼弃了传统的搜索方式，模拟自然界生物 进化过程，采用人工进化的方式对目标空间进行随机优化搜索。遗传算法具有 鲁棒性、隐含并行性和全局搜索等特点，并且容易与其它技术结合，适用于复 杂优化问题的并行处理，己经广泛应用于组合优化等领域【1 9 , 2 0 。 本章将介绍租糙集理论和遗传算法的相关知识，为后面结合粗糙集和遗传 算法理论，研究基于这两种理论方法的属性约简算法提供理论基础。 2 1 粗糙集理论基础 2 1 1 信息表知识表达系统 ( 1 ) 知识的分类概念 假定起初对论域里的对象具有必要的信息或知识，通过知识能够将其划分 到不同的类别。若对两个元素具有相同的信息，则它们是不可区分的，即根据 己有的信息不能将其划分开，显然这是一种等价关系。由特定区域内的所有个 体组成问题的论域u ，对于论域中由等价关系划分出的任意子集x ，都可称为 u 中的概念或范畴。论域u 中的任意概念簇称为关于u 的知识，它代表了对u 中个体的分类。 定义2 1 【8 l 知识可以定义为：给定一组数据( 集合) u 和等价关系集合r ，在 r 下对u 的划分，称为知识，记为u r 。u 上的一个簇划分( 对u 的分类) 称为 关于u 的知识库。 关于u 的一个知识库也可以理解为一个关系系统，其中u 是论域，r 是u 上的一簇等价关系，根据这些关系就可以对u 进行不同的划分。 设u 是一个论域，r 是u 上的一个等价关系。u r 表示u 上由r 导出的 所有等价类。【x 】r 表示包含元素x 的r 的等价类，x u 。一个知识库就是一个 5 关系系统k = u ，p ) ，其中u 是论域，p 是u 上的一个等价关系簇。如果q c _ u 且q a ，则n q ( q 的所有等价关系的交) 也是一个等价关系，记作i n d ( q ) 。 ( 2 ) 信息表知识表达系统和决策表 信息表知识表达系统的基本成分是研究对象的集合，关于这些对象的知识 是通过指定对象的属性( 特征) 和他们的属性值( 特征值) 来描述得。 定义2 2 一般地，一个信息表知识表达系统s 可以表示为s = ( u ，a ，v f ) 。 其中u 为对象的非空有限集合，称为论域；一= c k d d 为属性的非空有限集合， 子集c 和d 分别称为条件属性集和决策属性集，y = u 匕，圪是属性a 的值域； f u x a _ v 是一个信息函数，它为每个对象的每个属性赋予一个信息值，即 v a e a ，x e u 蕾：x ，a ) v a 对于每一个属性子集b 4 ，定义一个不可分辨二元关系( 不分明关 系) i n d ( b ) ，即 n 囝( b 产 ( x ，y ) u 2 ，v b b ( b ( x 勋) )( 2 - 1 ) 显然，i n d ( b ) 是- - 个等价关系，且玳d ( b ) = n i n d ( b ) ) f 3 8 1 。 k 矗 一个决策表是一个信息表知识表达系统s = ( u ，a ，v ，f ) ，彳= c u d 为属性的 非空有限集合，子集c 和d 分别称为条件属性集和决策属性集，c n d = a ， d a 。 条件属性c 和决策属性d 的等价关系i n d ( c ) 和i n d ( d ) 的等价类分别称为 条件类和决策类。 2 i 2 粗糙集的基本概念 粗糙集理论延拓了经典集合论，把用于分类的知识嵌入集合内，作为集合 组成的一部分。一个对象a 是否属于集合x ，需要根据我们拥有的关于论域的 知识来做出判断，可分为三种情况：对象a 肯定属于集合x ；对象a 肯定 不属于集合x ；对象a 可能属于集合x ，也可能不属于集合x 。因此，集合 划分依赖于所掌握的关于论域的知识，是相对的而不是绝对的。 定义2 3 l s lu 为非空的论域，等价关系r 将u 划分为互不相交的基本等价 类u 瓜。设x 量u ，如果x 能表示成r 的等价类的并集，则称x 在u 上是r 可定义的，否则称x 是r 不可定义的。r 可定义是可以在知识库k ( u ，r ) 中被 精确定义的；r 不可定义则不可能在这个知识库中被定义。r 可定义集也被称 为r 精确集，而r 不可定义集被称为r 非精确集或称r 粗糙集( 简称租糙集) 。 如果存在一个等价关系r 历r d ( 回，其中i n d ( k ) 是k 上给定的所有等价关 系的交集，使得z k 是r 精确的，则集合x 被称作k 中精确集；如果j c k 对任意r m d ( 目都是粗糙的，则x 被称作k 上的粗糙集。粗糙集可以近似的 定义，在粗糙集理论中采用两个精确集( 粗糙集的上近似集和下近似集) 的方法 6 来达到这个目的。 定义2 4 t 8 1 形式地，设x 是u 的子集，x u ，r 是u 上的等价关系，则 有： 疋( x ) = u y e u r i r z ( 2 - 2 ) 盖一( x ) = 【， y u r i y n x g ( 2 3 ) 分别称是( x ) 和r - ( x ) 为x 的r 下近似集和x 的r 上近似集，其中y 是u 上 等价关系r 对u 的划分。 下近似集被解释为u 中所有一定能被包含在x 里面的等价类的并集；上近 似集被解释为所有与x 的交不为空集的等价类的并集。事实上，下近似集疋( 。柳 是包含于x 中的最大r 可定义集；上近似集r 一( x ) 是包含x 的最小r 可定义 集。 定义2 5p o s r ( x ) = 尼( 肖) ，称为x 的正域，它是完全属于x 的个体元索 的集合。n e g r ( x ) = u r ( x ) ，称为x 的负域，是那些不能任意模糊地用等价 关系r 确定的个体元素的集合，它们不属于x ，而是属于x 的补集x 。下近似 集和上近似集的差称为x 的边界集：b n t 。( x ) = r 一( x ) 一足( 柳。它是那些通过等 价关系既不能在x 上被分类，也不能在x 的补集x 上被分类的元素的集合。显 然，b n r ( x ) 的元素越多，x 的粗糙度就越大。 x 是r 可精确定义的( 称x 是可定义的) ，当且仅当r 一( x ) = 足( 柳；x 对于 r 是粗糙的，当且仅当r ( x ) 足( x ) 强】。 2 1 3 属性约简与核 属性约简的目标就是要从条件属性集合中发现部分必要的条件属性，使得 根据这部分条件属性形成的相对于决策属性的分类和所有条件属性所形成的相 对于决策属性的分类一致，即和所有条件属性相对于决策属性有相同的分类能 力。 定义2 6 设u 为一个论域，p 和q 为定义在u 上的两个等价关系簇，尸c ， q c _ d ，q 的p 正域定义为p o s e ( q ) = u ( z ) 。若p o 彤( 9 = p o & h 。 ) ( 9 ， x 刨| q 称p 中条件属性a 为q 不必要的( 可省略的) 。p 中所有q 必要条件属性形成的 集合，称为p 的q 核( 相对属性核) ，记作c o r e e ( p ) 。如果决策表中每个条件 属性都是必要的，则称条件属性集c 是关于d 独立的；否则称c 是关于d 依 赖的。若决策表中条件属性集c 的予集b 关于d 独立，且p o s s ( d ) = p o s c p ) ， 则称b 是c 的一个d 约简( 相对约简) ，所有c 的d 约简构成的集合记作 r e d o ( c ) 。 7 2 1 4 区分矩阵和区分函数 区分矩阵( d i s c e r n i b i l i t ym a t r i x ) 是由波兰华沙大学的著名数学家s k o w r o n 提出来的，是近年来在粗糙集约简上出现的一个有力工具，利用这个工具，可 以将存在于复杂的信息系统中的全部不可区分关系表达出来1 1 0 】。 定义2 8 对于信息系统s = ( u ，a ，v f ) ，a = c v d ，c n d = a ，c 和d 分 别是条件属性和决策属性。s 的区分矩阵c 。是一个厅行对称矩阵，a ( x ) 是实例x 在属性a 上的值，c v ( i ，) 表示区分矩阵中第i 行，第j 列的元素，因此区分矩 阵的定义为： c o ( i ，) = 0 扣船“挑”d d ( 珈x ，) - 叫d ( 三：x j ( 2 4 ) 其中i ，j = 1 ，n 。 显然，区分矩阵是一个依主对角线对称的矩阵，在计算区分矩阵的时候， 只需要考虑其上三角( 或下三角) 部分就可以了。 根据区分矩阵的定义可知，当两个实例的决策属性取值相同时，它们所对 应的区分矩阵元素的取值为o ；当两个实例的决策属性不同且可以通过某些条 件属性的取值不同加以区分时，它们所对应的区分矩阵元素的取值为这两个实 例属性值不同的条件属性集合，即可以区分这两个实例的条件属性集合；当两 个实例发生冲突时，即a ( x 1 ) = a ( x j ) ，d “) d ( x j ) 的情况，则它们所对应的区 分矩阵中的元素取值为空集。显然，区分矩阵元素中是否包含空集元素可以作 为判定信息系统是否包含不一致( 冲突) 信息的依据。 定义2 9 区分函数是一个布尔函数，用表示。信息系统s = ( u ，a ，v ，f ) ， 对每个属性4 a ，若c 0 ( f ，) = “，a 2 ，a k 0 ，则指定一个布尔函数 q v a 2 v y a k ，用c v ( i ，) 来表示；若c d ( f ，) = o ，则指定布尔常量1 。定义区 分函数如下： a = ，1 7 ，c d ( f ，) ( 2 - 5 ) 区分函数是从区分矩阵中构造的。方法是把c v ( i ，_ ，) 的每个属性“或”起来， 然后再“与”起所有的c v ( i ，_ ，) 。区分函数有如下性质：函数极小析取范式 中所有合取式是属性集a 的所有约简。也即约简是满足能区别由整个属性集区 别的所有对象的属性极小集。 2 1 5 属性依赖度和属性重要度 ( 1 ) 属性依赖度( d e p e n d a b i l i t yo f a t t r i b u t e s ) 这个概念反映了属性与属性之间的关系。如果我们把一种属性看作是反映 物体的一种知识的话，那么属性依赖度就可以看作是一种知识对另一种知识的 3 推导能力，是一种知识依赖性的度量。当q 的所有概念可以用p 中的某些概念 定义时，则知识q 是从知识p 中可导的。当q 从知识p 中可导时，称q 依赖 于p ，记为p q 。依赖性可形式化地定义如下： 定义2 1 0 令k = ( u ，r ) 为一知识库，且令p ，q c r ； 1 ) 当i n d ( p ) g i n d ( q ) ，知识q 依赖于知识p ； 2 ) 当p j q 且q j p 。知识p 和q 是等价的记为p ；q ； 3 ) 当不存在p q ，且不存在q j p ，p 和q 是独立的。 显然，当且仅当m d ( p ) c 1 n d ( q ) ，有p j q 。 定义2 1 1 属性依赖度( 知识依赖度) ： 令k = ( u ，r ) 为一知识库，且令p ，q s 只，当 k = ，( p q ) = r p ( q ) = i e o s , ( q ) l u i ( 2 - 6 ) 时，我们称知识q 是k 度依赖p 的( 0 k s l ) ，记作p j q ，其中i l 表示集合 的个数；p o s e ( q ) = 【j ( 功为论域u 在q 的p 正域。因此， 氨 q i n ，、i k = r ( p ，9 ) = y 掣。 一，爿op i 如果k = l ，则称q 完全依赖于p ：如果o k l ，则称q 部分依赖于p ；如 果k = o ，则q 完全独立于p 。这种属性依赖度可解释为将对象分类的能力。准 确地说，当k = l 时，论域的所有对象都可以通过知识p 划入分类u q 的概念中， 也就是说，p o s a q ) = u = p o s a q ) ，根据相对约简的定义可知此时的p 就是一 个约简：当k 1 时，只有属于正域的对象可通过知识p 划入分类u q 的概念中， 还要其他对象不能正确的划分，此时的p 就不是一个约简；特别地，当k = o ， 论域中没有对象可以通过p 划入分类u q 的概念中。由依赖度定义可见，当 p j iq ，则有q 导出的分类u q 的正域覆盖了知识库的七x 1 0 0 个对象：另一 方面，只有属于分类正域的对象能被唯一的分类，即对象的k x l 0 0 对象通过 知识p 划入分类u q ；因此，k 也叫做衡量知识u p 对u q 划分质量的绝对标 准，也可以衡量p 是否是一个约筒。 ( 2 ) 属性的重要程度( s i g n i f i c a n c eo f a t t r i b u t e s ) 属性的重要度是指对分类的重要度。根据集合b 对集合c 近似分类的质量 r s ( c ) 这一概念，我们可以对论域实例属性的重要程度进行度量。在讨论不同的 问题时属性具有不同的重要度，这种重要度可在辅助知识的基础上事先假设， 并用“权重”表示。在粗糙集理论中不使用任何先验的信息，给出一种基于数 据的客观度量。为了找出某些属性或属性集的重要度，需要从属性集中去掉一 些属性，再考察没有该属性后分类会发生什么变化。若去掉该属性后分类情况 改变较大，说明该属性重要度高，反之重要度低。因此，属性的重要度可以用 9 正域来衡量。 对于属性集c 导出的分类属性子集b b 的重要度，我们可以用两者的依 赖程度的差来度量，即r b ( c ) - r 。( c ) 。这表示当从集合b 中去掉某些属性子集 昱。对属性集c 近似分类的质量的影响。属性的重要度也可以用 p o s s 、，( c ) p o s m f ( c ) 的形式来表示。 定义2 1 2 如果有s = ( 以c u d ) ，对任意a c ，则，( c 、 口 ，研则可以表示 成去除c 中的a 属性之后与d 之间的依赖关系，那么就可以用这两个量来表示 属性a 的重要程度： s g f ( a c d ) = 监嚎噼业1 _ 篙( 2 - 7 ) 若s g f ( a ，c ，d ) 越小，则表示属性a 的重要度越低，反之则越高。 2 2 遗传算法的基础理论 遗传算法是由美国m i c h i g a n 大学的h o l l a n d 教授及其学生在2 0 世纪6 0 年 代末研究形成的，它试图通过解释自然界中生物的复杂适应过程入手，模拟生 物进化机制来构造人工系统的模型。经过几十年来的发展，遗传算法不论是在 应用领域还是理论研究方面都取得令人瞩目的成果f 1 9 也。 2 2 1 遗传算法的特点 与传统的搜索方法相比，遗传算法采用了独特的方法和技术，主要表现在 以下几个方面睇“j j ： ( 1 ) 遗传算法具有自组织性、自适应性和智能性。应用遗传算法来求解问 题时，在确定了编码方案、适应度函数及遗传算子后，算法将利用进化过程中 所获得的信息自行组织搜索。遗传算法的这一特性，使它同时具有能根据环境 的变化而皂动发现环境的特性和规律的能力。从而使遗传算法能够用来解决一 些复杂的非结构问题。 ( 2 ) 遗传算法具有并行性，它在种群中按并行方式搜索而不是在一个单点 上进行寻优的。其并行性表现在两个方面；一是遗传算法本身具有并行性，使 它本身适合大规模并行。二是遗传算法具有内含并行性，它采用种群自组织的 方式组织搜索，同时可以搜索解空间内的多个区域，并相互交流信息。遗传算 法从一个种群开始搜索，并且可以同时向不同的方向进行搜索，对搜索空间中 的多个解进行评估，以使遗传算法具有极好的全局搜索性能，从而减少了陷入 局部最优解的可能。 c 3 ) 遗传算法使用参数的编码集，而不是参数本身进行工作。这一特点， 使得遗传算法且有广泛的应用领域。 ( 4 ) 遗传算法基本上不需要搜索空间的知识或其它辅助信息，而使用问题 1 0 本身的目标函数和相应的适应度函数进行工作。 ( 5 ) 遗传算法不是采用确定性规则。而是采用概率的变迁规则来指导它的 搜索方向。在优化过程中，使搜索的每一步向最终结果靠近的机制或智能称为 搜索的探索性或启发性。 ( 6 ) 遗传算法对给定的问题，可以产生很多的潜在解，最终的选择可以由 使用者确定。 2 2 2 遗传算法适合解决的问题 遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索方法。 美国m i c h i g a n 大学的h o l l a n d 教授编写的a d a p t a t i o ni nn a t u r a la n da r t i f i c i a l s y s t e m s ) ) 专著，是第一本系统论述遗传算法和人工资适应系统的书籍，系统的 阐述了遗传算法的基本理论和方法，为遗传算法奠定了数学基础，标志着遗传 算法的诞生。h o l l a n d 教授在这本书中指出，在自然界和人们生活中存在着一类