（计算机应用技术专业论文）基于属性相关性分类理论的属性选择方法研究.pdf

中文摘要 数据挖掘是一门从大量日常业务数据中提取有用信息的新兴学科，2 0 世纪9 0 年代以来发展迅速。日常业务数据可能不完整，含冗余或边界模糊等，应用数据 挖掘算法之前一般需要对原始数据进行预处理属性选择是一种重要的数据预处 理方法，可以降低数据集的维度和噪音，使数据挖掘算法效果更好 本文介绍了数据挖掘开源平台w e k a 的概况和总体结构，重点分析了其中的属 性选择算法的代码组织形式和运行过程；提出了参考分布律的概念，将属性相关 性归结为分布律和参考分布律之间的差异性；总结了已有的属性相关性计算方法 的缺点，根据相关性的新定义提出了衡量属性相关性大小的口指数和口指数，并 发现这两个指数的分布呈现出很强的规律性，可以将属性相关性分为4 种基本类 型；设计了两个属性选择算法，以参考属性和类属性之间相关度的类型作为取舍 属性的依据，并利用n a i v eb a y e s 分类算法和c 4 5 决策树算法评价属性选择的结 果。实验表明，在大多数的数据集合上，基于属性相关性的分类理论的属性选择 算法能够有效地选择属性并保持分类精度基本不变 关键词：数据挖掘：属性选择；分布律；w e k a ：相关性 分类号：t p 3 0 1 6 本文得到国家自然科学基金项目资助( 基金项目编号：6 0 6 7 3 0 8 9 ) d a t am i n i n gi san e ws u b j e c tt oe x t r a c tu s e f u li m f o r m a t i o nf r o ml a r g eq u a n t i t yo f d a i l y t r a n s a c t i o n a ld a t aa n dh a sb e e nf a s t d e v e l o p i n gs i n c e1 9 9 0 s n ed a i l y t r a n s a c t i o n a ld a t am a yb ei n c o m p l e t e ，r e d u n d e n to ri n d i s t i n c t , e t c s op r e p r o c e s s i n gi s u s u a l l yr e q u i r e dt ob ep e r f o r m e du p o nr a wd a t ab e f o r ea p p l y i n ga l g o r i t h m so fd a t a m i n i n g a t t r i b u t es e l e c t i o ni sa ni m p o r t a n tm e t h o do fd a t ap r e p r o c e s s i n g , b yw h i c ht h e d i m e n s i o na n dn o i s eo fd a t as e t sc a nb er e d u c e da n dt h ea l g o r i t h m so fd a t am i n i n gc a n b em o r ee f f e c t i v e m i s p a p e ri n t r o d u c e dt h eo v e r v i e wa n dg e n e r a ls t r u c t u r eo fo p e n s o u r c ed a t a m i n i n gp l a t f o r mw e k aa n da n a l y z e dt h ec o d eo r g a n i z a t i o n sa n dr u n n i n gp r o c e s s e so f a t t r i b u t es e l e c t i o na l g o r i t h m so ft h ep l a t f o r mi ng r e a t ed e p t h ；p r o p o s e dt h ec o n c e p to f r e f e r e n c ed i s t r i b u t i o nl a wa n da t t r i b u t e dc o r e l a t i o n sb e t w e e na t t r i b u t e st ob et h e d i f f e r e n c e sb e t w e e nr e f e i e n c ed i s t r i b u t i o ni a wa n dd i s t r i b u t i o nl a w ；s u m m a r i z e dt h e s h o r t c o m i n g so fe x i s t i n gc o m p u t a t i o n a lm e t h o d so fc o r e l a t i o nb e t w e e na t t r i b u t e sa n d p r o p o s e d 口一i n d e xa n d 口- i n d e xt om e a s u r ec o r e l a t i o nb e t w e e na t t r i u b u t e sb a s e do n t h en e wd e f i n i t i o no fc o r e l a t i o na n df o u n do u tt h a tt h ed i s t r i b u t i o n so ft h o s et w oi n d i c e s a r eh i g h l yr e g u l a ra n dc a nb eu s e dt od i v i d ec o r e l a t i o n sb e t w e e na t t r i b u t e si n t o4 c a t e g o r i e s ；d e s i g n e dt w oa t t r i b u t e s e l e c t i o na l g o r i t h m s ，i nw h i c ht h ec r i t e r i o no f d e c i d i n gw h e t h e rt or e t a i nac e r t a i na t t r i b u t eo rn o ti st h et y p eo fc o r e l a t i o nb e t w e e nt h a t a t t r i b u t ea n dc l a s sa t t r i b u t ea n dc l a s s i f i c a t i o na l g o r i t h m sn a i v eb a y e sa n dc a 5a r eu s e d t oe v a l u a t et h er e s u l to fa t t r i u b t es e l e c t i o n a st e s t i f i e db ye x p e r i m e n t s ，i nm o s to fd a t a s e t s ，a t t r i u b t es e l e c t i o na l g o r i t h m sb a s e do nc l a s s i f i c a t i o nt h e o r yo fc o r e l a t i o n sb e t w e e n a t t r i u b t e sc a ne f f e c t i v e l ys e l e c ta t t r i b u t e sa n dm a i t a i nc l a s s i f i c a t i o np e r f o r m a n c ea tt h e s a m et i m e k e y w o r d s ：d a t a m i n i n g ；a t t r i b u t es e l e c t i o n ；d i s t r i b u t i o nl a w ；w e k a ；c o r r e l a t i o n c l a s s n o ：t p 3 0 1 6 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校向国 家有关部门或机构送交论文的复印件和磁盘 学位论文作者签名： 萌疆， 导师签名： x 笺，荡。 签字闩期：p 。7 年1 2 月纠日签字日期：z 降亿月j 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位做储躲谚蕴签字瞧硼年蝴叫日 致谢 本论文的工作是在我尊敬的导师王志海教授的悉心指导下完成的，王志海教 授严谨的治学态度和科学的工作方法给了我极大的帮助和影响在此衷心感谢三 年来王志海老师对我的关心和指导 衷心感谢黄厚宽和田盛丰教授，两位教授宽广豁达的长者风范、以及严谨的 治学态度始终让我深深地敬仰他们在此期间对我的关心和鼓励让我深受感动 瞿有利老师老师对于我的科研工作和论文都提出了许多的宝贵意见，在此表 示衷心的感谢 在实验室工作及撰写论文期间，李广群、范亚琼、山丹、廉捷等同学对我论 文中的数据挖掘研究工作给予了热情帮助，在此向他们表达我的感激之情 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业 最后，衷心地感谢在百忙之中审阅论文的各位老师和专家，恳请各位老师多 多批评指正，并提出宝贵的意见 1 引言 1 1课题背景 2 0 世纪9 0 年代以来，随着信息技术和数据库技术的迅猛发展，人们可以非常 方便廉洁地获取和存储大量的数据，1 9 9 1 年有人预测全球的数据存储量每隔2 0 个 月要增长一倍如此大规模的海量的数据背后隐藏着许多重要的信息，传统的数 据分析工具( 如管理信息系统) 只能进行一些表层的处理( 如查询、统计等) ，而 不能获得数据之间的内在关系和隐含的信息为了摆脱“数据丰富，知识贫乏” 的困境，人们迫切需要一种能够智能地自动地把数据转换成有用信息和知识的技 术和工具，计算机技术的迅速发展和这种对强有力数据分析工具的迫切需求使得 数据挖掘技术应运而生数据挖掘工具能够对将来的趋势和行为进行预测，从而 很好地支持人们的决策，有些数据挖掘工具还能够解决一些很消耗人工时问的传 统问题，因为它们能够快速地浏览整个数据库，找出一些专家们不易察觉的极有 用的信息 数据挖掘的处理对象是大量的日常业务数据，目的是为了从这些数据中抽取 一些有价值的知识或信息原始业务数据是知识和信息提取的源泉，对于数据挖 掘十分重要，目前所进行的关于数据挖掘的研究工作，大多数着眼于数据挖掘算 法的探讨而忽视了对数据处理的研究一些比较成熟的算法对其处理的数掘集合 一般都有一定的要求，比如数据完整性好、数据的冗余性少、属性之| 日j 的相关性 小然而，实际系统中的数据一般都具有不完全性、冗余性和模糊性，很少能直 接满足数据挖掘算法的要求另外，海量的实际数据中无意义的成分很多，严重 影响了数据挖掘算法的执行效率，而且由于其中的噪声干扰还会造成无效的归 纳因此，在应用数据挖掘算法前，首先需要对数据进行预处理，去掉无关属性 减小属性之间的相关度，即进行属性选择，有着很重要的意义 属性选择通常作为数据挖掘的一个预处理步骤，在数据选择和为数据挖掘做 准备的过程中起着重要的作用这个过程是从原属性集合中删除不相关和( 或) 冗余的属性选出属性子集，以便根据确定的准则使属性空间得到最优的约简从 上个世纪七十年代以来，在统计模式识别、机器学习和数据挖掘等领域，属性选 择已经成为一个研究与开发成果丰富的领域，并且己经证明，在删除不相关和冗 余的属性、增加学习任务的效率、提高学习的性能( 预测的精度) 和增强学习结 果的可理解性等方面它是有效的 1 2本文所完成的工作 本文介绍了数据挖掘开源平台w e k a 的概况和总体结构，重点分析了其中的属 性选择算法的代码组织形式和运行过程；提出了参考分布律的概念，将属性相关 性归结为分布律和参考分布律之间的差异性；总结了已有的属性相关性计算方法 的缺点，根据相关性的新定义提出了衡量属性相关性大小的a 指数和口指数，并 发现这两个指数的分布呈现出很强的规律性，可以将属性相关性分为4 种基本类 型：设计了两个属性选择算法，以参考属性和类属性之间相关度的类型作为取舍 属性的依据，并利用n a i v eb a y e s 分类算法和c 4 5 决策树算法评价属性选择的结 果。实验表明，在大多数的数据集合上，基于属性相关性的分类理论的属性选择 算法能够有效地选择属性并保持分类精度基本不变 1 3 论文组织安排 本文的主要框架和结构如下： 第1 章给出了课题的出发点以及研究的问题及范围，分析了数据挖掘面临的 问题和属性选择的研究现状，介绍了本文所完成的工作 第2 章介绍了数据挖掘、属性选择的相关知识包括数据挖掘的定义，数据 挖掘的起源和数据挖掘的方法；属性选择的步骤，属性选择的各种常用方法 第3 章介绍了著名的丌源数据挖掘软件w e k a ，分析了w e k a 的架构并着重 分析了w e k a 中属性选择的相关内容，包括w e k a 中属性选择的评价方法、搜索算 法和实现方式等 第4 章总结了已有的属性相关性计算方法的缺点，提出了二维随机变量参考 分布律的概念，证明了随机变量相关的充要条件是分布律和参考分布律之日j 存在 着差异性，给出了属性相关性的计算公式口指数和芦指数，并根据这两个指数将 属性相关性分为4 种基本类型。 第5 章基于概率论相关性理论提出了两种新的属性选择算法一消除干扰性 算法和保留独立性算法消除干扰性只考虑了干扰相关性，设计思想上存在一些 漏洞，因而效果不尽如人意保留独立相关性算法在消除干扰性的基础上进行了 若干改进，在大多数数据集合上都能够有效地选择属性同时保持分类算法的分类 精度 第6 章总结全文，对本课题研究做了分析和总结，并给出了本课题将来的研 究内容和方向 2 2 理论综述 2 1 数据挖掘 2 1 1数据挖掘的概念和定义 随着计算机技术的迅猛发展以及网络的普及，许多行业如商业、企业、科研 机构和政府部门等都有了更多的机会和便捷的方法与外界进行信息交流，数据库 的规模、范围和深度都在快速不断扩大，从而积累了海量的、以不同形式存储的 数据资料，同时在许多领域也建立了数据仓库在这些海量数据中往往隐含着各 种各样的信息，这些信息人们往往凭直觉与经验是难以发现的如何从大量的数 据中获得有价值的信息，采用传统的数据库技术已显得无能为力了，数据的快速 增长与数据分析处理方法滞后的矛盾越来大，人们希望能够在对已有的大量数据 分析的基础上进行科学研究、商业决策或企业管理，从而达到为决策服务的目 的数据挖掘就是为了满足这种需求而迅速发展起来的一种新的数据处理技术它 的实质是一种发现知识的应用技术，是一个提取有用信息的过程自2 0 世纪末提 出一来，引起了许多专家学者的广泛关注，并应用到余融、零售业、工业过程、 电力、医疗保健和政府决策等各个领域，取得了良好的社会效益和经济效益，具 有广阔的开发和应用前景 目前数据挖掘的通用定义是指从大量的、不完全的、有噪声的、模糊的、随 机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用 的信息和知识的过程数据挖掘要解决的问题就是在庞大的数据中寻找有价值的 隐藏信息，加以分析，并将这些有意义的信息归纳成结构模式，提供给有关人员 在决策时参考1 “ 人们已经证明，数据发掘技术能够发现和跟踪数据集合中潜在的模式，因此， 有人认为，在数据库中，处理隐藏的知识、不可预料的模式和新规则的发现的所 有方法中，数据挖掘是最有效的如果没有数据挖掘技术，许多数据就很可能停 留在未使用的阶段正是数据挖掘能够为企业提供了全面、深入地分析和了解客 户及其行为特征的重要助臂 在商业的角度i - 2 j ，数据挖掘是一种新的商业信息处理技术，其主要特点是对 商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提 取辅助商业决策的关键性数据简而言之，数据挖掘其实是一类深层次的数据分 析方法数据分析本身已经有很多年的历史，只不过在过去数据收集和分析的目 3 的是用于科学研究，另外，由于当时计算能力的限制，对大数据量进行分析的复 杂数据分析方法受到很大限制现在，由于各行业业务自动化的实现，商业领域 产生了大量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于纯 机会的商业运作而产生分析这些数据也不再是单纯为了研究的需要，更主要是 为商业决策提供真正有价值的信息，进而获得利润但所有企业面临的一个共同 问题是：企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数 据中经过深层分析，获得有利于商业运作、提高竞争力的信息，就像从矿石中淘 金样，数据挖掘也因此而得名因此，数据挖掘又可以描述为：按企业既定业 务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的 规律性，并进一步将其模型化的先进有效的方法 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 的 1 ) 分类：按照分析对象的属性、特征，建立不同的组类来描述事物例如： 银行部门根据以前的数据将客户分成了不同的类别，现在就可以根据这些 来区分新申请贷款的客户，以采取相应的贷款方案 萄聚类：数据库中的记录可被划分为一系列有意义的子集，即聚类聚类增 强了人们对客观现实的认识，是概念描述和偏差分析的先决条件聚类技 术主要包括传统的模式识别方法和数学分类学2 0 世纪8 0 年代初， m c h a l s k i 提出了概念聚类技术其主要特点是，在划分对象时不仅考虑对象 之间的距离，还要求划分出的类具有某种内涵描述，从而避免了传统技术 的摹写片面性 3 ) 关联规则和序列模式的发现：关联是某种事物发生时其他事物会发生的这 样一种联系例如：每天购买啤酒的人也有可能购买香烟，比重有多大， 可以通过关联的支持度和可信度来描述与关联不同，序列是一种纵向的 联系例如：今天银行调整利率，明天股市的变化 4 1 预测：数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量 手工分析的问题如今可以迅速直接由数据本身得出结论一个典型例子是 市场预测问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报 最大的用户，其他可预测的问题包括预报破产以及认定对指定事件最可能 做出反应的群体 5 ) 偏差的检测：数据库中的数据常有一些异常汜录，从数据库中检测这些偏 差很有意义偏差包括很多潜在的知识，如分类中的反常实例、不满足规 则的特例、观测结果与模型预测值偏差、量值随时| 日j 的变化等偏差检测 的基本方法是，寻找观测结果与参照值之间有意义的差别对分析对象的少 数的、极端的特例的描述，揭示内在的原因 需要注意的是数据挖掘的各项功能不是独立存在的，而是互相联系发挥作用 2 1 3数据挖掘的基本过程 数据挖掘的基本过程如图2 2 所示，由以下几个步骤组成： 1 ) 数据清理：数据清理的目的是消除噪声或不一致数据，对数据库中的重复 元组也需要进行清理1 3 j 2 ) 数据集成：数据集成是将多个数据源中的数据结合起来，存放在一个一致 的数据库中 3 ) 数据选择：从数据库中检索与挖掘任务相关的数据，创建相关的目标数据 5 集，即选择数据集合或数据样本的一个子集，删除数据中有误的和无关的 部分 4 ) 数据变换：将数据变换或统一成数据挖掘工具所需要的形式 研数据挖掘：运用各种知识发现算法，从数据中提取出用户需要的知识，这 些知识可以用同一种特定的方式表示或使用一些常用的方式表达，如产生 式规则等等 回模式评估：根据某种兴趣度度量、解释所得的模型，识别能真正有效地表 示知识的模式，必要时应当反复进行数据挖掘这一步 7 ) 知识表示：使用可视化和知识表示技术，将得到的知识以用户能了解的方 式呈现给用户，这其中包括对知识一致性的检查，以保证本次发现的知识 不与以前发现的知识相抵触 图2 2 数据挖掘的基本过程 f i g u r e2 2t h eb a s i cp r o c e s so fd a mm i n i n g 2 1 4数据挖掘的方法 数据挖掘的方法很多，每种方法都有其特定适用领域某一种方法不可能胜 任所有的数据挖掘任务，一个复杂的数据挖掘系统常常采用多种数据挖掘方法， 通过整合多种数据挖掘方法来弥补不同数据挖掘方法所存在的不足数据挖掘的 方法主要有以下几种： 1 1 基于决策树的方法 6 决策树是建立在信息论基础之上，对数据进行分类的一种方法首先，通过 一批己知的训练数据建立一棵决策树然后，利用建好的决策树，对数据进行预 测决策树的建立过程可以看成是数据规则的生成过程，因此可以认为，决策树 实现了数据规则的可视化，其输出结果也容易理解决策树方法精确度比较高， 结果容易理解，效率也比较高，因而比较常用构建决策树的算法很多，其中最 具代表性的是c a r t 和c 4 5 算法 基于神经网络的方法 神经网络最早是由心理学家和神经生物学家提出的神经网络是大量的简单 神经元按一定规则连接构成的网络系统网络能够模拟人类大脑的结构和功能， 采用某种学习算法从训练样本中学习，并将获取的知识存储在网络各单元之间的 连接权中神经网络和基于符号的传统人工智能技术相比，具有直观性、并行性 和抗噪声等优点目前己出现了多种网络模型和学习算法，主要用于分类、优化、 模式识别、预测和控制等领域在数据挖掘领域，主要采用前向神经网络提取分 类规则 3 1 基于遗传算法的方法 遗传算法是一种基于生物进化论和分子遗传学的搜索优化算法它首先将问 题的可能的解按某种形式进行编码，编码后的解称为染色体；随机选取n 个染色 体作为初始种群，再根据预定的评价函数对每个染色体计算适应值，性能较好的 染色体有较高的适应值：选择适应值较高的染色体进行复制，并通过遗传算子， 产生一群新的更适应环境的染色体，形成新的种群，直至最后收敛到一个最适应 环境的个体，得到问题的最优化解 4 ) 贝叶斯方法 贝叶斯网络是由r h o w a r d 和j m a t h e s o n 于1 9 8 1 年提出的，它是一种概率推 理方法，它能从不完全、不精确和不确定的知识和信息中做出推理，可以处理不 完整和带有噪音的数据集，解决了数据阃不一致和相互独立的问题贝叶斯分类 是统计学分类方法它可以预测类成员关系的可能性一种比较简单的朴素贝叶 斯方法是一种基于概率的分类方法，它通过样本的属性值计算事例属于某一个类 的可能性，然后，将样本归属到最有可能的类中朴素贝叶斯分类在应用于大型 数据库时，表现出高准确率和高速度 5 1 基于粗糙集的方法 粗糙集作一种软计算方法，它可以不需任何辅助信息，如统计学中的概率分 布、模糊集中的隶属度等，仅依据数据本身提供的信息就能对数据进行化简并求 得知识的最小表达粗糙集方法可以克服传统的不确定信息的处理方法的不足， 并且能和它们有机结合，进一步增强对不确定、不完全信息的处理能力粗糙集 7 方法首先用近似的方法把信息系统中的属性值离散化，然后对每一个属性划分等 价类，再利用集合的等价关系进行信息系统的属性约简，最后得到一个最小决策 关系，便于获得规则目前成熟的关系数据库管理系统和新发展起来的数据仓库 管理系统为基于粗糙集的数据挖掘奠定了坚实的基础 2 2 属性选择 2 2 1属性选择概述 属性选择问题是分类、数据挖掘、图像处理、概念学习等等许多不同领域的 基础近年来，知识发现和数据挖掘方法在实际应用中不断增长的重要性，使得 属性选择问题成为十分热门的话题，尤其是在考虑从现实世界的数据库或数据仓 库中挖掘的时候，由于它不仅包含数量巨大的记录，而且包含大量的与挖掘任务 不相关的属性，属性选择就更加重要 有些数据属性对发现任务是没有影响的，这些属性的加入会大大影响挖掘效 率，甚至还可能导致挖掘结果的偏差因此，有效的缩减数据是很有必要的数 据简化是在对发现任务和数掘本身内容理解的基础上，寻找依赖于发现目标的表 达数据的有用特征，以缩减数据规模，从而在尽可能保持数据原貌的前提下最大 限度地精简数据量它主要有两个途径：属性选择和数据抽样，分别针对数据库 中的属性和记录 属性选择是指在初始的j v 个属性中选择出一个有m ( 卅 ) 个属性的子集， 这m 个属性可以像原来的 r 个属性样用来正确区分数据集中的每一个数据对 象随着域维度的增大，属性的数量也在不断增大发现最优属性子集通常是难 以实现的1 4 1 许多与属性选择相关的问题都已被证明是n p h a r d 问题1 5 j 由于无关属性在多数机器学习方案中存在负面影响，通常在学习之前先进行 属性选择，只保留一些最为相关的属性，而将其他属性都去除选择相关属性最 好的方法是人工选择，它是基于对学习问题的深入理解以及属性的真正含义而做 出的选择然而，自动方法也是很有用的通过去除不适当的属性以降低数据的 维度，能改善学习算法的性能还能提高速度，即使属性选择可能会带来很多计 算更重要的是，维度的降低能形成一个更为紧凑、更易理解的目标概念表达方 式，使用户的注意力集中在最为相关的变量上 2 2 2属性选择基本步骤 8 一般说来，属性选择算法由四个基本步骤组成：子集产生、子集评估、停止 准则和结果有效性验证【6 】如图2 3 所示 图2 3 属性选择基本步骤 f i g u r e2 3b a s i cs t e p so fa t t r i b u t es e l e c t i o n 子集产生是一个搜索过程，它产生用于评估的属性子集设表示原数据集 属性的数量，那么全部候选子集的数量是，这使得即使是中等的，对整个属 性空问进行穷尽式搜索也是不可行的 子集产生过程所生成的每个子集都需要用事先确定的评估准则进行评估，并 且与先前符合准则最好的子集进行比较，如果它更好一些，那么就用它替换i j 一 个最优的子集如果没有一个合适的停止规则，在属性选择进程停止前，它町能 无穷无尽地运行下去属性选择过程可以在满足以下的条件之一时停止：一个预 先定义所要选择的属性数、预先定义的迭代次数、是否增加( 或删除) 任何属性都不 产生更好的子集、已经根据确定的评估标准获得最优的子集选择的最优子集需 要通过在所选子集和原属性集进行不同的测试和比较，使用人工和现实世界的数 据集所产生的结果进行有效性验证 研究人员已经研究了属性选择的不同方面搜索是属性选择研究的关键问题【。7 ， 引，例如搜索起始点、搜索的方向和搜索策略另一个重要的方向是如何评估属性 子集的优势度i s , 9 1 2 2 3搜索属性空间 属性选择通过删除不相关的属性( 或维) 减少数据量通常使用属性子集选 择方法属性子集选择的目标是找出最小属性集，使得数据类的概率分布尽可能 地接近使用所有属性的原分布 “如何找出原属性集合的一个一好的，子集? ”d 个属性有夕个可能的子集穷 9 举搜索找出属性的最佳子集可能是不现实的，特别是当d 和数据类数目增加时因 此，对属性子集选择，通常使用压缩搜索空间的启发式算法通常，这些算法是 贪心算法，在搜索属性空间时，总是做看上去是最佳的选择他们的策略是做局 部最优选择，期望由此导致全局最优解在实践中，这种贪心算法是有效的，并 可以逼近最优解 属性选择的大多数方法都要牵涉到在属性空问搜索最有可能做出最好类预测 的属性子集属性空间搜索主要考虑4 个方面的问题1 1 0 l ：属性搜索的起始集合、 搜索算法、属性子集评价方法和搜索停止标准，不同的搜索方法对这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 l a s e t 基本上，属性子集的搜索方向是两个方向中的一个，即图中从上往下或是从 下往上在每个阶段，通过增加或删除一个属性，来改变目前的属性子集朝下 的方向，开始时是不含任何属性，然后每次增加一个，称为正向选择朝上的方 向，开始时包含了所有属性，然后每次减少一个，称为反向消除i “j 在正向选择时，每个当前子集没有包含的属性被暂时加入，然后对结果子集 的属性进行评估，譬如使用交叉验证方法评估产生一个数字结果用以衡量子集 的期望性能通过这个方法对依次添加每个属性所产生的结果进行定量，选择其 中最好的，然后继续如果向目前的子集中添加任何一个属性都不能有改善时， 即终止搜索这是一个标准的贪心搜索程序，能保证找到一个局部的，不必是全 局的、最好的属性集反向消除操作采用完全类似的模式在这两种情形中，对 于较小的属性集经常引用一个微小偏差在正向选择中，如果要继续搜索，评估 值的增加必须要超出某个预先设定的最小增量对于反向消除也采用类似的方法 还存在一些更为精细复杂的搜索算法正向选择和反向消除法可以结合成双 向搜索，同样一开始可以包含所有属性或者不含任何属性最佳优先搜索 ( b e s t f i r s ts e a r c h ) 不是在性能开始下降时停止搜索，而是保存到目前为止已经评 估过的所有属性子集清单，并按照性能衡量好坏排序的方法，因此它可以重访先 前的配置只要时问允许它将搜索整个空间，除非是采用某种停止标准限定范 围搜索( b e a ms e a r c h ) 也很类似，只是在每个阶段截取属性子集清单，因此它只 含有固定数目的束宽( b e a mw i d t h ) 中最有希望的候选对象【1 2 】遗传算法( g e n e r i c a l g o r i t h m ) 搜索程序松散地基于自然选择原理，使用对当前的候选子集的随机摄 动，而“进化出”好的属性子集 2 2 a属性选择方法 属性选择问题作为一个研究热点广泛应用于模式识别、统计学、机器学习等 领域，已经有很多国内外研究人员提出了独特的思想和解决方案1 4 , 协1 7 1 ，这些方法 通常可分为两种，即过滤法和打包法1 4 】 过滤法是一种独立于学习算法的属性选择方法，按照某种标准进行属性的筛 选，一般有以下两种筛选标准【l7 j ： 1 最小属性子集选择法 从待选属性子集中，选择一个包含属性最少的属性子集，因为通常意义上讲， 属性少的子集会降低时间和空间复杂度，提高学习算法的效率但这种方法也有 很大局限性，比如在对学校学生的学习成绩进行研究，其中的学号是学生的唯一 标识，如果按照这个选择标准，把学号这个单一属性作为候选虽然满足属性选择 的选择标准，但任何学习算法在此基础上进行学习的结果必然很差 2 根据某种评分标准进行属性选择 此种方法利用精确度、独立性、相关性、信息熵、距离等策略对属性进行评 1 1 分，但这种方法不能处理冗余属性 过滤法对学习算法的支持性不是很好，却以其计算的高效性，在高维属性选 择中得到很好的应用【1 6 1 此外，由于其独立于学习算法，所以过滤法中提供的属 性选择方法也可应用于打包法中【1 4 1 打包法将学习算法作为测试用的黑盒子，利用相关的学习算法对属性子集进 行评价，例如，利用学习算法的交差验证进行属性子集评价【射此种方法需要一个 属性子集搜索方法的支持，主要分以下几种搜索方式： 完全式搜索：也称为穷举搜索，它可以确保找到最优的属性子集但由于全 部可能的属性子集的数量是2 ，当属性数量变大时，这种搜索策略是不可行的 启发式搜索：由于穷尽式搜索受到限制，人们考虑利用启发式来引导搜索它 避免了全部的搜索，但同时也冒着丢失最优子集的风险由启发式指导进行的深 度优先的搜索排序的空日】复杂度可能是d ( 2 ) 或更低利用启发式搜索策略的算 法非常易于实现，并且产生子集的过程非常快，因为搜索空间仅仅是属性数量的 平方关系 不确定搜索：与前面介绍的两种搜索策略不同，这种策略在搜索下一个集合 时是随机的( 即当前集合没有根据任何先前的集合按照确定的规则有方向地增长或 删减1 这种算法能够不断产生最好的子集，随着时间的推移不断提高所选子集的 质量尽管搜索空间仍然是o ( z 5 ，但是这种策略通过设置最大可能的迭代次数使 得搜索的子集数量远远小于2 所选子集的最优性取决于可利用的资源参考文 献1 4 中采用的就是这种方法 打包法的优点是对学习算法的支持度高，缺点是时i h j 复杂度高，效率低 3w e k a 中的属性选择 3 1w e k a 概述 3 1 1w e k a 的背景 w e k a 全称w a i k a t oe n v i r o n m e n tf o rk n o w l e d g ea n a l y s i s l 2 3 ，即怀卡托智能分析 系统的缩写，于1 9 9 9 年在新西兰怀卡托大学开发问世在怀卡托以外的地方， w e k a 通常按谐音念成m e s a ，是一种现今仅存活于新西兰的并不会飞的鸟( 见图 3 1 ) w e k a 开发的本意用于服务于新西兰国家，解决新西兰工业遇到的k d d 问 题，使机器学习理论联系实际，开发新的机器学习算法，为机器学习领域提供一 个理论框架其设计者为数据挖掘界的大师l a nh w i t t e n 和e i b ef r a n k 图3 1 一种叫m e c c a 的鸟 f i g u r e3 1a b i r dn a m e dm e c c a w e k a 由j a v a 语言编写，并且限制在g n u 通用公众证书的条件下发布由于 j a v a 程序的平台无关特性使得w e k a 可以运行于任何装有j a v a 虚拟机的操作系统 上在已经测试过的平台包括l i n u x ，w i n d o w s 和m a c i n t o s h 操作系统，甚至还包 括个人数字化助手w e k a 提供了一个统一界面，可结合预处理及后处理方法，将 许多不同的学习算法应用于任何所给的数据集，并评估由不同的学习方案所得出 的结果 w e k a 为不同的学习算法提供了统一的接口，也提供了很多学习模式结果的评 估方法2 0 0 5 年8 月，在第1 1 届a c m s i g k d d 唇际会议上，怀卡托大学的w e k a 小组荣获了数据挖掘和知识探索领域的最高服务奖，w e k a 系统得到了广泛的认 可，被誉为数据挖掘和机器学习历史上的里程碑，是现今最完备的数据挖掘工具 之一w e k a 的每月下载次数已超过万次 正是由于这种开源、兼容、结构规范等特性，w e k a 自从发布以来，已经吸弓i 了众多的用户和科学工作者，他们在d m 领域对w e k a 进行了很多扩展，在w e k a 主页上可以看到，w e k a 及w e k a 相关扩展课题基本涵盖了d m 的基本技术和d m 发展趋势和热点话题根据w e k a 官方网站上的最新消息，w e k a 已经加入了世界 上著名的商业智能开源项目p e n t a h o ，这标志着w e k a 正从一个实验平台向着商业 应用迈进 3 1 2w b k a 的功能 w e k a 工作平台汇集了当今最前沿的机器学习算法及数据预处理工具它为数 据挖掘实验的整个过程，包括准备要输入的数据，统计地评估学习方案，以及可 视化输入数据及学习结果，提供了广泛的支持w e k a 不但包含多样化的学习算法， 还提供大量适应范围很广的预处理工具用户可通过一个公用的界面操作运用所 有已包含的工具组件，从而比较不同的学习算法，找出能够解决当前问题的最有 效的方法w e k a 平台中最有价值的部分是真实学习方案的实现其次是数据预处 理工具，也称作过滤器对所要处理的数据进行分析是整个工作中必不可少的一 环，w e k a 提供了许多用于数据可视化及预处理的工具 w e k a 平台包含能处理所有的标准数据挖掘问题的方法：数据预处理、分类、 聚类、关联规则挖掘以及属性选择并且可以在此上扩展很多新的机器学习模 式目f i 已很多用它分析数据，挖掘决策信息，以及做二次开发等在w e k a 上你 可以挖掘你的数据，变换你的数据，用指定的算法分析数据，然后分析学习结果 的质量和性能，所以的这一切都可以在w e k a 上实现，并且你不用编写任何代 码w e k a 的功能可以概括为以下几类： 1 ) 数据预处理，w e k a 就数据集能做一些常用的预处理，如离散化、正交化， 取样、属性选择、转换和合并属性等； 2 ) 分类，w e k a 系统内已有的分类算法，如决策树和决策表、基于实例的分 类、支持相量机、多层感知器神经网络、l o g i s t i c 回归、b a y e s 网络等； 3 ) 聚类，w e k a 也包含了诸多聚类模式，如k m e a n s ，e m ，c o b w e b ，x - m e a n s ， f a r t h e s t f i r s t 等； 4 ) 关联规则，w e k a 实现的关联规则有，a p r i o r i ，p r e d i c t i v e a p r i o r i ，t e r t i u s 等； 5 ) 属性选择，w e k a 的属性选择方法有b e s t f i r s t 、f o r w a r ds e l e c t i o n 、r a n d o m 、 e x h a u s t i v e 、g e n e t i ca l g o r i t h m ，r a n k i n g ，c o r r e l a t i o n - b a s e d ，w r a p p e r ， i n f o r m a t i o ng a i n 、c h i s q u a r e d 等： 6 ) 数据的可视化展示，w e k a 提供了从不同的角度观察数据的特点 1 4 3 2w e k a 设计框架 3 2 1w e k a 总体结构分析 w e k a 按照界面功能可以主要分为4 个部分( 见图3 2 ) ：e x p l o r e r 、e x p e r i m e n t e r 、 k n o w l e d g ef l o w 和s i m p l ec l i ，其中： e x p l o r e r 界面，包含了数据预处理和各种机器学习模式，w e k a 中几乎所有功 能均可以通过e x p l o r e r 中的菜单选择或者表单填写的方式访问到，e x p l o r e r 界面顶 部的六个不同的标签表示六个不同的面板，分别对应着w e k a 所支持的不同的数据 挖掘方式； e x p e r i m e n t e r 界面使得用户可设定好大型实验，另其开始运行，然后即可离开， 当实验完成后再回来分析所搜集到的性能统计数据这使得实验过程自动化； k n o w l e d g ef l o w 界面为那些喜欢从数据是如何在系统中流动的这样的角度出 发来思考问题的用户提供了e x p l o r e r 之外的另外一种选择它还允许将配置的设 计与执行应用于数据流( s t r e a md a t a ) 的处理： s i m p l ec l i 是命令行模式，隐藏在w e k a 互动式界面后面的是w e k a 的基本功 能这些功能可以原始形式通过命令界面运行： 此外新版w e k a 还增加了a f f f v i e w e r 和l o g 两个功能，在此就不再阐述 3 2 2w e k a 的包结构 图3 2 w e k a 总体结构 f i g u r e3 2w e k af r a m e w o r k w e k a 由j a v a 开发，其整体架构也按照j a v a 的包结构形式进行划分，其中c o r e 包是w e k a 系统的核心，并且它里面的类可被几乎其他所有的类读取：c l a s s i f i e r 包中包含用于分类及数值预测的大部分算法实现：a t t r i b u t e s e l e c t i o n 包在下文会有 详细说明，其他的还有a s s o c i a t i o n s 包、