（计算机应用技术专业论文）数据挖掘技术在考生志愿分析中的应用研究.pdf

河南大学硕士研究生学位论文第1 页 摘要 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，各行各业积累 了大量的历史数据，而这些激增的历史数据中往往隐藏着很多重要的信息。如何 从历史数据中及时发现有用的知识，从而挖掘出其潜在的价值，提高其利用率， 是信息处理技术研究领域的一项重要课题。作为其解决方案，近年来数据挖掘( d a t a m i n i n g ，d m ) 技术迅速崛起。 以省为单位，每年高考志愿信息相关记录高达数百万条，分布存储在省市的 多个数据库中，这些数据规模巨大，蕴涵丰富的决策信息和知识，开发这些宝贵 的信息资源，是服务高招录取工作，指导考生科学地填报志愿的一项重要任务， 是目前迫切需要解决的问题之一。 本文以数据挖掘技术为数据分析手段，根据高考志愿数据的特点和平行志愿 投档方式下考生的自我定位原则，对高考志愿及相关数据进行了分析和研究，提 出了一个基于数据挖掘技术的考生志愿风险评估模型，并给出了相应具体的算法 和解决方案。具体的有以下几个方面的工作。 1 对考生志愿相关数据进行预处理。 2 灵活运用决策树c 4 5 算法并进行改进，针对该算法易忽略小数据量属性的 缺点和为提高稀少样本精度，使用属性递归优化与经验优选策略相结合的方法； 同时提出了能进行增量学习的c 4 5 算法处理方法，生成非平衡数据集下的决策树， 设计一个志愿分析的分类器。 3 根据考生填报志愿时自我定位的实际情况，合理的选择k m e a n s 聚类算法 的初始中心，使用k m e a n s 聚类算法对院校等信息进行聚类，对高考相关数据进 行知识挖掘，获取其中规律性的潜在信息。 4 建立一个考生志愿风险评估模型，根据考生的成绩、科类、报考的专业和学 校等情况对高考录取情况进行预测，得出平行志愿投档方式下每个志愿较有可能 被录取的多个院校和该院校下的志愿风险系数，提供给高考填报志愿考生。 第1 l 页河南大学硕士研究生学位论文 据此所开发的“考生志愿风险评估系统”通过对过去三年的河南省高考志愿 相关数据进行实验测试，与当年高校实际录取情况分布基本吻合，有理由相信， 这些测试结果对来年考生在填报志愿时有着很好的参考价值。 关键词：数据挖掘；决策树；c 4 5 算法；k - m e a n s 算法；考生志愿 河南大学硕士研究生学位论文第1 1 1 页 a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to f d a t a b a s et e c h n o l o g ya n dw i d e l yu s a g eo fd a t a b a s e m a n a g e m e n ts y s t e m ，ag r e a td e a lo fh i s t o r i c a ld a t ai nv a r i o u st r a d e sa n di n d u s t r i e sh a v e b e e na c c u m u l a t e d , a n dt h a tt h ei n c r e a s i n gh i s t o r i c a ld a t ao f t e nc o n c e a lal o to fi m p o r t a n t i n f o r m a t i o n i ti sa ni m p o r t a n tr e s e a r c ht o p i ch o wt ot i m e l yd e t e c tu s e f u lk n o w l e d g e f r o mh i s t o r i c a ld a t aa n dt oe x c a v a t et h ev a l u eo fi t sp o t e n t i a lt oi n c r e a s et h e i ru t i l i z a t i o n a sp a r to fi t ss o l u t i o n ，i nr e c e n ty e a r s ，d a t am i n i n g ( d a t am i n i n g ，d m ) t e c h n o l o g yi s r i s i n gr a p i d l y t ot h ep r o v i n c ea sau n i t ，m i l l i o n so fc o r r e l a t i v ew i l lr e c o r d so fa n n u a lc o l l e g e e n t r a n c ee x a m i n a t i o ni n f o r m a t i o ni ss t o r e dd i s t r i b u t e d l yi nm u l t i p l ed a t a b a s e so fe v e r y a r e a s t h e s e l a r g e s c a l e d a t ac o n t a i nt h er i c h d e c i s i o n - m a k i n gi n f o r m a t i o na n d k n o w l e d g e d e v e l o p i n gt h e s ev a l u a b l ei n f o r m a t i o nt c s o u t c e st os e r v et h ec o l l e g e e n t r a n c ee x a m i n a t i o ne n r o l l m e n ta n dt og u i d ec a n d i d a t e st of i l lw i l l sa v a i l a b l yi sa n i m p o r t a n tt a s k ，a n di so n eo ft h ei s s u e sn e e du r g e n t l yt os o l v e t h i sp a p e rt a k e st h ed a t am i n i n gt e c h n o l o g ya st h ed a t aa n a l y s i sm e t h o d , a c c o r d i n g t ot h ec o l l e g ee n t r a n c ee x a m i n a t i o nw i s hd a t a sc h a r a c t e r i s t i ca n ds e l f - l o c a l i z a t i o n p r i n c i p l eo ft h ep a r a l l e lw i s ht h r o wf i l e ，c a r r i e so nt h ea n a l y s i sa n dt h er e s e a r c ht ot h e d a t ao fc o l l e g ee n t r a n c ee x a m i n a t i o nw i s ha n di t sc o r r e l m i v ed a t a , p r o p o s e sar i s k a s s e s s m e n tm o d e lo fe x a m i n e ew i s hb a s e do nt h ed a t am i n i n gt e c h n o l o g y ，a n dg i v e st h e c o r r e s p o n d i n gc o n c r e t ea l g o r i t h ma n ds o l u t i o n t h ec o n t e n t sa t ea sf o l l o w e d ： 1 t h ed a t ao fc o l l e g ee n t r a n c ee x a m i n a t i o nw i s ha n di t sc o r r e l a t i v ed a t ab ec a r r i e d o nt h ep r e t r e a t m e n t 2 t h e p a p e ru s e sf l e x i b l yt h ed e c i s i o n t r e ec 4 5 a l g o r i t h m a n dm a k e st h e i m p r o v e m e n t , t oc o n t r a p o s et h es h o r t c o m i n gt on e g l e c te a s i l ya t t r i b u t e so f t h el i t t l ed a t a a n dt oi n c r e a s et h es c a r c es a m p l ep r e c i s i o n ，m a k e su s eo fa s s o c i a t e dm e t h o do ft h e o p t i m i z a t i o no ft h ea t t r i b u t er e c u r s i o na n dt h eo p t i m a ls t r a t e g yb a s e do ne x p e r i e n c e ；a t t h es a m et i m e p r o p o s e st h ec 4 5a l g o r i t h m sp r o c e s s i n gm o d ew h oc a nc a r r yo nt h e i n c r e a s es t u d y ，p r o d u c e st h ed e c i s i o nt r e eu n d e rt h en o n - b a l a n c e dd a t as e t ，d e s i g n sa 第1 v 页河南大学硕士研究生学位论文 c l a s s i f i e ro ft h ew i s ha n a l y s i s 3 a c c o r d i n gt ot h ea c t u a ls i t u a t i o no ft h es e l f - l o c a l i z a t i o nw h e nc a n d i d a t e sf i l l w i l l s ，t h ep a p e rc h o o s e sr e a s o n a b l yt h ei n i t i a l c e n t e r so fk m e a n s c l u s t e r i n g a l g o r i t h m ，u s e st h ek - m e a n sc l u s t e r i n ga l g o r i t h mt oc a t yo nt h ec l u s t e r i n gw i t ht h e c o l l e g e sa n du n i v e r s i t i e s ，c a r r i e so i lt h ei n t e l l e c t i v ee x c a v a t i o nt ot h ec o r r e l a t i v ec o l l e g e e n t r a n c ee x a m i n a t i o nd a t a ，g a i n sr e g u l a rl a t e n ti n f o r m a t i o n 4 t h ep a p e re s t a b l i s h e sar i s ka s s e s s m e n tm o d e lo fe x a m i n e ew i s h ，c a r r i e so nt h e f o r e c a s tt os i t u a t i o n so ft h ec o l l e g ee n t r a n c ee x a m i n a t i o ne n r o l l m e n ta c c o r d i n gt o e x a m i n e e sa c h i e v e m e n t ，s o r to ft h es u b j e c t ，r e g i s t e rs p e c i a l t y ，s i t u a t i o n so ft h ec o l l e g e s a n du n i v e r s i t i e sa n ds oo n ，o b t a i n st h a te a c hw i s hh a v em a n yc o l l e g e sa n du n i v e r s i t i e s w h i c hc a l lb ee n r o l l e da n dr i s kc o e f f i c i e n t so ft h i sc o l l e g e sa n du n i v e r s i t i e sw i s hi nt h e p a r a l l e lw i s h p r o v i d e se x a m i n e e sw h of i nt h ew i s hd u r i n gt h ec o l l e g ee n t r a n c e e x a m i n a t i o n b a s e do nt h ea b o v et h e o 巧t h ed e v e l o p e ds y s t e mc a l l e d “r i s ka s s e s s m e n ts y s t e m o fe x a m i n e ew i s h h a se x p e r i m e n t i z e do nd a t ao ft h ec o l l e g ee n t r a n c ee x a m i n a t i o n s w i s hi n f o r m a t i o no fh e n a np r o v i n c eo fl a s tt h r e ey e a r s 。t h er e s u l ti si n o s c u l a t e dw i t ht h e d i s t r i b u t i o no ft h ec o l l e g ee n t r a n c ee x a m i n a t i o na c t u a lm a t r i c u l a t ei n f o r m a t i o no ft h a t y e a r t h e r e f o r e ，i ti sr e a l l ys u r et h a tt h et e s t i n gr e s u l t s ，a st h ee f f e c t i v er e f e r e n c ev a l u e ，a r e g o o dt oe x a m i n e eo ft h ec o m i n gy e a rf o rf i l l i n gi nw i s h 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 4 5a l g o r i t h m ；k - m e a n s a l g o r i t h m ；c a n d i d a t e sw i s h 笑寻学位论文独立完成和内番创渐前声明 本人向河南大学提窭硕士孝证章请。本人郡童声明：所呈交酮学t 主论五尧 本人在导师的才旨导下独立完成的，对所研究旮勺课趔有新的见解。据我所知，除 支峰特别加嘣说明。栎注帝致谢的地方外论文1 中不包括其他人已经发表或撂 写过的研究成杲，也不包括其他人为获得任何教育、科研机构的学伍或证书而 使用辽拍材料。与我一同工作的同葶对车科究所徽的任何贡献均巳翟论文串作 了明确酌说明并表示了谢意。 学位肆请，( 喾位论宽黪裔) 釜名：童3 垒殛色 鼬o i ：i i 牟6 月 目 荚子：学位澈囊著作投使两鞭毅韦 本人经河南犬学审核批准糍番灏士譬位。作为学位论文韵俳者。本人完全 了解并同毒河南锹孝有关保留i 糍霸弹砬勰菠韵要求，即j 确大学有权向窝篆 图书檐、科研信，黜、数据收剿几拘和奉板图书馆等掇供学位论文( 纸质支 末豸口电亍丈本) 以供罄焱检索、查阑。瓠一援枳可赢失学出于宣扬、展览学校 学术发展和进行学术交流筹司韵。豇以杀取影印、缩印、扫描牵拷贝等复青手 段保存、汇编学位论文( 纸质文本帝电子文本) 。 ( 涉及保密肉容酌学位论支在解客后运用奉援权书，j 学位获得者( 学t 至论文作者) 2r lo 甲卑6 月 日 学佐论文指导教师釜名： 盈l 垃l 2c 【o ? 卑6 月 露 河南大学硕士研究生学位论文第1 页 第1 章绪论 近年来，计算机技术和信息处理的广泛应用引起了经济结构、社会结构和生活 方式的深刻变化和变革，把人类带入了信息社会。在这一变革中，人们不再满足 于传统数据库系统中对数据的录入、查询和统计等功能，而是希望能够从激增的 数据背后发现其存在的关系和规则，根据现有的数据预测未来的发展趋势，为人 类的决策提供帮助。在这样的应用需求背景下，数据挖掘( d a t am i n i n g ，d m ) 作 为数据库中知识发现( 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 ，k d d ) n 2 1 的核心技术 迅速发展起来。k i ) d 的研究内容是如何自动地去处理数据库中大量的原始数据，从 中挖掘搜索出具有规律、富有意义的模式阳。如何从大量的高考数据中挖掘出决 策信息和有用的知识，是本文的研究课题。本章主要介绍数据挖掘技术在高招数 据中应用的研究背景、意义和现状，并简要介绍本文的主要研究内容和组织结构。 1 1 研究背景 高考向来是社会的一大热点，也是普通民众比较关注的问题。在高考过程中， 考生填报志愿是一个非常关键的一环。志愿填报是否适当，直接关系到考生能否 成功跨进入他所希望的高校学习，甚至于会影响考生一生的成长。在历年的高考 工作中，学生填报志愿都是依靠自己的分析以及老师和家长的经验。但是，这些 分析和经验很不全面，考生、老师或家长不可能了解所有学校的情况以及所有专 业的情况。另外，国家政策不断调整，各种形势变化无常，都对考生在选择学校 和专业时有巨大的影响。这些就更是个人经验难以解决的问题。 近年来，随着计算机技术的广泛普及，各省市招生办都相继采用计算机系统保 存考生信息以及招生院校，录取结果等信息。以河南省2 0 0 8 年高考为例，我省高 考考生相关记录高达8 0 0 多万条，分布存储在各级服务器的数据库中，经过传输、 汇总、集中到河南省招办，然后通过进行重组，采用新的数据组织模式，构成了 一个集成的、与时间相关的数据集合。这些信息涉及了招生院校专业调整，考生 第2 页河南大学硕士研究生学位论文 在选择学校和专业时的变化等各方面。所有这些，都对考生填报志愿有很大的帮 助。由于部门的政策及客观条件的限制，考生、老师和家长是难以访问到这些最 全面且最详尽的信息。 目前现有的高考志愿分析系统都使用心理学、计算数学的分析诊断模型、量 表和工具对历年高考数据进行统计分析晦1 ，而使用数据挖掘技术对高考志愿相关数 据进行深入分析，得出相关规则对考生填报志愿进行预测性指导的分析系统在我 国尚处于不成熟阶段。 本课题正是在此背景下提出的，其任务是对河南省招生办的招生数据进行处 理，使用数据挖掘技术，最终得到一个简洁的但较为完整的志愿填报参考准则。 1 2 研究意义 随着信息管理技术的飞速发展，各行各业都面临着前所未有的机遇和挑战。 教育考试尤其是高考作为全社会关注的焦点，同样面临着提高信息服务水平和质 量的社会需求。如何根据考生的实际情况，选择合适的学校，避免错报、高报、 低报的现象，提高填报志愿的准确性，提高考生被录取的机率，是目前迫切需要 解决的问题插3 。而数据挖掘技术是近年来兴起的新的信息处理技术，它在提供更高 层次的信息服务方面发挥着越来越重要的作用，但在高考数据分析中的应用尚处 于起步阶段。根据相关规定，有关高考数据的相关数据和由此得到的挖掘模型只能 存放于省招生办公室的专用服务器中，而各招生部门、学校和考生却是一个潜在的 多用户群体。高考数据分析具有很强的现实意义，在数百万条考生志愿数据中， 蕴藏着丰富的决策信息和知识，开发这些宝贵的信息资源，是服务高招工作，为 招生部门、学校和考生提供咨询和决策的一项重要途径和手段。本课题尝试在教 育考试领域的信息管理工作中使用数据挖掘技术，对高考成绩、志愿以及近年来 的招生数据进行分析，探索数据背后隐藏的信息与知识，最终得到一个简洁的但较 为完整的志愿填报评估准则，对考生填报志愿进行风险评估，以达到为高考决策 提供参考建议的目的，实现高考决策强有力的支持。 河南大学硕士研究生学位论文第3 页 1 3 国内外研究现状 高考作为我国一个独特的考试形式，高考领域的信息化建设较早，但数据挖 掘技术在高考数据分析中的研究非常少，对考生填报志愿进行预测性指导的分析 系统在我国尚处于不成熟阶段。 1 3 1 高考领域信息化建设的研究现状 自八十年代初期起，全国各省都相继在高考中运用计算机进行成绩处理和划 定录取控制分数线。1 9 9 0 年，湖南省在全国率先采用信息系统工程的方法，对招 生全过程使用计算机进行管理，研制了“普通高校招生管理信息系统”3 。1 9 9 6 年国家教委提出了今后几年内要在全国各省逐步推行远程网上录取的要求。在随 后的几年中，伴随新一轮高考改革的深入，教育部依托清华大学开发了全国普通 高校招生网上录取管理系统，各省也按照网上录取的要求开发了配套的信息采集 系统。高校招生网上录取依托互联网，将考生的纸介质档案改为在网上传递的电 子档案旧3 。网上录取从在2 0 0 1 年在全国所有省市全面实施，这标志着我国高考信 息管理手段的现代化又进入了一个新的历史时期。从2 0 0 5 年起，国家开始推行高 考试卷由计算机来批阅。 目前，在高考领域的信息化建设中，各级招生考试管理部门在事务操作型信 息系统的开发和利用上投入了大量的入力物力，也积聚了相当丰富的数据库资源。 与此同时，各级教育考试机构正在逐步从行政职能型向社会服务型转变，这就要 求高考工作必须更加贴近社会、面向社会需求。 2 0 0 1 年，教育部学生司和清华同方电脑公司通过中国大学生网站推出了高考 填报志愿综合参考系统阳1 ，近年来，一部分省份也陆续推出了高考志愿填报辅助参 考系统，从这些系统提供的资料来看，它仍然是一个普通的查询系统，不具备从 多个视角全面剖析数据的功能，还不能完全满足考生的需要，仍有值得进一步改 进的地方。 第4 页河南大学硕士研究生学位论文 1 3 2 数据挖掘的国内外研究现状及发展趋势 数据挖掘现在是数据库研究、开发和应用最活跃的分支之一，它涉及了计算 机科学中的多个领域，这些领域包括传统的数据库技术、人工智能、机器学习、 神经网络、统计学、模式识别、知识库系统、知识获取、信息提取、高性能计算 和数据可视化等学科一1 。随着这些学科的不断发展，数据挖掘也需要不断的发展。 作为一门新兴的技术，数据挖掘的发展也是适应科技发展大潮流的需要。针对数 据挖掘现在面临的主要问题，数据挖掘的研究与开发最主要的方向有以下一些： 与数据仓库和在线分析处理技术结合 挖掘多种类型的知识 处理复杂数据 高性能的数据挖掘 可视化和数据挖据。 数据挖掘的应用 国内从事数据挖掘研究的人员主要在大学，也有部分在研究所或公司。所涉 及的研究领域很多，一般集中于学习算法的研究、数据挖掘的实际应用以及有关 数据挖掘理论方面的研究。 国外数据挖掘研究方面主要有：对知识发现方法的研究进一步发展，如近年 来注重b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高n 们n ；传统的统计学 回归法在k d d 中的应用n 纠；k d d 与数据库的紧密结合。在应用方面注重k d d 商业软 件工具不断产生和完善，用户主要集中在大型银行、保险公司、电信公司和销售 业埒】。 数据挖掘的功能模型有：分类模型、回归模型、聚类模型、关联模型：数据 挖掘常用技术有：决策树、人工神经网络、遗传算法、近邻算法、贝叶斯、支持 向量机、k - m e a n s 、d b s c a n 等n 劓。 数据分类是数据挖掘技术的一个重要组成部分，是有效的k d d 分析方法，而 典型的分类算法是基于决策树的分类算法。决策树方法的起源是概念学习系统 河南大学硕士研究生学位论文第5 页 c l s 。引，然后发展到i d 3 方法埔1 而为高潮，最后又演化为能处理连续属性的c 4 5 仃1 ， 有名的决策树方法还有c a r t 和a s s i s t a n t 踟。9 1 。决策树是应用最广的归纳推理算 法之一。在决策树方法的发展演化过程中，也有学者另辟奚径，将粗糙集方法和 神经网络方法应用到决策树分类上。赵卫东等人将粗糙集理论应用于决策树的构 造过程，提出了一种利用粗糙集理论对决策树进行优化的算法隍训，苗夺谦等人用 相对泛化的概念构造多变量检验，提出一种评价多变量检验的准则口，张朝晖等 人提出了利用神经网络学习发现分类规则的方法，周志华等人提出了一种构造性 混合决策树学习方法c h d t 1 ，该方法用符号学习来进行定性分析，用神经网络学 习进行后续的定量分析，在一定程度上模拟了人类的思维过程。 1 3 3 数据挖掘技术在高考数据分析中的研究现状 在高考领域的信息化建设中，大多数学校和各级招生考试管理部门投入了大 量的人力物力，积聚了相当丰富的数据库资源。尽管数据挖掘技术在高招领域中 的应用不多，但近年来也不断有新的研究和应用。 2 0 0 4 年有学者提出了一种基于关键字的w e b 数字信息挖掘方法。利用该方法， 充分挖掘出w e b 页面上的关于高考招生的数据信息，在此基础上利用回归分析设 计并实现了一种基于w e b 挖掘的高考预测系统啦甜。但高考数据的大量相关数据只 能存放于招生办公室的专用服务器中，基于w e b 挖掘的高考预测系统的数据来源 没有招办专用服务器高考数据更具有权威性、准确性。 2 0 0 5 年内蒙古自治区高招参与人员构建高考数据分析模型晗耵，采用神经网络 和分类中的相关算法，对普通高考的录取数据进行分析，并对结果进行了评价， 但神经网络算法参数选取比较单一。 2 0 0 6 年西南科技大学有关人员根据数据挖掘技术的特点与高招改革的特点相 结合，建立了适用于高招管理和分析的数据挖掘模型，并采用决策树和c 4 5 算法 实现了高考学生生源分析系统3 ，返回挖掘的规则集。 2 0 0 7 年有研究人员于运用c 4 5 算法生成非平衡数据集下的二叉决策树，建立 一个高考数据分析模型诬们，并应用于高考志愿录取分类和预测中，给出了完整的 第6 页诃南大学硕士研究生学位论文 解决方案。 2 0 0 8 年研究人员将数据挖掘技术同w e b 服务技术结合，设计了一个高考志愿 分析模型；并通过对w e b 服务的s o a p 消息进行基于消息的签名和加密，保障了志 愿数据的安全性及隐私性：2 7 仲引。 但这些高考数据分析模型应用于高考录取预测中，使用数据挖掘算法时对数 据集的属性选择和属性值选择不太合理，且不具有增量学习能力，预测精度有待提 高。 近年来一部分省份陆续推出了高考志愿填报辅助系统。但这些系统只从往年 录取分数和位次角度为考生填报志愿、选择报考院校提供参考。却不能从根本上 解决考生在填报志愿时的盲目性。 1 4 研究内容 本文主要研究以下内容： ( 一) 高考数据的预处理。 本课题所需要收集的数据包括参加近几年内河南省高校入学考试考生的报名 信息库、成绩库、志愿库以及高考录取结束后的录取库。针对高考数据来源复杂、 属性繁多，域值很广，原始数据包含大量噪声数据、空缺数据和不一致数据等特 点，对数据进行抽取、清洗、转换、整理和装载等操作，通过对数据分析处理和 相关性分析，去除不相关的或冗余的属性，生成特殊的综合数据库。 ( 二) 通过对高考历史数据的分析研究，从综合数据库中取出样本集，应用数 据挖掘技术对样本集进行分析处理。 1 、利用改进的决策树算法c 4 5 进行数据挖掘，生成决策规则，对考生志愿 进行初步分析。 针对高考志愿数据大多数属性数据量较大、个别属性数据量较小，数据量少 的属性又比较重要这一事实，在决策树算法c 4 5 的基础上，同时考虑二层结点即 结点和其子结点增益，并根据经验加入优选法参数q ，使其不会出现大数据量属性 掩盖小数据量属性的现象，即：解决运用决策树算法分析高考志愿数据产生的不 河南大学硕士研究生学位论文第7 页 平衡现象( 为各个属性都建一个参数q ，形成一个属性的参数表，q 的大小由决策 者根据先验知识或领域知识来确定) ，同时提高稀少样本的精度。 通过分析和研究b a g g i n g ，a d a b o o s t 和s u b b a g g i n g 三种决策树的组合增进原 理和实现方法，改进决策树算法c 4 5 为新增量式的决策树学习算法。解决给定新 的数据集时c 4 5 算法必须重新构造一棵新树，不能利用先前生成的决策树，以至 增加高考志愿分析的工作量问题。 2 、根据平行志愿方式下考生的自我定位原则选择初始聚类中心，利用k - m e a n s 算法对院进行聚类，定义与考生志愿相关的指标，对考生志愿进一步分析。 ( 三) 用于志愿分析的考生志愿风险评估系统的实现 采用微软w i n d o w ss e r v e r2 0 0 3 、s o ls e r v e r 2 0 0 5 和v s 2 0 0 5 等作为系统开发 平台和工具，根据以上对考生志愿的分析，设计一个考生志愿风险评估系统。 为了方便考生可以更容易的使用本系统，我们在系统设计时采用了b s 结构。 这种结构可以使软件的更新更加方便，也使用户的反馈可以及时的返回。 1 5 本文章节安排 本文共分为四章。 第_ 章为绪论。主要介绍了数据挖掘技术在高校招生中研究背景、研究现状 和研究意义。 第二章为数据挖掘概论。首先介绍数据挖掘的起源；其次介绍数据挖掘的基 本概念、功能及分类；最后说明数据挖掘面临的主要问题及今后的研究发展方向。 第三章为考生志愿风险评估系统中使用的理论与相关知识。首先介绍平行志 愿方式及在此方式下考生的填报规则，并介绍考生数据的预处理知识。接着对决 策树算法和聚类算法进行了介绍，对c 4 5 算法和k - m e a n s 算法进行了改进。 第四章为考志愿风险评估系统的设计与实现。首先介绍了该系统的需求和总 体设计，接着介绍该系统的数据库接口，对改进的c 4 5 算法和k - m e a n s 算法进行 了描述，给出了系统的界面。 第8 页河南大学硕士研究生学位论文 第2 章数据挖掘概述 随着计算机硬件和软件的飞速发展，尤其是数据库技术与应用的日益普及， 人们面临着快速扩张的数据海洋，如何有效利用这一丰富数据海洋的宝藏为人类 服务，业已成为广大信息科技工作者所重点关注的焦点之一。为有效解决这一问 题，自二十世纪8 0 年代开始，数据挖掘技术逐步发展起来。而分类和聚类作为数 据挖掘中的重要的方法，目前的研究在商业上应用最多眨引。 本章主要介绍数据挖掘的基本理论。本文在考生志愿分析中所研究的决策树 算法和k - m e a n s 聚类算法是两种典型的数据挖掘技术，要更好的理解具体算法和 志愿分析的应用，需要了解数据挖掘的相关理论。 2 1 数据挖掘的基本概念 数据挖掘是从大量数据中识别出有效的、新颖的、有用的，以及最终可理解 的知识和模式的高级过程。其中数据是描述事物的信息集合，是我们进步发现 知识的原材料啪1 啪1 。 新颖：经过数据挖掘提取出的模式必须是新颖的。模式是否新颖可以通过两 个途径来衡量：其一是通过对比当前得到的数据和以前的数据或期望得到的数据 之间的比较来判断该模式的新颖程度；其二是通过对比发现的模式与已有的模式 的关系来判断。 潜在有用：即提取出的模式应该是有实际意义的。 可被人理解：数据挖掘的一个目标就是将数据库中隐含的模式以容易被人理 解的形式表现出来，从而帮助人们更好地了解数据库中所包含的信息。数据挖掘 不同于以往知识获取技术，它的特点之一是发现的知识是人们( 至少是领域专家) 易于理解的，如”i f t h e n 的形式。因此挖掘过程也是一个人机交互、螺旋上升 的过程。 模式：对于集合f 中的数据，可以用语台l 来描述其中数据的特性。e 属于 河南大学硕士研究生学位论文第9 页 l ，e 所描述的数据是集合f 的一个予集f e 。只有当表达式e 比列举所有f e 中元索 的描述方法更为简单时，才可称之为模式。 高级过程：数据挖掘是对数据进行更深层处理的过程，而不是仅仅对数据进 行加减求和等简单运算或查询，因此说它是个高级的过程。 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是数 据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信 息应具有先未知、有效和可实用三个特征。 先前未知的信息是指该信息是预先未曾预料到的，数据挖掘是要发现那些不 能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越是 出乎意料，就可能越有价值。 2 2 数据挖掘的应用对象 一般来讲，数据挖据所依赖的数据源多种多样，可以是常用的关系数据库、 事务数据库、数据仓库、高级数据库系统、文本数据库、多媒体数据库等，主要 取决于用户的目的及所处的领域3 。 ( 1 ) 关系数据库 数据库系统，也称数据库管理系统( d b m s ) ，由一组内部相关的数据和一组管 理和存取数据的软件程序组成。软件程序涉及如下机制：数据库结构定义，数据 存储，并发、共享或分布的数据访问，在面对系统瘫痪或未授权的访问时确保数 据的一致性和安全性。 关系数据库是表的集合，每个表都赋予一个唯一的名字，关系数据一般可以 通过数据库查询的方式进行访问。数据库查询使用关系查询语言，如s q l 语言， 或者借助于图形用户界面书写。当数据挖掘用于关系数据库时，可以进一步搜索 趋势或数据模式。在数据挖掘的数据源中，关系数据库是数据挖掘最流行的、最 丰富的数据源，因此它是我们数据挖掘研究的主要数据形式。 ( 2 ) 事务数据库 事务数据库通常由一个文件组成，其中每个记录代表一个事务。通常，一个 第1 0 页河南大学硕士研究生学位论文 事务包含一个唯一的事务标识号( t r a n s a c t i o ni d ，简称t i d ) ，和一个组成事务的 项的列表。事务可以存放在表中，每个记录代表一个事务。 ( 3 ) 数据仓库 数据仓库是一种全新的数据存储模式。它是一种语义上一致的数据存储，充 当决策支持数据模型的物理实现，并存放企业战略决策所需的信息。与其他数据 存储系统相比，数据仓库具有面向主题的、集成的、时变的等特征。 数据仓库最常见的应用有三种： 信息处理：支持查询和基本的统计分析，并使用交叉表、表、图表、或图进 行报告。 分析处理：支持基本的联机分析处理( o l a p ) 操作。一般地，它在汇总的和 细节的历史数据上操作。同时，它支持数据仓库的多维数据分析。 数据挖掘：支持知识发现，包括找出隐藏的模式和关联，构造分析模型，进 行分类和预测，并用可视化工具提供挖掘结果。 在数据仓库的三种应用中，信息处理可以反映直接存放在数据库中的信息， 但并不反映复杂的模式或隐藏在数据库中的规律。联机分析处理可以由用户选定 的数据仓库子集，在多粒度上导出汇总的信息，由此帮助简化数据分析。而数据 挖掘则更进一层，它的目标是尽可能自动地发现隐藏在大量数据中的隐含模式和 有趣知识。 ( 4 ) 高级数据库及高级数据库的应用 高级数据库系统是面向特殊应用的数据库系统，包括以下几种： 面向对象的数据库、空间数据库、时间和时间序列数据库、文本数据库、多 媒体数据库、异种数据库和基于w w w 的全球信息系统。 2 3 数据挖掘的功能及分类 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般 可以分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般性。预测 性挖掘任务在当前数据上进行推断，以进行预测1 。 河南大学硕士研究生学位论文第1 1 页 数据挖掘功能及它们可以发现的模式类型主要有概念类描述，关联分析，分 类和预测，聚类分析，孤立点分析，演变分析等n 州。 ( 1 ) 概念类描述 数据可以与类或概念相关联。用汇总的、简洁的、精确的方式描述每个类和 概念可能是有用的。这种类和概念的描述称为类概念描述。这种描述可以通过下 述方法得到： 萝数据特征化：是目标类数据的一般特征或特性的汇总。 数据区分：是将目标类对象的一般特性与一个或多个对比类对象的一般特 征比较。 数据特征化和比较：同时利用数据特征化和数据区分进行描述。 ( 2 ) 关联分析 关联分析发现关联规则，这些规则展示属性一值频繁地在给定数据集中一起出 现的条件，描述了大量数据中数据项集之间隐含的相关联系和有趣关系。 ( 3 ) 分类和预测 分类是找出描述并区分数据类或概念的模型，以便能够使用模型预测类标记 未知的对象类的过程。预测是构造和使用模型评估无标号样本类，或评估给定样 本可能具有的属性值或值区间。分类用来预测类标记，而通常预测限于值预测， 因此分类和预测是不相同的。 ( 4 ) 聚类分析 聚类用于从数据集中找出相似的数据并组成不同的组。与分类和预测不同， 聚类分析数据对象，而不考虑已知的类标记。 ( 5 ) 孤立点分析 数据库中可能包含一些数据对象，它们与数据的一般行为或模型不一致。这 些对象称为孤立点。大部分数据挖掘方法将孤立点视为噪声或异常而丢弃。然而， 在一些应用中，罕见的事件可能比正常出现的那些更有趣、因而更有价值。 ( 6 ) 演变分析 第1 2 页河南大学硕士研究生学位论文 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。尽管 这可能包括时间相关数据的特征化、区分、关联、分类或聚类，这类分析的不同 特点包括时间序列数据分析、序列、或周期模式匹配和基于类似性的数据分析。刚。 2 4 数据挖掘过程 数据挖掘一般按照以下的步骤进行： ( 1 ) 问题理解与陈述 该步骤要求对所要处理的问题有正确的理解，同时要有精确的描述，因为数 据挖掘是面向应用的，只有对数据挖掘所要应用的对象有充分的理解并把对问题 的理解准确的描述出来，才能使工程设计人员选择适当的挖掘技术和挖掘工具对 对象进行操作； ( 2 ) 数据预处理 该步骤主要对分析数据进行整理，把数据转换为合理的格式进行存储，以备 挖掘使用； ( 3 ) 建模 根据实际问题的特点，建立合适的挖掘模型； ( 4 ) 模型评估 在该步骤中，需要选择适当的数据挖掘技术，并对技术进行实现。而对挖掘 技术的实现是建立在多个模型的基础上的，模型评估要对发现的模式进行解释和 选择，去除多余和无用的模式，选出最优模型。评估方法可以用原先的数据对模 型进行测试，也可以用新的数据进行。根据测试结果可能要对挖掘模型进行进一 步改进和完善，因此数据挖掘是一个不断反馈的过程； ( 5 ) 得出结论 该步骤对挖掘结果进行解释，并把挖掘结果以易于用户理解的形式提供给用 户。结果提供形式可以是规则集、可视化结果等。同时根据挖掘得出的结果，对 挖掘模型进行详细说明。 河南大学硕士研究生学位论文第1 3 页 2 5 数据挖掘的常用方法 数据挖掘的方法很多，其中最常用的方法有概念描述法、决策树分类法、基 于划分的聚类方法等。 2 5 1 概念描述法 概念描述( c o n c e p td e s c r i p t i o n ) 就是通过对某类对象关联数据的汇总、分 析和比较，对此类对象的内涵描述，并概括这类对象有关特征。传统的有求和值、 平均值和方差等统计值，或者用柱状图和饼状图来显示概念描述的结果。概念描 述法在本文进行考生数据的预处理时有所应用。 2 5 2 决策树分类法 数据挖掘中决策树( d e c i s i o nt r e e ) 是一种经常要用到的技术，可以用于分析 数据，同样也可以用来作预测。常用的算法有i d 3 、c h a i d 、c a r t 、q u e s t 和c 4 5 、 p u b l i c 3 。 决策树分类( d e c i s i o nt r e ec 1 a s s i f i c a t i o n ) 是利用信息论中互信息( 信 息增益g a i n ) 寻找数据库中具有最大信息量的属性字段，建立决策树的一个结点， 在根据该属性字段的不同取值建立树的分支。决策树分类是类似于流程图的树结 构。本文以一个改进决策树算法的应用为例，进一步讨论了对树进行优化时可能 涉及的问题。 2 5 。3 基于划分的聚类方法 给定一个包含n 个数据对象的数据库，构建数据的k 个划分，每个划分表示 一个簇，且k n 。通常会采用一个相似度函数作为划分标准，例如距离。以便衡 量在同一个簇中的对象是“相似的 ，在不同簇中的对象是“相异的”。这些聚类 方法对在中小规模的数据库中很适用发现球状簇。划分聚类是由一个初始划分开 始，通过一个优化评价函数把数据从初始划分分解成若干子划分，输出的是多个 互不相交的聚类集，常用的主要算法有：k - m e a n s ，k - m e d o i d s ，c l r a r ，c l r a r a n s 盘占 3 3 】 弋to 第1 4 页河南大学硕士研究生学位论文 k - m e a n s 算法的思想：给定类的个数k ，将n 个对象分到k 个类中去，使得类 内对象之间的相似性最大，而类间相似性最小。k - m e d o i d