（计算机应用技术专业论文）数据挖掘在学分制成绩管理中的应用研究.pdf

摘要 近年来，数据挖掘技术己得到广泛的研究，并在商业、金融、医 疗等领域得到成功地应用，但在教学方面的应用比较少。本论文以笔 者所工作的学院为例，提出了应用数据挖掘技术关联规则和决策树技 术来挖掘隐藏在学生成绩背后有价值信息的研究方案，目的是为教学 管理者在今后的教学工作中提供重要的决策依据。 关联规则和决策树是数据挖掘应用领域较广的两种算法。本文首 先以计算机系历届毕业学生的专业课成绩为例，通过对数据进行数据 清理、数据转换、数据归约等数据预处理，利用关联规则a p r i o r i 算 法探讨课程之间的影响关系，指导学生合理选课和安排对不同科目的 学习计划。并结合d m x 实现数据挖掘，得到了实验结果并对实验结 果进行了分析和解释。其次以学生的入学成绩和毕业时所修课程成绩 的绩点值为实验数据，提出了学生培养模型并给出求解方案。 以本人所授非计算机专业班级的学生为研究对象，通过对学生进 行问卷调查，获取了有关学生的上机时间、基础程度、对计算机的感 兴趣程度、学习习惯等调查数据，根据学院教务系统获取学生的基本 情况信息数据和考试成绩数据，利用关系数据库中的连接操作，形成 了一个包含多个属性的学生成绩分析数据库。在决策树模型的建立过 程中，采用的是c 4 5 算法。该算法递归选择具有最大信息增益率的 属性作为测试属性，最终生成了学生成绩是否良好和学生成绩是否不 及格两个决策树模型，得到了易于理解的分类规则，并对产生的分类 规则进行了分析和评价，从而为教学部门提供决策支持信息，促使更 好地开展教学工作，提高教学质量。 关键词数据挖掘，学分制，决策树，关联规则 a bs t r a c t t h er e c e n tt e ny e a r s ，t h ed a t am i n i n gt e c h n o l o g yh a sb e e nw i d e l y s t u d i e d ，a n di nb u s i n e s sa n df i n a n c e ，m e d i c a lc a r ea n do t h e rf i e l d sh a v e s u c c e s s f u l l ya p p l i e di nt e a c h i n g ，b u ta p p l i c a t i o ni sl e s s i nt h i sp a p e rt h e a u t h o rw o r kc o l l e g e ，f o re x a m p l e ，p u tf o r w a r dt h ea p p l i c a t i o no fd a t a m i n i n gt e c h n o l o g y a s s o c i a t i o nr u l e sa n dd e c i s i o nt r e e t oe x c a v a t e s t u d e n t s p e r f o r m a n c eb e h i n dh i d d e ni nt h ev a l u a b l ei n f o r m a t i o n r e s e a r c h p l a n ，t h ep u r p o s ei s f o rt e a c h i n gm a n a g e m e n ti nt h et e a c h i n gw o r kt o p r o v i d ei m p o r t a n t b a s i sf o rd e c i s i o n m a k i n g 。 a s s o c i a t i o nr u l e sa n dd e c i s i o nt r e ei sd a t am i n i n ga p p l i c a t i o nw i d e t w oa l g o r i t h m s f i r s t l y ，c o m p u t e rs c i e n c eg r a d u a t es t u d e n t sw i t ha l lt h e m a j o ra c h i e v e m e n t s ，f o re x a m p l e ，t h r o u g ht h ed a t ad a t ac l e a n i n g ，d a t a t r a n s f e r ，d a t aa b o u td a t ap r e t r e a t m e n t ，t oe x p l o r ea p r i o r ia s s o c i a t i o nr u l e s a l g o r i t h mu s i n gt h er e l a t i o n s h i pb e t w e e nc l a s s e s ，a n dg u i d es t u d e n t st o d i f f e r e n tc l a s s e sa n dr e a s o n a b l ea r r a n g e m e n tp l a no fs t u d ys u b je c t s c o m b i n i n gd m x r e a l i z ed a t am i n i n g ，g e tt h ee x p e r i m e n t a lr e s u l t sa n d t h e e x p e r i m e n t a l r e s u l t sw e r ea n a l y z e da n de x p l a i n e d n e x tt ot h e a d m i s s i o n sg r a d e sa n dg r a d u a t es t u d e n t sa tc o u r s e sg r a d e so fp o i n t sf o r t h ee x p e r i m e n td a t a ，a n dt h ep r o p o s e dm o d e li sg i v e ns t u d e n t s ih a v eg r a n t e db yt h ec o m p u t e rs p e c i a l i z e dc l a s s e so fs t u d e n t sa st h e r e s e a r c ho b j e c t ，t h r o u g ht h eq u e s t i o n n a i r es u r v e yt os t u d e n t s ，t h er e l e v a n t s t u d e n t sb a s e do nt i m ea n do nt h ec o m p u t e r , t h ed e g r e eo fi n t e r e s t ，a n d h a b i t se t c ，a c c o r d i n gt ot h es u r v e yd a t ao fc o l l e g es t u d e n t s a d m i n i s t r a t i o n s y s t e mf o rt h eb a s i cs i t u a t i o no ft h ei n f o r m a t i o nd a t aa n dt e s ts c o r e s ， u s i n g t h ed a t ai nt h ed a t a b a s ec o n n e c t i o nr e l a t i o n s h i p ，f o r m e da c o n t a i n i n gm u l t i p l ea t t r i b u t eo fs t u d e n ta c h i e v e m e n td a t a b a s e i nt h e d e c i s i o nt r e em o d e lo ft h ep r o c e s s ，u s e si sc 4 5a l g o r i t h m t h e a l g o r i t h mh a st h el a r g e s tr e c u r s i v ec h o i c eo fa t t r i b u t ei n f o r m a t i o ng a i n r a t e ，t e s ta t t r i b u t e s a sag o o ds t u d e n ta c h i e v e m e n ti sg e n e r a t e da n d w h e t h e rs t u d e n t sf a i l e dt w od e c i s i o nt r e em o d e l ，e a s yt ou n d e r s t a n dt h e r u l e so fc l a s s i f i c a t i o n ，a n dt h ec l a s s i f i c a t i o nr u l e sa r ea n a l y z e da n d e v a l u a t i o n ，a n dp r o v i d e d e c i s i o n s u p p o r t f o rt e a c h i n g d e p a r t m e n t i n f o r m a t i o n ，m a k e ab e t t e rt e a c h i n gw o r k ，i m p r o v et h e q u a l i t y o f t e a c h i n g k e yw o r d sd a t am i n i n g ，c r e d i ts y s t e m ，d e c i s i o nt r e e ，a s s o c i a t i o n r u l e s 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：苹即阢如一 日期： 上月且日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者繇避逝左新签名丛嗍赳年乒月4 日 硕士学位论文第一章绪论 1 1数据挖掘的发展 第一章绪论 数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越 来越多，迅速增长的数据背后隐藏着许多重要的信息。人们希望能够对其进行更 高层次的分析，以便更好的利用这些数据。目前的数据库系统可以高效地实现数 据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据 现有的数据预测未来的发展趋势，缺乏挖掘数据背后隐藏知识的手段，导致了“数 据爆炸但知识贫乏”的现象。人们开始考虑如何从海量的信息中发现有用的知识， 提高信息的利用率，面对这一挑战，数据挖掘( d a t am i n i n g 简称d m ) 和知识发现 这一新型的数据分析技术诞生了。近年来，数据挖掘的研究工作取得了很大的进 展，各种数据挖掘软件的应用大大地推动了人们掌握、处理信息的能力，并为人 们带来了很大的经济效益。 数据挖掘其实是一个逐渐演变的过程，电子数据处理的初期人们就试图通过 某些方法来实现自动决策支持，当时机器学习成为人们关心的焦点。机器学习的 过程就是将些已知的并已被成功解决的问题作为范例输入计算机，机器通过学 习这些范例总结并生成相应的规则，这些规则具有通用性，使用它们可以解决某 一类的问题。随后，随着神经网络技术的形成和发展，人们的注意力转向知识工程， 知识工程不同于机器学习那样给计算机输入范例，让它生成出规则，而是直接给 计算机输入已被代码化的规则，而计算机是通过使用这些规则来解决某些问题。 专家系统就是这种方法所得到的成果，但它有投资大、效果不甚理想等不足。于 是人们又在新的神经网络理论指导下重新回到机器学习的方法上，并将其成果应 用于处理大型商业数据库。这就是数据库中的知识发现，简称k d d ( k n o w l e d g e d is c o v e r yi nd a t a b a s e ) 。它泛指所有从源数据中发掘模式或联系的方法，人们 接受了这个术语，并用k d d 来描述整个数据发掘的过程，包括最开始的制定业务 目标到最终的结果分析，而用数据挖掘( d a t am i n i n g ) 来描述使用挖掘算法进 行数据挖掘的子过程。但最近人们却逐渐开始使用数据挖掘中有许多工作可以由 统计方法来完成，并认为最好的策略是将统计方法与数据挖掘有机的结合起来。 1 2 国内外研究现状 数据库中发现知识( k d d ) 一词首次出现在1 9 8 9 年举行的第十一届国际联合 硕士学位论文 第一章绪论 人工智能学术会议上。到目前为止，由美国人工智能协会主办的k d d 国际研讨会 已经召开了多次，规模由原来的专题讨论会发展到国际学术大会，研究重点也逐 渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之 间的相互渗透。i e e e 的k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版 了k d d 技术专刊。并行计算、计算机网络和信息工程等其他领域的国际学会、学 刊也把数据挖掘和知识发现列为专题和专刊讨论。 与国外相比国内对数据挖掘的研究稍晚，1 9 9 3 年国家自然科学基金首次支持 对该领域的研究项目。目前，国内的许多科研单位和高等院校竞相开展知识发现 的基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究所、空 军第三研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法在 知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的 研究，华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、 吉林大学等单位开展了对关联规则开采算法的优化和改造，南京大学、四川联合 大学和上海交通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据 挖掘。 经过多年的努力，数据挖掘技术的研究己经取得了丰硕的成果。目前，数据 挖掘应用于许多领域，尤其在银行、电信、保险、零售等商业领域。数据挖掘所 能解决的典型问题包括：数据库营销、客户群体划分、背景分析、交叉销售等市 场分析行为、以及客户流失性分析、客户信用计分、欺诈识别等。 针对于高校实施学分制后的成绩管理是一个新的应用领域，大部分原地方专 科院校升为本科院校后都要由原来的学年制转变为学分制管理。在国内，也有相 关学者的研究方向为数据挖掘技术和成绩管理或成绩分析的，但大部分研究是将 某个具体数据挖掘技术( 例如关联规则) 应用在学生成绩分析上，未见有将两种算 法应用在同一领域进行研究，更没有同时结合实施学分制后成绩的数据挖掘。所 以，根据学分制学生成绩数据库作一些初步的分析，进行数据挖掘研究是学生成 绩分析的一个新发展。 1 3 研究背景及意义 目前，地方高校的在校生人数都已达上万的规模，教师人数也在不断增加。 高校运行着的各种系统和各类数据库，如学籍管理、成绩管理、人事管理等，己 经积累了大量的数据。管理人员只能通过简单的统计或排序等功能获得表面的信 息，由于缺乏信息意识和技术，隐藏在这些大量数据中的信息一直没有得到应用。 如何对这些数据进行重新利用，将现有的管理数据转化为可供使用的知识，提高 2 硕士学位论文 第一章绪论 学校管理决策性，提高管理水平和办学质量，是高校必须考虑的问题。 数据挖掘技术在商业、金融业、保险业、市场营销等领域已获得了较为广泛 的应用，但对教育信息的挖掘与知识发现方面的研究和应用相对来说很少。高校 对学生信息、成绩等数据的处理一般停留在简单的数据备份和查询阶段。随着数 据挖掘技术的成熟及应用领域的不断扩展，不少高校研究人员已开始研究将数据 挖掘技术应用于高校的教学、管理中。例如：将数据挖掘技术应用于学生信息管 理、高校的教学管理、教学质量评估、合理安排课程、招生就业及考试系统中， 对提高学校教学管理水平起到了很好的指导作用。 高等院校的根本任务是通过教学和教育工作来培养高层次人才，所以教学 工作始终是学校的中心工作。高等教育的重点和关键是提高整个教育质量，而学 生成绩恰是评估教学质量的重要依据，也是评价学生对所学知识掌握程度的重要 标志。所以通过对学生的成绩进行分析评估，为引导各校领导重视教学工作，注 意改善教学条件，加强教学管理，深化教学改革，努力提高教学质量提供了重要 的依据。 数据挖掘是一种决策支持过程，是深层次的数据信息分析方法，将数据挖掘 技术应用于成绩评估方面是非常有益的，它可以全面地分析考试成绩与各种因素 之间隐藏的内在联系，比如，经过对学生相关数据进行分析，数据挖掘工具可以 回答诸如“哪些因素对学生成绩可能有影响 等类似的问题，这是传统评价方法 无法具备的。 利用数据挖掘工具，对学生的学习成绩进行分析处理，可以及时得到学生的 评价结果，对学生出现的不良学习行为进行及时指正。另外，还能够克服教师主 观评价的不公正、不客观的弱点，减轻教师的工作量。成绩作为考试的结果，不 仅是对学生学业和教师教学效果的检查和评定，更是一种具有反馈于教学活动、 服务于教育决策、为教育科研提供资料等作用的信息。为充分发挥考试的效能， 综合评价命题质量，及时反馈教学效果，沟通教学信息，教学部门对考试成绩进 行统计分析和总结是非常必要的。 1 4 研究主要内容 随着地方高校招生规模的扩展及学分制的实施，在校生人数越来越多，学生 成绩分布越来越复杂，除了用传统的归纳或分类的统计方法对学生成绩分析得到 的一些结论外，还有一些不易察觉的信息隐含于其中，因此把数据挖掘技术引入 到学生成绩分析中，以找到影响学生成绩的真实原因，有利于有针对性地提高教 学质量和教学效果。 本文的研究内容主要包括三个方面： 硕士学位论文第一章绪论 一是通过对某班学生在校各门课程成绩的分析，利用d m x 挖掘出课程间的有 用规则，提出了基于课程分析的成绩预警模型，为今后的教学课程设置提供了参 考，同时对于那些易导致学生留级、无学位、退学的课程能够显示出来，当这些 课程出现问题时，能对学生起到预警作用。 二是考虑一些主客观因素尤其是学生的入校成绩对学生毕业成绩的影响并 建立起相应的学生培养模型，为科学地进行学生管理提供了辅助信息。 三是利用数据挖掘技术对学生成绩数据库进行分析和研究，应用数据挖掘中 的i d 3 算法对学生成绩数据进行分类，并对得到的结果进行了分析，得出了影响 学生成绩相关因素以及其它的一些结论。 1 5 论文的安排 论文共分为五章，各章的具体内容安排如下： 第一章绪论。主要介绍了本论文的研究背景和研究意义，综述了数据挖掘 的理论渊源、发展现状，以及国内外数据挖掘的发展情况。 第二章决策树和关联规则技术研究。主要介绍数据挖掘中关联规则的基本 概念、经典算法及研究现状；分析数据挖掘中分类技术的概念、决策树建立的过 程及选择属性的量度、决策树中的剪枝技术，并详细分析决策树技术中主要的算 法。 第三章关联规则在学生成绩管理中的应用。主要探索在学生成绩管理中数 据挖掘关联规则的应用，以某班学生在校的各门课程成绩为例，给出了基于课程 分析的成绩预警模型，完整地实现了数据关联规则挖掘的全过程，结合类s q l 语 言的d m x 实现数据挖掘，得出实验结果图，提出学生培养模型并给出求解方案。 第四章决策树技术在学生成绩管理中应用。详细并完整的实现决策树挖掘 技术在成绩分析中的应用全过程，最后根据c 4 5 算法建立了两个分析模型，包括 学生成绩是否优良的决策树模型和成绩是否不及格的决策树模型，从而为教学部 门提供了决策支持信息，更好地开展教学工作，提高教学质量。 第五章结论。本章主要总结了本次研究的实现的全过程，提出了课题下一 步工作的展望。 4 硕士学位论文第二章决策树和关联规则技术研究 2 1决策树 第二章决策树和关联规则技术研究 2 1 1 决策树定义 决策树决是一种用于分类、聚类和预测的预测型建模方法，采用“分而治之 的方法将问题的搜索空间分为若干子集。 在求解分类问题的方法中，决策树( d e c i s i o nt r e e ，d t ) 是最有用的一种方 法。应用这种方法需要构建一棵树对分类进行建模。一旦建好了树，就可以将其 应用于数据库的元组并得到分类结果。 决策树分类方法的定义为： 给定一个数据库d - t l ，o e o9 t n ，其中t i = ，数据库模式包 含下列属性 a 1 ，a 2 ，a h ) 。同时给定类别集合c = c 1 ，c m 。对于数据 库d ，决策树或者分类树是指具有下列性质的树： 每个内部结点都被标记一个属性a i 。 每个弧都被标记一个谓词，这个谓词可应用于相应父结点的属性。 每个叶结点都被标记一个类c j 。 利用决策树求解分类问题包括两个步骤： 1 决策树归纳，利用训练数据构建一棵决策树。 2 对每个元组t i d ，应用决策树确定元组的类别。 一般来说，决策树是一个类似于流程图的树结构，其中每个内部节点表示在一个 属性上的测试，每个分枝代表一个测试输出，而每个叶节点代表类或类分布，树 的最顶层节点是根节点。更明确的说，决策树是通过根节点到叶节点的顺序对实 例进行分类，其中，每个节点代表一个属性，每个分枝代表它所连接的上节点在 其属性上的可能取值。 在决策树的基本结构图中，中间节点常用矩形表示，叶子节点用椭圆形表示， 如图2 - 1 所示。其中a 1 是a t t r i b u t ev a l u e s 的值。 硕士学位论文第二章决策树和关联规则技术研究 图2 - 1 决策树结构图 它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较，并根 据不同的属性值判断从该节点向下的分枝，在决策树的叶节点得到结论，整个过 程都是以新节点为根的子树上重复。举例来说，一个实例的分类是从树的根节点 开始，测试该节点所代表的属性，然后沿属性取值的某个分枝向下移动，不断重 复这个过程，直至到达叶节点，即得到该实例所属的类。从根节点到叶节点的每 一条路径就对应着一组属性测试的合取规则，整个决策树就代表实例属性值约束 的合取的析取表达规则。这样就很容易转换成i f - t h e n 形式的分类规则，根据这 个分类规则就可以比较容易对未知数据对象进行分类识别和预测。 用决策树进行分类主要包含两步。第一步是利用训练数据集构造一棵决策树 模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程。第二步 是利用己经生成的决策树模型对未知输入的数据样本进行分类。对输入的记录， 从根节点依次测试记录的属性值，直到到达某个叶子节点，从而找到该记录所在 的类。在这两个过程中关键是决策树的构造。 2 1 2 决策树的建立 决策树的建立过程主要由两个阶段组成：第一阶段，建树阶段。选取训练数 据集进行学习，导出决策树。决策树归纳的基本算法是贪心算法，它采用的是自 顶向下递归的各个击破方式来构建判定树。第二阶段，剪枝阶段。用测试数据集 检验决策树，如果所建立的决策树不能正确回答所研究的问题，我们要对决策树 进行剪枝以解决过分适应数据问题，直到建立一棵正确的决策树，目的是降低由 于训练集的噪声而产生的起伏。 建立决策树的算法可以被描述成一个递归的过程：首先，选择训练样本的一 个属性作为节点，对该属性的每种可能的取值创建一个分枝，并据此将训练样本 6 硕士学位论文第二章决策树和关联规则技术研究 划分为几个子集。然后，对每个分枝采取相同的方法，训练样本是其父节点划分 的若干子集中的对应于该分枝取值的那个样本子集。当以下情况出现时停止该节 点分枝的分裂，并使其成为叶节点： ( 1 ) 给定节点的所有训练样本属于同类 ( 2 ) 没有剩余属性可以用来进一步划分样本 ( 3 ) 该分枝没有样本。 建立决策树的算法如下： 算法：g e n e r a t e d e c i s i o n t r e e 由给定的训练数据产生一棵判定树。 输入：训练样本s a m p l e s ，由离散值属性表示：候选属性的集合a t t r i b u t el i s t 。 输出：一棵判定树。 方法： ( 1 ) 创建节点n ： ( 2 ) i fs a m p l e s 都在同一个类ct h e n ( 3 ) 返回n 作为叶节点，以类c 标记： ( 4 ) i fa t t r i b u t e 1i s t 为空t h e n ( 5 ) 返回n 作为叶节点，标记为s a m p l e s 中最普通的类； ( 6 ) 选择a t t r i b u t e l i s t 中具有最高信息增益的属性t e s t a t t r i b u t e ： ( 7 ) 标记节点为t e s t ：attribute ( 8 ) f o re a c ht e s ta t t r i b u t e 中的已知值a i ： ( 9 )由节点n 长出一个条件为t e s ta t t r i b u t e = a ；的分枝： ( 1 0 ) 设s i 是s a m p l e s 中t e s t _ a t t r i b u t e = a i 的样本的集合： ( 1 1 ) i fs i 为空t h e n ( 1 2 ) 加上一个树叶，标记为s a m p l e s 中最普通的类： ( 1 3 ) e l s e 力口上个由g e n e r a t e d e c i s i o n t r e e ( s l ，a t t r i b u t e - l i s t t e s t _ a tt r i b u t e ) 返回的节点。 说明如下： 1 决策树开始时，作为一个单个结点( 根节点) 包含所有的训练样本集。 2 若一个节点的样本均为同一类别，则该节点就成为叶节点并标记为该类别。 3 否则该算法将采用信息熵方法( 信息增益) 作为启发信息来帮助选择合适的属 性，以便将样本分为若干子集。这个属性就成为该节点的测试属性。在算法中， 所有属性均为离散值，若有取连续值的属性，就必须首先进行离散化。 4 一个测试属性的每个值均对应一个将要被创建的分枝，同时也对应着一个被 划分的子集。 5 算法递归使用上述各处理过程，针对所获得的每个划分均又获得一个决策树。 7 硕士学位论文 第二章决策树和关联规则技术研究 若一个属性一旦在某个节点出现，那它就不能再出现在该节点之后所产生的子树 节点中。 6 算法递归操作停止的条件是： ( 1 ) 一个节点的所有样本均为同一类别。 ( 2 ) 若无属性可用于当前样本集，这里用少数服从多数的原则，将当前节点 标记成叶节点，并标记为当前所含样本集中类别个数最多的类别。 ( 3 ) 没有样本满足条件，则创建个叶节点并将其标记为当前节点所含样本 集中类别个数最多的类别。 2 1 3 属性选择度量 上述算法的核心是确定分枝准则，即如何从众多的属性变量中选择一个最佳 的分裂属性。通常，在树的每个节点上使用信息增益( i n f o r m a t i o ng a i n ) 度量选 择属性。选择具有最高增益( 或最大熵压缩) 的属性作为当前节点的测试属性。该 属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机 性或“不纯性”。这种理论方法使得对一个对象分类所需的期望测试数目达到最 小，并确保找到一棵简单的树。 2 1 4 树剪枝 在实际应用中，直接生成的完全决策树不能立即用于对未知样本进行分类。 由于完全决策树对训练样本的特征描述得“过于精确 ，无法实现对新样本的合 理分析，所以此时它不是一棵分析新数据的最佳决策树。一棵完全决策树能准确 地反映训练集中数据特征，但因失去了一般代表性而无法用于对新数据的分类或 预测，这种现象称为“过适应 。解决过适应问题的主要方法是对决策树进行剪 枝。 剪枝( p r u n i n g ) 方法的主要目的是去掉那些噪声或异常数据，使决策树具有 更泛化能力。剪枝常采用统计度量，剪掉最不可靠的分枝，从而带来较快的分类， 提高树独立于测试数据进行正确分类的能力。剪枝按其实施的时间分为两种方法： 事前修剪法和事后修剪法。 1 事前修剪法 该方法通过提前停止树的构造而对树“剪枝”，即通过在当前节点上判断是 否需要继续划分该节点所含训练样本集来实现。一旦停止，节点不再继续分裂， 当前节点就成为一个叶节点。该叶节点中可能包含多个不同类别的训练样朴由于 该修剪是在分枝之前做出的，所以称之为事前修剪。 事前修剪法的优点是在树生成的同时进行了剪枝，因而效率高，但是它可能 8 硕士学位论文第二章决策树和关联规则技术研究 剪去了某些有用但还没生成的节点。常用的方法是设定决策树的最大高度( 层数) 来限制树的生长。还有一种方法是设定每个节点必须包含的最少记录数，当节点 中记录的个数小于这个数值时就停止分割。然而，选择一个适当的阈值是比较困 难的，较高的阈值可能导致过分简化的树，而较低的阈值可能会导致多余树枝无 法修剪。 2 事后修剪法 该方法是由完全生长的树剪去分枝。通过删除节点的分枝，剪掉树节点。它 在允许决策树得到最充分生长的基础上，再根据一定的规则，剪去决策树中的那 些不具有一般代表性的叶节点或分枝。修剪后，被修剪的分枝节点就成为一个叶 节点，并将其标记为它所包含样本中类别个数最多的类别。 事后修剪法是一边修剪一边检验的过程，一般规则是：当树建好之后，对每 个内部节点，首先计算该节点上的子树被剪枝可能出现的错误率，然后，使用每 个分枝的错误率，结合每个分枝观察的权重评估，计算不对该节点剪枝的期望错 误率。如果剪掉该节点能够降低错误率，那么该节点的所有子节点就被剪掉，该 节点成为叶节点。产生一组逐渐被剪枝的树之后，使用一个独立的测试集评估每 棵树的准确率，就能得到具有最小期望错误率的决策树。 当然也可以结合使用事前修剪和事后修剪，形成混合的修剪方法。事后修剪 比事前修剪需要更多的计算时间，但通常产生的决策树更为可靠。 2 1 5 生成分类规则 决策树构造完毕后，就可以由决策树直接提取出分类规则，并以i f t h e n 形 式来表示规则。对从根到叶节点的每条路径创建一个规则。沿着给定路径上的每 个属性一值对形成规则前件( i f 部分) 的一个合取项。叶节点包含类预测，形成规 则的后件( t h e n 部分) 。 2 1 6 决策树相关算法 1 i d 3 算法 i d 3 算法是从c l s 算法发展而来，它是由q u i n l a n 于1 9 8 6 年提出的。在i d 3 算法 中属性的选择使用熵，使分类的效率和质量大大改进，因而应用非常广泛，是到 目前为止决策树方法中最常用的算法。i d 3 算法是一种基于信息增益的典型的自 上而下决策树归纳算法。该算法的主要特征是在一个结点上使用最大的信息增益 量作为启发式来决定应选取哪一个属性来进行树的展开。采用这种方法得到的决 策树结构简单、计算量小，但数据集规模较大的时候，就会出现过适应性的情况， 所以仅适用于小规模数据集的学习问题。 9 硕士学位论文第二章决策树和关联规则技术研究 其具体步骤如下： 已知训练例子集p n 。 ( 1 ) 如果p n 中的所有例子均为正例，则产生一个y e s 结点并终止：如果p n 中的 所有例子均为反例，则产生一个从n o 结点并终止：否则，根据该算法的启发式 策略选择一个属性a ，设a 取值为v l ，v 2 ，v r ，并生成新结点( 如图2 - 2 ) 。 图2 - 2 生成结点 ( 2 ) 将p n 中的例子根据其属性a 的取值加以划分，生成r 个子集记为p n l ，p n 2 p n r 。 ( 3 ) 递归地应用该算法到每个子集p n i 。 其中基于熵的属性选择如下： 设训练例子集p n 中含有p 个正例和n 个反例，则一个例子属于正例集p e 的概率为 p ( p + n ) ，属于反例集n e 的概率为n ( p 十n ) 。一棵决策树可以看作正、反例集的消 息源，因而产生这些消息期望信息为 ppnn i ( p ，n ) ：一百l o g 而一丽0 9 2 丽 公式( 2 - 1 ) 设属性a 取值为 a 1 ，a 2 ，a r ，) ，它们将p n 分类为r 个子集 p n l ，p n 2 p n r ) 。设 p n i 含有p ；个正例和n ；个反例，则子树所需要的期望信息的加权平均值为i ( p ；，n ，) 。 并且以a 为根的树所需要的期望信息为各子树所需要的期望信息的加权平均值， 即 rp i + n i e a ) 2 善五百i ( 陀n 1 ) 而以a 为根进行分类所得到的信息增益为： g a i n ( a ) = i ( p ，n ) 一e ( a ) 一个好的分类属性将使信息增益最大。 1 0 公式( 2 - 2 ) 硕七学位论文第二章决策树和关联规则技术研究 2 c 4 5 算法 决策树c 4 5 在如下几个方面改进了i d 3 算法： ( 1 ) 缺失数据。在构建决策树时，可以简单地忽略缺失数据，即在计算增益 比率时，仅考虑具有属性值的记录。为了对一个具有缺失属性值的记录 进行分类，可以基于已知属性值的其他记录来预测缺失的属性值。 ( 2 ) 连续数据。基本思想是基于训练样本中元组的属性值将数据划分为一 些区域。 ( 3 ) 剪枝。在c 4 5 中，有两种基本的剪枝策略： 子树替代法。是指用叶结点替代子树。仅当替代后的误差率与原始树 的误差率接近时才替代。子树替代是从树的底部向树根方向进行的。 子树上升法。是指用一棵子树中最常用的子树来代替这棵子树。子树 从当前位置上升到树中较高的结点处。对于这种替代也需要确定误差 率的增加量。 ( 4 ) 规则。c 4 5 既可以用决策树分类，也可以利用从决策树生成的规则进 行分类。别外，还提出了一些简化复杂规则的技术。一种方法是如果 训练集中的所有记录都被同等看待，则用较简单的形式来代替一条规 则的左侧部分。当没有其它的规则可用时，“其它类型的规则可以 用来表示应该做什么。 ( 5 ) 分裂。i d 3 算法偏袒具有较多值的属性，因而可能导致过拟合。在极 端的情况下，如果某个属性对于训练集中的每个元组都有惟一的一个 值，则认为该属性是最好的。这是因为对于每个划分都只有一个元组。 通过考虑每个划分中的势( c a r d i n a l i t y ) ，可以得到一定的改进。这 种方法利用增益比率来代替增益。增益比率( g a i n r a t i o ) 被定义为： g a i n r a ti o = g a i 面a 、 公式( 2 - 4 ) e 认1 为了达到最佳分裂的目的，c 4 5 先计算每个属性的增益，然后仅对那些高于信 息增益平均值的属性应用增益比率进行测试，这是为了补偿一个子集的规模与初 始集合的规模很相近进增益比率非常大的情况。 2 1 7 决策树构建算法性能的主要因素 决策树构建算法性能的主要因素取决于误训练集的规模和如何选择最佳分裂 属性。 硕士学位论文第二章决策树和关联规则技术研究 1 选择分裂属性。在构建决策树的过程中，哪个属性作为分裂属性会影响算 法性能，有一些属性作为分裂属性要优于其他属性。属性的选择不仅涉及 检验训练集中的数据，而且还涉及从领域专家得到的输入。 2 分裂属性的次序。 3 分裂数目。有些属性的定义域比较少，所以分裂的数目显然要根据定义域 来确定。但是如果定义域是连续的或者具有较大量的值，则分裂的数目就 不容易确定。 4 树的结构。为了改进应用树进行分类的性能，总是希望得到具有最少层次 的平衡树，然而在这种情况下，需要与多路分枝进行更加复杂的比较。 5 停止准则。当训练数据被正确分类时，树的产生过程就该停止。为了防止 产生过大的树，有时也希望提前停止。另外，提前停止还可以防止过拟合。 6 训练数据。产生的决策树的结构取决于训练数据。如果训练数据集太小， 则产生的树由于没有足够的特殊性，而不能很发地应用于更加通用的数据。 如果训练数据集太大，则产生的树可能发生过拟合。 7 剪枝。一棵树被构建以后，还需要对树进行修剪以提高在分类阶段树的性 能。剪枝阶段可能会删除过多的比较或者删除一些子树，以获得更好的性 能。 2 1 8 决策树的优缺点 优点：决策树易于理解并且高效。生成的规则易于解释和理解。由于树的规 则独立于数据库规模，所以决策树对于大型数据库具有很好的扩展性。数据库中 的每个元组经过这个树的过滤，所需时间是固定的并且正比于树的高度。可以对 许多属性的数据构建决策树。 缺点：决策树不易于处理连续数据。数据的属性域必须被划分为不同的类别 才能处理，所用的方法是将定义域空间划分为矩形区域。并非所有的分类问题都 可以转化成这种类型。决策树处理缺失数据也很困难，这是由于在树中不能产生 正确的分枝。决策树过程忽略了数据库中属性之间的相关性。 采用这种方法得到的决策树结构简单、计算量小，但数据集规模较大的时候， 就会出现过适应性的情况，所以仅适用于小规模数据集的学习问题。 硕士学位论文 第二章决策树和关联规则技术研究 2 2 关联规则技术 若两个或多个变量的取值之间存在某种规律性，就称为关联阱1 。关联规则 是数据挖掘诸多功能中的一种，也是目前最为重要和应用最广泛的数据挖掘方法 之一。关联规则的概念由a g r a w a l 、m i e l i n s k i 、s w a m i 提出，是数据中一种简单 但很实用的规则。关联规则模式属于描述型模式，发现关联规则的算法属于无监 督学习的方法。关联规则挖掘是发现大量数据中项集之间有趣的关联或相关联 系。随着大量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘 关联规则越来越感兴趣。从大量商务数据中发现有趣的关联关系，可以帮助许多 商务决策的制定。典型的关联规则挖掘是购物篮分析。由于关联规则挖掘可以发 现用传统的人工智能和统计方法无法发现的项与项或属性与属性间的关联规律， 因此具有重要的研究价值，同时它也满足了人们从大规模数据存储中获取知识的 迫切需求。目前世界上知名大学的研究机构和各大i t 公司的研究部门都投入了 大量精力对其进行研究，并取得了诸多研究成果。美国斯坦福大学智能数据库系 统实验室开发出了大量的商用化数据挖掘系统。i b 公司的a l m a d e n 实验室所进 行的q u e s t 项目同样也是数据挖掘研究领域中的佼佼者，该项目包含了对关联规 则、序列模式、分类及时间序列聚类的研究。除了以上提及的世界知名的公司和 科研机构外，还有许多大学的研究机构和学者对该领域的发展做出了重要贡献， 如加拿大s i m o nf r a s e ru n i v e r s i t y 大学的j i a w e i ha n ，比利时赫尔辛大学的 m a n n i l a to i v o n n e n 等都是数据挖掘研究的著名专家，它们的许多工作是在该 领域中具有奠基性的。 近年来，国内的关联规则挖掘研究也正逐渐掀起高潮，出现了一批相关的科 研项目，在算法和应用方面取得了一些具有扩展性或突破性的研究成果。尽管关 联规则挖掘起源于商业上对市场购物篮进行分析的问题，但是随着研究的不断深 入，其基本模型在多角度得到了扩充。关联规则挖掘技术的应用领域也越来越广 泛概括起来主要包括：商业与金融、人口普查数据分析、工程技术数据分析、医 疗、财政、宏观决策支持、电子商务、网站设计、通信和互联网等。关联分析的 目的是挖掘隐藏在数据间的相互关系，自动探测以前未发现的隐藏着的模式。 2 2 1 关联规则相关概念 1 项 对一个数据表而言，表的每个字段都具有一个或多个不同的。字段的每种取 值都是一个项( i t e m ) 。在进行挖掘关联规则时，项一般表示成谓词的形式，如 商品类型( 计算机) ，表示其中“商品类型”是字段名，“计算机”是字段的值。 硕士学位论文第二章决策树和关联规则技术研究 有时也直接用字段的值来表示。 2 项集 项的集合就是项集( i t e m s e t ) 。包含k 个项的项集被称为k 一项集，k 表示 项集中项的数目。由所有的项构成的集合是最大的项集，一般用符号i 表示。 3 事务 事务是项的集。本质上，一个事务就是事实表中的一条记录。事务是项集i 的子集。事务的集合称为事务集，通常就是事务数据库。一般用符号d 表示事务 集。对销售数据而言，事务数据库的记录一般由事务处理时间、一组顾客购买的 物品、顾客标识号等几个部分组成。每一个事务都有一个唯一的标识，如事务号， 记作t i d 。 数据库中关联规则的挖掘可形式化地定义为：设i = i 。，i ：，i ) 是所 有项目的集合，即数据库中所有的字段；d 是所有事物的集合，即数据库；每个 事务t 是一些项目的集合，t 包含在i 中，每个事务可以用惟一的标识符t i d 来 表示。设x 为某些项目的集合，如果x c t ，则称事务t 包含x 。则关联规则表 一 ， 不为： ( x c t ) x = c y c t ) f 其中x c t ，y c i ，x n y = 。 关联模型主要描述了一组数据项目的密切度或关系关联可分为简单关联、 时序关联、因果关联。关系或规则总是用一些最小置信度级别来描述的。置信度 级别度量了关联规则的强度。 关联规则的挖掘可以发现大量数据中数据项集之间有趣的关联。关联规则可 记为：a = = b ，a 称为前提或左部，b 称为后续或右部，更普遍性，则可表示关联规 则为：a 。