（计算机应用技术专业论文）基于ejb的数据分析助理系统的研究与设计.pdf

基于e j b 的数据分析助理系统的研究与设计 摘要 数据挖掘在各个领域中有着广泛的应用前景，是进行数据分析的重要工具。 企业在使用数据挖掘时，面临应用的分布性和对大数据集的挖掘需求这两个 应用方面的问题。此外，还有企业本身的软硬件环境的限制。如何充分利用企业 现有的软硬件资源，既能利用好数据挖掘这个强大的分析工具，满足应用需求， 又能方便管理和节约成本，已成为亟需解决的问题。 本文提出了构建适应企业环境的通用型数据挖掘系统的解决方案。该方案包 括近似挖掘技术的应用，以适应对大数据集挖掘进行的需求。设计和实现了基于 e j b 的数据分析助理d a a ( d a t aa n a l y s i sa s s i s t a n t ) 原型系统，并在该系统中 进行挖掘实践。 在企业实际应用中，挖掘系统对大数据集挖掘的支持是必要的。本文通过理 论分析和模拟实验，探讨了使用近似挖掘技术进行大数据集挖掘的途径，最后归 纳出实现近似挖掘的三个要点，即算法、挖掘框架和挖掘思路应用。 原型系统d a a 的功能涉及浏览、统计和数据挖掘等方面，其核心功能是数据 挖掘。本文对d a a 系统设计的论述包含基本功能的实现和系统性能的优化两个方 面内容。 设计工作主要包括挖掘系统体系结构设计、挖掘服务器端设计和客户端设 计。体系结构设计包括多层服务的划分和e j b 体系的选择。服务器端设计是工作 重点，包括e j b 服务设计和w e b 服务设计。客户端设计涉及界面设计、任务描述 和模型描述等内容。 在系统性能优化方面，结合了几个旨在提离系统性能的解决方案和技术。包 括粗粒度访问方案、中间数据管理技术、挖掘的异步通信技术等内容。 最后给出一个典型的应用实例，即d a a 在银行贷款系统的应用，包括分析人 员进行建模和客户应用模型两个方面。同时给出了近似挖掘技术在挖掘实践过程 中的应用实例。 关键词：数据挖掘；近似挖掘技术；e j b ：系统设计 基于e j b 的数据分析助理系统的研究与设计 a b s t r a c t d a t am i n i n gh a sg r e a ta p p l i c a t i o n p r o s p e c ti nt h er e a lw o r l d i t sa ni m p o r t a n tt o o l i nd a t aa n a l y s i s a sd a t am i n i n g t e c h n o l o g yu s e di ne n t e r p r i s e s ，t w oa p p l i c a t i o np r o b l e m sr i s e ，o n e i st h ed i s t r i b u t i o no f a p p l i c a t i o n ，a n dt h eo t h e ri st h en e e do fm i n i n gl a r g ed a t a s e t m o r e o v e r 也el i m i t a t i o no fs o f t w a r ea n dh a r d w a r ec o n d i t i o n si ne n t e r p r i s e ss h o u l db e c o n s i d e r e d t h u saf e a s i b l es o l m i o n ，w h i c hi sa b l et om e e tt h e r e q u i r e m e n to f a p p l i c a t i o n a n de n v i r o n m e n ts t a t u sf r o m e n t e r p r i s e s ，i su r g e n t l yd e m a n d e d t h i s p a p e r i n t r o d u c e sas o l u t i o nt od e v e l o pa g e n e r a l p u r p o s ed a t am i n i n gs y s t e m m a tc a na d a p tt ot h ee n v i r o n m e n to fe n t e r p r i s e s t h i ss o l u t i o na l s oi n c l u d e st h e a p p l i c a t i o no fa p p r o x i m a t e l ym i n i n gt e c h n o l o g yt om e e tt h er e q u i r e m e n to fm i n i n g l a r g ed a t a s e t w ed e s i g na n di m p l e m e n t t h ed a a ( d a t a a n a l y s i sa s s i s t a n t ) p r o t o t y p e s y s t e m ，t h e nc a r r i e do u tm i n i n gp r a c t i c ew i t ht h i ss y s t e m a sm i n i n gl a r g ed a t a s e ti sn e c e s s a r yi nr e a lw o r l d ，t h r o u g ht h e o r e t i c a lr e s e a r c h a n ds i m u l a t i n gt e s t ，w ec o m et ot h ec o n c l u s i o nt h a tt h e r e r et h r e em a i n p o i n t sn e e d e d i n p e r f o r m i n ga na p p r o x i m a t e l ym i n i n gp r a c t i c e t h e t h r e em a i np o i n t si n c l u d e s u p p o s i n ga l g o f i t h m s ，m i n i n gf r a m e w o r ka n dt h ec o n s i d e r a t i o no fa p p r o x i m a t e l y m i n i n gt e c h n o l o g yd u r i n gm i n i n gl a r g ed a t a , s e t 。 t h ef u n c t i o n so fd a ai n c l u d eb r o w s i n g , s t a t i s t i c sa n dd a t am i n i n g t h ec o r e f u n c t i o ni sd a t a m i n i n g t h e d i s c u s s i o no nd a as y s t e m d e s i g n i n c l u d e st h e i m p l e m e n t a t i o n o ff u n d a m e n t a lf u n c t i o n sa n dt h e o p t i m i z a t i o n o ft h e s y s t e m s p e r f o r m a n c e ， d e s i g nw o r k i n c l u d e ss y s t e ms t r u c t u r ed e s i g n ，s e r v i c ed e s i g na n dc l i e n ti n t e r f a c e d e s i g n a st os y s t e ms t r u c t u r ed e s i g n m u l t i t r i e da p p l i c a t i o na r c h i t e c t u r ea n de j b t e c h n o l o g yi s c o n s i d e r e d s e r v i c ed e s i g ni st h em a j o rw o r k ，w h i c hi n c l u d e se j b s e r v i c e d e s i g na n d w e bs e r v i c e d e s i g n w h i l ec l i e n t i n t e r f a c e d e s i g n i n c l u d e s i n t e r f a c ed e s i g n t a s kd e s c r i p t i o na n dm o d e l d e s c r i p t i o nd e s i g n o n a s p e c t o fo p t i m i z a t i o n ，w ec o m b i n e d s e v e r 越k e y s o l u t i o n s i n c l u d i n g c o a r s e - g r a i n e da c c e s s i n gm e t h o d ，i n t e r m e d i a t e d a t a m a n a g e m e n tt e c h n o l o g ya n d a s y n c h r o n o u sc o m m u n i c a t i o nt e c h n o l o g yi nm i n i n gp r o c e d u r et oi m p r o v es y s t e m s p e r f o r m a n c e ， a tt h ee n d ，at y p i c a la p p l i c a t i o ne x a m p l e d a au s e di nb a n kl o a ns c e n a r i oi s p r e s e n t e d t h e s c e n a r i o so fb u i l d i n gm o d e lb ya n a l y s t sa n d a p p l y i n gm o d e lb y c u s t o m e r sa r ei l l u s t r a t e d a ni n s t a n c eu s i n ga p p r o x i m a t e l ym i n i n gt e c h n o l o g yi sa l s o p r e s e n t e d ， k e y w o r d s ：d a t a m i n i n g ；a p p r o x i m a t e l ym i n i n gt e c h n o l o g y ；e j b ；s y s t e md e s i g n i l y7 3 4 2 2 0 基于e j b 的数据分析助理系统的研究与设计 第一章绪论 1 1 数据挖掘的应用现状 随着数据库技术的成熟和发展，以及数据库管理系统在各个领域中的广泛应 用，人们积累的数据越来越多。如何更好地利用现有地数据，对其进行深层次的 分析，甚至转化成有价值的信息和知识，已经日益成为迫切需要解决的问题。传 统的数据库系统可以高效实现数据录入、查询、索引、统计等事务性功能，然而 对发现隐藏在数据背后的知识却无能为力，导致出现“数据爆炸但知识贫乏”的 现象。于是，数据挖掘应运而生，开始在数据分析方面大显身手。可以说，数据 挖掘技术是数据库技术和信息技术发展的演化结果。 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的或者随 机的数据中，提取隐含在其中的、人们事先未知的、而又是潜在的有用信息和知 识的过程1 1 】。数据挖掘通过发现有用的新规律和新概念，提高了数据拥有者对大 量原始数据的深层次理解、认识和应用。与之相似的概念称为知识发现。 知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e s ) 是用数据库管理系统来存储数 据对象，用机器学习的方法来分析数据，挖掘大量数据背后毖藏的知识，也就是 数据库中的知识发现1 “。 在实际术语使用中，数据挖掘和知识发现往往被认为是同义词。从更为细致 的区分角度看，数据挖掘是知识发现的一个步骤。 数据挖掘技术从开始就是面向应用的，在各行各业的数据分析活动中，显示 了广阔的应用前景1 1 , 2 , 3 1 。比如，数据挖掘已经在银行业、保险业、证券投资业、 零售业、通信业、电子商务与互联网应用、科学研究、医药、生物与基因工程等 领域得到了应用。数据挖掘解决了具体的问题，比如，在市场营销中，可以通过 分析分销渠道的状况，建立利润评估模型，以便控制风险：在客户关系管理方面， 实现客户分类功能或客户行为分析功能，便于开展客户资源的管理；在电子商务 中，可以实现网上商品推荐、个性化网页、自适应网站建设：在金融保险业，可 以利用欺诈行为识别模型预防欺诈；在证券系统中，可利用行情预测模型进行分 析；在机场管理方面，可以进行旅客人数预测和货运优化：在制造业中，对生产 进行质量监控和预测；在基因工程中，可以对d n a 进行分类和识别；在企业应 用中，数据挖掘可以作为一种强有力的分析工具，支持管理决策。 1 2 企业的具体问题和解决方案 1 2 1 具体问题分析 1 、应用要求 在实际应用中，各个部门对本身的数据都有分析的需求，数据挖掘涉及的内 第1 页 基于e j b 的数据分析助理系统豹研究与澄计 容千差万别。企业应用数据挖掘时，需要解决的两个问题是： ( 1 ) 适应应用的分布性。 应用的分布性体现在两个方面，是，用户是分布的。一般来说，存在两种 需要挖掘服务的用户，一种是企业内部的数据分析人员，另一种是企业外部的客 户。数据分析人员可能处在企业的不同部门，需要对本部门的数据进行挖掘，以 便提供针对本部门的决策支持。从客户端一服务器的观点看，分析人员是申请挖 掘服务的用户。不少企业从本身业务特点出发，需要根据客户提交的个人信息对 客户进行在线评分( s c o r i n g ) ，这时客户实际是申请挖掘模型廒用服务的用户。二 是，待挖掘分析的数据对象也是分布的。数据可能来自不同部门的数据库，各种 平面文件，甚至数据仓库中立方体的数据。 ( 2 ) 适应各种数据集，尤其是大数据集的挖掘。 一般企业的数据相当庞杂，有来自销售部、财务部、人力资源部和生产部等 各种部门的各种数据，大数据比比皆是。比如，来自销售部门的交易数据可能每 天就有成千上万条。挖掘大数据集的难度比挖掘小数据集的要大褥多，对挖掘系 统的性能有较高的要求。 2 、软硬件环境 数据挖掘本身是一种计算密集的分析处理过程，需要使用大量的内存和c p u 资源，尤其是对大数据集的挖掘。这就要求有较高的硬件配置。而许多企业中， 特别是中小型企业，现有的软硬件环境相当有限，他们往往无法承担为各个部门 配置高性能的机器所需的费用。 在软件配置方面，专业挖掘软件虽然针对性强，一般对指定业务的挖掘效果 很好，但通常只适应于特定部门，比如财务部门、销售部门等。或者针对某一行 业，比如零售业、电信业、航空业等。对于很多企业内各个部门都需要获得有效 的数据分析服务，这就意味饕需要购买各种专业挖掘软件，软件配置成本很高。 显然，通用型的挖掘软件是一种很好的选择。 3 、结论 如果数据挖掘系统不能很好地适应企业的应用特点和现有的软硬件环境，数 据挖掘应用的推广将受到限制。那么，能否构建一种挖掘系统，既能适应企业现 有的软硬件环境，又能有效提供企业各个部门，企业内外用户的分析服务是值得 研究和探讨的。简单来说，构建一个有效又经济的挖掘系统是被高度期待的。 1 2 2 解决方案 本文提出了构建适应企业环境的通用型数据挖掘系统的方案，并进行相关研 第2 页 基于e j b 的数据分析助理系统的研究与设计 究和设计。通用型指系统的应用不针对某个特定行业，不限于某种类型的数据集， 这要求系统本身具备较齐全的挖掘算法库。企业级则区别于实验型系统，必须考 虑分布( 数据源、用户) 使用，多用户，大数据挖掘对象等实际应用环境，而且 系统设计应当符合经济规律，也就是说必须考虑到节约成本，包括管理维护成本、 硬件配置成本、软件开发成本、用户培训成本等方面。 本文的方案对实际应用问题的解决途径概括如下： ( 1 ) 选择e j b 策略构建基于分布计算技术的分析系统，有效解决了企业分布 应用问题，并且降低复杂软件的开发成本： ( 2 ) 系统允许结合近似挖掘方案，可以实现对大数据集的挖掘i ( 3 ) 采用多层体系结构，降低了管理维护成本和硬件配置成本： ( 4 ) 采用半紧藕合结构，提高了系统效率，又具备灵活性； ( 5 ) 集成各种挖掘功能，包括分类、聚类、关联规则等，体现系统的通用性； ( 6 ) 开发界面友好的客户端，对任务定义、挖掘结果展现的可视化支持，提高 了系统的易用性，降低了用户的培训成本。 1 3 本文的主要工作和创新之处 本文针对企业的软硬件环境，以及数据挖掘在实际应用中存在的问题，提出 基于e j b 的数据挖掘系统设计的解决方案，通过数据分析助理d a a ( d a t a a n a l y s i sa s s i s t a n t ) 原型系统的设计和实现，对解决方案的可行性和系统的效率 进行了研究和验证。 1 3 1 主要工作 ( 1 ) 研究采用近似挖掘的方法对大数据集进行挖掘，进一步归纳出应用系统中 实现近似挖掘的三个要点，即算法、挖掘框架和挖掘思路应用。 ( 2 ) 构建基于e j b 的数据分析原型系统d a a 。d a a 系统的功能涉及浏览、统 计和数据挖掘等方面，其核心功能是数据挖掘。设计工作主要由挖掘系统 体系结构设计、挖掘服务器端设计和客户端设计组成。体系结构设计包括 多层服务的划分和e j b 体系的选择。服务器端设计是工作重点，包括e j b 服务设计和w e b 服务设计。客户端设计包括界面设计、挖掘任务和挖掘 模型描述的设计。 ( 3 ) 对系统进行性能优化。结合了几个旨在提高系统性能的解决方案。包括粗 粒度访问方案、中问数据管理技术、挖掘的异步通信技术等内容。 ( 4 ) 在d a a 系统中进行挖掘实践。 1 3 2 创新之处 第3 页 幕于e j b 的数据分析助理系统的研究与醯计 ( 1 ) 通过研究解决大数据集挖掘的近似挖掘方法，归纳出应用系统中实现近似 挖掘的三个要点。 ( 2 ) d a a 原型系统的特点是： 基于e j b 体系，解决了分布应用的问题；在系统中结合近似挖掘技术，用于 解决对大数据集挖掘的问题。该系统整合了多种旨在提高系统整体性能的技术方 案，某些技术方案有创新。比如，在系统优化方面，本文提出了支持近似挖掘的 中间数据管理方案。总体来说，系统较好地适应了企业的软硬件环境，满足了数 据挖掘的实际需求。 1 4 论文的组织结构 本文共分六章，各章的内容简介如下： 第一章、绪论，主要对数据挖掘的应用现状和企业的具体应用需求进行分析， 第二章、 第三章、 第四章、 第五章j 第六耄、 考察了企业的软硬件环境，指出本文的主要工作和创新之处。 近似挖掘的研究，针对大数据集挖掘应用需求，对近似挖掘技术进行 研究和探讨。归纳出应用系统中实现近似挖掘的三个要点。 d a a 系统的设计，介绍d a a 系统的挖掘服务器端设计和客户端设计 两个方面。服务器端设计包括e j b 服务设计和w e b 服务设计；客户端 设计涉及界面设计、挖掘任务描述和挖掘模型描述等方面的内容。 d a a 系统的优化，论述了服务器端设计涉及的旨在提高服务器性能的 几个关键技术方案，包括粗粒度访问方案，中间数据管理技术，挖掘 异步通信技术等。 d a a 系统的应用，给出了系统在实际应用和近似挖掘实践的实例。 结束语，对本文作了工作总结，并指出未来研究方向和工作重点。 第4 页 基于e j b 的数据分析助理系统的研究与设计 第二章近似挖掘的研究 以小明大。见一叶落，而知步之将暮；睹瓶中之冰，而知天下之寒。 一淮南子说山训 2 1 引言 数据的迅速增长是数据挖掘发展的驱动因素，然而对大量数据的分析也是数 据挖掘研究的一大挑战。比如，简单的穷举法、经验分析法对于小数据集可以j 作得很好，而对t b 级的数据量就变成无能为力。目前有很多解决对策，其中一 个缓解由大数据量造成的困难的有效方法是进行数据归约( d a t ar e d u c t i o n ) ，以 便获得良好的挖掘效果。本章在数据归约方法基础上，研究了近似挖掘的方法， 归纳出应用系统中实现近似挖掘的三个要点。 22 大数据集的挖掘 2 21 大数据集 k d d 领域的许多研究人员和实验人员大多从事着包括机器学习、统计学、 人 ：智能、数据库等方向的研究。他们通常习惯于使用平面小数据集进行算法研 究，使用普通计算机几分钟就可以完成测试。对他们而言，一个有十万条记录和 几十个属性的数据集已经算大数据集( v e r y l a r g e d a t a s e t ) 了。然而，当今许多行 业的数据量是以g b 、t b 来计算的，比如企业数据仓库中数据量。显然采用原 有的方法对所有数据进行完整挖掘是不现实的。 许多文献显示，一个具有上百万条记录的数据集( 1 0 0 m b - - i g b 的范围) 就 可以看作是个大数据集了【4 】。然而，随着软硬件技术的逐步发展，这个数据范围 的上限还在不断扩展。本文的大数据集是指，如果真接由常规挖掘算法处理，由 于运行时间或空间限制，将无法顺利完成的数据量，对于一般的应用而言，不作 精确的定义。 2 2 2 可伸缩性问题 挖掘的可伸缩性( s c a l a b i l i t y ) 1 1 , 4 1 指挖掘算法是否能够有效处理大数据集的 阀题。 仅对挖掘算法进行时间复杂性分析是不够的。对于大数据集的挖掘，空间复 杂性的分析显得尤其重要。有许多挖掘算法是基于内存的，也就是说它们在挖掘 对蒙足够小，适合整个数据集装入内存时，可以工作得相当出色。然而，一旦数 据集尺寸超过内存容量，导致使用虚拟内存进行工作时，其性能将急剧下降，算 法本身的时间复杂度带来的影响已经远远不及进行内外存交换耗时的影响。这些 第5 页 基于e j b 的数据分析助理系统的研究与设计 算法显然不具有良好的可伸缩性。 2 ，2 ，3 解决方寨概览 鉴于大数据集的挖掘问题在企业数据分析中是不可避免的，挖掘系统只有具 备较强的可伸缩性，才能满足实际需求。主要可以通过三种途径来提高挖掘的可 伸缩性。即选取伸缩性良好的算法、进行数据划分( d a t a p a r t i t i o n i n g ) 和采用基 于关系数据集的挖掘法( r e l a t i o n a lr e p r e s e n t a t i o n s ) 4 1 。这些途径涉及的技术方法 如下表所示。 途径方案方法举例 选择高效算法( f a s t限制模型空间决策桩( d e c i s i o ns t u m p ) ，二阶段树( 2 1 e v e lt r e e ) a l g o r i t h m )增强启发搜索贪心算法，分治法 基于误差减少的剪枝 基于约束的搜索 动态搜索空间重构 算法的程序优化高效的数据结构 管帐员策略( b o o k k e e p i n gs t r a t e g i e s ) 针对硬件的优化 并行计算搜索空间并行 并行匹配 采用数据划分( d a t a属性选择相关性分析( u s er e l e v a n c ek n o w l e d g e ) p a r t i t i o n i n g )统计分析( u s es t a t i s t i c a li n d i c a t i o n s ) 子集学习( 1 l s es u b s e ts t u d i e s ) 实例选择随机采样( r a n d o ms a m p l i n g ) 重复压缩( d u p l i c a t ec o m p a c t i o n ) 分屡采样( s t r a t i f i e ds a m p l i n g ) 串行实例处理串行属性选择，串行实例学习 并行实例处理组合类描述，组合预测，组合多模型优选 关系数据挖掘数据表达关系化层次结构法，多表数据库，知识结构 (r e l a t i o n a l 归纳逻辑程序设计( i l p ) r e p r e s e n t a t i o n )与数据库系统整合s q l 语句嵌入挖掘，通过d b m s 挖掘 基于并行数据库，分布数据库挖掘 由于基于数据划分的方法可以作为相对独立的预处理来实现，通过直接处理 挖掘对象，获得的简化的中间数据集，可以提供给许多伸缩性差的算法使用。本 文着重研究基于数据划分的方法，归纳总结出近似挖掘技术方案，并把该方案整 合入挖掘系统的应用实现中，以便适应企业对大数据集挖掘的要求。 2 3 近似挖掘技术 本文所指的近似挖掘是在数据挖掘过程中，不直接使用待挖掘的原始数据 集，而是采用原始数据集的子集作为挖掘对象，以获得近似的挖掘效果的方法。 第6 页 基于e j b 的数据分析助理系统的研究与设计 包括三个方面的实现要点，即算法、挖掘框架和挖掘思路应用。 本文引入近似挖掘的目的是为了适应企业应用中对大数据集的挖掘要求。主 要体现在两个方面： 第一、 在保证模型性能的前提下，改善挖掘效率。基本思路是对大数据集 进行数据归约( d a t ar e d u c t i o n ) ，涉及属性选择和实例选择，强调 二者结合使用，有效降低挖掘对象的复杂度，减少了对挖掘时间和 资源需求。在很多情况下，比如对有相当数据规模的部门数据进行 挖掘，数据记录动辄上万条，如果直接采用常规挖掘算法处理，效 率低下：而采用近似挖掘技术，往往能获得满意效果。 第二、提高了挖掘算法的适用性。实际应用中，很多大数据集如果归约得 当，可以转化成小数据集，从而可以使用许多对处理基于内存的数 据集具有高性能，但本身伸缩性能不好的挖掘算法。 近似挖掘技术涉及属性选择和实例选择的各种算法，挖掘系统不仅需要实现 这些算法，还要整合必要的支持框架，以便提供用户对近似挖掘技术的支持。分 类挖掘是企业中应用最多的一种挖掘类型，决策树是常用的分类算法。下文从属 性选择和实例选择两方面探讨近似挖掘技术的算法实现问题，并结合分类挖掘 c 4 5 决策树算法进行实验。 2 3 1 近似挖掘的相关理论 1 、挖掘效果的评估 鉴于分类挖掘在企业数据分析中的广泛应用，以及分类挖掘有较为明确和成 熟的评估方法，本文选择分类挖掘与近似挖掘结合使用，以便对近似挖掘进行研 究。分类和预测方法一般按以下标准进行评估和比较f l j ： 预测的准确率：涉及模型正确地预测新的或以前未见过的数据的类标号 能力。 可伸缩性：涉及给定大量数据时，有效地构造模型的能力。 执行速度：涉及产生和使用模型的计算代价。 可解释性：涉及模型的可理解性和实用性。 鲁棒性：涉及给定数据含有噪声或空缺值时，模型正确的预测能力。 考虑到近似挖掘是通过改变挖掘对象数据集的方式来影响分类挖掘效果，我 们重点考察实施近似挖掘后，挖掘的执行速度( 用挖掘时间衡量) ，以及产生的 模型的预测准确率和模型的可解释性( 用模型的规模衡量) 这三个指标。 2 、三个指标 ( 1 ) 挖掘时间 第7 页 基于e j b 的数据分析助理系统的研究与设计 我们在考察时，主要从建模耗费的时间作为衡量。 未采用近似挖掘的挖掘时间l = 瓦。， 采用近似挖掘的挖掘时间t 。= t ，+ c ：+ 瓦。 其中，乃和正：分别是进行属性选择与进行实例选择花费的时闯；瓦。和 。分别是未采用与采用近似挖掘的挖掘算法执行建模的时间。如果采用近似挖 掘，建模时间是近似挖掘处理的时间和挖掘算法对处理后数据进行建模的时间的 总和。吃。小于瓦。，尤其对于较大数据集实施有效近似挖掘后，一般可以抵 消t 。和瓦：带来的额外时间花费，从而获得整体较小的时间花费，即l 瓦。 由于考察时采用同一种挖掘算法，比如c 4 5 算法，所以挖掘算法本身的时 间复杂度对建模时间的影响是一致的，这样作比较，就可以很容易观察到实施近 似挖掘对挖掘时间带来的影响。 ( 2 ) 预测准确率 通过对测试集进行模型应用，可以获得模型的准确率估计。通常我们选择准 确度作为考察的指标。考虑一个测试集样本空间，假定分类算法或分类器要识别 的某个类为正样本，样本数p o s ，它要识别的其它类为负样本，样本数n e g ，那 么真的正样本数t指分类器能正确识别的正样本数，假的正样本数指_pos fp o s 被分类器误分为正样本的负样本数，真的负样本数t _ _ n e g 指可被正确识别的负样 本数，假的负样本数f _ n e g 指被误分为负样本的正样本数，有p o s - - t _ p o s + f _ p o s ； n e g = t _ n e g + fn e g 。那么，准确率( a c c u r a c y ) 可以表达为： d c m 口掣：尘鬯塑。 p o s + n e g 对模型的准确率评估通常采用交叉验证法( c r o s sv a l i d a t i o n ) 1 2 o 交叉验证是 一种模型评估方法，通常用于分类模型准确率的评估。包括两分法( h o l d o u t ) 、 留一法( l e a v e o n e o u t ) 和k - 折交叉验证法( k - f o l d c r o s sv a l i d a t i o n ) 。k - 次迭代交叉 验证法1 2 , 5 是把数据集分为k 个予集，逐一选择k 个子集中的一个作为测试集， 其余的k 1 个子集作为训练集，这样进行k 次训练和测试，最后计算k 个数据 子集的错误数平均值作为结果错误数。k 一折交叉验证是对监督学习算法结果进行 评估的有效方法。数据集的划分可以采用等分法或随机划分。对于模型准确度测 试，采用的标准程序是进行1 0 个1 0 一折交叉验证。本文2 3 3 节和2 3 4 节的测试 实验就采用这种方法。 第8 页 基于e j b 的数据分析助理系统的研究与设计 为了从其它角度评估模型的预测性能，可以进一步考察其它三个相关指标【1 】 灵敏度( s e n s i t i v i t y ) ：s p 珊i t i v i t y ：l 旦竺 p o s 特效性( s p e c i f i c i t y ) ：印p c 咖妙：上墨堡 月昭 精度( p r e c i s i o n ) ：p r e c i s i o n ：譬l r p o s + ，一p o s ( 3 ) 模型的可解释性 模型的大小往往影响其可解释性。对于决策树，结点越多，树的规模越大， 模型也越复杂。未经归约的数据集含有大量无关或弱相关的属性，以及过多的实 例，直接导致大型决策树的生成。我们知道，决策树的树模型可以方便地转化成 规则形式，对于规模很大的树，产生的规则必然相当庞杂，可理解性也大大降低。 而且产生的庞大模型表面上预测准确率高，实际可能是由于对训练数据集的过度 拟合所致，所以通常会导致对新数据集的分类预测性能的下降【6 1 。 3 、数据归约 直接对以大数据集进行挖掘需要很长时间，也不一定能获得满意的结果。挖 掘结果可能是获得一个复杂的模型，尽管准确度由所提高，模型的可解释性却大 大降低。数据归约技术可以用来获得数据集的简化表示，它仍然接近于保留原数 据信息的完整性，规模却小得多。对经过归约预处理后的数据集进行挖掘，可以 产生相近的分析结果，效率则大大提高。数据归约技术是近似挖掘的实现基础， 近似挖掘对之进行了扩展。其中涉及的属性选择和实例选择方法将分别在下文进 行论述。 4 、相关性理论 相关性( r e l e v a n t ) 理论是近似挖掘技术的理论基础。近似挖掘要从原始的挖 掘对象数据集中获得与挖掘目标相关性最好的部分作为替代的挖掘对象数据集， 所以本质是进行相关分析。 从机器学习的角度，相关性指与目标概念的关联性。定义如下【_ 7 1 ：假设在实 例空间中，存在a 和b 两个样本，对应于目标概念c ，a 与b 有区别，即c ) e ( b ) ， 是因为它们的属性x 取不同的值，那么，就说属性和目标概念c 是相关的。 挖掘对象的复杂度，包含属性( a t t r i b u t e ) 和实例( i n s t a n c e s ) 两方面的复杂 度。属性复杂度包括属性的数目、属性的类型、属性取值的数目和范围、属性间 第9 页 基于e j b 的数据分析助理系统的研究与设计 的关联性等；实例复杂度包括实例数目、实例分布等。挖掘对象的数据质量影响 着挖掘的效果，如果其中存在无关的或冗余的信息，以及有噪声或不可信的数据， 将对挖掘训练产生干扰，获取的模型准确度不佳甚至失真。去除无关和弱相关的 部分，意味着一方面降低了挖掘对象的复杂度，另方面提高了挖掘对象的数据 质量。 尽管不同的挖掘算法对无关或冗余信息的敏感程度不同，根据相关性进行数 据选择，对获得较好的挖掘效果是很有帮助的。 2 3 2 决策树分类c 4 5 算法 决策树是一种类似二叉树或多叉树的树型结构。树中包括根结点在内的每个 非叶结点对应于训练样本集当中的一个非类别属性的测试，非叶结点的每个分枝 对应属性的一个测试结果，每个叶结点代表一个类或类分布。决策树是一种非常 赢观的分类模型表达形式。从决策树的根结点到叶结点的一条路径可以形成一条 分类规则。因此，决策树可以很方便地转化为简洁易懂的分类规则，或转化为 s q l 数据库查询语句。在性能方面，决策树分类法通常比其它分类法速度快， 比如神经网络对较小数据集也需较长训练时间。而且，般来说，决策树分类法 的准确度较高。 决策树分类由于自身优点，目前在分类问题的研究方面，决策树分类法占有 重要位置。本章的几个挖掘实验以及后续章节的挖掘实例均使用决策树挖掘算 法，采用著名的c 4 5 算法。 c 4 5 算法是q u i l a n 于1 9 9 3 年提出的一种典型的分类挖掘算法，具有分类准 确率高，分类速度快，可用于离散或连续型数据等优点，成为各种决策树算法的 基础，也是衡量分类算法性能的参照基准h j 。 1 、算法原理 c 4 5 采用基于信息增益率( i n f o 咖a t i o ng a i nr a t i o ) 的方法选择测试属性1 , 9 1 。设 有数据集t ，其类别集合为 c 1 ，c ：，c ，c k ，选择属性v 把t 划分为多个子集。 设v 有r 1 个不同的取值v ，v ：，v ，_ v 。，则t 被分为n 个子集五，正，五，工，其中z 中对应属性v 的取值都是ta 令p ( c j ) 为类别q 的发生概率，| t | 为数据集t 的 实例数，l l i 为v = v ，的实例数，i c ，l 为c ，类的实例数。 类别信息熵为i n f o ( t ) = p ( c ，) l 0 9 2 ( p ( c 伪 数据集t 的类别条件熵为c o n d _ i n f o ( t ) = 一p ( v ，) p ( c ，lv ，) l o g ：p ( c 1v ，) ， i 第1 0 页 基于e j b 的数据分析助理系统的研究与设计 选择属性v 对应的信息增益为g a i n ( v ) = i n f o ( t ) 一c o n di n f o ( t ) 。 选择属性v 的信息熵为s p l i t j n f o ( v ) = 一争型t t i 1 。g ：。t 1 1 衍；k ， 那么它对应的信息增益率为g a i n _ r a t i o ( v ) = g a i n ( v 1 s p l i t _ i n f o ( v ) 。 c 4 5 算法中产生决策树的伪码如程序2 3 1 t 1 0 1 ，其中t 为当前训练样本集， ta t t r i b u t e l i s t 为候选属性集。 程序2 3 1c 4 5 算法产生决策树 c 4 5 b u i l d t r e e ( 。i ，i t t r i b u t e l i s t ) - 创建根结点n ； i fv r ，t 类c ，t h e n 返回n 为叶结点，标记为类c ； i ft a t t d b u t e l i s t = mo r t 中所剩样本数少于给定阀值，t h e n 返回n 为叶结点， 标记为t 中出现最多的类； f o re a c h ta t t r i a b u t e l i s t 中的属性，计算信息增益率i n f og a i nr a t i o ； s e t n 的测试属性t e s t _ a t t r i b u t e = l a t t r i b u t e l i s t 中具有最高信息增益的属性： i f 测试属性是连续型，t h e n 找到该属性的分割阀值； f o re a c h 由结点n 长出的新叶结点f i f 该叶结点对应的样本子集t = 毋，t h e n 分裂该叶结点生成一个新结点， 其标记为t 中出现最多的类； e l s e 在该结点上执行c 4 5 b u i l d t r e e ( t ，ta t t r i b u t e l i s t ) ，对它继续进 行分裂； ) 计算每个结点的分类错误，进行树势枝。 最后一步进行决策树剪枝，可以避免过度拟合，获得规模较小的树有助于模 型的理解。需要说明的是，c 4 5 有不同的几种剪枝策略可以选用，剪枝策略对 执行时间、准确率和所得决策树的规模有影响。 2 、时间复杂度分析 假设训练集包含n 个实例以及m 个属性，对于结点的树型分布，可以推断树 的高度一般是l o g ：玎的一阶线性函数关系，从上文执行伪码分析可知，n 个叶结 点的树的增长率，也就是建树的时间复杂度为l o g ：n 的函数关系，我们假定一般 情况下决策树的形状与完全多叉树的形状较为接近，而非变态的单边树。在建树 过程中，每个高度层次，测试都需要考虑所有n 个实例，因此复杂度为o ( n l o g ：”) ； 而对于每个结点，各个属性都要参加测试，以便选择最佳分割属性，所以建树总 的时间复杂度为o ( m n l 0 9 2h ) 。 至于剪枝，采用子树替代策略( s u b t r e er e p l a c e m e n t ) ，时间复杂度为o ( n ) 。 第1 l 页 一 墨三! 里塑塑塑坌塑塑翌堡堕塑翌壅兰堕生 采用子树提升策略( s u b t r e el i f t i n g ) ，由于要考虑到实例在每个结点处的重新分类 问题，其时间复杂度将是0 ( m ( 1 0 9 ：n ) 2 ) 吼本文以下使用c 4 5 的实验均采用子树 替代策略，完成决策树建模的时间复杂度为o ( m n l o g ，n ) + 0 ( h ) 。采用近似挖掘 技术进行属性选择和实例选择后，减少了m 和n 的值，从而有效降低建模时问 复杂度。 2 3 3 属性选择 属性选择( a t t r i b u t es e l e c t i o n ) 是根据某些指标选择一个优化属性子集的过 程。一个优化的子集可以是属性数目最小的子集，也可以是具有最好的预测准确 率的子集。 评估指标的选取与属性选择的目的有关，可以是分类精度不会再减少，或者 是由选择的属性产生的类分布尽可能地接近贩始数据集的类分布。属性选择可以 看成是在属性子集状态空间的搜索过程。属性选择方法由属性评估方法 ( e v a l u a t i o l l ) 和搜索方法( s e a r c hm e t h o d ) 两部分组成。 本文讨论的属性的类型主要有连续型和离散型两种。当某一属性的值域为连 续域时，该属性为连续属性，或数值属性( n u m e r i c a la t t r i b u t e ) ，否则为离散属 性，或类属属性( c a t e g o r i c a l a t t r i b u t e ) 。离散属性包括二值型的特例布尔型，以 及多值型；连续属性包括各种类型的实数。 1 、属性选择的工作方式 根据属性选择与实际的挖掘算法之间的配合关系，或者说属性选择的工作方 式，可以分为嵌入型( e m b e d d e d ) 、过滤型( f i l t e r ) 和封装型( w r a p p e r ) 三种 形式1 7 , 1 1 。 嵌入型的属性选择完全融入具体的挖掘算法，是挖掘算法的组成部分】。比 如分类决策树算法i d 3 和c 4 5 ，在执行迭代划分测试的过程中，都根据内部的 评估函数，选择最佳的属性作为每一阶段分枝的评判属性。其它的如决策列表算 法，也有嵌入型的属性选择功能。 过滤型的属性选择是独立于具体挖掘算法进行的属性选择。简单的过滤型算 法测试每个属性与目标函数的相关性，然后选择相关性最强的前砸几个属性，接 下来具体算法就根据选中的这几个属性进行挖掘。r e l i e f 算法【1 2 】和f o c u s 算 法i j 刊都属于此类。 封装型的属性选择同样在具体挖掘算法之外执行属性选择，不过它调用具体 挖掘算法获得挖掘准确率，并以此作为属性选择的评估标准【l “。该类型的属性 选择往往可以获得更好的准确率估计，然而由于对每个属性选择测试都要调用挖 第1 2 页 基于e j b 的数据分析助理系统的研究与设计 掘算法，造成过高的计算代价。 从整个挖掘过程看，过滤型的属性选择可以当作预处理步骤，简单易用，而 且产生的中间结果可以为后续的各种具体挖掘算法利用。 2 、评估方法