硕士论文-决策树分类算法的研究及其在教学分析中的应用.pdf

河海大学 硕士学位论文 决策树分类算法的研究及其在教学分析中的应用 姓名 刘军 申请学位级别 硕士 专业 计算机应用技术 指导教师 王志坚 20061201 河海大学硕士研究生毕业论文决策树分类算法的研究及其在教学分析中的应用 摘要 数据挖掘 D a t a M i m n g 又称数据库中的知识发现 是一个从大规模数据库 的数据中抽取有效的 隐含的 以前未知的 有潜在使用价值的信息的过程 它 是当今众多学科领域特别是数据库领域最前沿的研究课题之一 对数据挖掘技术 的研究 国内外已经取得了许多令人瞩目的成就 并成功地应用到了许多领域 在高校的学生管理 教学工作科学化的今天 传统的教学管理手段已逐渐不 能适应社会发展的需求 与此同时 数据挖掘技术的快速发展及其应用领域的不 断扩大使得将数据挖掘技术应用于高校的教学 管理已是必然的趋势 如果以历 届的教学信息库为数据源 利用学生 教师及教材等情况信息 使用数据挖掘技 术发现以上各要素对学生课程成绩影响的强弱 挖掘结果将可用于合理的设置教 学方案 一般情况下 可将数据挖掘算法分成分类和预测 聚类分析 关联规则挖掘 等几种 其中决策树分类算法是其中最重要最常用的技术之一 也是目前研究的 热点问题 基于以上情况 本文做了如下工作 1 对各种决策树分类算法进行了详细介绍 研究了每种算法的主要优缺点 2 以学生课程成绩与教学要求 教材选用 教师情况和学生情况之间的关 系为前提 利用决策树分类算法I D 3 的传统实现途径开发了学生成绩分析系统 3 在认真分析传统实现方法所存在的问题后 提出了改进的实现途径C A S P C l m 曲i n gA l g o r i t h mO nS e r v e rP r o c e d u r e 并也将其实际应用于学生成绩分析 系统 和传统的实现方式相比 通过理论分析和实际数据测试 证明了改进的实 现方法C A S P 较好地解决了I D 3 算法实现中的空间复杂度和计算复杂度等问题 在系统设计方面 采用了模型 视图 控制器M V C M o d e l V i e w C o n t r o l l e r 的 设计模式 利用V B N E T 及S Q LS e r v e r2 0 0 0 数据库进行了实现 系统分为两个 部分 数据训练和数据预测 在数据训练部分 首先对教学历史数据 训练集 进行清洗 连续数据离散化 之后通过挖掘系统生成决策树和形成相应的规则 在数据预测部分 对需要预测的数据按规则测试 给出测试可视化界面和预测结 果 实践证明 此系统可以为教学质量分析和教学课程安排提供重要的依据 关键词数据挖掘算法 决策树算法 分类 分析和预测 河海大学硕士研究生毕业论文决策树分类算法的研究及其在教学分析中的应用 A b s t r a c t T h eD a t aM i n i n gi sa l s oc a l l e dt h ek n o w l e d g ed e t e c t i o nf r o mt h ed a t a b a s e w h i c h i st h ep r o c e s so f e x t r a c t i n gv a l i d i m p l i c i t u n k n o w n 1 a t e n ti n f o r m a t i o nf r o mt h el a r g e s c a l eo fd a t a b a s e I ti so n eo ft h er e s e a r c ht o p i c si nm a n ys e i e n t i t l ea r e a st o o e s p e c i a l l yi nt h ed a t a b a s er e a l m n 圮r e s e a r c ho fD a t aM i n i n gh a sr c a c h e ds i g n i f i c a n t a c h i e v e m e n ta n dh a sb e e na p p l i e dS U C C E S S f u l l yi nm a n ya r e a s H o w e v e r S u c c e s s f u l a p p l i c a t i o no f D a t aM i r l i n gi nt h ef i e l do f e d u c a t i o nh a sn o tb e e nr e p o r t e d W i t hm o r ea n dm o r es c i e n t i f i ew a y su s e di nt h es t u d e n t sm a n a g e m e n ta n d t e a c h i n gp r a c t i c e t h et r a d i t i o n a lm e a n sh a v ea l r e a d Yc a l l tf u l f i l lt h en e e do f t h es o c i a l d e v e l o p m e n t s B u ti f w eu s et h es u c c e s s i v eg r a d ed a t a b a s eo fs t u d e n t sa sd a t as o u r c e a n dm a k eu s eo f t h ed a t am i n i n gt e c h n i q u e st od i s c o v e rh o wt e a c h e r s s t u d e n t sa n d t e x t b o o k si n f o r m a t i o n si n f l u e n c et h es t u d e n t sg r a d e t h e nw ec a ne s t a b l i s h t h em a s o n a b l et e a c h i n gp r o j e c t sa c c o r d i n gt ot h ea b o v ed a t am i n i n gr e s u l t s U n d e rg e n e r a ls i t u a t i o n t h ea l g o r i t h mo fD a t aM i n i n gc a nb ed i v i d e di n t ot h e c l a s s i f i c a t i o na n dp r e d i c t i o n t h eg a t h e rk i n d s t h ea n a l y s i sa n dt h ec o n n e c t i o n r u l e sm i n i n g e t c A m o n gt h o s e t h ec l a s s i f i e a t i o no nd e c i s i o nt r e e si so n eo ft h e m o s ti m p o r t a n ta n dc o m m o nt e c h n i q u e s w h i c hi sa l s oah o t s p o ts t u d yc u r r e n t l y A c c o r d i n gt ot h ea b o v ec o n d i t i o n s t h ea r t i c l eh a sd o n et h ef o U o w i n gr e s e a r c h 1 R e s e a r c ht h ev a r i O U Sd e c i s i o nt r e ea l g o r i t h m sa n da n a l y z et h em a i nt e c h n i q u e c h a r a c t e r i s t i c so f e a c ha l g o r i t h m 2 B a s e do nt h er e l a t i o n s h i p so f s t u d e n t s g r a d ea n dt e a c h i n gr c q u e s Lt h ec h o i c eo f t e x t b o o k s t h ec i r c u m s t a n c eo ft h et e a c h e r sa n dt h es t u d e n t s t h ea u t h o rm a k eu s eo f t h et r a d i t i o n a lr e a l i z a t i o nm e t h o do fI D 3t oc a r r yo u tt h eg r a d ea n a l y t i c a ls y s t e m 3 W 1 l i l ea n a l y z m gt h et r a d i t i o n a lr e a l i z a t i o nm e t h o d sd e f e c tc a r e f u l l y t h i sa r t i c l e p u tf o r w a r da ni m p r o v e dr e a l i z a t i o nm e t h o dC A S P C l a s s i f y i n gA l g o r i t h mo nS e r v e r P r o c e d u r e w h i c hi sa l s oa p p l i e dt ot h eg r a d ea n a l y t i c a ls y s t e m C o m p a r i n gw i t ht h e t r a d i t i o n a lr e a l i z a t i o nm e t h o d t h r o u g ht h e 也e o r ya n a l y s i sa n dt h ea c t u a ld a t at e s t s t h ei m p r o v e dr e a l i z a t i o nm e t h o dC A S Pi sp r o v e dt or e d u c et h em e m o r ya n d c a l c u l a t i o nc o m p l i c a t i o n s I nt h eg r a d e a n a l y t i c a ls y s t e md e s i g n t h e a u t h o r a d o p t t h em o d e lo f M C fM o d e l V i e w C o n t r o l l e r a n du s eV B N E Ta n dS Q LS e r v e r2 0 0 0t or e a l i z e T h es y s t e mi sd i v i d e di n t ot w op a r t s d a t at r a i n i n ga n dd a t ap r e d i c t i n g T h et r a i n i n g p a r ti su s e dt oc l e a nt h et e a c h i n gh i s t o r yd a t a s t r a i n i n gr e c o r d s e t d i s p e r s et h e c o n s e c u t i v ed a t a sa n dt h e nf o r mt h ed e c i s i o nt r e e sa n dt h er u l e st h r o u g ht h ed e c i s i o n t r e e sa l g o r i t h m 1 h cp r e d i c t i n gp a r ti st ot e s tt h ec u r r e n td a t a sb yt h er u l e s g i v ea v i s u a li n t e r f a c ef o rt h et e s ta n dp r e d i c tr e s u l t s T h r o u g ht h ep r a c t i c e t h i ss y s t e mC a l l p r o v i d et h ei m p o r t a n tb a s i sf o rt e a c h i n ga n a l y s i sa n dc u r r i c u l u n la r r a n g e m e n t K e y w o r d st h eD a t aM i n m i n gA l g o r i t h m D e c i s i o nT r e eA l g o r i t h m C l a s s i f i c a t i o n A n a l y s i sa n dP r e d i c t i o n I I 学位论文独创性声明 本人所呈交的学位论文是我个人在导师指导下进行的研究工作 及取得的研究成果 尽我所知 除了文中特别加以标注和致谢的地方 外 论文中不包含其他人已经发表或撰写过的研究成果 与我一同工 作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意 如不实 本人负全部责任 论文作者c 签孙立雌彻6 年阳伊 学位论文使用授权说明 河海大学 中国科学技术信息研究所 国家图书馆 中国学术期 刊 光盘版 电子杂志社有权保留本人所送交学位论文的复印件或电 子文档 可以采用影印 缩印或其他复制手段保存论文 本人电子文 档的内容和纸质论文的内容相一致 除在保密期内的保密论文外 允 许论文被查阅和借阅 论文全部或部分内容的公布 包括刊登 授权河 海大学研究生院办理 黼椭孙五恽中纠圳驹 河海大学硕士研究生毕业论文 决策树分类算法的研究及其在教学分析中的应用 1 1 论文背景 第一章绪论 数据挖掘技术目前被认为具有令人兴奋的研究前景 它有着广泛的应用价 值 在企业应用领域 用于支持企业关键性决策 市场策略的制定等等 在国外 数据挖掘在大型商业 金融业 保险业等大型企业都开始得到应用 在商业方面 数据挖掘技术可以增强企业的竞争优势 缩短销售周期 降低生产成本 有助于 制定市场计划和销售策略 并已经成为电子商务中的关键技术 由于数据挖掘在 开发信息资源方面的优越性 已逐步推广到保险 医疗 制造业和电信等各个行 业的应用 但数据挖掘技术在教育层面上的应用还只能算是新生事物 处于发展 的初级阶段 近年来 随着教育事业的飞速发展 特别是高等教育的快速发展 教育管理 信息化 现代化水平有了长足的进步 各高校在M I S M a n a g e m e n t I n f o r m a t i o n S y s t e m 管理信息系统 方面已取得了可喜的成绩 如大部分高校都 在使用学生成绩管理系统 学籍管理系统 学生奖惩考评管理系统 高校人事管 理系统 高校教材管理系统 高校学生就业管理系统等 这些系统的成功实旋为 各高校的日常管理工作带来了很大的便利 提高了管理效率和水平 在日常的工 作中也积累了越来越多的数据 目前的这些数据库系统虽然基本上都可以实现数 据的录入 修改 统计 查询等功能 但这些数据所隐藏的价值并没有被充分挖 掘和利用 信息浪费比较严重 随着数据挖掘技术的成熟及应用领域的不断扩展 不少高校研究人员己经开 始研究将数据挖掘技术应用于高校的教学管理中 例如 将数据挖掘技术应用于 学生信息管理 高校的教学评估 学生成绩分析及考试系统中 将对提高学校教 学水平起到很好的指导作用 数据挖掘技术也可以为教育管理决策系统提供技术 支持 例如 通过挖掘分析某所著名大学的学生能力特征和教学特点 以及这两 者之间的关系 教育决策部门可以根据得到的挖掘结果考虑是否向其它大学推广 这所大学的教学特点 以期培养出大致相同能力特征的学生 数据挖掘在这种教 学经验归纳以及推广应用中有重要的作用 河海大学硕士研究生毕业论文决策树分类算法的研究及其在教学分析中的应用 1 2 数据挖掘在教育领域中的应用 目前各高校大都在学籍管理 成绩管理 师资管理等方面积累了大量的数据 资源 数据挖掘技术则可以利用这些数据资源解决高校教育领域中存在的诸多决 策问题 例如根据现有的教师资源情况 合理的预测将来一段时间教师资源的变 化情况 为学科建设和师资队伍建设提供决策依据 根据现有的学生成绩进行更 高层次的分析 为各级领导部门提供切实可行的提高教学质量 优化教学资源的 依据 对学生的就业情况进行数据挖掘 找到提高学生就业率的相应规律 并及 时科学的调整专业设置的方法等 总之 在目前高校扩招 学生就业压力大增的 情况下 数据挖掘的结果可以为各高校提供适应时代发展 合理配置高校资源以 加速其自身发展的重要方法 可以为高校管理者提供科学的决策依据 成为管理 决策支持系统中不可缺少的重要工具 当前 数据挖掘在教育领域中的应用主要体现在以下几个方面 1 在教学管理系统中的应用 将基于多维频繁谓词的多维关联规则数据 挖掘技术运用到教学管理系统中 建立一个教学管理关联规则挖掘系统 对学生 特征进行维间关联规则挖掘 通过挖掘系统可以得到许多有价值的信息 这些信 息在帮助学校更好地进行学生的培养 掌握学生表现情况 帮助教师备课以及安 排课程等方面具有重要的指导意义 2 在题库研究中的应用 随着教育改革的进一步深入 计算机应用的普 及 高校题库系统得到了越来越广泛的应用 高校题库系统主要包括组卷 考试 评卷以及试卷分析等几大部分 担负着考核学生水平 考察教师综合素质的重要 作用 对教学工作的开展有着非常重要的现实意义 纵观以往的题库管理系统 多半都以难易度 区分度等为主要衡量指标 以组成一套合理的试卷为目的 考 察学生的知识掌握水平 但是这些题库系统普遍缺乏综合分析 辅助决策的能力 并且对其历史积累的海量信息中隐含知识的利用无能为力 针对上述问题可以采 用数据挖掘中的聚类分析方法挖掘出隐藏在历史数据中的一些模式和知识 合理 组织题库以全面考察学生的学习水平和教师教学的综合素质 3 在高校教学质量评估中的应用 通过对具体院校学生的评教数据和部 分教师的档案数据进行数据挖掘 利用决策树 关联规则等挖掘算法挖掘影响教 学质量的关键因素 并对挖掘结果进行分析 验证其有效性后可以客观的评估教 2 河海大学硕士研究生毕业论文决策树分类算法的研究及其在教学分析中的应用 师的教学质量 4 在远程教学系统中的应用 针对远程教育中存在的教学质量问题 采 用数据挖掘方法对远程教育过程中积累的历史数据 W e b 日志等 进行分析和 挖掘 产生出有利于改进远程教学质量和服务水平的知识 从而为教师 学生和 远程教学管理人员服务 5 在分层次教学研究中的应用 将数据挖掘技术和现代教育统计学中有 关技术相结合 可以为实际教学活动提供决策指导 研究主要以数据挖掘技术中 关联规则发现的相关理论为基础 运用经典教育统计理论对教育活动中的分层次 教学实例进行分析 通过对教学活动中的各影响因素进行数据挖掘 从而发现影 响教学结果的关联规则 并将数据挖掘的预测结果反馈到新的教学活动中 为实 际教学活动提供决策指导 1 3 论文的主妻研究内容及工作 本课题的主要工作是研究如何将数据挖掘技术与教务管理信息系统相结合 从海量数据中提取出隐藏在数据之中的知识和模式 以使信息系统的功能得到最 大程度的利用 课题结合已有的技术和环境 主要做了如下工作 1 首先从理论上研究数据挖掘和教务管理信息系统结合的必要性和可行 性 其次结合学校教务管理部门信息资源的现状 利用决策树方法对教学信息库 中的数据 包括学生基本信息 课程信息 学生成绩信息 教师信息 教材信息 等 进行分析 找出影响学生课程成绩的因素及各因素间的关系 以便于在班级 排课时 对教师的配备和教材的选用进行指导 使学生能够保持良好的学习状态 从而促使更好地开展教学工作 提高教学质量 2 本文详细分析了常用的决策树生成算法I D 3 C 4 5 及基于最小G I N I 指标的S L I Q 算法和基于数据库技术的分类算法 重点研究了决策树挖掘算法 选用决策树作为本文研究重点的原因是它能够直观体现教学数据的特点 具有较 好的分类预测能力 而且可视化的决策树便于理解和提取决策规则 本文在分析 上述算法的基础上 对经典的决策树分类算法I D 3 的实现途径进行了改进 优化 的实现途径只在应用程序端存放挖掘数据的结构 而实际挖掘工作则由S Q L S e r v e r 端的相应存储过程来完成 以此构建高效的具有良好可扩展性的分类器 河海大学硕士研究生毕业论文决策树分类算法的研究及其在教学分析中的应用 经分析比较 改进后的实现途径可以将构建分类器所需的统计数据通过关系数据 库管理系统计算得到 避免了应用程序对训练集的多次顺序扫描和大量的数据传 送 提高了分类系统与数据库系统的集成度 同时也提高了算法的执行速度 大 大降低了算法执行时的空间复杂度 改进的实现途径具有随元组个数增长和随属 性个数增长两方面的良好的可扩展性 3 基于决策树分类算法的学生成绩分析系统的实现 本文将传统的决策 树生成技术和改进的实现途径C A S P C l a s s i f y i n g A l g o r i t h mo nS e r v e rP r o c e d u r e 相结合 建立成绩评估模型和根据模型形成I F T H E N 规则 并以产生的规则来 分析预测学生今后的成绩情况以指导教学 该系统基于W i n d o w s X P 操作系统 用V B N E T 实现 后台支持为S Q LS e r v e r2 0 0 0 数据库管理系统 考虑到挖掘算 法比较及数据源选择的需要 在参考了S Q L S e r v e r 2 0 0 0 A n a l y s i sS e r v i c e s 的图形 化方法后 本系统的模块采用分级对话可视化方法实现 在编程方面主要采用了 以下技术 A D O 数据库应用 在实现途径的改进中 利用A D O 中的C o m m a n c l 对象 调用S Q LS e r v e r 存储过程 实现了应用程序调用S Q LS e r v e r 存储过程的 方法 在传统的决策树生成算法中 采用A D O D B R e c o r d s e t 数据集过滤方法 高效地解决了属性个数的统计问题 采用M SC o m p o n e n tO L E D B 中的D a t a L i n k s 组件 解决了数据源的选取 具有较好的灵活性 采用T r e e V i e w 控件 实现决 策树的可视化以及数据表和属性的选取 4 河海大学硕士研究生毕业论文 决策树分类算法的研究及其在教学分析中的应用 第二章数据挖掘基本理论知识 1 数据挖掘的定义及研究背景 随着数据库技术的成熟和数据应用的普及 人类积累的数据量正在以指数速 度迅速增长 特别是进入九十年代以来 伴随着因特网 I n t e m e t 的出现和发展 展现在人们面前的是浩瀚无垠的信息海洋 虽然目前的数据库系统可以高效地实 现数据的录入 查询 统计等功能 但无法发现数据中潜在的关系和规则 无法 根据现有的数据预测未来的发展趋势 于是 一个新的挑战被提了出来 如何从 信息的汪洋大海中及时发现有用的知识 提高信息利用率呢 面对 人们被数据 淹没 人们却饥饿于知识 的挑战 从数据库中发现知识 K n o w l e d g eD i s c o v e r yi n D a t a b a s e s 及其核心技术 数据挖掘 D a t aM i n i n g 便应运而生 并得以蓬勃 发展 越来越显示出其强大的生命力 数据挖掘是从大量的 不完全的 有噪声的 模糊的 随机的实际应用数据 中 提取隐含在其中的 人们事先不知道的 但又是潜在有用的知识的过程 从 广义角度上讲 数据 信息是知识的表现形式 但在数据挖掘中更多把概念 规 则 模式 规律和约束等看作知识 原始数据可以是结构化的 如关系型数据库 中的数据 也可以是半结构化的 如文本 图形 图像数据 甚至是分布在网络 上的异构型数据 发现知识的方法可以是数学的或非数学的 演绎的或归纳的 发现的知识可以被用于信息管理 查询优化 决策支持 过程控制等 总之 数 据挖掘是一门广义的交叉学科 它的发展和应用涉及到不同的学科 尤其是数据 库 人工智能 数理统计 可视化 并行计算等领域 数据挖掘技术被认为是数据库和人工智能领域中研究 开发和应用最活跃的 分支之一 许多数据挖掘系统已经成功地应用于零售业 银行业 市场营销 电 信业 保险业 医疗等领域 世界上比较有影响的典型的数据挖掘系统有 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 具有典型数据集自动生成 关联发现 序列规律发现 概 念性分类和可视化显示等功能 可以自动实现数据选择 数据转换 数据挖掘和 河海大学硕士研究生毕业论文 决策树分类算法的研究及其在教学分析中的应用 结果显示 必要时重复这一过程 S o l u t i o n 公司的C l e m e n t i n e 提供了一个可视 化的快速建模环境 由数据获取 挖掘 整理 建模和报告等部分组成 A n g o s s 公司的K n o w l e d g eS E E K E R 是一个基于决策树的数据分析程序 具有相当完整 的分类树分析功能 国内从事数据挖掘研究的人员一般集中在大学 研究所和公 司 对数据挖掘进行研讨的大型刊物主要有 软件学报 计算机学报 模式 识别 等 主要从事算法和数据挖掘理论方面的研究 复旦大学 南京大学 西 安交通大学 东南大学 国防科大等单位已经在挖掘算法效率改进等方面做了不 少的工作 在具体应用方面 中科院计算所智能处理开放实验室的史忠植教授等 人设计了一个数据挖掘工具M S M i n e r 它是一种多策略知识发现平台 使用决 策树算法为广东地税提供纳税人异常情况检测 复旦德门公司开发的天眼数据挖 掘工具D m i n e r 集成了多种数据挖掘算法 取得了较好的挖掘效果 2 2 数据挖掘的步骤 数据挖掘的过程可粗略地分为 问题定义 数据收集和预处理 数据挖掘算 法执行以及结果的解释和评估 1 问题定义 数据挖掘的目的是为了在大量数据中发现有用的令人感兴 趣的信息 因此发现何种知识就成为整个过程中第一个也是最重要的一个阶段 在问题定义过程中 数据挖掘人员必须和领域专家以及最终用户紧密协作 一方 面明确实际工作对数据挖掘的要求 另一方面通过对各种挖掘算法的对比进而确 定可用的算法 后续的挖掘算法选择和数据集准备都是在此基础上进行的 2 数据收集和数据预处理 包括数据选取 数据预处理和数据变换三个 步骤 数据选取的目的是确定挖掘任务的操作对象 即目标数据 它是根据用户 的需要从原始数据库中抽取的一组数据 数据预处理一般可能包括消除噪声 推 导计算缺值数据 消除重复记录 完成数据类型转换等 当数据开采的对象是数 据仓库时 一般来说 数据预处理已经在生成数据仓库时完成了 数据变换的主 要目的是消减数据维数或降维 即从初始特征中找出真正有用的特征以减少数据 开采时要考虑的特征或变量个数 3 数据挖掘 数据挖掘算法执行阶段首先根据对问题的定义明确挖掘的 任务或目的 如数据总结 分类 聚类 关联规则发现或序列模式发现等 确定 河海大学硕士研究生毕业论文决策树分类算法的研究及其在教学分析中的应用 了挖掘任务后 就要决定使用什么样的挖掘算法 同样的任务可以用不同的算法 来实现 选择挖掘算法有两个考虑因素 一是不同的数据有不同的特点 因此需 要用与之相关的算法来挖掘 二是用户或实际运行系统的要求 有的用户可能希 望获取描述型的 容易理解的知识 而有的用户或系统的目的是获取预测准确度 尽可能高的预测型知识 4 结果的解释和评价 数据挖掘阶段发现出来的模式 经过评估 可能 存在冗余或无关的模式 这时需要将其剔除 也有可能模式不满足用户要求 这 时则需要将整个发现过程回退到前一阶段 如重新选取数据 采用新的数据变换 方法 设定新的参数值 甚至换一种算法等 另外 K D D 由于最终是面向人类 用户的 因此可能要对发现的模式进行可视化 或者把结果转换为用户易懂的另 一种表示 如把分类决策树转换为 I f t h e n 规则 数据挖掘算法执行仅仅是整个挖掘过程中的一个步骤 挖掘质量的好坏有两 个影响因素 一是所采用的数据挖掘技术的有效性 二是用于挖掘的数据的质量 和数量 如果选择了错误的数据或不适当的属性 或对数据进行了不适当的转换 则挖掘的结果是不会好的 可视化在整个数据挖掘的各个阶段都扮演着重要的角色 特别是在数据准备 阶段 用户可能要使用散点图 直方图等统计可视化技术来显示有关数据 以期 对数据有一个初步的了解 从而为更好地选取数据打下基础 在挖掘阶段 用户 则要使用与领域问题有关的可视化工具 在表示结果阶段 则还需要用到可视化 技术以使得发现的知识更易于理解 2 3 数据挖掘的目标和任务 数据挖掘的目标和任务主要有关联分析 聚类分析 分类 预测 时序模式 等 现分别对各种任务介绍如下 1 关联分析 A s s o c i a t i o nA n a l y s i s 两个或两个以上数据项的取值之间存在某种规律性 就称为关联 可以建立 起这些数据项的关联规则 数据关联是数据库中存在的一类重要的 可被发现的 知识 它反映一个事件和其他事件之间的依赖或关联 如果两项或多项属性之间 存在关联 那么其中一项的属性值就可以依据其他属性值进行预测 河海大学硕士研究生毕业论文决策树分类算法的研究及其在教学分析中的应用 例如 买面包的顾客中9 0 还买牛奶 这就是一条关联规则 在商场中将这 两样物品摆放在一起销售 将会提高销售量 在大型数据库中 这样的关联规则可以产生很多 这就需要进行筛选 一般 用 支持度 和 可信度 两个阈值来淘汰那些无用的关联规则 2 聚类分析 C l u s t e r i n g 聚类是把数据按照它们的相似性归纳成若干类别 同一类别中的数据距离较 小 彼此相似 不同类别中的数据距离较大 彼此相异 聚类分析可以建立宏观 的概念 发现数据的分布模式以及可能的数据属性之间的相互关系 聚类方法包括统计分析方法 机器学习方法和神经网络方法等 在统计分析 方法中 聚类分析是基于距离的聚类 这种聚类分析方法是一种基于全局比较的 聚类 它需要考察所有的个体才能决定类的划分 在机器学习方法中 聚类是无 指导的学习 此时距离是根据概念的描述来确定的 又称为概念聚类 在神经网 络中 般利用自组织神经网络方法进行聚类 如A R T 模型 K o h o n e n 模型等 这是一种无监督学习方法 当给定距离闽值后 各样本按阈值进行聚类 3 分类 C l a s s i f i c a t i o n 分类是数据挖掘中应用得最多的任务 分类就是找出一个类别的概念描述 并用这种描述来构造模型 一般用规则或决策树模式表示 类别的概念描述代 表着这类数据的整体信息 也就是该类的内涵描述 分为特征描述和辨别性描述 特征描述是对类中对象的共同特征的描述 辨别性描述是对两个或多个类之间的 区别的描述 分类的过程是 利用有关分类算法分析输入数据 寻找训练集中的数据所表 现出来的特性 为每个类找到 种准确的描述或者模型 并使用这种类的描述对 未来的测试数据进行预测分类 4 预测 P r e d i c a t i o n 预测是利用历史数据找出变化规律 建立模型 并由此模型对未来数据的种 类及特征进行预测 典型的预测方法是回归分析 即利用大量的历史数据 以时 间为变量建立线性或非线性回归方程 预测时 只要输入任意的时间值 通过回 归方程就可求出该时间的状态 近年来 发展起来的神经网络方法 如B P 模型 实现了非线性样本的学 习 能进行非线性函数的判别 分类也能进行预测 但分类一般用于离散数值 河海大学硕士研究生毕业论文决策树分类算法的研究及其在教学分析中的应用 回归预测用于连续数值 神经网络方法预测既可以用于连续数值 也可以用于离 散数值 5 时序模式 T i m e S e r i e sP a t t e m 时序模式是指通过时间序列搜索出重复发生概率较高的模式 与回归一样 它也是用已知的数据预测未来的值 但这些数据的区别是变量所处时间的不同 在时序模式中 需要找出在某个最小时间内出现比率一直高于某一最小百分 比 最小支持度阈值 的规则 这些规则会随着形势的变化作适当的调整 时序 模式中 一个有重要影响的方法是 相似时序 该方法能够按时问顺序查看时 间事件数据库 从中找出另一个或多个相似的时序事件 在实际挖掘中 分类模式和回归模式使用最为普遍 但通常是多种模式相结 合使用 分类模式 回归模式 时间序列模式属于受监督知识 可以直接用来检 测模式的准确性 一般在建立这些模式时 使用一部分数据作为样本 利用另外 一部分数据来检验 校正模式 聚类模式 关联模式则是非监督知识 因为在模 式建立前结果是未知的 模式的产生不受任何监督 2 4 数据挖掘的技术和算法概述 数据挖掘的方法通常可以分为两大类 一类是统计型 常用的技术有概率分 析 相关性 聚类分析和判别分析等 另一类是人工智能中的机器学习型 通过 训练和学习大量的样品集得出需要的模式或参数 由于各种方法都有自身的功能 特点以及应用领域 数据挖掘技术的选择将影响最后结果的质量和效果 通常是 将多种技术结合使用 形成优势互补 下面对数据挖掘中常用的决策树和神经网 络等几种技术方法进行深入讨论 包括技术的基本思想 优势与缺点和主要应用 领域 决策树 决策树主要是对基于数据的属性值进行归纳分类 常用于分类的层 次方法有 i f t h e n 规则 决策树方法的最大优点就是可理解性强 比较直观 其缺点是处理复杂性的数据时 分支数目非常多 管理起来难度很大 同时 还 存在数据的缺值处理等问题 其算法有I D 3 C 4 5 C A R T 和C H A I D 等 目前 出现的两种新算法S L I Q 和S P R I N T 可以对非常大的训练集进行决策树归纳 还 可以处理离散型属性和连续值属性 河海大学硕士研究生毕业论文决策树分类算法的研究及其在教学分析中的应用 遗传算法 遗传算法是一种全新的最佳化空间搜寻法 其最初概念是由J o h n H o l l a n d 于1 9 7 5 年提出 是一种基于生物进化理论的技术 基本观点是 适者生 存 在数据挖掘中 常把任务表示成一种搜索问题 利用遗传算法强大的搜索 能力找到最优解 具体做法是模仿生物进化的过程 通过进行选择 交叉和变异 遗传操作 直至满足最优解 遗传算法已经在优化计算和分类机器学习方面显示 出了明显的优势 贝叶斯网络 贝叶斯网络基于后验概率的贝叶斯定理 是建立在对数据进行 统计处理基础上的方法 它将不确定事件通过网络连接起来 可以对相关事件的 结果进行预测 其网络变量可以是可见的 也可以隐藏在训练样本中 贝叶斯网 络具有分类 聚类 预测和因果关系分析的功能 其优点是易于理解 预测效果 较好 缺点是对发生频率很低的事件预测效果不好 在医学和制造业等领域的应 用具有较好的效果 粗糙集 粗糙集理论是波兰P a w l a k 教授在1 9 8 2 年提出的 是一种新的数学 工具 这一方法在数据挖掘中具有重要的作用 常用于处理含糊性和不确定性的 问题 发现不准确数据或噪声数据内在的结构联系 也可以用于特征归约和相关 分析 其主要优点是不需要任何关于数据的初始的或附加的信息 因此广泛应用 于不确定 不完整的信息分类和信息获取 神经网络 神经网络是最常用的数据挖掘技术之一 最早由心理学家和神经 生物学家提出 它类似于人类大脑重复学习的方法 先给出一系列的样本进行学 习和训练 从而产生能够区别各种样本的不同特征和模式 样本集应该尽量具有 代表性 通过成千上万次的训练和学习后 系统将最终得出潜在的规则和模式 当它遇到新的样本数据时 系统就会根据训练结果自动进行预测和分类 其最大 的缺点是难于理解 即无法解释如何得出结果和使用了什么规则 此外 它还需 要很长的训练时间和大量的参数数据 该算法的优点是对复杂问题能够进行很好 的预测 对噪声数据的承受能力比较强 对未经训练的数据具有较好的分类能力 神经网络可细分为前馈式 反馈式和自组织神经网络 具有优化计算 聚类和预 测等功能 在商业界已得到广泛应用 金融市场采用神经网络建立信用卡和货币 交易模型 用于识别信贷客户 股票预测和证券市场分析等方面 河海大学硕士研究生毕业论文 决策树分类算法的研究及其在教学分析中的应用 3 1 引言 第三章决策树分类算法的研究 人类认识事物的过程是从分类开始的 分类能力是人类智能的基础 在从大 规模数据库获得知识的过程中必然涉及到数据的分类问题 分类是数据挖掘中的 一项非常重要的任务 目前在商业领域应用的最多 也一直是K D D 领域的研究热 点之一 分类的主要目标是提出一个分类模型 或分类器 所得的这个分类模 型能够将数据库中的数据项映射到给定类别中的某一个 3 2 数据分类 数据挖掘的核心算法主要有统计分析方法 神经元网络方法 分类方法 遗 传算法等 其中分类方法是数据挖掘应用领域中的重要技术之一 其描述如下 1 1 1 1 0 分类对象 输入数据或称训练集 T r a i n i n gS e t 是由一条条的数据库记录 R e c o r d 组成的 每一条记录包含若干属性 A t t r i b u t e 组成一个特征向量 训练集的每条记录还有一个特定的类标签 C l a s sL a b e l 与之对应 该类标签也 是系统的输入 一个具体的样本形式可以表示为样本向量 v l v 2 v n c 在这里v i 表示属性值 c 表示类别 分类目的 通过分析训练集中的数据所表现出来的特性 为每一个类别找到 一种准确的描述或者模型 这种描述常常用谓词来表示 并利用这些模型对未 来的测试数据进行分类 分类的评价方法或比较尺度 1 预测准确度 用得最多的一种比较尺度 特别是对于预测型分类任务 2 计算复杂度 依赖于具体的实现细节和硬件环境 在数据挖掘中 由 于操作对象是海量数据库 因此空间和时间的复杂度将是非常关键的问题 3 模型描述的简洁度 对于描述型的分类任务 模型描述越简洁越好 如采用规则表示的分类器就更有用 而神经网络方法产生的结果往往难以理解 河海大学硕士研究生毕业论文决策树分类算法的研究及其在教学分析中的应用 3 3 决策树分类简介 决策树方法自2 0 世纪6 0 年代以来 在分类 预测 规则提取等领域有着广 泛的应用 特别是Q u i l a n 于1 9 8 6 年提出I D 3 算法以后 在机器学习 知识发现 领域得到了进一步的应用及巨大的发展 决策树是一种树状结构 它的每一个树 结点可以是叶结点 对应着某一类 树结点也可以对应着一个划分 将该结点对 应的样本集划分成若干个子集 每个子集对应一个结点 对于一个分类问题或规 则学习问题 决策树的生成是一个从上至下 分而治之的过程 决策树从根结点 开始 对数据样本进行测试 根据不同的结果将数据样本划分成不同的样本子集 每个样本子集构成一个子结点 对每个子结点再进行划分 生成新的子结点 不 断反复 直至达到特定的终止准则 生成的决策树每个叶结点对应 个分类 对 于生成的决策树 可以从根结点开始 由上至下 提取规则 也可以对新的数据 集进行分类或预测 对一个样本进行分类时 从树的根结点开始 根据每个结点 对应的划分将其归到相应的子结点 直至叶结点 叶结点所对应的类别就是该样 本对应的分类 下面是构造决策树的一般性描述 1 开始时是 个训练集和空树 接下去对当前结点应用该结点的测试将 其划分 2 如果所有的当前结点的训练样本属于同一个类别 创建一个带有该类 的标签的叶子结点并停止 3 否则 使用最优测量 g o o d n e s sm e a s u r e 计算每一个集合的每一个可能 的划分 4 选择最优划分作为当前结点的测试 创建与该划分的不同输出同样多 的子结点 5 使用该划分的输出标注父亲和儿子之间的边并使用该划分把训练数据 划分到子结点中 6 把子结点作为当前结点 循环进行2 5 步骤 直到不存在可以划分的 结点为止 基于决策树的分类模型以其特有的优点广为人们采用 首先 决策树方法结 构简单 容易生成便于人们理解的规则 其次 决策树模型效率高 对训练集数 河海大学硕士研究生毕业论文 决策树分类算法的研究及其在教学分析中的应用 据量较大的情况较为适合 再者 决策树算法的计算量相对来说不是很大 然后 决策树方法通常不需要受训数据外的知识 擅长处理非数值型数据 最后 决策 树方法具有较高的分类精确度 它是在数据库的各个对象中找出共同特性 并按 照分类模型将它们进行分类 决策树分类操作通常有以下两个步骤 第一步 根据给定的训练集 找到合适的映射函数H f 一c 的表示模型 这一部通常称为模型训练阶段 第二步 使用上一步训练完成的函数模型预测数据的类别 或利用该函数模 型 对数据集中的每一类数据进行描述 形成分类规则 决策树分类算法通常分为两个阶段 决策树的生成 B u i l d i n g 和决策树的 修剪 P r u n i n g 本论文主要探讨决策树的生成算法 3 4 决策树生成算法研究 3 4 1I D 3 算法 假设T 为训练集 为T 构造决策树时根据信息增益 i n f o r m a t i o ng a i n 的值 选择分裂属性 并根据分裂属性值的个数n 将T 分成n 个子集 若第i 个子集 砸含有的元组类别一致 该结点就成为决策树的叶子结点而停止分裂 而对于不 满足此条件的T 的其它子集 按照上述方法继续分裂直至所有子集所含元组都属 于同一个类别或达到待定的终止准则为止 算法描述如下f 3 4 1 1 3 7 1 1 3 3 1 I D 3 T r e ef T T a t t r i b u t e l i s 0 其中T 为样本空间