（应用数学专业论文）高校学生就业信息的决策支持系统的应用研究.pdf

y ， 1 1 0 1 ：9 8 高校学生就业信息的决策支持系统的应用研究 专业： 硕士生： 指导教师： 应用数学 刘幸东 姚正安教授 摘要 由于数据库中存在着大量数据，因此从数据库中发现有用的信息显得十分重 要数据挖掘技术就是为解决这个问题而产生的，对数据挖掘技术的研究，国内外 己经取得了许多令人瞩目的成就，并成功地应用到了许多领域，但在教育领域中 的应用并不广泛， 由于我国大众化高等教育的普及，高等院校招生规模的扩大，高校学生数量 的激增，学生就业问题日益突出，各高校千方百计提高就业率，除了加强自身的办 学条件，高校的决策者很想知道如何培养学生能够提高就业率 高校一般都己建立了学生管理系统，保存有大量的学生就业历史数据如何 从这些数据中找出有用的信息，提供给决策者，是我们所关心的问题本文应用 数据挖掘技术，建立学生就业信息库，完整地实现了数据分类挖掘的全过程，包 括：确定数据挖掘对象及目标、采集数据、采用数据集成、数据清理、数据转换、 数据消减等数据预处理技术：根据就业数据具有分类的预知性与离散性的特点， 选择决策树c 4 5 算法，生成决策分类树，并利用事后修剪法对决策树进行修剪： 最后由决策树产生分类规则，完成了学生就业分析决策树模型的建立，挖掘出学 生就业的若干规律 关键词：数据挖掘：分类：决策树；分类规则：就业 t h ea p p l i e dr e s e a r c ho fd e c i s i o n m a k i n gs u p p o s e ds y s t e mo f e m p l o y m e n ti n f o r m a t i o no fu n i v e r s i t i e 宴s t u d e n t s m a j o r ：a p p i e dm a t h e m a t i c s n a m e ：l i ux i n g d o n g s u p e r v is o r ：y a oz h e n a n a b s t r a c t a sar e s u l to ft h ep o p u l a r i z a t i o no fo u rc o u n t r y sp o p u l a r i t yh i g h e re d u c a t i o n ，t h ee x p a n s i o no f c o l l e g er e c r u i t m e n to fs t u d e n t ss c a l e ，a n dt h es h a r p l yi n c r e a s i n go fu n i v e r s i t i e ss t u d e n tq u a n t i t y 。 t h ep r o b l e ma b o u ts t u d e n t s e m p l o y m e n ti sp r o m i n e n td a yb yd a y e a c hc o l l e g ee n h a n c e st h e e m p l o y m e n tr a t eb ya n ym e a n sp o s s i b l e b e s i d e ss t r e n g t h e n i n g t h e i ro w ns c h o o lc o n d i t i o n ， u n i v e r s i t i e s 。p o l i c y m a k e r sw a n t t ok n o wh o wt ot r a i ns t u d e n t st ob ea b l et oe n h a n c et h e e m p l o y m e n tr a t e t h eu n i v e r s i t i e sh a v ea l r e a d ye s t a b l i s h e dt h es t u d e n tm a n a g e m e n ts y s t e mg e n e r a l l y ，a n dh a v e p r e s e r v e dm a s s i v eh i s t o r i c a ld a t aa b o u ts t u d e n t s e m p l o y m e n t h o wt o d i s c o v e rt h eu s e f u l i n f o r m a t i o nf r o mt h e s ed a t at op r o v i d et ot h ep o l i c y - m a k e r si st h ei s s u eo fo u rc o n c e r n t h i sa r t i c l ei n t r o d u c e dt h ed e f i n i t i o n ，t h ef u n c t i o na n dt h ec o m m o n l yu s e dt e c h n o l o g yo fd a t a m i n i n g ，a n da l s oi n t r o d u c e dt h ec l a s s i f i c a t i o nt e c h n o l o g yo fd a t am i n i n g a c c o r d i n gt ot h ef a c t t h a te m p l o y m e n td a t ah a st h ec h a r a c t e r i s t i c so fk n o w i n gt h en a t u r a li na d v a n c ea n ds e p a r a t i n go f c l a s s i f i c a t i o n ，i ta p p l i e dam e t h o dn a m e dd e c i s i o nt r e et oc a r r ya n a l y s i so ns t u d e n t s e m p l o y m e n t i n f o r m a t i o na n dh a sr e a l i z e dt h ee n t i r ep r o c e s so ft h ed a t ac l a s sm i n i n gc o m p l e t e l y ，w h i c h i n c l u d e ss o m ed a t ap m t r e a t m e n tt e c h n o l o g ya ss p e c i f y i n gd a t am i n i n go b j e c ta n dg o a l ，g a t h e r i n g d a t a ，i n t e g r a t i n gd a t a ，c l e a n i n gu pd a t a ，c o n v e r t i n gd a t a ，r e d u c i n gd a t a ，a n d s oo n i tc h o s e d e c i s i o nt r e ec a 5a l g o r i t h mt op r o d u c te m p l o y m e n td e c i s i o nc l a s s i f i c a t i o nt r e e ，a n du s e dt h el a w o fp r o n ea f t e r w a r d st oc a r r yp r u n e so nt h ed e c i s i o nt r e e ；f i n a l l y ，i th a sp r o d u c e dt h ec l a s s i f i c a t i o n r u l eb yt h ed e c i s i o nt r e e ，c o m p l e t e dt h ee s t a b l i s h m e n to ft h em o d e lo fs t u d e n te m p l o y m e n t a n a l y s i sd e c i s i o nt r e e ，a n dm i n i n gc e r t a i nr u l e so nw h i c hs t u d e n t sa l eg o t t e ne m p l o y e d k e yw o r d s ：d a t am i n i n g ；c l a s s i f i c a t i o n ；d e c i s i o nt r e e ；c l a s s i f i c a t i o nr u l e ；e m p l o y m e n t u 中山大学硕士学位论文 第一章前言 本章首先介绍数据挖掘技术研究背景及研究意义，其次介绍了本文所选课题的研 究背景及其研究意义，最后介绍了本文结构安排的主要研究工作 1 。l 数据挖掘技术研究背景及研究意义 2 0 世纪9 0 年代以来，随着信息技术和数据库技术的迅猛发展，人们利用信息 技术生产和搜集数据的能力大幅度提高，可以非常方便地获取和存储大量的数据 千万个数据库被用于商业管理、政府办公、科学研究和工程开发等等，并且这一势 头仍将持续发展下去数据的积累越来越多，激增的数据背后隐藏着许多重要的信 息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据目前的数据 库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的 关系和规则，无法根据现有的数据预测未来的发展趋势缺乏挖掘数据背后隐藏的知 识的手段，导致了“数据爆炸但知识贫乏”的现象于是，一个新的挑战被提了出 来：在这被称之为信息爆炸的时代，信息过量几乎成为人人需要面对的问题，如何 才能不被信息的汪洋大海所淹没，从中及时发现有用的知识，提高信息利用率呢? 要想使数据真正成为一个企业的资源，只有充分利用它为企业自身的业务决策和战 略发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾因此，面对“被 数据淹没的人们，却饥饿于知识”的挑战，数据挖掘和知识发现c d m k d ) 技术应运 而生，并得以蓬勃发展，越来越显示出其强大的生命力它的出现为自动和智能地把 海量的数据转化成有用的信息和知识提供了有效的手段 数据挖掘( d m ，d a t am i n i n g ) 是指从数据库的大量数据中提取隐含的、先前未 知的并有潜在价值的信息和知识的过程数据挖掘的定义有很多，表达方式虽然不 同，但本质都是一样的本文主要采用数据挖掘从技术角度给出的定义m 数据挖掘技术的应用领域十分广阔，它可以从关系数据库、数据仓库、文本和 多媒体数据库、事务数据库和互联网等各种数据源上设法获取诸如分类模型、聚类 中【l l 大学硕士学位论文 模型、回归模型、关联模型和时间序列模型等多种知识模型刚可以说，有数据积 累的地方，就有数据挖掘技术的用武之地目前，数据挖掘技术在货篮数据分析、金 融风险预测、产品质量分析、电信、分子生物学、基因工程研究、i n t e r n e t 站点访 问模式发现以及信息搜索等领域得到了广泛的应用i ”数据挖掘技术被认为是数据 库和人工智能【9 】领域中研究、开发和应用最活跃的分支之一，汇聚了不同领域的研 究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方 面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成了新的技术 热点 1 2 数据挖掘技术的研究现状简介 到目前为止。对关系数据库和事务数据库进行数据挖掘和知识发现的研究己经 取得了一定的进展，最有影响的发现算法有：加拿大s i m o nf r a s e r 大学j h a n 教 授的概念树提升算法、i b m 的r a g r a w a l 的关联算法、澳大利亚的j r q u i n l a n 教 授的分类算法、密西根州立大学e r i c kg o o d m a n 的遗传算法等i b m ，g t e ，s a s ， m i c r o s o f t ，s i l i c o ng r a p h i c s ，i n t e g r a ls o l u t i o n s ，t h i n k i n gm a c h i n e s ，d a t a m i n d ， u r b a ns c i e n c e ，a b t e c h ，u n i c at e c h n o l o g i e s 等公司，相继开发出一些实用的k d d 商业系统和原型系统，如市场分析用的b e h a v i o r s c a n ，e x p l o r e r ，d t ( m a n a g e m e n t d i s c o v e r yt 0 0 1 ) ，金融投资领域的s t o c ks e l e c t o r ，a i ( a u t o m a t e di n v e s t o r ) ，欺 诈预警用的f a l c o n ，f a i s ，c l o n e d e t e c t o r 等 与国外相比，国内对b m k d 的研究稍晚，没有形成整体力量目前，国内从事数据 挖掘研究的人员主要集中在大学，也有部分在研究所或公司所涉及的研究领域很 多，一般集中于算法的研究、数据挖掘的实际应用以及有关数据挖掘理论方面的研 究目前进行的大多数研究项目是由政府资助进行的，如国家自然科学基金、8 6 3 计 划、“九五”计划等，但至今还没有关于国内数据挖掘产品的报道国内企业运用数 据挖掘技术来协助业务活动的应用还处于起步阶段成功应用的案例还比较少，这对 数据挖掘技术和工具的研究人员以及开发商来说，我国是一个有巨大潜力的市场 中山大学硕士学位论文 1 3 本文的选题背景与研究意义 随着数据库技术的成熟和数据应用的普及，人类积累的数据量正在以指数速度 迅速增长高校随着不断扩招，各种信息库也在不断地增多增大，学生成绩库、就 业信息库、党员信息库、人事管理库、工资库，现阶段对这些数据库的使用多数 停留在备份和查询上，这些大量数据隐藏的信息、规律没有被开发、利用譬如， 从大量以往积累的就业信息中，我们能否发现一些规律：什么样的学生到重点中学 工作，什么样的学生到小学工作，什么样的学生希望暂缓就业 数据挖掘技术在商业、金融业以及企业的生产、市场营销等方面都得到了广泛 的应用，而在高校领域应用相对较少随着数据挖掘技术的成熟及应用领域的不断 扩展，不少高校研究人员已开始研究将数据挖掘技术应用于高校的教学、管理中例 如，将数据挖掘技术应用于学生信息管理、高校的教学评估、学生成绩分析及考试 系统中，对提高学校教学管理水平起到了很好的指导作用 i o - 1 4 】 本研究将数据挖掘技术应用于就业信息分析，希望从大量积累的历史就业数据 中挖掘出有意义规则，为学校招生、培养人才提供科学决策参考依据，因此，本研 究具有十分重要的现实意义 1 4 本文的结构安排 第一章绪论数据挖掘技术研究背景及研究意义，以及国内外数据挖掘的现 状，介绍本论文的研究背景和研究意义 第二章数据挖掘技术主要介绍数据挖掘的基本知识，包括数据挖掘的过程、 数据挖掘的任务、数据挖掘的分类以及数据挖掘的常用技术和方法 第三章数据挖掘中的分类技术主要介绍数据挖掘中分类技术的基本知识、常 用分类方法，及各种分类方法的比较。 第四章数据挖掘分类技术在高校大学生就业信息中的应用主要应用数据挖 掘分类技术，建立了大学生就业决策树模型，得出分类规则，并针对地方性高校人 中山大学硕士学位论文 才培养提出了两点建议 第五章全文总结与下一步的工作主要总结本文的研究工作，创新点及下一步 的工作 中山大学硕士学位论文 第二章数据挖掘技术 本章主要介绍数据挖掘的相关知识，包括数据挖掘与知识发现的概念、数据挖 掘的过程、数据挖掘的任务、数据挖掘的分类、数据挖掘的对象，最后介绍了数据 挖掘的常用技术和方法 2 1 数据挖掘与知识发现 数据挖掘的定义有很多，表达方式虽然不同，但本质都是一样的【4 1 这里主要 采用数据挖掘从技术角度给出的定义： 数据挖掘( d a t am i n i n g ，简称d m ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的、但又有潜在的有用信息和 知识的过程 这个定义包括好几层含义：数据源必须是真实的、大量的、含噪音的；发现的 是用户感新兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放 之四海皆准的知识，仅支持特定的发现问题。 何为知识? 从广义上理解，数据、信息也是知识的表现形式，但是人们更把概念、 规则、模式、规律和约束等看作知识。人们把原始数据看作是形成知识的源泉，就 像从矿石中采矿一样原始数据可以是结构化的，如关系型数据库中的数据，也可 以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据发 现知识的方法可以是数学的，也可以是非数学的：可以是演绎的，也可以是归纳的 发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用 于数据自身的维护因此，数据挖掘是- - f l 广义的交叉学科，它汇聚了不同领域的 研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等方面的学者和 工程技术人员【1 2 j 从数据挖掘的技术角度定义，我们说数据挖掘是数据库中的知识发现 中山大学硕士学位论文 ( 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 s ，简称l ( d d ) t 3 1 的核心知识发现( k d o ) 被认为 是从数据中发现有用知识的整个过程数据挖掘只是数据库中知识发现的一个步 骤。但又是最重要的一步，它用专门算法从数据中抽取模式由于数据挖掘算法的 好坏将直接影响到k d d 所发现知识的准确性，而且目前k d d 研究大部分集中在数据挖 掘算法和应用的技术上，因此人们往往不严格区分数据挖掘和数据库中的知识发 现，两者互为使用般在科研领域中称为k d d ，而在工程领域则称为数据挖掘 2 2 数据挖掘过程 k d d l 生程如图2 1 所示，k d d 过程可以概括为三部分：数据预处理( d a t a p r e p r o c e s s i n g ) ，数据挖掘( d a t am i n i n g ) 及结果的解释和评估( i n t e r p r e t a t i o n e v a l u a ti o n ) 图2 1k d d 过程图 2 2 。l 数据预处理 数据预处理是数据挖掘( 知识发现) 过程中的一个重要步骤，尤其是在对包含有 噪声、不完整，甚至是不一致数据进行数据挖掘时，更需要进行数据的预处理，以 6 中山大学硕士学位论文 提高数据挖掘对象的质量，并最终达到提高数据挖掘所获模式知识质量的目的m 2 2 】 数据预处理又可分为四个步骤：数据清洗( d a t ac l e a n i n g ) 、数据集成( d a t a i n t e g r a t i o n ) 、和数据变换( d a t at r a n s f o r m a t i o n ) 、数据消减( d a t ar e d u c t i o n ) 数据清洗处理例程通常包括：填补遗漏的数据值、平滑有噪声数据、识别或除去异 常值( o u t l i e r ) ，以及解决不一致问题数据集成就是将来自多个数据源( 如：数据库、 文件等) 数据合并到一起由于描述同一个概念的属性在不同数据库取不同的名字， 在进行数据集成时就常常会引起数据的不一致或冗余大量的数据冗余不仅会降低 挖掘速度，而且也会误导挖掘进程因此在数据集成中还需要注意消除数据的冗余 数据转换主要是对数据进行规格化( n o r m a liz a ti o n ) 操作如把连续值数据转换为 离散型数据，以便于符号归纳，或是把离散型数据转换为连续值型数据，以便于神 经网络计算数据消减的目的就是缩小所挖掘数据的规模，但却不会影响( 或基本不 影响) 最终的挖掘结果现有的数据消减包括：( 1 ) 数据聚合( d a t aa g g r e g a t i o n ) ：( 2 ) 消减维数( d i m e n s i o nr e d u c t i o n ) ，即从初始特征中找出真正有用的特征以减少数据 挖掘时要考虑的特征或变量个数：( 3 ) 数据压缩( d a t ac o m p r e s s i o n ) ：( 4 ) 数据块消 减( n u m e r o s i t yr e d u c t i o n ) 川 2 2 2 数据挖掘 数据挖掘阶段首先要确定挖掘的任务或目的，如数据分类、聚类、关联规则发 现或序列模式发现等确定了挖掘任务后，就要决定使用什么样的挖掘算法选择 实现的算法有两个考虑因素：一是不同的数据有不同的特点，因此需要用与之相关 的算法来挖掘：二是要根据用户或实际运行系统的要求，有的用户可能希望获取描 述型的( d e s c r i p t i v e ) 、容易理解的知识，而有的用户只是希望获取准确度尽可能高 的预测型( p r e d i c t i v e ) 知识选择了挖掘算法后，就可以实旌数据挖掘操作，获取 有用的模式 2 2 3 结果的解释和评估 数据挖掘阶段发现出来的模式。经过评估可能存在冗余或无关的模式，这时需 中山大学硕士学位论文 要将其剔除：也有可能模式不满足用户要求，这时则需要回退到发现过程的前面阶 段，如重新选取数据，采用新的数据变换方法，设定新的参数值。甚至换一种挖掘 算法等另外，k d d 由于最终是面向人类用户的，因此可能要对发现的模式进行可视 化，或者把结果转换为用户易懂的另一种表示，如把分类决策树转换为“i f t h e n ”规则 数据挖掘仅仅是整个过程中的一个步骤数据挖掘质量的好坏有两个影响要素： 一是所采用的数据挖掘技术的有效性，二是用于挖掘的数据的质量和数量( 数据量的 大小) 如果选择了错误的数据或不适当的属性，或对数据进行了不适当的转换，则 挖掘的结果是不会好的 整个挖掘过程是一个不断反馈的过程比如，用户在挖掘途中发现选择的数据 不太好或是使用的挖掘技术产生不了期望的结果这时，用户需要重复先前的过 程，甚至从头重新开始 2 3 数据挖掘的分类 数据挖掘可按数据库类型、挖掘对象、挖掘任务、挖掘方法与技术等几个方面 进行分类n 2 3 1 按数据库类型分类 数据挖掘主要是在关系数据库中挖掘知识随着数据库类型的不断增加，逐步 出现了不同数据库的数据挖掘现在，除关系数据库挖掘外，还有模糊数据挖掘、 历史数据挖掘、空间数据挖掘等多种不同数据库的数据挖掘类型 2 3 2 按数据挖掘对象分类 数据挖掘除了对数据库这个主要对象进行挖掘外，还有文本数据挖掘、多媒体 数据挖掘、w e b 数据挖掘等由于对象不同，挖掘方法的差异很大 中山大学硕士学位论文 2 3 3 按数据挖掘任务分类 数据挖掘的任务有：关联分析、时序模式、聚类、分类、偏差监测、预测等 按任务分类可将数据挖掘分为：关联规则挖掘、序列模式挖掘、聚类数据挖掘、分 类数据挖掘、偏差分析挖掘和预测挖掘等类型 2 。3 4 按数据挖掘的方法和技术分类 数据挖掘的技术和方法较多包括归纳学习类、聚类方法类、统计分析类、仿 生物技术类、模糊数学类、可视化技术类等 2 4 数据挖掘的任务 数据挖掘的任务主要有关联分析、聚类分析、分类、预测、时序模式和偏差分 析等阁 2 4 1 关联分析( a s s o c i a t i o na n a l y s i s ) 两个或两个以上数据项的取值之间存在某种规律性，就称为关联，可以建立起 这些数据项的关联规则i ”j 数据关联是数据库中存在的一类重要的、可被发现的知 识，它反映一个事件和其他事件之间依赖或关联如果两项或多项属性之间存在关 联，那么其中一项的属性值就可以依据其他属性值进行预测 例如。买面包的顾客中9 0 还买牛奶，这就是一条关联规则在商场中将这两样 物品摆放在一起销售，将会提高销售量 在大型数据库中，这样的关联规则可以产生很多，这就需要进行筛选一般用 “支持度”和“可信度”两个阈值来淘汰那些无用的关联规则 9 中山大学硕士学位论文 2 4 2 聚类分析( c l u s t e r i n g ) 聚类是把数据按照它们的相似性归纳成若干类别，同一类别中的数据距离较小、 彼此相似，不同类别中的数据距离偏大、彼此相异【1 q 聚类分析可以建立宏观的概念， 发现数据的分布模式，以及可能的数据属性之间的相互关系 聚类方法包括统计分析方法、机器学习方法和神经闷络方法等在统计分析方 法中，聚类分析是基于距离的聚类，这种聚类分析方法是一种基于全局比较的聚类， 它需要考察所有的个体才能决定类的划分在机器学习方法中，聚类是无导师的学 习此时距离是根据概念的描述来确定的，又称为概念聚类，当聚类对象动态增加 时，概念聚类则称为概念形成在神经网络中，自组织神经网络方法用于聚类如 a r t 模型、k o h o n e n 模型等，这是一种无监督学习方法当给定距离阈值后，各样本 按阈值进行聚类 2 4 3 分类( c l a s s i f i c a t i o n ) 分类是数据挖掘中应用得最多的任务分类就是找出一个类别的概念描述，并 用这种描述来构造模型( 一般用规则或决策树模式表示) 类别的概念描述代表着这 类数据的整体信息，也就是该类的内涵描述【1 9 】 类的内涵描述分为：特征描述和辨别性描述特征描述是对类中对象的共同特 征的描述辨别性描述是对两个或多个类之间的区别的描述 分类的过程是：分析输入数据，经过有关算法，通过在训练集中的数据所表现出 来的特性，经过有关算法，为每一类找到一种准确的描述或者模型，并使用这种类的 描述对未来的测试数据进行分类 2 4 4 预测( p r e d i c a t i o n ) 预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种类 及特征进行预测1 2 典型的预测方法是回归分析，即利用大量的历史数据，以时间为变量建立线性 或非线性回归方程预测时，只要输入任意的时间值，通过回归方程就可求出该时 中山大学硕士学位论文 间的状态 近年来，发展起来的神经网络方法( 如b p 模型) ，实现了非线性样本的学习，能 进行非线性函数的判别 分类也能进行预测，但分类一般用于离散数值：回归预测用于连续数值：神经网 络方法预测既可以用于连续数值，也可以用于离散数值 2 4 5 时序模式( t i m e - s e r i e sp a t t e r n ) 时序模式是指通过时间序列搜索出的重复发生概率较高的模式与回归一 样，它也是用己知的数据预测未来的值，但这些数据的区别是变量所处时间的不同 在时序模式中，需要找出在某个最小时间内出现比率一直高于某一最小百分比( 最小 支持度阈值) 的规则这些规则会随着形势的变化作适当的调整时序模式中，一个 有重要影响的方法是“相似时序”用“相似时序”的方法，要按时间顺序查看时 间事件数据库，从中找出另一个或多个相似的时序事件 2 4 6 偏差分析( d e v i a ti o n ) 数据库中的数据存在很多异常情况，发现数据库中数据存在的异常情况是非常重 要的偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测 结果与模型预测值的偏差、量值随时间的变化等偏差检测的基本方法是，寻找观 测结果与参照值之间有意义的差别 2 5 数据挖掘的对象 数据挖掘的对象主要是关系数据库随着数据挖掘技术的发展，逐步进入到空 间数据库、时态数据库、文本数据库、多媒体数据库、环球网w e b 等文字、音频、 图像、视频等多媒体数据已逐渐成为信息领域的重要表现形式音频、视频的数据 量很大，要从千万计的多媒体数据中找出需要的数据和信息是很困难的目前，对 中山大学硕士学位论文 多媒体数据的处理只能在存取、编辑、集成、快进快退等基本操作上，对多媒体信 息的检索仅靠文件标识、关键字等进行检索，局限性很大目前兴起的基于内容的 多媒体检索，通过实例的查询方式，检索相似图像、音频、视频信息，已成为研究 的热点基于内容的音频、视频信息的聚类、分类、相似查询等数据挖掘技术正在 兴起 2 6 数据挖掘的方法和技术 数据挖掘方法是由人工智能、机器学习的方法发展而来，结合传统的统计分析 方法、模糊数学方法及可视化技术，以数据库为研究对象，形成了数据挖掘的方法 和技术p 御一 数据挖掘的方法和技术可分为以下六大类： 2 6 1 归纳学习法 归纳学习法是目前重点研究的方向从采用的技术上看，分为信息论方法和集 合论方法 1 信息论方法( 决策树方法) 信息论方法是利用信息论的原理建立决策树在知识工程领域，决策树是一种 简单的知识表示方法，它将事例逐步分类成代表不同的类别由于分类规则是比较 直观的，因而比较易于理解该类方法的实用效果好，影响较大由于该方法最后 获得的知识表示形式是决策树，故一般称它为决箫树方法这种方法般用于分类 任务中信息论方法中较有特色的方法有：i d 3 ，i b l e 方法 2 集合论方法 集合论方法是开展较早的方法近年来，由于粗集理论的发展使集合论方法得 到了迅速的发展这类方法中包括：覆盖正例排斥反例方法( 典型的方法有a q 系列 中山大学硕士学位论文 方法) 、概念树方法和粗糙集方法 2 6 2 聚类方法 聚类分析是直接比较样本中各样本之间的距离，将距离较近的归为一类，而将 距离较远的分在不同类中它把个给定的数据对象集合分成不同的簇种无监督分 类法其中较有特色的方法有：k - m e a n s ( k 一平均值) c l a r a 算法、b i r c h 算法、 c h a m e l e o n ( 变色龙) 算法、c l i q u e 算法等 2 6 3 统计分析方法 这是利用统计学原理对数据库中的数据进行分析的方法，统计分析既是一门独 立的学科，也作为数据挖掘的一大类方法统计分析方法包括有：常用统计( 如求大 量数据中的最大值、最小值、总和、平均值等) 、相关分析( 求相关系数来度量变量 间的相关程度) 、回归分析( 求回归方程来表示变量问的数量关系) 、差异分析( 从样 本统计量的值得出差异，来确定总体参数之间是否存在差异) 、判别分析( 建立一个 或多个判别函数，并确定一个判别标准对未知对象利用判别函数将它划归某一个 类别) 、b a y e s 网络( 利用联合概率和b a y e s 公式所描述的各网络变量间的因果关系来 进行数据分析) 2 6 4 仿生物技术 仿生物技术典型的方法是神经网络方法和遗传算法f “这两类方法已经形成 了独立的研究体系，它们在数据挖掘中也发挥了巨大的作用 1 神经网络方法 它是模拟了人脑神经元结构，以m p 模型和h e b b 学习规则为基础的，建立了三 大类多种神经网络模型( 前馈式网络、反馈式网络、自组织网络) 神经网络的知识 体现在网络连结的权值上，是一个分布式矩阵结构神经网络的学习体现在神经网 络权值的逐步计算上( 包括反复迭代或者是累加计算) 当需要从复杂或不精确数据 中山大学硕士学位论文 中获得概念比较困难的时候，利用神经网络技术特别有效经过训练后的神经网络 就像是具有某种专门知识的“专家”，因此可以像人一样从经验中学习 2 遗传算法 这是模拟生物进化过程的算法它由繁殖( 选择) 、交叉( 重组) 、变异( 突变) 三 个基本算子组成这种遗传算法起到产生优良后代的作用 这些后代需要满足适应值，经过若干代的遗传，将得到满足要求的后代( 问题的 解) 遗传算法已在优化计算和分类机器学习方面发挥了显著的效果 2 6 5 可视化技术 可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖析更清楚例 如把数据库中多维的数据变成多种图形，这对于揭示数据中的状况，内在本质以及 规律性起到很强的作用可视化数据挖掘的目的是使用户能够交互地浏览数据及挖 掘过程，提高数据挖掘效果可视化技术在数据挖掘的各个阶段都扮演着重要角色 如在数据准备阶段，使用散点图、直方图等统计可视化技术显示源数据，可以对数 据有个初步的了解，为更好的选取数据打下基础在挖掘阶段，用可视化形式描述 各种挖掘过程，从中用户可以看出数据从哪个数据仓库或数据库中抽取出来，怎样 抽取以及怎样预处理，怎样挖掘等在表示结果阶段，用可视化技术使发现的知识 更易于理解 2 6 6 模糊数学方法 由于模糊性是客观的存在，而且系统的复杂性愈高，使精确化能力便愈低，这 就意味着模糊性愈强这是z a d e h 总结出的互克性原理 利用模糊集合理论可对实际问题进行模糊评判、模糊决策、模糊模式识别、模 糊关联规则和模糊聚类分析 中山大学硕士学位论文 2 6 7 其它的方法 还有许多其它的方法如逻辑回归方法、关联规则方法、最近邻方法、文本采掘、 w e b 采掘、序列分析、s v m ，h y b r i d 等，也常被一些特定领域广泛采用 2 7 本章小结 本章主要介绍了数据挖掘的过程、分类、任务、对象和方法，为后面章节中的 数据挖掘的实际应用奠定了坚实的理论基础 中山大学硕士学位论文 第三章数据挖掘中的分类技术 数据分类( d a t ac l a s s i f i c a t i o n ) 在数据挖掘中是一项非常重要的任务，目前 在商业上应用最多，在其他领域的应用也逐渐展开本章首先介绍分类的目的、分 类的过程、分类的评估标准等分类技术的基本知识，接着介绍了决策树、贝叶斯分 类及神经网络分类等几种常用的分类方法及各种分类方法的比较 3 1 分类的基本概念 3 1 1 分类的目的 分类就是根据数据集的特点找出类别的概念描述，这个概念描述代表了这类数 据的整体信息，也就是该类的内涵描述1 1 9 , 2 4 1 分类的目的是：分析输入数据，通过在训练集中的数据所表现出来的特性，为 每一个类找到一种准确的描述或者模型这种描述常常用谓词表示并使用这种类 的描述对未来的测试数据进行分类尽管这些未来的测试数据的类标签是未知的， 我们仍可以由此预测这些新数据所属的类 分类可描述为：给定一训练数据的集合t ( 简称为训练集或训练数据库) ，t 中的 元素记录由若干个属性描述在所有属性中有且仅有一个属性作为类别属性属性 集合用矢i x = ( x l ，五，以) 表示，其中x ，( 1 f s 功对应各非类别属性，可以具有 不同的值域，即对于任一属性z = ， ，随属性的不同而变化当属性 的值域为连续值域时，该属性称为连续属性( n u m e r i c a la t t r i b u t e ) ，否则称为离散 属性( d i s c r e t ea t t r i b u t e ) ：用c 表示类别属性，c = ( q ，c 2 ，巳) 。即数据集有世个 不同的类别那么，t 就隐含地确定了一个从矢量x 到类别属性c 的映射函数h ： ，( x ) j c ，分类的目的就是采用某种方法( 模型) 将该隐含函数h 表示出来 分类器的构造方法有统计方法、机器学习方法、神经网络方法等统计方法包 1 6 中山大学硕士学位论文 括贝叶斯法和非参数法( 近邻学习或基于事例的学习) ，对应的知识表示则为判别函 数和原型事例1 2 ”机器学习方法包括决策树法和规则归纳法，前者对应的表示为决 箫树，后者则一般为产生式规则神经网络方法主要是b p 算法，它的模型表示是前 向反馈神经网络模型( 由代表神经元的节点和代表连接权值的边组成的一种体系结 构) ，b p 算法本质上是一种非线性判别函数另外，还有兴起的粗糙集( r o u g hs e t ) 方法，其知识表示是产生式规则 3 1 2 分类的主要步骤 分类( c l a s s i f i c a t i o n ) 是一个从现有的带有类别的数据集中寻找同一类别数据的 共同特性，并以此将它们进行区分的过程构造分类器的过程一般分为以下几个主要 步骤： ( 1 ) 将现有的已知类别的数据划分为训练数据和测试数据两部分 ( 2 ) 通过构造分类算法对训练数据进行学习，最终得到一个符合学习要求( 如训练 精度) 的分类模型，它可以以分类规则、决策树或数学公式等形式给出 ( 3 ) 使用分类模型对测试数据进行检测，如果符合测试要求( 如测试精度) ，则进行( 4 ) ； 否则，返回( 2 ) ( 4 ) 应用得到的分类模型对未知类别的新数据进行分类 3 1 3 分类方法的评估标准 分类问题评价一个属性集的好坏主要是衡量其类区分能力文献【2 6 】与文献 2 7 】 分别从统计学和信息论角度对分类问题中多种属性集评价标准进行了分析 目前基于信息熵i ”j 的属性评价标准应用最为广泛著名的分类器i d 3 与c 4 5 分别使用了两种基于熵的标准：信息增益( i n f o r m a t i o ng a i n ，i g ) 和增益率( g a i nr a t i o ， g r ) 文献1 2 9 1 指出了以上两种标准的缺陷，认为i g 有一种偏好较细划分的倾向而 g r 则偏好不均匀划分，文中提出了一种新的熵标准一正规增益( n o r m n i z e dg a i n ， n g ) ，并以大量的分类实验验证了n g 比i g 和g r 更有效属性选择在粗集 理论中是以求约简的形式来完成的，因此也被称为属性约筒。基于粗集理论的属性 中山大学硕士学位论文 约简方法【3 0 ”矧大多采用一致度( 也称作近似质量、分类质量) 作为属性集的评价 标准文献【3 3 】结合信息熵与粗集理论来构造属性选择标准，信息熵的加入有助于 克服粗集约简准则对噪声的敏感性和不能表达属性间概率因果关系的缺点使用神 经网络进行属性选择已存在大量的方法，对属性重要性的评价主要有两类方法 一 类是通过观察输入端有无该属性时网络输出的变化来制定相应的评价标准( 如分类 精度的变化) ；另一类则直接通过网络中与该特征相连的权重的大小来确定其相应的 重要性湘比较而言，第一类方法由于与网络的最终分类性能密切相关，因此对特征 重要性的评价更加确切为了满足能够处理大规模数据的要求，这些方法大多选择过 滤搜索策略，即先使用全部属性完成网络的分类，再删去对网络分类不重要的属性 在实际应用中，对各种分类方法的评估可以根据以下几条标准进行： ( 1 ) 预测准确率，指模型能够正确预测未知数据类别的能力 ( 2 ) 速度，指构造和使用模型时的计算效率 ( 3 ) 鲁棒性，指在数据带有噪声或有数据遗失的情况下，模型仍能进行正确预测的能 力 ( 4 ) 可扩展性，指对处理大量数据并构造相应有效模型的能力 ( 5 ) 易理解性，指所获模型提供的可理解程度 3 2 基于决策树的分类 决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法【3 4 , 3 5 , 3 6 】 图3 1 是为了解决某一问题而建立的一棵决策树，从中我们可以看到所谓决策树就是 一个类似流程图的树型结构，决策树由决策节点、分支和叶子几个部分组成其中树 的每个节点对应一个非类别属性，每条分支对应这个属性的每种可能值，而树的侮 个叶节点就代表一个类别一般决策树的中间节点常用矩形表示，而叶子节点常用 椭圆表示决策树可以很容易转换为分类规则，从根到每个叶节点的一条路径就对应 着一条分类规则目前已形成了多种决策树算法，如c l s ，i d 3 ，c h a i d ，c a r t ，f a c t ， c 4 5 ，g i n i ，s e e 5 ，s l i q ，s p r i n t 等其中最著名的算法是o u i n l a n 提出的i d 3 算法 中山大学硕士学位论文 图3 1 决策树示意图 f i g u r e 3 4ad e c i s i o nt r e e 输出决策树 图3 2 决策树生成过程 f i g u r e3 - 4t h ep r o c e s so fg e n e r a t i n gd e c i s i o nt r e e 1 9 中山大学硕士学位论文 3 2 1 决策树的生成 图3 2 简单描述了决策树生成的过程，由图中可见，决策树的生成分为学习及测 试两个阶段决策树学习阶段采用自项向下的递归方式决策树算法分成两个步骤 一是树的生成，开始时所有数据都在根节点，然后递归地进行数据划分，直至生成 时节点。二是树的修剪，就是去掉一些可能是噪音或者异常的数据决策树停止分 割的条件有：一个节点上的数据都是属于同一个类别：没有属性可以再用于对数据 进行分割 建立决策树的过程，即树的生长过程是不断的把数据进行划分的过程，每次划 分对应一个节点，也对应着一个划分属性对每个划分属性的选择都要求分成的组 之间的“差异”最大各种决策树算法之间的主要区别就是对这个“差异”衡量方 式的区别，也就是属性选择方法上的区别 建立一颗决策树可能只要对数据库进行几遍扫描之后就能完成，这也意味着需 要的计算资源较少，而且可以很容易的处理包含很多预测变量的情况，因此决策树 模型可以建立得很快，并适合应用到大量的数据上 对最终的决策树来说，在建立过程中让其生长得太“枝繁叶茂”是没有必要的， 这样既降低了树的可理解性和可用性，同时也使决策树本身对历史数据的依赖性增 大，也就是说这棵决策树对此历史数据可能非常准确，一旦应用到新的数据时准确 性却急剧下降，我们称这种情况为训练过度为了使得到的决策树所蕴含的规则具 有普遍意义，必须防止训练过度因此需要有一种方法能让我们在适当的时候停止树 的生长可用的方法有事前修剪法和事后修剪法常