（计算机应用技术专业论文）教育信息的关联规则挖掘.pdf

摘要 教育信息化使教育系统结累了大量的与教育、教学有关的数据，激增的数 据背后隐藏着许多重要的信息，由于缺乏挖掘数据背后隐藏的知识的手段，无 法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。 导致了“数据爆炸但知识贫乏”的现象。数据挖掘就是从大量的、不完全的、 有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不 知道的，但又是潜在有用的信息和知识的过程。关联规则挖掘是数据挖掘的一 个重要方面，它揭示事物之间的相关程度。教育中存在很多相关性问题，可以 用关联规则挖掘方法对教育信息进行数据挖掘，发现其中的教育规律。 关联规则表达数据库中属性之间的相关程度。关联规则x j y ，s u p p o r t = s ， c o n f i d e n c e = c 表示由规则的前提x 得到规则的结果y ，支持度为s ，置信度 为c 。本文通过对教育信息的关联规则挖掘，得出类似物理j 数学， s u p p o r t = 2 5 ，c o n f i d e 目a c e = 7 7 的结果，利用关联规则揭示的教育、教学的内 部规律、学生的发展模式、学课之间的相关性规律，科学地制定教育的中、长 期规划，更新教育理念，合理地组织教学活动，理性地引导学生朝德、智、体 方面全面发展。 关联规则挖掘的基本方法是基于频集的a p r i o r i 算法，根据给定的最小支持 度( m i n _ s u p ) ，在待挖掘数据库中找出所有频繁项集，根据给定的最小置信度 ( m i nc o a l ) ，由频繁项集产生强关联规则。在众多的数据挖掘工具中本文中采 用基于m ss q ls e r v e r 环境的数据挖掘。根据教育信息的数据特点，在应用 a p r i o r i 算法时稍作修改，即在用a p r i o r i 算法计算频繁项集前，先用类似聚类 的方法压缩数据( 经过量化处理) ，然后对压缩过的数据计算频繁项集，使计算 频繁项集的数据量减少。 教育信息挖掘模型( e i d m ) 是以教育系统为主要应用领域，以交互性、 数据源的可选择性、系统的可集成性、易操作性为主要设计原则的数据挖掘系 统模型，其中变换方法和量化方法体现了处理教育数据的功能，通过增加挖掘 模式库、变换方法和量化方法库的方法可较容易地扩充e i d m 的挖掘功能。 系统设计中采用不同的数据挖掘方法和不同的数据挖掘参数，产生不同应用 层次的关联规则，取其共同部分按被认可的程度分为三类：第一类规则描述的事 实和传统的教育学对有关问题的认识相一致，数据挖掘获得的关联规则用数据进 一步证实了教育理论的有关论述。第二类规则是人们在研究和工作中没有认识到 的或未被重视的事实，这类规则反映了教育规律，这是通过数据挖掘获取的新知 识。第三类规则是以前未被发现、现在也未被教育专家认可，但在现实中业已存 在、而且是在一定条件下一种有代表性的现象，其内涵还有待进一步研究。 关键词 关联规则，数据挖掘，教育信息，支持度，置信度 2 a b s t r a c t a l a r g e n u m b e rd a t ah a v eb e e nc r e a t e di nt h ec o u r s eo ft h ee d u c a d o n i n f o r m m i o n a l i t y t h e r ei sal o to fi m p o r t a n ti n f o r m a t i o na b o u te d u c a t i o ni nt h i sd a t a w ec a n tf i n dt h er e l a t i o na n dr u l e se x i s t e di nt h ed a t ab e c a u s el a c k e dt h et o o l so f k n o w l e d g ed i s c o v e r e d w eo x eu n a b l et of o r e c a s tf u t u r ea c c o r d i n g t ot h ee x i s t i n gd a t a i tc a u s e d t h ed a t ae x p l o s i o nb u t k n o w l e d g ed e f i c i e n t t h ed a t am i n i n gm e a n st h e p r o c e s st h a td i s c o v e r e dt h eu s e f u li n f o r m a t i o na n dk n o w l e d g ef r o mt h ed a t at h a ti s m a s s i v e ，n o tc o m p l e t e ，w i t hn o i s e ，f u z z ya n ds t o c h a s t i c t h ea s s o c i a t i o nr u l e1 i l i i l i i 玛 i sa ni m p o r t a n tf i e l do f d a t a m i n i n g i tp r o v i d e st h ed e g r e eo f r e l e v a n c eo f t h et h i n g s t h e r ea r em a n ya s s o c i a t i o nr u l e si ne d u c a t i o nd a t a d a t am h 1 i n g 啪d i s c o v e ri t t h ea s s o c i a t i o nr u l e se x p r e s st h er e l a t i o n a l i t yb e l 阳f 嘲t h ea t t r i b u t e so fd a t a b a s e s t h er u l ex j y ，s u p p o r t = s ，c o n f i d e n c e = c m e a n st h a to b t a i nt h eyf o r mxh a v e s u p p o r t = s a n dc o n f i d e n c e = c i nt h i sp a p e rw en l i n et h ea s s o c i a t i o nr u l e sf r o m e d u c a t i o ni n f o r m a t i o n t h er u l e ss u c ha sp h y s i c 蹄m a t h e m a t i c s ，s u p p o r t = 2 5 a n d c o n f i d e n c e = 7 7 c a l lb eo b t a i n e d e d u c a t i o n a la c t i v i t yw i l lb e o r g a n i z e da n dd e s i g n e d s c i e n t i f i c a l l yb yl o n gt i m ep l a na c c o r d i n gt ot h er u l e st h a te x p r e s st h ee d u c a t i o n a l r u l e s ，t h ed e v e l o p m e n to f s t u d e n t s ，a n dt h er e l e v a n tb e t w e e n t h ec o u r t s ， t h ee s s e n t i a lm e t h o do fa s s o c i a t i o nr u l e sm i n i n gi sb a s e do nt h el a r g ei t e m s e t s a p r i o r ia l g o r i t h m f i r s t , f i n dt h ef r e q u e n ti t e m s e t sa c c o r d i n gt o s m a l l e s ts u p p o r t a s s i g n e d s e c o n d ，f m dt h e s t r o n g a s s o c i a t i o nr u l e s a c c o r d i n g t ot h es m a l l e s t c o n f i d e n c e w e p r e f e rt h em ss q l s e r v e ra sm i n i n gt o o la m o n gs e v e r a ld a t am i n i n g s o f t w a r e s o m em o d i f i c a f i o nh a sb e e nm a d ei n a p r i o r ia l g o r i t h mi nt h el i g h to f p a r t i c u l a r i t yo fe d u c a t i o ni n f o r m a t i o n t h ed a t ah a v eb e e nc l u s t e r e db e f o r et o b e m i n e du s e d a p f i o r ia l g o r i t h m t h em a i na p p l i c a t i o nf i e l d so fe d u c a t i o ni n f o r m a t i o nd a t am i n i n g ( e i d m ) m o d e la r ee d u c a t i o ns y s t e m i th a sc h a r a c t e r i s t i co fi n t e r a c t i o n a l l y , s e l e c t i v i t yo f s o u r c ed a t a , i n t e g r a t i o n a l l ya n do p e r a t i o n a l l y t h et r a n s f o r m a t i o na n dq u a n t i f i c a t i o n 3 m e t h o dm a n i f e s tt h ef u n c t i o no fp r o c e s s i n ge d u c a t i o nd a t a i ti s e a s y t o e x p a n d f u n c t i o no ft h ee i d mb yi n c r e a s i n g m i n i n gp a t t e r n , t r a n s f o r m a t i o n m e t h o da n d q u a n t i f i c a t i o nm e t h o d i nt h es y s t e md e s i g n e d ，t h ea s s o c i a t i o nr u l e so fs e v e r a la p p l i c a t i o nl e v e lh a v e b e e no b t a i nw i t h s o m ed i f f e r e md a t am i n i n gm e t h o da n d p a r a m e t e r t h e r e s u l t sc a nb e d i v i d e di n t ot h r e ek i n d sa c c o r d i n gt ow h i c ht h e ya l ea c c e p t e d t h ef i r s tk i n d ：t h e r u l e s d e s c r i p tt h ef a c t st h a tc o n s i s tw i t ht h eu n d e r s t a n d i n ga b o u te d u c a t i o nt h e o r y t h i s a s s o c i a t i o nr u l e so b t a i n e db yd a t am i n i n gh a v ei m p r o v e dt h ee d u c a t i o nt h e o r yw i t h d a t a ，t h es e c o n dk i n d ：t h er u l ei st h ef a c tt h a th a sn o tb e e nr e a l i z e do rp a i da t t e n t i o n b e f o r e ，b u ti ti sr e c o g n i z e dt h en e w r u l e so fe d u c a t i o na n dn e wk n o w l e d g en o w , t h e t h i r dk i n d ：t h er u l ei sn o td i s c o v e r e db e f o r ea n di sn o tr e a l i z e db ys p e c i a l i s ta n d e d u c a t i o n a l i s tn o w b u ti tr e f l e c t e das o r to fp h e n o m e n o nt h a ti th a sb e e na n di t i s r e p r e s e n t a t i v ei nt h ec e r t a i nc o n d i t i o n t h er e a s o n o f t h i sk i n do f r u l es h o u l db es t u d y f u r t h e r k e yw o r d s a s s o c i a t i o nr u l e s ，d a t am i n i n g ，e d u c a t i o ni n f o r m a t i o n ，s u p p o r t , c o n f i d e n c e 4 论文独创性声明 y 6 4 0 8 9 7 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文 中除了特别加以标注和致谢的地方外，不包含其他人或其他机构已经发表或 撰写过的研究成果。其他同志对本研究的启发所做的贡献均已在论文中作了 明确的声明并表示了谢意。 作者签名： 单嗽一 论文使用授权声明 本人同意上海海运学院有关保留、使用学位论文的规定，即：学校有权 保留送交论文复印件，允许论文被查阅和借阅；学校可以上网公布论文的全 部或部分内容，可以采用影印、缩印或者其它复制手段保存论文。保密的论 文在解密后遵守此规定。 名：螳翩张压垃臁 第一章概述嘲 1 1 引言 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来 越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行高层次的分析， 以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计 等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋 势。由于缺乏挖掘隐藏在数据背后的知识的手段，导致了“数据爆炸而知识贫乏”的现 象。数据挖掘使数据库技术进入了一个更高的阶段，它不仅能对过去的数据进行查询和 遍历，而且能够找出过去数据之间的潜在联系。数据挖掘就是从大量的、不完全的、有 噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的，但 又是潜在有用的信息和知识的过程。数据挖掘可根据其功能分为：特征化和区分、关联 分析、分类和预测，聚类分析、孤立点分析和演变分析等。本文旨在运用经典的挖掘算 法，挖掘隐藏在教育信息中的关联规则。 关联规则是r a k e s ha g r a w a l 等人提出的数据挖掘领域中的一个重要课题。关联规 则揭示数据间的相互关系，关联规则的挖掘就是从一组给定的数据项以及交易集合( 每 一条交易是一个数据项的集合) 中，分析出数据项集在交易集合中出现的频度关系。挖 掘关联规则的算法已经有很多，比较重要的是a g r a w a l 等人提出的a p r i o r i 算法，以后 诸多的研究人员对关联规则挖掘算法进行了大量的研究和优化。如s a v a s e r e 等人设计了 一个基于划分( p a r t i t i o n ) 的算法，p a r k 等人提出的基于杂凑( h a s h ) 的算法、m a n n i l a 提出的基于采样的方法、l i n 和d u n h a m 提出的反扭曲( a n t i s h e w ) 算法、b r i n 等提出 的算法使用比传统算法少的扫描遍数来发现频集。随着关联规则挖掘被大量的应用，研 究人员先后提出了关联规则的若干种变体：s r i k a n t 等引入了泛化关联规则、a m i r 等提 出了排除关联规则、s a v a s e r e 提出了否定关联规则、o g d e n 提出的周期关联规则、 r s r i k a n t 等提出的数量关联规则、t u n g 提出的交易间联系规则。 1 2 问题的提出 关联规则挖掘较多地应用于商业系统，用于发现交易数据中不同商品( 项) 之间的 【注】本文得到黄浦区教育局重点课题“黄浦区教育信息关联规则挖掘”的资助a l 联系，这些规则找出顾客的购买行为模式，如购买了某一商品对其它商品的影响。发现 这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。在 已有的数据挖掘应用中，较少看到用于教育信息的挖掘，更少看到直接对反跌学生学业 情况的数据进行关联规则的挖掘，本文旨在对教育领域的数据挖掘进行探索性研究。 在教育系统中，特别是在各级各类学校中，学校的数据库中存贮着大量的教育教学 信息，其中一部分和教学有关：如学校的开课排课情况、任课教师情况等，另一部分是 和学生有关的信息：如学生的基本情况、家庭背景、身体状况、学生的历年的考试、测 验成绩等。特别是最近几年来随着教育信息化的推进、学校数据库的内容大大增加，学 校几乎实现了无纸化管理，所有的信息几乎都能在电脑上找到，学校数据库的内容已经 相当的完整。但是这些数据很少被开发利用，除了学期结束时打印学生情况表、打印学 期汇总表外，就是历届学生偶尔来校查一下在校时的成绩等简单的查询，这些隐藏着大 量教育信息的历史数据没有被好好地利用，没有好好挖摘隐藏在这些数据中的教育规律、 学生的培养模式、学生学课之间的差异性和相关性规律。 另一方面，在教育系统中存在着一些缺少依据的说法：如数学成绩好的同学物理成 绩也一定很好，或数学成绩好的同学其他的理科一定很好。如钢琴弹得很好的同学，他 的成绩一定不会差。又如父母是商学历的，孩子成绩一般不会差等等。在一定的条件下， 这些说法因其基本与事实一致而被广泛接受，但这些命题缺少理论的和实验的依据。这 些说法完全可以利用现在已经拥有的大量的数据，对其进行数据挖掘，来证实某些命题， 或说明某些说法不能成立，或者更确切地说明其支持度和可信度。 从大量的教育信息中挖掘出的正确的、可靠的、可信的关联规则对教育系统是相当 重要的，对教育教学改革具有指导性的意义。学校可以利用关联规则所揭示的学生在学 习中学课之间的相关性，适当组合学课课程，使相关学课互相促进共同提高；利用关联 规则发现的学生培养模式，合理设计课程开设的次序，符合学生智力发展规律；利用学 课的相关性、知识的相关性、学生学习兴趣的可迁移性，在活动课中组织跨学课的活动， 扩大学生在学习中学课之间的相关性和相关程度，引导学生从强势学课入手，提高相对 较弱的学课，最终使学生在学业上均衡发展。 本文通过对现有的教育教学历史数据进行关联规则的挖掘，其目的：( 1 ) 从大量的 数据中寻找教育规律、学生成长规律、学生学业成绩变化规律，揭示教育、教学中客观 存在的但未被发现的规律、或以前虽有认识，但不全面的规律，从了解规律着手，制订 2 正确的教育策略，使现代化的教育更有效。( 2 ) 可以从数据中寻找关联规则来验证教育 科学研究的结论，使其更科学、更有说服力。教育科研中常用的取样的方法可能会因样 本数据太小而不准确，也可能因为采用调查表时的霍桑效应使被试验者或被调查者处于 非常态而和常态下的数据有误差，而对历史数据的挖掘可以克服上述存在的缺陷。( 3 ) 通过本课题的研究，选择适当的关联规则挖掘算法、合适的数据挖掘工具和软件，形成 一个可行的教育教学数掘挖掘方法，使其能广泛地应用于教育教学决策和教育科学研究。 1 3 教育信息库 教育信息库由结构化的信息和非结构化信息组成。结构化信息是存在逻辑关系的数据 和信息，它包括各种数据库如f o x p r o 、f o x b a s e 、a c c e s s 、s q ls e r v e r 、s y b a s e 和e x c e l 等如图1 1 所示。 f o x p r o f o x b a s e t e x t 文本 数据文件 w e b 信息 匣曰口。 同构异构 图1 1 教育信息库结构 f o x p r o ：由于历史的原因，教育系统的招生考试信息系统多采用f o x p r o 数据库管 理系统，记录着所有学生的基本信息、报名信息、考试成绩、录取情况、获奖记录 等。 。f o x b a s e ：学校早期的信息管理系统较多采用f o x b a s e ，主要记录的是学生成绩， 如采用时序数据挖掘，这部分历史较长的数据最为有用。 。s q ls e r v e r ：区信息中心和大多数学校的管理信息系统采用此数据库，是区域中 数据库管理系数的主体。 a c c e s s 、s y b a s e ：部分学校管理信息系统采用的数据库。 e x c e l ：一些特殊的数据或根据特殊需要采集的数据。 这些结构化的数据库因采用异构的数据库管理系统，如数据挖掘所需的信息存放于几 种不同的、异构的数据库中，则在数据挖掘前必需通过数据集成将它们转换成同一结构 的数据库。教育信息还大量地以非结构化( 或半结构化) 的形式存在，且分散在各个部 门中，它们可能的形式是：w o r d 文档、某种数据文件、w e b 信息、t e x t 文本、多媒体图 像、甚至于保存在传统存储介质中的数据。若要对这类数据进行数据挖掘，应先将这些 数据转化为结构化数据或采用专门的数据挖掘方法如w e b 数据挖掘、t e x t 文本数据挖掘。 4 第二章基本概念 2 1 数据挖掘 2 1 1 数据挖掘的定义 1 9 8 9 年8 月，在第l l 届国际人工智能联合会议的专题讨论会e ，首次提出基于数据 库的知识发现( k o d ，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 ) 技术。该技术涉及机器学习、 模式识别、统计学、智能数据库、知识获取、专家系统、数据可视化和商性能计算领域。 1 9 9 5 年，在美国计算机年会( a c m ) 上，提出了数据挖掘( d m ，d a t am i n i n g ) 的概念， 即通过从数据库中抽取隐含的、未知的、具有潜在使用价值信息的过程。数据挖掘是k d d 过程中最为关键的步骤，在实际应用中对数据挖掘和曲d 这二个术语往往不加区别。数 据挖掘诞生后，诸多因素促进了数据挖掘技术的发展和应用，大规模数据库，尤其是数 据仓库的出现，促使数据挖掘技术得到迅速发展和应用；计算机技术，尤其是网络技术 和并行处理体系的发展，速度快、运算能力强的计算系统为数据挖掘的实现提供了良好 的6 l = 境；全球经济一体化的进程日盏加快，企业所面临的市场竞争压力日趋严重，企业 经营管理者希望能够从企业积累的大量历史数据中找到经营管理中存在的问题及其原 因；相关科学的发展促进了数据挖掘技术的应用。 数据挖掘的定义：塑堡整塑! 堕望m 幻i 啦煎是丛太量曲! 丕宝垒笪! 直堡直笪：搓 携曲，堕扭煎墼握主：握墼险盒查墓生照，厶鱼蔓盘丕知遒的! 焦区星澧查直目曲篮星 塑翅退曲蕉程! 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是数据挖掘是 在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有未知，有 效和可实用三个特征。 先前未知的信息是指该信息是预先未曾预料到的，既数据挖掘是要发现那些不能靠直 觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎薏料，就可 5 能越有价值。在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布 和啤酒之间有着惊人的联系。信息的有效性要求挖掘前要对被挖掘的数据进行仔细检查， 只有保证信息( 或数据) 的有效性，才能保证挖掘出来的信息的有效性。最为重要的是要 求所得的信息是有可实用性，即这些信息或知识对于所讨论的业务或研究领域是有效的、 是有实用价值和可实现的。常识性的、已被人们掌握的或无法实现的事实都是没有意义 的。 2 1 z 数据挖掘过程 数据挖掘过程可分为数据预处理( 数据清理、数据选择和数据集成) 、数据变换、数 据挖掘、模式评估和表示。数据挖掘过程如图2 1 图2 ，i 数据挖掘过程 ( 1 ) 数据预处理：数据预处理包括数据清理、数据选择和数据集成。 6 数据清理的任务是消除数据源( 如：关系数据库、数据仓库、事务数据库、超 文本和多媒体数据、w w w 等) 中的噪声、识别和处理孤立点数据，纠正数 据中的不一致，处理空缺值。数据中存在随机错误( 噪声) 和孤立点，噪声应 采取措施使其平滑，孤立点应识别是错误数据还是有用的但以前没有认识到的 数据。被挖掘的数据，特别是来自不同数据源的数据，可能对同一对象采用不 一致的描述：输入的错误也可能造成不致。对数据中的空缺值，可根据其数 据量的大小、对数据挖掘结果可能的影响，采用忽略该记录或填入适当的值( 如 中值或平均值) 。 数据选择是从所有与业务对象有关的数据中选择出适用于数据挖掘应用的数 据，舍弃与数据挖掘无关的数据。 数据集成是将多个数据源中的数据结合起来存放在一个一致的数据存储中，过 程中要消除属性的冗余。 数据清理、数据选择和数据集成三者的操作次序由数据源的环境与数据挖掘的 环境决定，可能的情况下先进行数据选择可以减少后阶段操作的数据量。 ( 2 ) 数据变换：将数据转换成适合于挖掘的形式。主要内容可能包括： 聚集：对某些数据进行汇总以适合挖掘算法。如将一天的销售量汇总成日 销售量。 数据归纳：使用概念分层，用高层次概念替换低层次的原始数据。 属性规范化：将属性数据按比例缩放，使之落在一个特定的区间，如o 1 0 0 。 属性构造：由已有的属性构造和添加新的属性，如由属性h e i g h t 和w i d t h 构造和添加a r e a 属性。 - 数据量化：对量化属性，使用预定义的概念分层进行离散化，以区间值替 换属性原来的数值。 ( 3 ) 数据挖掘：根据所采用的挖掘算法，运行相应挖掘软件和程序，产生候选数据 模式。 ( 4 ) 模式评估和表示：根据给定的兴趣度来评估所发现的候选数据模式，过滤掉不 感兴趣的模式，表示真正有趣的模式。 2 1 3 数据挖掘的功能 数据挖掘所能发现的知识有如下几种：广义型知识，反映同类事物共同性质的知识； 特征型知识，反映事物各方面的特征知识；差异型知识，反映不同事物之间属性差别的 知识；关联型知识，反映事物之间依赖或关联的知识；预测型知识，根据历史的和当前 的数据推测未来数据：偏离型知识，揭示事物偏离常规的异常现象。所有这些知识都可 以在不同的概念层次上被发现，以满足不同层次决策的需要。例如，从一家超市的数据 仓库中，可以发现的一条典型关联规则可能是买影碟机的顾客十有八九也买光盘”，这 种规则对于商家开发和实施客户化的销售计划和策略是非常有用的。 以下将主要从挖掘任务和挖掘方法的角度，着重讨论数据抽取、分类发现、聚类和 关联规则发现四种非常重要的发现任务。 ( 1 ) 数据抽取 数据抽取目的是对数据进行浓缩，给出它的紧凑描述。传统的也是最简单的数据抽 取方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值，或者用直方 图、饼状图等图形方式表示。数据挖掘主要关心从数据泛化的角度来讨论数据总结。数 据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过程。由于数据库上的 数据或对象所包含的信息总是最原始、基本的信息( 这是为了不遗漏任何可能有用的数 据信息) 。人们有时希望能从较高层次的视图上处理或浏览数据，因此需要对数据进行 不同层次上的泛化阱适应各种查询要求。数据泛化目前主要有两种技术：多维数据分析 方法和面向属性的归纳方法。 ( 2 ) 分类发现 8 分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。分类的目的是 找出一个分类函数或分类模型( 也常常称作分类器) ，该模型能把数据库中的数据项映 射到给定类别中的某一个。分类和回归都可用于预测。预测的目的是从利用历史数据记 录中自动推导出对给定数据的广义描述，从而能对未来数据进行预测。 要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库记录或 元组构成，每个元组是一个由有关字段( 又称属性或特征) 值组成的特征向量，此外， 训练样本还有一个类别标记。一个具体样本的形式可为：( v l ，v 2 ，v n ：c ) ：其中v i 表示字段值，c 表示类别。分类的效果一般和数据的特点有关。 ( 3 ) 聚类 聚类是把一组个体按照相似性归成若干类别，即物以类聚。它的目的是使得属于 同一类别的个体之间的距离尽可能的小，而不同类别上的个体间的距离尽可能的大。聚 类能帮助市场分析人员从客户数据库中发现不同的客户群，并且用购买模式来刻画不同 的客户群的特征。此外，聚类分析可以作为其它算法的预处理步骤。聚类方法包括统计 方法、机器学习方法、神经网络方法等。 ( 4 ) 关联规则发现 关联规则是形式如下的一种规则，“在购买面包和黄油的顾客中，有9 0 的人同时也 买了牛奶”( 面包八黄油j 牛奶) 。用于关联规则发现的主要对象是事务型数据库，其 中针对的应用则是售货数据，也称货篮数据。如果对这些历史事务数据进行分析，则可 对顾客的购买行为提供极有价值的信息。例如，可以帮助如何摆放货架上的商品( 如把 顾客经常同时买的商品放在一起) ，帮助如何规划市场( 怎样相互搭配进货) 。又如， 可以针对学生的学业情况记录，分析学生的学习兴趣与学科发展的规律和相关性， “数 学和外语好的同学中，7 7 的人物理也很好”( 数学八外语物理) 。“物理好的同学 中，7 7 的人数学也很好”( 物理j 数学) 。可以利用发现的关联规则，在教学中采用 某种策略，使这些关联规则所反映的教育规律在教学中发挥作用。 9 2 1 4 数据挖掘的分类 数据挖掘涉及的学科领域很多，有多种分类法。根据挖掘任务分，可分为分类或预测 模型发现、聚类、关联规则发现、序列模式发现、异常和趋势发现等等；根据挖掘对象 分，有关系数据库、面向对象数据库、空间数据库、时态数据库、文本数据库、多媒体 数据库、以及环球网w e b ：根据挖掘方法分，可粗分为：机器学习方法、统计方法、神经 网络方法和数据库方法。 2 2 关联规则 2 2 1 关联规则的定义 设i = i ，i2 j ”，i 。l 是项( i t e m ) 的集合。记刀为交易( t r a n s a c t i o n ) t 的集合，这里 交易t 是项的集合，并且t i 。对应每一个交易有唯一的标识，如交易号，记作t i d 。 设x 是一个i 中项的集合，如果x c _ t ，那么称交易t 包含x 。 个关联规则是形如x 毒y 的蕴涵式，这里x c i ，y c l ，并且x n y = 4 ) 。规则x j y 在交 易数据库d 中的支持度( s u p p o r t ) 是交易集中同时包含x 和y 的交易数与所有交易数之 比，记为s u p p o r t ( x 等y ) ，即 s u p p o r t ( x j y ) = l t ：x u y t ，t e d ) f o l i o ( o b ：s 规则x ；y 在交易集d 中的可信度( c o n f i d e n c e ) 是指包含x 和y 的交易数与包含x 的交易数之比，记为c o n f i d e n c e ( x y ) ，即 c o n f i d e n c e ( x j y ) = l t ：x u y t ，t e d ) i i t ：x c t ，t e d ) i 1 0 0 = c c o n f i d e n c e 还可以用支持度来表示，即： c o n f i d e n c e ( x j y ) = s u p p o r t ( x j y ) s u p p o r t ( x ) 1 0 0 = c 给定一个交易集d ，挖掘关联规则问题就是产生支持度和可信度分别大于用户给定的 最小支持度( m i n s u p ) 和最小可信度( m i n c o n f ) 的关联规则。 如果不考虑关联规则的支持度和可信度，那么在事务数据库中存在无穷多的关联规 l o 则。事实上，人们一般只对满足一定的支持度和可信度的关联规则感兴趣，同时满足最 小支挣度( m i n s u p ) 和最小可信度( m i n c o n f ) 的规则称为强规则。因此，为了挖掘出 有意义的关联规则，需要给定两个阈值：最小支持度和最小可信度。前者即用户规定的关 联规则必须满足的最小支持度，它表示了一组物品集在统计意义上的需满足的最低程度： 后者即用户规定的关联规则必须满足的最小可信度，它反应了关联规则的最低可靠度。 在实际情况下，一种更有用的关联规则是泛化关联规则。因为物品概念间存在一种层 次关系，如夹克衫、滑雪衫属于外套类，外套、衬衣又属于衣服类。有了层次关系后， 可以帮助发现一些更多的有意义的规则。例如“购买外套j 买鞋子”( 此处，外套和鞋 子是较高层次上的物品或概念，因而该规则是一种泛化的关联规则) 。由于商店或超市中 有成千上万种物品，平均来讲，每种物品( 如滑雪衫) 的支持度很低，因此有时难以发 现有用规则；但如果考虑到较高层次的物品( 如外套) ，则其支持度就较高，从而可能发 现有用的规则。 另外，关联规则发现的思路还可以用于序列模式发现。用户在购买物品时，除了具 有上述关联规律，还有时间上或序列上的规律，因为，很多时候顾客会这次买这些东西， 下次买同上次有关的一些东西，接着又买有关的某些东西。 2 2 2 关联规则的分类： ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系； 而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行 处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联 规则中也可以包含种类变量。 例如：性别= “女”j 职业= “秘书”，是布尔型关联规则；性别= “女”j a v g ( 收入) = 2 3 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层 次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 台式机j s o n y 打印机，是一个细节数据上的单层关联规则；台式机 j s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而在多 维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则 是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。 例如：啤酒j 尿布，这条规则只涉及到用户的购买的物品；性别= “女”j 职 业= “秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。 给出了关联规则的分类之后，在今后的分析过程中，我们就可以考虑某个具体的方法 适用于哪一类规则的挖掘，某类规则又可以用哪些不同的方法进行处理。 1 2 第三章关联规则的挖掘 3 1 频繁项集 项的集合称为项集( i t e m s e t ) 。包含k 个项的项集称为k - 项集。 项集的出现频率是指包含该项集的事务数，简称为项集的频率，或支持度计数，简 称计数。如果项集的出现频率大于或等于m i n s u p 与d 中事务总数的乘积，即项集满足 最小支持度，则称它为频繁项集( f r e q u e n ti t e m s e t ) ，简称频集。频繁k - 项集的集合 记作l k 。表3 1 中的数据实例是从考试成绩数据表中摘录的十条记录，其中i 表示这门 学课成绩好，0 表示这门学课成绩不好( 详见5 3 1 ) 。在此表中寻找频繁项集的过程如 下( 设m i n _ s u p = 2 0 ，m i n _ c o n f = 4 0 ) ： 学号语文( c i )数学( c 2 )外语( c 3 )政治( c 4 )理化( c 5 ) 1o1l01 210lo0 3010lo 4o10l1 510o0l 6100lo 7o10o1 8o1loo 9o1lll 1 0l1l0l 表3 i 数据实例 我们可以把表3 1 当作一个事务集d ，则= l o 。支持度计数为2 ，其中五个项c l c 5 分别计数，计数值大于支持度计数2 的项保留，小于支持度计数的项舍弃，得频繁卜 项集如表3 2 。再由频繁卜项集产生候选频繁2 一项集如表3 3 ，对每一候选项进行支持 度计数，计数值大于支持度计数2 的项保留，小于支持度计数的项舍弃后得频繁2 一项集 ( 表略) ，最后由频繁2 一项集和a p r i o r i 性质：频繁项集的所有非空子集都必须也是频 繁的，得到频繁3 一项集( 表3 4 ) 。 项集支持度计数 c l 4 c 2 ) 7 c 3 ) 5 e 4 ) 4 c 5 6 表3 2 候选频繁1 一项集 i项集 支持度计数 i c 2 ，c 3 ，c 5 3 表3 4 候选频繁3 一项集 项集支持度计数 c i ，c 孙 l c 1 ，c 3 2 c 1 ，c 4 1 c 】，c 5 2 f c 2 ，c 3 4 c 2 ，c 4 3 c 2 ，c 5 ) 5 c 3 ，c 4 1 c 3 ，c 5 3 c 4 ，c 5 2 表3 ，3 候选频繁2