已阅读5页,还剩68页未读, 继续免费阅读
(计算机应用技术专业论文)apriori_t算法研究及在高考数据分析中的应用.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
,p 原创性声明 liil iiii i ii ii i tii tii il y 1718 3 2 8 本人声明,所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知,除了论文中特别加以标注和致谢 的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名: 嗍珥年罩月屋门 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定,即:学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位沦文, 允许学位论文被食阅不u 借阅;学校叮以公前j 学位论文的伞部或部分内 容,可以采用复印、缩e | j 或它于段保存学位沦文。同时授权中幽科 学技术信息研究所将本! 学位论文收录到中国学位沦文全文数扒庠, 并通过网络向社会公众提供信息服务。 作行签辊: , 签名盈一烁掣;f 上,丝门 摘要 随着数据库技术和网络技术的发展,加上先进的自动数据采集工 具的使用,人们拥有的数据量急剧增加,这使得数据挖掘技术得到了 广泛的应用。高考数据中隐含着各地区高考教育的特点,蕴藏着高考 的发展规律和趋势,为了找出这些规律和趋势,我们利用数据挖掘技 术来对高考数据进行分析。 本文针对高考志愿预测分析、自主命题质量评价、加分政策影响 分析、中学教学绩效评价四个方面,利用关联规则挖掘a p r i o r i 算法 来对高考数据进行分析。由于a p r i o r i 算法在挖掘频繁项集时需要多 次扫描数据库,并产生大量的候选项集,时间复杂度过高。为了克服 a p r i o r i 算法的缺陷,本文采用项集信息表来记录项集信息,避免了 重复扫描数据库,并以此为基础对a p r i o r i 算法进行了改进,设计了 a p r i o r it 算法。本文对a p r i o r it 算法的基本思想及步骤做了详细的 描述,并通过示例和实验分析验证了算法的有效性和优势。此外,本 文将a p r i o r it 算法应用到高考数据挖掘中,针对高考关联规则挖掘 中产生无效规则较多的特点,研究设计了有效频繁项集关联规则的高 考数据挖掘方法,同时在分析“支持度一置信度”框架的衡量标准的 基础上,提出了高考数据的评价度标准,提高了高考关联规则挖掘的 效率。论文最后将a p r i o r it 算法应用到高考数据分析系统中,同时 利用该系统对2 0 0 8 年湖南省的高考数据进行了分析,完成了高考数 据分析系统的设计与开发。 关键词:数据挖掘,关联规则,高考数据,项集信息表,a p r i o r i j 算法 a bs t r a c t w i t ht h ed e v e l o p m e n to ft e c h n o l o g yi nd a t a b a s ea n dn e t w o r k , c o u p l e dw i t ht h eu s a g eo fa d v a n c e da u t o m a t e dd a t ac o l l e c t i o nt o o l s ,i t h a sad r a m a t i ci n c r e a s ei nt h ea m o u n to fd a t a ,s od a t am i n i n gt e c h n o l o g y h a sb e e nw i d e l ya p p l i e d t h eu n i v e r s i t ye n t r a n c ee x a m i n a t i o nd a t a i m p l i e st h ee d u c a t i o nc h a r a c t e r so fd i f f e r e n ta r e a sa n dd e v e l o p m e n tr u l e s a n dd e v e l o p m e n tt r e n d s i no r d e rt of i n do u tt h e s er u l e sa n dt r e n d s ,w e u s e dd a t a m i n i n gt e c h n o l o g y t o a n a l y z e t h e u n i v e r s i t y e n t r a n c e e x a m i n a t i o nd a t a t h i st h e s i s r e f e r st o u n i v e r s i t ye n t r a n c ee x a m i n a t i o nf o r e c a s t a n a l y s i s ,q u a l i t ye v a l u a t i o na b o u ti n d e p e n d e n tp r o p o s i t i o n ,i n f l u e n c eo f a d d i n gs c o r ep o l i c ya n de v a l u a t i o no fh i g hs c h o o lt e a c h i n gp e r f o r m a n c e b e c a u s ea p r i o r ia l g o r i t h ms h o u l ds c a nt h ed a t a b a s em a n yt i m e sw h e n m i n i n gf r e q u e n t l yi t e m sa n dw i l lg e n e r a t el a r g en u m b e r so fc a n d i d a t e i t e m s ,i th a sh i g ht i m ec o m p l e x i t y i no r d e rt oo v e r c o m et h i sd e f e c to f a p r i o r ia l g o r i t h m ,w eu s e di t e m si n f o r m a t i o nt a b l e st os t o r ei t e m s i n f o r m a t i o ns oa st oa v o i ds c a n n i n gt h ed a t a b a s em a n yt i m e s w eh a v e i m p r o v e da p r i o r ia l g o r i t h ma n dd e s i g n e da p r i o d ja l g o r i t h m t h i s t h e s i se x p l a i n e dt h eb a s i ci d e aa n ds t 印so fa p r i o r iti nd e t a i l ,v e r i f i e d t h ee f f e c t i v e n e s sa n da d v a n t a g e so ft h ea l g o r i t h mt h r o u g he x a m p l e sa n d e x p e r i m e n t a la n a l y s i s i na d d i t i o n ,a p r i o 凹a l g o r i t h mh a sb e e nu s e di n d a t am i n i n go fu n i v e r s i t ye n t r a n c ee x a m i n a t i o ni nt h i st h e s i s t ob e a i m e da tt h ep o i n tt h a tu n i v e r s i t ye n t r a n c ee x a m i n a t i o na s s o c i a t i o nr u l e s m a yg e n e r a t em a n yi n v a l i dr u l e s ,w ea n a l y z e da n dd e s i g n e dav a l i d f r e q u e n t l yi t e m sa s s o c i a t i o nr u l e si nu n i v e r s i t ye n t r a n c ee x a m i n a t i o nd a t a m i n i n g w - ep r o p o s e dt h ee v a l u a t i o nc r i t e r i ao fu n i v e r s i t ye n t r a n c e e x a m i n a t i o nd a t ab a s e do nt h ea n a l y s i so fw e i g h ts t a n d a r da b o u t d e g r e e o fs u p p o r t b e l i e f f r a m e w o r ka n di m p r o v e dt h ee f f i c i e n c yo fm i n i n g a t l a s t ,a p r i o r i _ ta l g o r i t h mh a sb e e nu s e di nt h eu n i v e r s i t ye n t r a n c e e x a m i n a t i o nd a t aa n a l y s i ss y s t e m 晰t ht h eh e l po ft h i s s y s t e m ,w e a n a l y z e dt h eu n i v e r s i t ye n t r a n c ee x a m i n a t i o nd a t ai nh u n a np r o v i n c ei n i i 2 0 0 8 ,d e s i g n e da n di m p l e m e n t e dt h eu n i v e r s i t ye n t r a n c ee x a m i n a t i o n d a t aa n a l y s i ss y s t e m k e yw o r d sd a t am i n i n g ,a s s o c i a t i o nr u l e ,u n i v e r s i t ye n t r a n c e e x a m i n a t i o nd a t a ,i t e m si n f o r m a t i o n t a b l e ,a p r i o 暄- ta l g o r i t h m i i i 目录 摘要i a b s t r a c t i i 目录。 第一章绪论1 1 1 高考数据分析与数据挖掘1 1 2 国内外研究现状2 1 2 1 数据挖掘技术的研究现状与水平2 1 2 2 关联规则挖掘的研究现状与水平4 1 3 课题的研究目的及意义5 1 4 本文的研究内容与组织结构。6 第二章数据挖掘与关联规则挖掘技术8 2 1 数据挖掘概述8 2 1 1 数据挖掘的概念8 2 1 2 数据挖掘的对象1 0 2 1 3 数据挖掘的分类1 2 2 1 4 数据挖掘的应用1 4 2 2 关联规则挖掘技术1 5 2 2 1 关联规则的基本概念1 5 2 2 2 关联规则的分类1 6 2 2 3 关联规则的挖掘方法1 7 2 2 4 关联规则挖掘的步骤18 2 3 本章小结1 9 第三章基于项集信息表的a p r i o r i算法21t 3 1a p r i o r i 算法的原理及步骤2 1 3 2a 研o r i 算法的不足及改进方法2 2 3 3a p r i o r it 算法一2 3 3 3 1 项集信息表2 3 i v 3 3 2a p r i o 喧j 算法的基本思想及步骤2 4 3 3 3a p r i o r it 算法描述2 5 3 3 4a p r i o r it 算法实现示例。2 8 3 4 应用结果分析31 3 5 本章小结3 3 第四章基于有效频繁项集关联规则的高考数据挖掘3 5 4 1 高考关联规则挖掘的特点3 5 4 1 1 高考事务数据库的特征分析3 5 4 1 2 高考志愿的关联规则挖掘。3 7 4 2a p r i o r i _ t 算法在高考关联规则挖掘中的改进3 7 4 2 1 基于高考数据的a p r i o r it 改进算法3 8 4 2 2 基于a p r i o r it 改进算法的高考关联规则挖掘流程3 9 4 2 3 实验分析4 0 4 3 基于高考数据的评价度标准4 l 4 3 1 基于“支持度置信度”框架的衡量标准的不足4 1 4 3 2 改进的高考关联规则评价体系4 2 4 4 本章小结4 3 第五章关联规则挖掘在高考数据挖掘分析中的应用4 4 5 1 高考数据中的关联规则挖掘4 4 5 1 1 高考志愿预测分析4 4 5 1 2 自主命题质量评价4 5 5 1 3 加分政策影响分析4 5 5 1 4 中学教学绩效评价4 6 5 2 高考数据分析系统的设计与实现4 6 5 2 1 系统开发环境及工具4 6 5 2 2 系统体系结构和功能模块。4 7 5 2 3 数据准备4 9 5 2 4 挖掘结果分析5 0 5 3 本章小结5 2 第六章结束语5 3 v 6 1 本文研究工作总结5 3 6 2 后续的研究工作与展望5 4 参考文献5 4 致谢。5 4 攻读硕士学位期间完成论文情况6 0 攻读硕士学位期间参加的科研情况6 0 v i 硕士学位论文第一章绪论 第一章绪论 1 1 高考数据分析与数据挖掘 搿百年大计,教育为本”,振兴教育是我国实现社会主义现代化的基础,也 是我国增强综合国力并在日趋激烈的国际竞争中立于不败之地的基础,发展教育 己经成为我国面向2 l 世纪的战略性抉择。高考是我国现代教育模式中的重要一 环,在社会主义教育事业中起着为高等院校输送人才的重要作用【。 高考是我国现代教育不可或缺的组成部分,随着教育事业的发展,高考经历 了多种形式的变革,许多负责高考的工作单位也累计了大量的原始高考数据,这 些数据并不是毫无规则的,而是蕴含大量有效信息的。高考数据涵盖了教学、升 学、命题及招生等多个方面,学校、考生、命题组及教育主管部门都希望通过分 析历年的高考数据来得到一些有效的规则以支持自己的决策。高考数据中存在许 多散乱的非结构化数据 2 j ,要提取有效的信息和规则必须对这些数据进行适当的 处理。最初,高考数据都使用纸质材料保存,人们通过检索、翻阅纸质材料要从 中发现有用的信息或有效的规则犹如大海捞针。随着计算机的普及与发展,越来 越多的考试信息使用了计算机进行处理和存放,大大减少了手工处理的程序,减 少了存储的空间,提高了存储的安全性和便捷性,与此同时,如何根据不同的要 求和特征,从海量高考数据中找出数据间的必然联系和潜在关系,己经成为招生 部门和考生的必然需求。简单的依靠传统的数学统计方法己无法满足现代教育管 理的需要,只有结合先进的数据挖掘技术并结合与高考相关的领域知识对数据进 行分析,才能科学合理的提取数据当中有用的信息,指导高考招生工作【3 】。 随着以电脑多媒体和网络通讯为基础的现代化信息技术在教育领域的广泛 应用,教育资源库中存储了海量的信息,如何把无以计数、若隐若现的教育信息 碎片组合成具有决策价值的信息拼图,数据挖掘为我们提供了一种新的思路。教 育信息化具有教材多媒化、资源全球化、教学个性化、活动合作化、管理自动化 和环境虚拟化等特点【4 】,这些特点使得数据挖掘技术在教育信息化中具有潜在的 应用价值。 数据挖掘是指从大量数据中挖掘出隐含的、先前未知的、对决策有潜在价值 的知识和规则的高级处理过程【5 1 。通过数据挖掘,有价值的知识、规则或高层次 的信息就能从数据库的相关数据集合中抽取出来,并从不同角度显示,从而使大 型数据库作为一个丰富的、可靠的资源为提取知识服务。数据挖掘技术不仅是面 硕士学位论文第一章绪论 向特定数据库的简单检索查询调用,而且对这些数据进行微观的分析综合和宏观 的统计推理,以便发现事件间的相互联系,指导实际问题的求解,还可以利用已 有的数据对未来的活动进行预测,这样人们对数据的应用就从低层次的查询操作 提高到了为决策者提供决策支持的层次。数据挖掘技术一经推出便在大型商业、 金融业、保险业、民航业及电信业等多个领域广泛应用开来,比如评估账户信用 等级、分析信用卡模式、获取股票交易的规则或规律、分析顾客的购买行为和习 惯、分析商场的商品构成、预测顾客购买新险种的规律等等,显示出了巨大的应 用价值。 何 1 2 国内外研究现状 随着各行业计算机化的推进,人们产生和收集数据的能力迅速提高,许多领 域的业务数据成倍增长,另外,作为全球信息系统的万维网的流行,已经将我们 淹没在数据的汪洋大海中。人们对于数据的处理不再满足于简单的统计检索,而 是致力于找出蕴含在这些数据背后的规律和含义,即能从数据中提取知识用于指 导实践。落后的信息管理系统中的数据分析工具已无法适应新的需求,因为无论 是查询、统计还是报表,其处理方式都是对指定的数据进行简单的数字处理,而 不能对这些数据所包含的内在信息进行提取。如何在繁杂的数据中寻找有用的知 识,使急剧增长的数据变成有价值的资源,成为一个迫切要解决的问题【6 】。存储 数据的爆炸性增长激起了人们对新技术和自动工具的需求,以便将海量数据转换 成信息和知识,数据挖掘技术就是在这种情形下应运而生的。数据挖掘的任务是 从数据中发现模式,这些模式分为6 种t 分类模式、回归模式、时间序列模式、 聚类模式、关联模式和序列模式,其中关联模式的挖掘是目前数据挖掘领域中最 为广泛研究的课题之一。数据项之间的关联规则称为关联模式,起初主要应用与 对购物篮的分析,随着研究的深入,关联模式在金融、生物、证券及安全交易、 电信等许多领域应用开来。 1 2 1 数据挖掘技术的研究现状与水平 随着数据库技术的迅速发展以及数据库管理系统的广泛应用,人们积累的数 据越来越多。如何从激增的数据背后找到有价值的信息,并从中提取出知识内容 已经成为目前数据挖掘和知识管理等研究领域的重要课题。而数据挖掘技术 ( d a t am i n i n g ) 正是解决这一课题的重要方法。权威的调查组报告显示,数据挖掘 将是今后几年全球范围内重点投资研究的十大新技术之一,它引起了学术界和工 业界的广泛关注,是当今数据库系统研究和应用领域内的一个热点问题。作为一 门新兴的交叉学科【_ 7 1 ,数据挖掘涉及到很多学科领域。在国外,数据挖掘的研究 2 硕士学位论文第一章绪论 已有二十多年的历史,理论体系较为成熟,并已有相应的软件产品应用于各行各 业,取得了显著的效果。总的来说,对数据挖掘的研究经历了如下四个阶段: 1 、第一代数据挖掘系统:支持一个或少数几个数据挖掘算法,数据一次调 到内存进行处理,典型如s a l f o r ds y s t c r p s 公司早期的c a r t 系统。 2 、第二代数据挖掘系统:集成数据库管理系统,支持数据库和数据仓库具 有好的扩展性,典型如d b m i n e r ,能通过d m q l 挖掘语言进行操作。 3 、第三代数据挖掘系统:数据挖掘系统生成的预言模型能在操作型环境中 充分使用,能够挖掘网络环境下的分布式和高度异质的数据。 4 、第四代数据挖掘系统:将数据挖掘和移动计算相结合,可以挖掘嵌入式 系统、移动系统、和计算设备产生各种类型数据。 国内从事数据挖掘研究的人员主要在大学,也有部分在研究所或公司。所涉 及的研究领域很多,一般集中于学习算法的研究、数据挖掘的实际应用以及有关 数据挖掘理论方面的研究【8 】。目前进行的大多数研究项目是由政府资助进行的, 如国家自然科学基金、8 6 3 计划、九五“计划 等。 国外数据挖掘的发展趋势其研究方面主要有:对知识发现方法的研究进一步 发展,如近年来注重对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高1 9 , 传统的统计学回归法在数据库知识发现( k d d ) 技术中的应用及k d d 与数据库的 紧密结合,在应用方面包括k d d 商业软件工具的不断产生和完善,注重建立解 决问题的整体系统,而不是孤立的过程【l o 1 l 】。用户主要集中在大型银行、保险 公司、电信公司和销售业。国外很多计算机公司非常重视数据挖掘的开发应用, i b m 和微软都成立了相应的研究中心进行这方面的工作,此外,一些公司的相 关软件也开始在国内销售,如p l a t i n u mb o 以及i b m 。 在2 l 世纪,数据挖掘的研究焦点可能会集中到以下几个方面: 1 、研究专门用于知识发现的数据挖掘语言,也许会像s q l 语言一样走向形 式化和标准化【1 2 】; 2 、寻求数据挖掘过程中的可视化方法,使得知识发现的过程能够被用户理 解且能操纵它,也便于在知识发现过程中的人机交互,使数据挖掘过程成为用户 业务流程的一部分:它包括数据用户化呈现与交互操纵两部分【1 3 】; 3 、研究在网络环境下的数据挖掘技术,特别是在i n t e m e t 上建立d m k d 服 务器,与数据库服务器配合,实现数据挖掘【1 4 15 】: 4 、融合各种异构数据的挖掘技术,加强对各种非结构化数据的挖掘,如文 本数据、图形图像数据、多媒体数据、空间数据库等【1 6 】; 5 、数据挖掘理论与算法研究。经过十几年的研究,数据挖掘已经在继承和 发展相关基础学科( 如机器学习、统计学等) 方面取得了可喜的进步与成果,探索 3 硕士学位论文第一章绪论 出了许多独具特色的理论体系。一方面,在这些大的理论框架下有许多面向实际 应用目标的挖掘理论等待探索和创新。另一方面,随着数据挖掘技术本身和相关 技术的发展,新的挖掘理论的诞生是必然的,而且可能对特定的应用产生推动作 用【1 7 1 。新理论的发展必然促进新的挖掘算法的产生,这些算法可能扩展挖掘的 精度和效率,对数据挖掘的某些阶段、某些数据类型、大容量数据集更有效,还 可能融合特定的应用目标【1 8 - 2 0 ,如c r m 、电子商务等。因此,对数据挖掘理论 和算法的探讨将是长期而艰巨的任务。 1 2 2 关联规则挖掘的研究现状与水平 事务数据库中关联规则的发现是数据挖掘中一个非常重要的研究领域,由 r a k e s ha g r a w a l 2 i 】等人在1 9 9 4 年首先提出来之后,获得了广泛的关注和长足的 发展。关联规则是对一个事物和其它事物的相互依存和相互关联的一种描述,针 对数据而言是发现数据中项集之间潜在的关联或依赖联烈2 2 1 。最初产生于零售 业中,在传统的零售商店中顾客通常是到一个柜台买完东西后再到另一个柜台去 买另一样东西,这样一来,商场经理虽然知道每一种商品的销售情况,但不知道 是哪些顾客购买的,也不知道这个顾客同时还买了哪些东西团】。随着超级市场 的出现,顾客可以在超市一次购得所有自己需要的商品,而条型码技术的广泛应 用,使商家非常容易收集和存储数量巨大的销售数据。一条这样的数据记录通常 都包括与某个顾客相关的交易日期、交易中所购物品等等。通过对以往的大量交 易数据进行分析就能获得有关顾客购买模式的有用信息,从而提高商业决策的质 量【2 4 1 。 关联规则挖掘的典型例子是“啤酒和尿布 的故事 2 5 】:在英国,周末喜欢 看英超联赛的一些年轻父亲下班后经常到超市去买婴儿尿布。超市经过对顾客的 购物信息进行挖掘,发现了一条非常有趣的规则:在购买婴儿尿布的年轻父亲中, 有3 0 4 0 的人同时要买一些啤酒。超市随后调整了货架的摆放,把尿布和啤 酒放在一起,结果销售额明显增加了。这个例子的直观意义就是顾客在购买某些 商品的时候有多大的可能购买其他的商品。关联规则一般以条件逻辑进行表示, 即“如果那么 的形式,另外也可以用相似逻辑进行表示,其形式为 “当的时候,也,目前规则基本上都是条件逻辑的表现形式【2 6 1 。关联 规则的应用主要包括顾客购物分析、目录设计、商品广告、邮寄分析、追加销售、 仓储规划、网络故障分析掣2 7 一引。 人们对关联规则挖掘的研究主要集中于挖掘算法的改进和度量规则的优化。 在算法研究方面,论文 2 9 3 2 提出了一些挖掘关联规则的改进算法,这些算法 几乎都用到了频繁项集的向下封闭性质来修剪候项目集。频繁项集的向下封闭性 4 硕士学位论文第一章绪论 质是指任何频繁项集的子集也是频繁项集。a i s 算法【3 3 】在读取事务时生成候选项 目集,这导致许多不必要的候选项目集。a p r i o r i 算法【3 4 】因使用了较好的候选集 生成过程而优于早期的算法。d h p 算法【3 5 】是a p r i o r i 算法的扩展,采用了h a s h 技术,产生的候选集数量明显减少。p a r t i t i o n 算法【3 6 】将数据库分成若干部分,每 一部分能在内存中高效处理,当阈值较小时,c p u 时间明显降低,该算法仅需 扫描数据库两次,从而使i o 开销减到最小。文献 3 7 】提出了挖掘关联规则取样 的效率分析,文献 3 8 - 4 0 1 提出了一些平行算法,文献【4 1 提出了一种使用取样的 所有规则查找的精确算法。d i c 算法 4 2 】在向前扫描数据库时动态的计算可变长 度的候选项目集并减少了扫描次数。m j z a k i 和m o g h a r a 在文献 4 3 】中描述 了挖掘关联规则的正常框架,描述了极大全1 矩阵与二部图的关系。文献 4 4 1 中 提到的粗集理论研究了属性之间的依赖关系。在关联规则兴趣度优化方面,朱扬 勇【4 5 】等把一个基于差异思想的兴趣度定义运用到关联规则中,重新设置了兴趣 度;文献 4 6 】提出基于统计相关性的兴趣度关联规则;文献 4 7 】提出了一种解决 规则组合爆炸问题的方法,引入了兴趣度,改进度和r y m o n 枚举树,建立了一 个带约束的关联规则挖掘模型,对a p r i o r i 算法进行了优化。其他相关的研究包 括在处理极大数据量时如何提高算法的效率、如何在挖掘的过程中与用户进行交 互、对于数值型字段在关联规则中的处理问题、生成结果的可视化以及结合用户 的领域知识等方向【4 8 5 2 1 。 1 3 课题的研究目的及意义 湖南省是一个教育大省,2 0 0 8 年全省共有5 3 万多考生参加高考。湖南省教 育考试院是湖南省高考工作的主管部门,经过多年的积累,考试院保存了大量的 高考数据,这些数据客观记录了湖南省各地区以考生为主体的高考历史情况和现 状,同时也隐含着各地区高考教育的特点,蕴藏着高考的发展规律和趋势。为了 找出这些规律和趋势,我们利用数据挖掘技术来对高考数据进行分析,以便总结 高考经验,促进全省教育事业的发展。本文从高考志愿预测分析、自主命题质量 评价、加分政策影响分析、中学教学绩效评价四个方面来对高考数据进行挖掘, 具有重要的应用价值。高考数据挖掘分析在往年高考录取数据的基础上,对考生 所填的志愿进行分析,预测其被录取的几率,减少了考生因志愿填报不当而落榜、 高分但被档次较低的大学录取等现象发生的次数。自主命题质量评价通过分析考 生各个试题的得分情况,判断其设定的难度系数与实际难易程度是否一致,从而 对高考命题进行评价,促进高考命题向更加科学的方向发展。加分政策影响分析 对高考中有加分优惠考生的录取情况进行分析,判断某项加分政策在高考录取工 作中所起的作用,从而指导高考优惠政策的制定。中学教学绩效评价通过对不同 硕士学位论文第一章绪论 类型高中的考生的高考成绩进行分析,确定不同高中的教学优势和劣势,学科强 处和弱点,从而在以后的教学工作中增强补弱,扬长避短。这些分析工作对改进 我省人才培养模式,提高考生质量和教学质量有着重要的指导意义。 本文在进行数据挖掘工作时,为了挖掘出高考数据中的众多规则,主要采用 关联规则挖掘技术。作为经典的频繁项集生成算法,a p r i o r i 算法在关联规则挖 掘的研究中有着相当重要的作用,它利用候选项集和频繁项集的相互作用来得到 全部频繁项集,并通过对候选项集进行剪枝以减少候选项集的尺寸。虽然对候选 项进行剪枝提高了算法的效率,但是a p r i o r i 算法仍然存在一些不足。人们对 a p r i o r i 算法进行了大量的优化和改进,比较著名的a p r i o r i 改进算法主要有基于 划分的改进算法、基于事务压缩的改进算法和基于散列的优化算法等几种【4 9 】。 但是由于挖掘的数据有各自的特点,并不存在一种适合所有数据集合的关联规则 挖掘算法。高考数据有其自身的特点,为了取得好的挖掘效果,本文在原有的 a p r i o r i 算法基础上进行了一定的改进,设计了a p r i o r i算法,该算法利用项集t 信息表和字符串匹配方法来查找频繁项集,再通过频繁项集生成关联规则。 a 砸o r it 算法避免了重复扫描事务数据库,比a p r i o r i 算法节省了许多i o 开销, 并通过对项集信息表建立索引、递归调用及字符串匹配优化等方法提高了项集检 索速度,在相同条件下,执行效率比a p r i o r i 算法要高。a p r i o r i算法能对高考t 数据进行有效的关联规则挖掘,得出正确的规则和结论,这些规则和结论能有力 的指导高考相关部门的工作。a p r i o r i算法对关联规则算法在其他领域的应用t 也具有一定的参考价值。 1 4 本文的研究内容与组织结构 本文对数据挖掘技术尤其是关联规则挖掘技术的研究现状和水平进行了一 定的调研,结合湖南省高考招生工作的现状,指出了高考数据挖掘的重大意义。 本文对关联规则挖掘技术中的a p r i o r i 算法进行了深入的研究,针对它需要多次 扫描事务数据库导致算法效率较低的缺陷,设计了一种以项集信息表为基础的 a p r i o r i 算法,降低了系统 开销。文中还针对高考数据挖掘的特点,对t i o a p r i o r it 算法进行了一定的改进,使其在挖掘高考关联规则时更加有效。本文 最后设计了一个高考数据分析系统,对2 0 0 8 年湖南省的高考数据进行挖掘分析。 本文的组织结构如下: 第一章绪论。本章主要介绍课题的研究背景及意义,重点讨论了数据挖掘 技术尤其是关联规则挖掘的研究现状与水平,阐明了高考数据挖掘工作的背景和 重要意义。 第二章数据挖掘与关联规则挖掘技术。本章主要介绍数据挖掘和关联规则 6 硕士学位论文第一章绪论 挖掘技术的一些基本知识,包括数据挖掘的概念、对象、分类及应用和关联规则 挖掘的基本概念、分类、方法及基本步骤等内容,本章的内容是下面章节的理论 基础。 第三章基于项集信息表的a p d o dt 算法。本章针对a p d o f i 算法需要多次 重复扫描事务数据库导致系统i o 开销过大的缺陷,设计了一种以项集信息表为 基础的a p n o dt 算法,降低了系统f o 开销。 第四章基于有效频繁项集关联规则的高考数据挖掘。本章首先介绍了高考 关联规则挖掘的特点,并针对这些特点对a p f i o dt 算法加入了字符串匹配过程, 从而减少了无效关联规则的生成个数,提高了a p f i o dt 算法的效率;其次,针 对基于“支持度一置信度框架的衡量标准存在挖掘高考关联规则时存在的缺陷, 加入了相关支持度的评价指标,完善了关联规则评价体系。 第五章关联规则挖掘在高考数据挖掘分析中的应用。本章从高考数据挖掘 出发,设计了一个高考数据分析系统,对高考数据进行高考志愿预测、自主命题 质量评价、加分政策影响分析和中学教学绩效评价四方面的挖掘分析。 第六章结束语。本章对论文的研究工作做了一个总结,并提出了后续的研 究工作及展望。 7 硕士学位论文 第二章数据挖掘技术与关联规则挖掘技术 第二章数据挖掘与关联规则挖掘技术 快速增长的海量数据远远超过了人们的理解能力,如果不借助强有力的分析 工具,很难弄清大堆数据中所蕴含的知识,数据挖掘技术的出现填补了数据和信 息之间的鸿沟。关联规则是描述数据库中数据项之间某种潜在关系的规则,关联 规则挖掘技术已成为数据挖掘中一个非常重要的方向。本章主要介绍数据挖掘与 关联规则挖掘技术的一些基本知识。 2 1 数据挖掘概述 随着社会的发展,数据量急剧膨胀,数据的时效性和复杂性远远超过了当前 的信息处理能力。信息化和全球化是二十一世纪的最大特征,在网络技术的推动 下,近十几年来,人们生产和搜集数据的能力大幅度地提高,而数据获得和生产 能力大大超过数据处理的能力。现今,由于数据生产、传输能力与数据分析能力 的不平衡,人们被数据淹没,寻找隐藏在其中的有用信息无异于大海捞针。人们 希望能够提供高层次的数据分析功能,自动和智能地在待处理的数据中寻找和发 现有用的信息知识。数据挖掘( d a t am i n i n g ) 技术也因此应运而生,并蓬勃发展, 越来越显示出强大的生命力。 2 1 1 数据挖掘的概念 数据挖掘这个术语首先出现于1 9 8 9 年8 月美国底特律召开的第1 届国际人 工智能联合会议上,经过二十年的研究至今己有许多定义,其中得到公认的是 w j f r a w l e y ,gp i a t e t s k y - s h a p i r o 等人在k d d9 6 国际会议上给出的一种定义: 数据挖掘( 或数据库中的知识发现) 是指从大量数据中提取有效的、新颖的、潜 在有用的以及最终可理解的模式的非平凡过程【1 0 13 1 ,下面介绍该定义中的一些 术语【1 3 t1 6 1 7 1 。 定义2 1 数据:指一个有关事实,的集合,用以描述事物的基本信息。如 学生档案数据库中有关学生基本情况的记录。一般来说这些数据都是准确无误 的。数据是数据挖掘的对象,不仅只是数据库,也可以是文件系统,或其它以任 何方式组织在一起的数据集合,例如w w w 信息资源,数据仓库等等。 定义2 2 模式 ”】:对于集合f 中的数据,我们可以用语言三来描述其中数 据的特征。三中的表达式e 所描述的数据是集合f 的一个子集疋,磊表明数据 集f 中的数据具有特性e 。作为一个模式,e 比枚举数据子集简单。例如“如果 硕士学位论文第二章数据挖掘技术与关联规则挖掘技术 分数在8 1 到9 0 之间,则成绩优良 可称为一个模式。 定义2 3 非平凡过程:所谓非平凡过程是指具有一定程度的智能性和自动 性,而绝不仅仅是简单的数值统计和计算。 定义2 4 有效性( 可信性) :从数据中发现的模式必须有一定的可信度,否则 数据挖掘就没有意义了。可以通过新增数据来检验模式的正确性,以c 来表示 模式e 的可信度c = c 佤毋,其中e ,e 所描述的数据集合r 属于f 。 定义2 5 新颖性:提取出的模式必须是新颖的。模式是否新颖可以通过两个 途径来衡量:一是通过比较当前得到的数据和以前的数据或期望得到的数据来判 断;二是通过对比发现的模式与己有模式的关系来判断。通常用一个函数n c e , 刃来表示模式的新颖程度,该函数的返回值是逻辑值或是对模式e 的新颖程度的 一个判定数值。 定义2 6 潜在作用:指提取出的模式将来会被实际运用,可以通过函数u 的值来衡量,函数己厂把三中的表达式映射到度量空间m ,u 表示模式e 的有作 用程度,“= u 佤刀。 定义2 7 可理解性:数据挖掘的一个目标就是将数据中隐含的模式以可被人 理解的形式表现出来,从而帮助人们更好地了解和使用数据中所包含的信息,这 主要体现在简洁性上。要想让一个模式更容易地被人们理解并不是一件很容易的 事,需要对其简单程度进行度量,用s = s 佤刀表示模式e 的可理解度。 从知识发现的角度,可以把数据挖掘视为数据库中知识发现过程的一个基本 步骤。一般知识发现的过程由以下几个步骤组成【7 9 7 】: l 、数据清理:消除噪声或不一致的数据; 2 、数据集成:多种数据源可以组合在一起; 3 、数据选择:从数据库中检索与分析任务相关的数据: 4 、数据变换:数据变换或统一成适合挖掘的形式,如通过汇总或聚类操作; 5 、数据挖掘:基本步骤,使用智能方法提取数据模式; 6 、模式评估:根据某种兴趣度量,识别表示知识的真正有趣的模式; 7 、知识表示:使用可视化和知识表现技术,向用户提供挖掘知识。 数据挖掘步骤可以与用户或知识库交互,将有趣的模式提供给用户,或作为 新的知识存放在知识库中。 从数据挖掘的广义观点来看,数据挖掘是从存放在数据库、数据仓库或其他 信息库中的大量数据中挖掘有趣知识的过程【9 1 2 , 1 5 】。基于这种观点,典型的数 据挖掘系统具有如图2 1 所示的结构。 9 硕士学位论文第二章数据挖掘技术与关联规则挖掘技术 硕士学位论文 第二素数据挖掘技术与关联规则挖掘技术 额 等问题。数据挖掘用于关系数据库时,可以进一步搜索趋势或关系模式,例 如,可以根据顾客的收入、年龄和以前的信用信息预测新顾客的信用风险,可以 检测偏差,发现与以前的年份相比,哪种商品的销售出人预料等。关系数据库具 有完备的数学理论基础和广泛的普及度,是数据挖掘最流行、最丰富的数据源, 是数据挖掘研究的最主要的数据形式【1 2 】。 2 、数据仓库 数据仓库是从多个数据源收集的信息存储,存放在一个一致的模式下,并通 常驻留在某个站点。数据仓库通过数据清理、数据变换、数据集成、数据装入和 定期数据刷新来构造。大部分情况下,数据挖掘都要先把数据从数据仓库中拿到 数据挖掘库或数据集市中。 通常,数据仓库用多维数据库结构建模。其中,每一维对应于模式中的一个 或一组属性,每个单元存放某个聚集度量值,如c o u n t 或s a l e sa m o u n t 。数据仓 库的实际物理结构可以是关系数据存储或多维数据立方体( d a t ac u b e ) 【7 1 。它提 供数据的多维视图,并允许预计算和快速访问汇总的数据。图2 2 给出了数据仓 库的基本结构。 图2 2 数据仓厍的结构 通过提供多维数据视图和汇总数据的预计算,数据仓库非常适合联机分析处 理( o l a p ) 。o l a p 操作使用数据的领域背景知识,允许在不同的抽象层提供数 据,这些操作适合不同的用户。o l a p 操作的例子包括下钻( d r i l l d o w n ) 和上卷 ( r o l l u p ) ,它们允许用户在不同的汇总级别观察数据例。 尽管数据仓库工具对于支持数据分析是有帮助的,但仍然需要更多的数据挖 掘工具,以便进行更深的自动分析。 3 、事务数据库 一般地说,事务数据库由一个文件组成,其中每个记录代表一个事务。通常, 一个事务包含个唯一的事务标识号t r a n s i d ( 如信用卡号) 和一个组成事务的项 的列表( 如顾客购买的商品) ,有的还包含事务的处理时间。事务数据库还可能有 硕士学位论文第二章数据挖掘技术与关联规则挖掘技术 一些与之相关联的附加表,包含关于事务的其他信息。事务数据库通常用于“购 物篮数据分析 ,对于
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年业务扩展计划讨论的联系信(3篇)范文
- 供应商资质变更信息更新通知(6篇)范文
- 节能厨房设备操作手册
- 文档格式转换标准测试报告催办函(4篇)
- 请求提前支付款项函(3篇范文)
- 设施农业环境调控自动化方案
- 2026年婚姻家庭咨询师一级(高级技师)专业能力冲刺模拟考试卷及答案(二十)
- 2026事业单位后勤岗面试历年真题题库及答案
- 汽车零部件加工工艺标准化手册
- 宠物用品电商营销策略方案
- 黑龙江省龙东十校联盟2027届高三上学期11月期中质量测试语文试卷(含答案)
- GB/T 7251.3-2026低压成套开关设备和控制设备第3部分:由一般人员操作的配电板(DBO)
- 欧盟电池护照EU2023-1542数据架构全解:唯一标识访问权限与数据更新合规指南
- 钢筋弯曲机使用安全要求培训
- 考研政治马克思主义基本原理核心知识点系统梳理框架
- ISO 14001-2026《环境管理体系 要求和使用指南》变化与应对行动说明表(雷泽佳编制-2026A0)
- (物理)2027版高中《基础自测小纸条》必修2(默写+背诵版)
- 2026年河北省中考英语试卷(含答案)
- 低压电缆头制作安装施工方案及技术措施
- 2026年中国东航行测笔试题库
- 塑料包装厂生产质量管理办法
评论
0/150
提交评论