（计算机应用技术专业论文）基于数据挖掘的毕业生就业信息管理系统.pdf

华中科技大学硕士学位论文 摘要 随着我国高等教育的普及高校的扩招，造成如今高校毕业生就业形势逐渐严峻。 当前对高校毕业生的就业状况分析较为简单，大多仅仅按学校就业率和专业就业率 进行评价，显得片面缺乏科学性。根据这一情况，借助计算机对毕业生就业信息进 行挖掘，对目前的教学质量和学生工作质量进行科学的综合分析，寻找影响毕业生 就业的蚓素，以便对我们今后的教学和学生工作提出指导性建议。 课题针对学生的性别、政治面貌、英语水平、综合成绩、素质培养、社会实践 等方面在学生就业所反映的情况建立一个数据挖掘分析模型，由此得到对教学质量 和学生工作质量评价的科学的新方法。针对毕业生就业情况建立数据挖掘分析模型 是数据挖掘分析方法的一个新尝试，这将进一步促进数据挖掘分析理论的发展，并 且拓宽了数据挖掘分析方法的应用领域，同时为教学质量分析和学生工作质量分析 提供科学评价的新方法。 论文介绍了课题的研究背景、阐述了数据挖掘技术发展的历程，接着针对常用 的决策树算法进行分析，最后详细讨论s l i o 算法的设计实现过程并把它应用到毕业 生就业信息中，借助计算机对毕业生的就业信息进行挖掘，所获取的知识对指导今 后的教学和学生工作有重要意义。 关键词：数据挖掘，s l i q 算法，决策树 i 华中科技大学硕士学位论文 a b s t r a 曛 w i t ht h ep o p u l a r i z a t i o no f 韬g h e re d u c a t i o ni nc o l l e g e sa n du n l v e r a i t i e si n c r e a s e d e n m t l m e m ，r e s u l t i n gi nt h ee m p l o y m e n ts i t u a t i o nf o rc o l l e g eg r a d u a t e si sn o wg r a d u a l l y g r i m 。a n a l y s i so f t h ee r d r r e n te m p l o ) a n e ms i t u a t i o nf o rc o l l e g eg r a d u a t e si sm o r es i m p l e ， m o s ts c h o o l so n l yb yt h ee m p l o y m e n tr a t ea n dt h ee m p l o y m e n tr a t ef o rp r o f e s s i o n a l e v a l u a t i o n , i ti so n e - s i d e dl a c ks c i e n t i f i c 。i nl i g h to ft h i ss i t u a t i o n 。t h e 瓣o fc o m p u t e r i n f o r m a t i o no nt h ee m p l o y m e n to fg r a d u a t e s ，e x c a v a t i o nw o r ko nt h eq u a l i t yo ft e a c h i n g a n ds t u d e n tq u a l i t ys c i e n t i f i ca n a l y s i s , t h ei m p a c to ft h eg r a d u a t e sf i n de m p l o y m e n t , i n o r d e rf o ro u rf u t u r ew o r ki nt e a c h i n ga n dg u i d i n gs t u d e n t ss u g g e s t e d t h et o p i co fs t u d e n ts 麟，p o l i t i c s , e n g l i s kc o m p r e h e n s i v er e s u l t s , t h eq u a l i t yo ft h e t r a i n i n g ，s t u d e n t si ns u c ha r e a s s o c i a lp r a c t i c e ，a sr e f l e c t e di nt h ee m p l o y m e n ts i t u a t i o n i nt h ee s t a b l i s h m e n to f ad a t am i n i n gm o d e l ，w h i c hh a sb e e no nt h eq u a l i t yo f t e a c h i n ga n d s t u d e n te v a l u a t i o no ft h es c i e n t i f i cq u a l i t yo ft h en e wm e t h o d s i nv i e wo ft h e e s t a b l i s h m e n to fg r a d u a t ee m p l o y m e n td a t am i n i n gm o d e li s # n e wa r e m p t 。a n a l y s i so f d a t am i n i n g ，w h i c hw i l lf u c t h e rp r o m o t et h ed e v e l o p m e n to ft h e o r y , e n dt ob r o a d e nt h e a p p l i c a t i o no fd a t am i n i n ga n a l y 癌盎鑫sw e l la sa n a l y s i so ft h eq u a l i t yo ft e a c h i n ga n d s t u d e n te v a l u a t i o no f t h eq u a l i t yo f t h en e ws c i e n t i f i ca n a l y s i sm e t h o d s + t h i sa r t i c l ei n t r o d u c e st h et o p i co fb a c k g r o u n d ，e x p l a i n e dt h eh i s t o r yo ft h e d e v e l o p m e n to fd a t am i n i n gt e c h n o l o g y , f o l l o w e db yt h ed e c i s i o nt r e ea l g o r i t h m c o m m o n l yu s e di nt h ea n a l y s i s , t h ef i n a ld e t a i l e dd i s c u s s i o ns l i qa l g o r i t h m 姆a c h i e v e t h ed e s i g np r o c e s sa n da p p l i e di tt ot h eg r a a u a t ee m p l o y m e n ti n f o r m a t i o n , t h eu 跚o f c o m p u t e ri n f o r m a t i o nf o rt 瓣e m p l o y m e n to fg r a d u a t e sa n dm i n i n g t i l ek n o w l e d g e g a i n e d1 0g u i d ef u t u r et e a c h i n ga n ds t u d e n tw o r k i so f g r e a ts i g n i f i c a n c e k e yw o r d s ：d a t am i n i n g ，s l i qa l g o r i t h m ，d c e i s i o nt r e e u 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均己在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担， 学位论文作者签名：臃 日期：7 伊彩年i o 月谢日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书 本论文属于 不保密目。 ( 请在以上方框内打“4 ”) 学位论文作者签名：黼 日期：o 护彩年p 月功日 指导教师签名：诹一 日期：立一年f 口月。昭 华中科技大学硕士学位论文 1 1 课题背景 1 绪论 数据挖掘1 1 】( d a t am i n i n g ) ，又称数据库中的知识发现( 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 ，k d d ) ，是指从大型数据库或数据仓库中提取隐含的、未知的、非平凡的 及有潜在应用价值的信息或模式，它是数据库研究中的一个很有应用价值的新领域， 融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术。数据挖掘 工具能够对将来的趋势和行为进行预测，从而能很好的支持人们的决策。 经过十几年的研究和实践，数据挖掘技术已经吸收了许多学科的最新研究成果 而形成独具特色的研究分支。勿容置疑，数据挖掘研究和应用具有很大的挑战性。 象其它新技术的发展历程一样，数据挖掘也必须经过概念提出、概念接受、广泛研 究和探索、逐步应用和大量应用等阶段。从目前的现状看，大部分学者认为数据挖 掘的研究仍然处于广泛研究和探索阶段。一方面，数据挖掘的概念已经被广泛接受。 在理论上，一批具有挑战性和前瞻性的问题被提出，吸引越来越多的研究者。数据 挖掘的概念从二十世纪八十年代被提出后，其经济价值已经显现出来，而且被众多 商业厂家所推崇，形成初步的市场。另一方面，目i j 的数据挖掘系统研制也决不是 象一些商家为了宣传自己商品所说的那样神奇，仍有许多问题需要研究和探索。 1 2 目的和意义 随着我国高等教育的普及，全国大部分高校都根据自身情况进行了扩招，造成 如今高校毕业生的就业形势逐渐严峻。当前对高校毕业生的就业状况的分析较简单， 大多仅仅按学校就业率和专业就业率进行评价，显得片面，缺乏科学性。在现实情 况中，所谓名校，热门专业，并不能保证毕业生绝对能就业。从微观上看，学生自 身的素质和某些硬性条件是影响就业的关键。根据这一情况，借助计算机对毕业生 的就业信息进行挖掘，对目前的教学质量和学生工作质量进行科学的综合分析，寻 1 华中科技大学硕士学位论文 找影响毕业生就业的因素，以便对我们今后的教学和学生工作提出指导性建议。 本课题针对学生的性别、政治面貌、英语水平、综合成绩、素质培养、社会实 践等方面在学生就业所反映的情况建立一个数据挖掘分析模型，由此得到对教学质 量和学生工作质量评价的科学的新方法。 1 3 数据挖掘的综合应用分析 麻省理工学院的科技评论杂志提出未来5 年对人类产生重大影响的1 0 大新 兴技术，“数据挖掘”位居第三。我们知道，数据挖掘技术从一开始就是面向应用的。 目前，在很多领域，数据挖掘都是一个很时髦的词，尤其是在诸如银行、电信，保 险、交通、零售( 如超级市场) 等商业领域。近年来，数据挖掘已经被应用c r m 。3 的 实践中，成为解决商业分析问题的典范。这种结合所能解决的典型商业问题包括： 数据库营销( d a t a b a s em a r k e t i n g ) 、客户群体划分( c u s t o m e rs e g m e n t a t i o n c l a s s i f i c a t i o n ) 、客户背景分析( p r o f i l ea n a l y s i s ) 、交叉销售( c r o s s s e l l i n g ) 、 客户流失性分析( c h u r na n a l y s i s ) 、客户信用记分( c r e d i ts c o r i n g ) 、欺诈发现 ( f r a u dd e t e c t i o n ) 等等。 但总的来说，把数据挖掘技术应用于毕业生的就业分析国内外都还是鲜有报道。 针对毕业生就业情况建立数据挖掘分析模型，是数据挖掘分析方法的一个新尝试。 这将进一步促进数据挖掘分析理论的发展，并且拓宽了数据挖掘分析方法的应用领 域，同时为教学质量分析和学生工作质量分析提供科学评价的新方法。 t 4 论文的总体结构 本文总共分为六章。 第一章：绪论。主要介绍课题的选题背景以及实现的目的和意义；接着对数据 挖掘技术的发展和应用状况进行了分析t 最后阐明本文的内容安排。 第二章：数据挖掘技术。通过分析数据挖掘技术产生的背景，介绍了数据挖掘 技术的概念以及常用的分类法和常用的知识表现方法：最后还介绍不同存储形式下 华中科技大学硕士学位论文 的数据挖掘问题。 第三章：数据挖掘算法的选择和比较。通过对常用分类算法进行分析，阐述了 选择策树分类算法的原因：接着介绍了决镱树的基本概念，并对常用的决策树算法 进行比较分析，阐明选择s l i q 算法的原因。 第四章：系统设计。首先对毕业生就业信息分析系统进行需求分析；接着 给出该系统的系统结构；最后介绍系统的概要设计。 第五章：系统实旌。通过对本系统总流程的具体说明，对采用的s l i q 算法给出 了具体的实施过程；本章还给出实现系统的核心数据结构；最后给出系统运行结果 并对它进行分析。 第六章：对本文所做工作进行了系统的总结。 焦 中科技大学硕士学位论文 2 数据挖掘技术 数据挖掘作为一个只有十几年研究历史的较新研究领域许多概念和技术是逐 步发展起来的。本章将并力求从不同视点和流派来阐述数据挖掘的重要概念、发展 和应用情况。 2 1数据挖掘技术的产生背景 2 1 1 数据挖掘技术的商业需求分析 数据挖掘之所以吸引专家学者的研究兴趣和引起商业厂家的广泛关注，主要在 于大型数据系统的广泛使用和把数据转换成有用知识的迫切需要。目前，由于各种 新型技术与数据库技术的有机结合，使数据库领域中的新内容，新应用、新技术层 出不穷，形成了庞大的数据库家族。但是，这些数据库的应用都是以实时查询处理 技术为基础的。从本质上说，查询是对数据库的被动使用。由于简单查询只是数据 库内容的选择性输出。因此它和人们期望的分析预测、决策支持等高级应用仍有很 大距离。 事实上，数据( d a t a ) 、信息( i n f o r m a t i o n ) 和知识( k n o w l e d g e ) 可以看作是 广义数据表现的不同形式例。毫不夸张地说，人们对于数据的拥有欲是贪婪的，特别 是计算机存储技术和网络技术的发展加速了人们收集数据的范围和容量。这种贪婪 的结果导致了“数据丰富而信息贫乏( d a t ar i c h & i n f o r m a t i o np o o r ) ”现象的产生。 数据库是目前组织和存储数据最有效的方法之一。但是面对目益膨胀的数据，数据 库查询技术已表现出它的局限性。例如，在现实社会中，如果人均日阅读时间在3 0 分钟的话，一个人一天最快只能浏览一份2 0 版左右的报纸。如果你订阅了1 0 0 份报 纸，其实你每天也不过只阅读了一份而已。面对计算机中的海量的数据，人们也处 于同样的尴尬境地，缺乏获取有效信息的手段。知识是一种概念、规则、模式和规 律等。它不会象数据或信息那么具体，但是它却是人们一直不懈追求的目标。事实 华中科技大学硕士学位论文 上。在我们的生活中，人们只是把数据看作是形成知识的源泉。我们是通过正面的 或反面的数据或信息来形成和验证知识的，同时又不断地利用知识来获得新的信息。 因此，随着数据的膨胀和技术环境的进步，人们对联机决策和分析等高级信息处理 的要求越来越迫切。在强大的商业需求的驱动下，商家们开始注意到有效地解决大 容量数据的利用问题具有巨大的商机学者们开始思考如何从大容量数据集中获取 有用信息和知识的方法。因此，在二十世纪八十年代后期，产生了数据仓库和数据 挖掘等信息处理思想。 2 1 2 数据挖掘产生的技术背景分析 任何技术的产生总是有它的技术背景的。数据挖掘技术的提出和普遍接受是由 于计算机及其相关技术的发展为其提供了研究和应用的技术基础。 归纳数据挖掘产生的技术背景下面一些相关技术的发展起到了决定性的作用： 1 数据库、数据仓库和i n t e r n e t 等信息技术的发展； 2 计算机性能的提高和先进的体系结构的发展； 3 统计学和人工智能等方法在数据分析中的研究和应用。 数据库技术从二十世纪8 0 年代开始，已经得到广泛的普及和应用。在关系型数 据库的研究和产品提升过程中，人们一直在探索组织大型数据和快速访问的相关技 术。高性能关系数据库引擎以及相关的分布式查询、并发控制等技术的使用，已经 提升了数据库的应用能力。在数据的快速访问、集成与抽取等问题的解决上积累了 经验。数据仓库作为一种新型的数据存储和处理手段，被数据库厂商普遍接受并且 作为辅助建模和管理工具快速推向市场，成为多数据源集成的一种有效的技术支撑 环境。另外，i n t e r n c t 的普及也为人们提供了丰富的数据源。据说，在美国电视达到 5 0 0 0 万户大约用了1 5 年，而i n t e r a c t 上网达到5 0 0 0 万户仅用了4 年。而且i n t e r a c t 技术本身的发展，已经不光是简单的信息浏览，以w e b 计算为核心的的信息处理技 术可以处理i n t e r a c t 环境下的多种信息源。因此，人们已经具备利用多种方式存储海 量数据的能力。只有这样，数据挖掘技术才能有它的用武之地。这些丰富多彩的数 据存储、管理及访问技术的发展，为数据挖掘技术的研究和应用提供了丰富的土壤。 华中科技大学硕士学位论文 计算机芯片技术的发展，使计算机的处理和存储能力日益提高。计算机性能的 提高和先进的体系结构的发展使数据挖掘技术的研究和应用成为可能。 历经了十几年的发展，包括基于统计学、人工智能等在内的理论与技术性成果 已经被成功地应用到商业处理和分析中。这些应用从某种程度上为数据挖掘技术的 提出和发展起到了极大地推动作用。数据挖掘系统的核心模块技术和算法都离不开 这些理论和技术的支持。从某种意义讲，这些理论本身发展和应用为数据挖掘提供 了有价值的理论和应用积累。数理统计是一个有几百年发展历史的应用数学学科。 数据挖掘技术是数理统计分析应用的延伸和发展，假如人们利用数据库的方式从被 动地查询变成了主动发现知识的话，那么概率论和数理统计这一古老的学科可以为 我们从数据归纳知识一一数据挖掘技术提供理论基础。 人工智能是计算机科学研究中争议最多但是仍始终保持强大生命的研究领域。 机器学习应该说是得到了充分的研究和发展，并且数据挖掘技术继承了机器学习解 决问题的思想。数据挖掘研究在继承已有的人工智能相关领域的研究成果的基础上， 客观地从数据集中发现蕴藏的知识。 2 2 数据挖掘概念 2 2 1 数据挖掘研究的理论基础 谈到知识发现和数据挖掘，必须进一步阐述它研究的理论基础问题。虽然关于 数掘挖掘的理论基础问题仍然没有到完全成熟的地步，但是分析它的发展可以使我 们对数据挖掘的概念更清楚。坚实的理论是我们研究，开发、评价数据挖掘方法的 基石。经过十几年的探索，一些重要的理论框架已经形成，并且吸引藿众多的研究 和开发者为此进一步工作，向着更深入的方向发展。 数据挖掘方法可以是基于数学理论的，也可以是非数学的；可以是演绎的，也 可以是归纳的。从研究的历史看，它们可能是数据库，人工智能、数理统计、计算 机科学以及其它方面的学者和工程技术人员，在数据挖掘的探讨性研究过程中创立 的理论体系。1 9 9 7 年，m a n n i l a 对当时流行的数据挖掘的理论框架给出了综述1 4 j 。结 6 盟 中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = ；= = = = = = = = = = = = = = = = = = = = = = = = = ；= = = = = = = = = = = = = = = = = = 合最新的研究成果，有下面一些重要的理论框架可以帮助我们准确的理解数据挖掘 的概念与技术特点： i 模式发现( p a t t e r nd i s c o v e r y ) 架构 在这种理论框架下，数据挖掘技术被认为是从源数据集中发现知识模式的过程 嗍。这是对机器学习方法的继承和发展，是目前比较流行的数据挖掘研究与系统开发 架构。目前，在关联规则、分类，聚类模型、序列模式( s e q u e n c em o d e l ) 以及决策 树( d e c i s i o n t r e e ) 归纳等模式发现的技术与方法上取得了丰硕的成果。 2 规则发现( r u l ed i s c o v e r y ) 架构 a g r a w a l 等综合机器学习与数据库技术，将三类数据挖掘目标即分类、关联及 序列作为一个统一的规则发现问题来处理嘲。他们给出了统一的挖掘模型和规则发现 过程中的几个基本运算，解决了数据挖掘问题如何映射到模型和通过基本运算发现 规则的问题。这种基于规则发现的数据挖掘构架也是目前数据挖掘研究的常用方法。 3 基于概率和统计理论 在这种理论框架下，数据挖掘技术被看作是从大量源数据集中发现随机变量的 概率分布情况的过科”。目前，这种方法在数据挖掘的分类和聚类研究和应用中取得 了很好的成果。这些技术和方法可以看作是概率理论在机器学习中应用的发展和提 高。实际上，大多数的理论构架都离不开统计方法的介入。统计方法在概念形成、 模式匹配以及成分分析等众多方面都是基础中的基础。 4 微观经济学观点( m i c r o e c o n o m i ev ie w ) 在这种理论框架下，数据挖掘技术被看作是一个问题的优化过程f 3 l 。1 9 9 8 年， k l e i n b e r g 等人建立了在微观经济学框架里判断模式价值的理论体系。他们认为，如 果一个知识模式对一个企业是有效的话，那么它就是有趣的。有趣的模式发现是一 个新的优化问题，可以根据基本的目标函数，对“被挖掘的数据”的价值提供一个 特殊的算法视角，导出优化的企业决策。 5 基于数据压缩( d a t ac o m p r e s s i o n ) 理论 在这种理论框架下，数据挖掘技术被看作是对数据的压缩的过程【9 】。按着这种 观点，关联规则、决策树、聚类等算法实际上都是对大型数据集的不断概念化或抽 7 华中科技大学硕士学位论文 象的压缩过程。 6 基于归纳数据库( i n d u c t i v ed a t a b a s e ) 理论 在这种理论框架下，数据挖掘技术被看作是对数据库的归纳的问题i 。个数 据挖掘系统必须具有原始数据库和模式库，数据挖掘的过程就是归纳的数据查询过 程。这种构架也是目前研究者和系统研制者倾向的理论框架。 7 可视化数据挖掘( v i s u a ld a t am i n i n g ) 1 9 9 7 年，k e i m 对可视化数据挖掘的相关技术给出了综述【“】。虽然可视化数据 挖掘必须结合其它技术和方法才有意义，但是以可视化数据处理为中心来实现数据 挖掘的交互式过程以及更好的展示挖掘结果等，已经成为数据挖掘中的一个重要方 面。 当然，上面所述的理论框架不是孤立的，更不是互斥的。对于特定的研究和开 发领域来说，它们是相互交叉并且有所侧重的。从上面的叙述中，我们也可以看出， 数据挖掘的研究是在相关学科充分发展的基础上提出并不断发展的，它的概念和理 论仍在发展中。 2 3 数据挖掘技术的分类问题 + 数据挖掘涉及的学科领域和方法很多，有多种分类方法。 根据挖掘任务可以分为：分类或预测模型发现、数据总结与聚类发现、关联规 则发现、序列模式发现、相似模式发现、混沌模式发现、依赖关系或依赖模型发现、 异常和趋势发现等。 ， 根据挖掘对象可以分为：关系数据库、面向对象数据库( o b j e c t o r i e n t e d d a t a b a s e ) 、空间数据库、时态数据库、文本数据源、多媒体数据库、异质数据库、 遗产数据库以及w e b 等对象的挖掘。 根据挖掘方法可以分为：机器学习方法、统计方法，聚类分析方法、神经网络 ( n e u r a l n e t w o r k ) 方法、遗传算法( o e n e t i c a l g o d t h m ) 、粗糙集( r o u g h s e t ) 方法、 集成方法等。 8 华中科技大学硕士学位论文 根据数据挖掘所能发现的知识可以分为：广义型知识挖掘、差异型知识挖掘、 关联型知识挖掘、预测型知识挖掘、偏离型( 异常) 知识挖掘、不确定性知识等。 当然，这些分类方法都从不同角度，刻画了数据挖掘研究的策略和范畴，他们 是互相交叉而相互补充的。下面我们将从几个不同的角度来进一步阐述目前所研究 的问题和所采用的主要方法。 2 。4 数据挖掘常用的知识表示模式与方法 数据挖掘的目的是发现知识，知识耍通过一定的模式给出。可用于数据挖掘系 统的知识表示模式是丰富的，通过对数据挖掘中知识表示模式及其所采用方法的分 析，可以更清楚地了解数据挖掘系统的特点。 2 4 1 广义知识挖掘 广义知识( g e n e r a l i z a t i o n ) 是指描述类别特征的概括性知识。我们知道，在源 数据( 如数据库) 中存放的一般是细节性数据，而人们有时希望能从较高层次的视 图上处理或观察这些数据，通过数据进行不同层次上的泛化来寻找数据所蕴涵的概 念或逻辑，以适应数据分析的要求。数据挖掘的目的之一就是根据这些数据的微观 特性发现有普遍性的、更高层次概念的中观和宏观的知识。 1 概念描述( c o n c e p td e s c r i p t i o n ) 方法 概念描述本质上就是对某类对象的内涵特征进行概括。概念描述分为特征性 ( c h a r a c t c d z a t i o n ) 描述和区别性( d i s c r i m i n a t i o n ) 描述。前者描述某类对象的共同 特征，后者描述不同类对象之间的区别。 概念描述是广义知识挖掘的重要方法，目前已经得到广泛研究。归纳起来有下 面一些有代表性的方法： ( 1 ) 概念归纳( c o n c e p ti n d u c t i o n ) 方法 这种方法来源于机器学习。我们知道，典型的示例学习把样本分成正样本和负 样本，学习的结果就是形成覆盖所有正样本但不覆盖任何负样本的概念描述。但是， 9 华中科技大学硕士学位论文 要把这种思想应用到数据挖掘中耍解决两个关键问题。第一，必须扩大样本集的容 量和范围。但扩大后的样本集可能难于有效地精确实现“覆盖所有正样本但不覆盖 任何负样本”的概念归纳目标。因此，最大限度地使用样本进行归纳就是必须解决 的关键问题之一。第二，对于数据挖掘系统来说，正样本来自于源数据库，而负样 本是不可能在源数据库中直接存储的，但是缺乏对比类信息的概念归纳是不可靠的。 因此，从源数据库中形成负样本( 或区别性信息) 以及相关的评价区别的度量方法 等也是要解决的另一个重要问题。 ( 2 ) 多维数据分析可以看作是一种广义知识挖掘的有效方法 数据分析的经常性工作是数据的聚集，诸如计数、求和、平均、最大值等。既 然很多聚集函数需经常重复计算，而且这类操作的计算量一般又特别大，因此一种 很自然的想法是，把这些汇总的操作结果预先计算并存储起来，以便于高级数据分 析使用。最流行的存储汇集数据类的方法是多维数据库( m u l t i - d i m e n s i o nd a t a b a s e ) 技术。多维数据库总是提供不同抽象层次上的数据视图。关于多维数据模型的操作， 已经被很好研究，许多文献可能和数据仓库、o l a p 联系起来1 1 ”l 。其实，这种模型 可以成为广义知识发现的基础。 ( 3 ) 面向数据库的概化方法 数据库，特别是关系型数据库是数据挖掘的主要源数据类型。近年来，在面向 数据库的广义知识挖掘方面进行了有针对性的研究。值得一提的是，加拿大 s i r e o n f r a a e r 大学提出的面向属性的概念归约方法【l 。它直接对用户感兴趣的数据 视图( 用一般的s q l 查询语言即可获得) 进行泛化，而不是像多维数据分析方法那样 预先就存储好了泛化数据。原始关系经过泛化操作后得到的是一个泛化关系，它从 较高的层次上总结了在低层次上的原始关系。有了泛化关系后，就可以对它进行各 种深入的操作而生成满足用户需要的知识，如在泛化关系基础上生成特性规则、判 别规则、分类规则以及关联规则等。 2 ，多层次概念描述问题 由数据归纳出的概念是有层次的，例如，l o c a t i o n 是“华中科技大学”，那么我 们可能通过背景知识( b a c k g r o u n d k n o w l e d g e ) 归纳出“武汉市”、“中国”、“亚洲” 华中科技大学硕士学位论文 等不同层次的更高级概念。这些不同层次的概念在是对原始数据的不同粒度上的概 念抽象。目前，广泛讨论的概念分层( c o n c e p th i e r a r c h y ) 技术就是为了解决这个问 题。所谓概念分层实际上就是将低层概念集映射到高层概念集的方法。例如，一个 记录销售人员销售情况的数据库的表s a l e s ( e n o ，e n a m e ，e a g e ，v a l u e ， d e p t ) ，它的每个属性的定义域都可能存在蕴涵于领域知识内的概念延伸。 互4 2 关联知识挖掘 关联知识( a s s o c i a t i o n ) 反映一个事件和其它事件之间的依赖或关联。数据库 中的数据关联是现实世界中事物联系的表现。数据库作为一种结构化的数据组织形 式，利用其依附的数据模型可能刻画了数据间的关联( 如关系数据库的主键和外键) 。 但是，数据之间的关联是复杂的。关联知识挖掘的目的就是找出数据库中隐藏的关 联信息。关联可分为简单关联、时序( t i m es e r i e s ) 关联、因果关联、数量关联等。 这些关联并不总是事先知道的，而是通过数据库中数据的关联分析获得的，因而对 商业决策具有新价值。 从广义上讲，关联分析是数据挖掘的本质。既然数据挖掘的目的是发现潜藏在 数据背后的知识，那么这种知识一定是反映不同对象之间的关联。在上面我们提到 的广义知识挖掘问题实际上是挖掘数据与不同层次的概念之间的关联。当然，本节 的关联分析还是指一类特定的数据挖掘技术，它集中在数据库中对象之间关联及其 程度的刻画。 关联规则挖掘是关联知识发现的最常用方法。最为著名的是a g r a w a l 等提出的 a p r i o d 及其改进算法【5 1 5 1 。为了发现出有意义的关联规则，需要给定两个闽值：最小 支持度( m i n i m u ms u p p o r t ) 和最小可信度( m i n i m u mc o n f i d e n c e ) 。挖掘出的关联规 则必须满足用户规定的最小支持度，它表示了组项目关联在一起需要满足的最低 联系程度。挖掘出的关联规则也必须满足用户规定的最小可信度，它反映了一个关 联规则的最低可靠度。关联规则的研究和应用是数据挖掘中最活跃和比较深入的分 支，许多关联规则挖掘的理论和算法已经被提出。 2 4 3 类知识挖掘 华中科技大学硕士学位论文 = ；= = = = = = = = = = = = = = ：；= ： ：=： = 类知识( c l a s s ) 刻馘了一类事物，这类事物具有某种意义上的戴同特征，并明 显彝不弱娄事兹穗区捌。窝其它魏文献稳对应，这堡稳受知识是摆数攒笼掘熬分类 和聚娄两类数据挖掘应用所对应的知识。 1 ，分类 分焱是数据挖掘枣鹣一个重要的鄹拣翔任务，它的爨的是学会一个分类模型( 称 作分粪器) ，该模型熊把数据库中的数据颁映射到泠定类剐中。要祷逢分类器，需器 有一个训练样本数据集作为输入。由于数据挖掘是从源数据集中挖掘知识的过程， 这种类知识也必须来自于源数据，应该避对源数据的过滤、抽取( 抽样) 、压缩以及 概念褥敷等。藏橇嚣攀习斡鼹熹，分类按零跫一静旨指导豹学嚣 b u y ( x ，v i d e o s ) s u p p o r t = 4 0 ，c o n f i d e n c e = t i f f 。但是，事实上，计算机游戏捌 录象产熬是受稳关躲，嚣麴买了其孛一耱的喜户实际土减少了购买爨一糖兹可能性。 医此，科传统的数据挖掘框架的知识评价问题，也是关系型数据痒中数据挖掘走向 实际应用必须要解决的问题。 5 约束数据挖掘瓣题 数糍挖掘系统在麓户的约束指导下进行，可懿撵赫挖摇效率拳l 猿确度。关子它 的研究是一个很宽泛的课题。在可视化和交互式数槲挖掘中，用户约束的使用和输 入是可视他和交互式挖掘的前提。对荧系型数据库而富，由于它的属性的复杂性( 如 大量数爨嚣毪存在) ，瓣瞧关联豹蕴涵存德夔及多表袋多篡次壤念等瓣惩，终素数撂 挖掘问嬲就显得更为重嚣。 蓑撩型数据库中的数据挖掘是一个应用价值很高的研究领域。有许多课题需要 遗一步滚入。 2 5 4w e b 数据源中的数据挖掘 面向w e b 的数据挖掘比面向数据库的数据挖掘要篾杂得多，因为w e b 上的数据 是复杂熬。有些是焉续褥靛( 魏w e b 爱) ，运誊都是蠲长鹣句子或短浚寨表这文糖炎 信息；糍些可能是半蹈构的( 如e m a i l ，h t m l 页) 。描开这些复台对象蕴涵的一般 性描述特征成为数据挖掘的不可推卸的责任。 w e b 挖掘( w e bm i n i n g ) 必须露对下萄一些关键阉题 1 ，异构数据澡舔麓 w e b 网站上的信息是一个更大、更复杂的数据体。如果把w e b 上的每一个站点 信息香作是个数据源的话，那么这娥数据源是异构的，因为每个站点的信息和组 织帮不一群。怒要蘧| 矮逸秀海量数撵遴行蘩据挖掘，譬先，必须要醭究菇点之麓雾 构数掘的集成问题。只有将这些站点的数据都集成剽一个统一的视嘲上，才有可能 华中科技大学硕士学位论文 获取所需的东西。其次，还要解决w e b 上的数据查询问题。因为如果不能很有效的 得到所需的数据，对这些数据进行分析、集成、处理就无从谈起。 2 半结构化的数据结构 w e b 上的数据与传统的数据库中的数据不同，w e b 上的数据更多是半结构化的。 面向w e b 的数据挖掘必须以半结构化模型和半结构化数据模型抽取技术为前提。针 对w e b 上的数据半结构化的特点，寻找一个半结构化的数据模型是解决问题的关键 所在。除了要定义一个半结构化数据模型外，还需要一种半结构化模型抽取技术。 我们知道，每一站点的数据都各自独立设计，并且数据本身具有自述性和动态可变 性，因此面向w e b 的数据挖掘是一项复杂的技术。 2 6 小结 本章介绍了数据挖掘技术的产生、发展和应用前景。从不同角度阐述了数据挖 掘的概念和含义。本章还归纳了数据挖掘研究的理论基础，并从数据挖掘的知识表 示模式角度归纳了数据挖掘的主要技术与方法。本章也对数据挖掘的主要研究热点 与应用进行了剖析。 华中科技大学硕士学位论文 = = = = ；= = = = = ；= = = = = = = = = = = = = = = = = = = ：= = = ：= 3 数据挖掘算法的选择和比较 3 1 选择决策树分类法的原因 在数据挖掘分类技术中，主要有决策树法、贝叶斯法、神经网络法和粗糙集等 方法。本文选择决策树分类法进行研究，主要是基于以下几点考虑： i 决策树方法能够生成可以理解的规则。由于系统的最终用户是主管学生工作 的管理者，他们往往不具备数据挖掘的知识，因此挖掘方法的可解释性十分重要。 而决策树是以树型结构表示最终分类结果，而且还可以生成i f - t h e n 形式的规则， 这样接近于人们对现实世界事物的认知和表示方式 2 决策树方法的计算量相对来说不是很大。决策树方法的计算量相对其他方法 来说比较小，这样可以大大地缩短计算时间，提高系统的执行效率。 3 决策树方法可以处理连续和离散数据。毕业生就业信息数据涵盖面比较广， 包含的种类也比较多，不仅有定性属性( 即离散型数据) 还有定量属性( 即连续型属 性) 。 4 决策树可以清晰的显示出属性的重要程度”1 。决策树是通过计算信息嫡选择 分裂属性的，而信息嫡正是该属性重要性的度量标量。从直观上看，决策树结点所 在的层次越商，该结点所代表的属性就越重要，相反结点所代表的属性对此次分类 的作用就越小。那么，同一层次结点的作用基本相同，没有明显的大小之分。 综合以上四点，本文选择分类技术中的决策树方法，用于毕业生就业信息分类。 3 2 决策树的基本概念 决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无秩序、无规则 的事例中推理出决策树表示形式的分类规则，它采用自顶向下的递归方式，在决策 树的内部节点进行属性值的比较并根据不同的属性值判断从该节点向下的分支，在 决策树的叶节点得到结论。所阻从根到叶节点的一条路径就对应着一条合取规则， 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 目= = = = = = = = = = = = = = = = = = 整棵决策树就对应着一组析取表达式规则。 在具体应用的时候决策树分类算法通常分为两个阶段：决策树构建( b u i d i n g ) 和决策树修剪( p r u n i n g ) 。常用的决策树算法有：i d 3 ，c 4 5 和s l i q 等。 3 2 1i d 3 算法 i d 3 算法在树的每个节点上使用信息增益度量选择测试属性1 1 5 】，选择具有最高 信息增益( 或最大熵压缩) 的属性作为当前节点的测试属性，该属性使得对结果划分 中的样本分类所需的信息量最小，并反映划分的最小随机性。这种信息理论方法使得 对一个对象分类所需的期望测试数目达到最小，并确保找到一棵简单的树。它是基于 如下的理论： 设s 是s 个数据样本的集台。假定类标号c i ( i = 1 ，d m ) 具有1 t 1 个不同值，设 s i 是类c i 中的样本数。对一个给定的样本分类所需的期望信息由下式给出： i ( s l ，s l l i ) = - - p , l 0 9 2 ( ，o ( 公式1 ) 其中p i 是任意样本属于c 。的概率，并用s l s 来估计。 设属性a 具有v 个不同值 a i ，a d 。可以用属性a 将s 划分为v 个子集 s i ，；其中，s ，包含s 中这样一些样本，它们在a 上具有值a j 。如果a 选作测试 属性，则这些子集对应于由包含集合s 的节点生长出来的分枝。设s l j 是子集s j 中类c 的样本数。根据由a 划分成子集的熵由下式给出： e ( a ) = 主堕二等墅! i ( s i i ，嘶) ( 公式2 ) 其中，项兰坐= = ! 堕充当莉个子集的权，并且等于子集( 即a 值为码) 中的t o 样本个数除以s 中的样本总数。熵值越小，子集划分的纯度越高。对于给定的子集 有： i ( 5 u ，s 驴“，嘶) ；一p 1 0 9 2 ( p 6 ) ( 公式3 ) 2 1 华中科技大学硕士学位论文 其中，脚= 等是中的样本属于类c i 的概率。 l o ，l 在a 上分枝将获得的编码信息是： g a i n ( a ) - - i ( s l ，s z ，s i l l ) - - e ( a )( 公式4 ) 以上就是有关i d 3 算法的基本理论。 3 2 2c a 5 算法 c 4 5 算法是从i d 3 算法中改进而来的，c 4 5 算法与i d 3 算法所不同的是在后面使 用信息增益比例来取代信息增益。 其中，s l 到s c 是c 个值的属性a 分割s 而形成的c 个样本子集。这时，在属 性a 上所得到的信息增益比为： g a i n r a t i o ( 4 ，s ) = 面g a 而i n ( s , a ) ( 公式5 )=。 s p t i n n f o t s a 、 c 4 5 算法计算每个属性的信息增益比。具有最高信息增益比的属性选作给定集 合s 的测试属性a 创建一个节点，并以该属性标记，对属性的每个值创建分枝，并据此 划分样本。 3 2 3 s l i q 算法 一般决策树中，使用信息量作为评价节点分裂质量的参数。s l i q 算法中，使用 g i n i 指标( g i n ii n d e x ) 代替信息量( i n f o r m a t i o n ) ，g i n i 指标比信息量性能更 好且计算方便。对数据集包含n 个类的数据集s ，g i n i ( s ) 定义为： 6 i n i ( s ) = 1 一p j 印j( 公式6 ) p 。是s 中第j 类数据的频率。如果集合s 分成两部分s 和s 。那么该分割的g i n i 就是： 6 i n i _ s p l i t ( s ) = n i n * g i n i ( s 1 ) + n , n * g i n i ( s 2 )( 公式7 ) 其中n 为集合s 的记录数，n t 为s t 的记录数，n z 为s 。的记录数。g i n i s p l i t ( s ) 越小， i n