（计算机应用技术专业论文）数据挖掘技术在高校招生工作中的应用.pdf

摘要 摘要 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，各行各业积累 了大量的历史数据，而这些激增的历史数据中往往隐藏着很多重要的信息。如何 从历史数据中及时发现有用的知识，从而挖掘出其潜在的价值，提高其利用率， 是信息处理技术研究领域的一项重要课题。作为其解决方案，近年来数据挖掘 ( d a t a m i n i n g ，d m ) 技术迅速崛起。 数据挖掘是目前信息领域和数据库技术的前沿研究课题，被公认为最具发展 前景的关键技术之一。数据挖掘涉及到数理统计、模糊理论、神经网络和人工智 能等多种技术，技术含量比较高，实现难度也较大。 本文以数据挖掘技术的研究作为核心，深入研究了关联规则和聚类分析技 术。关联规则及聚类分析作为数据挖掘的两个重要方法，有着可理解性强、简洁 性好、应用范围广等优点。本文探讨了这两种挖掘算法实现中的各项技术，以及 它们在现实系统中的应用。 在任何一所高校中，往往都积累有大量学生的入学信息、毕业生信息和在校 期间的成绩等资料。如果能对这些数据进行关联规则和聚类分析的挖掘，寻找出 考生的各种因素与学生在校期间成绩以及毕业信息之间的关联关系，研究考生生 源特征与培养之间的关系，进而能指导学校的招生和就业等工作。 本文以北京第二外国语学院的学生数据为背景，通过大量的数据预处理工 作，应用关联规则的f p - g r o w t h 算法及基于图论的m e t i s 聚类算法对上述数据进行 了数据挖掘，最终挖掘到有一定价值的信息。 本人所做的工作主要如下： 1 、论述了数据挖掘的基本理论、相关技术： 2 、讨论了关联规则的a p r i o r i 算法及其改进算法f p - t r e e 及f p - g r o w t h 算法； 3 、讨论了聚类分析的几类方法： 4 、在高校学生数据库中实现了关联规则挖掘及聚类分析。具体工作包括： 应用实例的分析、从原始数据收集到数据的预处理的实现、以及关系数 据库到适合挖掘的数据转换；实现了利用f p - t r e e 及f p - g r o w t h 算法寻找 频繁项集、输出挖掘到的关联规则；实现了应用聚类分析的基于图论的 方法对学生数据进行聚类，输出聚类的结果。 5 、利用粗糙集中条件信息熵和互信息值的理论，提出对聚类结果和所有的 特征进行计算，寻找出在所有的特征集中，哪些特征对聚类的贡献最大 的方法，即寻找哪些特征会是最能将学生分类的特征。 关键词数据挖掘；关联规则分析；聚类分析；高校招生 a b s t r a c t w i t hr a p i dd e v e l o p m e n to fd a t ab a s ea n de x t e n s i v ea p p li c a t i o no fd a t a b a s em a n a g e m e n ts y s t e m ，t h e r eh a v eb e e na r i s i n gl a r g ea m o u n t so f h i s t o r i c a ld a t af i l e si na l lf i e l d sf r o mw h i c hi m p o r t a n ti n f o r m a t i o na r e s t o r e d t h e r e f o r eh o wt om a k ee f f i c i e n tu s eo fs t o r e df il e sa n dd i go u t t h e i ri m p l l e dv a l u e sh a sb e c o m eac r u c i a lp r o j e c ti nt h er e s e a r c hf i e l d o fi n f o r m a t i o na n a l y s i s t om e e tt h ec h a l l e n g e ，d a t am i n i n gh a ss h o w ni t s e d g er e c e n t l y d a t am i n i n g ，t h el a t e s ts c i e n t i f i cp r o j e c ti ni n f o r m a t i o nf i e l da n d d a t ab a s et e c h n i q u e ，i sb e l i e v e dt ob et h em o s tp r o s p e r o u sk e yj o i n tf o r t h ef u t u r et e c h n i q u ed e v e l o p m e n t i tc o v e r sm a t h e m a t i c ss t a t i c sv a g u e c o v e r i n gt h e o r y ，n e u r a ln e t w o r ka n da r t i f i c i a li n t e l l i g e n c ew h i c ha 1 1 c o n t a i n sc o m p li c a t e dt e c h n i q u em a n a g e m e n ta n di sd i f f i c u l tt ob et u r n e d i n t or e a l i t y t h et h e s i si sb a s e do nt h ed a t am i n i n ga n ds e a r c hd e e p l yi n t ot h e a s s o c i a t i o nr u l ea n dc l u s t e ra n a l y s isw h i c ha r eu n d e r s t a n d a b l e ，s i m p l e a n da p p l i e dw i d e l y t h e r ei sm u c h s t o r e di n f o r m a t i o ni nm a n yu n i v e r s i t i e si n c l u d i n g e n t r a n c ei n f o r m a t i o n g r a d u a t ei n f o r m a t i o na n da 1 1t h ec r e d i ti n f o r m a t i o n m i n i n gt h o s er e l a t e di n f o r m a t i o na n df i n d i n gt h e i ri n n e rr e l a t i o n s h i p a c c o r d i n gt ot h ea s s o c i a t i o nr u l ea n dc l u s t e ra n a l y s i sw i l lh e l pg r e a t l y t ot h es t u d e n t se n r o l i m e n ta n de m p l o y m e n t b a s e do na n a l y s i so fm u c hi n f o r m a t i o nf r o mt h eb a c k g r o u n do ft h e b e i j i n gi n t e r n a t i o n a ls t u d i e su n i v e r s i t y ，t h i st h e s i st r i e st oc o m et o t h i st a r g e tb yf p g r o w t ha n dm e t i sb a s e do ng r a p ht h e o r y t h et h e s i s i n c l u d e st h ef o l l o w i n g ： 1 p r o v i d i n ga n dd e s c r i b i n gt h eb a s i ct h e o r i e sa n d r e l a t e dt e c h n i q u e so f d a t am i n i n g ： 2 d i s c u s s i n ga p r i o r i t yf r o ma s s o c i a t i o nr u l e ，f p t r e e a n df p g r o w t h a p p r o a c h ： 3 d i s c u s s i n gs e v e r a lm e t h o d si n t h ef i e l do fc l u s t e ra n a l y s i s ： 4 a p p l y i n ga s s o c i a t i o nr u l ea n dc l u s t e ra n a l y s i si nu n i v e r s i t yd a t ab a s e s y s t e ms u c ha sr e a l s i t u a t i o na p p l i c a b l ea n a l y s i s ，o r i g i n a l d a t a c o l l e c t i o na n dd a t ac o n v e r t i n g ：a s s o c i a t i o nr u l e i n t o d e e pd a t a r e l a t i o n s h i pb y f p t r e ea n df p g r o w t h ：c a t e g o r i z e ds t u d e n t s i n f o r m a t i o ne f f i c l e n t l y 。 5 t r y i n gt of i n dd e c i s i v em e t h o d st oc h a r a c t e r i z ec o l l e g es t u d e n t sa n d f i n d i n gt h em o s t c o n t r i b u t i v ef a c t o r sb yc o n d i t i o n a li n f o r m a t i o n e n t r o p ya n dm u t u a li n f o r m a t i o nf r o mt h et h e o r e t i c a ls y s t e mo fr o u g h s e t s i i a b s t r a c t k e y w 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 ；c l u s t e ra n a l y s i s ；u n i v e r s i t ys t u d e n t s r e c r u i t i n g i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：多耪日期：埘算刀 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：盟导师签名：；芝l日期：乡汐扮夕 第1 章绪论 第1 章绪论 1 1 数据挖掘的历史及其发展 随着计算机应用及i n t e r n e t 的日益普及，“丰富的数据与贫乏的知识”的问 题日见突出，世界上的数据正以惊人的速度增长，堆积如山。不同行业的人们都 希望从这些数据中得到信息和知识，而数据挖掘( d m ：d a t am i n i n g ) 就是从大量 的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、 人们事先不知道的、但又是潜在有用的信息和知识的过程，它是知识发现 ( k d d ：k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 的重要步骤。发现的知识可用于商 务管理、生产控制、市场分析、工程设计、科学探索、信息管理和查询处理等等。 数据挖掘是应用需求推动下的多种学科融合的结果跚恻嘲。 首先是数据库技术，尤其是超大规模数据库的出现。从2 0 世纪6 0 年代起，数 据库技术己经系统地从原始的文件处理进化到复杂的庞大的数据库系统。自7 0 年代以来，数据库系统的研究和开发已经从层次和网状数据库系统发展到关系数 据库系统、数据建模工具、索引和数据组织技术。从8 0 年代起，数据库技术的特 点是广泛接受关系技术，研究和开发新的功能强大的数据库系统。这些使用了先 进的数据模型，如扩充数据模型、面向对象模型、对象一关系模型和演绎模型。 多媒体数据库和基于i n t e r n e t 的全球信息系统成为信息产业的主力军。在过去3 0 年中，计算机硬件令人吃惊的进步导致了功能强大的计算机、数据收集设备和存 储介质的大量供应。这些技术大大推动了计算机和信息产业的进步，使得大量的 数据库和信息存储用于事务管理、信息检索和数据分析。数据的丰富带来了对强 有力数据分析工具的需求。由于缺乏强大的数据分析工具，存储数据的大型数据 库很少被访问，重要的决策不是以数据库中丰富的数据为基础，而是以决策者的 直觉做出的，隐藏在这些数据之后的更重要的信息则没有被充分利用。数据库技 术的日益成熟和数据仓库的发展为数据挖掘提供了发挥的平台。 其次是人工智能技术。数据库技术飞速发展的同时，计算机技术的另一领域 一人工智能自1 9 5 6 年诞生之后取得了重大进展。经历了博弈时期、自然语言理解、 知识工程等阶段，目前的研究热点是机器学习。机器学习是用计算机模拟人类学 习的一门科学，比较成熟的算法有神经网络、遗传算法等。自2 0 世纪5 0 年代开始， 研究机器学习以来，先后经历了神经模型和决策理论、概念符号获取及知识加强 和论域专用学习三个阶段，根据人类学习的不同模式，人们提出了很多机器学习 方法，如：实例学习、观察和发展学习、神经网络和遗传算法等等。其中某些常 用且成熟的算法已被人们用于实际的应用系统及智能计算机的设计和实现中。数 据挖掘中的许多方法就是来源于机器学习。用数据库管理系统来存储数据，用机 器学习的方法来分析数据，挖掘大量数据背后的知识，这两者的结合为数据库中 北京t 业大学1 = 学硕十学位论文 知识发现的产生奠定了坚实基础。 最后是计算机性能的迅速发展。先进的计算机技术，例如：计算机存储设备 性价比的迅速提高，使许多企业有能力收集和存储海量数据；更快和更强大的计 算能力和并行体系结构；对巨大量数据的快速访问，都为数据挖掘的实施扫清了 障碍。随着计算机性能的不断提高、数据挖掘技术的不断改进，数据挖掘应用将 会越来越普及。 数据挖掘的对象是某一专业领域中积累的数据，挖掘过程是一个人机交互、 多次反复的过程，挖掘的结果要应用于该专业。因此数据挖掘的整个过程都离不 开应用领域的专业知识。目前数据挖掘技术在货篮数据( b a s k e td a t a ) 分析、金 融风险预测、产品产量、质量分析、分子生物学、基因工程研究、i n t e r n e t 站点 访问模式发现以及信息搜索和分类等许多领域得到了成功的应用。一套金融风险 预测系统一年可以挽回数千万美元的损失：“深篮”计算机能够战胜人类国际象 棋世界冠军，成功的一个主要因素是具有知识发现能力，能从存储了7 0 万盘棋的 数据库中提取有用的知识：如果你通过i n t e r n e t 访问著名的亚马逊网上书店，会 发现当你选中一本书后，会出现“该书的购买者中有百分之几同时购买了某某书” 的推荐。可见，数据挖掘技术己经步入人们日常生活。因此，数据挖掘是应用需 求推动下跨学科发展的产物。 1 2 目前数据挖掘研究现状 1 2 1国外研究与应用现关 数据挖掘( d m ) 的实质是一种发现知识的应用技术，是一个提取有用信息的过 程。与数据挖掘意义相近的术语有数据开采、知识抽取、信息收集和信息发现等， 现在普遍采用的主要有数据挖掘和数据库中的知识发现( k d d ) 。k d d 一词最早出现 在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上，它是指从数据库中抽 取大量数据中隐含的、潜在的和有用的知识的过程。在1 9 9 3 年，i e e e 的k n o w l e d g e a n dd a t ae n g i n e e r i n g 会刊出版了k d d 技术专刊，发表的论文和摘要体现了当时 k d d 的最新研究成果和动态。目前k d d 的国际研讨会的数量和规模逐渐扩大，1 9 9 7 年数据挖掘和知识发现的国际学术刊物d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y 开始创刊，许多杂志刊物也为数据挖掘开辟了学术专栏，为该领域的研究与交流 提供了广阔的舞台。由于数据挖掘可以为企业构筑竞争优势，为社会带来巨大的 经济效益，一些国际知名公司也纷纷加入数据挖掘的行列，研究开发相关的软件 和工具。美国的i b m 公司于1 9 9 6 年研制了智能挖掘机i n t e l l i g e n tm i n e r ，用来提 供数据挖掘解决方案；s p s s 股份公司开发了基于决策树的数据挖掘软件 s p s s c h a i d ：思维机器公司在1 9 9 7 年开发t d a r w i n 这一数据挖掘套件，还有s g i 公司的m i n e r s e t ，s i m o nf r a s e r 大学的d b m i n e r ，m i c h a l s k i 等人的i n l e n n 儿踟 第l 章绪论 m _ in_ 等，o r a c l e 公司、s a s 公司和m a p i n f o 公司等也都开发了相关的产品蹭1 。此外，在 i n t e r n e t 上还有不少k d d 电子出版物，其中以半月刊k n o w l e d g ed i s c o v e r y n u g g e t s 最为权威，另一份在线周刊为d s ( 决策支持) ，1 9 9 7 年开始出版。自由论 坛d me m a i lc l u b 可以通过电子邮件讨论数据挖掘和知识发现的热点问题。数据 挖掘是数据库和信息决策领域的最前沿的研究方向之一，已引起了国内外学术界 的广泛关注。 1 2 2国内研究与应用现状 目前，国内k d d 已成为计算机科学工作者所关注的热点问题，同时也涌现出 一批优秀的研究成果。南京大学的徐洁磐、陈栋等人开发了一个原型系统： k n i g h t ，这是一个通用的d m - k 具，可用于处理不同领域的知识发现任务，主要有 聚类分析、特征知识发现、分类规则发现、关联规则发现、函数依赖发现及基于 查询的知识发现等：中科院软件所的史忠植研究员领导的课题组在d m 技术的研究 上也有大量成果，发表若干论文；李得毅院士、孟海军等人发表多篇论文n 伽。尽 管如此，目前我国在k d d 方面的理论研究和应用研究还是十分薄弱的。从事数据 挖掘理论研究和改进挖掘算法的不乏其人，但是如何将数据挖掘理论算法在实践 中有效的运用还有待迸一步的研究，国内目前也才刚刚起步。数据挖掘的实际应 用却并不乐观，主要是因为不同行业有着不同行业的规则，不能够通过个工具 或者一个算法来统一所用的挖掘，必须根据这个行业的规则和方法来为它进行专 门的挖掘。在进行数据挖掘应用时对行业规则和数据挖掘一定要同样的十分熟 悉，必须为这次挖掘应用选择适合的数据库和挖掘算法。所以，数据挖掘如何应 用到行业规则中成为数据挖掘成功与否的关键因素。因此，充分的理解行业的规 范和业务，成为数据挖掘成功的首选和必要的条件。 1 3 课题研究的背景及意义 高校本科招生工作作为高校教育的重要组成部分，直接关系到高校人才培养 的规模和质量。随着社会和经济的发展，以及我国高等教育大众化模式的深入， 越来越多的人有机会进入高等学校学习。那么在招生规模逐年扩大的今天，生源 竞争越来越激烈，招生录取己经成为高校名副其实的生命线。在这种情况下，做 好高校招生工作的研究，生源质量评价，显得尤为重要。 众所周知，数据挖掘技术在许多领域已取得了令人非常满意的应用，如零售 业、电信业、银行业等。那么随着招生工作信息化程度的逐步提高，尤其是网上 招生录取工作的普及，各校招生部门积累了大量的招生数据，这些数据往往只用 于一般的查询和打印等。事实上，在这些数据中隐藏了大量有用的知识，需要我 们应用数据挖掘这一新兴技术来发现，挖掘出来的知识可以辅助高校在招生工作 中进行决策，尤其是在科学地、有指针性地制定招生来源计划以及争取优质生源 北京丁业大学下学硕十学位论文 方面，从而促进招生工作的科学化。 本人作为高校招生工作的直接参与者，在从事具体工作的同时，也在反复地 思考，考生的基本情况、高考成绩、不同的录取方式、不同的生源范围等因素与 入学后学生的培养到底有多大的相关性? 高校在每年的高招录取时主要面对的 生源群有什么样的特征? 带着这些问题，本人准备应用数据挖掘技术对招生工作 做一些探索和研究，从而探寻更有利于人才培养的高校招生录取模式，为高校的 招生多样化选拔的实践探索提供参考性意见。 近年来，我国高等教育已经由精英式教育迈进了大众化教育阶段，但也随之 出现了一系列的问题，例如大学生每年因学习成绩差不能正常毕业的人数增加。 因此高校开始对学生入学时的生源质量提出了质疑，近年来相关部门及研究人员 对高等学校现行的招生录取体制进行了深层次的反思和讨论，但在我查阅的相关 资料中发现大多数的研究都是从定性分析、从理论的角度对当前的高考招生录取 制度进行评判或提出未来的设想。而做定量的分析的很少，并且很少有将各类学 生的入学情况和学生在大学培养结果结合起来，运用数据挖掘技术寻找他们之间 的内在相关性的。 数据挖掘技术在教育领域中的应用大约探索了有4 到5 年的时间n ，主要应 用于建议课程顺序、教学评价、学生生涯规划、学生管理、智能题库分析等方面 n 2 咀1n “屿1 ，本课题试图将数据挖掘技术应用于高校招生工作中。作者相信随着 关联分析、聚类、概念描述、偏差检测等技术的不断发展和完善，数据挖掘必将 在教育领域中发挥越来越大的作用，同时随着人们对这一技术的日益关注，数据 挖掘在教育领域的应用范围也会越来越广，从而快速推进教育的改革和发展。 1 4 论文的研究内容 本论文将着重对数据挖掘技术及其在高校招生工作中的应用进行研究，从而 为高校招生工作提供决策依据。将重点研究两种数据挖掘技术，分别为关联规则 和聚类分析。将详细分析：关联规则中的f p g r o w t h 算法和聚类分析中的基于图 论的方法。并利用北京第二外国语学院0 3 - 0 5 级高考统招、单独招生考生基本信 息和在校期间成绩等数据，通过关联规则分析及聚类分析，从不同的录取方式、 入学成绩、学生素质、来源地区等方面，对学生的入学信息与在校期间的培养、 就业情况等指标进行相关性分析和聚类分析，进而得出数据背后隐藏的有用信 息，并对得出的结论、招生工作中出现的问题以及对今后工作的指导等方面进行 分析。 1 5 论文组织结构 第一章是绪论部分，主要介绍了本论文的研究背景和研究意义，综述了数据 挖掘技术的理论渊源、以及国内外数据挖掘的发展情况。 4 第1 帝绪沦 第二章重点论述数据挖掘技术的相关理论及相关概念。主要介绍了数据挖掘 技术的定义、数据挖掘与相关学科的区别与联系、数据挖掘的功能、数据挖掘的 步骤等内容。 第三章着重论述关联规则算法，主要介绍关联规则的a p r i o r i 算法，并针对 该算法的缺陷介绍了a p r i o r i 算法的改进方法- - f p - t r e e 和f p - g r o w t h 算法。本 章是作者对数据挖掘技术在高校招生工作中应用的理论基础。 第四章论述了本论文所涉及到的挖掘技术一聚类分析。主要介绍了聚类分析 的相关概念，主要的聚类方法及基于图论的聚类方法。 第五章介绍利用数据挖掘技术的关联规则中的f p - t r e e 算法及聚类分析中 的基于图论的m e t i s 聚类方法，实现了数据挖掘技术在高校学生信息分析中的应 用，对数据挖掘技术应用到本科招生工作中进行了初步探讨。 第2 章数据挖掘技术 2 1数据挖掘定义 数据挖掘从产生至今已有多种定义，其中得到公认的是n 引：数据挖掘是从大 量数据中揭示出有效的、新颖的、潜在有用的，以及最终可理解的知识和模式的 非平凡过程。下面对一些概念作详细的解释： 数据：是一组事实f 的集合( 如关系数据库中的记录) ，它是描述事物有关方面 的信息，一般来说这些数据都是准确无误的。 模式：是一个用语言l 来表示的一个表达式e ，它可以用来描述数据集f 的某个 子集ff 。只有当表达式巨比列举的所有f ，中元素的描述方法更为简单时，才可以 称之为模式。例如：“如果温度在3 卜4 0 之间，则天气炎热 可称为一个模式， 而温度为“3 l ，3 2 ，3 3 ，3 4 ，3 5 ，3 6 ，3 7 ，3 8 ，3 9 ，4 0 ，则天气炎热”就不能 称之为一个模式。 过程：数据挖掘是一个多阶段的处理过程，它涉及数据预处理、模式提取、 知识评价及过程优化：该过程具有迭代的性质，而“非平凡的”是指其要有一定 程度的智能性和自动性。 有效的：是指发现的模式对于新的数据仍保持有一定的可信度，否则数据挖 掘就毫无意义。 新颖的：经过数据挖掘提取出的模式必须是新的。至少对系统来说应该如此。 模式是否新颖可以通过两个途径来衡量：其一是得到的数据，通过比较当前得到 的数据和以前得到的数据来判断该模式的新颖程度：其二是通过其内容所包含的 知识，通过对比发现的模式与已有的模式的关系来判断。通常我们可以用函数n ( e ，f ) 来表示模式的新颖程度，该函数的返回值是逻辑值或是对模式e 的新颖程 度的一个判断数值。 潜在有用：是指发现的知识将来有实际效用，如用于决策支持系统里可以提 高经济效益。 可理解：数据挖掘的一个目标就是将数据中隐含的模式能被用户理解，目前 它主要表现在简洁性上，从而帮助人们更好的了解数据库中所包含的信息。数据 挖掘不同于以往知识获取技术的一个特点是发现的知识是人们( 至少是领域专家) 可以理解的，如“i f t h e n 的形式，因此数据挖掘过程也是一个人机交互， 螺旋上升的过程。而以往的方法，如人工神经网络，不论是知识发现过程还是知 识应用过程，内部都是一个近“黑箱”过程。 其中，有效的、新颖的、潜在有用和可理解的综合在一起可称之为兴趣性。 7 北京1 = 业人学t 学硕十学位论文 2 2 数据挖掘与相关学科的区别与联系 2 2 1数据挖掘与数据库报表工具的区别 数据库报表制作工具是将数据库中的某些数据抽取出来，经过一些数学运算， 最终以特定的格式呈现给用户，而数据挖掘则是对数据背后隐藏的特征和趋势进 行分析，最终给出关于数据的总体特征和发展趋势。报表工具也许能制作出满足 下列要求的表格：上学期考试未通过及成绩优秀的学生有关情况。但它不能回答 下述问题：考试未通过及成绩优秀的学生在某些方面有些什么不同的特征? 而数 据挖掘就可以回答这个问题。 2 2 2 数据挖掘与传统数据分析工具的区别 数据挖掘与传统数据分析工具的主要区别在于它们探索数据关系时所使用 的方法。传统数据分析工具使用基于验证的方法，即用户首先对特定的数据关系 做出假设，然后使用分析工具去确认或否认这些假设。这种方法的有效性受到许 多因素的限制，如提出的问题和预先假设是否合适等。与分析工具相反，数据挖 掘使用基于发现的方法，运用模式匹配和其他算法决定数据之间的重要联系。 2 2 3 数据挖掘与机器学习的联系及区别 数据挖掘就是利用机器学习的方法从数据库中提取有价值的知识的过程，是 数据库技术和机器学习的交叉学科。数据库技术侧重于对数据存储处理的高效率 方法的研究，而机器学习则侧重于设计新的方法从数据中提取知识。数据挖掘利 用数据库技术对数据进行前端处理，而利用机器学习方法则从处理后的数据中提 取有用的知识。具体地说，数据挖掘与机器学习的不同在于： ( 1 ) 数据挖掘是从现实世界中存在的一些具体数据中提取知识，这些知识 在数据挖掘出现之前早已存在，但是人们往往没有意识到或没有明确这些知识的 存在t 而机器学习是一种有目的的“教”； ( 2 ) 由于数据挖掘使用的数据来自于实际的数据库，所要处理的数据量可 能很大，因此数据挖掘中学习算法的效率和可扩充性就显得尤为重要； ( 3 ) 数据挖掘所处理的数据来自于现实世界，数据的完整性、一致性和正 确性都很难保证，如何将这些数据；9 n - r 成学习算法可以接受的数据还需要进行深 入的研究； ( 4 ) 数据挖掘可以利用目前数据库技术所取得的研究成果来加快学习过程， 提高学习的效率； ( 5 ) 由于数据挖掘的数据自来于实际的数据库，而与这些数据库数据有关 的还有其他一些背景知识，这些背景知识的合理运用也会提高学习算法的效率。 第2 帝数据挖掘技术 苎! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 竺! ! ! ! ! ! 苎! ! ! ! ! ! ! ! ! ! ! ! ! 曼! ! ! ! ! ! ! ! ! ! ! ! ii 一 。 = 一m 1 i ! 曼 2 2 4 数据挖掘与联机分析处理( o l a p ) 的区别 o l a p t i 数据挖掘的功能可以视为不交的：o l a p 是数据汇总聚集工具，它帮助 简化数据分析；而数据挖掘自动发现隐藏在大量数据中的隐含模式和有趣知识。 o l a p 工具的目标是简化和支持交互数据分析，而数据挖掘的目标是尽可能的自动 处理，尽管允许用户知道这一过程。在这种意义下，数据挖掘比传统的联机分析 前进了一步。 另一种更广泛和能被接受的观点：数据挖掘包含数据描述和数据建模。由于 o l a p 系统可以提供数据仓库中数据的一般描述，o l a p 的功能基本上是用户指挥的 汇总和比较( 通过上钻、下钻、旋转、切片和其他操作) 。这些尽管有限，但都是 数据挖掘功能。 同样根据这种观点，数据挖掘的涵盖面要比简单的o l a p 操作宽的多，因为它 不仅执行数据汇总和比较，而且执行关联、分类、预测、时间序列分析和其它数 据分析任务。数据挖掘不限于分析数据仓库中的数据。它可以分析现存的、比数 据仓库提供的汇总数据粒度更细的数据。它也可以分析事务的、文本的、空间的 和多媒体数据，这些数据很难用现有的多维数据库技术建模。这种意义下，数据 挖掘涵盖的数据挖掘功能和处理的数据复杂性要l l o l a p 大得多。 由于数据挖掘涉及的分析比0 l a p 更自动化、更深入，数据挖掘应有更广的应 用范围。数据挖掘可以帮助商界经理们找到更合适的客户，也能获得对商务的洞 察，帮助提高市场份额和增加利润。此外，数据挖掘能够帮助经理们了解顾客的 群体特点，并据此制定价格策略：不是根据直觉，而是根据顾客的购买模式导出 的实际商品组来修正商品的排放；在降低推销商品开销的同时，提高总体推销的 纯效益。 2 3 数据挖掘的功能 数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖 掘的目标是从数据库中发现隐含的、有意义的知识，主要有以下六类功能晗： 2 3 1分类和预测 分类是这样的过程，它找出描述并区分数据类或概念的模型，以便能够使用 模型预测类，标记未知的对象类。在某些应用中，人们可能希望预测某些空缺的 或不知道的数据值，而不是类标记。当被预测的值是数值数据时，通常称之为预 测。一个典型的例子是市场预测问题，数据挖掘使用过去有关促销的数据来寻找 未来投资中回报最大的用户，其它可预测的问题包括预报破产以及认定对指定事 件最可能做出反应的群体。 9 北京下业大学t 学硕f ：学化论文 竺! ! 皇! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 皇! ! ! 詈! ! ! ! ! ! ! ! 苎! ! ! ! 苎! ! 苎竺! ! ! ! i ；二 一 i i ! ! ! ! ! 詈! 苎! ! ! ! ! ! 鼍 2 3 2关联分析 关联规则是发现在同一事件中出现的不同项的相关性，即寻找关联或相关的 关系。这些规则揭示了属性值频繁的、在同一数据集中同时出现的条件。比如： 经典的数据挖掘实例，超市对数据进行分析，意外地得出“啤酒和尿布”的关联 规则，就是购买啤酒的人往往也会购买尿布。关联分析广泛应用于购物篮或事务 数据分析。 2 3 3 聚类分析 聚类用于从数据集中找出相似的数据并组成不同的组。聚类分析增强了人们 对客观现实世界的认识，是概念描述和偏差分析的先决条件。聚类分析的目的是 要使类与类之间差别最明显，而同一个类之间的数据则尽可能地相似。聚类技术 主要包括划分方法、分层方法、基于密度的方法及基于图论的方法等等。 2 3 4 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概 念描述分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述 不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的 共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 2 3 5 演变分析 数据的演变分析是指描述行为随时间变化的对象的规律或趋势，并对其建立 数学模型。例如对股票交易数据的演变分析，可以识别整个股票以及某一公司的 股票交易演变规律。这种规律可以帮助预测未来股票市场的走向，以便对投资做 出正确的决策。 2 3 6 孤立点分析 数据库中可能包含一些数据对象，他们与数据的一般行为或模型不一致。这些 数据对象是孤立点。大部分数据挖掘方法将孤立点视为噪声或异常而丢弃。然而， 在一些应用中，罕见的事件可能比正常出现的那些更有意义。孤立点分析正是对 这些异常的数据进行分析，例如孤立点分析可发现信用卡欺骗。 2 4 数据挖掘的过程 数据挖掘的过程主要包括以下四个步骤n7 1 ： 2 4 1定义挖掘问题 在开始数据挖掘之前，最重要的就是了解现有数据和挖掘问题。要想充分发 挥数据挖掘的价值，必须要对目标有一个清晰明确的定义，即决定到底想干什么。 1 0 第2 章数据挖掘技术 清晰地定义出挖掘问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的最 后结果往往是不可预测的，但要探索的问题应是有预见的、有目标的。为了数据 挖掘而数据挖掘则带有盲目性，是不会成功的。 2 4 2 数据准备 这个阶段又可进一步分成3 个子步骤：数据集成、数据选择、数据预处理。 2 4 2 1数据集成数据挖掘可能涉及到内部多个数据源，还可能需要一些外 部的数据( 如人口统计、天气数据或信用卡使用数据等) ，这就需要将多个数据 源中的数据结合起来存放在一个一致的数据存储( 如数据仓库) ，以便于数据挖 掘操作。 2 4 2 2 数据选择这个阶段需要选择用于数据挖掘的数据( 即源数据的子 集) 。这与对数据进行采样和选择预测变量是不同的，这里只是粗略的把一些冗 余或无关的数据除去。有时，由于资源的限制、费用的限制、数据使用的限制和 数据质量等原因也必须对数据进行选择。 2 4 2 3 数据预处理主要是对上一阶段产生的数据进行再加工，检查数据的 完整性及数据的一致性，对其中的噪声数据进行处理，对丢失的数据可以利用统 计方法进行填补。对一些不适合于操作的数据进行必要的处理等。 2 4 3 数据挖掘 对经过转换的数据进行挖掘。除了完善并选择合适的挖掘算法外，其余一切 工作都能自动地完成。 2 4 4 模式评价和解释 在数据挖掘出现结果后，要对挖掘结果进行解释和评估。将挖掘出的结果以 一种易于理解的形式表示出来，并进行解释和评价。具体包括消除无关的、多余 的模式，过滤出要呈现给用户的信息；利用可视化技术将有意义的模式以图形或 逻辑可视化的形式表示，转化为用户可以理解的语言。一个成功的数据挖掘的应 用应能将原始数据转换为更简洁、更易理解、可明确定义关系的形式。此外还包 括解决发现的结果与以前知识的潜在冲突，及利用统计方法对模式进行评价，决 定是否需要重复以前的操作，以得到最优、最适合的模式。 2 5 本章小结 本章详细论述了数据挖掘技术的定义；将数据挖掘与数据库报表工具，数据 挖掘与传统数据分析工具，数据挖掘与机器学习，数据挖掘与联机分析处理 ( o l a p ) 进行了比较；最后介绍了数据挖掘的六大类功能以及数据挖掘一般要经 历的步骤。 第3 章关联舰则数据挖掘算法研究 鼍! ! ! ! ! ! ! ! ! ! i i l i。 一i =“=二i ii ! 曼苎! 皇 第3 章关联规则数据挖掘算法研究 关联规则挖掘的研究一直是数据挖掘领域的一个重要方向。关联规则挖掘的 目的是从大型事务数据库中挖掘出不同项目之间的关联关系，如果两项或多项属 性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测n 鲫n 引。 a g r a w a l 等人于1 9 9 3 年首先提出了挖掘交易数据库中项集间的关联规则问题乜0 | ， 以后诸多研究人员对关联规则的挖掘问题进行了大量的研究，他们的工作包括对 原有的算法进行优化，如引入随机采样、并行算法，已提高算法挖掘效率。关联 规则的发现可分为两步。第一步是迭代识别所有的频繁项目集，要求频繁项目集 的支持率不低于用户设定的最低值：第二步是从频繁项目集中构造可信度不低于 用户设定的最低值的规则乜门乜2 地3 仲引。识别或发现所有频繁项目集是关联规则发 现算法的核心，也是计算量最大的部分。关联规则是数据中一种简单但很实用的 规则。关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的算 法2 引。 3 1关联规则 定义l 嘶1 关联规则挖掘的事务数据库记为t d b ，t d b = t ，t ：，t 。) ， t 女= il ，i2 ，ip ，t 称为事务，i ，称为项目”。 定义2 乜6 1 设i = i ，i ：，i 。 是t d b 中全体项目组成的集合，”每一个事务t 是i 中一组项目的集合，即t i ，每个t 有一个唯一的标识符t z d ”。 定义3 乜目设项目集x 是i 中项目的集合，如果x 中有k 个项目，那么称x 的长度 为k ，记为k 项目集。 定义4 昭础如果项目集x c t ，则称事务t 满足项目集x ，项目集x 在事务数据库t d b 中的支持度，记为s u p p o r t ( x ) ，即事务数据库t d b 中满足项目集x 的事务数占总 事务数的比例。 定义5 堙6 3 如果项目集x 在事务数据库t d b 中的支持度不小于用户或专家给定的 最小支持度阈值，那么称项目集x 为频繁项目集，反之称为非频繁项目集。 定义6 乜町一条关联规则就是形如x y 的蕴涵式，其中x c _ 工，y i ，x n y = 矽，x 称 为规则的前件，y 称为规则的后件。关联规则x y 成立的条件是满足： ( 1 ) 支持度s ，即事务数据库t d b 中至少s 个事务包含x uy ： 北京t 、i k 人学丁学顶f ”y - 位论文 ( 2 ) 置信度c ，c = s u p p o r t ( xuy ) s u p p o r t ( x ) ，即事务数据库t d b 包含x 的事 务中至少有c 的事务同时也包含y 。 关联规则挖掘可以分解为下列两个子问题乜引： ( 1 ) 找出所有频繁项目集，这些项目集在t d b 中的支持度不小于最小支持度 ( m i n s u p ) ： ( 2 ) 由频繁项目集产生强关联规则，这些规则必须满足最小置信度 ( m i n c o n f ) 。 目前所有的关联规则挖掘算法都是针对第一个问题提出的，其中以算法 a p r i o r i 为代表。 3 2 a p r ior i 算法 3 2 1 a p rio r 算法：使用候选项集找频繁项集 a g r a w a l 等人在1 9 9 4 年提出了a p r i o r i 算法例，该算法是 一种最有影响的挖掘布尔关联规则频繁项集的算法，它采用逐层迭代的方法自底 向上进行搜索，就是先找出l 频繁项目集，记为l 。，再利用l ，找到2 一频繁项目集 l ：，依此类推，直至不能找长度更大的频繁项目集，找每个l 。需要一次数据库扫 描。a p r i o r i 算法定义了一个关键的过程a p r i o r i g e n ( l t ) 用来从l t 中产生lk + i ， 该过程由连接和剪枝组成。 ( 1 ) 连接：首先，利用l k 与自身连接产生k + l 候选项目集的集合，记为c 。 为叙述方便，先假设项目集中项目按字典顺序排列，设l ，和l ：为l 。中的项目 集，l 。 j 表示l 。的第j 个项目。如果两个项目集前( k 1 ) 个项目相同，那么就满 足连接条件，即如果( ( l l 1 = l2 1 ) a ( l 。 2 = l2 2 ) a ( l l k 一1 = l2 k 一1 ) a ( l 。 k l2 k ) ) ，那么项目集l l 和l2 是可连接的，条件 ( l l k l ： k ) 是保证不重复连接。连接l 。和l2 产生的候选项目集是 ( l 。 1 ，l ， 2 ，“l ， k ，l2 k ) 。 ( 2 ) 剪枝：所有的k + l 频繁项目集都包含在候选项目集c 中。先根据 a p r i o r i 性质：任何非频繁的( k - i ) 一项集都不可能是频繁