（应用数学专业论文）决策树方法在远程教育辅助教学中的应用研究.pdf

决策树方法在远程教育辅助教学中的应用研究 姓名：孙卫强 专业：应用数学 指导老师：姜正禄教授姚正安教授 摘要 数据挖掘( d a t am i n i n g ) 是目前国内外数据库与信息决策领域最前沿的研究 方向之一，它能够找到大量数据背后所隐藏的规律性，从而为决策者提供相应的 支持信息。数据挖掘技术虽然已经被广泛地应用在许多领域，但是在教育领域的 应用与研究尚处于初始阶段，因此对该技术进行深入的分析与研究，不仅有着十 分重要的理论意义，而且有着非常重要的应用价值。 现阶段各网络学院对学生信息等数据的处理一般停留在简单的数据库管理 和查询阶段，不能发挥其应有的作用。根据这些数据具有分类的预知性和离散性 的特点，可以灵活运用决策树i d 3 算法，生成决策分类树。但是由于i d 3 算法 有多值偏向属性的不足，如何对属性进行筛选以提高分类精确度，就成了问题的 关键。为此，本文运用了一种基于灰色关联度的修正因子属性选择方法。该方法 首先计算各特征属性与类别属性之间的灰色关联度，并将它们排序；其次对信息 增益大但取值较多的属性通过灰色关联度来判断是否最优，从而确定是否降低它 的信息增益：最后对信息增益大取值多但灰色关联度低的属性，在计算其信息增 益时通过灰色关联度的正弦值来代替用户兴趣度值，其它属性计算信息增益时用 户兴趣度设为o 。仿真结果表明效果良好。 用上述方法对影响学生成绩相关属性集进行属性选择，把基于决策树理论的 数据挖掘改进算法引入到学生成绩分析中，找出影响学生成绩的潜在因素，从而 为教学部门提供决策支持信息，促使更好地丌展教学工作，提高教学质量。此方 法与传统的决策树数据分类方法相比，它可有效地选择出对于分类最重要的属 性，提高规则的预测精度，并增强决策树的抗干扰能力。 关键词：数据挖掘，决策树，多值偏向，修正因子，学生成绩 t h e a p p l i e dr e s e a r c ho fd e c i s i o n - t r e em e t h o do f t h ea s s i s t e dt e a c h i n gi nd i s t a n c ee d u c a t i o n m a j o r ：a p p l i e dm a t h e m a t i c s n a m e ：s u nw e i q h n g s u p e r v i s o r ：j i a n gz h e n g l u , y a oz h e n g a n a b s t r a c t d a t am i n i n gi so n eo ft h ef r o n t i e r so fr e s e a r c hi nt h ef i e l d so fd a t a b a s ea n dd s s ， a n di tc a nf i n dt h eo r d e r l i n e s st h a th i d eb e h i n dt h ev o l u m ed a t at oo f f e rc o r r e s p o n d i n g i n f o r m a t i o nf o rm a k i n gm a n a g ed e c i s i o n i th a sb e e nw i d e l yu s e di nm a n yf i e l d s ，b u ti t i ss t i l li nt h ei n i t i a ls t a g ei nt h ef i e l do fe d u c a t i o n s o ，i th a sv e r yi m p o r t a n tm e a n i n g st o u s ed a t am i n i n gi ne d u c a t i o n , b o t hi ns c i e n c ea n dm a r k e t n o w a d a y s ，t h e s t u d e n t si n f o r m a t i o n ，r e s u l t sa n do t h e rd a t aw h i c hi s o n l y g e n e r a l l yp r o c e s s e dw i t hs i m p l em a n a g e m e n ta n dq u e r yi nt h ei n s t i t u t eo fd i s t a n c e e d u c a t i o n , c a nn o tp l a yi t sd u er o l e b a s e do nc h a r a c t e r so ft h es e t t i n gu po fs p e c i a l t i e s i n f o r m a t i o na n dt a k i n gp r e t r e a t m e n to ni t ，t h ep a p e r 锄b ec o n s i d e r i n go fu s i n g1 1 ) 3 a l g o r i t h mn e a t l yf o rb u i l d i n gd e c i s i o nt r e e h o w e v e r , c o n s i d e r i n go ft h em u l t i v a l u e b i o so fi d 3a l g o r i t h m ，i tb e c o m e sak e yt ot h ep r o b l e mo fh o wt oi m p r o v et h e p r e c i s i o no fc l a s s i f i c a t i o n i no r d e rt oo v e r c o m et h ep r o b l e m , t h i sp a p e rp r e s e n t sa m e t h o do fm o d i f i e dc o e f f i e i e n ta t t r i b u t e ss e l e c t i o nb a s e do nd a t aa t t r i b u t ei m p o r t a n c e r a n k i n g f i r s t l y ，c a l c u l a t i n gg r a yr e l a t i o n a lg r a d eb e t w e e nc h a r a c t e r i s t i c s a t t r i b u t e a n dc l a s s i ca t t r i b u t ea n dr a n k i n gt h e m s e c o n d l y , u s i n gg r a yr e l a t i o n a lg r a d et oj u d g e w h e t h e rr e d u c et h ei n f o r m a t i o ng a i no fa t t r i b u t ew h i c hh a sm a n yv a l u e sa n dg r e a t i n f o r m a t i o ng a i n f i n a l l y , f o rt h o s eg r a yr e l a t i o n a lg r a d el o w e rw h i l ei n f o r m a t i o ng a i n h i g h e r ，i nt h ec a l c u l a t i o no fi t si n f o r m a t i o ng a i nb yt h es i n eo fg r a yr e l a t i o n a lg r a d e i n s t e a do ft h eu s e ri n t e r e s tr a t e ，w h i l eo t h e r sb y0 t h ee f f i c i e n c yo ft h i sa p p r o a c hi s d e m o n s t r a t e db ys i m u l a t i o ne x a m p l e s t h ea l g o r i t h mi sa p p l i e di nt h ea n a l y s i s i n go nt h es e to fa t t r i b u t e sr e l a t e dt o s t u d e n t s a c h i e v e m e n td a t am i n i n gs y s t e ma n df i n d i n go u tt h eu n d e r l y i n gf a c t o r s a f f e c t i n gs t u d e n ta c h i e v e m e n t ，s oa st op m v i d ed e c i s i o ns u p p o r ti n f o r m a t i o nf o r a c a d e m i cd e p a r t m e n t sa n di m p r o v et e a c h i n gq u a l i t y c o m p a r e dw i t ht h et r a d i t i o n a l d a t ac l a s s i f i c a t i o nm e t h o d su s e di nd e c i s i o nt r e e ，t h ep r o p o s e dm e t h o dc a nf i n do u t t h em o s ti m p o r t a n ta t t r i b u t ee f f i c i e n t l y , r a i s e st h ea n t i q a m m i n gc a p a c i t yo fd e c i s i o n t r e ea n di m p r o v e st h ep r e d i c t i o np r e c i s i o no fr u l e sp r o d u c e d k e y w o r d s ：d a t am i n i n g ，d e c i s i o nt r e e ，m u l t i v a l u eb i o s ，m o d i f i e dc o e f f i c i e n t ，s t u d e n t s a c h i e v e m e m l i l 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：矛小卫强 日期：2 d o 年乡月弼日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规 定，即：学校有权保留学位论文并向国家主管部门或其指定 机构送交论文的电子版和纸质版，有权将学位论文用于非赢 利目的的少量复制并允许论文进入学校图书馆、院系资料室 被查阅，有权将学位论文的内容编入有关数据库进行检索， 可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：荆卫多虽 导师签名：m 日期：7 0 l o 年易月日日期：抛年6 月z 日 第一章绪论 1 1 课题提出背景及意义 2 0 世纪末和本世纪初，高等教育遇到了前所未有的挑战。这种挑战主要来 自于经济社会的发展对各方面人才的需求，从而转化为对高等教育的新的要求。 我国当前高等教育正在进行改革，其目的是要实现教育的大众化，以便为我国现 代化事业的发展培养出高素质的建设者和接班人。那么，如何才能真正实现高等 教育从精英教育向大众化教育的转变就成了摆在我们面前亟待解决的问题。值得 关注的是，实现高等教育的大众化，不仅是简单的量的扩张，同时要注重质的提 高，大众化的教育要切实能够为社会培养出具有创新精神和意识的人才。单纯依 靠传统高校在规模上的扩张是难以真正实现教育大众化的艰巨任务的，因为我国 目前综合经济实力还不够强大。随着现代信息技术的发展，全球数字技术和电子 通信的进步，以及计算机多媒体和国际互联网的诞生，一种新型的教育形式观 代远程教育应运而生了。 现代远程教育是以计算机网络技术为基础，以人工智能、决策科学以及系统 科学为指导，以多媒体技术为主要手段的一种新型教育模式。在我国教育资源短 缺经济实力不够强大的条件下，现代远程教育是构筑知识经济时代人们终身学习 体系的主要手段，是适合我国办好大教育的战略措施。因此，实施现代远程教育 工程不仅是对传统教学形式和教育模式的重大创新和突破，而且它能够使稀缺的 高等教育资源最大限度地服务于人民群众，满足大众对高等教育的迫切需求。我 国远程教育技术的发展，经历了三个阶段： 第一阶段是函授教育； 第二阶段是广播、电视等手段被应用于教育； 第三阶段是通过计算机网络等多媒体手段进行教学和学习。 2 0 1 0 年1 月8r ，中国远程教育杂志社主办、对外经济贸易大学远程教 育学院协办的“贸大远程”杯中国现代远程教育十年( 1 9 9 9 2 0 0 9 ) 十大最具影响 力事件评选结果揭晓，这次评选结果很好地描述了远程教育在中国近年来的发展 历程及其重要性。发展远程教育已经成为发展中国家教育事业的一项战略抉择， 1 其目标和任务是“到2 0 1 0 年，基本形成多规格、多层次、多形式、多功能，具 有中国特色的终身教育体系”【1 】o 随着高等教育大众化阶段的到来，我国远程高等教育凸显出一些不足之处： 1 、招生规模扩大，这就导致师资力量、教育资源以及经费等的不足。制度 的不完善导致对学生绩效考评标准模糊，难以把握课程质量关。 2 、远程教育的生源主要是高考落榜学生以及其他接受学历教育的社会人员， 学生基础较差，生源结构复杂。再加上普通高校扩招，使远程教育的生源质量下 降，无形中也在降低远程教育的质量。 3 、面对国际竞争，我国远程教育必须提升自身的教育质量才能赢得学生， 赢得市场。 因此，对于我国远程高等教育来说，教育质量问题就成为获取社会公信力， 获取自身生存和发展的关键。 现阶段各远程教育试点单位对学生信息等数据的处理一般还停留在简单的 数据库管理和查询阶段，不能进一步发挥其作用。以学生成绩为例，教育者对学 生成绩的分析处理一般仅仅是将学生成绩简单的分为优、良、一般、差等，然后 统计各级别的人数，但是对于学生取得这些成绩的原因往往无法了解，更不能制 定相应的措施对学生因材施教。如何开发利用这些数据，理性地分析教学中各方 面的成效得失是广大教师共同关心的问题。 数据挖掘技术可以从大量的、有噪声的、随机的实际应用数据中，提取出隐 含在其中人们事先不知道的，但又是潜在有用的知识和信息。通过这种技术把获 取的知识和信息提供给决策支持系统。这种技术已被广泛地应用在各领域，包括 科学探索、生产控制、工程设计、市场分析和商务管理等郾，4 l ，随着信息技术的 发展，数据挖掘在网络教学中的应用研究也逐渐深入。如果能够利用数据挖掘技 术对收集到的与学生学习相关的历史数据进行分析，找到影响学生学习成绩的因 素，从而可以为教师深入理解学生的实际学习情况，制定相关的教学目标提供有 力的决策支持，必然有益于提高远程教育教学质量【5 ，6 。 本文的工作就是基于这样一个背景下展开的。以中山大学网络学院学生的成 绩为应用背景，利用数据挖掘技术分类算法对影响学生成绩的因素进行深入的分 析，以得出有用的结论，用来更好的指导教学，提高远程教育教学质量。 2 1 2 国内外研究现状 1 2 1 国内外数据挖掘技术的发展现状 从整体上看，国外在数据挖掘领域中的研究内容十分广泛，并且已经取得了 明显的成果。国外有许多学术组织、科研机构和公司从事数据挖掘工具的研制和 开发，而且已经出现了许多数据挖掘和知识发现系统。国际上比较有影响的数据 挖掘系统有：a n g o s s 公司的k n o w l e d g es e e k e r 、s a s 公司的e n t e r p r i s em i n e r 和i b m 公司的i n t e l l i g e n tm i n e r 等。除此之外，还有许多其它的数据挖掘系统或 原型系统，如：k l o s g e n 等人开发的e x p l o r a 系统、a n a n d 等人开发的s p o t l i g h t 系统和加拿大s i m o nf r a s e r 大学韩家炜教授领导的小组开发的d b m i n e r 系统等 竺1 8 l 可 。 与国外相比，国内对数据挖掘与知识发现的研究与应用要晚一些，而且还处 于刚起步的阶段。目前大多数研究项目是由政府资助进行的，而且从事数据挖掘 研究的人员主要集中在大学，也有部分在研究所或公司，如中科院计算技术研究 所和中国人民大学统计系数据挖掘中心等。其中，中科院计算所智能处理开放实 验室的史忠植教授等人设计了一个数据挖掘工具m s m i n e r ，使用决策树算法为 广东地税提供纳税人异常情况检测；复旦德门公司开发的天眼数据挖掘工具 d r a i n e r 集成了多种数据挖掘算法，取得了较好的挖掘效果；青岛海尔青大软件 有限公司开发的数据仓库软件h d c ( h i g h w a yd e c i s i o nc e n t e r ) ，目前已广泛应 用于政府部门、服务业、金融业、制造等行业。可以说，目前国内有关电信、证 券、金融等行业中数据仓库和数据挖掘方面的研究与讨论日渐增多，但是投入实 际运用的系统与案例不多【9 ，1 0 ，1 。 总之，数据挖掘的研究重点逐渐从发现方法转向系统应用，其规模已由原来 的专题讨论会发展到国际学术大会，并且开始注重多种发现策略和技术的集成， 以及多种学科之间的相互渗透。 1 2 2 数据挖掘技术在国内外教育领域的应用现状 在教育领域，数据挖掘也开始发挥积极的作用。 3 在国外；数据挖掘技术在教育领域的应用比较多，许多国家已经利用数据挖 掘技术开发出比较成熟的教学系统，如加拿大大学开发的v i r t u a l - u 、l o t u s 公司 的l e a r n i n gs p a c e 和英属哥伦比亚大学计算机科学系开发的w e b c t ( w e bc o u r s e t o o l s ) 等，而且有些系统已经开发出了针对教学的基本评价功能，如v i r t u a l - u 教 学平台则包含了作业、考试的定性定量评价与管理，是一个比较全面的教学评价 软件。另外，国外还有些公司如：c i s c o 已经开发出了一种先进的成绩评价系统， 对其学员在学习、培训过程中的成绩进行评价，公司可以利用这些评价数据对计 划和课程作出不断的改进【1 2 ，1 3 1 。 如前所述，在国内数据挖掘技术的应用还处于起步阶段，成功应用的案例比 较少，在教育领域更是少之甚少。由于国外的数据挖掘产品是按照他们的教育体 制和教学模式来设计的，而国内外教育体制显然存在许多不同之处，所以我们不 能直接利用国外产品。因此，开发适合我国特色的数据挖掘产品显得尤为重要， 对数据挖掘技术研究人员以及开发商来说，我国将是一个有巨大潜力的市场【1 4 】。 目前，国内的一些大学也正在努力开发自己的产品。比如浙江大学通过使用关联 规则技术对高校人事信息库进行挖掘，试图找到影响学科发展的因素以及影响学 科发展的各个要素之间的关系1 1 5 】。前人大多是尝试运用关联规则算法，分析教 师学历、职称、年龄等与教学效果之间的关系或者研究各种课程之间的相互关系， 以此来研究开设课程的先后关系掣1 6 ，1 7 , 1 8 , 1 9 l 。 1 3 本文的主要工作和结构安排 网络教育学院在教学和管理工作中积累了大量的数据，目前这些数据还未能 被有效利用。鉴于社会对高等学校发展的需求和目前高校数据管理现状，利用这 些数据理性地分析学校各方面工作的成效以及学生培养过程中的得失变得十分 重要【2 叫。 本文针对现阶段网络学院实际教学中亟待解决的问题( 如何有效提高教学质 量) 进行了深入的探讨。通过调查问卷和从网络平台搜集整理数据，基于数据挖 掘决策树方法对“学生成绩”这一数据资源以及影响学生成绩相关因素进行挖掘 获得辅助决策知识，以进一步掌握学生的学习情况，并用于指导教学和学生的学 习。 4 论文的主要工作和结构安排： 第一章绪论。介绍本文的研究背景和意义，综述了数据挖掘的在国内外的应 用现状，总结整个研究工作的内容以及论文的组织结构。 第二章数据挖掘与分类技术。首先对数据挖掘的概念、数据挖掘的过程、数 据挖掘的功能等进行了简明扼要的介绍。然后介绍了分类的定义、分类过程、数 据预处理和评价标准等。最后重点分析了i d 3 算法并提出改进算法s m c d t ，通 过仿真实验，阐述s m c d t 方法的有效性和可用性。 第三章s m c d t 算法在学生成绩分析中的应用。利用s m c d t 算法对各属性 建立决策树模型，然后利用测试数据评估了算法的有效性，从中提取出分类规则， 并针对网络学院教学中的完善和提高提出了几点建议。 第四章论文总结与展望。总结本文的研究工作，对研究中存在的问题和有待 进一步解决的问题进行了分析，并对数据挖掘技术在影响学生成绩分析中的研究 前景进行了分析和展望。 5 第二章数据挖掘与分类技术 2 1 数据挖掘概述 数据收集和数据存储技术的快速进步使得各科研组织机构积累了海量数据。 所以如何能有效的利用这些信息进行更深入、更高层次的分析，逐渐成为人们日 益关注的问题。数据挖掘技术就是在这种瓶颈下产生的，它克服了当前数据分析 技术在处理这些新型数据集提出的挑战中的种种局限性，有效地得出合理的结 果，从而数据挖掘引起了信息产业界的极大关注，并取得了蓬勃发展。 数据挖掘思想来源：( 1 ) 来自统计学的估计、抽样和假设检验。( 2 ) 模式识 别、人工智能和机器学习的搜索算法、学习理论和建模技术。( 3 ) 进化计算、最 优化、信息论、可视化、信号处理和信息检索。数据挖掘还需要其他领域支撑作 用。特别地，需要数据库系统提供有效的查询、存储和索引处理支持【2 1 l 。 1 9 8 9 年在加拿大召开了第一届知识发现和数据挖掘( k d d ) 国际学术会议 后，数据挖掘就成为国外的热门研究方向。1 9 9 3 年，e i e e e 的k n o w l e d g ea n dd a t a e n g i n e e r i n g 会刊出版了k d d 技术专刊。数据挖掘技术正进行着蓬勃的发展。到 目前为止，k d d 国际研讨会已经召开了十多次，研究重点逐渐从发现方法转向 系统应用，规模也由原来的专题讨论会发展到国际学术大会，研究注重多种发现 策略和技术的集成，以及多学科之间的相互渗透。1 9 9 9 年亚太地区在北京召开 的第三届p a k d d 收到1 5 8 篇论文。另外，在i n t e m e t 上还有不少k d d 电子出 版物，规模也逐渐扩大，其中以半月刊k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威。 与国外相比，国内对数据挖掘的研究时间稍晚，研究领域并不是很广泛，主要集 中于一些算法的理论研究且没有形成整体力量。 随着科技的日新月异、经济的飞速发展，新的问题会不断出现，数据的积累 量会不断加大。为了更好地适应社会的发展，缩短与世界强国之间的差距，增强 我国的国力，我们要加大对科技的投入，齐心协力应对面临的挑战，加快推动我 国在数据挖掘方面的发展速度。 6 2 1 1 数据挖掘概念 数据挖掘是在大型数据存储库中，自动地发现有用信息的过程。数据挖掘 ( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用 数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识 的过程1 2 2 1 。 数据挖掘环境如图2 1 所示。 、 数据挖可视化 - _ 掘工具 - - , 工具 数据库 图2 一l 数据挖掘环境 数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 是于1 9 8 9 年 在美国召开的第1 1 届国际人工智能联合会议的专题讨论会上提出的。关于数据 挖掘与k d d 的关系有许多不同的观点。第一种观点认为k d d 是数据挖掘的一 个特例，这是早期比较流行的观点，这种描述主要强调数据挖掘在数据形式上的 多样性。第二种观点认为数据挖掘是k d d 过程的一个步骤，它是k d d 不可缺 少的一部分，而k d d 是将未加工的数据转换为有用信息的过程。目前为止，人 们对数据挖掘算法的研究基本属于这样的范畴。事实上，在许多的文献和场合中， 这两个术语都不加区分地被人们使用。 2 1 2 数据挖掘过程 如图2 2 所示，数据挖掘是一个多阶段数据处理过程，它主要包括以下几个 步骤： 第一步：确定挖掘对象。 首先要认清数据挖掘的目的，清晰地定义出所要挖掘的问题是数据挖掘过 程中一个重要的步骤。挖掘的最后结果虽然是不可预测的，但是要探索的问题应 该是可以预见的，如果为了数据挖掘而数据挖掘则带有一定的盲目性，一般是不 7 会成功的。 图2 2 数据挖掘过程和主要步骤 第二步：数据准备。该过程又可以分为下面三步： ( 1 ) 数据的选择 对各数据库进行搜索，找出所有与挖掘对象有关的内部或者外部的数据信 息，并从中选择出适用于数据挖掘的数据。 ( 2 ) 数据的预处理 数据库极易受噪声、丢失数据和不一致数据的侵扰，并且多半来自多个异构 数据源。低质量的数据将导致低质量的挖掘结果。因此对多个数据库的合并，要 去除明显错误的不相关、冗余、噪声数据，收集噪声信息以决定在后续步骤采取 何种解决噪声问题的方法。 ( 3 ) 数据的转换 就是根据挖掘算法，将数据转换成一个分析模型。建立一个真正适合挖掘算 法的分析模型是数据挖掘成功的关键。 8 第三步：数据挖掘。 通过挖掘算法的应用，得到分类规则或关联规则等其他模式。 第四步：结果分析。 解释并评估结果，确定哪些是有用的、有效的模式。评估的方法有很多种。 有些模式可以直接用数据来检验其准确性，有些则可以根据用户多年的经验。这 个步骤还包括把所得到的结果用易于理解的方式呈现给用户，比如可视化技术。 第五步：知识的同化。 主要是巩固所得到的知识并进一步加以利用，如检查与其他知识是否冲突， 将知识合并到另一系统，以进一步加工利用等。 2 1 3 数据挖掘系统的分类 数据挖掘是一门交叉学科，受到多个学科的影响，包括统计学、机器学习、 数据库系统、可视化和信息科学等。此外数据挖掘方法还使用了大量其他学科的 技术，如神经网络、粗糙集理论、模糊逻辑、知识表示、归纳逻辑程序设计或高 性能计算等等1 2 3 , 2 5 】。这么多学科混合在一起，数据挖掘研究就产生了大量的、各 种不同类型数据挖掘系统。根据不同的标准，数据挖掘系统可以分类如下例： ( 1 ) 基于所得到的知识分类：演变( e v o l u t i o n ) 分析、偏差( d e v i a t i o n ) 分析、 孤立点分析、聚类和相似性分析等等。 ( 2 ) 基于数据库类型分类：基于网络信息的挖掘和文本挖掘等。 ( 3 ) 基于采用的技术分类：人工神经网络、遗传算法、决策树、模糊逻辑、 可视化和最近邻技术等等。 2 1 4 数据挖掘功能 数据挖掘是一个交叉学科领域，各个学科新的研究成果促使数据挖掘技术日 趋成熟。数据挖掘功能是用于确定数据挖掘任务中要找的模式类型。数据挖掘的 方法一般分为预测型和描述型【2 6 1 。预测性数据挖掘的任务是在当前数据上进行 推断，并进行预测；描述性数据挖掘主要用于刻画数据库中数据的一般特性。 数据挖掘的功能主要有以下六类： 9 ( 1 ) 关联分析【2 7 】 关联分析的目的就是找出数据库中隐藏的关联网，发现项集之间有趣的关联 或相关联系。从广义上讲，关联分析是数据挖掘的本质。随着数据库中数据的积 累，许多业界人士开始对于他们数据库中挖掘关联规则越来越感兴趣。关联分析 被广泛的应用于购物篮或事务数据分析等。 ( 2 ) 概念类描述【2 8 】 一般数据库中往往存放着大量的细节数据。但是，对于这些细节数据，用户 通常希望以简洁的形式描述。这种数据描述可以提供一类数据的概貌，或将它与 其他类相区别。此外，用户希望灵活地以从不同的角度和不同的粒度描述数据集。 这种描述性数据挖掘称为概念类描述。这种描述可以通过数据特征化、数据区 分等方法得到。概念类描述本质上就是对某类对象的内涵特征进行概括。 ( 3 ) 分类和预测【2 9 , 3 0 】 分类和预测可以用于提取描述重要数据类的模型或预测数据未来的趋势，是 两种不同的数据分析形式。分类就是找出能够描述并区分数据类或概念的模型， 以便可以使用模型预测数据对象的类标号。特别的，当被预测的值是数值数据时， 通常称之为预测。分类和预测的应用是十分广泛的。例如，可以通过建立分类模 型，对工厂的机器运转情况进行分类，用来预测机器故障的发生情况。 ( 4 ) 孤立点分析【3 1 ，3 2 l 数据库中可能包含一些与数据的一般行为或模式不一致的数据对象，这些数 据对象被称为孤立点，通常它们作为噪音来处理。孤立点分析又称孤立点挖掘、 例外挖掘、异常检测、挖掘极小类、小事件检测、偏差检测。许多数据挖掘算法 试图使孤立点的影响最小化，或者排除它们。但孤立点本身可能是非常重要的信 息。从知识发现的角度看，在某些应用里，那些很少发生的事件往往比经常发生 的事件更有趣、也更有研究价值。孤立点分析对于欺诈探测、医疗分析及许多其 他的任务是非常有用的。比如可以通过购物地点、类型或者购物频率来检测信用 卡欺骗性使用等。 ( 5 ) 聚类分析 聚类分析也称群分析、点群分析，是研究分类的一种多元统计方法。常见的 聚类方法有：直接聚类法、最短距离聚类法和最远距离聚类法等。聚类形成的每 个类可以看作一个对象类，由它可以导出规则。聚类是典型的无导师学习算法。 ( 6 ) 演变分析p 3 州 数据演变分析包括时间序列分析、序列或周期模式匹配和基于类似性的数据 分析，它主要描述行为随时间变化的对象的规律或趋势，并对其建模。例如，可 以从股票交易数据中挖掘出整个股票市场和特定公司的股票演变规律，帮助预测 股票市场价格的未来走向，帮助股票投资者做出决策。 在数据挖掘中，不同的实际问题，必须结合特定的背景知识，采用不同的数 据挖掘方法，没有哪种方法可以解决所有的问题，有的问题甚至需要结合多种方 法共同进行解决。一般地，在实际应用中，具体使用哪些方法主要取决于问题的 类型以及数据的类型和规模。 2 2 分类的基本知识 2 2 1 分类的定义及目的 分类是数据挖掘中最重要的技术之一。目前实现分类的方法有机器学习方 法、统计方法和人工智能方法等，常用的技术有：决策树分类、神经网络分类、 贝叶斯分类和支持向量机分类等。分类就是根据数据集的特点找出类别的概念描 述，这个概念描述代表了这类数据的整体信息，也就是该类的内涵描述【2 9 】。 分类的定义：通过学习来确定一个目标函数( t a r g e tf u n c t i o n ) f ，把每个 特征属性集x 映射到一个预先给定的类标号( 类别属性) y 。一般地，目标函数 也常被称为分类模型( c l a s s i f i c a t i o nm o d e l ) 。 分类也可以这样描述：给定一个数据集合t ( 称为训练数据库或训练集) ，t 中的每一个元素由若干个属性刻画。在每个元素的所有属性中有且仅有一个属性 被作为类别属性，其他各属性被称为非类别属性或者特征属性。元素属性集合用 矢量x = ( 石。，x ：，以) 表示，其中置( 1 sfs 咒) 对应表示各即特征属性，它们可 以具有不同的值域，即对于任一属性置= ( 黾，劫，) ，m i 随属性的不同而不 同。当一属性的值域为离散值时，该属性称为离散属性( d i s c r e t e a t t r i b u t e ) ，否则 】1 称为连续属性( n u m e r i c a la t t r i b u t e ) ；用c 表示类别属性，且假设数据集有k 个不 同的类别，可以令c 一( c 1 ，c 2 ，气) 。这样，丁就隐含地确定了一个从特征属性z 到类别属性c 的映射函数f ：f ( x ) _ c 。 分类的目的：通过分析待分类数据集，利用训练集数据所表现出来的特性， 反复学习，从而用一种准确的描述或者模型来刻画每一个类。然后使用类的描述 对未知类别的测试数据集进行分类。虽然这些测试数据集的类标签是未知的，我 们仍能够预测这些新数据所属的类。 2 2 2 分类的过程 分类( 构造分类器) 是在被告知每个训练元组属于哪个类的情况下进行的， 即每个训练元组的类标号是确定的。分类器的构造过程通常分为以下四个步骤： ( 1 ) 将类标号已知的数据集分为测试集和训练集两部分。 ( 2 ) 利用已知数据的特征，构造合适的分类算法对训练集中的数据进行学 习、修正，得到一个符合要求的分类模型。分类模型常用数学公式、决策树或分 类规则的形式来表示。比如，根据顾客信用信息的数据库，学习生成分类规则， 进而可以按照顾客的信誉度类别来对顾客进行识别( 见图2 - 3 ) 。 训练数据 姓名年龄收入信誉度 张三 s3 5 低 良 李四 s3 5 低优 分类方法 王五3 5 4 5 呙优 赵六 4 5 中良 分类规则 i f 年龄= 3 5 4 5 a n d 收入= 高t h e n 信誉度= 优 图2 - 3 ：获取信用规则 这些规则不仅仅是简单的分类，它能对数据库的内容提供更好的理解，也可 以用来为以后的数据样本分类。 ( 3 ) 使用第( 2 ) 步中的分类模型对其它测试数据进行分类，评估其性能( 见图 2 4 ) 。若满足学习基本要求，则进行第( 4 ) 步；否则，返回第( 2 ) 步继续训练学习。 ( 4 ) 运用得到的满足要求的分类模型对未知类标号的新数据进行预测分类。 测试数据 姓名年龄收入信誉度 as3 5 低优 b 3 5 - 4 5两优 新数据 ( c 3 5 4 5 ，高) 信誉度= 优 图2 4 ：使用信用模型对顾客分类 2 2 3 分类数据的预处理 数据库或者其他搜集到的数据往往具有一些遗漏和噪声等，因此在建立分类 模型之前，需要处理数据，以帮助提高分类的性能。 1 、数据清理 数据清理( d a t ac l e a n i n g ) 主要包括：填充遗漏的数据值、除去异常值( o u t l i e r ) 、 平滑有噪声的数据以及解决不一致问题等。使用一些数据清理方法对数据进行预 处理是有必要的，因为现在多数数据挖掘过程将处理的重点是避免所挖掘出的模 式对数据过分逼近( o v e rf i t t i n g ) 。遗漏的数据的处理往往采用忽略或用均值填补 遗漏值的方法，而噪声数据通常采用平滑技术进行处理，数据不一致可以利用它 们与外部的关联关系进行手工处理。 2 、相关分析 在分类时，有一些属性可能是不相关的，例如：一运动员参赛时的参赛号( 属 性) 就可能与比赛成绩不相关；同样地，一个人的学习成绩与身份证号( 属性) 1 3 就可能不相关。此外还可能有一些属性是冗余的。因此，有必要进行属性的相关 分析，删除学习过程中冗余的或不相关的属性。在机器学习中，这一过程被称为 特征选择( f e a t u r es e l e c t i o n ) 。属性的相关分析可以帮助提高分类的有效性和可伸 缩性。理想情况下，在原来的数据集上学习所用的时间要大于用于相关分析上的 时间加上从压缩了的数据集上学习的时间。 3 、数据转换 一些数据可以泛化到较高层的概念，例如，对于连续值的属性“年龄”的数 值可以泛化为诸如“儿童、青年、中年或者老年”若干个离散的区间。类似地， 对于离散值的属性，如“街道”，可以泛化到更高的抽象概念，如“城市”或者“国 家”。泛化可以有效地减少学习过程中的时间，因为泛化会压缩原来的训练数据 集。 2 2 4 分类方法的评估标准 分类算法的核心是分类器，其性能决定了分类结果对人们的有用度。分类方 法比较多，各有利弊，因此有必要对他们进行研究。一方面，可以对其加以改进 和完善，优化其性能。另一方面，可以扬长避短，在特定情况下选择最优的方法。 目前比较常用的分类方法的评估标准主要有以下几点： ( 1 ) 预测准确率 是指分类器正确地预测未知的数据( 即类标号信息未知的元组) 的类标号的 能力。各个分类器的性能是不同的，预测准确率也不同。如果一个分类器的分类 ， 准确率小于百分之五十，可以认为其预测结果是没有价值的，该分类器也就没有 什么用处了。在其他条件等同的情况下，我们当然首选准确率高的分类方法。 ( 2 ) 健壮性 健壮性又被称为鲁棒性，表示对那些带有冗余、噪声或者缺省值的数据模型 的正确预测能力。现实中的数据库通常有噪声，一个好的分类器应该能够消除噪 声的影响；相反，如果一个分类器不善于消除噪声的影响，将严重影响分类准确 率。 ( 3 ) 速度 指构造和使用分类器时的计算效率。一般情况下数据集中数据的数量和分类 1 4 准确率成正比，所以产生分类器的试验数据集通常是比较大的。性能好的分类器 在产生和使用时时间比较短。 ( 可伸缩性 指给定的规模大小不同的数据集，有效构造模型的能力。分类器应该能够适 应不同数据量的情况。有些分类器在数据量很小的情况下可以有效的构造模型， 但是随着数据量的增大，其构造模型的能力显著下降，这最终也会影响分类准确 性。 ( 5 ) 模型简洁度和可理解性 对于描述型的分类任务，模型描述越简洁并且越容易理解则越受欢迎。由于 用户往往不具有分类的专业知识，所以分类结果越简洁且容易理解越好。例如， 采用规则表示的分类器构造法是比较有用的，而神经网络方法产生的结果就比较 难以理解。 2 2 5 基于决策树的分类 决策树分类法是一种简单但却广泛使用的分类技术，它直接提供了一种展示 类似在什么样的条件下会得到什么相应的结果这类规则的方法，其表现形式是类 似于流程图的树结构，可以做出分类及预测。另外，它的生成过程以及分类、预 测过程和提取的分类规则比较易于理解。该方法的优点在于直观性和易于理解 性；不足之处是在节点选择时趋向于选择取值较多的属性并且整棵树都要受到根 节点的影响，也就是说根结点不同，就会造成整棵树完全不同。因此，在决策树 的生成过程中根节点的选取是非常重要的。本文采用了改进的节点( 属性) 选择 方法，有效避免了i d 3 算法的多值偏向属性选择的不足，得到分类率较高、结构 简洁的决策树s m c d t 模型。 决策树可以较容易转换为易于理解的分类规则，从根开始到每个叶节点的一 条路径就对应着一条分类规则。目前己形成了多种决策树算法及其改进算法，如 c l s 、i d 3 、c h a i d 、c a r t 、f a c t 、c 4 5 、s p r i n t 等。其中最著名的算法之 一是q u i n l a n 提出的i d 3 算法。 决策树的基本组成部分：决策节点、分支和叶子。在表示决策树时，中间节 点( 根节点) 常用矩形表示，而叶子节点则常用椭圆表示。下面举个例子来说明 1 5 决策树的构成：比如客户在贷款申请中，银行要对申请的风险大小做出判断，图 2 5 是为了解决这个问题而建立的一棵贷款风险决策树。 图2 - 5 贷款风险决策树 2 3 决策树的生成与改进的i d 3 算法 2 3 1 决策树的生成 决策树的生成过程一般分为学习与测试两个阶段。决策树学习阶段采用自顶 向下的递归方式进行，根据训练数据集提供的信息选择属性节点。建立决策树的 过程，实际就是不断地把数据进行划分的过程。每次划分对应着一个节点，也对 应着一个划分属性。 决策树算法分为两个步骤： 一是树的生成。利用属性选择方法逐层选择节点，直至生成叶节点。对每一 个划分属性的选择都要求使得分成的组之间的“差异”最大。各种决策树算法之间 的最主要区别就是对这个“差异”衡量方式的差别，也就是属性选择方法上的差 别。 二是树的修剪。在建立决策树的过程中没有必要让其生长的太“枝繁叶茂”， 这样会降低树的直观性和可用性，因此在适当的时候我们应该停止树的生长。决 策树停止分割的条件是：一个节点上的数据都是属于同一个类别或者没有属性可 以再用于对数据进行分割。常用的方法有事前修剪法和事后修剪法，事前剪枝法 的思想主要是设定决策树的最大高度( 层数) 来限制树的生长。与之相对应的是在 1 6 树建立好之后对其进行修剪的事后修剪，也就是说先允许树过度生长，然后根据 一定的规则，在保持决策树准确度的前提下剪去那些不具有代表性的节点和分 枝。 2 3 2i d 3 算法分析 i d 3 算法是q u i n l 如在1 9 8 6 年提出的一种基于信息熵的决策树学习算法【3 5 1 。该 算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的 归纳分类。该算法从树的根节点处的所有训练集开始，通常使用信息增益的方法 来帮助确定生成每个节点时应采用的合适属性。算法递归地应用到每个子节点， 直到一个节点上的所有样本都分到同一个类中。 d 3 算法的优点在于：搜索空间是完全的假设空间，目标函数必在搜索空间 中，不存在无解的危险；算法的基础理论比较清晰，在属性选择时利用了信息增 益的概念；决策树的每个分支都对应一个分类规则，可以生成容易理解i f - t h e n 分类规则，因此产生的分类规则直观性强，易于理解等。 但是，i d 3 算法也存在着如下不足瞰，3 7 】： ( 1 ) 计算信息增益时倾向于选择具有多值的属性，这样不太合理，因为在很 多情况下取值较多的属性并不总是最优的属性