（计算机应用技术专业论文）数据挖掘中属性选择算法的分析与研究.pdf

摘要 摘要 数据挖掘技术提供了海量数据分析的一种有效方法。目前，数据挖掘在零售， 军事，商业智能，金融等众多领域都得到了广泛的应用。通常数据挖掘算法对数 据的质量都有较高的要求，如冗余度小，相关程度高，噪音低等。但是实际中产 生的业务数据往往不具有这些特点，因此对数据挖掘的数据进行预处理就成为一 项重要的任务。属性选择就是对数据挖掘中的数据进行预处理的一个很重要的步 骤。一个好的属性选择方法可以有效地减少数据的冗余度和降低数据的维度，使 得数据挖掘算法在经过处理的数据集合上有更加良好的表现。 本文首先介绍了数据挖掘的基本思想与处理步骤，在此基础上进一步阐述了 属性选择对数据挖掘的重要意义，并针对属性选择的步骤和属性选择方法进行了 详细的分析。同时，结合数据挖掘研究平台w e k a ，分析了属性选择算法的设计与 实现，深入剖析了属性选择算法的运行过程。进而，实现了一种基于信息增益和 遗传算法结合的属性选择方法，并通过大量的实验分析，论述了这种方法存在的 问题。最后，提出了一种基于最小描述长度和遗传算法结合的属性选择方法，这 种方法采用最小描述长度作为对属性集合进行评价，使用遗传算法作为对属性集 合的空间进行搜索，对于搜索过程中的每个属性集合都使用最小描述长度标准进 行评价，确定这个属性集合是否可以继续保留在搜索过程中。该方法保留了遗传 算法的鲁棒性和高效性，不仅可以在较短的时间内发现属性子集，而且利用最小 描述长度作为评价标准选择出来的属性子集在用于分类时可以达到更好的分类效 果。大量的实验同时表明这种方法在绝大部分数据集上都有良好的性能，并且其 平均错误率优于w e k a 平台上已实现的那种基于遗传算法的属性选择方法。 关键词：数据挖掘：属性选择；最小描述长度；遗传算法 分类号：t p 3 0 1 6 本文得到国家自然科学基金项目资助( 基金项目编号：6 0 6 7 3 0 8 9 ) v a b s l r a c t a bs t r a c t d a t am i n i n gt e c h n i q u e sh a v eb e e np r o v i d i n ga ne f f e c t i v ea n de f f i c i e n tm e t h o df o r d a t aa n a l y s i s , w h i c hh a v eb e e nw i d e l yu s e di nr e t a i l i n g , m i l i t a r yo p e r a t i o n ，b u s i n e s s i n t e l l i g e n c e ，f i n a n c ea n dm a n yo t h e rd o m a i n s t h ea l g o r i t h m si nd a t am i n i n gu s u a l l y r e q u i r em u c hm o r eq u a l i f i e dd a t a , s u c ha ss m a l lr e d u n d a n c y , h i g hc o r r e l a t i o n ，a n dl o w n o i s e h o w e v e r , r e a lw o r l dd a t a o f t e nd on o tm e e tt h e s ec h a r a c t e r i s t i c s ，d a t a p r e p r o c e s s i n g si na d v a n c eh a v eb e e nb e c o m i n go n e o fi m p o r t a n tt a s k si nd a t am i n i n g a t t r i b u t es e l e c t i o ns h o u l db eak e ys t e pi nd a t ap r e p r o c e s s i n g s a n yb e t t e ra t t r i b u t e s e l e c t i o nm e t h o dc o u l dr e d u c ed a t ar e d u n d a n c ya n dd i m e n s i o n so fd a t ae f f e c t i v e l ya n d e f f i c i e n t l y , m a k i n gd a t am i n i n ga l g o r i t h m sm o r ee f f e c t i v eo nt h ed a t aw h a th a v eb e e n p r e p r o c e s s e d t h i st h e s i sf i r s ti n t r o d u c e dt h eb a s i ci d e a so fd a t am i n i n ga n di t sp r o c e s s i n gs t e p s ， t h e nd e m o n s t r a t e dt h ei m p o r t a n c eo na t t r i b u t es e l e c t i o nf o rd a t am i n i n g ，a n do u t l i n e d m a i ns t e p sa n dm e t h o d so fa t t r i b u t es e l e c t i o ni nd e t a i l m e a n w h i l e ，i tf o c u s e do n o n eo f d a t a m i n i n gr e s e a r c hp l a t f o r m s w e k a , m a i n l y o nt h ea n a l y s i so fd e s i g na n d i m p l e m e n t a t i o nf o ra t t r i b u t es e l e c t i o na l g o r i t h m s ，a n dad e t a i la n a l y s i so fa t t r i b u t e s e l e c t i o no p e r a t i o n s t h e n ，a na t t r i b u t es e l e c t i o nm e t h o db a s e do ni n f o r m a t i o ng a i na 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 d d i s c u s s i o n so ne x p e r i m e n t a lr e s u l t sh a v es h o w n i t sp r o s a n dc o n s f i n a l l y , am e t h o db a s e do nam i n i m u md e s c r i p t i o nl e n g t ha n dg e n e t i c a l g o r i t h mi sp r o p o s e d , w h i c hu s e dam i n i m u md e s c r i p t i o nl e n g t ha st h ee v a l u a t i o no f a t t r i b u t es e t s ，a n dag e n e t i ca l g o r i t h m 舔t h es e a r c ho fa t t r i b u t es e t ss p a c e ，e v a l u a t i n g e v e r ya t t r i b u t es e td u r i n gt h es e a r c hp r o c e s s ，t od e c i d ew h e t h e rt h i ss u b s e ts h o u l db e k e p ti i lt i l es e a r c hp r o c e s s ，t h i sm e t h o dc o u l dm a i n t a i nr o b u s t n e s sa n de f f i c i e n c yi n g e n e t i ca l g o r i t h m s ，n o to n l yf i n d i n gt h a ta t t r i b u t es u b s e t si na r e s o n a b l es h o r tt i m e ，b u t a l s ot h eu s eo fm i n i m u md e s c r i p t i o nl e n g t h 勰e v a l u a t i o nc r i t e r i ac o u l di m p r o v e a c c u r a c yo nc l a s s i f i c a t i o nb yt h es e l e c t e da t t r i b u t e s al a r g en u m b e ro fe x p e r i m e n t a l r e s u l t sh a v es h o w nt h a tt h i sm e t h o dc a ng e tg o o dp e r f o r m a n c eo nm o s to ft h ed a t as e t s ， a n dt h ea v e r a g ee r r o rr a t ei sb e t t e rt h a nt h eg e n e t i ca l g o r i t h mt h a tw a si m p l e m e n t e do n w e k ap l a t f o r m k e y w o r d s d a t am i n i n g ；a t t r i b u t es e l e c t i o n ；m d l ；g e n e t i ca l g o r i t h m c l a s s n o ：t p 3 0 1 6 v l l 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名：签字日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校向国 家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：葱嘭像痧 导师签名： 上名店歹 签字日期：刀留午p 月纠旧 签字日期：0 8 年肛月心日 致谢 本论文的工作是在我的导师王志海教授的悉心指导下完成的，王志海教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢几年来 王志海老师对我的关心和指导。 瞿有利老师悉心指导我完成了实验室的科研工作，在学习上和生活上都给予 了我很大的关心和帮助，在此向瞿有利老师表示衷心的谢意。孙永奇老师对于我 的科研工作和论文都提出了许多的宝贵意见，在此向孙永奇老师表示衷心的感谢。 在实验室工作及撰写论文期间，谢作将、季长冰、李锦善等同学对我论文中 算法实现方面的工作提出了宝贵的意见，并给予了热情的帮助，在此向他们表达 我的感激之情。 另外也感谢我的家人和我的朋友，他们的理解和支持使我能够在学校专心完 成我的学业。 最后，衷心地感谢在百忙之中审阅论文的各位老师和专家，恳请各位老师多 多批评指正，并提出宝贵的意见 引言 1 1研究背景 1 引言 随着信息技术和数据库技术的迅猛发展，人们可以非常方便的获取和存储大 量的数据，曾有人预测全球的数据存储量每隔2 0 个月要增长一倍。如此大规模的 数据背后隐藏着许多重要的信息，传统的数据分析工具( 如管理信息系统) 只能 进行一些表层的处理( 如查询、统计等) ，而不能获得数据之间的内在关系和隐含 的信息。为了摆脱“数据丰富，知识贫乏”的困境，人们迫切需要一种能够智能、 自动地把数据转换成有用信息和知识的技术和工具，计算机技术的迅速发展和这 种对强有力数据分析工具地迫切需求使得数据挖掘技术应运而生。数据挖掘工具 能够对将来的趋势和行为进行预测，从而很好地支持人们的决策，有些数据挖掘 工具还能够解决一些很消耗人工时间的传统问题，因为它们能够快速地浏览整个 数据库，找出一些专家们不易察觉地极有用的信息。 数据挖掘的处理对象是大量的日常业务数据，目的是为了从这些数据中抽取 一些有价值的知识或信息。原始的业务数据是知识和信息提取的源泉，对数据挖 掘十分重要。目前所进行的关于数据挖掘的研究工作，大多数着眼于数据挖掘算 法的探讨而忽视了对数据处理的研究。一些比较成熟的算法对其处理的数据集合 一般都有一定的要求，比如数据完整性好、数据的冗余性少、属性之间的相关性 小。然而，实际系统中的数据一般都具有不完全性、冗余性和模糊性，很少能直 接满足数据挖掘算法的要求。另外，海量的实际数据中无意义的成分很多，严重 影响了数据挖掘算法的执行效率，而且由于其中的噪声干扰还会造成无效的归纳。 因此，在应用数据挖掘算法前，首先需要对数据进行预处理，去掉无关属性、减 少属性之间的相关度，即进行属性选择，有着很重要的意义。 属性选择通常作为数据挖掘的一个预处理步骤，在数据选择和为数据挖掘做 准备的过程中起着重要的作用。这个过程是从原属性集合中删除不相关和( 或) 冗余的属性，选出属性子集，以便根据确定的准则使属性空间得到最优的约减。 从上个世纪七十年代以来，在统计模式识别、机器学习和数据挖掘等领域，属性 选择已经成为一个研究与开发成果丰富的领域，并且已经证明，在删除不相关和 冗余的属性、增加学习任务的效率，提高学习的性能( 预测的精度) 和增强学习 结果的可理解性等方面它是有效的。 北京交通大学硕士学位论文 1 2 本文所完成的工作 数据挖掘领域中，如何对数据进行预处理是非常重要和非常复杂的问题。常 用的数据预处理方法有数据抽样，离散化，和属性选择。数据抽样是对数据集合 进行横向选择的一个过程，离散化则可以将连续性的属性转化为离散型进行处理， 而属性选择则是从纵向对数据集合的属性进行约减的一个过程。这些预处理过程 分别适用于数据挖掘的不同方面。 属性选择通常作为数据挖掘的一个预处理步骤，在数据属性选择和为数据挖 掘准备数据的过程中起着重要的作用。常用的属性选择方法都需要结合一定的属 性评价方法和搜索方法来共同完成属性选择的任务。目前，属性选择的评价方法 有属性子集评价方法和单个属性的评价方法，而搜索的方法则集中在穷尽式搜索 和启发式搜索两个方面。 基于以上的背景，本文的主要工作如下： 首先，从通用角度和商业角度综述了数据挖掘的概念和定义，阐述了数据 挖掘的五个基本功能以及常用的数据挖掘方法； 其次，介绍了属性选择的基本概念，进行属性选择所需要的基本步骤，属 性选择的搜索空间，并分析了属性选择的搜索方法和评价方法； 第三，介绍了遗传算法的基本概念，遗传算法的八个组成部分，以及遗传 算法的特点和遗传算法的应用领域； 第四，概述了数据挖掘的开源工具w e k a 的内容和功能，着重分析了w e k a 平台上有关属性选择的算法，以及w e k a 平台上属性选择方法的运行方式； 第五，详细总结了前人在属性选择方面所完成的工作，并在此基础上实现 了一种基于信息增益和遗传算法相结合的属性选择方法，使用信息增益作 为属性子集的评价方法，使用遗传算法作为属性空间的搜索方法，对于搜 索得到的每个属性子集都使用信息增益进行评价，用以确定这个属性集合 是否应该继续保留在搜索过程中。经过大量的实验比较，结果显示这种方 法虽然和以前提出的属性选择方法有所不同，但是算法的效率却并没有显 著的改进； 第六，详细分析了基于信息增益和遗传算法的属性选择方法的优缺点，并 提出了基于最小描述长度和遗传算法的属性选择方法，这个方法使用统计 推断理论中的最小描述长度作为属性子集的评价方法，仍旧使用遗传算法 作为属性子集的搜索方法，对搜索的每个属性子集使用最小描述长度进行 评价，以此决定改属性集合是否应该继续保留在搜索过程中。该方法继续 保留了遗传算法的鲁棒性和高效性的特点，能够在较短时间内找到较好的 2 弓 言 属性集合，采用最小描述长度评价后的数据集合在用于分类时会有更好的 分类效果。通过大量的实验比较，发现该方法在实验效果上优于w e k a 平 台上已实现的属性选择方法； 最后，总结了本文的主要工作内容。 本文在深入分析了属性选择方法的基础上，使用了遗传算法和最小描述长度 标准构造属性选择过程，同时充分利用遗传算法和最小描述长度的优点，逐步深 入的进行算法设计，建立属性选择方法。它以强有力的理论背景作支持，并在试 验中验证了其有效性。 1 3 论文组织安排 本文的主要框架和结构如下： 第l 章：给出了课题的出发点以及研究的问题和范围，分析了数据挖掘面临 的问题和属性选择的研究现状，介绍了本文所完成的工作。 第2 章：全文的理论基础，分别介绍了数据挖掘、属性选择、遗传算法理论 的相关知识，包括数据挖掘的定义，数据挖掘的起源和数据挖掘的方法；属性选 择的步骤，属性选择方法的分类，遗传算法的相关定义等。 第3 章：介绍了著名的开源数据挖掘软件w e k a ，分析了w e k a 的架构。 第4 章：重点分析了w e k a 中属性选择的相关内容，包括w e k a 中属性选择的 评价方法，搜索算法和w e k a 下属性选择算法的运行方式等。 第5 章：提出了一种基于信息增益和遗传算法的属性选择方法，进行了实验， 得出了实验结果，并对实验结果进行了分析。 第6 章：本文的核心部分，提出了一种基于最小描述长度和遗传算法结合的 属性选择方法，并通过实验验证了该方法具有很好的效率。 第7 章：对全文进行了总结，并给出了本课题将来的研究内容和方向。 属性选择和遗传算法 2 属性选择和遗传算法 数据挖掘是多门学科和多种技术相结合的产物，也是一个非常年轻而又活跃 的研究领域它是利用了统计和人工智能技术的应用程序，把这些高深复杂的技 术封装起来，使人们不用自己掌握这些技术也能完成同样的功能，并且更专注于 自己所要解决的问题数据挖掘根据作用领域和方法不同产生了多个分支，分类 作为其中一种重要数据分析技术广泛应用在金融、证券、科学、工程等实际领域。 本章首先简要介绍数据挖掘的概念和功能，接下来详细介绍属性选择的定义， 属性选择的子集空间以及属性选择的评价方法和搜索方法。 2 1数据挖掘 2 1 1数据挖掘的概念和定义 随着计算机技术的迅猛发展以及网络的普及，许多行业如商业、企业、科研 机构和政府部门等都有了更多的机会和便捷的方法与外界进行信息交流，数据库 的规模、范围、和深度都在快速不断扩大，从而积累了海量的、以不同形式存储 的数据资料，同时，在许多领域也建立了数据仓库。在这些海量数据中往往隐含 着各种各样的信息，这些信息凭直觉与经验是难以发现的。从大量的数据中获得 有价值的信息，采用传统的数据库技术已经显得无能为力了，数据的快速增长与 数据分析处理方法滞后的矛盾越来越大，人们希望能够在对已有的大量数据分析 的基础上进行科学研究、商业决策或企业管理，从而达到为决策服务的目的。数 据挖掘就是为了满足这种需求而迅速发展起来的一种新的数据处理技术。它的实 质是一种发现知识的应用技术，是一个提取有用信息的过程。自2 0 世纪末提出以 来，引起了许多专家学者的广泛关注，并应用到金融、零售业、工业过程、电力、 医疗保健和政府决策等各个领域，取得了良好的社会效益和经济效益，具有广阔 的开发和应用前景。 目前数据挖掘通用的定义是：指从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有 用的信息和知识的过程】。数据挖掘要解决的问题就是在庞大的数据中寻找有价 值的隐藏信息，加以分析，并将这些有意义的信息归纳成结构模式，提供给有关 人员在决策时参考【4 3 j 。 s 北京交通大学硕士学位论文 人们已经证明，数据挖掘技术能够发现和跟踪数据集合中潜在的模式，因此， 有人认为，在数据库中，处理隐藏的知识、不可预料的模式和新规则发现的所有 方法中，数据挖掘是最有效的。如果没有数据挖掘技术，许多数据就很可能停留 在未使用的阶段。正是数据挖掘能够为企业提供全面、深入的分析和了解客户及 其行为特征的重要助臂。 在商业角度上【4 2 l ，数据挖掘是一种新的商业信息处理技术，其主要特点是对 商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提 取辅助商业决策的关键性数据。简而言之，数据挖掘其实是一类深层次的数据分 析方法。数据分析本身已经有很多年的历史，只不过在过去数据收集和分析的目 的是用于科学研究，另外，由于当时计算能力的限制，对大数据量进行分析的复 杂的数据分析方法受到很大限制。现在，由于各行业业务自动化的实现，商业领 域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于 纯机会的商业运作而产生的。分析这些数据也不再单纯的为了研究需要，更主要 是为商业决策提供真正有价值的信息，进而获得利润。但所有企业面临的一个共 同问题是：企业数据量非常大，而其中真正有价值的信息却很少。因此从大量的 数据中经过深层分析，获得有利于商业运作、提高竞争力的信息，就像从矿是中 淘金一样，数据挖掘也因此而得名。因此，数据挖掘又可以描述为：按企业既定 业务目标，对大量得企业数据进行探索和分析，揭示隐藏得，未知的规律性，并 进一步将其模型化的、先进的、有效的方法。 2 1 2。数据挖掘的功能和方法 为了解决日益更新的海量数据对传统的数据分析技术所带来的挑战，来自不 同学科的研究者汇集在一起，开始着手开发可以处理不同数据类型的更有效的、 可伸缩的工具。这些工作建立在研究者之前使用的方法学和算法之上，在数据挖 掘领域达到高潮。数据挖掘也迅速地接纳了来自其他领域的思想，这些领域包括 最优化、进化计算、信息论、信号处理、可视化和信息检索【j 引。 数据挖掘综合了各个学科的技术，有很多功能，当前主要有以下五类功能【j 川： 1 ) 分类：按照分析对象的属性、特征，建立不同的组类来描述事务。例如： 银行部门根据以前的数据将客户分成了不同的类别，现在就可以根据这些类别来 区分新申请贷款的客户，以采取相应的贷款方案1 2 。 2 ) 聚类：数据库中的记录可被划分为一系列有意义的子集，即聚类。聚类增 强了人们对客观现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要 包括传统的模式识别方法和数学分类学。2 0 世纪8 0 年代初，m c h a l s k i 提出了概念 6 属性选择和遗传算法 聚类技术的主要特点是，在划分对象时不仅考虑对象之间的距离，还要求划分初 的类具有某种内涵描述，从而避免了传统技术的某些片面性。 3 ) 关联规则和序列模式的发现：关联是某种事务发生时其他事务是否会发生 的这样的一种联系。例如：每天购买啤酒的人也有可能购买香烟，比重有多大， 可以通过关联的支持度和可信度来描述。与关联不同，序列是一种纵向的联系。 例如：今天银行调整利率，明天股市会有什么样的变化。 4 ) 预测：数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量 手工分析的问题，如今可以迅速直接由数据本身得出结论。一个典型例子是市场 预测问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户， 其他可预测的问题包括预报破产以及认定对指定事件最可能做出反应的群体。 5 ) 偏差的检测：数据库中的数据常有一些异常记录，从数据库中检测这些偏 差很有意义。偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特 例、观测结果与模型预测值偏差、量值随时间的变化等。偏差检测的基本方法是， 寻找观测结果与参照值之间有意的差别对分析对象的少数的，极端的特例的描述， 揭示内在的原因。 需要注意的是数据挖掘的各项功能不是独立存在的，而是互相联系发挥作用 的。 数据挖掘的方法很多，每种方法都有其特定适用的领域。某一种方法不可能 胜任所有的数据挖掘任务，一个复杂的数据挖掘系统常常采用多种数据挖掘方法， 通过整合多种数据挖掘方法来弥补不同数据挖掘方法所存在的不足。数据挖掘的 方法主要有以下几种： 1 ) 基于决策树的方法 决策树是建立在信息论基础之上、对数据进行分类的一种方法。首先，通过 一批已知的训练数据建立一棵决策树。然后利用建好的决策树，对数据进行预测。 决策树的建立过程可以看成是数据规则的生成过程，因此可以认为，决策树实现 了数据规则的可视化，其输出结果也容易理解。决策树方法精度确实比较高，结 果容易理解，效率也比较高，因而比较常用。构建决策树的算法很多，其中最具 代表性的是c a r t 和c 4 5 算法m 1 。 2 ) 基于神经网络的方法 神经网络最早是由心理学家和神经生物学家提出的。神经网络是大量的简单 神经元按一定规则连接构成的网络系统。网络能够模拟人类大脑的结构和功能， 采用某种学习算法从训练样本中学习，并将获取的知识存储在网络各单元之间的 连接权中。神经网络和基于符号的传统人工智能技术相比，具有直观性、并行性 和抗噪声等优点。目前已出现了多种网络模型和学习算法，主要用于分类、优化、 7 北京交通大学硕士学位论文 模式识别、预测和控制等领域。在数据挖掘领域，主要采用前向神经网络提取分 类规则m j 。 3 ) 基于遗传算法的方法 遗传算法是一种基于生物进化论和分子遗传学的搜索优化算法。它首先将问 题的可能的解按某种形式进行编码，编码后的解称为染色体；随机选取个染色 体作为初始种群，再根据预定的评价函数对每个染色体计算出适应值，性能较好 的染色体有较高的适应值；选择适应值较高的染色体进行复制，并通过遗传算子， 产生一群新的更是适应环境的染色体，形成新的种群，直至最后收敛到一个最适 应环境的个体，得到问题的最优化解【”儿矧。 4 ) 贝叶斯方法 贝叶斯网络是由r h o w a r d 和j m a t h e s o n 于1 9 8 1 年提出来的，它是一种概率 推理方法，它能从不完全、不精确和不确定的知识和信息中做出推理，可以处理 不完整和带有噪音的数据集，解决了数据间不一致和相互独立的问题。贝叶斯分 类是统计学分类方法。它可以预测类成员关系的可能性。一种比较简单的朴素贝 叶斯方法是一种基于概率的分类方法，它通过样本的属性值计算事例属于某一个 类的可能性，然后，将样本归属到最优可能的类中。朴素贝叶斯分类再应用于大 型数据库时，表现出高准确率和高速度t 4 0 。 5 ) 基于粗糙集的方法 粗糙集作为一种软计算方法，它可以不需任何辅助信息，如统计学中的概率 分布、模糊集中的隶属度等，仅依据数据本身提供的信息就能对数据进行化简并 求得知识的最小表达。粗糙集方法可以克服传统的不确定信息的处理方法的不足， 并且能和它们有机结合，进一步增强对不确定、不完全信息的处理能力。粗糙集 方法首先用近似的方法把信息系统中的属性值离散化，然后对每一个属性划分等 价类，再利用集合的等价关系进行信息系统的属性约简，最后得到一个最小决策 关系，便于获得规则。目前成熟的关系数据库管理系统和新发展起来的数据仓库 管理系统为基于粗糙集的数据挖掘奠定了坚实的基础1 4 。 2 2属性选择 属性选择问题是分类、数据挖掘、图像处理、概念学习等许多不同领域的基 础【6 1 。近年来，知识发现和数据挖掘方法在实际应用中不断增长的重要性，使得属 性选择问题成为十分热门的话题，尤其是在考虑从现实世界的数据库或数据仓库 中挖掘的时候，由于它不仅包含数量巨大的记录，而且包含大量与挖掘任务不相 关的属性，属性选择就更加重要。有些数据属性对发现任务是没有影响的，这些 属性选择和遗传算法 属性的加入会大大影响挖掘效率，甚至还可能导致挖掘结果的偏差。因此，有效 的缩减数据是很有必要的。数据简化是在对发现任务和数据本身内容理解的基础 上寻找依赖于发现目标的表达数据的有用特征，以缩减数据规模，从而在尽可能 保持数据原貌的前提下最大限度的精简数据量。它主要有两个途径：属性选择和 数据抽样，分别针对数据库中的属性和记录。 属性选择是指在初始的个属性中选择出一个有m ( 朋 ， 震冀鋈黧黧麓黧懑鞫瓢燃貔燃毖渤巍崩燃纛貔躺锄缓渤磁褫毖瑟麓貔么翮荔磁旌篪茏绷 ( 7 ) 脒霹缪缪秽嘲缪嘲寥缪嘲黪嗍嬲缪粼缀镧 豺黝辘貔躺缓玩貔施燃缴施燃编渤貔磁缀么磁缓貔兹滋缓貔罐貔貔嵫 ( 9 ) ， ， 戮蔡删缪搿缪期彩黟猢戮嬲缪嘲燃缪缪獬燃蝴糊 劾磁缓缓燃缓漱篪燃缀貔锄燃缓渤勰黝缢貔瀚缓缓捌缀巍澎舷凌 鬻曩鬟懑戮黼黼藉 注：表中( 1 ) 为c f s s u b s e t e v a l ；( 2 ) 为c l a s s i f i e r s u b s e t e v a l ；( 3 ) 为c o n s i s t e n c y s u b s e t e v a l ； ( 4 ) 为w r a p p e r s u b s e t e v a l ：( 5 )为c h i s q u a r e d a t t r i b u t e e v a l ；( 6 ) 为g a i n r a t i o a t t r i b u t e e v a l ； ( 7 ) 为i n f o g a i n a t t r i b u t e e v a l ：( 8 ) 为o n e r a t t r i b u t e e v a l ；( 9 ) 为p r i n c i p a i c o m p o n e n t s ；( 1 0 ) 为 r e l i e f a t t r i b u t e e v a l ；( 1 1 ) 为s v m a t t r i b u t e e v a l ：( 1 2 ) 为s y m m e t r i c a l u n c e r t a t t r i b u t e e v a l 。 4 5在w e k a 平台下执行属性选择方法 在w e k a 中属性选择方法既可以单独执行，也可以和某种分类算法结合起来执 行。前者输出的是属性选择算法的结果，后者输出的是分类正确率等统计信息， 也可以以此来对属性选择方法进行比较。 单独执行属性选择主要有命令行和图形界面两种方式： 1 ) 命令行执行属性选择方法 运行“c m d e x e ”，进入w e k a 的“c l a s s ”文件所在的目录。在该目录下，键 入“j a v aw e k a a t t r i b t e s e l e c t i o n a t t r i b u t e s e l e c t i o ns t r i n g a - is t r i n g b - ss t r i n g c ”， 然后回车。其中，s t r i n g a 是属性选择算法的类名，s t r i n g b 是训练集合的文件名， s t r i n g c 是子集搜索算法的类名。在s t r i n g a 和s t r i n g c 中还可以包括算法相应的参 数。图4 4 给出了一个单独运行属性选择算法的例子。 4 3 北京交通大学硕士学位论文 罔44 单独运行属性选择方法 f 1 9 44 r u na m i b u t es e l e c t i o na l g o r i t h ma l o n e 2 1 图形界面中执行属性选择方法 舢从w e k a 主界面中进入e x p l o r e r 界面 b 1 在e x p l o r e r 界面巾选择训练集合，如图45 所示点击“o p e nf i l e ”按 钮浏览并选择文件，这里选择的是a u t o sa r f f 数据集。如果选择的数据 集还需要经过些处理( 比如离散化) ，则在选择了数据集| 三l 后可以 点击“f i l t e r s ”下面的“c h o o s e ”按钮来选择所要使用的过滤方法。 罔45 选择数据集 f i g u r e4 5 c h o o s e d a t as cc w e k a 平台下属性选择方法的分析 c ) 选择好计l 练数据集后进入属性选择选项卡，井选择属性评价方法和属 性子集搜索算法，通过鼠标右键点击评价方法和搜索算法可以设置运 行参数。这里以c f s s u b s e t e v a l 属性评价方法和b c s t f i l s t 搜索算法为 例，如图4 6 所示。 图4 6 选择评价方法 f i g u r e46 c h o o s e a t t r i b u t e e v a l u a t o r d ) 接下来选择类属性和交叉验证相关参数，这里选择“p l a y ”为类属性 属性全集为验证集合如图4 7 所示。 o v e f v a j “ o c r 6 s s l 3 i d a t i 。 。m ) n w 冀 = 三二 弧 r j 川- l t0 l 女t 一“e a ro p ) 图4 7 选择类属性 f i g u r e 7 4 c h o o s e c l a s s e ) 点击“s t a r t ”( 如图47 所示) 按钮可以运行属性选择程序最终选 择的结果为属性o u t l o o k 和w i n d y ，输出结果如图48 所示。 北京交通大学硕士学位论文 s 1 警 图48 属性选择结果 f 倒48 a t t r i b u t es e l e c t i o n o u t p u t 将属性选择方法和分类算法结合执行的方法也有两种，即在命令行方式下执 行和在界面中运行。 1 ) 命令行方式下将属性选择方法和分类算法结合执行 运行“c m de x e ”，进入w e k a 的“c l a s s ”文件所在的目录。在该目录下，键 入“j a v aw e k a c l a s s i f i e r s r e c t a a t t r i b u t e s e l e e t e d c l a s s i f i e r - es t r i n g a - - ts t f i n g b - - s s 砸n g c - ws t r i n 由”，然后回车。其中，s t r i n g a 是属性选择方法的类名，s t r i n g b 是训练数据集的文件名，s t r i n g c 是子集搜索算法的类名，s t r i n g d 是分类算法的类 名。在s t r i n g a ，s t r i n 薛，s t r i n g d 中还可以包含相应算法的参数，s i n g h ，s u n 班 的参数直接放在类名之后，s t r i n g d 的参数直接放在类名之后，并用“一”将两部 分分隔开来。图4 9 给出了一个在命令行方式下属性选择方法与分类算法结合执行 的例子。 w e k a 平台下属性选择冉法的分析 图49 与分类算法结合运行属性选择方法 f i 9 4 9 r u na t i t _ i b u t e 骈l 钟n o na l g o r i t h m w i t hc l a s s i f i c a t i o na l g o r i t h m 2 ) 界面方式下将属性选择方法和分类算法结合执行 在图形界面方式下执行属性选择方法和分类算法的结果如图4 】o 北京交通大学硕士学位论文 图41 0 界面下分类算法与属性选择算法结台运行的结果 f i 9 41 0 0 u t p u t o f a 卅i b u t e 钟l e c t i o n a l g o r i t h m w i t hc l a s s i f i c a t i o na l g o r i t h m 几种属性选择方法的比较与分析 5 几种属性选择方法的比较与分析 在这一章中，首先描述一种基于信息增益和遗传算法相结合的属性选择方法， 该方法使用遗传算法作为子集搜索方法，使用信息增益( i n f og a i n ) 算法作为子集 的评价算法。之后，对该方法和其他几种属性选择方法进行比较和分析。 5 1信息增益作为评价方法 在信息论中，信息是系统有序程度的一个度量，信息熵定义为：h ( x ) = - x n f 节阮) 幸l o gm j ，式中而为随机事件独立出现的可能状态在使用信息增益作为评价方 法时，使用的计算公式如( 5 1 ) 所示 缱二蚓闭咖卅潮明叼咖 e r t n 纠k = - j ( 5 1 ) 条件熵的定义是：如果仪y 冲( 五力，那么条件熵坝的定义为：般印j f ) = 一以，y ) 幸l o g 及y i 功在使用信息增益作为评价方法时，使用的计算公式如( 5 2 ) 所示 跏f 】阴) 川翻 删= 1 面矿 ( 5 2 ) 根据上面已经给出的信息熵和条件熵的定义，我们可以很容易的得出信息增 益的计算公式是：心y ) = 域玲同闭功在使用信息增益作为评价方法时，相应的 计算公式如( 5 3 ) 所示 励白国埘明= 倒删一彻诏酬明( 5 3 ) 其中，c o u n t s k i 【， 是存储每个属性值在每个类值下的计数值的数组，数组中的七 表示属性，i 代表属性值，代表类值实例集的每个实例分配一个为l 的权值， 然后将其加到满足上述三个条件的c o u n t s k 阴中 信息增益算法在计算属性的信息时有很良好的表现。使用信息增益来做属性 子集的评价算法有一些需要解决的问题。由于信息增益方法适用于计算单个属性 的信息增益，如何计算属性子集的信息增益是一个必须解决的问题。在计算属性 子集的信息增益时必须考虑到属性之间的相关关系。我们假设属性之间存在线性 相关关系，并使用累加和的方法来计算属性子集的信息增益。首先计算属性集合 4 9 北京交通大学硕士学位论文 中每个属性的信息增益，然后按照求和的方法，对每个属性子集求得信息增益。 将所得的信息增益作为属性子集的适应值。然后从种群中选择信息增益最大的个 体，作为适应性最好的个体。在最终的搜索结束后，返回搜索空间中搜索到的信 息增益最大的个体作为最后的返回值。 所以，使用信息增益的属性选择方法是使用遗传算法来产生属性子集，用信 息增益作为评价属性子集的评价方法。 5 2使用信息增益和遗传算法的实现 使用信息增益和遗传算法的属性选择方法的实现需要分别实现这两个类，即 用作搜索方法的g a 0 类和用作评价子集方法的i n f o g a i n s u b s e t e v a l 0 类。接下来详 细讨论这两个类的实现。 首先来看搜索方法g a 0 类。 在w e k a 平台上实现g a 0 类，首先需要继承a s s e a r c h o 类，并在程序中实现 s e a r c h ( ) 方法。这个方法是实现对子集空间搜索的主方法。为了要实现使用遗传算 法的方法进行搜索，在该类中还实现了i n i t i a l i z e ( ) ，m u t a t i o n ( ) ，c r o s s o v e r ( ) ， e v a l u a t e p o p u l a t i o n ( ) ，s e l e c t i o n ( ) ，r e p l a c e ( ) 方法。由于在初始化的过程中采用的是 随机的对种群中的个体赋值0 和l ，为了防止种群中所有的个体都是0 的情况，在 实现的过程中还加入了一个方法a d j u s t m e n t ( ) ，该方法检测在种群中所有的个体都 是o 时做出相应的调整。 在程序的实现过程中，我们采用二维数组来保存整个种群，其中，二维数组 的行数代表的是种群的规模，列数代表每个个体的长度。个体的长度等于数据集 合中非类属性的个数，个体中第f 个位置取值为l 表示第f 个属性在该子集中出现， 否则表示该属性没有出现在这个个体中。 在程序的参数设置上面，整个算法迭代的次数默认值是1 0 0 次。这个值不能 设置的太小，太小的时候不能保证遗传算法对整个属性子集的空间进行完全的搜 索，由于种群大小的默认值是1 0 ，所以1 0 0 次的迭代基本上可以保证对于属性子 集空间的搜索。 在遗传操作的使用上，我们结合使用了交叉操作和变异操作。由于在实际的 自然界中，变异的概率是很低的。如果变异的概率太低，那么算法对属性空间的 搜索会过于缓慢，在本程序中，我们采用的默认值是o 0 2 ，但如果变异的概率太 高则会造成个体在搜索空间来回摆动，会造成算法的不稳定，故而变异的概率不 应该设置的很大。当然，在程序的运行过程中，允许通过参数c 来设置变异的概 率。在变异的实现中，我们使用的是结合变异的概率产生一个随机数，使用这个 几种属性选择方法的比较与分析 随机数作为变异基因出现的位置。对一个种群而言，只允许变异出现在一个等位 基因上。要实现交叉操作，首先需要从种群中选择两个进行交叉操作的父体，在 父体的选择时，我们采用的方法还是产生随机数的方法。产生的随机数的范围限 制在o 一种群大小。在选择好这两个父体之后，还需要产生一个随机数( 范围限制 在o 一个体大小) ，用这个随机数作为进行交叉操作的交叉点。选择好交叉操作的 父体和交叉点后，就可以执行交叉操作。交义操作的结果是产生两个新的个体， 其中一个个体含有第一个父体的前半部分和第二个父体的后半部分，另一个个体 含有第一个父体的后半部分和第二个父体的前半部分。交叉操作的执行过程如图 5 1