（通信与信息系统专业论文）数据挖掘技术在毕业生就业工作中的应用研究.pdf

中文摘要 中文摘要 近年来我国高等院校的就业问题不断突现，原因不仅包括经济改革、高等院 校扩招、教育资源紧缺、就业模式不健全等，还包括高等教育模式不适应社会要 求的重要因素。深化高等教育改革、改进高效学生培养模式已刻不容缓。 本文试图通过数据挖掘技术，发现学生的教育属性和就业属性之间的关联性， 找出社会需要的应用型人才的模型，从而给决策者提供指导或数据支持，改进现 有的教育模式。 关联规则挖掘是数据挖掘的重要内容之一对于群体的特征与行为的数据挖 掘是关联规则挖掘的一个重要同时也是非常复杂的一个方向。如学生就业系统中 学生个体自然信息与他们就业行为之间的关联倾向就属于这类情况。而目前很多 通用的数据挖掘工具，基于对更通用的挖掘需要的考虑，并没有能对上述的挖掘 需求给予足够的支持。本文通过研究多维关联规则数据挖掘技术，基于已有算法， 针对算法中存在的不足进行改进，实现了一种基于维间多维关联规则数据挖掘的 高效实用的方法。在通过掌握实际的学生信息基础上，测试了该方法的有效性， 并建立了一个基于关联规则的就业分析系统。 本文的就业分析系统由两部分构成，数据库处理和数据挖掘算法执行。数据 库处理包括数据的读取、查询、统计、更新以及前台的简单系统界面等，采用 m i c r o s o f t a c c e s s2 0 0 3 。数据挖掘算法执行就是采用我们改进后的a p r i o r i 算法。将 实际学生就业数据作为输入处理，得出很多有意义的信息，这些知识在帮助高等 院校更好的进行学生培养、对学生表现情况的掌握以及课程的安排等方面无疑具 有重要的指导意义。 关键词：数据挖掘，关联规则，多维频繁项集 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，t h ee m p l o y m e n tp r o b l e m so fu n i v e r s i t yg r a d u a t e si no b rc o u n t r y a p p e a r e du n c e a s i n g l y , t h e r e a s o ni sn o to n l yt h ee c o n o m yr e f o r m ，e n l a r g i n gt h es c a l eo f e n r o l l m e n t , t h el a c ko fe d u c a t i o nr e s o u r c e , a n dt h ei m p e r f e c te m p l o y m e n tm o d e l ，b u t a l s ot h eu n s u i t e dm o d e lo fh i g h e re d u c a t i o n i ti su r g e n tt h a tw ed e e p e n st h eh i g h e r e d u c a t i o nr e f o r m , a n da m e l i o r a t e st h ee d u c a t i o nm o d e lo fu n i v e r s i t y t h eu n i v e r s i t i e s a n dc o l l e g e sn p 宅d st of a c et h es o c i e t ya n dt r a i nt h ea p p f i c a t i o ns t u d e n t s i nt h i sa r t i c l ew ea t t e m p t st od i s c o v e rt h ea s s o c i a t i v e 忙l m i o n sb e t w e e nt h e e d u c a t i o na t t r i b u t e sa n dt h ee m p l o y m e n ta t t r i b u t e so fg r a d u a t e sa n df i n dt h et y p eo f a p p l i c a t i o np e r s o nw h i c ht h es o c i e t yn e e d st h r o u g ht h e d a t am i n i n gt e c h n o l o g y a s s o c i a t i o nm l e sm i n i n gi so n eo fi m p o r t a n tm a t t e r so fd a t am i n i n g m i n i n gd a t a b e t w e e np e o p l ec h a r a c t e r sa n dt h e i ra c t i o n si sa ni m p o r t a n ta s p e c tf o rm u l t i d i m e n s i o n a l a s s o c i a t i o nr u l e s f o re x a m p l e ，a s 8 0 c i a f i o nt r e n db e t w e e ns t u d e n t s n a t u r ei n f o r m a t i o n a n dt h e f tb e h a v i o r b u tm a n yg e n e r a lm i n i n gt o o l sh a v en o tp a i dm u c ha t t e n t i o nt ot h e s e a s p e c t s i nt h i sp a p e r w em a i n l yr e s e a r c h e dm u l t i d i m e n s i o n a la s s o c i a t i o nm l e sm i n i n g , a n dp r o p o s eam o r ee f f i c i e n tm e a l 岱w h i c hi sb a s e do nt h eo r i g i n a la l g o r i t h mi n m u l t i d i m e n s i o n a la s s o c i a t i o nr u l e sm i n i n g a n du s i n gt h em e i n s , w ed e s i g nas y s t e mt o a n a l y z et h er u l e so fu n d e r g r a d u a t ee m p l o y m e n t t h es y s t e mm a i n l yi n c l u d e st w op a r t s ：t h em a n i p u l a t i o no fd a t a b a s e ( a c c e s s i n g 、 q u e r y i n ga n du p d a t i n gt h ed a t a b a s e ) a n dm i n i n gd a t ai nt h eb a c k g r o u n d i ti sb a s e do n m i c r o s o f ta c c e s s2 0 0 3d a t a b a s ea n dt h ec o r ea l g o r i t h mo fd a t am i n i n gi si m p r o v e d a p r i o r ia l g o r i t h m a f t e ra n a l y z i n gt h ed a t ao fu n d e r g r a d u a t ee m p l o y m e n t , t h es y s t e m c a ng i v eu ss o m em e a n i n g f u lg u l e s ，w h i c hw i l ls h o wt h er e l a t i o n s h i pb e t w e e nt h e s t u d e n t sb e h a v e di nu n i v e r s i t ya n do b t a i n e de m p l o y m e n ti n f o r m a t i o na f t e rg r a d u a t e d a n dc a nh e l pa u t h o r i t yc o n c e r n e dm a k eb e t t e rd e c i s i o nt oa s s i s tt h es t u d e n t st of i n da j o b k e y w o r d s ：d a t am i n i n g , m u l t i d i m e n s i o n a lf r e q u e n ti t e m ss e t ，a s s o c i a t i o nr u l e s 图目录 图目录 图2 - 1 数据挖掘视为知识发现的一个步骤7 图2 - 2 f a y y a d 过程模型 图2 - 3c r i s p d m 过程模型 图4 1 系统简单模型 图4 2 关系数据库表 图4 3 属性概化图 3 2 图4 4 频繁谓词挖掘流程 图4 _ 5 基于a p i o r i 算法求多维频繁谓词流程图 图4 6 改进后的a p r i o r i 算法流程图 图4 7 强关联规则流程图 图犏相关性分析流程图 3 6 4 2 4 3 图4 _ 9 智育成绩高学生就业示意图5 3 图4 - 1 0 智育成绩中学生就业示意图 一 5 3 表目录 表目录 表2 - 1 学生基本信息数据库示意1 0 表2 2 学生就业信息数据库示意1 0 表2 - 3 预处理后的学生基本信息表1 1 表2 - 4 学生事务信息表1 1 表3 - 1 简单的学生信息表示意2 1 表3 - 2 学生生源信息数据库2 6 表3 - 3 学生成绩数据库2 6 表3 4 学生就业信息数据库2 6 表3 5 学生信息总表2 6 表3 - 6 预处理后的学生信息表2 9 表4 1 生源信息表3 5 表4 2 学生成绩表3 5 表4 3 就业信息表3 5 表4 - 4 学生信息总表3 7 表禾5 经过数据预处理后的学生信息事务表加 表4 6 谓词集表4 1 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：日期：石7 年g 月工日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 导师签名：3 座翔垒 日期：如7 年易月2 - e t 第一章引言 第一章引言 近年来，随着数据库信息量的急剧增长和存储设备的不断升级，产生了大量 的数据，这对我们对数据的分析、综合和抽取“知识”的能力提出了更高的要求。 人们通过传统方法所获得的存在于这些数据中的信息量仅仅是整个数据库所包含 信息的一小部分，即数据的表层信息，然而隐藏在这些数据之后的更重要的信息 是关于这些数据的整体特征的描述及对其发展趋势的预测等信息，即知识，是我 们无法用传统方法来获取的。为了处理这些数据，开发新一代能够“自动地”、“智 能地”分析处理这些海量原始数据的工具显得非常必要。于是数据挖掘技术应运 而生，并成为一个新兴的、在数据库和信息决策领域处于前沿研究的方向之一。 数据挖掘方法的提出，让人们有能力最终认识数据的真正价值，即蕴藏在数据中 的信息和知识，这些知识是隐含的、事先未知的潜在有用的信息。 目前，在我国教育软件市场里，专门针对学生各种数据进行挖掘从而发现智 力与德育、智育与体育、乃至于综合素质与工作问的关系、预测学生发展轨迹和 智能评价的信息系统几乎空白。随着经济发展社会进步，高等教育深入发展，招 收人数不断增加，使得毕业生数量逐年递增，已经超过经济发展带来的社会新增 就业岗位的增加。同时，经济的高速发展，使得传统的高等教育已跟不上社会对 人才的需求，高等教育改革迫在眉睫。人们一致认为大学本科阶段教育就是要培 养社会需要的应用型人才，然而什么样的方法可以达到这一目的，目前尚无定论。 在高等院校中，存在着大量的学生个人的教育信息和就业信息。对于教育信 息，一部分和教学相关，如学业成绩、获奖情况等；一部分和非智力因素有关， 如学生的性别、身体状况、心理因素等。毕业生就业信息则可能包括企业地域、 企业性质、职位、行业、薪资待遇等。尤其是近年来，信息化的推进使得学生信 息库极其丰富。但这些资料都没有或很少被利用，学校在制定学生的培养方式时 较少的利用这类信息。如果能从这类信息中找到一个一般规律，启发相应管理者 注意哪些学生应注重哪些方面，则会起到相当好的效果。本课题就是从这个思想 出发，研究学生个人的信息和最终就业的情况，挖掘出其中隐藏的信息，更正以 前某些可能错误的观点。 电子科技大学硕士学位论文 1 1 数据挖掘研究现状 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知 识的过程1 t j 。还有很多和这一术语相近似的术语，如从数据库中发现知识( k d d ) 、 数据分析、数据融合( d a t af u s i o n ) p _ j , 及决策支持等。人们把原始数据看作是形成 知识的源泉，就像从矿石中采矿一样。原始数据可以是结构化的，如关系型数据 库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网 络上的异构型数据。发现知识的方法可以是数学的，也可以是非数学的；可以是 演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优化、决策 支持、过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门广义的 交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、 可视化、并行计算等方面的学者和工程技术人员。 知识发现k d d 一词首次出现在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能 学术会议上。迄今为止随着k d d 在学术界和工业界的影响越来越大，国际k d d 组委会于1 9 9 5 年把专题讨论会更名为国际会议，在加拿大蒙特利尔市召开了第一 届k d d 国际学术会议，以后每年召开一次。迄今为止，由美国人工智能协会主办 的k d d 国际研讨会已经召开了1 3 次，人数由二三十人发展到现在的七八百人。 研究重点也逐渐从发现方法转向系统应用，并且注重多种发现策略和技术的集成， 以及多种学科之间的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列 为议题之一，成为当前计算机科学界的一大热点。 1 9 9 7 年亚太地区在新加坡组织了第一次规模较大的p a k d d 学术研讨会，很有 特色。此外，数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也 纷纷开辟了k d d 专题或专刊。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 会刊领先 在1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论文代表了当时k d d 研究的最新 成果和动态，较全面地论述了k d d 系统方法论、发现结果的评价、k d d 系统设 计的逻辑方法，集中讨论了鉴于数据库的动态性冗余、高噪声和不确定性、空值 等问题，k d d 系统与其它传统的机器学习，专家系统、人工神经网络、数理统计 分析系统的联系和区别，以及相应的基本对策。 随着d m k d 研究逐步走向深入，人们越来越清楚地认识到，d m k d 的研究主 要有3 个技术支柱，即数据库、人工智能和数理统计。数据库技术在经过了8 0 年 代的辉煌之后，已经在各行各业成为一种数据库文化或时尚。数据库界目前除了 2 第一章引言 关注万维网数据库、分布式数据库、面向对象数据库、多媒体数据库、查询优化 和并行计算等技术外，已经在开始反思，数据库最实质的应用仅仅是查询吗? 理 论根基最深的关系数据库最本质的技术进步点，就是数据存放和数据使用之间的 相互分离。查询是数据库的奴隶，发现才是数据库的主人l 这是很多工作者在热 心数据库建设后发出的感叹。 由于数据库文化的迅速普及，用数据库作为知识源具有坚实的基础；另一方面， 对于一个感兴趣的特定领域客观世界，先用数据库技术将其形式化并组织起 来，就会大大提高知识获取起点，以后从中发掘或发现的所有知识都是针对该数 据库而言的。因此，在需求的驱动下，很多数据库学者转向对数据仓库和数据挖 掘的研究，从对演绎数据库的研究转向对归纳数据库的研究。专家系统曾经是人 工智能研究工作者的骄傲。专家系统实质上是一个问题求解系统，目前的主要理 论工具是基于谓词演算的机器定理证明技术= 阶演绎系统。领域专家长期以 来面向一个特定领域的经验世界，通过人脑的思维活动积累了大量有用信息。在 研制一个专家系统时，知识工程师首先要从领域专家那里获取知识，这一过程实 质上是归纳过程，是非常复杂的个人到个人之间的交互过程，有很强的个性和随 机性。因此，知识获取成为专家系统研究中公认的瓶颈问题。 当前，数据挖掘在各行各业都有众多应用，是当今最热门的技术之一。研究焦 点集中在以下几个方面；研究专门用于知识发现的数据挖掘语言，像s q l 语言一 样走向形式化和标准化；寻求数据挖掘过程中的可视化方法，使得知识发现的过 程能够被用户理解，也便于在知识发现过程中的人机交互；研究在网络环境下的 数据挖掘技术，特别是在b l 哪c t 上建立d m k d 服务器，与数据库服务器配合， 实现数据挖掘；加强对各种非结构化数据的挖掘，如文本数据、图形图像数据、 多媒体数据。但是，无论怎样，需求牵引，市场驱动是永恒的，d m k d 将首先满 足信息时代用户的急需，大量基于d m k d 的决策支持软件工具产品将会问世。数 据挖掘技术最先应用于金融和商业领域，在教育领域的应用现在仍处于初级阶段， 现在基于教育教学管理信息系统的数据挖掘应用有判定树法、聚类分析法、多维 关联规则法等。 1 2 关联规则研究现状 在交易数据项目之间挖掘关联规则【2 l 【3 】【4 】的问题是ra g 姐w a l 等人首先引入 的。典型的关联规则的例子就是“9 0 的顾客在购买面包和黄油的同时也会购买牛 3 电子科技大学硕士学位论文 奶”。挖掘关联规则的算法已经有很多，比较重要的是a g r a w a l 等人提出的a p f i o f i 算法，以后诸多的研究人员对关联规则挖掘算法进行了大量的研究和优化。如 s a v 猫c 心等人设计了一个基于划分0 a n i t i o n ) 的算法【5 l 。p a r k 等人提出的基于杂凑 ( h a s h ) 的算法、m a n n i l a 提出的基于采样的方法嘲，l i n 和d u n h a m 提出的反扭曲 ( a n t i s k e w ) 算法、b d n 等提出的算法使用比传统算法少的扫描遍数来发现频集。随 着关联规则挖掘被大量的应用，研究人员先后提出了关联规则的若干种变体： s r i k a n t 等引入了泛化关联规则川，a m i r 等提出了排除关联规则，s a v a s e r e 提出了否 定关联规则i 卯，o g d e n 提出的周期关联规则、r s d k a m 等提出的数量关联规则川， t u n g 提出的交易阋联系规则。 关联规则的应用包括附加邮递、目录设计、追加销售、仓储规划以及基于购 买模式对顾客进行划分等。更广泛一些，关联规则在其它领域也可以得到应用， 比如医学研究人员希望从已有的成千上万份病历中找出患某种疾病的病人的共同 特征，从而为治愈这种疾病提供一些帮助。这些应用中的数据库都是极其庞大的， 因此，不仅需要设计高效的算法来挖掘关联规则，而且如何维护和更新这些规则， 如何确认这些规则是否有价值，如何在分布式数据库中进行关联规则的挖掘等等 这些问题都必须得以解决。 关联规则分为基于事务数据库德单维关联规则和基于关系数据库的多维关联 规则。其中多维关联规则又可分为维间多维关联规则和混合维关联规则。关联规 则挖掘性能的关键主要体现在频繁项集的挖掘算法的性能上。由于关联规则是数 据挖掘中一种重要的模式，许多解决策略不断被提出。其中比较著名的是以连接 和剪枝的方法获取候选集进而获得频繁项集的a p d o r i 算法，以及基于a p f i o f i 算法之 上的一些改进算法，如划分和事务压缩等方法。本文运用的算法也是基于a p r i o r i 算法的改进算法。 1 3 研究的现实意义 本文中要建立一个基于学生信息的关联规则挖掘系统。通过对学生的招生信 息、在校表现和就业信息的挖掘获得对校方培养学生、了解学生的有用信息。把 数据挖掘这样一门新兴技术应用到学生管理工作中，这在大力提倡科教兴国的今 天无疑具有重要意义。要建立的学生信息管理系统分为前台的数据库处理和后台 的联机分析挖掘两部分。本文中的工作主要集中在后台的挖掘系统部分。通过在 学生信息管理系统中的具体实践和运用，对多维关联规则数据挖掘技术进行了探 4 第一章引言 索，实现了基于多维频繁项集进行关联规则数据挖掘的一种实用高效的方法。 本文从我们掌握的大量实际的学生个人信息和就业数据出发，利用改进的关 联规则算法，挖掘其中内在的、不易发现的对高校教学、就业工作具有指导价值 的信息。如果将其应用于高校实际的管理决策之中，具有极其重要的现实意义。 5 电子科技大学硕士学位论文 第二章数据挖掘概述 本章介绍本课题涉及到的相关的数据挖掘基本概念与技术。 2 1数据挖掘基本概念 2 1 1 什么是数据挖掘 简单的说，数据挖掘就是从大量数据中提取或“挖掘”知识。解决这样一个 问题：我们掌握了大量的数据，但是我们的知识却很贫乏，如何从这些数据中提 取出有用的知识，利用这些知识解决后续的问题。通常，数据挖掘可被定义为： 从大量的、不完全的、有噪声的、模糊的、随机的数据中识别有效的、新颖的、 潜在有用的及最终可理解的模式的过程。它是一门交叉学科，涉及多个领域，如 数据库技术、人工智能、机器学习、神经网络、统计学、模式识别、知识库系统、 知识获取、信息提取、高性能计算和数据可视化等等。 2 1 2 数据挖掘和知识发现 很多人将数据挖掘视为另一种常用的术语数据库中的知识发现【1 1 或k d d 的同 义词。而有些人将数据挖掘仅仅视为知识发现过程中的一个步骤。知识发现过程 如图2 - 1 所示，由以下步骤组成： 一6 第二章数据挖掘概述 图2 - 1 数据挖掘视为知识发现的一个步骤 ( 1 ) 数据清理：清除噪声或不一致数据； ( 2 ) 数据集成：多种数据源可以组合在一起； ( 3 ) 数据选择：从数据库中检索与分析任务相关的数据； ( 4 ) 数据变换：数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作； ( 5 ) 数据挖掘：基本步骤，使用智能方法提取数据模式； ( 6 ) 模式评估：根据某种兴趣度度量，识别表示技术，向用户提供挖掘的知识； ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 以上是将数据挖掘看成知识发现的一个步骤，我们觉得这样理解比较合理， 但是在产业界和数据库研究界，数据挖掘比知识发现更流行，故我们将数据挖掘 视为知识发现的同义词，且只使用数据挖掘这一术语。 2 2 数据挖掘功能 数据挖掘功能用于指定数据挖掘人物中要找的模式类型。数据挖掘任务一般 可以分为两类田j ：描述和预测。描述性挖掘任务刻画数据库中数据的一般特性。 预测性挖掘任务在当前的数据上进行推断、预测。数据挖掘系统要能够挖掘多种 类型的模式以适应不同的用户需求或不同的应用，且应当能够发现各种粒度( 即不 同的抽象层) 的模式口l 。由于有些模式并非对数据库中的所有数据都成立，通常每 个被发现的模式带上一个确定性或“可行性”度量。数据挖掘功能以及他们可以 7 电子科技大学硕士学位论文 发现的模式类型介绍如下。 2 2 1概念类描述：特征化和区分 数据可以和类或概念相关联。数据特征化( d a t ac h a r a c t e d z a t i o n ) 是目标类数据 的一般特征或特性的汇总。通常，用户指定类的数据通过数据库查询收集。有许 多有效的方法将数据特征化和汇总，如基于数据立方体的o l a p 上卷操作等。数 据特征的输出可以用多种形式提供，包括饼图、条图、蓝线、多维数据立方体和 包括交叉表在内的多维表。结果描述也可以用概化关系( g e n e r a l i z e dr e l a t i o n ) 或规则 形式( j 际作特征规则) 提供。 数据区分( d a t ad i s c r i m i n a t i o n ) 是将目标类对象的一般特性与一个或多个对比类 对象的一般特性比较。目标类和对比类由用户指定，而对应的数据通过数据库查 询检索。区分的输出形式类似于特征描述，但区分描述应当包括比较度量，帮助 区分目标类和对比类。用规则表示的区分描述称为区分规贝i j ( d i s c r i m i n a n tr u l 曲。用 户应当能够对特征和区分描述的输出进行操作。 2 2 2关联分析 关联分析( a s s o c i a t i o na n a l y s i s ) 用于发现关联规则( a s s o c i a t i o nr u l e ) ，这些规则展 示属性值频繁的在给定数据集中一起出现的条件。更形式的，关联规则是形如 x y ，即“4 弘且且a 一日且岛且只”的规则，其中4 ( f l m ) 、 曰，( ，= 1 ，1 ) 是属性值对。关联规则x 哮y 解释为“满足x 中条件的数据库元组 大多也满足y 中条件”。关联规则根据规则中属性个数可分为单维关联规则 ( s t o 酉c d i m e n s i o n a la s s o c i a t i o n a lr u l e ) 和多维关联规则( m u l t i d i m e n s i o n a la s s o c i a t i o n r u l e ) 。 2 2 3 分类和预测 分类( c l a s s i f i c a t i o n ) 是为了找出描述并区分数据类或概念的模型，以便能够使 用模型预测类标记未知的对象类。导出模型是基于对训练数据集的分析。导出模 型可以用多种形式表示，如分类( w - t r l 规则、判定树、数学公式或神经网络。 判定树是一种类似于流程图的树结构，每个节点代表一个属性值上的测试，每个 分支代表测试的一个输出，树叶代表类或类分布。判定树容易转换成分类规则。 当用于分类时，神经网络是一组类似于神经元的处理单元，单元之间加权连接。 8 第二章数据挖掘概述 分类可以用来预测数据对象的类标记。然而，在某些应用中，人们可能希望 预测某些空缺的活不知道的数据值，而不是类标记。当被预测的值是数值数据时， 通常称之为预测( p r c d i c a t i ) 。尽管预测可以涉及数据值预测和类标记预测，通常 预测限于值预测，并因此不同于分类。预测也包含基于可用数据的分布趋势识别。 相关分析( r e l e v a n c ea n a l y s i s ) 可能需要在分类和预测之前进行，它试图识别对 于分类和预测无用的属性，这些属性应当排除。 2 2 4 聚类分析 聚类( c l u s t e r i n g ) 分析数据对象，而不考虑已知的类标记。一般情况下，训练数 据中部提供类标记，因为不知道从何开始。聚类，可以用于产生这种标记。对象 根据最大化类内的相似性、最小化类间的相似性的原则进行聚类或分组。即对象 的簇( 聚类) 这样形成，它使得在一个簇中的对象具有和高的相似性，而与其他簇中 的对象很不相似。所形成的每个簇可以看成一个对象类，由它可以导出规则。聚 类也便于分类编制( t a x o n o m yf o r m a t i o n ) ，将观察到的内容组织成类分层结构，把类 似的事件组织在一起。 2 2 5 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这 些数据对象是孤立点( o u t l i e r ) 。大部分数据挖掘方法将孤立点视为噪声或异常而丢 弃。然而，在一些应用中( 如欺骗检测) ，罕见的事件可能比正常出现的那些更有趣。 孤立点数据分析称作孤立点挖掘( o u t l i e rm i n i n g ) 。 孤立点可以使用统计试验检测。它假定一个数据分布或概率模型，并使用距 离度量，到其它聚类的距离很大的对象被视为孤立点。基于偏差的方法通过考察 一群对象主要特征上的差别识别孤立点，而不是使用统计或距离度量。 2 2 6 演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时问变化的对象的规律或趋势，并 对其建模。尽管这可能包括时间相关数据的特征化、区分、关联、分类或聚类， 这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于类似性 的数据分析。 9 电子科技大学硕士学位论文 2 3 挖掘的数据类型 原则上讲，数据挖掘可以在任何类型的数据存储上进行。这包括，关系数据 库、数据仓库、事务数据库、高级数据库系统、展开文件和w w w 。高级数据库 包括面向对象和对象关系数据库；面向特殊应用的数据库，如空间数据库、时间 序列数据库、文本数据库和多媒体数据库。挖掘的挑战和技术可能因存储系统而 异。 2 3 1 关系数据库 数据库系统，也称数据库管理系统p b m s ) ，由一组内部相关的数据( 称作数据 库1 和一组管理和存取数据的软件程序组成。关系数据库是表的集合，每个表包含 一组属性( 列或字段) ，并通常存放大量元组( 记录或行) 例如，就业信息系统中我们给出以下的非常重要的关系数据库： 表2 1 学生基本信息数据库示意 姓名 学号 专业生源地英语水平学分绩 张三2 2 0 0 0 0 1通信工程四川六级 9 0 李四 2 2 0 0 0 0 2通信工程 重庆四级 8 4 表2 - 2 学生就业信息数据库示意 姓名就业号单位名称单位性质单位所在地类别 张三 2 2 0 0 0 0 12 9 所 国营二级城市 李四2 2 0 ( ) 0 0 2华为民营一级城市 2 3 2 数据仓库 数据仓库是从多个数据源收集的信息存储，存放在一个一致的模式下，并通 常驻留在单个站点。数据仓库通过数据清理、数据变换、数据集成、数据装入和 定期数据刷新来构造。通常，数据仓库用多维数据库结构建模。其中，每一维对 应模式中的一个或一组属性，每个单元存放某个聚集度量值，如c o u n t 。数据仓库 的实际物理结构可以是关系数据存储或多维数据立方体。微软公司的o l a p 一1 0 第二章数据挖掘概述 s e r v i c e s 要求数据仓库具有个非常特殊的表单，即以一个实际表格为特征的表 单。为了便于o l a p s e r v i c e s 的使用，实际表格必须包含能够展现所需的量度的最 底层的细节的行。例如，在学生信息系统中最后应通过对数据的预处理形成类似 如下格式的表单： 表2 - 3 预处理后的学生基本信息表 学号专业生源地类别计算机水平英语水平学分绩 2 2 0 0 0 0 11l11a 2 2 0 0 0 0 2l122b 2 3 3 事务数据库 事务数据库由一个文件组成，其中每个记录代表一个事务。通常，一个事务 包含一个唯一的事务标识号f r m si d ) ，和一个组成事务的项的列表( 如学生的学科 信息) ，在学生信息系统中，存在一张学生事务信息表： 表2 _ 4 学生事务信息表 i 学号学业成绩i 2 2 0 0 0 0 19 0 2 2 0 0 0 0 28 4 l 2 3 4 高级数据库系统和高级数据库应用 关系数据库系统广泛的应用于商务应用。随着数据库技术的发展，各种高级 数据库系统已经出现并在开发中，以适应新的数据库应用需要。新的数据库应用 包括处理空间数据、工程设计数据、超文本和多媒体数据及w w w 等。这些应用 需要有效的数据结构和可伸缩的方法，处理复杂的对象结构、变长记录、半结构 化或无结构的数据以及文本和多媒体数据，并具有复杂结构和动态变化的数据库 模式。为了响应这些应用需求，开发了高级数据库系统和面向特殊应用得数据库 系统。包括面向对象和对象关系数据库系统、空间数据库系统、时间和时间序列 数据库系统、文本和多媒体数据库系统、异种和遗产数据库系统、基于w w w 的 全球信息系统。 一1 1 电子科技大学硕士学位论文 2 4 数据挖掘过程模型 数据挖掘需要遵循一定的过程模型。常见过程模型有两个，下面分别基于介 绍、分析。两者各自有各自的优缺点，在应用时应根据实际需要选择。 f a y y a d 过程模型【8 l 如图2 - 2 所示： 数据准备 数据挖掘结果表达和解析 图2 - 2f a y y a d 过程模型 c r i s p o d m 的过程模型【9 1 如图2 - 3 所示： 图2 - 3c r i s p - d m 过程模型 c r i s p d m 过程模型和f a y y a d 相似，但有两方面的改进，一是更加紧密地和 实际业务联系在一起，二是更加强调整个数据挖掘过程是一个不断循环不断改进 的过程，后续的工作可能会发现新的商业问题和解决方案。 以前的数据挖掘过程大多是f a y y a d 模型，但后来随着商业应用需求的增加， c r i s p d m 模型成为新宠。由于我们的工作单一性和研究性的特点，我们采用了 f a y y a d 模型。 1 2 第二章数据挖掘概述 2 5数据挖掘常用技术 正如前面所介绍的那样，数据挖据可以实现多种功能，如特征化和区分、关 联分析、分类和预测、聚类分析、孤立点分析、演变分析以及其他，不同的功能 的实现技术会因功能的内在差异而不同。 2 5 1 人工神经网络 人工神经网络1 1 0 l ( a n n ，a r t i f i c i a ln e u r a ln e t w o r k ) 是反映人脑结构及功能的 一种抽象数学模型，一个人工神经网络是由大量神经元节点互连而成的复杂网络， 用以模拟人类发现知识和进行知识表示与存储以及利用知识进行推理的行为。人 工神经网络为解决复杂网络提供了相对简单的方法，常用于分类和回归，只能处 理数值型数据。 人工神经网络技术、模糊信息处理技术和进化计算等构成为当前智能计算的 的主流技术。由于人工神网络所固有的分布记忆和快速并行计算能力，使得它已 经成为知识发现与数据挖掘的一种重要方法。与其他数据挖掘方法不同，将神经 网络技术用于数据挖掘，要解决好两个关键问题：一是降低网络学习训练的时间； 二是挖掘结果的可理解性，即对挖掘结果的解释。 有三大类人工神经网络模型： 前馈式网络，以感知机、b p 反向传播网络、函数型网络为代表，用于预测、 模式识别等； 反馈式网络，以h o p f i e l d 的离散模型和连续模型为代表，分别用于联想记忆 和优化计算； 自组织网络，以a p t 模型、k o h o n e n 模型为代表，用于聚类。 神经网络的优势是可以根据实际问题的需求选择合适的训练集得到极为精确 的模型，得到的结果与现实差异较小，但其隐含的中间结点个数可能会很多，隐 含层的个数和每层结点数决定了神经网络的复杂度。也可能会因为训练过度而使 得将模型移出训练集后会出现较多错误，复杂度高。 2 5 2决策树 归纳学习是符号学习中研究最为广泛的一种方法，它对给定关于某个概念的 一些力已知的正例和反例，从中归纳出一个通用的概念描述。归纳学习能够获得 1 3 电子科技大学硕士学位论文 新的概念，创建新的规则，发现新的知识。决策树【n 】( d e c i s i o n 扛) 是以实例为 基础的归纳学习方法，提供了一种展示类似在什么条件下会得到什么值这类规则 的方法。该方法根据训练数据最终生成以树状结构表示的分类器，其每个内部节 点都是对某一属性的判断，所有的叶子节点则代表最终的分类。 构造决策树的算法可以被描述成一个递归的过程：首先，选择一个属性作为 根节点，为该属性每种可能的取值生成一个分支，从而把训练集分成了几个子集。 然后，对每个分支节点继续分裂，子节点所划分的集合是其父节点划分的若干子 集中对应于该分支节点取值的那个实例集。如果在任一时刻，某个节点的所有实 例都属于一个分类，那么就停止该节点的分裂，使其成为叶节点。 决策树算法的关键是树的生长，树的生长过程就是将数据不断切分的过程。 “枝繁叶茂”并不一定好，会降低树的可理解性和可用性。可以通过限制树的层 数或是修剪过长的树来达到控制树的大小，但可能会降低准确度，需要在两者之 间作权衡。决策树特别适合用于处理非数值型数据，对于某些数值型数据，可能 需要将其转化成数值型数据再进行处理，反而会增加运算量。 2 5 3遗传算法 遗传算法【1 2 i 是仿生物学理论，目前广泛应用于优化领域，其收敛性好，且不 易陷入局部最小点，因而近来被深入研究。 在数据挖掘领域，它和神经网络等进行结合，用来求解某型参数等效率较高。 遗传算法是一种基于生物进化过程的组合优化方法，其基本思想是：随着时间 的更替，只有最适合的物种才得以进化。它由三个基本算子组成： l 、繁殖( 选择) ：从一个旧种群( 父代) 选择出生命力强的个体产生新种群( 后代) 的过程； 2 、交叉( 重组) ：选择两个不同个体( 染色体) 的部分( 基因) 进行交换，形成新个 体； 3 、变异( 突变) ：对某些个体的某些基因进行变异“1 变0 或o 变1 ) 。 数据挖掘就是根据遗传算法获得最合适的模型，并据此对数据模型进行优化， 遗传算法擅长于聚类分析。 2 5 4 统计分析方法 此类方法中利用统计学原理【1 3 l 对数据仓库中的数据进行处理，方法如下所示： 1 4 第二章数据挖掘概述 1 、常用统计，大量数据中的最大值、最小值、总和、平均值等； 2 、相关分析，相关系数来度量变量间的相关程度； 3 、回归分析，回归方程( 线性或非线性) 来表示变量间的数量关系； 4 、差异分析，样本统计量的值得出差异，来确定总体参数之间是否存在差异 ( 假设检验) ； 5 、聚类分析，直接比较样本中各样本之间的距离，将距离较近的归为一类， 而将距离较远的分在不同类中； 6 、判别分析，建立一个或多个判别函数，并确定一个判别标准，对未知对象 利用判别函数将它划归某一个类别。 2 5 5 粗集t r o u g hs e t ) 粗集【1 4 l 基于给定训练数据内部的等价类的建立。在数据库中，将行元素视为 对象，列元素看成属性，分为条件属性和决策属性。等价关系r 定义为不同对象 在某个或某几个属性上取值相同，满足等价关系的对象的集合称为该关系r 的等 价类。条件属性上的等价类e 与决策属性上的等价类y 之间有三种情况：一是下 近似，y 包含e ；二是上近似，y 和e 的交非空；三是无关，y 和e 的交为空。 对下近似建立确定性规贝i j ，对上近似建立不确定性规贝含可信度，对无关情况不 存在规则。 2 5 6 模糊集 一种表达和处理不确定性的重要方法。利用模糊集【切合理论对实际问题进行 模糊评判、模糊决策、模糊模式识别和模糊聚类分析。模糊性是客观存在的，系 统的复杂性越高，精确化能力就越低，也就意味着模糊性越强。这是z a d e h 总结 出的互克性原理。以上提到的模糊方法都取得了较好的效果。 2 6 数据挖掘性能问题 数据挖掘性能问题包括数据挖掘算法的有效性、可伸缩性和并行处理。 有效性和可伸缩性是指对于大型数据库数据挖掘算法的运行时间必须是可预 计和可接受的。解决挖掘算法中的有效性和可伸缩性是系统实现的关键问题。此 外，越来越复杂化和多样化的数据库类型也使数据挖掘面临巨大的挑战。 1 5 ， 电子科技大学硕士学位论文 2 7 数据仓库及数据立方体 数据仓库是伴随着决策支持系统的演化发展而逐渐发展起来的。数据仓库是 一个面向主题的、集成的、时变的、非易失的数据集合f 1 6 1 ，支持管理部门的决策 过程。数据仓库的构建需要数据集成、数据清理和数据统一。数据仓库也是数据 挖掘的重要预处理步骤。此外，数据仓库提供联机分析处理( 0 l 气n 工具，用于各 种多维数据分析。也有利于有