（统计学专业论文）数据挖掘中基于统计相关的属性选择研究.pdf

摘要 摘要 计算机存储和数据库管理技术的飞速发展，收集和管理海量数据成为可 能；而计算机和数据库管理技术的普及则降低了与之相关的成本，使之成为 现实。面对存储量日益增大的各类数据集，为真正满足决策信息获取的需求， 从海量数据中挖掘或提取有用信息、规则、模式的各类数据挖掘方法和技术 被提出。不相关或冗余噪声数据的存在，以及出于简约建模的考虑，属性选 择相关问题也进入人们的视野。 属性选择作为数据挖掘的一个数据预处理步骤，或归纳学习算法的一部 分，是海量数据建模的一个重要环节，与属性约简一同构成数据挖掘的两种 属性变量处理技术。然而，不同于属性约简的通过属性空间投影减少输入属 性，属性选择以属性变量与目标属性属性间相关与冗余关系测度为基础，根 据事先设定的属性评估准则( 或函数) 来选择数据挖掘模型所需的输入属性。 属性选择结果存在原始属性度量维度的直接缩减，而属性约简则不然，其输 出结果是原始属性测度的线性或非线性组合，不存在原始属性度量维度的减 少。由于其决定着构建模型的输入属性，所以属性选择方法的性能直接影响 着数据挖掘任务算法的输出结果。但是，属性选择方法的性能直接受属性间 相关与冗余关系测度方式、属性空间搜索策略和属性评价函数( 方式) 等三 个因素的影响，三因素的不同组合形成不同的属性选择方法，可以获得不同 的性能输出。故从属性间关系的测度、属性空间搜索策略和属性评估方法等 角度研究属性选择方法对数据挖掘输出性能影响有其直接的理论价值；而数 据挖掘研究的应用导向型特点则决定了其不缺乏现实意义。 属性关系测度、属性空间搜索和属性评价准则共同构成属性选择的三位 一体过程，是属性选择问题的三个核心。属性关系测度的好坏直接表现为由 测度结果所表述的属性间关系的真实与否，是属性评估与选择的基础，对属 性选择输出结果有着直接的影响；属性评价准则，作为属性选择的基准，和 数据挖掘中基于统计相关的属性选择研究 属性测度一样，均对属性输出结果产生直接的影响；属性空间搜索决定着最 优属性或属性子集产生的方式，对属性选择算法的运行时间和空间耗费起决 定性影响。本文主要从第一方面问题不同属性间相关或冗余关系测度对 属性选择方法性能影响着手讨论基于统计相关的属性选择算法对数据挖 掘任务输出的影响。 本文的研究内容分为六章。 第1 章引言。首先陈述数据挖掘产生的时代背景和数据挖掘的意义与作 用；然后，就数据集中不相关、冗余以及噪声数据的存在，阐述属性选择的 必要性和意义，概述属性选择问题研究的发展和其基本特点，并提出本文所 要研究的问题。而后，指出文章所要完成的工作，也就是本文可能的创新之 处。最后，对文章结构安排进行了阐述。 第2 章数据挖掘理论评述。本章分为四节，第一节是对数据挖掘的概念 和定义的回顾与述评，主要介绍了数据挖掘发展的基本历程，数据挖掘的定 义和基本概念，以及数据挖掘知识发现过程等相关内容。第二节是对数据挖 掘的任务和功能的综述，主要介绍了数据挖掘的数据描述与建模预测两大基 本任务，以及基于两大基本任务的5 类基本职能：类概念描述( c l a s s c o n c e p t d e s c r i p t i o n ) 、频繁模式分析( f r e q u e n tp a t t e ma n a l y s i s ) 、聚类( c l u s t e r i n g ) 、分类 ( c l a s s i f i c a t i o n ) 和预测( p r e d i c t i o n ) 、演变分析( e v o l u t i o na n a l y s i s ) 。第三节 是对数据挖掘方法的介绍，主要介绍了本文实证研究中将要采用的5 类预测 建模方法：线性回归( l r ) 、朴素贝叶斯分类( n b ) 、分类树归纳学n ( c 4 5 ) 、 k 近邻( 州) 和神经网络r b f ，以及其基本算法。其次，对属性选择相关 问题进行了简要概述，包括属性关系的测度、属性空间搜索策略、属性选择 流程，以及基于不同测度的属性选择方法。 第3 章属性选择理论评述。本章分为六节介绍属性选择问题。第一节对 属性选择问题进行概述，主要介绍了属性选择的作用和意义，属性选择所需 考虑的三个方面，以及属性选择的应用领域。第二节是对属性选择中属性间 关系测度的述评，主要介绍了距离测度( d i s t a n c em e a s u r e s ) 、信息测度 ( i n f o r m a t i o nm e a s u r e s ) 、相依性测度( d e p e n d e n c em e a s u r e s ) 、分类误差率测 度3 1 和一致性测度【3 1 】等常用测度，并在此基础上对上述属性间关系测度方法 进行了简要评述；最后，对基于属性关系测度的属性评价准则进行了简要说 2 摘要 明。第三节介绍了属性选择算法时间和空间耗费有重要影响的属性搜索策略。 第四节，对两组概念进行了简要辨析，首先介绍了属性选择与属性约简的异 同；而后则对属性选择和模型选择的关系进行了讨论，并指出属性选择实质 也是一种模型选择。第五节，介绍了属性选择的基本流程。最后，在第六节 简要介绍了属性选择的两种基本方式：过滤式和绑定式属性选择。 第4 章基于统计相关的属性选择。本章分三节对基于统计相关的属性选 择进行了讨论。第一节，对统计相关进行基本设定，首先对a l m u a l l i m 与 d i e t t e r i c h ( 1 9 9 1 ) 、j o h n 等( 1 9 9 7 ) 、b l u m a 与l a n g l e y ( 1 9 9 7 ) 和y u 与l i u ( 2 0 0 4 ) 等从不同角度对属性“相关”和属性冗余的讨论和定义进行了回顾， 并在此基础上提出了简单相关和条件相关的定义；接下来介绍了c f s 算法中 将用到的两类属性相关测度：对称不确定性( s y m m e t r i c a lu n c e r t a i n t y ) 和 p e a r s o n 相关，最后，引入适用于数据挖掘任务的v - m 属性相关测度，并介绍 了不同类型属性间相关关系的计算公式。第二节，首先介绍了m a r k ( 1 9 9 9 2 0 0 0 ) 基于统计复合检验理论所提出的属性评估函数m e r i t ，而后考虑属性间间接, 作用关系的存在，提出一个基于偏相关调整的属性选择评估函数m e r i t 。第。 三节是对基于相关的属性选择方法的讨论，首先介绍了m a r k ( 1 9 9 9 ，2 0 0 0 ) 的属 性选择方法c f s ，随后，提出基于属性间v - m 统计测度的属性选择算法 s c f s ( s t a t i s t i c a lc o r r e l a t i o nb a s e df e a t u r es e l e c t i o n ) ，最后提出基于m e r i t 测度s 的属性选择算法p c f s ( p a r t i a lc o r r e l a t i o nb a s e df e a t u r es e l e c t i o n ) 。 第5 章性能分析和评价。本章分四节分别对试验数据、试验方法、试验 输出结果、性能分析评价和算法适用性分析进行了讨论。第一节，重点介绍 试验数据的选择和试验方法的科学设计。第二节给出三种属性选择算法在7 9 个数据集上的结果输出。第三节，对试验结果的分析评价，试验结果表明， 文中所提出的属性选择方法s c f s 及其改进p c f s 在部分数据集中输出结果优 于c f s ，但就总体性能而言，要稍弱于c f s 。为探究数据集的结构特征和属 性选择算法表现之间是否存在直接的关系，文章在第四节以不同属性选择算 法输出差异为选择项，数据集的特征为输入自变量建立l o g i s t i c 离散选择模型。 模型结果表明，数据集的结构特征和属性选择性能表现之间的关系因挖掘任 务模型的不同而有所不同。 数据挖掘中基于统计相关的属性选择研究 第6 章结束语。本章在总结本文研究过程、主要研究结论的基础上，指 出了本研究中所存在的不足，改进的可能以及以后的研究方向。 本文的主要研究结论是，一方面，基于统计相关的属性选择算法s c f s 和p c f s 能够有效地完成数据挖掘建模任务中的属性选择任务。在大多数数 据域中，算法在不明显降低数据挖掘任务输出的前提下，能有效减少不相关、 冗余及噪声属性在数据挖掘任务中的输入，提升挖掘任务学习的效能；在部 分数据域上，算法甚至能提高挖掘任务输出的性能。但其仍存在不足之处， 表现在和c f s 相比，在总体性能表现上仍显不足。但是其在部分数据集上的 表现明显优于c f s ，说明其也有可取之处。同时，基于不同属性选择算法输 出结果和数据集结构特征的离散选择模型输出表明，在数据挖掘任务执行中 不能盲目的选用属性选择方法，而应根据所研究数据集的具体特征和所要训 练学习的数据挖掘任务来进行。 本文的主要贡献和意义在于： 1 从原始属性的统计关系测度入手，提出基于v m 测度的属性选择算法 s c f s 和p c f s ，并通过性能试验验证了算法的可用性和有效性，在部分数据 集上表现优于c f s ； 2 考虑属性间间接作用关系的存在，提出了基于偏相关调整的属性评估 函数m e r i t , ，在探索属性间关系的测度上进行了有益的尝试； 3 拓展了数据挖掘任务执行中可选择属性选择算法的范围； 4 通过实证结果指出，属性选择应基于学习任务以及学习对象本身的数 据结构特点进行，这对数据挖掘工作的开展具有较强的现实意义。 关键词：属性选择数据挖掘 l o g i t 模型 属性相关 4 相关测度 属性冗余 a bs t r a c t g e n e r a l l ys p e a k i n g ，m o r ed a t ao rv a r i a b l e sm e a nm o r ei n f o r m a t i o no r k n o w l e d g e m e n ta b o u ts o m e t h i n go fi n t e r e s tf o ru s h o w e v e rac e n t r a lp r o b l e mi n d a t am i n i n gi sf e a t u r es e l e c t i o nw h i c h i d e n t i f y i n gar e p r e s e n t a t i v es e to ff e a t u r e s f r o mw h i c ht oc o n s t r u c tap r e d i c t i v em o d ef o rap a r t i c u l a r t a s k , d u et ob e i n g i r r e l e v a n t , r e d u n d a n t , a n dn o i s yf e a t u r e s t h e r ea r et h r e ef a c t o r st h a ti n f l u e n c et h ee f f e c to ff e a t u r es e l e c t i o n , w h i c ha r e t h em e a s u r eo ff e a t u r er e l e v a n c et h a tu s e dt os c a l et h ei r r e l e v a n c e ，t h er e d u n d a n c e b e t w e e n t w of e a t u r e s ，s e a r c hs t r a t e g yo ff e a t u r es p a c e ，a n dt h ee v a l u a t i o nr u l eo f f e a t u r es e l c t i o n t h i st h e s i sa d d r e s s e dt h ep r o b l e m so ff e a t u r es e l e c t i o nf o rd a t am i n i n gt h r o u g h as t a t i s t i c a lc o r r e l a t i o nb a s e d a p p r o a c h t h ec e n t r a lh y p o t h e s i si st h a tg o o df e a t u r e s e t sc o n t a i nf e a t u r e st h a tc a l lb e t t e rp r e d i c tt h et a r g e t ，y e tu n c o r r e l a t e dw i t he a c h o t h e r af e a t u r ee v a l u a t i o nf o r m u l a , b a s e do ni d e a sf r o mt e s tt h e o r y , p r o v i d e sa n o p e r a t i o n a ld e f i n i t i o no ft h i sh y p o t h e s i s 【3 3 ，3 4 1 c f s ( c o r r e l a t i o nb a s e df e 栅e s e l e c t i o n ) i sa na l g o r i t h mt h a tc o u p l e st h ea b o v ee v a l u a t i o nf o r m u l a , w h i c h d e v e l o p e db ym a r k ( 19 9 9 ，2 0 0 0 ) h o w e v e rs c f s ( s t a t i s t i c a lc o r r e l a t i o nb a s e d f e a t u r es e l e c t i o n ) a n dp c f s ( p a r t i a lc o r r e l a t i o nb a s e df e a t u r es e l e c t i o n ) a r et w o a l g o r i t h m st h a th a v et h es a m ee v a l u a t i o nf o r m u l aa n dt h es a m eh e u r i s t i cs e a r c h s t r a t r g yw i t hc f s ，h o w e v e r 谢mad i f f e r e n tc o r r e l a t i o nm e a s u r ev 二m 【51 1 恤c h g i v e nb yv j r a y w a r d - s m i t hi nh i sp a p e r c f s ，s c f s ，a n dp c f sw e r ee v a l u a t e da n dc o m p a r e db ye x p e r i m e n t so n a r t i f i c i a la n dn a t u r a ld a t a s e t s ，i n c l u d i n g3 7d a t a s e t sw h o s e p r e d i c t e dt a r g e tf e a t u r e i sd i s c r e t ev a l u ea n d4 0d a t a s e t sw h o s ep r e d i c t e d t a r g e tf e a t u r ei sc o n t i n u o u sv a l u e t h r e ed a t am i n i n ga l g o r i t h m sw e r eu s e d ：n b ( n a i v eb a y e s i a nc l a s s i f i e r ) ，c 4 5 ( a d e c i s i o nt r e el e a r n e r ) ，a n dk n n ( kn e a r e s tn e i g h b o r ) t ot e s ti nd a t a s e t sw i t h d i s c r e t et a r g e tf e a t u r e t w oa l g o r i t h m s ：n n r b fa n dl rw e r eu s e df o ro t l l e r s e x p e r i m e n t sd a t a s e t ss h o w e dt h a tc f s ，s c f sa n dp c f sc a nq u i c k l yi d e n t i f i e sa n d s c r e e n si r r e l e v a n t ，r e d u n d a n t ，a n dn o i s yf e a t u r e s ，b u tc f sw i t hal i t t l e b e t t e r p e r f o r m a n c eo nt h ew h o l e f i n a l l y , w ef o u n do u ti tt h a tt h ep e r f o r m a n c eo f a l g o r t h m si sa f f e c t e db yt h ec h a r a c t e r so fd a t a s e t sa n dt a s ka l g o r i t h m st h r o u g h d e v e l o p i n gal o g i tm o d e lf o re v e r yd a t am i n i n ga l g o r i t h mb a s e do no u t p u to ft h r e e a l g o r i t h m sa n dt h ec h a r a c t e r so fd a t a s e t s k e y w o r d s ：f e a t u r es e l e c t i o nm e a s u r eo fr e l e v a n c e d a t am i n i n g r e l e v a n tf e a t u r e r e d u n d a n tf e a t u r e l o g i tm o d e l 2 西南财经大学 学位论文原创性及知识产权声明 本人郑重声明：所呈交学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已注明引用的内容外，本论文不含任何其他个 人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人 和集体，均已在文中以明确方式标明。因本学位论文引起的法律结果完全由 本人承担。 本学位论文成果归西南财经大学所有。 特此声明 学位申请人： 年月日 1 引言 1 1 问题的提出 1 引言 2 0 世纪六、七十年代以来，计算机科学技术的飞速发展使得存储或获得 海量数据成为可能，数据存储成本的不断降低则加速了这一过程的发展。因 为数据生成和积聚的量超过了分析人员所能分析的数量【7 】，建立一套方法来从 数据库中自动分析数据和进行知识发现将是一种必然性选择【l j 。面对日益丰 富的数据，为满足从中发现有用信息的需要，首先发展起来的是用于获知特 定对象属性特征的数据库查询技术；然而，随着提供查询和事务处理的大量 数据库系统广泛付诸实践，人们不再满足于数据库系统的简单查询功能，提 出了更深层次的需求和问题：如何从海量的数据中提取( 或学习) 有用的潜 在信息、知识和规律? 对这一问题，人们进行了有益的探索，其结果是导致 了处理大型或海量数据的数据挖掘技术的产生和发展。 数据挖掘出现于2 0 世纪8 0 年代后期，9 0 年代有了突飞猛进的发展并可 望在新千年继续繁荣【2 l 】。数据挖掘从机器学习、统计学、数据库等多学科领 域汲取营养，发展了一套适合自身特点的数据挖掘方法和数据处理手段，用 于知识学习、信息提取和结果可视化展现。其处理和学习的对象则是来自于 不同社会、经济领域的大量的日常业务数据或试验观察数据。一般来说，更 多的数据应包含更多的信息，更多属性变量意味着被观察研究对象更多方面 信息的获取。但是，数据挖掘任务建模过程中，在考虑模型拟合效果、任务 系统运行时间和数据存储空间限制的前提下，对某些数据集而言，包含所有 或更多的属性变量的模型并不一定是最适合、最满意的( 或最优的) 模型。 这是因为数据集中存在和学习任务不相关的属性变量，或者是高度相关而冗 余属性变量，它们会导致无效的归纳和降低学习的效率【l 。最近的研究表明， 数据挖掘中基于统计相关的属性选择研究 简单最近邻算法( k n n ) 对不相关属性非常敏感它的样本复杂度( 达到 给定精度所需最低样本量) 与冗余属性呈指数性增长【3 引。决策树算法，如c 4 5 ， 有时可能过度拟合数据，从而获得较大的树，在许多情形下，去掉不相关或 冗余的信息可使得c 4 5 产生更小的树【2 7 】。朴素贝叶斯分类算法由于其给定类 的属性独立性假设，冗余属性的存在也可能影响其分类表现【3 7 】。大量的实证 研究结果表明，属性选择在提高学习任务的效率、任务预测的精度和增强、 获得规则的可理解性等方面是较有成效的【2 7 3 2 1 。由此，可知在数据挖掘任务 建模过程中，通过一定的方式和方法去掉不相关或冗余属性，进行属性变量 选择往往可以获得更令人满意的知识学习模型。这也就引发并促进了有关属 性选择问题的研究和讨论。 属性选择通常作为数据挖掘的一个数据预处理步骤，或归纳学习算法的 一部分，是机器学习、模式识别和海量数据挖掘建模的一个重要环节，其输 出直接影响模型的输出结果，属性选择方法的改进也就直接意味着模型输出 性能的改进。自上世纪七十年代以来，属性选择研究不断发展，目前，在统 计模式识别、机器学习和数据挖掘等学科领域，属性选择已经成为一个较为 成熟的研究和开发领域；在与之相关的属性相关测度、属性选择规则开发和 算法设计等方面也取得了丰硕的成果。 属性选择研究从讨论属性与数据挖掘或机器学习任务的相关测度出发， 研究不同的属性关系测度方法、属性空间搜索策略和搜索方法对于建模结果 的影响，最后从建模结果、算法运行空间和时间耗费等角度评判相应方法和 策略的优劣。有选择必然需要一定的评价和比较标准。要从众多属性中选出 有用且不影响模型效果的属性，没有合理而有效的属性评价标准，其过程将 是不可想象的。或许应用领域的专家可以挑选出一些有用的属性，但是这将 是一项困难而费时的任务，特别是当数据结构非常复杂时，更是如此。因此， 建立一套自动化的属性评判和选择标准或方法将是完成属性选择任务所必须 走出的一步。一般的属性评价和选择标准均从预测属性与目标属性和模型目 标之间的关系角度出发，通过量化的方法评价和选择属性。越能真实地反映 属性变量之间的关系，通过属性选择步骤所获得的模型将越接近真相。但是 如何测度属性变量之间的关系才能获得更好的属性选择和建模结果呢? 如何 评价和选择属性，以什么为标准或评价函数才能既可选择更少的属性又能改 2 i 引言 进或不降低模型输出的性能呢? 现有的属性间关系测度方法是否合理，有无 改进之处? 如何改进? 这都将是属性选择和数据挖掘建模研究人员不得不考 虑和面对的问题。 近年来，在基因图谱、文本分类、图像恢复、气象预报、空间科学研究 和客户关系管理等领域，随着数据库技术的发展，其存储数据在实例的数量 和属性的数量上都有了巨大的增长。这两个方面数量上的增长，一方面，对 学习算法的可伸缩性提出了新的挑战；同时，数据集属性的增加，也使得人 们不得不面临高维稀疏等数据问题。正如人类社会新问题的出现往往导致相 关领域的飞速发展一样，这些问题的出现也促进了属性选择问题相关领域的 研究和开发，使得针对相应领域和任务的学习算法和方法不断被提出，不断 被改进，数据挖掘软件的相关功能模块也不断被增加或更新。如，s a se m 4 1 的变量选择只有在线性回归和l o g i s t i c 模型里有，而且是沿用传统统计变量 选择的后向删除、前向增加、逐步回归，增减变量的依据是f 值改变量( 多 元线性回归) 和z 2 改变量( 1 0 9 i s t i c 模型) ；s p s sc l e m e n t i n e 和s q l s e r v e r 数据挖掘模块使用的变量选择方法仅仅通过测度评估单个预测变量和结果变 量直接的关联或相关关系来选择后提出属性变量，没有联合选择变量子集的 功能；而开源数据挖掘软件平台w e k a 新增了m a r k ( 1 9 9 9 ，2 0 0 0 ) 基于属性间相 关测度的属性选择算法c f s ，从属性集合的角度来讨论选择属性或属性子集的 选择。 1 2 本文所要完成的工作 针对属性选择所面对的问题，本文在总结前人有关数据挖掘及属性选择 理论研究的基础上，对以下几个方面问题进行了讨论： 1 辨析以下几组概念： ( 1 ) 属性选择( f e a t u r eo ra t t r i b u t es e l e c t i o n ) 与模型选择； ( 2 ) 属性选择与属性约简( a t t r i b u t er e d u c t i o n ) 。 2 “属性相关 和“属性冗余定义； 3 基于m a r k ( 1 9 9 9 ，2 0 0 0 ) 属性选择算法c f s ，引入v j r a y w a r d - s m i t h ( 2 0 0 7 ) 提出的适用于数据挖掘应用的属性间相关测度统计量，提出新的属 3 数据挖掘中基于统计相关的属性选择研究 性选择算法s c f s ，以及在其基础上经偏相关调整的属性选择算法p c f s 。 4 s c f s 、p c f s 与c f s 算法试验性能比较； 5 基于数据集变量属性特征和数据挖掘算法特点的属性选择方法适用性 分析。 1 3 本文结构 在以上讨论基础上，第2 、3 章评述数据挖掘和属性选择等相关研究，辨 析属性选择、模型选择和属性约简等概念；第4 章讨论基于统计相关的属性 选择算法s c f s 和p c f s 的构建，及其与c f s 的异同；第5 章以s a s 9 1 和 w e k a 3 5 7 为试验平台，实证比较3 种属性选择算法的性能，并根据实证结果 建立离散选择l o g k 模型讨论分析属性选择算法的数据集和数据挖掘任务适 用性；最后，第6 章对本次研究进行总概，讨论研究之不足，以及改进之可 能。 4 2 数据挖掘理论述评 数据挖掘理论述评 2 1 数据挖掘：概念和定义 随着计算机技术的迅猛发展以及数据库管理技术的逐渐普及，数据信息 的获取和存储成本不断下降，数据库的规模、范围和深度都在快速不断扩大， 人类社会逐渐为各类数据信息所淹没。起始于2 0 世纪6 0 年代的数据库管理 技术，尽管早已系统地从原始的文件处理演变到复杂地和功能强大的数据库 系统；同时数据库系统的研究和开发也已经从早期的层次和网状数据库系统 发展到开发关系数据库系统、数据建模工具以及索引和存取方法【2 l 】；此外， 联机事务处理( o l 心) 也已得到广泛的应用。但是数据库技术的发展仍不能 满足人们对海量数据中潜在的有价值信息、知识和规律的提取等高级数据分 析【2 l 】的需求。于是，- - i - j 跨多学科领域的新的学科领域产生了，这就是数据 挖掘( d a t am i n i n g ，d m ) 。 数据挖掘( d a t am i n i n g ) 这一概念最先于1 9 9 5 年在美国计算机年会 ( a c m ) 上被提出。数据挖掘是“d a t am i n i n g ”的一种较为形象的译法，充 分体现了从海量、有噪声数据中发现知识这样一个过程。此外，国内也有学 者把其译为“数据采掘 、“数据开采”、或“数据采矿。 就定义而言，不同的学者，有不同的理解，许多人把数据挖掘视为另一 个常用术语数据中的知识发现( k d d ，k n o w l e d g ed i s c o v e r ya n d d a t a m i n i n g ) 的同义词，而另一些人则认为数据挖掘是知识发现的一个基本步骤。知识发 现过程如图2 1 所示，由以下步骤组成【2 l 】： 1 数据清理：消除噪声和不致数据； 2 数据集成：多种数据源的组合； 3 数据选择：从数据库中提取与分析任务相关的数据： 数据挖掘中基于统计相关的属性选择研究 4 数据变换：改变数据形式，使其适用于相应的数据挖掘形式，如数据 转换、汇总，或聚集： 5 数据挖掘：根据相应的数据挖掘算法提取数据模式； 6 模式评估：根据某种兴趣度度量，识别出有用( 或有趣) 模式； 7 知识解释和表示：使用可视化和其他知识表示技术，把有用模式表达 为客户能够理解的语言文字和图示，向用户提供所挖掘的知识。 r ：； 图2 1 ：知识发现过程 步骤1 4 组成数据预处理过程，为数据挖掘准备数据；步骤5 - 6 为根据任 务目标所开发算法的有用知识学习过程；步骤7 则是规则解释和可视化表达 过程；所有这些步骤构成了整个的知识学习过程。本文采用前一种观点，把 数据挖掘看成一个从数据准备开始到知识解释和表示的知识发现过程。这可 以用一个通用的定义表述为：从大量的、不完全的、有噪声的、模糊的、随 机数据中、发现和提取隐含在数据中的、人们事先未知的、但潜在有用的信 息和模式的过程【5 8 】。 此外，不同应用领域的研究人员根据不同的目的和需要，还提出了许多 和上述定义相近的术语，如知识提取、信息发现( i n f o r m a t i o nd i s c o v e r y ) 、数 据模式分析、数据考古、信息收割( i n f o r m a t i o nh a r v e s t i n g ) 和数据捕捞( d a t a a r c h e o l o g y ) 等 2 1 1 。 6 2 数据挖掘理论述评 2 2 数据挖掘的任务和功能 一般而言，数据挖掘任务可以分为两类：描述和预测【2 1 i 。描述性挖掘任 务描述数据库中数据的一般特征和性质。预测性挖掘任务对当前数据进行推 断，以做出预测。具体而言，描述性挖掘任务用于发现数据分布特征和属性 之间的关联和相关；而预测性挖掘任务则在数据特征描述的基础上对数据的 某一方面或属性特征进行判定，推测事物发展演变的趋势和走向。根据任务 执行过程中所使用方法、模式的不同，前者包含以数据特征化和区分1 为方法 的概念类描述、以相关和关联为基础的频繁模式挖掘，以及以发现数据集聚 特征为目的的聚类分析；后者，则有分类与预测、离群点2 探测和演变分析。 综合两类任务的不同具体功用，可以获得当前数据挖掘的5 类主要模式类型 和功能： 1 类概念描述( c l a s s c o n c e p td e s c r i p t i o n ) ：用汇总的、简洁的和精确的方 式描述各个类和概念以表现数据和类或概念之间的可能关联。这类描述可以 由以下几种方式实现：( 1 ) 数据特征化，一般地汇总所研究类( 通常称为目 标类( t a r g e tc l a s s ) ) 的数据；( 2 ) 数据区分，将目标类与一个或多个可比较 类( 通常称为对比类( c o n t r a s t i n gc l a s s ) ) 进行比较；( 3 ) 数据特征化和比较。 2 频繁模式分析( f r e q u e mp a a e ma n a l y s i s ) ：以数据之间存在的关联或相 关特性为基础，发现和找出事务之间所存在的有趣模式。事物之间由于其内 在的关联和相关特性，当一事物发生时，另一事物也将会以较大的概率发生。 而数据是事物特性的一种抽象化描述，所以我们可以通过分析数据中所表现 出的这种相关和关联程度，来分析事物之间的本质联系。这种方法如若用来 分析行为之间的前后联系，则又称为序贯分析。 3 聚类( c l u s t e r i n g ) ：通过描述事务之间的集聚特性把事务划分为不同的 类，以便增强对客观事物的认识，是概念描述【2 1 】和偏差检测【5 6 】的先决条件。 1 数据特征化( d a t ac h a r a c t e r i z a t i o n ) 是目标类数据的一般特性或特征的汇总。通常，用户指定类的数 据通过数据查询收集。例如，为研究上一年销售增加1 0 的软件产品的特征，可以通过执行一个s q l 查 询收集关于这些产品的数据。 数据区分( d a t ad i s c r i m i n a t i o n ) 是将目标数据对象的一般特性与一个或多个对比类对象的一般特性进行 比较。目标类和对比类由用户指定，而对应的数据通过数据库查询检索。 2 这里所说的离群点( o u t l i e r ) 是异常值的另一种说法，指数据库中可能包含的一些与数据一般行为或 模型不一致的数据对象。 7 数据挖掘中基于统计相关的属性选择研究 如市场营销中的消费者细分，以及根据社会经济发展程度对国家和地区的划 分。 4 分类( c l a s s i f i c a t i o n ) 和预测( p r e d i c t i o n ) ：前者按照分析对象的属性、 特征，根据预设的类别把其划分到不同的类。数据挖掘的这一功能在实践中 已得到较为广泛的应用，如银行、系统的客户信用等级划分，保险公司的客 户价值管理。此外，网络安全领域的入侵检测，银行、保险公司的欺诈分析 等均以此功能为基础。当把发生几率很小的对象看作一类时，分类就是离群 点探测。而后者则建立连续值函数模型，根据事物的属性、特征值推断事物 在目标属性、特征上的表现。两者均是完成数据挖掘盼推断预测任务，不同 之处在于目标属性特征是否为离散或连续值。 5 演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或 趋势，并对此进行建模。分析过程可能包括时间相关数据的特征化、区分、 关联和相关分析、分类、预测或聚类。其分析所具有的独特特点是包含时间 序列数据分析、系列或周期模式匹配和基于相似性的数据分析。 数据挖掘过程是一个知识发现的复杂过程，源于不同的数据挖掘任务， 其可能包含以上功能中的几个或全部。有时，为达特定分析目的，不同功能 之间需要配合使用。如，在网络安全防护中，我们首先需要使用类似于聚类 的功能找出具有入侵性质的数据流；而后，才可能根据网络数据流的不同特 质对具有入侵性质的数据流进行防范。 2 3 数据挖掘方法 数据挖掘作为一门跨统计学、机器学习、人工智能等多学科领域的、新 兴的学科领域，大量从其他基础学科领域汲取营养，形成了其独特的基于问 题( 或数据挖掘学习任务) 的高级数据分析和知识提取方法体系：不同的数 据挖掘任务具有不同的数据挖掘方法；对于同一问题( 或任务) 的处理，可 选择各具特点的不同学科领域方法( 或算法) 。例如，处理描述性挖掘任务有 数据特征化和数据区分等概念抽象和数据汇总概要处理；预测性挖掘任务因 目标变量属性的不同有分类和预测方法。此外，对于银行、保险公司客户欺 诈分析问题，根据不同的需要，可以选择基于不同学科领域的方法，如传统 8 2 数据挖掘理论述评 统计分类法、朴素贝叶斯( n a i v eb a y e s i a n ) 或其改进方法、支持向量机( s v m ) 、 决策树和神经网络( n n ) 等。 根据本文的需要，我们选择性介绍与预测性挖掘任务相关的一些典型数 据挖掘方法及其基本算法。 1 决策树归纳分类( c 4 5 ) 决策树归纳是建立在信息论基础之上，按一定的属性度量和选择准则对 数据对象进行分类的一种方法，由于归纳学习到的知识被表示成一棵决策树 形式而得名。最早的决策树归纳算法，i d 3 ( i t e r a t i v ed i c h o t o m i s e r ，迭代的二 分器) 1 2 4 ，由机器学习研究者j r o s sq u i n l a n ，在扩展e b h u n t ，j m a r i n 和 p t s t o n e 的概念学习系统基础上，于2 0 世纪7 0 年代后期和8 0 年代初期开发。 此外，决策树归纳最主要并且被广泛应用于医疗诊断、金融信贷评估的两种 算法c 4 5 2 2 牙- i c a r t 2 8 1 ( 分类与回归树) 分别由q u i n l a n 与l b r e i m a n ，j f r i e d m a n ，r o l s h e n 和c s t o n e 等几位统计学家提出。 i d 3 、c 4 5 和c a r t 均采用贪心( 即非回溯的) 搜索方法，决策树以自顶 向下的方式从训练元组集和相关联的类标号递归的构造。随着树的构建，训 练集递归地划分成较小的子集。基本决策树算法概括如图2 2 【2 1 1 。 以上三种决策树归纳方法在从训练元组学习决策树时采用了类似的策 略。而方法之间的不同在于各自采用不用的属性选择度量。i d 3 使用信息增益 2 4 】作为属性度量；c 4 5 的属性度量是信息增益率( i n f o r m a t i o ng a i nr a t e ) 2 3 】： 而c a r t 则以基尼指数( g i n ii n d e x ) 2 8 1 为其属性度量。此外，许多基于其他 属性度量方式的一些决策树归纳算法也已被开发出来，如，基于z 2 度量的 c h a i d t 9 】和基于c s e p t 5 0 1 、g 统计量( r s o k a la n df r o m b i o m e t r y f r e e m a n ，1 9 8 1 ) 的方法等。 一般而言，决策树归纳法用于对离散性属性进行归纳学习效果更好。尽 管在连续属性离散化条件下，该方法用于连续属性数据集分类也可获得较好 的分类效果。但是，连续型属性变量的离散化过程将损失类内的距离信息， 从而可能影响归纳学习的效果。 9 数据挖掘中基于统计相关的属性选择研究 算法：g e n e r a t e d e c i s i o n _ t r e e 。由数据划分d 的训练元组产生决策树。 输入： 数据划分d ，是训练元组和对应类标号的集合； 候选属性的集合； a t t r i b u t e s e l e c t i o n _ m e t h o d ，一个确定“最好”地划分数据元组为个体类 的分裂准则的过程。这个准则由分裂属性和分裂点或分裂子集组成。 输出：一棵决策树 方法： 1 )创建一个节点n ： 2 ) 如果d 中的元组都是同一类c ，则 3 ) 返回n 作为叶节点，以类c 标记； 4 ) 如果a t t r i b u t e1 i s t 为空，则 5 ) 返回n 作为叶节点，标记d 中的多数类； 6 ) 如果a t t r i b u t e j i s t 不为空，使用a t t r i b u t e _ s e l e c t i o n _ m e t h o d ( d ，a t t r i b u t e l i s t ) ，找出“最好”的s p l i t t i n g _ c r i t e r i o n ； 7 ) 用s p l i t t i n g _ c r i t e r i o n 标记节点n ； 8 ) 如果s p l i t t i n gc r i t e r i o n 是离散值，并且允许多路划分，则 9 ) a t t r i b u t e l i s t - - a t t r i b u t e l i s t s p l i t t i n g _ a t t r i b u t e ： 1 0 ) 对于s p l i t t i n g _ c r i t e r i o n 的每一个输出j 1 1 )设d ；是d 中满足输出j 的数据元组的集合； 1 2 ) 如果d ：为空，则 1 3 )增加一个树叶到节点n ，标记为d 中的多数类； 1 4 ) 否则增加一个由g e n e r a t e _ d e c i s i o n t r e e ( d ；，a t t r i b u t e _ l i s t ) 返回 的节点到节点n ； 图2 - 2 ：由训练元组归纳决策树的基本算法 2 贝叶斯分类 以贝叶斯定理为基础的贝叶斯分类从概率角度来预测数据元组类别归属 关系的可能性。基于属性独立性的不同假设，贝叶斯分类法又划分为以类条 件独立为假设的朴素贝叶斯分类法( n a i v eb a y e s i a nc l a s s i f i e r ，或被称为简单 贝叶斯分析) 和以属性子集之间条件独立为假设的贝叶斯信念网络( b a y e s i a n b e l i e f n e t w o r k ) 。此外，由于概率计算方法的不同，还有基于核的非参数贝叶 斯方法1 4 j 。 简单贝叶斯分类法以贝叶斯定理为基准，按以下步骤进行工作： 1 ) 分割数据集，获得训练数据元组和相关联的类标号的集合d ； 2 ) 计算预测元组在属性x 条件下，属于类c i ( i - l ，2 ，m ) 的后验 概率： 1 0 2 数据挖掘理论述评 e ( c ：塑g 塑g ! , i x ) p 3 ) 根据最大后验假定，判定各数据元组的类别归属。 在后验概率的计算过程中，如果先验概率未知，一般可使用各