（计算机应用技术专业论文）数据挖掘技术在成人学生授课方式偏好分析中的应用.pdf

中文摘要 本文介绍了数据挖掘的相关概念，系统论述了数据挖掘技术及其挖 掘算法，以及数据挖掘技术在各个领域中的应用情况。着重研究了分类 规则中的决策树方法，并对决策树技术的各类算法的原理、特点进行了 系统阐述。文中运用相关分析并结合c 4 5 决策树算法，对天津财贸管 理干部学院的成人大专学生喜爱的“授课方式问卷调查结果数据集进 行了数据挖掘，其目的就是通过对挖掘结果产生的规则进行分析，从 而对不同专业、不同年龄段等各类群体的学生采取更具针对性的、适当 的教学策略，实现个性化教学，从而提高教学效率。 本文针对不同群体学生“授课方式修选择结果的数据，初步探讨了 在数据清理阶段，利用统计学中的相关性分析方法，来预先对 i f 练集中 的属性集合进行归约，( 其中，筛选属性的阈值设定，主要依据相关系 数检验表中的参考值) 进而简化树结构，提高数据挖掘的效率。本文详 细描述了运用c 4 5 算法对约简后的训练集进行数据挖掘的具体实现方 法，对由此产生的模型进行了分析、验证，最后，根据得出的规则，给 出了针对不同群体学生的教学策略。此外，对适于大数据集挖掘的s l i q 算法的原理、特点也进行了一定地描述，并给出了伪代码。 关键词：数据挖掘、分类、决策树、基于决策树的分类算法、相关性分 析、个性化教学 a b s t r a c t t h i sp a p e ri n t r o d u c e sd a t am i n i n ga n di t sr e l e v a n t c o n c e p t i o na n da l s o s y s t e m a t i ce x p o u n d sd a t am i n i n gt e c h n o l o g ya n di t sm i n i n ga l g o r i t h m s i tm a k e s as p e c i a le f f o r tt o s t u d yc l a s s i f i c a t i o n r u l e sd e c i s i o nt r e ea n ds y s t e m a t i c e x p o u n d s d e c i s i o nt r e e t e c h n o l o g y st h e o r ya n df e a t u r eo fe v e r ya l g o r i t h m s a f t e rt h eq u e s t i o n n a i r ei n v e s t i g a t i o nt ot h es t u d e n t so ft i a n j i ni n s t i t u t eo f fi n a n c i a l & c o m m e r c i a lm a n a g e m e n t ，t h ea u t h o rm a k e sad a t am i n i n go nt h e d a t as e to ft h es t u d e n t s f a v o r i t et e a c h i n gm e t h o d sa n dm a k e sac o r r e l a t i o n a n a l y s i sb yt h ed e c i s i o nt r e em e t h o d a sar e s u l t ，t oh e l pt e a c h e r st of i n dm o r e s u i t a b l et e a c h i n gt a c t i c sf o rt h ed i f f e r e n ts p e c i a l t i e s ，d i s t i n c t a g es t a g e sa n d m a k et h e i rt e a c h i n gm o r ee f f i c i e n c y a c c o r d i n gt ot h ed a t ao nt h ec h o i c ef o rt e a c h i n gm e t h o db yd i f f e r e n ts t u d e n t g r o u p s ，t h ep a p e rs t u d i e sa n da n a l y z e st h eu s i n go fc o r r e l a t i o na n a l y s i si n p r e r e d u c t i o na t t r i b u t e sa s s e m b l yo ft r a i n i n gs e ti nt h ed a t ac l e a n i n gs t a g e s e t t i n g t h et h r e s h o l do f s c r e e n i n g a t t r i b u t e m a i n l y i na c c o r d a n c ew i t h c o r r e l a t i o nc o e f f i c i e n te x a m i n et a b l e ，f u r t h e rs i m p l i f yt h es t r u c t u r eo f t h et r e e t o i m p r o v ed a t am i n i n ge f f i c i e n c y t h i sp a p e rg i v eam i n u t ed e s c r i p t i o no f s p e c i f i c r e a l i z a t i o nm e t h o dt h a tu s i n gc 4 5 a l g o r i t h mt o d a t a m i n i n g o n r e d u c t i o n t r a i n i n gs e t i na d d i t i o n ，i n t r o d u c e ss l i qa l g o r i t h mt h e o r y ，f e a t u r e w h i c hi ss u i t a b l ef o rd a t am i n i n go nl a r g ed a t as e ta n dg i v ei t sp s e u d oc o d e k e y w o r d s ：d a t am i n i n g ，c l a s s i f i c a t i o n ，d e c i s i o nt r e e ，c l a s s i f y i n ga l g o r i t h m b a s e do nd e c i s i o nt r e e ，p e r s o n a l i z a t i o nt e a c h i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丕鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 - 2 哆年 厂月岁口日 学位论文版权使用授权书 本学位论文作者完全了解苤洼盘堂 有关保留、使用学位论文的规定。 特授权苤鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 靴敝储鹤：嘲 签字日期：矽岁年j 月扣日 新躲移勿司 签字日期：2 和7 年 月 日 第一章引言 1 1 研究背景与意义 第一章引言 随着信息社会的来临，大量信息在给人们带来方便的同时也带来了信息 的消化、信息的辨识、信息的安全、信息形式的一致性等问题。人们开始考 虑：如何才能不被信息淹没，而且从中及时发现有用的知识，提高信息利用 率，最终避免“数据爆炸但知识贫乏一的现象朝。面对这一挑战，数据挖掘 和知识发现技术应运而生，并显示出强大的生命力。数据挖掘和知识发现使 数据处理技术进入了一个更高级的阶段。它不仅能对过去的数据进行查询， 而且能够找出过去数据之间的潜在联系，进行更高层次的分析，以便更好地 解决决策、预测等问题。选择数据挖掘这一术语，表明了与统计、精算、长 期从事预言模型的经济学家之间没有技术的重叠。数据挖掘是一门交叉性学 科，涉及到机器学习、神经网络、模式识别、归纳推理、统计学、数据库、 数据可视化、高性能并行等多个领域。 1 1 1 数据挖掘的背景 数据挖掘的商业背景： 数据挖掘首先是需要商业环境中收集了大量的数据，然后要求挖掘的知识 是有价值的。有价值对商业而言，不外乎三种情况：降低开销；提高收入； 增加股票价格。 数据挖掘的技术背景： 1 ) 数据挖掘技术包括三个主要部分：算法和技术；数据；建模能力。 2 ) 数据挖掘和机器学习( m a c h i n el e a r n i n g ) 机器学习是计算机科学和人工 智能a i 发展的产物。机器学习分为两种学习方式：自组织学习( 如神经网络) ； 从例子中归纳出规则( 如决策树) 数据挖掘的社会背景： 数据挖掘号称能通过历史数据的分析，预测客户的行为，而事实上，客户自 己可能都不明确自己下一步要作什么。所以，数据挖掘的结果，没有人们想 象中神秘，它不可能是完全正确的。客户的行为是与社会环境相关连的，所 第一章引言 以数据挖掘本身也受社会背景的影响。 用评级的模型运行得非常成功，但是， 1 1 2意义 比如说，在美国对银行信用卡客户信 它可能不适合中国。 数据挖掘技术同样可以应用于教育管理领域：对学生成绩数据库进行数 据挖掘，可找出影响学生总体成绩的关键学科，通过加强对这些关键学科的 教学管理，提高学生关键学科的成绩，从而间接的促进其他学科的学习成绩； 根据学校教学质量评估的实际情况，对学生的评教数据库以及教师的信息库 进行数据挖掘，从中找出影响评教结果的关键因素，为教师提高教学水平、 改善教学质量提供决策依据。本文结合成人高校内部组织的，有关“学生乐 于接受的授课方式 的问卷调查活动，对学生选择的授课方式调查结果数据 库进行数据挖掘，期望找出不同类型学生所乐于接受的授课方式，为教师在 教学过程当中改进、丰富、完善教学方法，提高教学效率提供有针对性的策 略依据。 1 2 研究现状 与国外相比，国内对数据挖掘的研究稍晚，没有形成整体力量。目前， 国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研 究，这些单位包括清华大学、中科院计算技术研究所、空军第三研究所、海 军装备论证中心等。其中，北京系统工程研究所对模糊方法在知识发现中的 应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究，华 中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉 林大学等单位开展了对关联规则开采算法的优化和改造；南京大学、四川联 合大学和上海交通大学等单位探讨、研究了非结构化数据的知识发现以及 w e b 数据挖掘。 g a r t n e rg r o u p 的一次高级技术调查将数据挖掘和人工智能列为“未来三 到五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理 体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。根据最近 g a r t n e r 的h p c 研究表明，“随着数据捕获、传输和存储技术的快速发展，大 型系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用更为广阔 的并行处理系统来创建新的商业增长点。” 第一章引言 数据挖掘技术在教育领域上的应用也已经开始，但并不广泛。上海海事 大学使用基于决策树的技术，设计的教育信息挖掘模型( d t e i d m ) ，对学校 积累的学生的各类相关信息如：课程成绩库、学生基本信息等进行挖掘，以 期对教育管理、改革提供决策依据。另外，浙江大学运用关联规则技术对高 校的人事信息库进行挖掘，试图找到影响学科发展的因素，发现如何评价一 个学科，以及影响学科发展的各个要素之间的关系。 当前，在成人教学过程中，学生生源素质变化很大，许多教师感到学生 的学习态度越来越差，教师授课难度也在不断加大。因此，教学效率同其他 各层次教学相比较，属于较低一类。针对这种情况，要想改善这一局面，首 先要明确学生是教、学当中的主体，既然主体发生了变化，那么作为客体的 教师自然也要改变以前的教学方式，以适应这一变化。 那么，如何变化，首先就要分析成人学生特点，研究他们究竟适于在哪 种情境中更乐于学习。为此，学院教务管理部门，对学生所喜爱的授课方式 进行了问卷调查，并对结果进行分析、研究，以便为今后的教学提供更具针 对性的策略。但是，如果采用传统手段对结果进行简单的数据分析、列举， 并不能揭示出本质性的规律，对教学的指导作用也不是十分明确。所以，如 何分析、表达、解释和使用调查结果，使其给出相匹配教学策略，从而产生 好的教学效果，实现和谐的教学环境，正是目前面临的一个值得研究的新课 题。 1 3 研究内容 本文介绍了数据挖掘的相关概念，简要阐明了一些数据挖掘技术及其相 关的挖掘算法。详细论述了分类规则挖掘中各种决策树方法的特点及算法实 现的原理，重点研究了c 4 5 决策树算法在教学授课方式选择中的应用策略。 通过对天津财贸管理干部学院成人大专学生选择的乐于接受的授课方式结 果数据及其学生基本数据的挖掘，利用c 4 5 决策树算法挖掘出不同类型的 成人学生所乐于的接受授课方式，并对挖掘结果进行分析并验证其有效性， 从而制定出有针对性的指导策略，以提高教学效率。 第二章数据挖掘概述 2 1 数据挖掘的概念 第二章数据挖掘概述 数据挖掘在1 9 8 9 年8 月美国底特律市召开的第十一界国际联合人工智能 学术会议上正式形成。从9 5 年开始，每年举行一次知识发现( k n o w le d g e d i s c o v e r yi nd a t a b a s e ，k d d ) 国际学术会议，把对数据挖掘知识和知识发 现的研究推入高潮。数据挖掘还有被译为数据采掘、数据开采和数据发掘等， 但数据挖掘还未有一致的定义。对数据挖掘有如下定义： 定义1g p i a t e t s k ys h a p i o r ，w j f r a w l e y 等定义数据挖掘为从 数据库的大量数据中揭示出隐含的、先前未知的、潜在有用的信息的非平凡 过程。 定义2有人简单认为，数据挖掘就是数据库中知识的发现。 定义3有人认为，数据挖掘是发现数据中隐藏的模式和关系的过程。 定义4有人认为，数据挖掘是从大量数据中提取或挖掘知识。 定义5f a y y a d 等在“知识发现9 6 国际会议一上认为，知识发现是从 数据库中发现知识的全部过程，而数据挖掘则是此全部过程中一个特定的关 键一步。这种观点将数据挖掘的对象局限于数据库。 定义6 数据挖掘广义的定义为在一些事实或观察数据的集合中寻找模 式的决策支持的过程h ，。 综上所述，我们可以定义数据挖掘为在各类数据( 包括结构化数据、半 结构化的数据和非结构化数据) 所组成的不同形式的数据集合( 数据库、文 件系统或其他) 中，通过一定的工具与方法寻找出暗含地、有价值的知识的 一类深层次的数据分析方法n 引。 数据挖掘的对象可以是结构化的，如关系数据库中的数据；也可以是半 结构化的，如文本、图形和图像数据；甚至是分布在网络上的异构型数据。 发现知识的方法可以是数学的，也可以是非数学的：可以是演绎的，也可以 是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控 制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把 人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决 策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、 人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术 第二章数据挖掘概述 人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。 这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要 去发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际 上，所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域 的，同时还要能够易于被用户理解。最好能用自然语言表达所发现的结果。 2 2 数据挖掘的方法 数据挖掘方法通常可分为两大类：一类是基于统计分析的，常用的技术 有概率分析、相关性、聚类分析和判别分析等；另一类是基于人工智能中的 机器学习，通过训练和学习大量的样本得出需要的模式或参数。由于各种方 法都有自身的功能、特点以及应用领域，一种数据挖掘算发不可能完成所有 不同类型的数据挖掘任务，通常是将多种技术结合使用，形成优势互补。常 用的数据挖掘方法有决策树法、遗传算法、贝叶斯网络、粗糙集、神经网络、 统计分析等。 2 3 数据挖掘的基本过程 保证数据挖掘成功的两个关键要素：一是准确定义你所要解决的问题， 定位准确的问题通常会带来好的回报；二是使用正确的数据，选定你所能得 到的数据，并对这些数据做有效的整合和转换，数据挖掘的成功离不开清晰 的过程定义。数据挖掘过程一般包括采集数据、数据预处理、数据变换、数 据挖掘和解释评价。数据挖掘的核心技术是人工智能、机器学习、统计等， 但一个数据挖掘系统不是多项技术的简单组合，而是一个完整的整体，它还 需要其他辅助技术的支持，才能完成数据挖掘的过程，最后将分析结果呈现 在用户面前。其中数据挖掘的数据分析过程可分成四个过程：数据预处理、 数据变换、数据挖掘和模式的解释评价。 2 3 1 数据预处理 数据预处理：本阶段又可进一步细分成数据清理、数据选择和数据集成。 数据清理：其任务是消除数据源( 如：关系数据库、数据仓库、事物 数据库、超文本和多媒体数据、w w w 等) 中的噪声、识别和处理孤 立点数据，纠正数据中的不一致，处理空缺值。数据中存在随机错误 第二章数据挖掘概述 ( 噪声) 和孤立点。噪声应采取措施使其平滑，孤立点应识别是错误 数据还是有用的但以前没有认识到的数据。被挖掘的数据，特别是来 自不同数据源的数据，可能对同一对象采用不一致的描述；输入的错 误也可能造成不一致。对数据中的空缺值，可根据其数据量的大小、 对数据挖掘结果可能的影响，采用忽略该纪录或填入适当的值( 如中 值或平均值) 。 数据选择：其任务是从所有与业务对象有关的数据中选择出适用于数 据挖掘应用的数据，舍弃与数据挖掘无关的数据。 数据集成：在这一步中，是将多个数据源中的数据结合起来存放在一 个一致的数据存储中，在这一过程中要消除属性的冗余。 数据清理、数据选择和数据集成三者的操作次序由数据源的环境与数据 挖掘的环境决定，可能的情况下先进行数据选择可以减少后阶段操作的数据 量。 2 3 2 数据变换 将数据转换成适合于挖掘的形式。主要内容包括： 聚集：对某些数据进行汇总以适合挖掘算法。如将一天的销售量汇总 成日销售量。 数据归纳：使用概念分层，用高层次概念替换低层次的原始数据。 属性规范化：将属性数据按比例缩放，使之落在一个特定的区间，如 0 - 1 0 0 。 属性构造：由已有的属性构造和添加新的属性，如由属性h e i g h t 和 w i d t h 构造和添加a r e a 属性。 数据量化：对量化属性，使用预定义的概念分层进行离散化，以区间 值替换属性原来的数值。 2 3 3 数据挖掘 根据所采用的挖掘算法，运行相应挖掘软件和程序，来分析数据，产生 候选数据模式。 2 3 4 模式的解释评价 数据挖掘将获取的信息以便于用户理解和观察的方式反映给用户，由于 第二章数据挖掘概述 用户要求的不同，数据挖掘分析的数据的范围会有所不同，例如分析一年内 或三个月内的销售情况，再例如分析东部地区的销售情况，这样数据挖掘系 统会得出不同的结论。 如果分析人员对分析结果不满意，可以递归地执行上述三个过程，直到 满意为止。总之，该过程的任务就是根据给定的兴趣度来评估所发现的候选 数据模式，过滤掉不感兴趣的模式，表示真正有兴趣的模式。 评价数据挖掘工具的主要指标：数据准备、数据访问、算法与建模、模 型评价和解释、用户界面。 数据挖掘过程的分步实现，不同阶段会需要不同专长的人员，他们大体 可以分为三类：业务分析人员，要求精通业务，能够解释业务对象，并根据 各业务对象确定出用于数据定义和挖掘算法的业务需求；数据分析人员，精 通数据分析技术，并对统计学有较熟练得掌握，有能力把业务需求转化为数 据挖掘的各步操作，并为每步操作选择合适的技术；数据管理人员，精通数 据管理技术，并从数据库或数据仓库中收集数据。 2 4 数据挖掘的应用领域 由于数据挖掘能够带来巨大的经济效益，所以，数据挖掘在商业领域应 用非常广泛，比如金融( 风险预测) 、零售( 顾客行为分析) 、电信、电子商 务等。并且为解决诸如欺诈甄别、保留客户、消除摩擦、数据库营销、市场 细分、风险分析、亲和力分析、客户满意度、破产预测、职务分析等业务问 题提供了有效的方法。例如，电讯公司和信用卡公司就是用数据挖掘检测欺 诈行为的先行者。保险公司和证券公司也开始采用数据挖掘来减少欺诈。零 售商则更多的使用数据挖掘来决定每种商品在不同地点的库存量，通过数据 挖掘更灵活的进行商品促销和优惠活动。 随着信息化在各行各业的日益提高，以及数据挖掘技术的日益成熟和完 善，当前，数据挖掘技术的应用正逐步向更广泛的领域内渗透。如在天文学、 生物学、教育、卫生、医疗、体育等领域，都拥有广阔的发展前景。 第三章分类挖掘规则 第三章分类规则挖掘 数据库中隐藏着许多可以为商业、科研等活动的决策提供所需要的知识 卿。分类与预测是两种数据分析形式，它们可用于抽取能够描述重要数据集 合或预测未来数据趋势的模型。分类方法( c l a s s i f i c a t i o n ) 用于预测数据对 象的离散类别( c a t e g o r i c a ll a b e l ) ；而预测( p r e d i c t i o n ) 则用于预测数据 对象的连续取值。机器学习、专家系统、统计学和神经生物学等领域的研究 人员已经提出了许多具体的分类预测方法。最初的数据挖掘方法大多都是在 这些方法及基于内存基础上所构造的算法。目前数据挖掘方法都要求具有基 于外存以处理大规模数据集合能力且具有可扩展能力。 3 1 分类与估值 3 1 1 分类 分类要解决的问题是为一个事件或对象归类。在使用上，既可以用此模 型分析已有的数据，也可以用它来预测未来的数据。分类的概念是在已有数 据的基础上学会一个分类函数或构造出一个分类模型( 即我们通常所说的分 类器( c 1 a s s i f i e r ) ) 。该函数或模型能够把数据库中的数据记录映射到给定 类别中的某一个，从而可以应用于数据预测。例如，用分类来预测哪些客户 最倾向于对直接邮件推销做出回应，又有哪些客户可能会换他的手机服务提 供商，或在医疗领域当遇到一个病例时用分类来判断一下从哪些药品着手比 较好。分类作为一类重要的数据挖掘问题，可描述如下： 输入数据，或称之为训练集( t r a i n i n gs e t ) ，是由一条条的数据源记录组 成的。一条记录包含若干个属性而组成的一个特征向量。训练集的每条记录 还有一个特定的类标签( c l a s sl a b e l ) 与之对应。该类标签是系统的输入，通 常是以往的一些经验数据。一个具体样本的形式可为样本向量：( v l ， v 2 ，v n ；c ) 。在这里v i ( i - - 1 ，2 ，n ) 表示字段值，c 表示类别。 分类问题还可如下定义：一个有n 个样本的训练集如形式( x ，y ) 给 出，y 是一个离散的类说明，而x 是一个有d 个属性的向量。每个属性可以 是符号表示的，也可以是数值表示的。目标是建立一个模型：y = f ( x ) ，从 而根据将来的x 来高精度的预测y 。 第三章分类挖掘规则 3 1 2 分类器 训练集是构造分类器的基础。标签属性的类型必须是离散的，且标签属 性的可能值的数目越少越好( 最好是两或三个值) 。标签值的数目越少，构 造出来的分类器的错误率越低。通常的分类器有三种：决策树分类器，选择 树分类器和证据分类器。本文主要研究的是决策树分类器。从训练集中自动 地构造出分类器的算法叫做生成器。 3 1 3 估值 估值与分类类似，不同之处在于，分类描述的是离散型变量的输出，而 估值处理的是连续值的输出；分类的类别是确定的数目，估值的量是不确定 的。例如：根据购买模式，估计一个家庭的收入；根据房地产产生收益的模 式估计房地产的价值。 一般来说，估值可以作为分类的前一步工作。首先给定一些输入数据， 通过估值，得到未知的连续变量的值；然后根据预先设定的阈值，进行分类。 例如：银行处理家庭贷款业务，先运用估值，给每个客户记分，然后根据阈 值，将贷款级别分类。 3 2分类的目的与应用 分类的目的：预测资料所属的类别( c l a s sl a b e l ) 、分析影响资料归类的因 素；分类的应用：信用额度核准( 例如：根据预测的信用等级决定核卡额度) 、 目标行销( 例如：找出会购买笔记本型电脑的顾客属性) 、医疗诊断( 根据 病人症状判断其是否罹患s a r s ) 。 3 3 分类方法与步骤 3 3 1 分类方法 常用的数据分类方法有：决策树归纳、贝叶斯分类、贝叶斯信念网络、 k - 最近邻法、神经网络、基于示例学习法、遗传算法等。 第三章分类挖掘规则 3 3 2 分类的一般步骤 1 模型的创建 对一个类别已经确定的模型创建模型，每一条记录都属于一个确定的类 别，我们用类标签，记录属性类别。用于创建模型的数据集叫训练集。模型 可以用分类规则、决策树，或者数学方程的形式表达。 2 模型使用 用创建的模型预测未来或者类型未知的记录，估计模型的准确率，使用 创建的模型在一个测试集上进行预测，并将结果和实际值进行比较，以评估 模型的准确性。用于测试模型的数据集叫测试集。在比较时须注意测试集和 训练集是独立的。 3 4 分类规则挖掘的应用 例如，银行可以构造一个分类模型来对客户进行信用等级评估( 普通或 优良) ；可以构造一个客户跳槽模型，将客户划分成两类：忠诚客户和跳槽 客户。分析人员可以根据忠诚客户和跳槽客户的历史数据，构造模型。使用 该模型可帮助公司更好的理解它的客户，更精确的预测客户的去留情况。其 它典型应用诸如：市场调查、疗效诊断、寻找店址等。 第四章决策树方法 4 1 决策树 第四章决策树方法 4 1 1 决策树方法基本原理 决策树是一种常用的监督学习方法啼】。它首先要求选择一个训练样本数 据集，以训练集的一个子集形成一个决策树。若此树没有给所有对象给出一 个正确答案，则将例外情况加入树中，不断重复这一过程直到发现正确的决 定集，最终将形成这样一棵树：每一片叶子表示一个类名，每个枝节描述一 个属性，节点的每一分支对应于该属性的每一个可能取值。 一棵决策树是这样一棵树，如图4 1 所示。树中的每一个元素就是一个 结点，全部是叶结点的树称为纯树。该树的每个非终端点均表示被考察数据 项目的一个测试或决策。根据测试结果，选择某个分支。为了分类一个特定 数据项目，从根结点开始，一直向下判定，直到到达一个叶子结点为止。当 到达一个终端结点时，一个决策便形成了。决策树也可解释成一种特殊形式 的规则集，其特征是规则的层次组织关系。 在决策树中，有两种结点：决策结点和状态结点。由决策结点引出若干 树枝，每个树枝代表一个决策方案，每个方案树枝连接到一个新的结点。这 个新的结点既可能仍是一个新的决策结点，也可能是一个状态结点。每个状 态结点表示一个最终状态。在决策树中，状态结点对应着叶结点。决策树用 于解决分类问题时，决策结点表示待分类对象的属性，每个树枝表示它的一 个可能取值，而状态结点则表示分类结果。决策树算法的技术难点是如何选 择一个好的分支方法进行取值。 决策树方法最大的优点在于它的可理解性和直观性。然而，要成功地用 决策树方法建立数据模型，必须要建立若干个分支。决策树方法也同样存在 数据的缺值处理问题。如果缺少一个数据元素，我们就无法遍历这个元素对 应的数据结点。 第四章决策树方法 4 1 2 决策树算法介绍 图4 - 1 一般决策树结构 决策树有许多算法，其中比较著名的是，1 9 8 6 年j r q u i l a n 在机器 学习( m a c h i n el e a r n i n gj o u r n a l ) 杂志上发表的题为“回归决策树 ( i n d u c t i o no fd e c i s i o nt r e e s ) 的论文中，介绍了一种示例学习方法i d 3 算法3 ，该方法的前身是c l s 方法。c l s 方法的工作过程是：首先找出最 有判断力的因素把数据库划分成多个子集( 对应树的一个分枝) ，构成一个 分枝过程，然后对每个子集递归调用分枝过程，直到所有子集仅包含同一类 型数据为止。最后得到的决策树能对新的例子进行分类。c l s 的不足是它处 理的学习问题不能太大。为此，j r q u i l a n 借用信息论中的互信息( 或称 信息增益，i n f o r m a t i o ng a i n ) 作为属性判断能力的度量，并将建树方法嵌 入一个迭代的外壳中，提出了著名的i d 3 决策树学习算法，通过选择窗口 来形成决策树。其核心思想是首先检验数据库中所有字段，找出具有最大信 息增益g a i n ( a ) 的字段作为决策树的一个结点，再根据字段的不同取值建 立树的分支，对每个子集分支重复建立树的下层结点和分支，直到某一子集 的结果属于同一类。 i d 3 是一个典型的决策树学习系统，它仅对部分搜索空间进行搜索，能 保证找到一个简单而不一定最简化的决策树。它基于信息理论的最大互信息 原则，对数据集进行多极分类确定子树。然而，从示例学习最优化的角度分 析，理想的决策树分为三种：叶子数目最少；叶子节点深度最小；叶 节点数最小且叶子节点深度最小。寻找最优决策树已被证明是最困难的问 第四章决策树方法 题。i d 3 算法试图减少树的平均深度，却忽略了叶子数目的研究。其启发式 函数并未达到最优，存在的主要问题有： 互信息的计算依赖于取值的数目较多的属性，而取值较多的属性不一定 最优； i d 3 是非递增学习算法； i d 3 是单变量决策树( 在分枝节点上仅考虑单个属性) ，许多复杂概念的 表达困难，属性间相互关系强调不够，容易导致决策树中子树的重复或有效 属性在决策树的某一分枝被检验多次； 抗噪性差，训练集中正例与反例的比例很难控制； 针对上述问题，出现了许多较好的改进算法，1 9 9 3 年j r q u il a n 出版 了专著机器学习规则( p r o g r a m sf o rm a c h i n el e a r n i n g ) ，对i d 3 算法 在预测变量的缺失值处理、剪枝技术、派生规则等方面进行了补充和改进， 提出了后来极其流行的c 4 5 决策树算法h 1 。目前还出现了c 4 5 的商业改进 版c 5 0 算法，在大数据情况下的效率和生成规则的数量与正确性方面有了 显著的提高。此外，c h a i d ( c h i - s q u a r ea u t o m a t i ci n t e r a c t i o nd e t e c t i o n ) 算法和c a r t 算法也有相当广泛的应用。 4 1 3 可扩展的决策树算法介绍 前面所介绍的一些算法如i d 3 、c 4 5 和c a r t 等，都假定所有的训练子集 都可以同时存在主存里，因此他们能够学习的样本数就受到了严格的限制。 虽然其有效性已经通过许多小数据集的学习归纳得到了验证，但当采用这些 算法对大规模数据库进行数据挖掘时，其性能就变的很差，于是人们不断提 出了许多有关决策树可扩展性问题的解决算法。其中，代表性的算法s l i q 和s p r i n t 。这两个算法都可以处理符号值和连续值，都采用了对存放在外存 的数据集中的数据预先进行排序，并利用新的数据结构来帮助构造决策树。 它们都是基于硬盘的决策树学习算法，假定所有的样本都存在硬盘上，通过 反复读取来学习它们。可以说，扩展决策树算法为海量数据集设计了一个决 策树学习者。其不足之处就是若数据集大到了硬盘无法容纳程度时，这些方 法将彻底失败。其它还有如：p u b l i c 、r a i n f o r e s t 算法。 s l l 0 算法1 s l i q 算法( s u p e r v is e dl e a r n i n gi nq u e s t ) 是一种快速可伸缩分类器， 它是一个可伸缩的、能够处理大数据集的决策树。其决策树生成分成两个阶 第四章决策树方法 段：树生长阶段和树剪枝阶段，s l i o 算法的一大特点就是对数值性和分类性 属性的分类均适合。 在树生长阶段，s l i q 对于数值型属性是采用预排序技术来评估分支，对 于种类型属性是采用快速划分子类的技术来决定分支，其排序过程结合广度 优先的树生长策略以便能对常驻磁盘的大数据集进行分类，在树剪枝阶段是 基于m d l ( 最小描述长度) 的算法获得分类集。 ( 1 ) s l i q 算法的建树阶段算法如下： m a k e t r e e ( t r a i n i n gd a t at ) p a r t i t i o n ( t ) ： p a r t i t i o n ( d a t as ) i f ( a l lr e c o r d ssa r ei nt h es a m ec a l s s ) t h e nr e t u r n ： e v a l u a t es p lit sf o re a c ha t t r i b u t ea u s et h eb e s ts p l i tt op a r t i t i o nsi n t os 1a n ds 2 ： p a r t i t i o n ( s 1 ) ： p a r t i t i o n ( s 2 ) ： 分支时s l i q 采用二分查找树结构，对每个节点都需要先计算最佳分裂方 案，然后执行分裂。在s l i q 算法中使用g i n i 指标代替信息量，对包含n 个 类的数据集s ，g i n i ( s ) 定义为： g i n i ( s ) = l 一p j p ， 公式( 4 1 ) i l 其中p j 是s 中第j 类数据的相对频率。g i n i 值越小，信息增益 ( i n f o r m a t i o ng a i n ) 越大。信息增益最高的分裂将被作为分裂方案。 ( 2 ) 剪枝阶段 由于训练数据中的“噪声刀影响而造成的错误的分支枝条将导致利用模 型时的分类错误。剪枝就是去除那些导致错误的枝条，在可能的子树中挑选 出错率最小的子树。 s l i q 的剪枝算法m d l ( m i n i m u md e s c r i p t i o nl e n g t h ) 属于迟滞剪枝算 法，m d l 的目标是生成一棵描述长度最小的决策树。m d l 原理认为：最好的 编码模型是描述数据代价最小的模型。如果模型m 对数据集d 进行编码，那 么描述代价为： c o s t ( m ，d ) = c o s t ( dim ) + c o s t ( m )公式( 4 - 2 ) 第四章决策树方法 其中，c o s t ( mid ) 表示用模型m 对数据d 编码的编码代价，c o s t ( m ) 表示描述模型本身所需的编码长度。 由于s l i q 算法具有1 ) 运算速度快，对属性值只作一次排序；2 ) 利用 整个训练集的所有数据，不做取样处理因而不丧失精确度；3 ) 能轻松处理 磁盘常驻的大数据集；4 ) 低代价的m d l 剪枝算法( 5 ) 更快的更小的目标树 等诸多优点，突破了传统分类器的只能处理7 0 0 k b 数据的瓶颈，所以特别适 合在w e b 环境中大容量数据的分析和处理。 s l i q 算法存在的缺点有：( 1 ) 由于需要将类别列表存放于内存，而类别 列表的长度与训练集的长度是相同的，这就一定程度上限制了可以处理的数 据集的大小。( 2 ) 由于采用了预排序技术，而排序算法的复杂度本身并不是 与记录个数成线性关系，因此使得s l i q 算法不可能达到随记录数目增长的线 性可扩展性。 4 2 决策树算法的构造 尽管所有的决策树算法处理数据的方式都很相似，但它们之间最重要的 区别就在于，决定如何根据重要性对不同变量进行分组和排序时，采用不同 的数学算法。 1 从数据源中选取变量。用户从数据源的所有变量中选择一个变量作为 因变量，还有许多类似的输入变量。 ( 1 ) 分析每个对结果产生影响的变量，对每一变量的值进行分组。这是 一个迭代过程。 ( 2 ) 得到基于每一变量的分组之后，就可找到对于因变量来说最具有预 测性的一个变量，并且可以用这个变量来创建决策树的叶子结点。 决策树的构造算法可通过训练集t 完成，其中t = ( ，而x = ( a l ，a 2 ，册) 为一个训练实例，它有n 个属性，分别列于属性表( a 1 ，a 2 ， a n ) 中。其中a j 表示属性a i 的取值。c j c = c i ，c 2 ，c m ) 为x 的分类结果。 从属性表中选择属性a i 作为分类属性；若属性a i 的取值有膨个，则将t 划分 为肌个子集，t l ，t k i ，其中t j = l l ) t ， 且x 的属性取值a 为第i 个值；接下来从属性表中删除属性a i ；对于每一个t i j ( 1 ，k i ) ，令t = t j 力如果属性表非空，返回第一步，否则输出。 训练数据批处理，自顶向下递归构造决策树d t r e e ( e x a m p le s ， a t t r i b u t e s ) i f 所有样本属于同一分类，返回标号为该分类的叶结点 第四章决策树方法 e l s ei f 属性值为空，返回标号为最普遍分类的叶结点 e l s e 选取一个属性，a ，作为根结点 f o ra 的每一个可能的值v i 令e x a m p l e s i 为具有a = v i 的样本子集 从根结点出发增加分支( a = v i ) 如果e x a m p l e s i 为空 则创建标号为最普遍分类的叶结点 否则递归创建子树一一调用d t r e e ( e x a m p l e s i ，a t t r i b u t e s 一 a ) ) 构造好的决策树的关键在于如何选择好的逻辑判断或属性。对于同样一组例 子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较 大概率时，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在 于选择恰当的逻辑判断或属性。 4 30 4 5 算法原理及实现 c 4 5 算法是构造决策树分类器的一种算法，它是i d 3 算法的扩展。i d 3 算法只能处理离散型的描述性属性，而c 4 5 算法还能够处理描述性属性是 连续型的情况。这种算法利用比较各个描述性属性的g a i n 值的大小，来选 择g a i n 值最大的属性进行分类。如果存在连续型的描述性属性，那么首先 要做的是把这些连续型属性的值分成不同的区间，即“离散化一。 1 把连续型属性值“离散化一的具体方法是： ( 1 ) 寻找该连续型属性的最小值，并把它赋值给m i n , 寻找该连续型属性的最大值，并把它赋值给删凰 ( 2 )设置区间【m i n , m a 朋中的个等分断点彳j ，它们分别是 a i ：m i n + m a x - m t n i公式( 4 3 ) n 其邙i = 1 。2 n ( 3 ) 分别计算把j f r 杉f ja i 和( 彳j ，m a x ) ( f = 1 ，2 ，肋作为区间值时的g a i n 值，并进行比较 ( 4 ) 选取g a i n 值最大的a k 做为该连续型属性的断点，把属性值设置 为【m i n , a k 和( a k ，m a x ) 两个区间值。 第四章决策树方法 2 g a i n 信息增益 决策树是建立在信息理论( i n f o r m a t i o nt h e o r y ) 的基础上的，决策树的 方法循环地寻找某一标准，它能够带来与本次分类相关的最大信息。构造好 的决策树的关键在于如何选择适当的属性。对于同样一组记录集，可以有很 多决策树能符合这组记录集。人们研究出，一般情况下，树越小则树的预测 能力越强。要构造尽可能小的决策树，关键在于选择恰当属性。属性选择依 赖于各种对例子子集的不纯度( i m p u r i t y ) 度量方法。不纯度度量方法包括 信息增益( i n f o r m a t i o ng a i n ) 、信息增益比( g a i nr a t i o ) 、g i n i i n d e x 、距离度 量( d i s t a n c em e a s u r e ) 、j - m e a s u r e 、g 统计、x2 统计、证据权重 ( w e i g h to f e v i d e n c e ) 、正交法( o r t o g o n a l i t ym e a s u r e ) 、相关度( r e l e v a n c e ) 和r e l i e f 。不同的度量有不同的效果，特别是对于多值属性。c 4 5 算法使用 信息增益( i n f o r m a t i o ng a i n ) 的概念来构造决策树，其中每个分类的决定都 与前面所选择的目标分类有关。 ( 1 ) 信息理论( i n f o r m a t i o nt h e o r y ) 和熵( e n t r o p y ) 1 9 4 8 年，香农( c e