（计算机软件与理论专业论文）数据挖掘在高校招生中的研究与应用.pdf

上海师范大学硕士学位论文 摘要 摘要 数据挖掘技术从产生以来，己经被应用于多种领域，并得到了充分的验证， 显示了其重要的经济和社会价值。 随着高等教育的迅速发展，高校新生进校成绩的差异增大。高校如何在招生 时对学生进行有效的筛选以及进校后如何对学生进行管理，已成为各高校面临的 一个问题。 本文深入分析了数据挖掘技术与高校信息的特点，阐述了该技术应用于高校 招生和高校管理中的可行性必要性以及实施的思路。在研究了a p r i o r i 和c 4 5 数 据挖掘算法的基础上，对上述两算法进行了有效地改进，并基于改进的算法实现 了高校招生分析系统。本文做的工作主要表现在以下几个方面： ( 1 ) 提出了把数据挖掘技术应用于高校招生工作和高校管理工作的思想，分 析了该应用的可行性与必要性； ( 2 ) 把数据挖掘技术的特点与高校信息的特点相结合，建立了适用于高校管 理和高校招生的数据挖掘模型： ( 3 ) 有效地改进了a p r i o r i 算法和c 4 5 算法，在a p r i o r i 算法上提出了交集理 论，减少了程序访问数据库的次数；对c 4 5 算法的改进是引进了推进技术。提高 了分类精确度。 ( 4 ) 基于改进的a p r i o r i 和c 4 5 算法实现了高校招生分析系统，挖掘出高校 招生决策规则集，为高校招生和管理工作提供了决策支持。 关键词：高校招生，数据挖掘，关联规则，决策树，熵 第1 页 上海师范大学硕士学位论文 摘要 a b s t r a c t d a t a m i n i n gh a sb e e nf u l l yv e r i f i e dw h i l ei ta p p l y i n gi nm a n yf i e l d s s i n c ei tc o m ei n t ob e i n g ，s h o w i n gi t si m p o r t a n te c o n o m i ca n ds o c i a lv a l u e w i t ht h ef a s td e v e l o p m e n to fc h i n e s eh i g h e re d u c a t i o n ，t h ed i f f e r e n c e o fc 0 1 l e g ef r e sh i i l e np e r f o r m a n c ei si n c r e a s i n g h o wt oe n r o l la n dh o wt o m a n a g es t u d e n t sa f t e rt h e yc o m ei n t os c h 0 0 1i sap r o b l e mw h i c hc o l l e g e i sf a c i n g i nt h i sp a p e r ，t h ed a t a m i n i n gt e c h n o l o g ya n dt h ec h a r a c t e r i s t i c so f c o l l e g ei n f o r m a t i o nw a sd e e p l ya n a l y s i s e d i tp r o p o s e dt h en e c e s s i t yt h a t d a t a m i n i n gu s e di nu n i v e r s i t yi n f o r m a t i o n t h ep a p e ri sa d v a n c e di nt h e f o l l o w i n ga s p e c t s ： f i r s to fa 1 1 ，t h ei d e ao fa p p l y i n gd a t a m i n i n gt e c h n o l o g yt op r o g r e s s u n i v e r s i t i e s m a n a g e m e n tw a sb r o u g h tf o r w a r d ，a n dt h ef e a s i b i l i t yo ft h i s i d e aw a sa n a l y z e d ： s e c o n d l y ，a ni n t e g r a t e dd a t a m i n i n gm o d e lw a sf o u n do nt h eb a s eo f a n a l y z i n gd a t a m i n i n gt e c h n o l o g ya n du n i v e r s i t i e s s t a t u sg e n e r a l l y ： t h i r d l y ，a p r i o r i8 1 9 0 r i t h ma n dc 4 。5a l g o r i t h mw a r ei m p r o v e d u s et h e i n t e r s e c t i o nt h e o r ya n dp r o p u l s i o nt e c h n o l o g y f i n a l l y ，a n a l y s i so ft h ec 0 1 l e g ee n t r a n c es y s t e mw a si m p l e m e n t e d ，i t r e t u r nm i n i n gr u l e ss e ta n dp r o v i d eam a n a g e m e n td e c i s i o n m a k i n gs u p p o r t k e y w o r d s ：c o l l e g ee n r o l l m e n t ，d a t a m i n i n g ，a s s o c i a t i o nr u l e s ，d e c i s i o n t r e e ，e n t r o p y 第1 i 页 上海师范大学硕士学位论文论文独创性声明和使用授权声明 论文独创性声明 本论文是我个人在导师的指导下进行的研究工作及取得的研究成果。论文中 除了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研 究成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并 表示了谢意。 名：渺 论文使用授权声明 吼勰鼎叫切 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅，学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 6 0 名枷 导师签名：琶参轧 日期：枷r 户功p 上海师范大学硕士学位论文第一章绪论 第一章绪论 1 1 论文的研究背景和意义 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数 据越来越多。如何从激增的数据背后找到有价值的信息，并从中提取出知识内容 已经成为目前数据挖掘和知识管理等研究领域的重要课题。而数据挖掘技术 ( d a t am i n i n g ) 正是解决这一课题的重要方法。权威的g a r t n e r 调查组报告显示， 数据挖掘将是今后几年全球范围内重点投资研究的十大新技术之一，它引起了学 术界和工业界的广泛关注，是当今数据库系统研究和应用领域内的一个热点问 题。 1 1 1 数据挖掘技术及其研究现状 所谓数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息 和知识的过程。特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不 仅是面向特定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃 至宏观的统计、分析、综合和推理，以指导实际问题的求解，企图发现事件问的 相互关联，甚至利用已有的数据对未来的活动进行预测。 根据信息存储格式，用于数据挖掘的对象包括关系数据库、面向对象数据库、 数据仓库、文本数据源、多媒体数据库、空间数据库、时态数据库、异质数据库 以及i n t e r n e t 等。常用的数据挖掘算法大致有统计方法、机器学习方法、神经网 络方法和数据库方法。统计方法又可细分为：回归分析( 多元回归、自回归等) 、 判别分析( 贝叶斯判别、费歇尔判别、非参数判别等) 、聚类分析( 系统聚类、 动态聚类等) 、探索性分析( 主元分析法、相关分析法等) 、以及模糊集、粗糙 集、支持向量机等。机器学习可细分为：归纳学习方法( 决策树、规则归纳等) 、 基于范例的推理c b r 、遗传算法、贝叶斯信念网络等。神经网络方法可细分为： 前向神经网络( b p 算法等) 、自组织神经网络( 自组织特征映射、竞争学习等) 等。数据库方法主要是基于可视化的多维数据分析或o l a p 方法，另外还有面向属 上海师范大学硕士学位论文第一章绪论 性的归纳方法。可见，数据挖掘是一门广义的交叉学科，它汇聚了不同领域的研 究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和 工程技术人员。数据挖掘的工具集分为数据预处理、数据采掘和数据评价3 大主 要模块。如下所示： ( 1 ) 数据预处理：负责对挖掘的数据源作必要的准备指定需要使用的数据集 的名称及位置，利用随机取样、等距取样、分层取样、顺序取样或分类取样的方 法对获取的数据取样。通过数据筛选去掉不希望包括进来的观测值，最后将数据 进行某种转换操作，转换后的值作为新的变量存放在样本数据中。 ( 2 ) 数据采掘：即对经过预处理的数据进行挖掘，先建立一个数据挖掘的数 据库( d m d b ) ，放置此次要进行操作的数据，同时进行一些诸如变量最大、最小、 平均、标准差等预处理，为数据挖掘建立一个良好的工作环境，然后利用聚类算 法进行数据挖掘。 ( 3 ) 数据评价：即用一种通用的数据挖掘评价的架构来比较不同模型的效 果，预报各种不同类型分析工具的结果，在进行各种比较和预报的评价之后，给 出一系列标准的图表，供用户进行定量评价。 作为一门新兴的交叉学科，数据挖掘涉及到很多学科领域。在国外，数据 挖掘的研究已有二十多年的历史，理论体系较为成熟，并已有相应的软件产品应 用于各行各业，取得了显著的效果。总的来说，对数据挖掘的研究经历了如下四 个阶段： ( 1 ) 第一代数据挖掘系统：支持一个或少数几个数据挖掘算法，数据一次调 到内存进行处理，典型如s a l f o r ds y s t e m s 公司早期的c a r t 系统。 ( 2 ) 第二代数据挖掘系统：集成数据库管理系统，支持数据库和数据仓库， 具有好的扩展性，典型如d b m i n e r ，能通过d m q l 挖掘语言进行操作。 ( 3 ) 第三代数据挖掘系统：数据挖掘系统生成的预言模型能在操作型环境中 充分使用，能够挖掘网络环境下的分布式和高度异质的数据。 ( 4 ) 第四代数据挖掘系统：将数据挖掘和移动计算相结合，可以挖掘嵌入式 系统、移动系统、和计算设备产生各种类型数据。 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉 及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关 2 上海师范大学硕士学位论文 第一章绪论 数据挖掘理论方面的研究。目前进行的大多数研究项目是由政府资助进行的，如 国家自然科学基金、8 6 3 计划、九五“计划 等。 国外数据挖掘的发展趋势其研究方面主要有：对知识发现方法的研究进一步 发展，如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高；传 统的统计学回归法在k d d 中的应用；k d d 与数据库的紧密结合。在应用方面包括： k 叻商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是孤立 的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。国外很多计 算机公司非常重视数据挖掘的开发应用，i b m 和微软都成立了相应的研究中心进 行这方面的工作，此外，一些公司的相关软件也开始在国内销售，如p 1 a t i n u m ， b o 以及i b m 。 在2 1 世纪，数据挖掘的研究焦点可能会集中到以下几个方面： ( 1 ) 研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形 式化和标准化； ( 2 ) 寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用户理 解且能操纵它，也便于在知识发现过程中的人机交互，使数据挖掘过程成为用户 业务流程的一部分：它包括数据用户化呈现与交互操纵两部分； ( 3 ) 研究在网络环境下的数据挖掘技术，特别是在i n t e r n e t 上建立d m k d 服务 器，与数据库服务器配合，实现数据挖掘； ( 4 ) 融合各种异构数据的挖掘技术，加强对各种非结构化数据的挖掘，如文 本数据、图形图像数据、多媒体数据、空间数据库等。 ( 5 ) 数据挖掘理论与算法研究。经过十几年的研究，数据挖掘已经在继承和 发展相关基础学科( 如机器学习、统计学等) 方面取得了可喜的进步与成果，探索 出了许多独具特色的理论体系。一方面，在这些大的理论框架下有许多面向实际 应用目标的挖掘理论等待探索和创新。另一方面，随着数据挖掘技术本身和相关 技术的发展，新的挖掘理论的诞生是必然的，而且可能对特定的应用产生推动作 用。新理论的发展必然促进新的挖掘算法的产生。 经过十几年的研究和实践，数据挖掘技术已经成为了一个独具特色的研究分 支。但是，这决不意味着挖掘理论的探索已经结束，恰恰相反它留给了研究者丰 富的理论课题。一方面，在这些大的理论框架下有许多面向实际应用目标的挖掘 3 上海师范大学硕士学位论文第一章绪论 理论等待探索和创新。另一方面，随着数据挖掘技术本身和相关技术的发展，新 的挖掘理论的诞生是必然的，而且可能对特定的应用产生推动作用。新理论的发 展必然促进新的挖掘算法的产生，这些算法可能扩展挖掘的有效性，如针对数据 挖掘的某些阶段、某些数据类型、大容量源数据集等更有效；可能提高挖掘的精 度或效率；可能融合特定的应用目标，如c r m 、电子商务等。因此，对数据挖掘 理论和算法的探讨将是长期而艰巨的任务。 1 1 2 论文的研究意义 数据挖掘技术从产生以来，己经被应用于多种领域，并得到了充分的验证， 显示了其重要的经济价值，同时在应用过程中得到不断的完善和进步。迄今为止， 数据挖掘在财务系统、电信行业、零售业、卫生保健行业和生物医学以及科学和 工程等领域都得到了应用并且都有相应成熟的挖掘系统形成，对这些领域做出了 很大贡献。虽然数据挖掘可以用于多种行业，但是数据挖掘在不同行业中的应用 并不具备通用性，即数据挖掘的应用必须与各行业本身的特点相结合，建立行业 专门的挖掘系统。 随着中国高等教育从以往的精英型培养到现在的大众型培养的转变，接受高 等教育的人数激增，由此产生的在校生信息量随之倍增。而且现行的高考制度和 高校管理制度在某种程度上有一定的弊端，教育决策者们一直都在致力于高考和 高校制度的改革。 任何一项制度的改革或者决策的制定都要以事实和数据为依据。高校的发展 无关其规模和资金投入，关键是教育质量。教育质量的高低大部分取决与学生专 业的掌握程度。所以，高校要提高自己的教育质量，首先要在招生中对学生有充 分的了解，同时结合高校自身的特点，把二者相结合来制定相应的招生策略，把 合适相关专业学习的学生招进来，然后对招进来的学生因材施教，才能形成具有 自身特色的教育体制。 而且，学校在国家统一分配招生名额的基础上，可以享有一定的招生自主权。 学校只有充分了解学生的各方面特点，才能根据自己掌握的信息在进行招生时充 分利用自己的招生自主权力。 4 上海师范大学硕士学位论文第一章绪论 另外，在学生数据量剧增以及教育目标日趋复杂的情况下，人工分析学生数 据是不现实的，借助数据挖掘工具对大量学生数据进行深层次分析，可以挖掘出 学生各项数据中隐藏的重要信息。 综合以上分析，把数据挖掘技术应用于高校招生中有很大的现实意义，而目 前数据挖掘在高校招生中还没有完整的挖掘系统可以使用。本课题把数据挖掘应 用于高校教育中，实现一个用于高校招生的数据挖掘系统。 1 2 论文的主要内容 本课题在详细分析数据挖掘理论和技术的基础上，结合高等学校招生的实际 情况，提出了把数据挖掘技术应用于高校招生分析中。在对数据挖掘的各项技术 和算法分析的情况下，考虑高校学生数据的实际特点，采用基于关联规则和决策 树的数据挖掘技术( 即：改进的a p r i o r i 算法和c 4 5 算法) 在w i n d 傩s 环境下对系统 进行了实现，挖掘了学生入学信息与大学期间的成绩信息存在的有价值信息以及 建立了一个高校招生模型。为高校招生和教育管理工作提供了有价值的参考信 息。 1 3 论文的章节安排 第一章绪论，主要介绍论文的研究背景、课题的意义，以及本论文的内容 及设计方法； 第二章数据准备，主要介绍数据挖掘进行之前对数据进行选择和预处理的 步骤和方法： 第三章数据挖掘模型与算法改进，主要介绍数据挖掘模型功能、数据挖掘 的过程等、以及挖掘算法的分析与改进； 第四章高校招生挖掘系统的设计，主要介绍系统的设计思想、数据的处理、 系统使用的挖掘过程模型以及主要的数据结构； 第五章实验结果分析，主要介绍对挖掘的结果进行说明与分析； 第六章总结和展望，主要介绍几个重要结论，同时总结本文的创新点和将 来的研究方向。 上海师范大学硕士学位论文第二章数据准备 2 1 数据选择 第二章数据准备 数据选择是数据挖掘操作进行的第一步，是在对系统进行正确理解和认识的 基础上进行的，数据选择的目的是对挖掘的原始数据进行初步地约简。在确定数 据挖掘的业务对象后，对所有与业务对象有关的内部和外部数据进行搜索，选择 出适合于数据挖掘应用的数据，完成数据选择。 2 1 1 数据选择的必要性 数据选择是对数据挖掘中所用到的数据进行的第一次缩减。因为数据库中的 数据量一般来说都非常大，涵盖的范围也比较广，有些数据表中的数据和挖掘系 统之间可能没有任何关系。如果不把这些无用数据筛选掉，那么它们也会参与挖 掘过程，这样不仅造成资源浪费，更重要的是会挖掘结果造成负面影响，因为即 使完全不相关的数据也可以挖掘出相应的“规律 ，而这些规律除了会对判断造 成障碍以外，没有其他实际价值和意义。数据选择就是根据对工程的理解，从大 量的现有数据中选择适合工程挖掘需要的数据，作为挖掘操作的对象。 2 1 2 数据选择的方法 在进行数据选择时，要根据业务对象的实际需要，分析清楚哪些数据是数据 挖掘中比较重要的数据元。在数据量非常大的情况下，完全由人来进行选取是不 现实的。一般在信息量非常大的时候都采取人机结合的方式。由人来选择较高概 念层次上的数据类别，而通过预先编制好的程序来选择数据库中具体的数据表 格。 2 1 3 数据选择的步骤 6 数据选择操作一般包括以下3 步： ( 1 ) 数据表选择； 上海师范大学硕士学位论文 第二章数据准备 ( 2 ) 数据表中的属性选择： ( 3 ) 多个数据表中的属性整理和统一。 这里的数据选择是最初意义上数据选择，在数据集成到数据集中以后还有同 样的选择操作。在数据选择中，对其中第( 1 ) 、( 2 ) 步是根据工程需要和工作者对 工程的理解进行数据的初始化约简。第( 3 ) 步要把选择出的数据表中的属性进行 统一。比如：两个班级的学生综合成绩表，班级( 1 ) 中存在字段：学习成绩，班 级( 2 ) 中存在字段：智力成绩。这两个字段表达同一个意义，但是有不同的字段 名。如果不进行统一，这些数据就无法进行集成生成挖掘需要的数据集。 2 2 数据预处理 数据预处理在数据挖掘中起着非常重要的作用。数据预处理的结果数据是进 行数据挖掘的对象，其质量直接影响到数据挖掘的效果。本章主要介绍数据挖掘 中数据预处理的工作过程和预处理过程中使用到的相关方法和技术。 数据预处理一般包括以下几个步骤： ( 1 ) 数据清理； ( 2 ) 数据集成； ( 3 ) 数据规约。 数据准备( 包括数据选择和数据预处理) 的过程如图2 1 所示： 图2 1 数据准备的步骤 上海师范大学硕士学位论文第二章数据准备 2 2 1 数据清理 数据清理是数据预处理中的第一步。在该步骤中，对经过初步筛选的数据进 行进一步处理。因为经过初步筛选后的数据中还存在很多缺陷，或者说这些数据 是脏数据。而在脏数据的基础上是不可能建立一个良好的挖掘模型的。数据清理 一般包括缺失值处理、噪声数据处理、异常数据处理、重复数据检查以及数据的 有效性验证等。清理过的数据放入数据集市中以备集成使用。 对不同的数据缺陷，数据清理一般分别采用如下的方法进行处理： ( 1 ) 缺失值的处理 忽略元组：该方法在一个元组中有多个属性值都空缺时采用，即把该元组 删除不计。该方法实现简单，但只能在特殊情况下使用。 填补：分手工填补和自动填补。 手工填补实现起来比较困难。特别是在数据量比较大，缺失值也较多时，填 补起来费时费力。 自动填补分下面几种： 用全局常量进行填补； 用属性的平均值进行填补； 用同类元组的属性平均值进行填补； 用出现概率最大的值进行填补。 推测：用回归分析、判定树、贝叶斯形式化方法等推导工具，对其他元组 中的值进行分析推导，根据推导结果对缺失的属性值进行预测。该方法由于使用 现有的数据对缺失值进行推测，更好地保存了数据之间的联系。 以上三种方法的缺点就是所使用的替代值都可能造成偏差。最优的方法是用 所有可能的值对缺失值替代，生成多种数据挖掘解决方案，然后对其合理性分别 进行分析和解释。但是这种方法需要付出很大代价。 ( 2 ) 噪声数据的处理 一般来说，测量一个变量时存在的偏差称为噪音。偏差较大时，就成为孤立 点。处理噪声数据一般采用平滑技术。该技术有以下几种方法实现： 分箱：首先把数据属性值进行分段( 箱) ，对每一段分别进行平滑。分箱是 一种局部平滑技术。 r 上海师范大学硕士学位论文 第二章数据准备 聚类：可以通过把近似数据进行聚集，识别出数据集合中无类可归的孤立 点( 又称异常点) 。对异常点的处理要特别谨慎，有些异常点是错误的，而有些异 常点是正确的，正确的异常点中隐藏着一些特殊的有用的信息。比如学生成绩： 如果一个学生的某科成绩( 百分制) 大于1 0 0 或者小于。那么该异常点就是一定错 误的；而对于一个人的年龄，如果大于1 2 0 ，那么该值相对于大多数数据来说是 异常的，该数据可能是错误的，但也有可能是正确的，如果是正确的，那么该异 常点就具有很重要的意义，其中包含了很有价值的信息。 回归：根据现有的数据，归纳出一个普遍适应的回归函数，利用该函数对 所有的元组进行测量，找出与回归函数偏差较大的噪声数据，进行相应的平滑处 理。 ( 3 ) 冗余数据处理 这里的冗余数据指的是数据表中存在的重复的元组以及同一数据集市里的 数据表之间存在的重复数据现象。 2 2 2 数据集成 数据经过清洗后，根据不同的来源，放入不同的数据集市。不同数据集市里 的数据一般情况下是不一致的。而数据挖掘的对象必须是一个紧密偶合的数据 集，因此就要对不同的数据集市进行集成，把其中的数据结合成一个新的实体即 数据集中。 数据集成过程中主要解决的问题有数据冗余、实体不一致性、数据值冲突。 ( 1 ) 数据冗余 在集成阶段要处理的冗余数据指的主要是不同数据集市之间存在的重复元 组和重复的数据表，在集成操作进行时要把这些重复数据删除，以保证数据挖掘 操作所用的数据集中的数据的唯一性。 ( 2 ) 不同数据集市中实体不一致性 在数据选择阶段己经对同一个数据集市中的不同数据表中的属性不一致性 进行了解决，在数据集成阶段要进行的是同种性质的工作，只是要进行一致化的 是不同数据集市中的相同意义的属性名。 ( 3 ) 数据值冲突 9 上海师范大学硕士学位论文第二章数据准备 数据值冲突产生的原因是来自不同数据集市的数据对于数值的规定可能不尽相 同。例如不同的学校对学生的成绩值的规定，有些采用百分制，有些采用五级制 等。在数据集成时必须把这些冲突的数据值进行统一。 2 2 3 数据规约 数据规约是继数据选择之后对数据进行的第二次缩减。数据的规约一般包含 从三个方面进行：行规约、列规约和数值规约。行规约是把数据表从行的数量上 进行缩减，列规约即维度规约，使数据表从属性上进行删除或合并。数值规约是 对某个属性的值的数量进行缩减。数据归约的目的是减少数据量和提高挖掘结果 的质量，其中提高数据挖掘结果的质量是规约的主要日的。 ( 1 ) 数值规约 数值规约就是对元组的某个属性的值进行约简，使得属性的值的数量尽可能 的少。数值规约一般从两个方面进行：数据泛化和连续数据离散化。 数据泛化 数据泛化针对的是无序型数据，是把初始数据值从更高的层次上进行抽象和 概括，选择替代的、较小的数据表示形式来代替原有的数据值，以达到减少数据 值的数量的目的。未经泛化的数据值一般数量比较多，过于细化，不具有高度代 表性，进行挖掘时很难挖掘出其中隐藏的有价值的信息。例如：对于“职业 中 的美术、音乐、摄影等等，这些可以经过泛化，归入“艺术 类；而其中的餐饮、 家政等行业，都可以经过泛化概括归入“服务 类中。如此一层一层概括，逐步 约简数据集中属性值的个数。图2 2 说明了数据泛化的层次概括。 l o 图2 2 数据泛化的层次概括 f ig2 2l a y e r so fd a t a g e n e r a liz e 上海师范大学硕士学位论文 第二章数据准备 在本系统中的学生数据中，需要进行泛化的属性主要是学生信息表中父母职 业和文化程度以及高中毕业学校的档次。 因为进行泛化的操作和实际业务紧密联系，需要工作者根据实际业务需求进 行泛化的定义和概括，确定泛化所要概括的层次或高度；实际替代时利用程序来 实现。 根据被泛化属性的性质不同在进行泛化处理时选择不同的操作方式，一般包 括两种：有参方法和无参方法。 有参方法就是在进行泛化时根据实际需求确定一个模型来对数据进行评估， 设定若干个参数，把数据集中的相应属性值用参数代替，代替后的数据与原数据 只有意义上的关联，而在表象上不存在关联。上面的关于职业的例子采取的就是 有参规约方法。 无参方法包括聚类、直方图、选样等实现技术。 连续数据离散化 对非连续性数据的数值规约采用的是泛化的技术，对于连续型数据进行规约 采用的是离散化技术。离散化要执行的操作就是把原本没有明确分割界限的连续 数据划分成少量的区间，使得每个元组的相应属性值都能落入某个区间中，再把 每个区间映射到一个特定的离散符号。 离散化操作分两个步骤进行： 第一步：分割区间的确定 第二步：对分割完成后生成的有限个数的区间的表述 其中第一步是离散化过程的关键步骤。现有的数据离散化技术大致分为非监 督离散化和监督离散化。监督和非监督是相对于输出类来说的。如果在离散化的 过程中仅仅考虑待离散的属性值，而不考虑待离散的属性值和元组的输出类之间 的关系，这种离散化称为非监督离散化，否则就称为监督离散化。非监督离散化 方法包括等距离划分、等频度划分等：监督离散化技术包括自然划分法、信息熵 方法、检验法和贝叶斯决策法等。非监督离散化方法实现简单，但是因为在进行 离散化时未考虑离散属性值与决策属性值之间的关系，因此离散的效果差于监督 离散化方法。 上海师范大学硕士学位论文第二章数据准备 等距离和等频度划分方法主要是基于统计基础的，等距离划分法是按照数据 值之间的间隔宽度进行区间划分，等频度是按照每个区间的数据元组个数相等进 行划分。这些方法实现起来也比较简单，这里不做详细介绍。 自动离散化技术充分考虑了离散属性和决策属性之间的关系，并以此为依据 结合相应的数学和统计工具实现连续数据的离散化。例如2 0 世纪9 0 年代中期， n g u y e n 和s k o w r o n 在粗糙集理论和布尔推理的基础上，提出一种全局有监督的离 散化算法，简称n s 算法；其他的还有层次聚类离散化方法、基于熵的离散化方法 等等。 ( 2 ) 属性规约 数值规约的对象是数据集中元组的某个属性的值，是从数值的角度对数据进 行处理。在数据集市被集成为数据集之后，根据实际的挖掘特性，某些属性可能 是不必要的，即冗余的属性。这些属性对挖掘结果没有帮助，甚至会影响挖掘的 效果和效率。对于这种情况，就要对数据集进行属性规约，也称特征规约。 属性规约是从列的角度对数据集进行化简。对属性进行规约主要基于挖掘执 行时间、挖掘结果的描述精度以及挖掘模型的描述精度等几个方面的考虑。理想 的情况是属性规约以后既能减少挖掘执行时间又能提高分类的精度，同时可以简 化描述。 属性规约的策略及方法 属性规约从广义上包括特征提取( f e a t u r ee x t r a c t i o n ) 和特征选择 ( f e a t u r es e l e c t i o n ) 。特征提取是把原属性集中的属性按照等级进行重新排序， 即把等级高的属性排在最前面；特征选择是构造一个新的属性子集，新的属性子 集中的各个属性之间是平等关系。 特征提取中，对于属性的等级高低可以从不同方面进行衡量，包括数据一致 性、信息内容、样本之间的距离和特征之间的最终统计相关性等等。这种方法可 以分析出各个属性之间的相关性，但是不会找出一个属性子集。这方面的算法包 括主成分分析、分类相关成分、投影寻踪法等。 特征选择就是从原始属性集中找出一个属性子集，该子集要尽可能的小，但 是与原始属性集的挖掘精度没有太大的差别甚至要优于原始属性集的挖掘精度。 下面对特征选择进行详细说明。 上海师范大学硕士学位论文第二章数据准备 属性选择的执行过程 特征选择即从原始属性集合中选出一个对现实系统来说尽可能最优化的属 性子集。该属性子集的选择过程是一个反复的过程，在这个反复的过程中主要需 要解决几个方面的问题：第一，新的属性子集的产生方法；第二，新的属性子集 和原最优属性子集之间的性能优劣的评价；第三，新子集停止产生的条件。 以信息熵为测评标准进行属性选择 在i d 3 和c 4 5 算法中。信息熵是对事物不确定性的一个量度指标。熵值越大 表示事物不确定性高，熵值小表示事物纯净度高。信息熵标准用来处理连续型数 据时是对数据进行积分运算，这会增大计算量，一般情况下先对连续型数据进行 离散化处理。再进行熵计算。 对于数据集s ，根据决策属性值把s 分成n 个不相交的子集，其中s 中样本个数 为isi ，各个不相交的子集中的样本个数分别为js 1j ，is 2l ，is n l ，p i 是第i 个子集( 即第i 类) 占全集的比例，即p i = js i j is l ，则集合s 的信息熵见式( 2 1 ) 蜘( s ) 一罗何9 2 ) ) ( 2 一1 ) 符 考虑s 按照属性x 进行分区，若属性x 有k 个属性值，则x 把s 分为k 个不相交的 子集。每个子集分别为s x 。s x 。s x 。，则每个子集的信息熵见式( 2 2 ) ： 蛾( s ) 自一善( 1 跚i ) 事蜘) ( 2 2 ) 属性x 的信息增益值见式( 2 3 ) ： g a i n ( x )= i n f o ( s ) 一i n f o 。( s ) ( 2 3 ) 如表2 1 所示，x 和y 是两个分类属性，z 为决策属性。对表2 1 所示的数据表 进行简单离散化，得到表2 2 ，再利用信息增益的标准进行评估。 表2 1 属性选择实例表 t a b 】e2 1t a b 】ef o rd is c r e t e c h a r a c t e r s e 】e c t jo n 1 3 上海师范大学硕士学位论文 第二章数据准备 表2 2 属性选择实例表 t a b l e2 2t a b l ef o rd i s c r e t e c h a r a c t e r s e l e c t i o n 按照决策属性z ，根据公式( 2 1 ) ，( 2 2 ) ，( 2 3 ) 计算数据集的信息熵及各个 属性的信息增益： i n f o ( s ) = 一( 3 6 ) 木l o g 。( 3 6 ) 一( 3 6 ) 木l o g ：( 3 6 ) = 1 i n f o 。( s ) = 一o 5 木( ( 一( 1 3 ) ：i c l 0 9 2 ( 1 3 ) ) + ( 一( 2 3 ) 水l o g ：( 2 3 ) ) ) 木2 = 0 9 1 8 l i n f o ，( s ) = 一o 5 木( 一l 木l 0 9 2 1 ) 一o 5 半( 一1 ：l c l 0 9 2 1 ) = o g a i n 。( s ) = 卜0 9 1 8 l = o 0 9 g a i n ，( s ) = 1 属性y 的信息增益值大于属性x 的增益值，在进行约简时，可以把属性x 约简 掉。这里特别强调的是，信息增益标准适用于离散型数据值，所以对于连续型的 属性值，用信息增益标准进行分析时需要先将其进行离散化处理。 1 4 上海师范大学硕士学位论文第三章数据挖掘模型与算法改进 第三章数据挖掘模型与算法改进 数据预处理之后，生成挖掘需要的数据集。下面的工作就是进行挖掘操作。 作为数据挖掘系统的主体部分，挖掘操作过程中要用到多种理论和技术。 挖掘操作主要分以下几个步骤进行： ( 1 ) 挖掘模型建立 ( 2 ) 挖掘方法选择 ( 3 ) 挖掘算法确定 ( 4 ) 执行挖掘操作 ( 5 ) 挖掘结果输出 ( 6 ) 挖掘结果测试 3 1 挖掘过程模型建立 在进行数据挖掘之前，要根据工程的实际特性搭建一个合理的挖掘过程模 型。挖掘过程模型是在理论和经验的基础上建立的，其性能只有在挖掘操作结束 后，根据实际的数据挖掘结果进行模型验证。 数据挖掘模型的建立要从对数据的分析开始。针对选定的挖掘算法，将数据 转化成一个分析模型。建立的分析模型是否适合挖掘算法对挖掘能否成功起着关 键的作用。 数据挖掘模型主要分两种，一种是f a y y a d 总结出的过程模型，以下称为 f a y y a d 过程模型：另一种是遵循c r i s p d m 标准的过程模型，本文称其为c r i s p d m 过程模型。 本节对这两种挖掘模型进行简单说明。 3 1 1f a y y a d 数据挖掘过程模型 f a y y a d 数据挖掘模型的执行流程如图3 1 所示。 f a y y a d 过程模型偏向于技术方面。从图中可以看出，该过程模型的执行分 以下几个部分： ( 1 ) 数据预处理：包括数据清洗、数据集成、数据选择、数据变换几个步骤； 1 5 上海师范大学硕士学位论文第三章数据挖掘模型与算法改进 ( 2 ) 数据挖掘：这是知识挖掘的一个基本步骤，其作用就是利用智能方法挖 掘数据模式或规律知识； ( 3 ) 模式评估：根据一定评估标准从挖掘结果中筛选出有意义的模式知识； ( 4 ) 知识表示：利用可视化和知识表示技术，向用户展示挖掘出的相关知识。 图3 1f a y y a d 挖掘模型过程 f i g3 1f a y y a dd a t a m i n i n gm o d e l 根据f a y y a d 的数据挖掘过程模型，数据挖掘可以理解为一个循环迭代过程， 该模型从数据入手，到知识结束。 f a y y a d 过程模型存在的两个比较大的问题是： ( 1 ) 因为模型从数据入手，在过程模型中对系统本身的认识和对数据的理解 没有反映出来。而在数据挖掘中对工程的认识和理解是非常重要的，它代表着方 1 6 上海师范大学硕士学位论文第三章数据挖掘模型与算法改进 向的正误：对于数据的理解如果有偏差，在数据选择时所选择的数据对挖掘过程 和结果会产生很大影响； ( 2 ) 因为模型结束于知识，所以对于得到的知识如何使用，该模型没有作任 何反映。而对于挖掘结果的应用是一个系统中非常重要的部分。 3 1 2c r i s p d m 过程模型 c r i s p d m ( c r o s s i n d u s t r yp r o c e s sf o rd a t am i n in g ) ，即交叉行业数据 挖掘过程标准。1 9 9 6 年d a i m l e r c h r y s l e r ，s p s s ，n c r 三个公司发起建立一个社团 创建tc r i s p d ms p e c i a li n t e r e s tg r o u p ( 简称为s i g ) 在1 9 9 9 年，s i g 组织开发 并提炼出c r i s p d m ( c r o s s i n d u s t r ys t a n d a r d p r o c e s sf o rd a t am i n i n g ) ，同 时在m e r c e d e s b e n z 和o h r a ( 保险领域) 企业进行了大规模数据挖掘项目的实际试 用。图3 2 说明了c r i s p d m 过程模型中各步骤之间的关系。 图3 2c r i s p 一删过程模型 f i g3 2c r i s p d md a t a m i n i n gm o d e l 该模型的执行分以下六个步骤进行： ( 1 ) 业务理解：对项目目标理解和客户需求的理解，转化为一个数据挖掘的 定义和为了达到目标的初步方案； 上海师范大学硕士学位论文第三章数据挖掘模型与算法改进 ( 2 ) 数据理解：检测数据的质量，对数据有初步的理解，探测数据中比较有 趣的数据子集，进而形成对潜在信息的假设： ( 3 ) 预处理：包括从原始粗糙数据中构建最终数据集的全部工作，主要包括： 制表，记录，数据选择和转换，以及数据清理等等； ( 4 ) 建模：各种各样的建模方法将被加以选择和使用，并将其参数校准为理 想的值： ( 5 ) 评估：对建立的模型进行评估，确保模型达到企业目标； ( 6 ) 部署：把建模信息以客户能够使用的方式组织和呈现出来。 c r i s p d m 过程模型从数据挖掘技术应用的角度划分数据挖掘任务，将数据挖 掘技术和应用紧密结合，注重数据挖掘的质量和如何与业务问题相结。 该过程模型存在的问题： ( 1 ) 挖掘结果在对实际情况进行指导时未使用最优化方法； ( 2 ) 对挖掘过程中使用的挖掘技术没有明确反映。 3 1 3 数据挖掘过程模型的评估 挖掘模型建立以后，要对建立的模型进行评估，对挖掘模型主要从模型的准 确性、可理解性和性能三个方面进行评价。模型的建立和评估一起使得挖掘模型 的建立成为一个反复迭代循环的过程。在模型建立过程中要研究多个可供选择的 模型，通过对多个模型评估找出最能适应当前挖掘情况、最能解决问题的模型。 模型的准确性评估需要时间来进行验证，在这一方面需要用到统计分析技 术。 模型的可理解性一般表现在不同的输入数据会对输出结果产生的影响的解 释和对复杂数据集挖掘结果的预测能力。就对挖掘结果的解释性方面来说，神经 网络模型的可理解性较差，而决策树模型的可理解性最强：从对复杂数据集挖掘 结果的预测性能方面来说，决策树挖掘模型的复杂数据集处理能力较差。 模型的性能评估主要从模型的构建速度以及从其中获取预测结果的速度方 面来进行评价。 1 8 上海师范大学硕士学位论文第三章数据挖掘模型与算法改进 3 1 4 挖掘知识的应用 数据挖掘操作的意义和最终目的就是把挖掘结果应用到实际工作中，利用挖 掘结果对现实进行指导和预测。 对挖掘知识应用的前提是对知识的理解。知识的应用是把挖掘结果和实际工 作的需求相结合而实现的。知识的作用表现在对实际工作的指导和预测两个方 面。 对知识进行正确理解和使用，不仅对实际工作会产生促进作用，同时对挖掘 系统也会产生帮助。因为数据挖掘系统模型的建立是一个反复迭代、不断完善的 一个过程，如果合理应用挖掘的结果，就可以产生正确的反馈信息，挖掘模型根 据反馈信息，不断进行修订和完善。 3 2 挖掘算法的分析与改进 3 2 1 关联规则算法分析 关联规则是数据挖掘研究中的一个重要分支。自从r a g r 鲫a l 等人在 s i g m o d 9 3 上第一次提出这个问题以来，关联规则一直是众多学者的研究热点。 现已发表的研究论文包括确定性关联规则的挖掘、量化关联规则的挖掘、增量式 关联规则的挖掘、模糊关联规则的挖掘、广义关联规则的挖掘等。关联规则挖掘 的目的是在交易数据库中发现各项目之间的关联关系。 ( 1 ) 关联规则的基本概念 假设i = i l ，i 2 ，i m ) 是所有项的集合，相当于商品的所有种类的集合， d 是所有事务的集合，也即数据库中记录的集合，事务t = t 1 ，t 2 ，t nt i i ，相当于交易中的商品列表。若x 、y 是数据项集，x 中含有的项数目为k ， 则称为k 一数据项集。 事务集d 中的规则x y ( 其中x i ，y i ，x n y = ) 是由支持度( s u p p o r t ) 和确信度( c o n f i d e n c e ) 约束的，支持度表示规则的频度，确信度表示规则的强度。 规则x y 在交易数据库d 中的支持度是交易集中同时包含x y 的交易数与所有交 易数之比，记为s u p p o r t ( x y ) = l x u y t ，t d ) l l d i 。 1 9 上海师范大学硕士学位论文第三章数据挖掘模型与算法改进 规则x y 在交易数据库d 中的可信度是交易集中同时包含x y 的交易数与包 含x 的交易数之比，记为c o n f i d e n c e ( x y ) = i x u y t ，t d ) i l x t ，t d ) i 。 给定一个交易集d ，挖掘关联规则问题就是产生支持度和可信度分别大于用 户给定的最小支持度( m i n s u p p ) 和最小确信度( m i n c o n f ) 的关联规则。当规则的 确信度和支持度分别大于m i n s u p p 、m i n c o n f 时，我们认为规则是有效的，称为 强关联规则。当数据项集x 的支持度大于m i n s u p