（计算机科学与技术专业论文）基于属性间相关性分析的属性选择方法研究.pdf

中文摘要 摘要：数据挖掘是一门从大量的日常业务数据中提取隐含的同时又是有用的 信息的新兴技术数据挖掘算法对其处理的数据集合一般都有一定要求，比如数 据完整性好、数据冗余性少、属性之间相关性小等然而，日常业务数据一般都 可能具有不完整性、冗余性和模糊性等特点因此，应用数据挖掘算法之前一般 需要对原始数据进行预处理属性选择是一种重要的数据预处理方法，可以降低 数据集的维度和噪音，使数据挖掘算法效果更好 本文首先介绍了属性选择的相关技术及本文所涉及的信息论的基本概念，随 后详细分析了属性选择包中算法的静态组织结构和动态运行过程，然后介绍了已 有相关性评价方法，着重叙述了新的属性间冗余性的分析和最大关联最小冗余的 评价标准最后本文设计了两个基于属性间相关性分析的属性选择算法一个是 消除属性间冗余性的算法，它利用决策独立相关性和决策依赖相关性来分别度量 属性与类属性之间关联性和属性与属性之间冗余性另一个是排序法与打包法相 结合的算法，它是一个两阶段方法，首先排序法利用最大关联最小冗余标准选择 一些较好的属性子集，然后打包法利用交叉验证选择最佳属性子集利用n a i v e b a y e s 分类算法和c 4 5 决策树算法评价属性选择的结果，实验表明，在大多数的 数据集合上，这两个算法能够显著地约减属性并保持分类精度基本不变 关键词：数据挖掘；属性选择；信息论；w 呔a ；相关性 分类号：t p 3 0 1 6 a b s t r a c t ：d a t al i l i l l i n gi san e w t e c h n o l o g yw h i c he x t r a c t sp o t e n t i a la n du s e f u l i n f o r m a t i o nf r o ml o t so fd a i l yt r a n s a c t i o n a ld a t a d a t am i n i n ga l g o r i t h mo f t e nh a ss t r i c t r e q u i r e m e n to fd 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 ed a t ar e d u n d a n c y , w e a ka t t r i b u t e s c o r r e l a t i o na n ds oo n h o w e v e r , t h ed a i l yt 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 a n to ri n d i s t i n c t ，e t c s o ，p r e p r o c e s s i n gi su 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 n l a wd a t ab e f o r ea p p l y i n gd a t am i n i n ga l g o r i t h m s 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 t m 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 en o i s eo fd a t as e t sc a nb er e d u c e da n dt h e a l g o r i t h m so fd a t am i n i n g 啪b em o r ee f f e c t i v e i nt h i sp a p e r , w ef i r s t l yi n t r o d u c ea t t r i b u t es e l e c t i o nr e l a t e dt h e o r ya n db a s i c c o n c e p t so fi n f o r m a t i o nt h e o r y t h e nw ed e t a i l e d l ya n a l y z et h es t a t i co r g a n i z a t i o n a l s t r u c t u r e sa n dd y n a m i cr u n n i n gp r o c e s s e so fa l g o r i t h m si nt h ep a c k a g eo fa t t r i b u t e s e l e c t i o n t h e nw ei n t r o d u c et h ee x i s t i n gc o r r e l a t i o n - b a s e de v a l u a t i o nm e t h o d sa n d d e s c r i b et h en e w a n a l y s i so fr e d u n d a n c yb e t w e e n a t t r i b u t e sa n dt h ee v a l u a t i o nc r i t e r i o n o fm a x r e l e v a n c ea n dm i n - r e d u n d a n c yi n g r e a td e p t h f i n a l l y , t w on o v e la 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 sb a s e do nt h ea n a l y s i so fc o r r e l a t i o nb e t w e e na t t r i b u t e sa r ed e s i g n e d o n ei sa t t r i b u t e sr e d u n d a n c yr e m o v a la l g o r i t h m ，w h i c hu s e sd e c i s i o ni n d e p e n d e n t c o r r e l a t i o na n dd e c i s i o nd e p e n d e n tc o r r e l a t i o nt o r e s p e c t i v e l ym e a s u r et h er e l e v a n c e b e t w e e no n ea t t r i b u t ea n dt h ec l a s sa t t r i b u t ea n dt h er e d u n d a n c yb e t w e e no n ea t t r i b u t e a n da n o t h e ra t t r i b u t e t h eo t h e ri sr a n k - w r a p p e ra l g o r i t h m ，w h i c hi st w o s t a g ea p p r o a c h i nt h i s a l g o r i t h m ，f i r s t r a n km e t h o du s e st h ec r i t e r i o no fm a x - r e l e v a n c ea n d m i n - r e d u n d a n c yt os e l e c ts o m eg o o da t t r i b u t es u b s e t s ，a n dt h e nw r a p p e rm e t h o du s e s c r o s s - v a l i d a t i o nt os e l e c tt h eb e s ta t t r i b u t es u b s e t t h ec 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 e b a y e sa n dc 4 5a r eu s e dt oe v a l u a t et h er e s u l to fa t t r i b u t es e l e c t i o n a st e s t i f i e db y e x p e r i m e n t s ，i nm o s to fd a t as e t s ，t h e s ea t t r i b u t es e l e c t i o na l g o r i t h m sc a ne f f e c t i v e l y s e l e c ta t t r i b u t e sa n dm a i n 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 es 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 ；i n f o r m a t i o nt h e o r y ；w e k a ；c o r r e l a t i o n c 1 a s s n o ：t p 3 0 1 6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意 学位论文作者签名：哿娃馏 签字日期： ：2 0 0 q 年6 月鼹日 6 1 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校向国 家有关部门或机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：罂产建智 导师签名： 蔓基培。 签字日期：2 0 0 c 1 年6 月瞪日签字日期：砩年，月日 致谢 本论文的工作是在我的导师王志海教授的悉心指导下完成的，王志海教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响在此衷心感谢两年来 王志海老师对我的关心和指导 黄厚宽教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向黄厚宽老师表示衷心的谢意 瞿有利老师对于我的科研工作和论文都提出了许多的宝贵意见，在此表示衷 心的感谢 在实验室工作及撰写论文期问，程新宇、邵鲁杰、孙兴中等同学对我论文的 研究工作给予了热情帮助，在此向他们表达我的感激之情 另外也感谢我的父母，他们的理解和支持使我能够在学校专心完成我的学业 最后，衷心地感谢在百忙之中审阅论文的各位老师和专家，恳请各位老师多 多地批评指正，并提出宝贵的意见 l 引言 1 1 课题背景 随着信息技术和数据库技术的迅猛发展及数据库管理系统的广泛应用，大型 数据库系统已经在各行各业普及，数据库中存储的数据量急剧增大在大量的数 据背后隐藏着许多重要信息，而这些重要信息可以很好地支持人们的决策可是 传统的数据分析工具( 如管理信息系统) 只能进行一些表层的处理( 如查询、统 计等) ，而隐藏在这些数据之后的更重要的信息则没有被充分利用这些信息是关 于数据的整体特征的描述及对发展趋势的预测，在决策生成的过程中具有重要的 参考价值为了摆脱“数据丰富，知识贫乏 的困境，人们迫切需要一种能够智 能地自动地把数据转换成有用信息和知识的技术和工具，计算机技术的迅速发展 和这种对强有力数据分析工具的迫切需求使得数据挖掘技术应运而生 数据挖掘是随着数据库和人工智能发展起来的一门新兴的数据库技术其处 理对象是大量的同常业务数据，目的是为了从这些数据中抽取一些有价值的知识 或信息原始业务数据是知识和信息提取的源泉，对于数据挖掘十分重要，目前 所进行的关于数据挖掘的研究工作，大多数着眼于数据挖掘算法的探讨而忽视了 对数据处理的研究一些比较成熟的算法对其处理的数据集合一般都有一定的要 求，比如数据完整性好、数据冗余性少、属性之间相关性小然而，实际系统中 的数据一般都具有不完全性、冗余性和模糊性，很少能直接满足数据挖掘算法的 要求另外，海量的实际数据中无意义的成分很多，严重影响了数据挖掘算法的 执行效率，而且由于其中的噪声干扰还会造成无效的归纳预处理已经成为数据 挖掘系统实现过程中的关键问题 数据预处理是数据挖掘的重要一环，而且必不可少要使挖掘内核更有效地 挖掘出知识，就必须为它提供干净、准确、简洁的数据 属性选择通常作为数据挖掘的一个预处理步骤，在数据选择和为数据挖掘做 准备的过程中起着重要的作用这个过程是从原属性集合中删除不相关和( 或) 冗余的属性选出属性子集，以便根据确定的准则使属性空间得到最优的约简从 上个世纪七十年代以来，在统计模式识别、机器学习和数据挖掘等领域，属性选 择已经成为一个研究与开发成果丰富的领域，并且己经证明，在删除不相关和冗 余的属性、增加学习任务的效率、提高学习的性能( 预测的精度) 和增强学习结 果的可理解性等方面它是有效的 1 2 本文研究的工作和意义 本文研究的工作主要有以下几个方面： 第一，整体上分析了相关理论的基础知识简单分析了数据挖掘的概念、功 能、基本过程及常用方法；重点分析了属性选择的定义、基本步骤、空间搜索及 一般方法；最后对信息论相关概念进行了较为详尽的分析 第二，全面分析了w e k a 平台中属性选择包中的算法首先介绍了w e k a 平台 的背景与总体框架；其次着重分析了其中属性选择包的静态组织形式；最后较为 详细的分析了属性选择包的动态运行过程 第三，叙述了属性间相关性分析的理论描述了属性相关性概念，包括属性 与类属性之问关联性和属性与属性之间冗余性；介绍了线性相关性评价方法和经 典算法c f s 的相关性评价方法；给出了新的属性间冗余性的分析，描述了决策独 立相关性和决策依赖相关性概念；详述了最大关联最小冗余的评价标准 第四，提出了两种基于属性间相关性分析的属性选择算法一个是消除属性 间冗余性的算法，它利用决策独立相关性和决策依赖相关性来分别度量属性与类 属性之间关联性和属性与属性之间冗余性，通过综合考虑属性子集中的关联性和 冗余性来评价子集价值另一个是排序法与打包法相结合的算法，它是一个两阶 段方法，首先排序法利用最大关联最小依赖的评价标准来选出一些较好的属性子 集，然后打包法再利用交叉验证来选择最优子集利用n a i v eb a y e s 分类算法和 c 4 5 决策树算法评价属性选择结果，实验表明，在大多数的数据集合上，这两个 算法能够有效地选择属性并保持分类精度基本不变 本文工作的意义在于： 第一，提出了新的属性子集的评价方法，它利用决策独立相关性和决策依赖 相关性来分别度量属性与类属性之间关联性和属性与属性之间冗余性特别地， 决策依赖相关性考虑了类属性对属性与属性之间冗余性的影响消除属性问冗余 性的属性选择算法，利用这个评价方法，产生了较好的效果 第二，给出了新的单个属性的评价方法，它利用最大关联最小冗余的评价标 准，综合考虑了一个属性所具有的关联性和冗余性，因而更为准确地评价了该属 性的价值 第三，提出了排序法与打包法相结合的属性选择方法，它既利用了排序法执 行速度快的特点，又利用了打包法选择精度高的特点 1 3 论文组织安排 2 本文的主要框架和结构如下： 第1 章给出了课题的出发点以及研究的问题及范围，分析了数据挖掘面临的 问题和属性选择的研究现状，并论述了本文研究的工作和意义及论文的组织结构 第2 章介绍了数据挖掘、属性选择和信息论的相关知识包括数据挖掘的概 念和方法；属性选择的概念、步骤和常用方法；信息论的相关概念 第3 章介绍了著名的数据挖掘开源软件w e k a ，分析了w e k a 的架构重点分 析了w e k a 中属性选择包的相关内容，包括w e k a 中属性选择的评价方法、搜索策 略及实现方式等 第4 章叙述了属性间相关性分析理论包括相关性概念、线性相关性评价方 法、经典算法c f s 的相关性评价方法、属性间冗余性的分析和最大关联最小冗余 的评价标准，本章为后面属性选择算法提供了理论基础 第5 章提出了两种基于属性间相关性分析的属性选择算法，即消除属性问冗 余性的算法和排序法与打包法相结合的算法这两个算法在大多数数据集合上都 能够有效地选择属性同时保持分类算法的精度 第6 章总结了全文，对本课题研究做了分析和总结，并给出了本课题将来的 研究内容和方向 3 2 相关理论综述 本章主要介绍了相关理论的基础知识，包括数据挖掘的概念、功能、基本过 程及常用方法，数据预处理概念，属性选择的定义、基本步骤、空间搜索及有关 方法，信息论的背景和相关概念 2 1 数据挖掘 随着现代信息技术的迅猛发展，在全球内掀起了信息化的浪潮信息产生的 渠道越来越多，更新的频率日益加快，各行业均产生了数以亿计的数据库人们 面对着大量的数据，却往往无法找到需要的信息，很难发现有用的知识，这就是 所谓的“数据丰富，信息贫乏 数据的快速增长与数据分析处理方法滞后的矛盾 越来越大，如何充分、有效地利用这些宝贵的数据资源成为当今世界共同关心的 热点课题随着数据库技术、人工智能、数理统计和并行计算等技术的发展与融 合，数据挖掘技术应运而生本节主要介绍了数据挖掘的概念、功畿、基本过程 及常用方法 2 1 1数据挖掘的概念 目前数据挖掘的通用定义是指从大量的、不完全的、有噪声的、模糊的、随 机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用 的信息和知识的过程这个定义包含以下四个层次的含义： 1 ) 数据源必须是真实的、大量的、含噪声的； 2 发现的是用户感兴趣的知识； 3 ) 发现的知识要可接受、可理解、可运用，最好能用自然语言表达发现结果； 4 1 并不是要求发现放之四海皆准的知识，也不是要去发现崭新的自然科学定 理和纯数学公式，更不是什么机器定理证明，所有发现的知识都是相对的，是有 特定前提和约束条件的、面向特定领域的 数据挖掘要解决的问题就是在庞大的数据中寻找有价值的隐藏信息，加以分 析，并将这些有意义的信息归纳成结构模式，提供给有关人员在决策时参考人 们已经证明，数据发掘技术能够发现和跟踪数据集合中潜在的模式因此，有人 认为，在数据库中处理隐藏的知识和发现新规则的所有方法中，数据挖掘是最有 效的如果没有数据挖掘技术，许多数据就很可能停留在未使用的阶段 4 从商业角度出发，数据挖掘可以描述为：按企业既定业务目标，对大量的企 业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将 其模型化的先进有效的方法数据挖掘从本质上说是一种新的商业信息处理技术， 数据挖掘技术把人们对数据的应用从低层次的操作提高到决策支持分析预测等更 高级应用上【l 】数据挖掘所得到的信息应具有先前未知性、有效性和可使用性三个 特征挖掘出的信息越是出乎意料，就可能越有价值在商业应用中最典型的例 子就是一家连锁店通过数据挖掘发现了小孩尿布和啤酒之间有着惊人的联系 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 数据挖掘综合了各个学科技术，有很多的功能，当前主要有以下五类功能： 1 ) 分类：分类数据挖掘是先分析一个训练数据集，找到一个描述并区分数据 类的模型，然后使用这个模型对类标记未知的对象类进行分类例如：银行部门 根据以前的数据将客户分成了不同的类别，现在就可以根据这些来区分新申请贷 款的客户，以采取相应的贷款方案 2 ) 聚类：聚类就是将数据对象分组成为多个类或簇，在同一个簇中的对象之 5 问具有较高的相似度，而不同簇中的对象差别较大聚类增强了人们对客观现实 的认识，是概念描述和偏差分析的先决条件 3 ) 关联规则和序列模式的发现：关联是某种事物发生时其他事物会发生的这 样一种联系关联分析的典型例子是购物篮分析，描述顾客的购买行为例如啤 酒和尿布的故事与关联不同，序列是一种纵向的联系例如：今天银行调整利 率，明天股市的变化 4 ) 预测：数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量 手工分析的问题，如今可以迅速直接由数据本身得出结论一个典型例子是市场 预测问题，数据挖掘使用过去有关促销的数据来寻找未来投资中回报最大的用户 5 ) 偏差的检测：数据库中的数据常有一些异常记录，从数据库中检测这些偏 差很有意义偏差包括很多潜在的知识，如分类中的反常实例、观测结果与模型 预测值偏差等偏差检测的基本方法是寻找观测结果与参照值之间有意义的差别 2 1 3数据挖掘的基本过程 数据挖掘的基本过程如图2 2 所示，由以下几个步骤组成： 1 ) 数据清理：数据清理的目的是消除噪声或不一致数据，对数据库中的重复 元组也需要进行清理【2 1 2 ) 数据集成：数据集成是将多个数据源中的数据结合起来，存放在一个一致 的数据库中 3 ) 数据选择：从数据库中检索与挖掘任务相关的数据，创建相关的目标数据 集，即选择数据集合或数据样本的一个子集，删除数据中有误的和无关的部分 4 ) 数据变换：将数据变换或统一成数据挖掘工具所需要的形式 5 ) 数据挖掘：运用各种知识发现算法，从数据中提取出用户需要的知识，这 些知识可以用同一种特定的方式表示或使用一些常用的方式表达 6 ) 模式评估：根据某种兴趣度度量、解释所得的模型，识别能真正有效地表 示知识的模式，必要时应当反复进行数据挖掘这一步 7 ) 知识表示：使用可视化和知识表示技术，将得到的知识以用户能了解的方 式呈现给用户，这其中包括对知识一致性的检查，以保证本次发现的知识不与以 前发现的知识相抵触 6 i | 理与集成 图2 2 数据挖掘的基本过程 f i g u r e2 2t h eb a s i cp r o c e s so fd a t am i n i n g 2 1 4数据挖掘的方法概述 数据挖掘的方法通常可以分为两大类：一类是统计型，常用的技术有概率分 析、相关性、聚类分析和判别式分析等；另一类是人工智能中的机器学习型，通 过训练和学习大量的样品集得出需要的模式或参数由于各种方法都有自身的功 能特点以及应用领域，数据挖掘技术的选择将影响最后结果的质量和效果，通常 是将多种技术结合使用，形成优势互补数据挖掘的方法主要有以下几种： 1 ) 决策树：决策树主要是基于数据的属性值进行归纳分类，常用于分类的层 次方法有“i f - t h e n 规则构建决策树的算法很多，其中最具代表性的是c a r t 和 c 4 5 算法 2 ) 神经网络：神经网络最早是由心理学家和神经生物学家提出的神经网络 是大量的简单神经元按一定规则连接构成的网络系统网络能够模拟人类大脑的 结构和功能，采用某种学习算法从训练样本中学习，并将获取的知识存储在网络 各单元之间的连接权中 3 ) 遗传算法：遗传算法最初是由j o h nh o l l a n d 于1 9 7 5 年提出，是一种基于生 物进化理论的技术，其基本观点是“适者生存 ，在数据挖掘中，常把任务表示成 一种搜索问题，利用遗传算法强大的搜索能力找到最优解 4 ) 贝叶斯方法：贝叶斯网络是由r h o w a r d 和j m a t h e s o n 于1 9 8 1 年提出的， 它是一种概率推理方法，能从不完全、不精确和不确定的知识和信息中做出推理， 7 彬 可以处理不完整和带有噪音的数据集，解决了数据间不一致和相互独立的问题 5 ) 粗燥集：该理论是波兰p a w l a k 教授在1 9 8 2 年提出的，它是一种新的数学 工具这一方法在数据挖掘中具有重要的作用，常用于处理含糊性和不确定性的 问题 2 2 数据挖掘中的数据预处理 海量数据中既有噪声数据和空缺数据，又存在数据不一致现象，这些因素都 会影响人们对数据信息的使用因此，在执行数据挖掘算法前有必要通过预处理 来提高数据的质量数据预处理技术为进一步的数据分析做准备，并能确定挖掘 算法的类型，可以提高数据挖掘算法的效率和质量 数据预处理应该包括以下几方面的功能： 1 ) 数据集成：数据集成主要是将多文件或多数据库运行环境中的异构数据进 行合并处理，解决语义的模型性该部分主要涉及数据的选择、数据的冲突问题 以及不一致数据的处理问题 2 ) 数据清洗：数据清洗要去除源数据集中的噪声数据和无关数据，处理遗漏 数据和清洗脏数据，去除空白数据域和知识背景上的白噪声，考虑时间顺序和数 据变化等主要包括重复数据处理和缺失数据处理，并完成一些数据类型的转 换数据清洗的另一个重要内容是数据类型的转换，通常是指连续型属性的离散 化 3 ) 数据变换：数据变换主要是找到数据的特征表示，用维变换或转换方式减 少有效变量的数据或找到数据的不变式，包括规格化、归纳、切换、旋转和投影 等操作 4 ) 数据简化：有些数据属性对挖掘任务是没有意义的，这些属性的加入会大 大影响挖掘效率，甚至还可能导致挖掘结果的偏差因此，有效地缩减数据是很 必要的数据简化是在对挖掘任务和数据本身内容理解的基础上，寻找依赖于挖 掘目标的表达数据的有用特征，以缩减数据规模，从而在尽可能保持数据原貌的 前提下最大限度地精简数据量它主要有两个途径：属性选择和数据抽样，分别 针对数据库中的属性和记录 2 3 属性选择 属性选择问题是分类、数据挖掘、图像处理、概念学习等等许多不同领域的 基础近年来，知识发现和数据挖掘方法在实际应用中不断增长的重要性，使得 属性选择问题成为十分热门的话题，尤其是在考虑从现实世界的数据库或数据仓 库中挖掘的时候，由于它不仅包含数量巨大的记录，而且包含大量的与挖掘任务 不相关的属性，属性选择就更加重要本节主要叙述了属性选择的定义、基本步 骤、空间搜索和有关方法 2 3 1属性选择的定义 由于所面对的实际问题不同，研究者对属性选择有不同的要求和多种形式的 定义常见的定义有： 1 ) 属性选择：属性选择是根据某一特定标准从属性集合中选取最优子集的过 程该定义比较笼统，没有对属性选择的标准以及最优子集的定义给出明确的定 义 2 ) 属性选择：在所有的个属性所组成的属性集合中选取一个由m 个属性组 成的子集，其中肘事先给定，并且m n ，使得这个子集在原集合的所有元素个 数为肘的子集中对于某种评价标准是最优的该定义事先给定了属性子集的基数 m ，因此选择的范围大大缩小，所选择的结果很大程度上受到数值膨的影响，对 于同样的属性集合，不同的膨可能对应完全不同的结果 3 ) 属性选择：从描述实例的属性集合中选择一个必要的、充分的并且元素个 数最少的属性子集来描述目标概念【3 】此定义给出了属性选择的理想状态，属性选 择的结果是一个包含了目标概念所有信息的属性子集 们属性选择：通过从原属性集合中选择一个子集，来提高用于分类和预测的 模型的预测正确率，或者在保证一定预测正确率的前提下降低模型结构的复杂 性该定义将数据挖掘算法的预测正确率作为衡量属性子集优劣的标准，希望在 保证正确率的基础上通过属性选择来降维或者来改善算法的学习性能 上述不同的定义体现对属性选择基于不同的数学描述、面对不同实际问题、 针对不同目的的不同理解一个完善的定义是对问题进行研究的基本出发点，许 多属性选择方法都是在它自身的定义上发展起来的 2 3 2属性选择的基本步骤 有许多种属性选择方法属性选择方法通常要面对的问题是：怎样才能搜寻 到“最好 的属性? 用什么准则来确定最好的属性子集已经被找到? 在什么情况 下需要增加新的属性或者删除一个属性? 特定应用如何确定属性的选取? 一般的，属性选择方法通过搜索属性子集，试图根据某些评价函数从2 月个候 9 选子集中找出最好的一个随着维度的增大，属性的数量也在不断增太，拔现最 优属性子集通常是难以实现的 4 1 许多与属性选择相关的问题都已被证明是 n p h a r d 问剐5 1 一般说来，属性选择算法由四个基本步骤组成：子集产生、子集 评估、停止准则和结果有效性验证【6 1 如图2 3 所示 图2 3 属性选择基本步骤 f i g u r e2 3t h eb 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 子集产生是一个搜索过程，它产生用于评估的属性子集设表示原数据集 属性的数量，那么全部候选子集的数量是，这使得即使是中等的，对整个属 性空间进行穷尽式搜索也是不可行的 子集产生过程所生成的每个子集都需要用事先确定的评估准则进行评估，并 且与先前符合准则最好的子集进行比较，如果它更好一些，那么就用它替换前一 个最优的子集如果没有一个合适的停止规则，在属性选择进程停止前，它可能 无穷无尽地运行下去属性选择过程可以在满足以下的条件之一时停止：一个预 先定义所要选择的属性数、预先定义的迭代次数、是否增加( 或删除) 任何属性都不 产生更好的子集、已经根据确定的评估标准获得最优的子集选择的最优子集需 要通过在所选子集和原属性集进行不同的测试和比较，使用人工和现实世界的数 据集所产生的结果进行有效性验证 研究人员已经研究了属性选择的不同方面搜索是属性选择研究的关键问题 网，例如搜索起始点、搜索的方向和搜索策略另一个重要的方向是如何评估属性 子集的优势度【8 】 2 3 3属性空间搜索 属性选择通过删除不相关的属性( 或维) 减少数据量通常使用属性子集选 择方法属性子集选择的目标是找出最小属性集，使得数据类的概率分布尽可能 地接近使用所有属性的原分布 “如何找出原属性集合的一个好的子集? d 个属性有2 d 个可能的子集穷 1 0 举搜索找出属性的最佳子集可能是不现实的，特别是当d 和数据类数目增加时因 此，对属性子集选择，通常使用压缩搜索空间的启发式算法通常，这些算法是 贪心算法，在搜索属性空间时，总是做看上去是最佳的选择他们的策略是做局 部最优选择，期望由此导致全局最优解在实践中，这种贪心算法是有效的，并 可以逼近最优解 属性选择的大多数方法都要牵涉到在属性空间搜索最有可能做出最好类预测 的属性子集属性空间搜索主要考虑4 个方面的问题 9 1 ：属性搜索的起始集合、搜 索算法、属性子集评价方法和搜索停止标准，不同的搜索方法对这4 个问题的实 现方式不同图2 4 展示了著名的天气数据的属性空间 图2 4 天气数据集的属性空间 f i g u r e2 4t h ea t t r i b u t es p a c eo f t h ew e a t h e rd a t a s e t 基本上，属性子集的搜索方向是两个方向中的一个，即图中从上往下或是从 下往上在每个阶段，通过增加或删除一个属性，来改变目前的属性子集朝下 的方向，开始时是不含任何属性，然后每次增加一个，称为正向选择朝上的方 向，开始时包含了所有属性，然后每次减少一个，称为反向消除f 旧】 在正向选择时，每个当前子集没有包含的属性被暂时加入，然后对结果子集 的属性进行评估，譬如使用交叉验证方法评估产生一个数字结果用以衡量子集 的期望性能通过这个方法对依次添加每个属性所产生的结果进行定量，选择其 中最好的，然后继续如果向目前的子集中添加任何一个属性都不能有改善时， 即终止搜索这是一个标准的贪心搜索程序，能保证找到一个局部的，不必是全 局的、最好的属性集反向消除操作采用完全类似的模式在这两种情形中，对 于较小的属性集经常引用一个微小偏差在正向选择中，如果要继续搜索，评估 值的增加必须要超出某个预先设定的最小增量对于反向消除也采用类似的方法 还存在一些更为精细复杂的搜索算法正向选择和反向消除法可以结合成双 向搜索，同样一开始可以包含所有属性或者不含任何属性最佳优先搜索不是在 性能开始下降时停止搜索，而是保存到目前为止已经评估过的所有属性子集清单， 并按照性能衡量好坏排序的方法，因此它可以重访先前的配置只要时间允许它 将搜索整个空间，除非是采用某种停止标准限定范围搜索也很类似，只是在每 个阶段截取属性子集清单，因此它只含有固定数目的束宽中最有希望的候选对象 【l l 】遗传算法搜索程序松散地基于自然选择原理，使用对当前的候选子集的随机 摄动，而“进化出好的属性子集 2 3 4属性选择方法 属性选择问题作为一个研究热点广泛应用于模式识别、统计学、机器学习等 领域，已经有很多国内外研究人员提出了独特的思想和解决方案【1 2 1 6 1 ，这些方法 通常可分为两种，即过滤法和打包法 过滤法是一种独立于学习算法的属性选择方法，按照某种标准进行属性的筛 选，一般有以下两种筛选标准： ( 1 ) 最小属性子集选择法 从待选属性子集中，选择一个包含属性最少的属性子集，因为通常意义上讲， 属性少的子集会降低时间和空间复杂度，提高学习算法的效率但这种方法也有 很大局限性，比如在对学校学生的学习成绩进行研究，其中的学号是学生的唯一 标识，如果按照这个选择标准，把学号这个单一属性作为候选虽然满足属性选择 的选择标准，但任何学习算法在此基础上进行学习的结果必然很差 ( 2 ) 根据某种评分标准进行属性选择 此种方法利用精确度、独立性、相关性、信息熵、距离等策略对属性进行评 分，但这种方法不能处理冗余属性 过滤法对学习算法的支持性不是很好，却以其计算的高效性，在高维属性选 择中得到很好的应用此外，由于其独立于学习算法，所以过滤法中提供的属性 选择方法也可应用于打包法中 打包法将学习算法作为测试用的黑盒子，利用相关的学习算法对属性子集进 行评价，例如，利用学习算法的交差验证进行属性子集评价此种方法需要一个 属性子集搜索方法的支持，主要分以下几种搜索方式： 1 2 完全式搜索：也称为穷举搜索，它可以确保找到最优的属性子集但由于全 部可能的属性子集的数量是，当属性数量变大时，这种搜索策略是不可行的 启发式搜索：由于穷尽式搜索受到限制，人们考虑利用启发式来引导搜索它 避免了全部的搜索，但同时也冒着丢失最优子集的风险由启发式指导进行的深 度优先的搜索排序的空间复杂度可能是a 妒) 或更低利用启发式搜索策略的算法 非常易于实现，并且产生子集的过程非常快，因为搜索空间仅仅是属性数量的平 方关系 不确定搜索：与前面介绍的两种搜索策略不同，这种策略在搜索下一个集合 时是随机的( 即当前集合没有根据任何先前的集合按照确定的规则有方向地增长或 删减) 这种算法能够不断产生最好的子集，随着时间的推移不断提高所选子集的 质量尽管搜索空间仍然是伙外，但是这种策略通过设置最大可能的迭代次数使 得搜索的子集数量远远小于少所选子集的最优性取决于可利用的资源 打包法的优点是对学习算法的支持度高，缺点是时间复杂度高，效率低 2 4 信息论基础 信息论是人们在长期通信工程实践中，由通信技术与概率论、随机过程和数 理统计相结合而逐步发展起来的一门学科信息论从它诞生的那时起就吸引了众 多领域学者的注意，他们竞相应用信息论的概念和方法去理解和解决本领域中的 问题本节主要介绍信息论的背景、相关概念及其在属性选择中的应用 2 4 1信息论概述 从历史上看，信息论的形式是两部分人共同努力的结果，一部分是通信工程 方面的学者，另一部分是统计数学家通常人们公认信息论的奠基人是美国科学 家香农，他在1 9 4 8 年发表了著名的论文通信的数学原理，为信息论奠定了理 论基础 信息是信息论中最基本、最重要的概念，它是一个既抽象又复杂的概念这 一概念像在实践中提出来的其它科学概念一样，是在人类社会互通情报的实践过 程中产生的在现代信息理论形成之前的漫长时期中，信息一直被看作是通信的 消息的同义词，没有赋予它严格的科学定义到了2 0 世纪4 0 年代末，随着信息 论这一学科的诞生，信息的含义才有了新的拓展 香农在1 9 4 8 年发表了一篇著名的论文通信的数学原理他从研究通信系 统传输的实质出发，对信息作了科学的定义，并进行了定性和定量的描述信息 1 3 是事物运动状态或存在方式的不确定性描述这就是香农信息的定义 信息论在语音信号压缩、图像信号压缩、计算机文件的压缩、计算机网络中 数据传输可靠性的保证、计算机的容错问题、模式分类问题与树分类器的设计等 方面均有成功应用的范例 2 4 2信息论相关概念 ( 1 ) 信息熵 熵是通讯和信息理论中一个非常重要的概念，它是衡量一个随机变量取值的 不确定性程度【l 刀而就数据集合而言，熵可以作为数据集合的不纯度或者说不规 则程度的量度，所谓的不规则程度指的是集合中数据元素之间依赖关系的强弱从 随机过程的角度出发，设x 是离散随机变量，它可能的取值为工的概率为以曲，那 么定义 日( x ) = 一p ( x ) l o g ：p ( x ) x e x 这里月就是随机变量x 的熵，它是衡量随机变量取值的不确定性的量度在 随机试验之前，只了解各取值的概率分布，而做完随机试验后，就确切的知道了 取值，不确定性完全消失了这样，通过随机试验获得了信息，且该信息的数量 恰好等于随机变量的熵，在这个意义上，熵又可作为信息的度量 熵是从平均意义上来表征信源总体信息测度的，熵的计算公式是由 c e s h a n n o n 首次提出的熵这个词是从统计力学中借用来的，在统计热力学中， 熵是一个系统的混乱度的衡量，混乱度越小，熵越小，信息学中的熵是不确定性 的衡量，不确定性越小，即概率越大，熵越小，信息量越小在信息论中，信息 熵只能减少而不能增加，这就是著名的信息不增性原理 在信息论中，熵通常作为某信源所蕴含的信息量的量度在此，川表达了 属性x 所包含的信息量的多少就属性x 而言，熵可以用于衡量该属性的纯度， 一个属性的熵越小，表明属性中的数据在属性域上的分布越不平均，比如属性中 属于某个属性值或某几个属性值的数据较多，而属于另外属性值的数据较少，则 这个数据集合越纯如果一个属性的所有数据都属于同一属性值，那么这个属性 的熵就为0 ，此时该属性所包含的信息为0 ，即该属性在数据集合中不存在对数据 有用的信息反之，一个属性的熵越大，说明数据在属性域上的分布越均匀，那 么这个属性也就越不纯比如，如果属性彳中的数据在属性域上均匀分布，那么 属性的熵最大，其蕴含的信息越多 ( 2 ) 条件熵 1 4 已经知道一个属性x 的不纯度或不规则程度可以用熵来表示，而条件熵则是 衡量在另一个属性y 已知的情况下，该属性的不确定性程度，或者说属性x 对属 性y 的依赖强弱程度 在给定y 条件下x 的熵是条件概率分布p ( a i l b j ) 的熵，也就是：( 其中p ( a i , 幼 是a i 和易的联合概率，而烈研l 幼是给定易条件下a i 的概率) 日( x l y ) = p ( 岛) h ( x i 哆) ，皇i = 一p ( q ，包) l o g ：p ( qi 也) 产l1 = 1 = - p ( b j ) y p ( a i b ) l o g ：p ( 口，i 岛) j = l 1 = 1 从信息论的角度看，条件熵曰闲y ) 表示在已知一随机变量y 的情况下，对另 一随机变量x 的不确定性的度量信息理论证明：条件熵在一般情况下总是小于 无条件熵，即熵与条件熵存在下面的不等式关系： h ( y i x ) 日( 】，) ，日( x l y ) ( x ) 从直观上说，由于事物总是有联系的，因此，在平均意义上，对随机变量x 的了解总能使随机变量】，的不确定性减少这样，对y 的了解也会减少x 的不确 定性 ( 3 ) 互信息 在信息论中，为了更好地描述事物之间的普遍联系，引进了互信息的概念对 于两个随机变量x 和y ，它们之间在某种程度上也是相互联系的，即它们之间存在 着一定的统计依赖关系，互信息量反映了两个随机变量之间相互依存关系的强弱 已知在获知一个随机变量( 如】，) 的取值的条件下，随机变量x 的条件熵脚闭d 总是不大另一随机变量x 的无条件熵曰这样，在已知随机变量】，以后，x 的 不确定度的减少量为月一豳冈y ) ，这个差值实际上就是已知】，的取值后所提供的 有关x 的信息于是定义两个离散随机变量x 和】，之间的互信息眠y ) ，( x ；y ) = 日( x ) 一日( zf 】，) = 一e p ( a i ) l o g ：+ z x p ( a , ，b ) l o g ：p ( qi 岛) i = 1，= lj = l = 喜鼽咖g ：揣 f = i ，= ip t “，y l ， 1 5 , - - m p ( 岛) l o g ：p ( 也) + n mp ( 吩，哆) l o g ：p ( 吃i a i ) j