（计算机应用技术专业论文）基于聚类在自考考生流失多重因素分析中的应用研究.pdf

摘要 摘要 深入了解自学考试考生流失的综合凶素，对提高自考管理水平十分重要。北京 市自学考试业务系统拥有近十年来较为完整的考生信息数据库，应用数据挖掘对其 海量数据进行分析处理，具有很强的理论与现实意义。 本文应用数据挖掘技术中聚类分析方法及其划分算法，对高等教育自学考试( 自 考) 流失考生的多重因素进行了分析，重点分析整理了北京市7 年( 2 0 0 1 - 2 0 0 7 ) 的 自考数据库，得出了自学考试考生流失的综合凶素，并通过一般统计方法进行了验 证。 本研究分为样本定义、提取及预处理、算法选择及实现和后验证等几个步骤。 在样本定义时，首先明确了考生流失的概念，确定了使用毕业生“跨度”和“暂 停期”作为考生流失的特征，并根据流失数据与毕业生数据的比较分析，确定了流 失特征量的阈值。 在样本提取及预处理时，以样本定义为依据，对白考数据库进行了处理，提取 了流失样本，进行了数据标准化。样本属性选择是应用聚类分析方法的前提。本文 通过分析候选属性在毕业生和流失考生中的相对分布，观察其是否有显著差别的方 法，确定了年龄、性别、职业等1 8 个属性，完成了样本预处理。 在应用聚类分析方法时，重点研究和实现了划分方法中的k - m e a n s 算法，介绍 了k 值确定的实验过程，依据类内间距的计算结果对最优结果进行了选择与科学评 价。研究中使用c + + 语言编程，完整实现了数据库的自动处理、相应算法实现、结果 输出等功能，论文中给出了全部伪代码及流程描述。 在后验证中，通过常规统计方法，对聚类分析结果进行了验证，结果基本相符。 本文是聚类在国内考生流失问题上的首次应用。作者通过研究，找出了自学考试 考生流失的综合因素，在一定程度上解决了考试系统一直以来存在的拥有海量数据 但是不能利用的矛盾。本文的研究成果不但为调整和制定相关政策提供了可靠依据， 也为数据挖掘这一先进技术在考试系统中深入发展作了有益尝试，为后继研究者利 用数据挖掘解决考试系统中的问题，提供了一条可行的思路。 关键词数据挖掘；聚类；k 均值；自学考试；考生流失 a b s t r a c t a b s t r a c t i t i sv e r yi m p o r t a n tf o rt h ea d m i n i s t r a t o r st oc o m p r e h e n s i v e l yu n d e r s t a n dt h e p r i n c i p a lc a u s e so ft h ed r o p o u t si ns e l f - t a u g h th i g h e re d u c a t i o ne x a m i n a t i o n s ( s t h e e ) ， s o a st o i m p r o v et h ea d m i n i s t r a t i v ee f f i c a c y b e i ji n gs e l l t a u g h ts y s t e mh a sal a r g e d a t a b a s ec o n t a i n i n gf a i r l yc o m p l e t ed a t ao fe x a m i n e e si nt h ep a s t10m o r ey e a r s i tw i l l h a v eh i g ha c a d e m i ca n dp r a c t i c a lv a l u eb ya p p l y i n gd a t am i n i n ga sa na p p r o a c ht o a n a l y z ea n ds o r to u tt a r g e t e di n f o r m a t i o nf r o mt h o s ed a t a c l u s t e r i n ga n a l y s i s ，i np a r t i c u l a rp a r t i t i o n i n gw i t hk - m e a n sa l g o r i t h m ，h a sb e e n i m p l e m e n t e di n t h i sp r o j e c tt oa n a l y z ed a t ao ft h el a s t7y e a r s ( 2 0 0 1 - 2 0 0 7 ) o fb e i j i n g s t h e e i tf i g u r e do u tp r i n c i p a lc a u s e so fd r o p o u t ，a n dp r o v e dt h a tb yc r o s sc h e c k i n gw i t h c l a s s i c a ls t a t i s t i cm e t h o d o l o g i e s t h ed a t aa n a l y s i sw a sc o m p l e t e di ns e v e r a ls t e p si n c l u d i n gs a m p l ed e f i n i t i o n ，d a t a e x t r a c t i o na n dp r e - p r o c e s s i n g ，a l g o r i t h me v a l u a t i o n i m p l e m e n t a t i o na n dp o s th o c v e r i f i c a t i o n t h ed e f i n i t i o no fd r o p o u tw a sd e t e r m i n e dw i t ht w oa t t r i b u t e so f c y c l el e n g t h a n d “s i l e n tp e r i o d ”t h r e s h o l d sf o rd r o p o u tw e r ea l s od e f i n e da f t e rt h ea n a l y s i so fg r a d u a t e s a n dd r o p o u t ss a m p l e s o n c et h ed r o p o u ta t t r i b u t e sa n dt h r e s h o l d sw e r ei np l a c e ，s a m p l e s w e r es o r t e do u to ft h ed a t a b a s ea n dw e r es t a n d a r d i z e di n p r e p r o c e s s i n g t h e i d e n t if i c a t i o no fa t t r i b u t e sw a sr e q u i r e da st h ep r e m i s eo fd a t ap r o c e s s i n gi nc l u s t e r a n a l y s i s t h ed i s t r i b u t i o np a t t e r no fe a c ha t t r i b u t ew a sc a r e f u l l yc o m p a r e di ng r a d u a t e s a n dd r o p o u t s i ft h e r ew a ss i g n i f i c a n td i f f e r e n c ei nd i s t r i b u t i o nb e t w e e nt h ea b o v et w o g r o u p s ，t h e ni tw a si d e n t i f i e da sa na t t r i b u t ev a r i a b l e b yt h i sm e t h o d ，t o t a l l yt h e r ew e r e e i g h t e e na t t r i b u t e si n c l u d i n ga g e ，s e x ，o c c u p a t i o n ，e t c s e l e c t e da sv a r i a b l e si n t ot h en e x t s t 印 k - m e a n sw a st h ep r i m a r ya l g o r i t h mi nt h i sp r o je c t t h i sp a p e rr e p o r t e di nd e t a i l s a b o u tt h ep r o c e d u r e so fk f a c t o r sd e t e r m i n i n g ，d i s t a n c ec a l c u l a t i o no fc l u s t e r s ，a n dr e s u l t s o p t i m i z a t i o n a l ld a t ap r o c e s s i n gw a sa u t o m a t i c a l l yd o n ei na na p p l i c a t i o nc o m p i l e do f c 抖t h ep r o g r a mf l o wc h a r t sa n dm a jo rs o u r c ec o d e sw e r ea l s os h a r e di nt h i sp a p e r c l a s s i cs t a t i s t i cm e t h o d o l o g yw a su s e di nt h ep o s th o cv e r i f i c a t i o n a l lr e s u l t sw e r e w e l lc o r r e l a t e d t h i si st h ef i r s ta t t e m p ti nc h i n aa n a l y z i n gd r o p o u t sw i t hd a t am i n i n gc l u s t e r i n g t h ep r i n c i p a lc a u s e sw e r es o r t e do u ta n dv e r i f i e d t h es u c c e s s f u lp r a c t i c ef o u n d e dan e w w a yt of i n do u ta na n s w e rf r o mt h ee n o r m o u sd a t a b a s ew i t h o u tm i n i n ga n df u r t h e rs t a t i s t i c a n a l y s i sb e f o r e t h o s er e s u l t sh a v ep r o v i d e dv a l u a b l ei n f o r m a t i o nf o rt h ea u t h o r i t i e si n p o l i c ym a k i n gt oi m p r o v ea d m i n i s t r a t i v ee f f i c a c y , a n df u r t h e rm o r e ，t h i sa t t e m p tp r o v i d e d a na p p r o a c hf o ro t h e rr e s e a r c h e r st oe x t e n dd a t am i n i n gi n t op r o b l e ms o l v i n gi nn a t i o n a l s e l f - t a u g h te d u c a t i o ns y s t e m k e yw o r d sd a t am i n i n g ；c l u s t e r i n ga l g o r i t h m ；k - m e a n s ；s e l f - t a u g h th i g h e re d u c a t i o n 北京t 、i p 人学p 硕十1 _ 奇：论文 e x a m i n a t i o n s ；e x a m i n e el o s s i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 签名：垒鱼羔日期：型 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保 留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：堡! ! 兰导师签名娥j 州 第1 章绪论 第1 章绪论 1 1 本研究课题的学术背景 随着现代信息技术、通讯技术、数据库技术、网络技术、数字化图书馆和计 算机技术的高速发展及数据库管理系统的广泛应用，加上使用先进的自动数据生 成和采集工具，使得数据库存储的数据量急剧增大。例如。n a n a 轨道卫星上 的地球观测系统e o s 每小时会向地面发回5 0 g b 的图象信息；世界上最大的数 据仓库之一，美国的零售商系统w a l m a r t 每天会产生约2 亿次的交易数据；人 类基因组数据库项目已经收集了数以g b 的人类基因编码数据等。据统计，全球 的信息量每2 0 个月翻一番。面对“堆积如山 的数据集合，无论在时间意义上 还是在空间意义上，传统的数据分析手段都难以应付，人们无法有效地理解并使 用这些数据，由此导致越来越严重的“数据灾难”，造成大量数据资源的浪费。 传统的信息系统大部分是查询驱动的，数据库作为历史知识库对于一般的查询过 程是有效的。传统的数据分析方法只能获得这些数据的表层信息，很难对数据进 行深层次的处理，而且不能获得数据属性之间的内在关系和隐含的信息，即不能 获得重要的有价值的知识。这样，海量数据的生成和搜索技术与滞后的数据分析 之| 、日j 形成了鲜明的对照，这需要新的技术来自动、智能和快速地分析海量的原始 数据，以使消耗大量财力与物力收集与整理到的宝贵资源数据得以充分利 用，由此引发了一个新的研究方向：数据挖掘与知识发现的理论与技术研究。 数据挖掘与知识发现技术是计算机领域一个非常有活力的研究课题，其研究 成果已广泛应用于金融、医疗保健、零售、制造业、工程与科学等行业。十多年 来，在教育考试领域，大力推进现代化、信息化建设，从最初的计算机采集考生 数据，到网上报考、网上阅卷等工作的丌展，目前已逐步成熟，积累了大量的考 生数据。如何很好的利用现有的数据资源，更贴近考生、了解考生的状况，如何 为考生提供更人性化的服务，体现已人为本的现代化教育。我们的课题研究过程 就是利用数据挖掘中的聚类分析方法寻找高等教育自学考试考生各种属性和考 生流失之间的关系，为领导提供有实的数据，提供有效的建议，更好的服务于教 育机构，服务于考生。 1 2 国内外研究现状 1 2 1 对考生流失的研究现状 国外对于高等教育中学生辍学的研究开始得很早，在7 0 年代以后形成了比 北京i 、i k 人l ：硕f j 学何论文 较完整的理论体系，由于国外没有自学考试，我们考察了与自学考试相近的国外 远程教育辍学研究发展与现状。 国外对于远程教育的学生辍学主要从学生的特征和环境，学习者的行为，课 程设置影响等方面去寻找辍学规律，建立模型，已形成了相当的理论体系： 如k e n n e d y 和p o w e l l i2 1 于1 9 7 6 年提出的二维辍学模型，这个模型在9 0 年代 作了一些改进和调整，它主要描述了预定特征( 教育背景、社会背景、经济背景 和学习动机等) 、生活改变( 家庭关系变化、身体状况和工作变化等) 和教育制 度和组织( 课程结构、课程传输、交互作用和支持系统等) 三个影响辍学因素的 交互作用。 又如s p a d y 3 】的第一代动态模型和在它的基础上发展出来的t i n t o 的第二代 动态模型，这两个模型受到“自杀模型”启发，从学习者行为的结果、行为的态 度、行为的目的以及行为本身的关系来研究辍学的原因。尤其是后者，比s p a d y 模型更加线性化，被整个教育辍学问题的研究者所重视和大量引用。在此之后还 有k e m b e r 在1 9 8 9 t 3 j 年提出的模型，他对t i n t o 模型进行了修改，更加强调了学 习者的特征和社会背景的影响。 9 0 年代后期到现在，关于网络和在线学习的辍学问题的研究在国外也开始 进行。 国外的远程教育理论体系已相对完备，但对网络时代的辍学问题还在探究阶 段，还没有成型的理论，但整个理论体系对如何降低辍学率，如何解决学习者的 学习障碍等方面并没有取得有效的成果和进展。【4 】 和国外的研究相比，国内的辍学研究进展要更缓慢，目前国内还没有进行过 大范围的调研，虽然有些机构进行过几次小规模的样本抽查，但几乎都未公开过 调查结果，更没有对结果做过理论解释。这些研究都是针对学生的单一属性进行 的简单统计分析，不能较全面的反映学生流失的主、客观原因。本研究从考生多 个属性出发，使用数据挖掘中聚类分析的方法，寻找出自考流失考生的主要特征， 揭示出考生流失的综合因素。 1 2 2 数据挖掘技术国外研究现状 1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论 会上首次提出“数据库中的知识发现”( k d d ) 技术。随后，在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举办了k d d 专题讨论会，汇集了来自各个领域的研究人员和应 用开发者，集中讨论了数据统计、海量数据分析算法、知识表现、知识运用等问 题。随着参加会议人数的不断增多，从1 9 9 5 年开始，每年都要举办一次k d d 国际会议。另外，从1 9 9 7 年开始，k d d 拥有了自己的专门杂志( k n o w l e d g e d i s c o v e r ya n dd a t am i n i n g ) ) ，k d d 包括数据预处理、数据挖掘、知识评价等处理 过程。数据挖掘是k d d 过程中的关键步骤，是指从大型数据库或数据仓库等数 第1 章绪论 据源中提取人们感兴趣的知识，这些知识是隐含的、事先未知的潜在有用信息， 提取的知识一般町表示为概念、规则、规律、模式等形式。用数据库管理系统来 存储数据，用机器学习的方法来分析数据，挖掘人量数据背后的知识，两者的结 合促成了数据挖掘技术的产生。1 5 】 由于数据库中的数据被形象地比喻为矿床，因此，数据挖掘一词很快流传丌 来。由于它应用的普遍性及由此带来的高效益，新型的数据分析技术数据挖 掘成为一个具有广阔应用前景的热门研究方向。许多公司纷纷推出了自己的数据 挖掘系统。目前，世界上比较有影响的典型数据挖掘系统有：s a s 公司的 e n t e r p r i s em i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、s g i 公司的s e t m i n e r 、s p s s 公 司的c l e m e n t i n e 、s y b a s e 公司的w a r e h o u s es t u d i o 、r u l e q u e s tr e s e a r c h 公司的 s e e 5 、还有c o v e r s t o r y 、e x p l p r a 、k n o w l e d g ed i s c o v e r yw o r k b e n c h 、d b m i n e r 、 q u e s t 等。 2 0 0 1 年，g a r t n e rg r o u p 的一次高级技术调查将数据挖掘和人工智能列为“未 来三到五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理 体系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。 1 2 3 数据挖掘技术国内研究现状 与国外相比，国内对数据挖掘的研究稍晚。我困的数据挖掘研究开始于9 0 年代中期，到9 0 年代中后期，初步形成了知识发现和数据挖掘的基本框架。自 9 0 年代中期一批研究成果( 学术论文) 逐渐发表在计算机学报、计算机研 究与发展、软件学报、人工智能与模式识别等刊物上。研究重点也正在从 发现方法转向系统应用，并且注重多种策略和技术的集成，以及多种学科之间的 相互浸透。但是基本上还是以学术研究为主，实际应用上处于起步阶段。【7 1 1 9 9 3 年国家自然科学基金首次支持我们对该领域的研究项目。目前，国内的许多科研 单位和高等院校竞相丌展知识发现的基础理论及其应用研究，这些单位包括清华 大学、中科院计算技术研究所、空军第三研究所、海军装备论证中心等。其中， 北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，华中 理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学 等单位开展了对关联规则算法的优化和改造；南京大学、四川联合大学和上海交 通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘。1 9 】 同时，数据挖掘技术在教育层面上的应用已经开始，但并不广泛。浙江大学 使用关联规则发现技术对高校的人事信息库进行挖掘，试图找到影响学科发展的 因素，发现如何评价一个学科，以及影向学科发展的各个要素之间的关系。另外， 曲阜示范大学体育系与上海闵行体委人才的选拔探讨了数据挖掘的可行性。在每 年对中小学生的体质调查中，积累了大量的数据，利用数据挖掘技术，他们试图 从数据中深入寻找各种冈素的相互联系，发现一些随诸因素动态变化而产生的新 北京川k 人学i 学硕t j 学何论文 的指导学校体育科研和教学训练的规律，进而发现运动人才。近几年，数据挖掘 在高校中的应用也越来越多，大连交通大学尝试了关联规则在教务管理中的应用 研究【6 】，华东师范大学尝试了数据挖掘技术在高校教学质量评估中的应用研究【7 】， 等等。 北京工业大学在考试方面曾做了成人招生考试【8 j 和自学考试【9 l 的一些研究， 但是，总体上数据挖掘技术应用于考试系统中的研究还比较少，这对数据挖掘技 术和工具的研究人员以及开发商来说，我国是一个有巨大潜力的市场。 1 3 课题来源与主要研究内容 高等教育自学考试自1 9 8 1 年开考至今已经历了2 6 年，全国累计参加自学考 试的考生已达到近2 亿人次，本、专科毕业生3 0 0 余万人，为我国高等教育的改 革和发展做出了重要贡献。白考是一种以个人自学、社会助学、国家考试相结合 的高等教育形式，具有开放性、学制灵活、花费低、学习方法自主、学习时间自 由、不受年龄限制等特点，具有很多其他形式的高等教育无法比拟的优势，深受 社会各界考生的欢迎。【l o 】 但从每年的新考生和毕业生人数比例来看，可以看出有大量的考生没有完成 所选的专业课程，放弃了自考，形成了考生中的“流失】。考生流失的原因很 多，正常的流失是不可避免的，但减少一些客观条件造成的流失，不仅对自学考 试本身，对社会、经济都将具有进步意义。既有利于我国终生教育体系的建立和 高等教育大众化，也有利于学习化社会的形成，为国家和个人教育投资都将起到 不可小视的积极作用。 自考的高流失现象一直困扰着自考的管理工作，同时也不同程度的影响着考 生选择自考学习。北京教育考试院自学考试办公室积累了大量的考生数据，其中 近7 年的数据较完整，统计发现自2 0 0 1 年至2 0 0 7 年，报考人数最多的一年近 4 0 万人，而我们数据库中却保留着同期考生数据近2 0 0 万条，因此，大大增加 了管理难度，提高了管理成本。分析流失的因素，一方面，为自考考生数据管理 提供一种可行的方法；另一方面，为调整和制定自学考试的相关政策提供可靠依 据，指导更多的考生完成学业，对自学考试和全民教育、终生教育的可持续发展 有着重要的意义。 从研究现状来看，目前国内对高等教育尤其是自学考试的考生流失研究是非 常不够的。北京教育考试院自学考试办公室累积了l o 多年自考考生的相关数据， 这些数据包含了考生的基本信息、参加考试情况、成绩等相关属性。由于数据量 大，很难找到各种属性和考生流失之间的关系，因此在分析中引入数据挖掘技术， 主要研究以下几个方面的内容： - 4 第1 章绪沦 ( 1 ) 科学定义考生流失的概念、提取流失样本； ( 2 ) 根据流失数据与毕业生数据的比较分析，合理确定流失属性； ( 3 ) 重点研究聚类分析方法及其划分算法在此项目中的应用； ( 4 ) 使用c + + 语言实现k m e a n s 算法，得到聚类结果，并进行相关分析； ( 5 ) 运用常规统计方法对聚类结果进行验证。 1 4 论文组织结构 论文的结构安排如下： 第1 章绪论 简述了本研究课题的背景、研究现状及其理论与现实意义。 第2 章数据挖掘相关技术 本章主要介绍了数据挖掘一些基本概念。阐述了数据挖掘产生的历史必然 性，给出了数据挖掘的定义，介绍了数据挖掘的任务、数据挖掘的主要技术方法。 并对聚类分析方法作了简单介绍，包括聚类规则的定义、分类、评价标准和相关 概念。 第3 章考生流失因素分析与相关数据的确定 本章主要在介绍自考主要业务和当前业务系统的基础上，分析了考牛流失的 主要因素，提出了应用聚类方法解决本研究的必要性。并科学定义了自考考生流 失的概念，提取了流失样本，确定了流失特征。 第4 章聚类分析算法研究及设计实现 本章是论文的核心。通过对聚类方法中的划分方法及本研究使用的k m e a n s 算法的深入研究，同时分析整理了北京市7 ( 2 0 0 1 2 0 0 7 ) 年的自考数据，科学确 定流失特征，合理选用数据标准化方法，成功的实现了该算法在自考考生流失多 重因素的聚类分析研究，并给出了全部伪代码及流程描述。 第5 章聚类结果分析与验证 本章介绍了k 值确定的实验过程，依据类内间距的计算结果对最优结果进行 了选择与科学评价，同时对挖掘结果进行了分析，并通过传统方法对其进行了验 证，证明其有效性。 最后，对本论文做了总结和展望。 第2 章数据挖掘相关技术 2 1 数据挖掘 第2 章数据挖掘相关技术 数据挖掘是通过仔细分析大量数据来揭示有意义的新的关系、趋势和模式的 过程。是数据库研究中一个很有应用价值的新领域，是一门很广义的交叉学科， 它汇聚了不同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并 行计算等方面的学者和工程技术人员。数据挖掘作为一种技术，它的生命周期正 处于沟坎阶段，需要时间和精力去研究、开发和逐步成熟，并最终被人们所接受。 【1 2 1 2 1 1 数据挖掘的定义 数据挖掘( ( d a t am i n i n g ) 指的是从大量的、不完全的、有噪声的、模糊的、随 机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和 知识的过程。在较浅的层次上，它利用现有数据库管理的查询、检索及报表功能， 与多维分析、统计分析方法相结合，进行联机分析处理( o l a p ) ，从而得出可供 决策参考的统计分析数据；在深层次上，则从数据库中发现前所未有的、隐含的 知识。o l a p 的出现早于数据挖掘，它们都是从数据库中提取有用信息的方法， 就决策支持的需要而言是相辅相成的。o l a p 可以看作一种广义的数据挖掘方 法，它旨在简化和支持联机分析，而数据挖掘的目的是使这一过程尽可能自动化。 数据库中的知识发现( k d d ) 是识别出存在于数据库中有效的、新颖的、具有 潜在价值的乃至最终可理解的模式的非儿过程。一般的看法是d m 只是k d d 的 一个步骤。但是由于d m 这个词的广泛使用，因此可把他们看成同义词。综合来 说，数据挖掘是由数据或数据库及相关技术构成主体，从大量的、不完全的、分 析过程有噪声的、模糊的、随机的数据中挖掘有效的未知新模式为目标的探索、 分析过程。k d d 的核心过程如图2 1 所示。 旁r 幽2 1k d d 数据挖抛呐核心过程 f i g u r e2 1 c o r ep r o c e d u r e so f k d d d a t a m i n i n g 2 12 数据挖掘的分类 数扼挖掘涉及的学科领域和力法搬多，柏多种分类 法。根捌挖掘任务。可 分为分类或t m 测模型发现、数捌总结、聚类、关联规则发现、序列模式发现、依 赖关系或依赖模型发现、片常和趋贽发现等。根州挖删对象分，有关系数槲库、 面向对象数据斤、空m 数据库、时态数据库、文术数据库、多媒体数据库、片构 数据库、遗产数据库以及w e b 。根抓挖扪方沾，呵分为机器学习方法、统汁方 法、神经网络方法和数据库方法二 数据挖掘常川的算法有决策树、遗传算法、儿叶斯川络、籼糙集、神经刚络 和统计分析等，每种算法都有白身的功能tj 优势。决策树的最人优点就足呵理解 性，很直观，主要用十分i 炎和归纳挖掘，f h 在数据量较大和数据复杂的情况下， 该算法则显得力不从心；遗f 算法擅k 于数据策类，拍组合优化问题上也有独特 的优势；肌叫斯嗍络县宵分黄、聚炎、预测和凼果必系分析等功能，易丁理解， 预测效果较好；料糙集在数据挖捌中其有重要的作_ l | j ，常h j 。处理禽枷性和不确 定眭的问题，也可以用j 特征p 约和相关分析，神经网络在商、i k 界得到广泛的应 用，在泌别信贷客户、股票预测和u e 券h 场分析等方血具有良好的效果。数据挖 掘的每种技术都有各自的特点，往征足将几种技术方法结合使_ l j ，形成优势互补。 2 13 数据挖掘的任务 数据挖捌的仟务 要有七项：天联分析、序列模式发现、聚类、分类、预测 偏差检测、描述与可视化。 1 卅 第2 章数据挖掘相关技术 ( 1 ) 关联分析 关联分析的主要目标是发现数据库中数据项之问是否存在某种关联关系。若 两个或多个数据项的取值之间重复出现且概率很高时，它就存在某种关联，可以 建立起这些数据项的关联规则。 在大型数据库中，关联规则的数最很多。通常，我们需要使用“支持度”和 “信任度”两个阈值来筛选其中的强规则。 ( 2 ) 序列模式发现 序列模式发现是通过时问序列搜索出重复发生概率较高的模式。 在时序模式中，需要找出在某个最小时间内出现比率一直高于某一最小百分 l l ( 闽值) 的规则。这些规则会随着形式的变化做适当的调整。 ( 3 ) 聚类 聚类就是将数据库中的数据进行分组，使得每一组内的数据尽可能相似，而 不同组间的数据尽可能不同。聚类技术在统计数据分析、模式识别、图象处理等 领域都有广泛的应用。 聚类不依赖于预先定义好的类，不需要训练集，属于无监督的学习。 在统计分析方法中，聚类分析是基于距离的聚类，如欧氏距离、海明距离等。 这种聚类分析方法是一种基于全局比较的聚类，它需要考察所有的个体才能决定 类的划分。 在神经网络中，用于聚类的是自组织神经网络方法，如a r t 模型、k o h o n e n 模型等。 ( 4 ) 分类 分类即区分数据类别，是数据挖掘中应用最多的任务。首先从数据中选出已 经分好类的训练集，在此训练集上运用分类技术，建立用规则或决策树表示的分 类模型，即找出一个类别的概念描述。然后，根据分类模型对于没有分类的数据 进行分类。 建立分类决策树的方法，典型的有m 3 ，c 4 5 ，i b l e 等方法。建立分类规则的 方法，典型的有a q 方法、粗集方法、遗传分类器等。 ( 5 ) 预测 预测是利用历史数据找出变化规律，建立模型，并用此模型来预测未来数据 的种类、特征等。预测与分类类似，不同之处在于，分类描述的是离散型变量的 输出，而预测处理连续值的输出，同时分类的类别是确定数目的，预测的量是不 确定的。 典型的预测方法是网归分析，即利用大量的历史数据，以时间为变量建立线 性或非线性回归方程。预测时，只要输入任意的时间值，通过凹归方程就可求出 该时问的状态。 北京川p 人学l ：。硕卜学何论文 ( 6 ) 偏差检测 偏差检测是通过数据分析，发现数据库中存在的数据异常情况的技术。 偏差检测的基本方法是寻找观察结果与参照之| 、日j 的差别。观察常常是某一个 域的值或多个域值的汇总。参照是给定模型的预测、外界提供的标准或另一个观 察。 ( 7 ) 描述和可视化 数据挖掘结果的表示方式，即对数据进行约简、概化或图形描述等。 2 1 4 数据挖掘的主要技术方法 数据挖掘的主要技术方法有：统计分析方法、粗集方法、决策树方法、神经 网络方法、模糊逻辑、规则归纳、最近邻技术等。【1 4 】【1 2 】【1 】 ( 1 ) 统计分析方法 统计分析方法是利用统计学、概率论的原理对各属性进行统计分析，从而找 出它们之间的关系和规律。统计分析方法是最基本的数据挖掘技术方法之一。 在数据挖掘领域，统计分析方法可用于分类和聚类。 ( 2 ) 粗集方法 粗集理论是波兰z p a w l a k 教授在1 9 8 2 年提出的。在数据挖掘领域，料集方 法被广泛应用于不精确、不确定、不完全的信息的分类和知识获取。 ( 3 ) 决策树方法 决策树方法就是利用训练集生成一个测试函数，根据不同取值建立树的分支： 在每个分支子集中重复建立下层结点和分支，这样便生成一棵决策树。然后对决 策树进行修剪处理，最后把决策树转化为规则，利用这些规则可以对新事例进行 分类。 这种方法实际上是根据信息论原理对数据库中存在的大量数据进行信息量 分析，在计算数据特征的互信息的基础上提取出反映类别的重要特征。 典型的决策树方法有分类回归树( ( c a r t ) ，i d 3 ，c 4 5 等。决策树方法主要用 于分类。 ( 4 ) 神经网络方法 神经网络方法的原理是模拟人脑的神经元结构，以m p 模型和h e b b 学习规 则建立起前馈式网络、反馈式网络和自组织网络3 大类多种神经网络模型。基于 神经网络的数据挖掘工具对于非线性数据具有快速建模能力，其挖掘的基本过程 是先将数据聚类，然后分类计算权值，神经网络的知识体现在网络连接的权值上。 神经网络方法用于非线性数据和含噪声的数据时具有更大的优越性，比较适 合于市场数据库的分析和建模。目前，在数据挖掘中，最常用的神经网络是b p 第2 章数据挖掘相关技术 和r b f 网络。但是，人工神经网络还是一门新兴科学，有一些理论尚未彻底解 决，比如收敛性、稳定性、局部最小值以及参数调整问题等等。 神经网络具有对非线性数据快速拟合的能力，可用于分类、聚类、特征挖掘 等多种数据挖掘任务，在事务数据库的分析建模方面有广泛的应用。 ( 5 ) 模糊逻辑 模糊数学是继经典数学、统计数学之后，数学史上的又一新发展。针对一个 问题，复杂性越高，有意义的精确化能力就越低。模糊性是客观存在的，当数据 量越大而且复杂性越大时，对它进行精确描述的能力越低，就是说模糊性越强。 在数据挖掘领域，模糊逻辑可以进行模糊综合判别、模糊聚类分析等。 ( 6 ) 规则归纳 规则归纳包括关联规则和i f t h e n 规则。 ( 7 ) 聚类分析和模式识别 聚类分析主要是根据事物的特征对其进行聚类或分类，以期从中发现规律和 典型模式。这类技术是数据挖掘的最重要技术之一。 ( 8 ) 最近邻技术 最近邻技术是通过k 个与之最相近的历史汜录的组合来辨别新记录。这种技 术可用作聚类、偏差分析等挖掘任务。 ( 9 ) 可视化技术 这是一类辅助方法，它采用比较直观的图形图表方式将挖掘出来的模式表现 出来，从而增强数据的表达和理解力。这在数据挖掘中非常重要，数据可视化正 受到同益广泛的重视。 2 1 5 数据挖掘的发展趋势 美国已经丌始研发一套名为“信息全面感知”( t o t a li n f o r m a t i o na w a r e n e s s ，t i a ) 的反恐怖主义信息监控系统，主要运用数据挖掘技术，搜集全球各地计算机使用 者传递的信息，综合情报单位搜集能力，筛检可疑的线索与实证，及时发出预警 信息，t 认系统将能提供诸如特定地区的旅行记录、可疑电子邮件来往、不寻常 的资金转移、罕见的医疗行为( 如炭疽热治疗) 等信息。专家指出，这套系统极为 庞大复杂，完成后将是人类有史以来最大规模的信息监控系统。 w w w 为数据挖掘提供了丰富的数据资源，同时也是一个艰巨的挑战。w e b m i n i n g 是一项复杂的技术，由于w e b 数据挖掘比单个数据仓库的挖掘要复杂 得多，因而面向w e b 的数据挖掘成了一个难以解决的问题而x m l ( e x t e n s i b l e m a r k u pl a n g u a g e ) 的出现为解决w e b 数据挖掘的难题带来了机会。由于x m l 能够使不同来源的结构化的数据很容易地结合在一起，因而使搜索多样的不兼容 北京k 人i ：硕十何沦文 的数据库成为可能。另外还有空间数据挖掘，多媒体数据挖掘( m u l t i m e d i a d m ) ( 包括t e x td m ，v i d e od m 和a u d i od m ) ，d n a 数据挖掘和生物信息学 ( d n ad m a n db i o i n f o r m a t i c s ) 等。【1 5 】【1 6 】 数据挖掘的理论基础和挖掘算法还有很大的空间有待发展和完善。 数据挖掘的个人稳私和信息安全问题也是急需关注和解决的。 2 2 聚类分析方法介绍 2 2 1 聚类方法的定义 聚类是将物理或抽象对象进行分组并将相似对象归为一类的过程。与分类不 同，聚类的目标是在没有任何先验知识的前提下，根据数据的相似性将数据聚合 成不同的簇( 或类) ，使得相同簇中的元素尽可能相似，不同簇中的元素差别尽 可能大，因此又被称为非监督分类。 聚类分析作为数据挖掘系统中的一个模块，既可以作为一个单独的工具以发 现数据库中数据分布的深层信息，也可以作为其他数据挖掘分析算法的一个预处 理步骤。与其他领域的研究相比，数据挖掘中的聚类分析博采众家之长，在引入 其他领域的成熟聚类算法的基础上，加入了针对计算机行业特点的内容，比如考 虑与大数据库德结合、算法性能的优化、标准的接口等问题。 聚类【l7 】就是将数据对象分组成为多个簇，使得同一个簇中的对象之间具有较 高的相似性，而不同簇中的对象具有较大的相异性，一个好的聚类方法应产生具 有如下特性的聚类结果：簇内的对象高度相似，而簇间的对象很少相似。 2 2 2 聚类方法基本概念 以下对聚类分析方法的一些基本概念进行介绍：【2 5 】 定义l ：假定一个数据对象由d 个属性( 也称为度量或变量) 描述，则若干个 具有d 个属性的数据对象就构成了d 维数据空间。在d 维空间中，数据对象 被称作d 维数据点，则d 维数据点x 可表示为x = ( x 1 ，x d ) ，其中x i 表示第i 个属性值，d 表示空间的维数。 定义2 ：由n 个d 维数据点组成的集合( 又称为d 维数据集) s 可表示为 s = ( s l ，s n ) ，其中s i = ( s i l ，s i d ) ，且s “表示第i 个数据点的第j 个属性值。 定义3 ：根据数据点之间的相似性，将d 维数据集v 划分成 c l ，c 2 ，c k 的过程称为聚类分析，其中k n ，c i 中， c i 至v ( i = l ，2 ，k ) ，并且 第2 章数据挖掘十订笑技术 i jc ，：v 。这罩，c i 一般被称做类或簇，下文将统一称之为“簇”。 f = i 聚类分析以相似性( 或相异性) 为基础来划分簇，但是数据对象之间的相似性 ( 或相异性) 没有唯一的定义。评价相似性的角度有三种，分别是基于距离的、基 于密度的和基于连接的。前两类通常适用于欧几早得空间，第三类则适用于任意 度量空间。 定义4 ：根据数据点之间的距离评价相似性：距离越短，相似性越大；反 之，距离越长，相似性越小。 理想情况下，数据点v i 和v j 的距离d i i 必须满足以下条件： 1 d i i o ( 非负性) 2 d i ；= 0i f f v i - - v j 3 d i = d j ( 对称性) 4 d i k di j + d j k ，其中v i v j v k ( 三角不等性) 满足上述条件的d i i 的取值在o 一，d i i 越小，v i 和v j 的相似性越大，反之， d i i 越大，v i 和v j 的相似性越小。 关于在聚类中用到的距离测量( d i i 的测量) 将会在4 2 章节中具体讨论。 聚类方法具有广泛的应用，典型的如文档的聚类，以及一些特定领域的成功 应用、子空间聚类、可视空间聚类问题也得到了研究。本文将讨沦聚类分析在自 考考生流失多重因素分析中的应用。 2 2 3 聚类方法的分类 聚类的方法大体可以划分为以下几类【1 8 】：划分方法、层次方法、基于密度的 方法、基于网格的方法和基于模型的方法。下面简单介绍一下其中的划分方法、 层次方法和基于密度的方法。 ( 1 ) 划分方法 给定一个包含n 个数据对象或元组的数据库，一个划分方法构建数据的c 个 划分，每个划分表示一个簇，且c n 。通常会采用一个划分准则( 经常称为相 似度函数) ，例如距离，以便在同一个簇中的对象是“相似的”，在不同簇中的对 象是“相异的”。这些聚类方法对在中小规模的数据库中发现球状簇很适用。 ( 2 ) 层次方法 层次方法对给定数据对象集合进行层次的分解。根据层次分解是自底向上还 是自顶向下形成，层次聚类的方法可以进一步分为凝聚的和分裂的。层次聚类方 法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被撤消，因此而不 能更证