（计算机应用技术专业论文）基于粗糙集合的属性选择方法研究.pdf

中文摘要 数据挖掘是从2 0 世纪9 0 年代以来迅速发展起来的一门新兴技术其处理对 象是大量的日常业务数据，耳的是将隐含的、尚不为人知的，同时又是潜在有用 的信息从数据中提取出来机器学习为数据挖掘的实现提供了理论基础，包括从 原始数据库中提取信息，并以可理解的形式表达知识，进而适用于各种用途机 器学习算法对其处理的数据集合一般都有一定要求，比如数据完整性好、数据冗 余性少、属性之间相关性小等然而，日常业务数据中一般都可能具有不完整性、 冗余性和模糊性等特点目自口解决这一问题的有效手段是在执行机器学习算法之 前对数据进行预处理，去掉不完整或冗余的数据 属性选择是数据预处理的一个重要环节一种好的属性选择算法可以对数据 集进行降噪与降维，使机器学习算法具有更好的效果目前属性选择已经成为国 内外研究的热门话题之一，已经有一些行之有效的属性选择算法粗糙集合理论 是一种描述不完整性和不确定性的数学工具，在机器学习与知识发现、决策支持 与分析等方面有着广泛的应用粗糙集合理论的精髓是数据约简，利用数据约简 可以处理属性选择问题，目前已有一些属性选择算法的研究开始关注于应用粗糙 集合理论，并初步得到实验验证 本文首先介绍了属性选择的相关技术，包括属性选择中非常关键的属性评价 方法和属性搜索算法其次，叙述了本文所涉及的粗糙集合理论的基本概念，特 别分析了粗糙集合理论中的数据约简和利用区分矩阵计算约简的基本方法进而， 在剖析数据挖掘开源工具w e k a 系统中的属性选择实现的相关内容的基础之上，提 出了一种新的属性选择算法，该算法以粗糙集合理论中的核集作为属性选择的初 始集合，以对称不确定性作为属性评价方法，综合考虑了属性与类之间和属性与 属性之间的相关性最后，在实验中用n a i v eb a y e s 分类算法和c 4 5 决策树算法 作为属性选择结果的评价器，在属性选择后的新数据集和原始数据集上分别运行 上述两种算法，最后将各自的分类结果进行比较得出结论由于此方法保留了对 机器学习贡献较大的核集属性因此在具有核集属性的数据集上比其他利用空集作 为初始集合的属性选择算法有更好的属性选择效果 关键词：数据挖掘；属性选择；粗糙集合；w e k a ；属性评价 分类号：t p 3 0 1 6 a b s t r a c t d a t am i n i n gi san e wt e c h n o l o g yw h i c hd e v e l o p e dr a p i d l yf r o m1 9 9 0 s i td e a l s w i t hl o t so fd a i l yo p e r a t i o nd a t aw i t ht h eo b j e c t i v et oe x t r a c tp o t e n t i a lu s e f u lb u t u n k n o w ni n f o r m a t i o nf r o mt h er a wd a t a m a c h i n el e a r n i n gp r o v i d e st h e o r e t i c a lb a s i cf u r d a t am i n i n g , i n c l u d i n ge x t r a c t i n gi n f o r m a t i o nf r o mo r i g i n a ld a t a b a s ea n de x p r e s s i n gi t i nc o m p r e h e n s i b l ew a y m a c h i n el e a r n i n ga l g o r i t h ma l w a y sh a ss t r i c tr e q u i r e m e n to f d a t as e ts u c ha sg o o di n t e g r i t y , l i t t l er e d u n d a n c y ，w e a kc o r r e l a t i o na n ds o0 1 1 h o w e v e r , t h ed a i l yd a t ai sa l w a y sn o ts a t i s f a c t o r yl i k et h a t c u r r e n t l yd a t ap r e p r o c e s s i n gi st h e e f f e c t i v ew a yt or e d u c er e d u n d a n to ri n c o m p l e t ed a t ab e f o r ee x e c u t i n gt h ea l g o r i t h m f e a t u r es e l e c t i o ni sa ni m p o r t a n tc o m p o n e n to fd a t ap r e p r o c e s s i n g , ag o o df e a t u r e s e l e c t i o na l g o r i t h mc a nr e d u c en o i s ea n dd i m e n s i o no fd a t as e t ss oa st om a k eag o o d e f f e c tt om a c h i n el e a r n i n ga l g o r i t h m n o w a d a y s ，f e a t u r es e l e c t i o nh a sb e c o m eah o t r e s e a r c ht o p i ca n dt h e r ea r e a l r e a d y s o m ew e l l - e s t a b l i s h e d a l g o r i t h m sh a v eb e e n p r o p o s e d r o u g hs e tt h e o r yi sam a t h e m a t i c a lt o o lw h i c hc h a r a c t e r i z i n gi m p r e c i s e ， u n c e r t a i n t ya n da l lk i n d so fi n c o m p l e t ei n f o r m a t i o n i th a sb e e nw i d e l yu s e di nm a c h i n e l e a r n i n g , k n o w l e d g ed i s c o v e r y , d e c i s i o ns u p p o aa n do t h e ra r e a s t h ee s s e n c eo fr o u i g h s e tt h e o r yi sd a t ar e d u c t i o nw h i c hc a l lb eu s e df o rf e a t u r es e l e c t i o nh a sa l r e a d yb e e n a p p l i e dt os o m ea l g o r i t h m ss u c c e s s f u l l y t h i st h e s i sf i r s ti n t r o d u c e sf e a t u r es e l e c t i o nr e l a t e d t h e o r yi n c l u d i n gf e a t u r e e v a l u a t i o na n ds e a r c hm e t h o d s s e c o n d l y , t h eb a s i cc o n c e p t so fr o l l g hs e tt h e o r y e s p e c i a l l yt h ed a t ar e d u c t i o na n dg e t t i n gr e d u c t i o nw i t hd i s c e r n i b i l i t ym a t r i xh a v eb e e n d e s c r i b e d t h i r d l y , b a s i n go nt h ec o n t e n to ff e a t u r es e l e c t i o nr e l a t e di nw e k aw h i c hi s a l lo p e ns o u r c ed a t am i n i n g t o o l ，w ep r o p o s ean e w f e a t u r es e l e c t i o na l g o r i t h mb a s e do n r o u g hs e tt h e o r y , w h i c hv i e w e dt h es e to fc o r ef e a t u r e sa st h ei n i t i a ls e t a n dd e f i n ea s y m m e t r i c a lu n c e r t a i n t ym e a s u r e m e n tm e t h o da sf e a t u r e sc o r r e l a t i o ne v a l u a t i n g c r i t e r i o n t h e a l g o r i t h mc o n s i d e r sr e l a t i o n s h i pn o to n l yb e t w e e na t t r i b u t e sb u ta l s o b e t w e e na t t r i b u t ea n dc l a s s a tl a s t ，n a i v eb a y e sa n dc 4 5w e r eu s e dt oe v a l u a t et h e r e s u l to ff e a t u r es e l e c t i o ni nt h ee x p e r i m e n tt h e nc a r r i e do u tt h ec o n c l u s i o n e x p e r i m e n t a lr e s u l t sh a v es h o w nt h a tt h i sa l g o r i t h mh a db e t t e rp e r f o r m a n c eo nt h ed a t a w i t hn o n e m p t yf e a t u r ec o r es e t st h a nt h ep r e v i o u sa l g o r i t h m s k e y w o r d s ：d a t am i n i n g ；f e a t u r es e l e c t i o n ；r o u g hs e t ；w e k a ；f e a t u r ee v a l u a t i o n c i a s s n o ：t p 3 0 1 6 致谢 本论文的工作是在我尊敬的导师王志海教授的悉心指导下完成的，王志海教 授严谨的治学态度和科学的工作方法给了我极大的帮助和影响在此衷心感谢三 年来王志海老师对我的关心和指导 衷心感谢黄厚宽和田盛丰教授，两位教授宽广豁达的长者风范、以及严谨的 治学态度始终让我深深地敬仰他们在此期间对我的关心和鼓励让我深受感动 林友芳老师悉心指导我完成了实验室的科研工作，在学习上和生活上都给予 了我很大的关心和帮助，在此向林友芳老师表示衷心的谢意 瞿有利老师，魏名元老师对于我的科研工作和论文都提出了许多的宝贵意见， 在此表示衷心的感谢 在实验室工作及撰写论文期间，丁久玲、王永峰、赵晓伟等同学对我论文中 的数据挖掘研究工作给予了热情帮助，在此向他们表达我的感激之情 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业 最后，衷心地感谢在百忙之中审阅论文的各位老师和专家，恳请各位老师多 多批评指正，并提出宝贵的意见 1 1 课题背景 1 引言 2 0 世纪9 0 年代以来，随着信息技术和数据库技术的迅猛发展，人们可以非常 方便廉洁地获取和存储大量的数据，1 9 9 1 年有人预测全球的数据存储量每隔2 0 个 月要增长一倍如此大规模的海量的数据背后隐藏着许多重要的信息，传统的数 据分析工具( 如管理信息系统) 只能进行一些表层的处理( 如查询、统计等) ，而 不能获得数据之间的内在关系和隐含的信息为了摆脱“数据丰富，知识贫乏” 的困境，人们迫切需要一种能够智能地自动地把数据转换成有用信息和知识的技 术和工具，计算机技术的迅速发展和这种对强有力数据分析工具的迫切需求使得 数据挖掘技术应运而生数据挖掘工具能够对将来的趋势和行为进行预测，从而 很好地支持人们的决策，有些数据挖掘工具还能够解决一些很消耗人工时间的传 统问题，因为它们能够快速地浏览整个数据库，找出一些专家们不易察觉的极有 用的信息 数据挖掘的处理对象是大量的日常业务数据，目的是为了从这些数据中抽取 一些有价值的知识或信息原始业务数据是知识和信息提取的源泉，对于数据挖 掘十分重要，目前所进行的关于数据挖掘的研究工作，大多数着眼于数据挖掘算 法的探讨而忽视了对数据处理的研究一些比较成熟的算法对其处理的数据集合 一般都有一定的要求，比如数掘完整性好、数据的冗余性少，属性之间的相关性 小然而，实际系统中的数据一般都具有不完全性、冗余性和模糊性，很少能直 接满足数据挖掘算法的要求另外，海量的实际数据中无意义的成分很多，严重 影响了数据挖掘算法的执行效率，而且由于其中的噪声干扰还会造成无效的归 纳因此，在应用数据挖掘算法前，首先需要对数据进行预处理，去掉无关属性 减小属性之间的相关度，即进行属性选择，有着很重要的意义 属性选择通常作为数据挖掘的一个预处理步骤，在数据选择和为数据挖掘做 准备的过程中起着重要的作用这个过程是从原属性集合中删除不相关和( 或) 冗余的属性选出属性子集，以便根据确定的准则使属性空间得到最优的约简从 上个世纪七十年代以来，在统计模式识别、机器学习和数据挖掘等领域，属性选 择已经成为一个研究与开发成果丰富的领域，并且已经证明，在删除不相关和冗 余的属性、增加学习任务的效率、提高学习的性能( 预测的精度) 和增强学习结 果的可理解性等方面它是有效的 1 2 本文所完成的工作 本文围绕属性选择问题展开讨论，研究了w e k a 中的属性选择相关内容和基于 相关性属性选择的评价方法并基于粗糙集合理论和对称不确定性属性评价方法 提出了一种新的属性选择算法，并通过实验得出该算法在具有核集属性的数据集 上进行属性选择具有很好的效果 1 3 论文组织安排 本文的主要框架和结构如下： 第1 章给出了课题的出发点以及研究的问题及范围，分析了数据挖掘面临的 问题和属性选择的研究现状，介绍了本文所完成的工作 第2 章是全文的理论基础，分别介绍了数据挖掘、属性选择和粗糙集合理论 的相关知识，包括数据挖掘的定义，数据挖掘的起源和数据挖掘的方法；属性选 择的步骤，属性选择的各种常用方法；粗糙集合的相关定义，如何利用分明矩阵 计算属性核集，以及粗糙集合在属性选择中的应用等等 第3 章介绍了著名的开源数据挖掘软件w e k a ，分析了w e k a 的架构并着重 分析了w e k a 中属性选择的相关内容，包括w e k a 中属性选择的评价方法、搜索算 法和实现方式等 第4 章是介绍了几种基于相关性的属性选择评价方法，其中包括了线性相关 性属性评价方法、r e l i e f 算法和本文第五章中c b s u 算法所用到的基于信息熵的对 称不确定性属性评价方法，本章为后续属性选择算法提供了属性评价的理论基础 第5 章是本文的核心部分，本文基于粗糙集合理论和对称不确定性属性评价 方法提出了一种新的属性选择算法c b s u ，并通过实验验证了该算法在具有核集的 数据集上的表现优于其他基于对称不确定性属性评价的属性选择算法，在没有核 集的数据集上的属性选择效果与其他算法保持一致 第6 章总结全文，对本课题研究做了分析和总结，并给出了本课题将来的研 究内容和方向 2 2 1 数据挖掘 2 相关理论综述 2 1 1 数据挖掘的概念和定义 随着计算机技术的迅猛发展以及网络的普及，许多行业如商业、企业、科研 机构和政府部门等都有了更多的机会和便捷的方法与外界进行信息交流，数据库 的规模、范围和深度都在快速不断扩大，从而积累了海量的、以不同形式存储的 数据资料，同时在许多领域也建立了数据仓库在这些海量数据中往往隐含着各 种各样的信息，这些信息人们往往凭直觉与经验是难以发现的如何从大量的数 据中获得有价值的信息，采用传统的数据库技术已显得无能为力了，数据的快速 增长与数据分析处理方法滞后的矛盾越来大，人们希望能够在对已有的大量数据 分析的基础上进行科学研究、商业决策或企业管理，从而达到为决策服务的目 的，数掘挖掘就是为了满足这种需求而迅速发展起来的一种新的数据处理技术它 的实质是一种发现知识的应用技术，是一个提取有用信息的过程自2 0 世纪末提 出一来，引起了许多专家学者的广泛关注，并应用到金融、零售业、工业过程、 电力、医疗保健和政府决策等各个领域，取得了良好的社会效益和经济效益，具 有广阔的开发和应用前景 目前数据挖掘的通用定义是指从大量的、不完全的、有噪声的，模糊的、随 机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用 的信息和知识的过程数据挖掘要解决的问题就是在庞大的数据中寻找有价值的 隐藏信息，加以分析，并将这些有意义的信息归纳成结构模式，提供给有关人员 在决策时参考l l j 人们已经证明，数据发掘技术能够发现和跟踪数据集合中潜在的模式，因此， 有人认为，在数据库中，处理隐藏的知识、不可预料的模式和新规则的发现的所 有方法中，数据挖掘是最有效的如果没有数据挖掘技术，许多数据就很可能停 留在未使用的阶段正是数据挖掘能够为企业提供了全面、深入地分析和了解客 户及其行为特征的重要助臂 在商业的角度上1 2 l ，数据挖掘是一种新的商业信息处理技术，其主要特点是对 商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提 取辅助商业决策的关键性数据简而言之，数据挖掘其实是一类深层次的数据分 3 e 基銮堕盔堂亟堂鱼途塞翅羞堡迨筮蕉 析方法数据分析本身已经有很多年的历史，只不过在过去数据收集和分析的目 的是用于科学研究，另外，由于当时计算能力的限制，对大数据量进行分析的复 杂数据分析方法受到很大限制现在，由于各行业业务自动化的实现，商业领域 产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于纯 机会的商业运作而产生分析这些数据也不再是单纯为了研究的需要，更主要是 为商业决策提供真正有价值的信息，进而获得利润但所有企业面临的一个共同 问题是：企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数 据中经过深层分析，获得有利于商业运作、提高竞争力的信息，就像从矿石中淘 金一样，数据挖掘也因此而得名因此，数据挖掘又可以描述为：按企业既定业 务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的 规律性，并进一步将其模型化的先进有效的方法 2 1 2 数据挖掘的功能 为了解决日益更新的海量数据对传统的数据分析技术所带的挑战，来自不同 学科的研究者汇集在一起，开始着手开发可以处理不同数据类型的更有效的、可 伸缩的工具这些工作建立在研究者先前使用的方法学和算法之上，在数据挖掘 领域达到高潮特别的，数据挖掘利用了来自如下一些领域的思想：( 1 ) 来自统计 学的抽样、估计和假设检验；( 2 ) 人工智能、模式识别和机器学习的搜索算法、建 模技术和学习理论数据挖掘也迅速地接纳了来自其他领域的思想，这些领域包 括最优化、进化计算、信息论、信号处理、可视化和信息检索 一些其他领域也起到重要的支撑作用特别的，需要数据库系统提供有效的 存储、索引和查询处理支持源于高性能( 并行) 计算的技术在处理海量数掘集 方面常常是重要的分布式技术也能帮助处理海量数据，并且当数据不能集中到 一起处理时更是至关重要 图2 1 数据挖掘是许多学科的汇集 f i g u r e2 1d a t am i n i n gi sam i xo fm a n yd i s c i p l i n e s 4 e 丞銮迪厶鲎亟堂僮迨塞担羞堡途绽述 数据挖掘综合了各个学科技术，有很多的功能，当前主要有以下五类功能： 1 ) 分类：按照分析对象的属性、特征，建立不同的组类来描述事物例如： 银行部门根据以前的数据将客户分成了不同的类别，现在就可以根据这些 来区分新申请贷款的客户，以采取相应的贷款方案 2 ) 聚类：数据库中的记录可被划分为一系列有意义的子集，即聚类聚类增 强了人们对客观现实的认识，是概念描述和偏差分析的先决条件聚类技 术主要包括传统的模式识别方法和数学分类学2 0 世纪8 0 年代初， m c h a l s l d 提出了概念聚类技术其主要特点是，在划分对象时不仅考虑对象 之间的距离，还要求划分出的类具有某种内涵描述，从而避免了传统技术 的摹写片面性 3 ) 关联规则和序列模式的发现：关联是某种事物发生时其他事物会发生的这 样一种联系。例如：每天购买啤酒的人也有可能购买香烟，比重有多大， 可以通过关联的支持度和可信度来描述与关联不同，序列是一种纵向的 联系例如：今天银行调整利率，明天股市的变化 4 ) 预测：数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量 手工分析的问题如今可以迅速直接由数据本身得出结论一个典型例子是 市场预测问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报 最大的用户，其他可预测的问题包括预报破产以及认定对指定事件最可能 做出反应的群体 5 ) 偏差的检测：数掘库中的数据常有一些异常记录，从数据库中检测这些偏 差很有意义偏差包括很多潜在的知识，如分类中的反常实例、不满足规 则的特例、观测结果与模型预测值偏差、量值随时间的变化等偏差检测 的基本方法是，寻找观测结果与参照值之间有意义的差别对分析对象的少 数的、极端的特例的描述，揭示内在的原因 需要注意的是数据挖掘的各项功能不是独立存在的，而是互相联系发挥作用 2 1 3 数据挖掘的基本过程 数据挖掘的基本过程如图2 - 2 所示，由以下几个步骤组成： 1 ) 数据清理：数据清理的目的是消除噪声或不一致数据，对数据库中的重复 元组也需要进行清理f 3 】 2 ) 数据集成：数据集成是将多个数据源中的数据结合起来，存放在一个一致 的数据库中 3 ) 数据选择：从数据库中检索与挖掘任务相关的数据，创建相关的目标数据 集，即选择数据集合或数据样本的一个子集，删除数据中有误的和无关的 部分 4 ) 数据变换：将数据变换或统一成数据挖掘工具所需要的形式 5 ) 数据挖掘：运用各种知识发现算法，从数据中提取出用户需要的知识，这 些知识可以用同一种特定的方式表示或使用一些常用的方式表达，如产生 式规则等等 6 ) 模式评估：根据某种兴趣度度量、解释所得的模型，识别能真正有效地表 示知识的模式，必要时应当反复进行数据挖掘这一步 7 ) 知识表示：使用可视化和知识表示技术，将得到的知识以用户能了解的方 式呈现给用户，这其中包括对知识一致性的检查，以保证本次发现的知识 不与以前发现的知识相抵触 2 1 4 数据挖掘的方法 图2 2 数据挖掘的基本过程 f i g u r e2 2t h eb a s i cp r o c e s so f d a t am i n i n g 数据挖掘的方法很多，每种方法都有其特定适用领域某一种方法不可能胜 任所有的数据挖掘任务，一个复杂的数据挖掘系统常常采用多种数据挖掘方法， 通过整合多种数据挖掘方法来弥补不同数据挖掘方法所存在的不足数据挖掘的 方法主要有以下几种： 6 1 1 基于决策树的方法 决策树是建立在信息论基础之上，对数据进行分类的一种方法首先，通过 一批己知的训练数据建立一棵决策树然后，利用建好的决策树，对数据进行预 测决策树的建立过程可以看成是数据规则的生成过程，因此可以认为，决策树 实现了数据规则的可视化，其输出结果也容易理解决策树方法精确度比较高， 结果容易理解，效率也比较高，因而比较常用构建决策树的算法很多，其中最 具代表性的是c a r t 和c 4 5 算法 2 ) 基于神经网络的方法 神经网络最早是由心理学家和神经生物学家提出的神经网络是大量的简单 神经元按一定规则连接构成的网络系统网络能够模拟人类大脑的结构和功能， 采用某种学习算法从训练样本中学习，并将获取的知识存储在网络各单元之间的 连接权中神经网络和基于符号的传统人工智能技术相比，具有直观性、并行性 和抗噪声等优点目前己出现了多种网络模型和学习算法，主要用于分类、优化、 模式识别、预测和控制等领域在数据挖掘领域，主要采用前向神经网络提取分 类规则 3 1 基于遗传算法的方法 遗传算法是一种基于生物进化论和分子遗传学的搜索优化算法它首先将问 题的可能的解按某种形式进行编码，编码后的解称为染色体；随机选取n 个染色 体作为初始种群，再根据预定的评价函数对每个染色体计算适应值，性能较好的 染色体有较高的适应值；选择适应值较高的染色体进行复制，并通过遗传算子， 产生一群新的更适应环境的染色体，形成新的种群，直至最后收敛到一个最适应 环境的个体，得到问题的最优化解 4 1 贝叶斯方法 贝叶斯网络是由r h o w a r d 和j m a t h e s o n 于1 9 8 1 年提出的，它是一种概率推 理方法，它能从不完全、不精确和不确定的知识和信息中做出推理，可以处理不 完整和带有噪音的数据集，解决了数据间不一致和相互独立的问题贝叶斯分类 是统计学分类方法它可以预测类成员关系的可能性一种比较简单的朴素贝叶 斯方法是一种基于概率的分类方法，它通过样本的属性值计算事例属于某一个类 的可能性，然后，将样本归属到最有可能的类中朴素贝叶斯分类在应用于大型 数据库时，表现出高准确率和高速度 5 ) 基于粗糙集的方法 粗糙集作一种软计算方法，它可以不需任何辅助信息，如统计学中的概率分 布、模糊集中的隶属度等，仅依据数据本身提供的信息就能对数据进行化简并求 得知识的最小表达粗糙集方法可以克服传统的不确定信息的处理方法的不足， 7 并且能和它们有机结合，进一步增强对不确定、不完全信息的处理能力粗糙集 方法首先用近似的方法把信息系统中的属性值离散化，然后对每一个属性划分等 价类，再利用集合的等价关系进行信息系统的属性约简，最后得到一个最小决策 关系，便于获得规则目前成熟的关系数据库管理系统和新发展起来的数据仓库 管理系统为基于粗糙集的数据挖掘奠定了坚实的基础 2 2 属性选择 2 2 1 属性选择概述 属性选择问题是分类、数据挖掘、图像处理、概念学习等等许多不同领域的 基础近年来，知识发现和数据挖掘方法在实际应用中不断增长的重要性，使得 属性选择问题成为十分热门的话题，尤其是在考虑从现实世界的数据库或数据仓 库中挖掘的时候，由于它不仅包含数量巨大的记录，而且包含大量的与挖掘任务 不相关的属性，属性选择就更加重要 有些数据属性对发现任务是没有影响的，这些属性的加入会大大影响挖掘效 率，甚至还可能导致挖掘结果的偏差因此，有效的缩减数据是很有必要的数 掘简化是在对发现任务和数据本身内容理解的基础上，寻找依赖于发现目标的表 达数据的有用特征，以缩减数据规模，从而在尽可能保持数据原貌的自i 提下最大 限度地精简数据量它主要有两个途径：属性选择和数据抽样，分别针对数据库 中的属性和记录 属性选择是指在初始的个属性中选择出一个有小( 肌 ) 个属性的子集， 这m 个属性可以像原来的个属性一样用来正确区分数据集中的每一个数据对 象随着域维度的增大，属性的数量也在不断增大发现最优属性子集通常是难 以实现的【4 】许多与属性选择相关的问题都已被证明是n p - h a r d 问题【5 1 由于无关属性在多数机器学习方案中存在负面影响，通常在学习之前先进行 属性选择，只保留一些最为相关的属性，而将其他属性都去除选择相关属性最 好的方法是人工选择，它是基于对学习问题的深入理解以及属性的真正含义而做 出的选择然而，自动方法也是很有用的通过去除不适当的属性以降低数据的 维度，能改善学习算法的性能还能提高速度，即使属性选择可能会带来很多计 算更重要的是，维度的降低能形成一个更为紧凑，更易理解的目标概念表达方 式，使用户的注意力集中在最为相关的变量上 2 2 2 属性选择基本步骤 8 一般说来，属性选择算法由四个基本步骤组成：子集产生、子集评估、停止 准则和结果有效性验证【6 1 如图2 3 所示 图2 3 属性选择基本步骤 f i g u r e2 3b a s i cs t e p so f a t t r i b u t es e l e c t i o n 子集产生是一个搜索过程，它产生用于评估的属性子集设表示原数据集 属性的数量，那么全部候选子集的数量是少，这使得即使是中等的，对整个属 性空问进行穷尽式搜索也是不可行的 子集产生过程所生成的每个子集都需要用事先确定的评估准贝进行评估，并 且与先前符合准则最好的子集进行比较，如果它更好一些，那么就用它替换前一 个最优的子集如果没有一个合适的停止规则，在属性选择进程停止前，它可能 无穷无尽地运行下去属性选择过程可以在满足以下的条件之一时停止：一个预 先定义所要选择的属性数、预先定义的迭代次数、是否增加( 或删除1 任何属性都不 产生更好的子集、已经根据确定的评估标准获得最优的子集选择的最优子集需 要通过在所选子集和原属性集进行不同的测试和比较，使用人工和现实世界的数 据集所产生的结果进行有效性验证 研究人员已经研究了属性选择的不同方面搜索是属性选择研究的关键问题【7 ， 踟，例如搜索起始点、搜索的方向和搜索策略另一个重要的方向是如何评估属性 子集的优势度i s , 9 】 2 2 3 搜索属性空间 属性选择通过删除不相关的属性( 或维) 减少数据量通常使用属性子集选 择方法属性子集选择的目标是找出最小属性集，使得数据类的概率分布尽可能 地接近使用所有属性的原分布 “如何找出原属性集合的一个好的子集? ”d 个属性有r 个可能的子集穷 举搜索找出属性的最佳子集可能是不现实的，特别是当d 和数据类数目增加时因 此，对属性子集选择，通常使用压缩搜索空间的启发式算法通常，这些算法是 贪心算法，在搜索属性空间时，总是做看上去是最佳的选择他们的策略是做局 部最优选择，期望由此导致全局最优解在实践中，这种贪心算法是有效的，并 可以逼近最优解 属性选择的大多数方法都要牵涉到在属性空间搜索最有可能做出最好类预测 的属性子集属性空间搜索主要考虑4 个方面的问题1 1 0 】：属性搜索的起始集合、 搜索算法、属性子集评价方法和搜索停止标准，不同的搜索方法对这4 个问题的 实现方式不同图2 4 展示了大家非常熟悉的天气数据的属性空间 图2 4 天气数据集的属性空间 f i g u r e2 4a t t r i b u t es p a c eo ft h ew e a t h e rd a t a s e t 基本上，属性子集的搜索方向是两个方向中的个，即图中从上往下或是从 下往上在每个阶段，通过增加或删除一个属性，来改变目前的属性子集朝下 的方向，开始时是不含任何属性，然后每次增加一个，称为正向选择朝上的方 1 0 向，开始时包含了所有属性，然后每次减少一个，称为反向消除【1 1 1 在正向选择时，每个当前子集没有包含的属性被暂时加入，然后对结果子集 的属性进行评估，譬如使用交叉验证方法评估产生一个数字结果用以衡量子集 的期望性能通过这个方法对依次添加每个属性所产生的结果进行定量，选择其 中最好的，然后继续如果向目前的子集中添加任何一个属性都不能有改善时， 即终止搜索这是一个标准的贪心搜索程序，能保证找到一个局部的，不必是全 局的、最好的属性集反向消除操作采用完全类似的模式在这两种情形中，对 于较小的属性集经常引用一个微小偏差在正向选择中，如果要继续搜索，评估 值的增加必须要超出某个预先设定的最小增量对于反向消除也采用类似的方法 还存在一些更为精细复杂的搜索算法正向选择和反向消除法可以结合成双 向搜索，同样一开始可以包含所有属性或者不含任何属性最佳优先搜索 ( b e s t f i r s t s e a r c h ) 不是在性能开始下降时停止搜索，而是保存到目前为止已经评 估过的所有属性子集清单，并按照性能衡量好坏排序的方法，因此它可以重访先 前的配置只要时间允许它将搜索整个空间，除非是采用某种停止标准限定范 围搜索( b e a ms e a r c h ) 也很类似，只是在每个阶段截取属性子集清单，因此它只 含有固定数目的束宽( b e a mw i d t h ) 中最有希望的候选对象i l z l 遗传算法( g e n e r i c a l g o r i t h m ) 搜索程序松散地基于自然选择原理，使用对当前的候选子集的随机摄 动，而“进化出”好的属性子集 2 2 4 属性选择方法 属性选择问题作为一个研究热点广泛应用于模式识别、统计学、机器学习等 领域，已经有很多国内外研究人员提出了独特的思想和解决方案【4 协1 7 1 ，这些方法 通常可分为两种，即过滤法和打包法1 4 j 过滤法是一种独立于学习算法的属性选择方法，按照某种标准进行属性的筛 选，一般有以下两种筛选标、准【”j ： 1 最小属性子集选择法 从待选属性子集中，选择一个包含属性最少的属性子集，因为通常意义上讲， 属性少的子集会降低时间和空间复杂度，提高学习算法的效率但这种方法也有 很大局限性，比如在对学校学生的学习成绩进行研究，其中的学号是学生的唯一 标识，如果按照这个选择标准，把学号这个单一属性作为候选虽然满足属性选择 的选择标准，但任何学习算法在此基础上进行学习的结果必然很差 2 根据某种评分标准进行属性选择 此种方法利用精确度、独立性、相关性、信息熵、距离等策略对属性进行评 1 1 分，但这种方法不能处理冗余属性 过滤法对学习算法的支持性不是很好，却以其计算的高效性，在高维属性选 择中得到很好的应用【1 “此外，由于其独立于学习算法，所以过滤法中提供的属 性选择方法也可应用于打包法中【1 4 1 打包法将学习算法作为测试用的黑盒子，利用相关的学习算法对属性子集进 行评价，例如，利用学习算法的交差验证进行属性子集评价1 4 】此种方法需要一个 属性子集搜索方法的支持，主要分以下几种搜索方式： 完全式搜索：也称为穷举搜索，它可以确保找到最优的属性子集但由于全 部可能的属性子集的数量是少，当属性数量变大时，这种搜索策略是不可行的 启发式搜索：由于穷尽式搜索受到限制，人们考虑利用启发式来引导搜索它 避免了全部的搜索，但同时也冒着丢失最优子集的风险由启发式指导进行的深 度优先的搜索排序的空间复杂度可能是d ( 2 ) 或更低利用启发式搜索策略的算 法非常易于实现，并且产生子集的过程非常快，因为搜索空间仅仅是属性数量的 平方关系 不确定搜索：与前面介绍的两种搜索策略不同，这种策略在搜索下一个集合 时是随机的( 即当前集合没有根据任何先前的集合按照确定的规则有方向地增长或 删减) 这种算法能够不断产生最好的子集，随着时间的推移不断提高所选子集的 质量尽管搜索空间仍然是d ) ，但是这种策略通过设置最大可能的迭代次数使 得搜索的子集数量远远小于所选子集的最优性取决于可利用的资源参考文 献1 4 中采用的就是这种方法 打包法的优点是对学习算法的支持度高，缺点是时间复杂度高，效率低 2 3 粗糙集合理论基础 2 3 1 粗糙集合概述 粗糙集( r o u g hs e t ) 理论【1 8 】是一种描述不完整性和不确定性的数学理论，最 早由波兰科学家乙p a w l a k 于1 9 8 2 年提出它从新的角度对知识进行定义，把知 识看作是关于论域的划分，从而认为知识是有粒度的，知识的粒度性是造成使用 已有知识不能精确表示某些概念的原因这就产生了所谓关于不精确的“边界” 思想著名哲学家f r e g e 认为“概念必须有明确的边界没有明确边界的概念，将 对应于一个在其周围没有明确界限的区域”粗糙集合理论中的模糊性就是种基 于边界的概念，即一个模糊的概念具有模糊的不可被明确划分的边界在没有掌 握所有关于对象域知识的情况下，只能用一对逼近来描述对象域上的集合【1 9 1 租糙集理论认为知识就是将对象进行分类的能力假定起初对全域里的元素 ( 对象) 具有必要的信息或知识，通过这些知识能够将其划分为不同的类别，若 对两个元素具有相同的信息，则它们就是不可区分的( i n d i s c e r n i b l e ) ，即根据已有 的信息不能够将其划分开，显然这是一种等价关系不可区分关系是粗糙集合理 论的最基本概念，在此基础上引入了成员关系、上近似和下近似等概念来刻画不 精确性与模糊性 粗糙集合与传统集合理论有相似之处，但是它们的出发点完全不同。传统集 合论认为：一个集合完全是由它的元素所决定，一个元素要么属于这个集合，要 么不属于这个集合模糊集合对此做了改进，它给成员赋予一个隶属度，使得模 糊集合能够处理一定的模糊和不确定数据，但是其模糊隶属度需要认为给定，这 给它的应用带来了不便传统集合论和模糊集合理论都是把成员关系作为原始概 念来处理，集合的并和交就建立在其元素的隶属度的所盯和m n 操作上，因此其 隶属度必须事先给定( 传统集合默认隶属度为1 或0 ) 在粗糙集合理论中，成员 关系不再是一个原始的概念，无需认为给元素指定一个隶属度，避免了主观因素 的影响 然而粗糙集合论和模糊集合理论并不是互相竞争的理论，而是互补的租糙 集合理论基于知识的不可区分性，模糊集合理论则侧重知识的模糊性不可区分 性和模糊性实际上是不完全知识的两个不同侧面不可区分性是指知识的粒度， 它影响所讨论的域的定义租糙集假定起初对全域里的元素( 对象) 有必要的信 息或知识，即通过这些知识能够将其划分为不同的类别若对两个元素具有相同 的信息，则它们就是不可区分的，即根据已有的信息不能够将其划分开模糊性 是由于自然语言的范畴经常是渐近的概念所导致，因此模糊性是指集合具有平滑 的边界借用图像处理中的例子说明，粗糙集是关于像素的大小，而模糊集是关 于多个灰度级别的存在；模糊集合理论依赖于表达成员关系的强度的有序关系， 而粗糙集是基于等价关系，这些等价关系表示由不可区分对象类所形成的划分因 此，他们之间有一定的区别，是一种自然的补充 粗糙集合理论经过二十余年的发展，已经广泛应用于数据挖掘、模式识别、 机器学习等研究领域并且该理论在属性选择与知识发现两个方向的研究已经广 泛应用于医学、控制系统、社会科学、转换电路和图像处理等一系列实际应用领 域【捌 2 3 2 粗糙集合相关定义 定义1 ：在粗糙集( r o u g hs e t ) 理论中，信息系统由r - - ( t r , 4cd ) 四元组表 示，其中u 是论域，代表所有实例的集合，爿是所有属性集合，c 和d 为爿的两 个子集且爿= c u d ，分别代表条件属性和决策属性另定义y 表示属性值集合，f 是u x a v 的映射 例如表2 1 所示的信息系统中，论域【，_ 缸“x 2 , x 3 ，x 4 ，x 5 ， ，条件属性c 毛和，b ， c ，决策属性d = 似 表2 1 一个信息系统 t a b l e2 1a ni n f o r m a t i o ns y s t e m 条件属性f决策属性口 abcd x t 32l2 x 2 2111 x , 12112 兄l111 厨 2221 3122 定义2 ：若a 4 ，p c _ a ，二元关系i n d ( p ) 被称作等价关系，定义如下： n 移( p ) = g ，y ) u 卅 c a p ，邵o ，) ) 其中五y 为论域【，中的实例，口 表示属性a 在实例工上的值如果0 ，y ) e i n d ( p ) ，则称x ，y 关于p 等价 定义3 ：u i n d ( p ) 称作论域u 在等价关系p 上划分的等价类的集合同样定 义u i n d 和u i n o ( d ) 为由条件属性和决策属性划分的等价类集合 定义4 ：对于任意的概念x u ，属性子集r 鲥，两个子集： _ r x = u y e u r ：y x 砝= o y e u r ：y n x * 妒 ( 2 1 ) ( 2 2 ) 分别被称作概念x 关于r 的下近视和上近似边界值b n d 。 ) 一r x 一鱼， 若b n d r ( x ) = 妒i 1 1 r x 一_ g r ，则称概念x 是可定义的，否则x 在r 上是粗糙的( 见 图2 5 ) 璺墨表示包含在x 中的最大r 可定义集，r x 表示包含在工中的最小尺可 定义集 1 4 让羿k ( 近似1 xl o wa p p r o x i m a t i o n ) 图2 5 租糙集示意图 f i g u r e2 5r o u g hs e t s k e t c h 定义5 ：c 关于d 的正区域是论域，上由c 所划分的等价类集合u i n d 中的 等价类包含于u i i n d ( d ) 某个等价类的并集，表示如下： p o s c (