（计算机应用技术专业论文）北京市高中会考数据挖掘研究.pdf

摘要 摘要 北京市普通高中毕业会考作为以测量和评价高中学生学业水平、学校教学质 量为主要目的大规模考试，属于标准参照性考试，它是衡量普通高中学生是否达 到毕业标准的依据。随着数据库系统在会考管理中的广泛应用，北京教育考试院 积累了大量与会考相关的数据。由于缺乏有效的处理手段，这些数据在业务活动 结束后成了难得再访问的数据档案。将数据挖掘技术引入高中会考数据分析中，对 沉积的数据进行分析，找出背后隐藏的知识，发现数据中潜在的规律，从而为科 学评价高中会考在高中教育教学中的作用，为教育行政部门制定相关政策提供数 据支持。 数据挖掘成功的关键是确定合适的挖掘目标，挖掘目标的确立既要考虑业务 管理的需要，还要考虑已有数据的特性，保证目标在现有数据的基础上是可以实 现的。主要目标是通过分析不同考试时间( 正常考试、非正常考试) 、不同类别 考生( 普高、私立) 、不同考试形式( 统一考试、自行组考) 的考试分数特性， 对现有的政策的修改和完善提供数据支持，从而使北京市高中会考能够真正发挥 对教育教学质量的监控和评价作用。 首先，收集整理相关数据，数据主要由会考业务系统产生，为满足挖掘主题 的需求可能还需要从其他业务系统获得数据。现有的业务系统主要采用关系数据 模型，为挖掘的需要可能需要进行模型转换。其次，需要对原始数据进行清理， 去掉异常数据，如空值、不合理的值；还需要对原始数据进行简化，删除与挖掘 主题无关的数据。 确定了挖掘目标和对数据进行预处理之后，下面接着是选择合适的满足挖掘 需要的挖掘算法，本课题在研究几个重要的挖掘算法的特性、算法的应用方式、 算法的实现等方面的基础上，主要研究两类算法：关联分析和分类分析。如何有 效利用挖掘算法解决实际问题是研究的重点。 最后，对挖掘得到的结果进行分析，确定其代表的含义，判定是否具有实际 意义。 关键词会考系统；数据挖掘；关联规则；决策树 a b s t r a c t a b s t r a c t b e i ji n gc o m m o nh i g hs c h o o lu n i f o r me x a m i n a t i o n , b e i n gac r i t e d o n r e f e r e n c e d l a r g es c a l et e s t , a i m st om e a s u r ea n dv a l u es c h o o lw o r ko fh i 曲s c h o o ls t u d e n t sa n d q u a l i t yo fs c h o o lt e a c h i n g ，a n di ti st h eb a s i su s e dt ow e i g hw h e t h e rs t u d e n t sr e a c hh i 曲 s c h o o lg r a d u a t i o ns t a n d a r d s w i t ht h ee x t e n s i v ea p p l i c a t i o no fd a t a b a s es y s t e mi nt h e u n i t e de x a m i n a t i o nm a n a g e m e n t ，b e i j i n ge d u c a t i o ne x a m i n ec e n t e ra c c u m u l a t el a r g e n u m b e ro fr e l e v a n td a t aa b o u tt h eu n i t e de x a m i n a t i o n b e c a u s el a c ko fe f f e c t i v e p r o c e s s i n gm e a n s ，t h e s ed a t ab e c o m er a r er e v i s i t e dd a t af i l e sa f t e r t h ee n do ft h e b u s i n e s sa c t i v i t i e s d a t am i n i n gt e c h n o l o g yi n t r o d u c e di nd a t aa n a l y s i so ft h eu n i t e d e x a m i n a t i o n ，a n a l y s i so fs e d i m e n t a r yd a t a , f i n do u th i d d e nk n o w l e d g ea n dp o t e n t i a l r u l e sa b o u td a t a ，p r o v i d e sd a t as u p p o r tf o rs c i e n t i f i ce v a l u a t i o no ft h er o l eo ft h eu n i t e d e x a m i n a t i o ni ns e n i o r h i 曲s c h o o lt e a c h i n g a n df o re d u c a t i o na d m i n i s t r a t i o n d e p a r t m e n t sm a k i n gr e l a t i v ep o l i c y t h ek e yo fd a t am i n i n gi st oi d e n t i f yas u i t a b l eg o a lo fm i n i n g i no r d e rt o i d e n t i f yt h eg o a lo fm i n i n gi ti sn o to n l yt oc o n s i d e rb u s i n e s sm a n a g e m e n tn e e d s ，b u t a l s ot oc o n s i d e rt h ec h a r a c t e r i s t i c so fd a t at oe n s u r et h a tt h eo b j e c t i v e sd a t ac a nb e a c h i e v e do nt h eb a s i so fa v a i l a b l e t h em a i no b j e c t i v ei st ot h r o u g ha n a l y s i so fd i f f e r e n t e x a m i n a t i o nt i m e ( n o r m a le x a m i n a t i o n ，n o n - n o r m a le x a m i n a t i o n ) ，d i f f e r e n tt y p e so f c a n d i d a t e s ( n o r m a l ，p r i v a t e ) ，d i f f e r e n tf o r m so fe x a m i n a t i o n ( e x a m i n a t i o n ，t h eg r o u p s e l f - e x a m i n a t i o n ) o ft h et e s ts c o r e s ，t os u p p o r tt h ee x i s t i n gp o l i c yc h a n g e sa n dt o i m p r o v et h ep r o v i s i o n o fd a t a , s ot h a t h i g hs c h o o l c e r t i f i c a t eo fe d u c a t i o n e x a m i n a t i o no fb e i ji n gc a nr e a l l yp l a yh i 曲s c h o o le x a m i n a t i o no fe d u c a t i o nq u a l i t y m o n i t o r i n ga n de v a l u a t i o nr o l e f i r s to fa l l ，c o l l e c tr e l e v a n td a t a , w h i c hf r o mt h em a i nb u s i n e s ss y s t e mo f e d u c a t i o ne x a m i n a t i o n ，i no r d e rt om e e tt h en e e d so fm i n i n gt h e m em a yb er e q u i r e d f r o mo t h e rb u s i n e s ss y s t e m sa c c e s st od a t a t h ee x i s t i n gb u s i n e s ss y s t e mi sm a i n l yu s e d r e l a t i o n a ld a t am o d e l ，t h en e e df o re x c a v a t i o nm a yb en e e d e dm o d e lc o n v e r s i o n s e c o n d l y ，t h en e e dt oc l e a nu pt h eo r i g i n a ld a t a ，r e m o v et h ea b n o r m a ld a t a ，s u c ha sn u l l a n du n r e a s o n a b l ev a l u e ；n e e df o rs i m p l i f i c a t i o no ft h eo r i g i n a ld a t a , d e l e t ea n dn o t r e l e v a n tt ot h es u b j e c to fd a t am i n i n g i i i 北京工业大学工学硕士学位论文 i d e n t i f i c a t i o no ft h et a r g e ta n dp r e t r e a t m e n to ft h ed a t am i n i n g ，t h e nb e l o wi sa s u i t a b l ec h o i c et om e e tt h en e e d so fm i n i n ga l g o r i t h m ，o nt h eb a s eo fr e s e a r c h i n g s e v e r a li m p o r t a n tc h a r a c t e r i s t i c so ft h em i i l i i 培a l g o r i t h m s ，t h ea p p l i c a t i o no fa l g o r i t h m s ， t h ea l g o r i t h mt oa c h i e v e ，a n ds oo n t w om a j o rm e t h o d s ：c o r r e l a t i o na n a l y s i sa n d c l a s s i f ya n a l y s i sa l es t u d i e d h o we f f e c t i v eu s eo fm i n i n ga l g o r i t h m st os o l v ep r a c t i c a l p r o b l e m si st h ef o c u so f t h es t u d y f i n a l l y ，t h e r e s u l t so fm i n i n gi sa n a l y z e dt od e t e r m i n et h em e a n i n go ft h e i r r e p r e s e n t a t i v e sa n dd e t e r m i n ew h e t h e r i th a sap r a c t i c a ls i g n i f i c a n c e k e y w o r d su n i f o r me x a m i n a t i o ns y s t e m ；d a t am i n i n g ；a s s o c i a t i o nr u l e ；d e c i s i o nt r e e i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：梨颦冬缝 日期：z 么2 15 2 22 q 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学问论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：考苌錾照导师签名：摊日期：她 第1 章绪论 第1 章绪论 1 1 数据挖掘出现的背景 随着数据库技术的成熟应用和获取数据技术的飞速发展，人类积累的数据 正以指数速度增长。全世界每天新存入数据库的数据量超过万兆字节。数据如 洪水正向人们滚滚而来。大量的数据背后隐藏着许多重要的信息，人们希望能 够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统虽 然可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的 关系和规则，无法根据现有的数据预测未来的发展趋势。因此，面对“人们被 数据淹没，却饥饿于知识 的挑战，数据挖掘技术应运而生。 数据挖掘技术的应用领域十分广阔，它可以从关系数据库、数据仓库、文 本和多媒体数据库、事务数据库和互联网等各种数据源上设法获取诸如分类模 型、聚类模型、回归模型、关联模型和时间序列模型等多种知识模型。可以说， 有数据积累的地方，就有数据挖掘技术的用武之地。目前，数据挖掘技术在货 篮数据( b a s k e td a t a ) 分析、金融风险预测、产品质量分析、分子生物学、基因 工程研究、i n t e r n e t 站点访问模式发现以及信息搜索等领域得到了广泛的应用。 数据挖掘技术被认为是数据库和人工智能领域中研究、开发和应用最活跃的分 支之一，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理 统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘 这一新兴的研究领域，形成了新的技术热点。 1 2 目前研究现状 1 2 1 国外研究及应用现状 国际上对数据利用的研究在理论、技术和应用三个方面展开。理论方面的 研究包括：数据和知识的表示；结构化、文本和多媒体数据的模型构造；不确定 性管理；知识的实用性评测；数据挖掘的算法复杂性和效率分析；海量数据集 的统计学等。技术方面的研究主要包括数据挖掘方法、数据挖掘算法和知识发 北京工业大学工学硕士学位论文 现过程。应用研究包括开发各种数据挖掘系统和工具及其在各个行业中的应用， 例如在市场分析、金融投资、欺诈甄别、医疗卫生、环境保护、产品制造和科 学研究、电子商务和有关数据保密的问题等众多领域获得了不少成功的应用， 取得了十分可观的社会效益和经济效益。当前，世界上很多大公司开发了数据 挖掘工具及相关软件，世界上比较有影响的典型数据挖掘系统有：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 l 公司的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 o i r a 等。 通用数据挖掘工具对于使用者的要求比较高，需要多种人才的配合，才能 达到使用目的。为解决这一问题，一些专用数据挖掘系统应运而生，如：加州 理工学院喷气推进实验室与天文科学家合作开发的s k i c a t 系统，帮助天文学家 发现遥远的类星体；芬兰赫尔辛基大学计算机科学系开发的t a s a 系统，帮助预 测网络通信中的警报；i b m 公司的a d v a n c e d s c o u t 系统针对n b a 的数据，帮助 教练优化战术组合，一度在数据库界被传为佳话。最近，还有不少数据挖掘产品 用来筛选i n t e r n e t 上的新闻，保护用户不受无聊电子邮件的干扰和商业推销， 受到极大的欢迎。 1 2 2 国内研究及应用现状 与国外相比，国内对数据挖掘的研究较晚，仅仅停留在学术研究阶段。目 前，国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应用研 究，这些单位包括清华大学、中科院计算技术研究所、空军第三研究所、海军 装备论证中心等。其中，北京系统工程研究所对模糊方法在知识发现中的应用 进行了较深入的研究，北京大学也在开展对数据立方体代数的研究，华中理工 大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等 单位开展了对关联规则开采算法的优化和改造，南京大学、四川联合大学和上 海交通大学等单位探讨、研究了非结构化数据的知识发现以及数据挖掘，总之， 经过十几年的发展，对数据挖掘的研究已经从最初表面的、孤立的问题向系统 的、全面的方向发展。大体来说，对数据挖掘的研究目前主要集中在数据挖掘 技术和算法的研究、数据挖掘的理论研究以及数据挖掘的应用研究三个方面。 目前，我国出版有关数据挖掘具有代表性的著作有：h a nj k a m b e ri 数 据挖掘：概念与技术，2 0 0 1 年，机械工业出版社出版，北京：张尧庭，谢邦昌， 朱世武数据挖掘入门及应用从统计技术看数据挖掘( 电子版) 。具有 代表性的论文主要有：朱世武等数据挖掘与其他技术比较，统计研究2 0 0 3 年第7 期：赵黎明等基于数据挖掘的专利引文研究与知识发现，预测 2 第1 苹绪论 2 0 0 2 年第6 期：统计与信息论坛2 0 0 2 年刊登了中国人民大学统计学系数据 挖掘中心关于数据挖掘理论和应用研究的系列论文6 篇，这些著作和论文可供从 事数据挖掘研究和应用者参考。 国内企业运用数据挖掘技术来协助业务活动的应用还处于起步阶段。成功 应用的案例还比较少，把数据挖掘应用于考试系统，服务于教育的更是少之又 少，对数据挖掘技术和工具的研究人员以及开发商来说，我国是一个有巨大潜 力的市场。 1 3 课题来源与主要研究内容 北京教育考试院成立于1 9 9 6 年2 月，隶属于北京市教育委员会。主要负 责北京地区的中考、高中会考、普通高考、成人高考、高教自考、研究生招生 考试及面向社会的非学历等级证书考试的管理和研究工作，并负责管理和承办 北京地区中外合作教育考试。 北京教育考试院是首都教育系统的重要组成部分，建设和提高考试院信息 化管理，是教育改革的方向，也是适应未来发展的需要。自2 0 0 0 年1 1 月起， 北京工业大学与北京教育考试院进行合作，开始进行北京市教育考试院信息管 理系统项目的研究，陆续开发了北京教育考试院网络信息系统平台、北京市高 中会考、成人高考、高教自考等信息管理系统，进一步提高了各级各类考试的 科学化、规范化管理水平，引导北京市教育考试系统走持续发展的道路。 北京市普通高中毕业会考是北京教育考试院组织的一项重要考试，涉及北 京市全部的普通高中学生以及部分职技类学校学生，每年进行两次，参加考试 人数达3 0 多万，报考科次近1 0 0 万。高中毕业会考本质上是一种标准参照的水 平性考试，它既是高中学生毕业的依据，也是衡量高中学生学业水平的依据。 北京市从1 9 9 0 年开始全面实施高中毕业会考，许多教育测评专业人员对高中会 考在高中教学方面的作用以及会考命题对教学目标的体现等方面进行了研究， 但是，由于种种原因，研究结果更多地停留在定性层面，没有上升到定量的水 平。随着数据库系统在会考管理中的广泛应用，考试院积累了大量与会考相关 的数据。由于缺乏有效的处理手段，这些数据在业务活动结束后成了难得再访 问的数据档案。迫切需要利用强有力的工具来对沉积的数据进行分析，找出背 后隐藏的知识。 因此，为了能够更加科学评价高中会考的作用，发挥高中会考对高中教育 教学的监控和评价功能，为教育行政部门制定并完善相关政策提供数据支持， 开展本课题的研究。 3 北京工业大学工学硕士学位论文 1 4 论文结构安排 本文通过对数据挖掘技术的研究，着重在数据挖掘技术的应用上。在后续 章节中将结合北京市高中会考现状，对数据挖掘技术在高中会考信息处理中的 应用进行深入研究，通过分析不同的会考分数特性，从而，可以有针对性地修 改现有的会考政策，保证会考的信度和效度，使会考成绩能够真实地反映实际 的教学水平和学习水平。 第一章：绪论。主要介绍数据挖掘的历史、发展及国内外研究现状，并介 绍了问题提出的背景和意义，主要内容以及结构组织。 第二章：数据挖掘技术。主要介绍数据挖掘的基本知识，包括数据挖掘的 概念、过程、任务、分类、对象、常用技术和方法知识表示以及应用领域。 第三章：关联规则数据挖掘算法研究。主要介绍数据挖掘关联规则算法 a p r i o r i 。 第四章：决策树分类算法研究。主要介绍经典决策树算法c 4 5 。 第五章：会考数据挖掘系统的设计与实现。介绍会考系统的数据挖掘过程， 重点介绍了a p r i o r i 算法和c 4 5 算法在会考系统中实施的全过程。 4 第2 章数据挖掘技术 第2 章数据挖掘技术 2 1 数据挖掘的定义 数据挖掘从产生至今已有多种定义 1 ，其中得到公认的是：数据挖掘是从 大量数据中揭示出有效的、新颖的、潜在有用的，以及最终可理解的知识和模 式的过程。是数据库中的知识发现( 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 ，简称 k d d ) 的核心。 下面对一些概念作详细的解释：数据：数据是一组事实f 的集合( 如关系 数据库中的记录) ，它是描述事物有关方面的信息，一般来说这些数据都是准确 无误的。模式：语言l 表示的表达式e ，它可以用来描述数据集f 的某个子 集f e ，它比枚举所有f e 中元素更简单，我们称e 为模式；有效、新颖、潜 在有用、可被人理解：表示发现的模式有一定的可信度，应该是新的、将来有 实用价值的、能被用户所理解的知识晗1 。 知识发现( k d d ) 被认为是从数据中发现有用知识的整个过程。数据挖掘只是 数据库中知识发现的一个步骤，但又是最重要的一步，它用专门算法从数据中 抽取模式。人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。 原始数据可以是结构化的，如关系型数据库中的数据，也可以是半结构化 的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知识 的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳的。 发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可 以用于数据自身的维护。因此，数据挖掘是一门广义的交叉科学，它汇聚了不 同领域的研究者，尤其是数据库、人工智能、数理统计、可视化、并行计算等 方面的学者和工程技术人员。 2 2 数据挖掘技术的起源 数据挖掘是应用需求推动下多种学科融合的结果凹1 。 首先是数据库技术。随着数据库技术的不断发展及数据库系统的广泛应用， 人类积累的数据量正以指数速度增长。例如：w a lm a r t 公司每天要处理二千万 个事务；美国航天局1 9 9 9 年发射的地球观测系统每小时要产生5 0 g b 的图像数据。 5 北京工业大学工学硕士学位论文 毫无疑问，这些庞大的数据库及其中的海量数据中蕴藏着丰富的信息。但是仅 仅依靠传统的数据检索机制和统计分析方法还不能揭示出其中所蕴含的知识h 1 。 数据挖掘技术正是在这种强烈需求背景下，由数据库技术推动、演化而来的， 数据库技术的不断成熟和数据仓库的发展为数据挖掘提供了发挥作用的平台。 其次，在数据库技术飞速发展的同时，人工智能领域的一个分支机器 学习的研究也取得很大进展。自5 0 年代开始机器学习的研究以来，先后经历了 神经模型和决策理论、概念符号获取及知识加强、领域专用学习三个阶段，根 据人类学习的不同模式人们提出了很多机器学习方法，如：实例学习、观察和 发现学习、神经网络和遗传算法等等。其中某些常用且较成熟的算法已被人们 运用于实际的应用系统及智能计算机的设计和实现中。数据挖掘中的许多方法 就来源于机器学习。 最后，使数据挖掘能够得到广泛应用的关键一点是计算机性能的迅速发展。 计算机存储设备性价比的迅速提高，使许多企业有能力收集和存储海量数据， 而计算机计算能力性价比的提高，则为数据挖掘的实施扫清了障碍。随着计算 机硬件性能的不断提高、数据挖掘技术的不断改进，数据挖掘应用将会越来越 普及。 2 3 数据挖掘项目考虑的问题 谈到数据挖掘应从以下三方面加以考虑，一是采用数据挖掘算法要解决的 问题，二是为数据挖掘所做的数据准备，三是数据挖掘的各种分析算法。 数据挖掘的分析算法主要来自于以下两个方面：统计分析和人工智能( 机 器学习、模式识别等) 。数据挖掘研究人员和数据挖掘软件供应商，在这一方 面所做的主要工作是优化现有的一些算法，以适应大数据量。另外需要强调的 是，任何一种数据挖掘的算法，不管是统计分析方法、神经元网络、各种树分 析方法，还是遗传算法，没有一种算法是万能的。不同的问题，需要用不同的 方法去解决。即使对于同一个问题，可能有多种算法，这个时候，也需要评估 对于这一特定问题和特定数据哪一种算法表现好。 做数据挖掘研究的人，往往把主要的精力用于改进现有算法和研究新算法 上。人们都知道数据准备是必不可少的一步，但很少有人真正花时间和精力去 研究。其实数据挖掘最后成功与失败，是否有经济效益，数据准备起到了至关 重要的作用。数据准备包含很多方面： 一是从多种数据源去综合数据挖掘所需要的数据，保证数据的综合性、易 用性、数据的质量和数据的时效性，这有可能要用到数据仓库的思想和技术； 另一方面就是如何从现有数据中衍生出所需要的指标，这主要取决于数据挖掘 6 第2 章数据挖掘技术 者的分析经验和工具的方便性。 实施数据挖掘项目考虑的问题： 1 ) 超大规模数据库和高维数据问题 2 ) 数据丢失问题 3 ) 变化的数据和知识问题 4 ) 模式的易懂性问题 5 ) 非标准格式的数据、多媒体数据、面向对象数据处理问题 6 ) 与其他系统的集成问题 7 ) 网络与分布式环境下的k d d 问题 8 ) 个人隐私问题 2 4 数据挖掘的功能 数据挖掘系统的功能主要有以下几大类： 统计归纳：利用统计模型和数学模型来解释异常的数据模式。通常使用的 模型有线性分析和非线性分析、连续回归分析和逻辑回归分析、单变量和多变 量分析以及时间序列分析。统计分析工具能够提供可视化功能和分析功能来寻 找数据间关系，构造模型来解释数据，交互式过程和迭代过程用来求精模型， 最终开发出最具适应性的模型来将数据转化为信息。 关联分析：关联分析搜索数据库的条目，从中寻找重复出现概率高的模式。 它展示了数据间未知的关联关系。其典型的应用是购物篮分析，如购买商品a 和 b 的客户有8 5 同时也购买了商品c ，用规则表示为a ，b = c ( 8 5 ) 。本文第三 章将着重对关联技术进行讨论。 分类和预测：分类和预测用于提取描述重要数据类的模型或预测未来的数据 趋势。分类可预测类标号( 或离散值) ，预测可以预测连续值。例如，建立分 类模型对银行贷款的安全风险进行分类；建立预测模型对商品的销售量、股票 价格、产品合格率等进行预测。分类技术有判定树归纳、贝叶斯分类和贝叶斯 网络、神经网络、最近临、基于安全的推理、遗传算法、粗糙集和模糊逻辑等。 预测方法包括线性的、非线性的和广义线性回归模型。本文第四章将着重对分 类技术进行讨论。 聚类分析：聚类将数据对象分组成为多个类或簇，在同一个簇中的对象之 间具有较高的相似度，而不同簇中的对象差别较大。聚类与分类不同，它要划 分的类是未知的。相似度是根据描述对象的属性值来计算的。聚类分析广泛应 用于模式识别、数据分析、图像处理和市场研究。在商务上，聚类分析能帮助 市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同 7 北京工业大学工学硕士学位论文 的客户群的特征。聚类技术有划分方法、层次方法、基于密度的方法、基于网 格的方法和基于模型的方法。 2 5 数据挖掘过程 在实施数据挖掘之前，先制订计划，确定要采取什么样的步骤，每一步要 做什么，要达到什么样的目标。有了好的计划才能保证数据挖掘有条不紊的实 施并取得成功。数据挖掘一般包括四个步骤：确定挖掘目标、数据准备、挖掘 操作、结果表达和解释3 。虽然我们把各个步骤按顺序排列，但数据挖掘过程并 不是线性的，要取得好的结果就要不断反复和重复这些步骤。 2 5 1 确定挖掘目标 清晰地定义出挖掘目标，认清数据挖掘的目的是数据挖掘的重要一步，挖掘 的最后结果是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数 据挖掘则带有盲目性，是不会成功的。因此，在挖掘之前要明确目的和需求。 2 5 2 数据准备 这个阶段又可进一步分成3 个子步骤：数据集成、数据选择、数据变换。 数据集成数据挖掘可能涉及到内部多个数据源，还可能需要一些外部 的数据( 如人口统计、天气数据或信用卡使用数据等) ，这就需要将多个数据源 中的数据结合起来存放在一个一致的数据存储( 如数据仓库) 中，以便于数据 挖掘操作。 数据选择这个阶段需要选择用于数据挖掘的数据( 即源数据的子集) 。 这与对数据进行采样和选择预测变量是不同的，这里只是粗略的把一些冗余或 无关的数据除去。有时，由于资源的限制、费用的限制、数据使用的限制和数 据质量等原因也必须对数据进行选择。 数据变换将数据转换成适合于挖掘的形式乜3 。数据变换可能涉及如下内 容： 平滑：由于数据库中可能存在各种错误数值( 如身份证号码可能被粗心的 数据录入人员录入了年龄) ，还可能存在空缺值。这些都会最终影响模型的质量。 因此必须采取分箱、聚类和回归等技术来修正错误数值、填充空缺的数值。 聚集：有时需要对数据进行汇总和聚集。例如，可以根据学校所属区域， 考试年月等将数据分为若干类。 8 第2 章数据挖掘技术 规范化：有些算法和工具对数据范围有要求，如神经网络要求所有的变量 都在0 - 1 之间，这就需要对原始数据按一定比例缩放，使之落入一个特定的区 间。 属性构造：很多情况下需要从原始数据中衍生一些新的属性以提高数据挖 掘的效率和可靠性。 2 5 3 挖掘操作 根据所要挖掘的模式类型选择适当的数据挖掘算法，选取合适的模型和参 数。当然，没有一种算法或工具适应所有的数据，通常也很难在开始时就能决 定哪种算法对你所面临的问题来说是最好的，因此很多情况下，需要建立不同 的模型( 参数或算法) ，从中选择最好的。 2 5 4 结果表达和解释 将挖掘出的结果以一种易于理解的形式表示出来，并进行解释和评价。具 体包括消除无关的、多余的模式，过滤出要呈现给用户的信息；利用可视化技 术将有意义的模式以图形或逻辑可视化的形式表示，转化为用户可以理解的语 言。一个成功的数据挖掘的应用应能将原始数据转换为更简洁、更易理解、可 明确定义关系的形式。此外还包括解决发现的结果与以前知识的潜在冲突，及 利用统计方法对模式进行评价，决定是否需要重复以前的操作，以得到最优、 最适合的模式。 2 6 数据挖掘研究中存在的问题 要理解数据挖掘，首先要弄明白数据挖掘需要解决哪些问题，目前还面临着 哪些难题。目前，数据挖掘中的许多问题都已获得解决，但数据挖掘技术的研 究还很不成熟，面临着许多问题有待解决。如数据的巨量性、动态性、噪声性、 缺值和稀疏性，发现模式的可理解性、兴趣或价值性，应用系统的集成，用户 的交互操作，知识的更新管理，复杂数据库的处理等等n 1 。下面对这些问题进行 较为详细地讨论。 2 6 1 有效处理巨量和高维的数据 包含上百万条记录和数千兆字节甚至几兆兆字节的数据库已经司空见惯， 9 北京工业大学工学硕士学位论文 数据库关系表所涉及的属性或变量数也大到成百上千的数量。这种数据的巨量 和高维性使得数据挖掘时模式的搜索空间异常巨大，同时还可能导致搜索出无 意义模式的机会增加。传统的技术已经难以适用，如常规的机器学习方法一般 只能处理不超过几千个记录或例子的数据集。为了解决这些问题，需要有高效 的，特别是线性计算复杂度的( 近似) 算法、抽样方法、大规模并行处理技术、 维数消减方法等技术。 2 6 2 数据噪声与缺值 在商业数据库中噪声和缺值是一种常见现象。如美国人口普查数据的错误 率就高达2 0 0 5 。错误或噪声可能来自于数据录入的误操作或现实中不可避免的因 素( 如民意调查的主观性) 。数据遗失有两类情况：一是某些字段上缺值，另 一种是数据库在设计阶段就可能没有考虑某些重要属性或字段( 数据库并不是 为数据挖掘而设计的，它的设计有自己的考虑) ，而这些属性对于数据挖掘进 行知识发现可能很重要。因此，需要研究出可行的方法来对这些噪声数据和缺 值进行有效处理。 2 6 3 交互性用户界面 数据挖掘过程中操作者的适当参与是必不可少的。一方面，数据挖掘系统 应该为用户提供表达其要求和挖掘策略的交互界面，深化数据挖掘过程，使得 用户能从不同角度灵活看待多抽象层上的数据挖掘结果。另一方面，数据挖掘 系统要把生成的结果通过交互界面传递给用户。因此，准确而直观地描述挖掘 的结果和友好而高效的用户界面一直是这方面研究的重要课题。 2 6 4 应用系统的集成 一个单独的数据挖掘发现系统如果不和具体的应用系统集成或结合，将毫 无意义。数据挖掘应该和数据库管理系统或m i s 、电子表单、实时传感数据采 集，特别是决策支持系统集成在一起。 2 6 5 挖掘对象的多样化 数据库发展的一个趋势是各种类型数据的使用，特别是多媒体数据越来越 多，这要求相应的数据挖掘系统不但有处理数值数据的功能，还应能处理符号、 1 0 第2 章数据挖掘技术 文本、声音、图形、图像、视频等类型数据。 以上的问题涉及数据挖掘的方方面面，它们都有待人们去进行更深入的研 究工作，这将不断的推动数据挖掘技术深入发展和广泛应用，创造出更多的社 会和经济价值。 2 7 本章小结 本章论述了数据挖掘产生的历史必然性，介绍了数据挖掘的概念，数据挖 掘的功能，数据挖掘的过程，数据挖掘技术研究的方向以及数据挖掘过程中应 该注意的问题等等。 第3 章关联规则数据挖掘算法研究 第3 章关联规则数据挖掘算法研究 关联规则( a s s o c i a t i o nr u l e ) 的概念首先是由r a g r a w a l 等人于1 9 9 3 年 在嘲中提出的，此后他们又在口m 3 中对关联规则进行了更深入的研究。关联规则 挖掘用来发现大量数据中项集之间有趣的关联或相关联系。随着大量数据不停 地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴 趣。从大量商业事务记录中发现有趣的关联关系，可以帮助制定商务决策，如 货架布置、捆绑销售等。 引发关联规则挖掘的典型例子是购物篮分析。它通过发现顾客放入其购物 篮中不同商品之间的联系，分析顾客的购买习惯，这种关系的发现可以帮助零 售商制定营销策略。例如，在设计商店布局时，可以将经常一块购买的商品放 近一些，以刺激这些商品一起销售；也可以将这些商品放在货架的两端，诱发 购买这些商品的顾客一路挑选其他商品。 如何从大量数据中发现关联规则? 什么样的关联规则最有趣? 下面重点讨 论这些问题。 3 1 关联规则挖掘的基本概念 3 1 1 关联规则的含义 关联规则是形如x = y 的表示式，其中x 和y 是项的集合。这种规则的 直观含义是：包含x 的事物通常也包含y 陋1 。例如，在超级市场中“有2 的 客户同时购买了蔬菜和水产，而购买蔬菜的顾客中有6 0 的人同时也购买了水 产”。这里2 被称为规则的支持度( s u p p o r t ) ，6 0 被称为规则的置信度 ( c o n f i d e n c e ) 。如果一个规则满足最小支持度阈值( m i n _ s u p ) 和最小置信度阈 值( m i n _ c o n f ) ，则被认为是有趣的。最小支持度和最小置信度阈值一般由用户 或领域专家设定。 3 1 2 关联规则相关概念 设i = i 。，i 。，i 。) 是项的集合。设任务相关的数据d 是数据库事务的 北京工业大学工学硕士学位论文 集合，其中每个事务t 是项的集合，使得t 量i 。每个事务有一个标识符，称 作t i d 。设x 是一个项集，x c i ，x c t ，y c i ，且x n y = o ，如果规则x = y 在事务集合d 中成立，具有支持度s 、置信度c ，并满足最小支持度阈值和最小置 信度阈值，则称此规则为强关联规则。其中： s u p p o r t ( x = y ) = p ( x u y ) c o n f i d e n c e ( x = y ) = p ( yx ) 含有k 个项的项集称为k 一项集，项集的出现频率是包含项集的事务数，称 为项集的频率、支持计数或计数。如果项集的出现频率大于或等于最小支持度 与d 中事务总数的乘积，即项集满足最小支持度，则称它为频繁项集( f r e q u e n t it e m s e t ) 。频繁k 一项集的集合通常记作l k 。 关联规则的挖掘分成两步： ( 1 ) 找出所有频繁项集，即找出所有满足最小支持度的项集。 ( 2 ) 由频繁项集产生强关联规则，也就是说要找出满足最小支持度和最小 置信度的规则。 由于第二步相对较容易，因此目前的研究重点在第一步，即找出频繁项集。 挖掘的总体性能也由第一步决定。 3 2 关联规则挖掘算法a p r i o r i a p r i o r i 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。它使 用一种称作逐层搜索的迭代方法，k 一项集用于探索( k + 1 ) 一项集。首先，找出频 繁卜项集的集合，该集合记作l 。l 。用于找频繁2 一项集的集合l 。，而l 。用于找l 。， 如此下去，直到不能找到频繁k 一项集。找每个l 。需要一次数据库扫描。为提高频 繁项集逐层产生的效率，a p r i o r i 性质被用于压缩搜索空间。 a p r i o r i 性质：频繁项集的所有非空子集都是频繁的n 3 。 证明：设项集r 是频繁的，即p ( r ) m i ns u p 。项集r 的任一非空子集 p ，p c r 。对事务t ，如果r c t ，则p c r c t ，即包含项集r 的事务同时也包 含项集p 。因此，项集p 出现的频率不会小于项集r 出现的频率，即p ( p ) p ( r ) 。又因为p ( r ) m i n _ s u p ，所以p ( p ) m i n _ s u p ，即项集p 是频繁的。 推论1若k _ 项集的某个非空子集不是频繁的，则该k _ 项集也不是频繁 的。 推论1 是a p r i o r i 性质的逆否命题。推论l 说明了这样一个事实，如果一个集 合不能通过测试，则它的所有超集也不能通过相同的测试。a p r i o r i 算法正是利 用这样的事实来压缩搜索空间的。 由l h 找l k ，要经过两个步骤：连接和剪枝。连接就是通过l k 。与自己连接 1 4 第3 章关联规则数据挖掘算法研究 产生候选k 一项集的集合。该候选项集的集合记作c t 。剪枝就是对c t 中的各项集出 现次数计数，将c 。中不满足最小支持度的项集删除掉，则所有满足最小支持度的 项集构成了l 。如果根据连接的结果直接进行数据库扫描，计算量太大，因为连 接的结果集可能很大。 a p r i o r i 算法伪代码描述如下陷1 ： 算法：a p r i o r i 使用根据候选生成的逐层迭代找出频繁项集。 输入：事务数据库d ，最小支持度阈值m i n _ s u p 。 输出：d 中的频繁项集l 。 方法： 1 ) l 1 = f i n d _ f r e q u e n t _ 1 - i t e m s e t s ( d ) ； 2 ) f o r ( 1 f 2 ；l r 一1 a ；k 抖) 3 ) 4 )c k = a p r i o r i _ g e n ( l k 1 ，m i n _ s u p ) ； 5 ) f o re a c ht r a n s a c t i o nt d 6 ) s c a nd a t a b a s ef o rc o u n t s 7 )c t = s u b s e t ( c k ，t ) ；g e tt h es u b s e t so f tt h a ta r ec a n d i d a t e s 8 ) f o re a c hc a n d i d a t ec c t 9 )c c o u n t + + ； 1 0 ) 1 1 ) l k = c c ric c o u n t m i n _ s u p 1 2 ) 1 3 ) r e t u l t ll =u k l k ； p r o c e d u r ea p r i o r i _ g e n ( l k l ：f r e q u e n t (