（计算机应用技术专业论文）基于粗糙集理论与遗传算法的分类算法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 数据挖掘是通过对数据的分析和理解，从而获得隐含在数据背 后的有用信息。根据数据挖掘任务的不同，可以将数据挖掘的模式 分为以下几种：分类模式、预测模式、关联规则模式、回归模式、 聚类模式、时间序列模式等。不论是哪一种模式，算法都起着非常 重要的作用。 本文主要是对分类模式的算法进行研究，其主要工作包括以下 几个方面： 1 )总结了目前分类模式中常用的方法。 2 )介绍粗糙集理论和遗传算法的基本理论、概念，并总结了 粗糙集理论中属性约简的经典算法。 3 )介绍了一种基于依赖度的属性核求取算法，并对此算法进 行了改进，改进后的算法可以求取属性的一个约简。 4 ) 在对遗传算法和粗糙集理论研究的基础上，提出一种基于 粗糙集理论和遗传算法的分类算法，并用个数据集对该 算法进行验证。该分类算法也对简单遗传算法进行了改 进，增加了动态改变交叉率和变异率的思想。 论文共分5 章。第一章简单介绍了数据挖掘的产生和发展，并 总结了当前数据挖掘研究的状况；第二章重点介绍粗糙集理论的相 关知识，并介绍了几种经典的属性约简算法；第三章对遗传算法进 行了介绍；第四章详细介绍了基于重要度和依赖度的属性约简算 法，以及基于租糙集和遗传算法的分类算法；第五章通过一组数据 对该分类算法进行验证。 关键词：数据挖掘；粗糙集；遗传算法；分类规则；属性约筒 西南交通大学硕士研究生学位论文 第2 页 a b s t r a c t d a t am i n i n g ( d m ) i sat e c h n i q u et h a ta i n l st oa n a l y z ea n d u n d e r s t a n dl a r g es o u r c ed a t aa n dr e v e a lu s e f u lk n o w l e d g eh i d d e ni nt h e d a t a f r o mt h ed i f f e r e n tt a s k o fd m , t h e r ea r es e v e r a lp a t t e r n sa s f o l l o w s ：c l a s s i f i c a t i o np a t t e m ，p r e d i c t i o np a t t e r n ，a s s o c i a t i o nr u l e p a t t e r n ，r e g r e s s i o np a t t e r n ，c l u s t e r i n gp a t t e r n ，t i m es e r i e sp a t t e r n ， a n ds oo n a l g o r i t h mi sv e r yi m p o r t a n tf o ra n y p a t t e r n t h ee m p h a s i so ft h i st h e s i si st h ea l g o r i t h mo f c l a s s i f i c a t i o n p a t t e r n t h em a i nc o n t r i b u t i o no ft h i sd i s s e r t a t i o ni n c l u d e s ： 1 1 s u r v e yt h ec u r r e n ta l g o r i t h m so f c l a s s i f i c a t i o np a t t e m 2 、i n t r o d u c et h eb a s i ct h e o r ya n dc o n c e p to fr o u g hs e t sa n d g e n e t i ca l g o r i t h m s ，a n ds u m m a r i z et h ec l a s s i ca l g o r i t h m so f a t t r i b u t er e d u c t i o nb a s e do n o u g hs e t s 3 ) i n t r o d u c ead e p e n d a b i u t ya l g o r i t h mo fa t t r i b u t er e d u c t i o n , a n dt h e ni m p r o v et h ea l g o r i t h mb a s e do nd e p e n d a b i l i t ya n d i m p o r t a n c e 4 1b a s e do nt h er e s e a r c ho fg e n e t i ca l g o r i t h ma n dr o u g hs e t s ， p r o p o s ea c l a s s i f i c a t i o na l g o r i t h m ，a n du s es o m ed a t at ov e r i f y i t a m o n gt h ea l g o r i t h m ，i m p r o v et h es i m p l eg e n e t i ca l g o r i t h m b yc h a n g i n gt h ep r o b a b i l i t yo fc r o s s o v e ra n dm u t a t i o n i n d y n a m i c t h et h e s i si so r g a n i z e da sf o l l o w s ：c h a p t e r1i n t r o d u c e ss o m e b a s i cc o n c e p t sa n dt h ed e v e l o p m e n ts t a t eo fd a t am i n i n g c h a p t e r2 i n t r o d u c e ss o m eb a s i cc o n c e p t so fr o u g hs e t sa n d # y e st h es u r v e yo n s e v e r a lt y p i c a lr e d u c t i o na l g o r i t h m s c h a p t e r3i n t r o d u c e st h eb a s i c c o n c e p t so fg e n e t i ca l g o r i t h m c h a p t e r4i n t r o d u c e st h ei m p r o v e m e n to f t h ed e p e n d a b i l i t ya n di m p o r t a n c ea l g o r i t h mo fa t t r i b u t er e d u c t i o n ，a n d t h e nd e s c r i b e st h ei d e ao fa l g o r i t h mb a s e do nr o u g hs e t sa n dg e n e t i c a l g o r i t h m c h a p t e r5u s e ss o m ed a t at ov e r i f yt h ea v a i l a b i l i t yo ft h e a l g o r i t h m 西南交通大学硕士研究生学位论文 第3 页 k e y w o r d s ：d a t am i n i n g ；r o u g hs e t s ；g e n e t i ca l g o r i t h m s ； c l a s s i f i c a t i o nr u l e ；a t t r i b u t er e d u c t i o n 西南交通大学硕士研究生学位论文第6 页 第一章引言 数据挖掘( d a t am i n i n g ，d m ) 的研究领域始于2 0 世纪9 0 年代， 它是一门交叉学科，涉及到数理统计、人工智能、机器学习、模式 识别、数据可视化、数据库等多项技术领域。经过十几年的研究发 展，数据挖掘开始走向成熟，并正朝着更深入的方向发展。 本章主要介绍了数据挖掘的产生与发展、分类模式的常用研究 方法以及论文的研究内容及方法。 1 1 数据挖掘的产生与发展 随着数据库技术的迅速发展和数据库管理系统的广泛应用，使 得各企事业单位积累了大量的数据。并且人们也意识到在这些大量 的数据背后必然隐含着许多重要信息，因此人们希望能够对这些信 息进行更高层次的分析，以便能对决策者提供更好的支持。 但是，目前使用的数据库管理系统通常是用来存储数据和对数 据进行简单的操作，比如增加、删除、查询、修改等，这些操作根 本不可能为我们提供隐含在数据背后的重要信息。因此，我们必须 研究出一种新的数据分析手段，数据挖掘正是为了解决传统分析方 法的不足，并针对大规模数据的分析处理而出现的。 数据挖掘是指从大型数据库或数据仓库中提取人们感兴趣的 知识，这些知识是隐含的：事先未知的、潜在有用的信息，提取的 知识一般可以表示为概念( c o n c e p t s ) 、规则( r u l e s ) 、规律 ( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式1 1 1 。由于数据挖掘能够从 大量的数据中提取出隐藏在数据之后的有用信息，它被越来越多的 领域所应用，并取得良好的效果，为人们做出正确的决策提供了很 大的帮助。 数据挖掘被认为是数据库知识发现中最重要的一部分。基于数 据库的知识发现( 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 ，k d d ) 一词， 最早是在1 9 8 9 年8 月美国底特律市召开的第1 1 届国际人工智能学 西南交通大学硕士研究生学位论文第7 页 术会议中提出的，其目的是在数据库中发现不被人们所知道的、潜 在的知识和有用的信息。国际k d d 学术会议起初每两年召开一次， 1 9 9 3 年后则每年召开一次。 1 9 9 5 年在加拿大蒙特利尔召开第一届知识发现和数据挖掘国 际学术会议，数据挖掘这一术语被学术界正式提出，它为在海量数 据中提取信息带来了新的希望。自1 9 9 5 年以来，国外在数据挖掘 和知识发现方面的论文非常多，并已经成为了热门研究方向。数据 挖掘的技术历经了数十年的发展，并已经形成了一些成熟的技术。 这些技术和高性能的关系数据库引擎以及广泛的数据集成，让数据 挖掘技术在当前的数据仓库环境中开始进入实用阶段。 此外，数据库、人工智能、信息处理、知识工程等领域的国际 学术刊物也纷纷开辟了k d d 专题或专刊。i e e e 的k n o w l e d g ea n d d a t ae n g i n e e r i n g 会于0 首先在1 9 9 3 年出版了k d d 技术专刊，所发 表的5 篇论文代表了当时k d d 研究的最新成果和动态。随后，各 类k d d 会议、研讨会纷纷涌现，许多领域的国际会议也将k d d 列为专题讨论。1 9 9 9 年，i e e e 和a c m 再次推出k d d 专刊，介绍 数据挖掘在各个领域的应用成果。 不仅如此，在i n t e m e t 上还有不少k d d 电子出版物，其中以半 月刊 k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威， 在 h t t p ：w w w k d n u g g e t s c o m - 中，可以下载各种数据挖掘工具软件和数 据挖掘相关的资料。 目前，国外数据挖掘的发展趋势和研究方向主要有：传统的统 计学回归法在k d d 中的应用；k d d 与数据库的紧密结合。在应用 方面包括：k d d 商业软件工具不断产生和完善，注重建立解决问 题的整体系统，而不是孤立的过程。用户主要集中在银行、保险、 电信、销售业。国外的许多计算机公司也非常重视数据挖掘的开发 应用，i b m 和m i c r o s o f t 都成立相应的研究中心进行这方面的工作。 很多著名的计算机公司开始尝试开发k d d 方面的软件开发，比较 典型的有s a s 公司的e n t e r p r i s em i n e r ，i b m 公司的i n t e l l i g e n t m i n e r ，s g i 公司的s e t m i n e r ，s p s s 公司c l e m e n t i n e 等等。w e b 数 据挖掘产品有n e tp e r c e r p t i o n s ，a c c r u e l n s i g h t 和a c c r u eh i tl i s t ， c o m m e r c et r e n d s 等。 与国外相比，国内对k d d 的研究稍晚，目前进行的大多数研 西南交通大学硕士研究生学位论文 第8 页 究项目是由政府资助进行的，如国家自然科学基金、8 6 3 计划等。 1 9 9 3 年国家自然科学基金开始对数据挖掘研究进行支持。1 9 9 4 年4 月在北京召开的第三届亚太地区k d d 国际会议( p a k d d 9 9 ) 响应 热烈，共收到论文1 5 0 多篇。国内从事数据挖掘的人员主要集中在 大学和研究所。所涉及的研究领域很广，对学习算法的研究和数据 挖掘的实际应用及数据挖掘理论方面的研究占了很大的比重。但 是，到目前为止，国内还没有比较成熟的数据挖掘产品。 1 2 分类模式的常用研究方法 根据数据挖掘的任务的不同，可以将数据挖掘的模式分为以下 几种：分类模式、预测模式、关联规则模式、回归模式、聚类模式、 时间序列模式等。 由于本文研究的是对数据的分类，因此将重点放在数据挖掘中 对分类的研究状况分析。 分类的目的是提出一个分类函数或分类模型( 即分类器) ，通 过分类器将数据对象映射到一个给定的类别中。现阶段分类模式中 比较常用的方法有以下几种： ( - - ) 决策树学习法 决策树学习的基本算法是贪心算法，它采用自顶向下的递归方 式构造决策树。h u n t 等人于1 9 6 6 年提出的概念学习系统( c o n c e p t l e a r n i n gs y s t e m ，c l s ) 是最早的决策树算法，以后的许多决策树算法 都是对c l s 算法的改进或由c l s 衍生而来。q u i n l a n 于1 9 7 9 年提 出著名的i d 3 ( i n t e r a c t i o nd e t e c t i o n ) 算法，但i d 3 只能处理离散属 性的数据。c 4 5 是以i d 3 为蓝本的算法，它能处理连续属性值的数 据。其他决策树方法，如：i d 4 和i d 5 ，都是在3 1 1 3 3 算法的基础上 进行的改进。s u q 、s p r i n t 、r a i n f o r e s t 算法可以构建具有伸缩性 的决策树。在我国，钟鸣，陈文伟等提出的示例学习算法i b l e 9 l 也克服了i d 3 算法的不足。 ( - - ) 贝叶斯分类法 西南交通大学硕士研究生学位论文第9 页 贝叶斯分类最常见的是朴素贝叶斯分类( n a i v eb a y c s c l a s s i f i c a t i o n ) ，又称简单贝叶斯分类( s i m p l eb a y e s i a n c l a s s i f i c a t i o n ) 。它将训练样本a 分解为特征向量c 和决策类别向 量d 。 假定一个特征向量的各个分量相对于决策变量是独立的，即各 分量独立作用于决策变量，这一假定叫做类条件独立。这个假定简 化了计算，所以称为“朴素的”。一般认为只有在满足类条件独立的 情况下，朴素贝叶斯分类才能获得准确最优的分类效果；在属性相 关性较小的情况下，能获得近似最优的分类效果。 这种假定以指数级速度来降低贝叶斯网络的复杂性，而且在许 多实际应用领域，它表现出相当的健壮性和高效性。然而，在实际 情况中变量之间可能存在着依赖关系，这样朴素贝叶斯分类法就不 实用，而贝叶斯信念网络可以解决这个问题。 贝叶斯信念网络通过指定一组条件独立性假定( 有向无环图) ， 以及一组局部条件概率集合来表示联合概率分布。贝叶斯信念网络 允许在变量的子集间定义条件独立性，并且提供一种因果关系的图 形，因而可以在其上进行学习。目前，如何从训练数据中学习贝叶 斯信念网络是研究的一个焦点。 ( 三) 基于遗传算法的分类 遗传算法是一种模拟生物自然选择与遗传机理的随机搜索算 法。与其他确定性算法不同，遗传算法只对系统的输出进行适应度 的评定，与系统的内部复杂性无关，是一种黑箱方法，因此遗传算 法特别适合于比较复杂问题。 遗传算法是一种启发式搜索算法，它可以在解空间内进行充分 的搜索，其时耗和效率都优于其他优化算法。但是，它容易收敛于 局部极小值。近年来，越来越多的是将遗传算法与神经网络、粗糙 集等技术的结合起来。如利用遗传算法优化神经网络结构，在不增 加错误率的前提下，删除多余的连接和隐层单元：用遗传算法和 b f ( b a c kp r o p a g a t i o n ) 算法结合训练神经网络，然后从网络提取规则 等。 ( 四) 神经网络方法 西南交通大学硕士研究生学位论文 第1 0 页 神经网络由于具有良好的鲁棒性、自组织自适应性、并行处理、 分布存储等特性，适合于解决数据挖掘的问题，因此近年来越来越 受到人们的关注。用于分类的典型神经网络模型是前馈式神经网络 模型。神经网络方法的缺点是“黑箱”性，人们难以理解网络的学习 和决策过程。 ( z k ) 基于粗糙集的分类 粗糙集理论是波兰数学家z p a w l a k 在1 9 8 2 年提出的一种分析数 据的数学理论。它是利用上、下近似集来处理不确定性问题。粗糙 集理论用于发现分类规则的基本思想是：首先根据决策属性的不同 取值，将数据分成不同的类别，并且生成判断规则：然后再利用粗 糙集的规则发现算法获取分类规则。基于粗糙集的分类算法简单， 易于操作，但是利用粗糙集的分类算法所生成的规则有可能不完 整。 粗糙集作为一种软计算方法，可以克服传统不确定处理方法的 不足，并且和其他软计算方法能有机地结合进一步增强对不确定、 不完全信息的处理能力。目前，在国内外都有学者将粗糙集和其他 的学科相结合【1 0 f 1 2 j 驯，如粗糙集和信息论、粗糙集和遗传算法及粗 糙集和神经网络相结合，不过研究的述不是很多。当然对粗糙集理 论和其他学科结合的机构和个人远不止这些，还有许多，在此就不 一一列举。 1 3 本论文研究内容及结构安排 在事务数据库中挖掘分类规则是数据挖掘领域中的一个非常 重要的研究课题。数据挖掘的目标是采用有效的算法从火量现有的 数据集合中发现并寻找未知的、潜在的有用信息，并用浅显的语言 或者形式来显示出来。因此，在数据挖掘的过程中，算法起着至关 重要的作用。 本文研究的主要内容是将粗糙集和遗传算法相结合来构造一 个用于寻找分类规则的算法。 论文共分5 章。 西南交通大学硕士研究生学位论文第1 1 页 第一章对数据挖掘的产生与发展做出概括，并总结了分类模式 的常用研究方法。 第二章对粗糙集的有关理论和相关算法进行简单的介绍。 第三章对遗传算法的基本知识进行介绍。 第四章针对粗糙集中属性依赖度的属性约简算法的不足，进行 了改进；针对遗传算法的特点提出一些改进措旌；然后详细介绍了 基于粗糙集和遗传算法的分类算法，并对算法的性能进行分析。 第五章应用实际数据对该分类算法进行验证。 西南交通大学硕士研究生学位论文第1 2 页 第二章粗糙集理论 粗糙集理论是一种研究不精确、不一致和不确定性知识的数学 工具。其基本原理是利用等价类的思想，在保持分类能力不变的情 况下，通过对知识的约简来简化决策表，从而导出问题的决策或分 类规则。 2 1 概述 粗糙集理论是一种比较新的软计算方法，它从诞生到现在仅仅 2 0 多年，但是它的发展速度却是惊人的。它可以有效地分析和处理 不完备信息，可以应用于各个不同的领域。 2 1 11 理论的产生和今后研究方向 波兰数学家z d 4 a w l于年发表的经典论文3jak 1 9 8 璺 r o u g h s e t s 标志着粗糙集理论的诞生 粗糙集理论是一种数据分析理论。最初它的研究主要集中在波 兰，因此没有日起国际计算机界和数学界的重视。直到i 9 9 0 年， 由于该理论在数据的决策分析、模式识别、机器学习与知识发现等 方面的成功应用，才逐渐引起人们的关注。1 9 9 1 年，z p a w l a k 的著 作 r o u 功s e t 堋e o r e t i c a la s p e c t so f r e a s o n i n ga b o u td a t a ) ) 问世， 标志着粗糙集理论及其应用进入活跃时期。1 9 9 2 年，在波兰召开了 关于粗糙集理论的第一届国际学术会议，从此每年都要召开以粗糙 集为主题的学术会议，并且国际上还成立了粗糙集学术研究学会。 1 9 9 5 年，a c mc o m m u n i c a t i o n 将粗糙集列为新浮现的计算机科学 的研究课题。 在我国，粗糙集的研究起步较晚，从1 9 9 4 年才开始。但是， 国内也非常重视其研究，从2 0 0 1 年开始，每年召开一次中国粗糙 西南交通大学硕士研究生学位论文第1 3 页 集与软计算学术研讨会( c r s s c ) 。目前，我国对粗糙集的研究领 域主要集中于理论方面，应用研究的实例研究较少。 目前，粗糙集理论已成为信息科学研究中最活跃的领域。在今 后的研究过程中以下一些研究方向将是粗糙集研究的主要方面【强 1 9 j ： ( 1 ) 高效约简算法 粗糙集一开始就是应用于约简。但是，到目前为止还没有一种 非常有效的算法。因此，高教、快速的约简算法仍然是未来粗糙集 研究的方向之一。 2 ) 大数据集问题 现在的数据库越来越大，粗糙集如何处理这一挑战仍然是个问 题。虽然现在已经有一些探索，但是还没有找到一种令人满意的方 法。这就需要发展相应的算法，比如并行计算。 ( 3 ) 多方法融合 现在虽然有许多数据挖掘算法，但是却没有一种算法适用于所 有的测试集，它们都是局部优于其他算法。因此，多种方法的融合 可能是进一步提出高性能分类算法的方法之一。尤其是将粗糙集和 其他软计算方法( 如：遗传算法、模糊集、概率论等) 相结合的算 法，将是粗糙集的另一个研究热点。 ( 4 ) ，对不完备信息处理 在现实的信息中，有许多信息是不完整或者相矛盾的，怎样对 这些不完备信息的处理也将是粗糙集的研究方向。 2 1 2 粗糙集理论的特点 粗糙集从诞生到现在虽然时间很短，但是发展得相当快，并且 应用到很多领域中，这是因为它具有如下特点【4 】： 1 它能处理各种数据，包括不完整( i n c o m p l e t e ) 的数据以及 拥有众多变量的数据； 2 它能处理不精确性和模棱两可( a m b i g u o u s ) 的数据，包括 确定性和非确定性的情况； 3 它能求得知识的最小( r e d u c e ) 表达和知识的各种不同颗粒 西南交通大学硕士研究生学位论文 第1 4 页 ( g r a n u l a r i t y ) 层次； 4 它能从数据中揭示出概念简单，易于操作的模式( p a t t e r n ) ； 5 它能产生精确而又易于检查和证实的规则，特别适合于智能 控制中规则的自动生成。 粗糙集与模糊集都能处理不完备( i m p e r f e c t ) 数据，但方法有 所不同，模糊集侧重于描述信息的含糊程度( v a g u e n e s s ) ，而粗 糙集则强调数据的不可分辨性( i a d i s c e r m b i l i t y ) 、不精确性 ( i m p r e c i s i o n ) 和模棱两可性( a m b i g u i t v ) 。 粗糙集研究的重点是分类，即对不同种类中的对象集合之问的 关系研究；而模糊集研究的是属于同一类的不同对象的隶属关系， 重在隶属程度。模糊集和粗糙集的不同点还有，模糊集在处理问题 时需要隶属函数，而粗糙集却利用数据本身的信息对数据进行处 理，不需要任何额外信息。 因此，粗糙集和模糊集是两种不同的理论，但它们之间也不是 相互对立的，它们在处理不完整数据方面可以互为补充。 2 2 粗糙集理论的相关概念 粗糙集理论是一种刻划不完整性和不确定性的数学工具。它能 有效地分析和处理不精确、不一致、不完整的信息，并从中发现隐 含的知识，揭示潜在的规律。它不仅为信息科学和认知科学提供新 的研究方法，而且也为智能信息处理提供了有效的处理技术。为了 便于后面章节的讨论，本节介绍一些与粗糙集理论的相关概念。 2 2 1 知识库和信息系统 假定r 是u 的一个等价关系，则u r 表示r 的所有等价类构 成的集合， x 】。表示包含元素x e u 的r 等价类。知识库嘲就是一 个关系系统k = ( u ，r ) ，其中u 为非空有限集，称为论域，r 是 u 上的一族等价关系。也就是说，u 上的一族划分就是关于u 的一 个知识库。 西南交通大学硕士研究生学位论文第1 5 页 若p c r ，且p f ，则np ( p 中所有等价关系的交集) 也是一个 等价关系，称为p 上的不可区分关系，记为m d ( p ) ，并且 x 】t 2 恩【x r 1 6 】。 信息系统由一个四元组组成，即：i = u ，a , v ，毋。其中：u 为对 象集，即论域；a 是属性集合，它由条件属性集c 和决策属性集d 构成，即：a c u d ；v 为各属性的值域；f 为u x a v 的映射 关系，它为u 中各对象的属性指定唯一值。 2 2 2 上、下近似集和正域 粗糙集理论是经典集合论的延伸，它把用于分类的知识嵌入集 合中，作为集合的一部分。根据现有的知识，我们可以对一个对象 a 是否属于集合c 的判断有三种情况： ( 1 ) a 肯定属于集合c ； ( 2 ) a 肯定不属于集合c ； ( 3 ) a 可能属于也可能不属于集合c 。 集合的划分依赖于我们所掌握的论域知识，是相对的而不是绝 对的。 粗糙集中用上近似集1 6 1 和下近似集【6 i 来精确描述类似问题。 知识库k = ( u ，r ) ，对于每个子集x c _ u 和一个等价关系 r i n d ( k ) ，定义： r x = u y u r l y x ) r x = u y u r l y n xp 中) 分别称他们为x 的r 下近似集和r 上近似集。 p o s r ( x ) 一丛称为x 的r 正域。集合b n r ( x ) 一r x 一丛称 为x 的r 边界域f 6 1 。 墼丕或p o s 。( x ) 是由那些根据知识r 判断肯定属于x 的u 中元 素组成的集合；r x 是那些根据知识r 判断可能属于x 的u 中元 西南交通大学硕士研究生学位论文第1 6 页 素组成的集合；根据知识r 不能判断肯定属于x 或肯定属于。x ( 即 u x ) 的元素组成集 b n 。( x ) 。 2 2 3 属性的依赖度和重要度 在信息系统中，各个属性之间有可能存在一定的联系，在粗糙 集中我们用依赖度来定义属性之间的联系。 令k = ( u ，c u d ，v ，f ) 为一决策表，且r c 当 k = 。( d ) = l p o s 。( d ) i i u l 时，我们称属性d 是k ( 0 k5 1 ) 度依 赖于属性r 的。当k = l 时，称d 完全依赖于r ；0 k ； w i n d ( p ) = a l ，a s ) ， a 2 ，a 8 ， a 3 ， a 4 ) ， 6 ) ， a 7 ) 根据上面的介绍，我们可以计算出： u i n d ( e - p 1 ) = a l ，a 5 ， a 2 ，a 7 ，a s ， a 3 1 ， a 4 1 ， a 6 1 1 ：# u i n d ( p ) ，这表明p 1 是p 中必要的； o i n d ( p p 2 ) ) = “a 1 ，a s ， a 2 ，a s ， a 3 1 ， a 4 1 ， 6 1 ， a 7 ) = u i n d ( n ，这说明p 2 是p 中不必要的； i j i n d ( p 一 p 3 ) ) = a 1 ，a l 5 ) ， a 2 ，a s ) ， a 3 ) ， a 4 1 ， 6 1 ， a 7 t = u i n d ( p ) ，这说明p 3 也是p 中不必要的。 上述的计算说明，通过等价关系p 1 ，p 2 ，p 3 的集合定义的分 类与根据p 1 和p 2 或者p 1 和p 3 定义的分类相同。为了得到p = p 1 ， p 2 ，p 3 1 的约简，可以通过验 ! j e p 1 ，p 2 1 和 p 1 ，p 3 是否独立来得 到结果。通过验证发现， p 1 ，p 2 和 p 1 ，p 3 都是独立的，因此它 们都是p 的约简。 根据核的概念，可以得出c o r e ( p ) = l p l ，p 2 np 1 ，p 3 i = p 1 。 西南交通大学硕士研究生学位论文第1 9 页 2 3 2 属性约简的基本算法 属性约简是粗糙集研究的一个热点。到目前为止，研究学者已 经提出了多种属性约简算法，本节介绍几种典型属性约简算法。 1 基本算法1 3 1 基本算法的思想是：首先根据信息系统的决策表构造可辨识矩 阵m ；然后再利用可辨识矩阵m 得到可辨识函数f ；最后把可辨 识函数f 利用吸收律对它进行化简，使其成为最小析取范式，得到 的每一个主蕴含式都为约简。 该算法的优点是：可以求出所有的约简。然而，对大量数据的 可辨识函数的约简是一个非常困难的问题，因此，该算法只适合于 小数据量的情况。基本算法的时间复杂度为 0 ( 2 i q 4 i a l + l u i + 1 9 i u l ) ，其中i c 痿示条件属性的个数，j a | 表示属性 个数，l u 陵示元组个数。 2 基于可辨识矩阵的启发式算法 s k o w l o w 提出可辨识矩阵【”j 并且提出可辨识矩阵可用于属性 约简。在此基础上，利用可辨识矩阵得到许多启发式约简算法。这 些算法的共同点都是先得到可辨识矩阵，由可辨识矩阵求出属性的 核，再在此基础上根据某种启发式规则向属性核中加入属性，直到 满足条件为止。以此为基础的典型算法有如下两种： ( 1 ) h ux i a o h u a 提出计算一个最好的或者用户指定的最小约 简的算法【1 6 】，该算法非常简单、直观，它利用可辨识矩阵求出核， 并将此核作为计算约简的出发点，将属性的重要度作为启发规则。 其基本思想是：先按照属性的重要度的大小逐个加入属性，直 到该集合是一个约简为止：然后检查集合中的每一个属性，即移走 属性后看该集合对决策属性的依赖度是否发生变化，如果依赖度不 变化则可以将该属性去掉，反之则保留该属性。通过可辨识矩阵求 属性核的时间复杂度为o ( | c l + l uj t l g l u i ) ，而在利用条件属性的 重要度的时候最多需要循环i c l 次，因此该算法的最坏时间复杂度为 西南交通大学硕士研究生学位论文第2 0 页 o ( i c l 2 + l u + l g i u i ) 。 ( 2 ) j e l o n e k 等人提出了逐步扩展型算法【切，其算法和h u x i a o h u a 的算法有相同之处，但是，j e l o n e k ；! e 算法中应用了近似精 度的概念。近似精度的定义为： 设p _ c ( 条件属性) ，对由决策属性产生的划分 y 1 ，y 2 ， k y k 的p 近似精度( a p p r o x j m a t i o nq u a l i t y ) 为：y p =a r d ( p y i ) 雨 c a r d ( u ) ，其中p y i 为y j 的p 下近似集，c a r d ( ) 表示集合的基数。 该算法的基本思想是：首先根据可辨识矩阵求出属性核r ；然 后求出属性核r 和条件属性的每个等价划分的近似精度：如果y 。 = y 。，则r 为属性约简：否则，对所有的属性a c ，计算增量g a i n = y 。 。 r 。，若a 是使相应的g a i n 达到最大的属性，则置r = r u a ) 并判断它是否为约简( r 。= y 。) ， 若是，则停机；否则， 继续上述过程。 在该算法中，从核( 可以是空集) 开始，每扩展一次，都要对所 有的属性a c ，计算新的近似精度y 。u a ) ，计算量是比较大的。容 易验证，y 。的计算的时间复杂度为o ( i c l + l u l 3 ) 。由于选择晟大的 增量g a i n 需要对整个条件属性进行遍历一次，因此，在最坏情况下， j e l o n e k 算法的计算时问复杂度为o ( i c l 2 。i u l 3 ) 。 3 遗传算法 到目前为止，有很多人利用遗传算法来计算属性的约简问题。 这类算法的不同之处，就是编码和适应度函数设计的不同。最具代 表性的是b j o r v a n d 和k o m o r o ws k i 提出的遗传算法。在这个算法中， 他们用每个位串来代表可辨识矩阵的一项，即两个对象的区分属性 西南交通大学硕士研究生学位论文第2 l 页 集。其中值为1 表示该属性存在，为0 则不存在。这样每个位串是一 个约简的候选。他们定义的适应度函数如下： ，一业+ 矿c 而v n i m 一一m i ，z 其中：n 表示属性集的个数，l v 表示位串中1 的个数，c v 是位串 能区分的对象组合的个数，m 是对象的个数。 函数中的前一部分是希望l v 的长度尽量小，而后部分则希望可 以区分的对象尽可能多些。在设计初始种群时，可以人为地加一些 信息，比如将属性核或者专家认为重要的属性加入种群，这样可以 加快算法收敛。 4 基于属性依赖度的属性约简算法 属性的依赖度算法【2 3 1 ，是根据决策属性集对条件属性集的依赖 程度来计算的，郎：去掉冗余的知识后，如果决策属性对剩下的属 性集是完全依赖的话，这一部分知识是可以被约去的；反之，则是 不可约简的。 在这个算法中，运用了以下的一个命题，即：条件属性集的核 是所有由决策属性集中强依赖的条件属性集的子集的交集。该命题 的证明详见参考文献 2 3 1 。 算法描述如下： c o r e = c ；c o r e 表示核，c 表示条件属性集 f o r ( i = o ；i ；“+ ) n 表示属性值的个数 f = c - c m c i 表示第i 个属性值 听( d ) ；c a r d ( p o s f ( d ) ) c a r d ( u ) ： 掌盯，( d ) 表示f 集合对决策属性d 的依赖度，c a r d ( ) 表示 元素的多少+ i f ( 毋( d ) = = 1 ) c o f e = c o r e f ： 该算法思想简单，而且没有像一般的算法那样需要先求出可辨 识矩阵，然后才能求属性的核。但是，该算法只得到了条件属性的 核，并没有得到属性的一个约简。如果在对该算法进行改进，就能 西南交通大学硕士研究生学位论文第2 2 页 够得到属性的一个约简。改进的算法将在第四章介绍。 除了这些算法之外，还有许多其它算法，例如基于基因的算法 、动态约简算法【2 l 】、基于粗糙熵的算法【2 2 】等等。每一种算法都有 其自身的特点和应用范围，并不能说某一种算法完全优于另外一种 算法或比另外的算法差。 到目前为止，粗糙集理论的属性约简算法还没有一个公认的、 高效的算法。而且，这些算法中很多都是在利用可辨识矩阵的基础 来求属性的核，但是求可辨识矩阵是一个非常困难的问题，尤其在 是数据量大、属性较多的情况下。 西南交通大学硕士研究生学位论文第2 3 页 第三章遗传算法 遗传算法( g e n e t i c a l g o f i t h r a s ，g a ) 是由美国m i c h i g a n 大学的 j o h nh o l l a n d 教授与其同事、学生在2 0 世纪6 0 年代末7 0 年代初研 究形成的，它试图通过解释自然界中生物的复杂适应过程入手，模 拟生物进化机制来构造人工系统的模型。经过2 0 多年来的发展， 遗传算法不论是在应用领域还是理论研究方面都取得令人瞩目的 成果，特别是近年来计算机界的进化计算热潮，推动了遗传算法的 进一步发展。 3 1 遗传算法的产生、发展及特点 在2 0 世纪5 0 年代就有计算机科学家进行“人工进化系统”的研 究，其出发点是进化思想可以发展成为许多工程问题的优化工具。 这就是遗传算法的雏形，但是当时由于缺乏一种通用的编码方法， 人们只能依赖变异操作来产生新的基因结构，因此早期的算法收效 甚微。 6 0 年代中期，j o h nh o l l a n d 提出位串编码技术，该编码技术既 适用于变异操作又适用于交叉操作，并且他强调了遗传算法的主要 操作应该是交叉操作，而不是变异操作。 7 0 年代初，h o l l a n d 教授提出遗传算法的基本定理模式定 理，从而奠定了遗传算法的理论基础。模式定理揭示出种群中优良 个体的样本数将以指数级韵规律增长，因而他从理论上保证了遗传 算法是一个可以厢采哥找最优解的优化过程。 1 9 7 5 年，h o l l a n d 教授出版了第一本系统论述遗传算法和人工 自适应系统的专著，其名称为“a d a p t a t i o ni n n a t u r a la n da r t i f i c i a l s y s t e m ”( 自然系统和人工系统的自适应性) 。同年，m i c h i g a n 大学的d ej o n g 博士在他的博士论文遗传自适应系统的行为分析 中，结合模式定理进行大量的纯数学值函数优化计算实验，建立了 遗传算法的工作框架，为遗传算法的应用打下坚实的基础。 西南交通大学硕士研究生学位论文 第2 4 页 2 0 世纪8 0 年代是遗传算法和进化计算的蓬勃发展时期。首先， h o l l a n d 教授实现了第一个基于遗传算法的机器学习系统分类 器系统，为分类器系统构造了完整的框架。其次，在国际上以遗传 算法、进化计算为主题的多个国际会议在世界各地定期召开。1 9 8 5 年，在美国卡耐基梅隆大学召开的第一届国际遗传算法会议 i c g a 8 5 ，以后该会议每隔一年举行一次。有关遗传算法基础理论 的学术活动也很活跃，第一届遗传算法与分离系统研讨会于1 9 9 0 年在美国印地安那大学召开，以后每隔两年召开一次。 在我国，9 0 年代以来有关遗传算法方面的研究也相当活跃，并 且取得了一定的成果。 遗传算法是模拟生物进化过程的计算模型，是遗传学和计算机 科学相结合、相渗透而形成的计算方法。它为我们提供了一种以有 限代价来解决搜索和优化问题的有效途径，它不同于传统的搜索和 优化方法，其主要原因是它具有以下特点【冽： 1 遗传算法具有智能性，具体表现在自组织、自适应和自学习 性。应用遗传算法求解问题时，只要编码方案、适应度函数及遗传 算予确定以后，算法将仿照进化过程中“适者生存”的原则对求解问 题进行自行组织搜索，从而获得问题的最优解。由于遗传算法具有 智能性，因而它可以解决复杂的非结构化问题。 2 遗传算法的本质并行性。它的并行性表现在两个方面，一是 遗传算法是内在并行的( i n h e r e n tp a r a l l e l i s m ) ，即遗传算法本身非 常适合大规模并行；二是遗传算法的内含并行性( i m p l i c i t p a r a l l e l i s m ) ，由于遗传算法采用种群的方式组织搜索，因而可以 同时搜索解空间内的多个区域，并相互交换信息。 3 遗传算法不需求导或其他的辅助知识，而只需要影响搜索方 向的目标函数和相应的适应度函数。 4 遗传算法强调概率转化规则，而不是确定的转化规则。 5 遗传算法对给定问题可以产生许多的潜在解，最终的选择可 以由使用者确定。 6 遗传算法可以更加直接地应用。 西南交通大学硕士研究生学位论文第2 5 页 3 2 遗传算法的编码方法 把一个问题的可能的解从其解空间转换到遗传算法所能处理 的搜索空间的转化方法，称为编码1 2 2 1 。遗传算法求解问题时首先考 虑的就是如何进行编码。编码方法会影响交叉、变异等操作，而且 编码方法在很大程度上决定了种群的遗传进化运算的效率。目前有 许多不同的编码方法，常用到的有二进制编码、实数编码、符号编 码等。这些编码各有优缺点，下面分别对它们进行介绍。 3 2 1 二进制编码 二进制编码是遗传算法中最常用的一种编码方法，它所使用的 编码符号由二进制符号0 和1 组成，所构成的染色体是一个二进制 串。在二进制编码中，按一定的顺序每一位或几位二进制就对应一 个参数变量，因此，编码后的二迸制串能够表示出所求问题的信息。 染色体的长度与问题的求解精度有关。 设某参数x 的取值范围是 x m i n ，x m a x ，用长度为n 的染色 体来表示该参数，总共能产生2 。种不同的染色体，则编码精度为 p = ( x m a x x m i n ) ( 2 “1 ) ，由此我们可以看出染色体的长度足 够的话，就能达到足够的精度。 二进制编码方法由于编码和解码操作都简单，交叉、变异操作 容易实现，而且二进制编码也便于利用模式定理进行理论分析因 此在实际应用中比较常见。但是它也有缺点，如：在二进制编码中 变异操作不能保证父个体和新个体的接近性，因此二进制编码的种 群稳定性不足；二进制编码不便于