（教育技术学专业论文）基于关联规则数据挖掘技术的高校学生学习成绩分析.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 近年来随着高校不断扩招，学校学生人数和教师人数大幅度增加，给高校学生管 理和教学工作带来了严峻的考验，传统的教学管理手段已经逐渐不能适应社会的发展 了。高校有很多信息系统和各类数据库，如学籍管理系统、成绩管理系统、人事管理 系统等，这些系统和数据库已经积累了大量的数据，但是由于缺乏必要的信息技术和 手段，管理人员只能通过简单的统计分析、排序、备份等功能获得表面信息，隐藏在 数据背后的信息不能得到有效利用。 数据挖掘就是从历史数据集中发现隐含模式，并且应用这些模式进行预测。数据 挖掘技术能够对已有的大量数据分析的基础上进行科学研究、商业决策或企业管理， 从而达到为决策支持服务的目的。关联规则挖掘比较，是数据挖掘领域里最为活跃的 研究方向之一，它反映一个事件和其他事件直接依赖或关联的知识。 本文首先对数据挖掘做了一般性讨论，包括数据挖掘的历史、概念、相关技术。 然后，对数据挖掘中重要的关联规则挖掘算法做了深入的研究，分析了关联规则挖掘 算法中经典的a p f i o f i 算法及其a p f i o f i t i d 算法，总结了算法中存在的问题，接着在 a p f i o f i t i d 算法基础上提出了改进算法。最后，利用改进算法，依据数据挖掘的标准流 程对某高校2 0 0 4 级到2 0 0 8 级五个年级不同专业学生的计算机程序设计基础与v f 课程成绩为研究对象，挖掘得到了影响成绩的因素，从而为提高教学质量提供依据。 高校中可以挖掘的信息不仅仅是成绩，还可以对学生年龄( 思维认知成熟度) 、性别、 爱好、家庭背景、健康状况、学籍、学历、高考成绩、课程内容、试卷、教师等信息 进行数据挖掘，从而为管理者和教师提供决策依据，因人施教，提高高校教学水平和 教学管理工作成效。 关键词：数据挖掘；成绩； a p f i o f i 算法；a p f i o f i t i d 算法 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t t h ef a c t ，t h a tw i t ht h ee n r o l l m e n te x p a n s i o n ，t h en u m b e ro fs t u d e n t sa n dt e a c h e r so f c o l l e g eh a si n c r e a s e dg r e a t l yi nr e c e n ty e a r s ，g i v e st h em a n a g e m e n ta n dt e a c h i n gas e v e r e t r i a l t h et r a d i t i o n a lm a n a g e m e n ta n dt e a c h i n gm e t h o d sc a nn o ta d a p tt ot h ed e v e l o p m e n to f s o c i e t y t h e r ea r em a n yi n f o r m a t i o nm a n a g e m e n ts y s t e m sa n dd a t a b a s e si nt h ec o l l e g e ，s u c h a ss t u d e n tr e g i s t r a t i o nm a n a g e m e n ts y s t e m ，a c h i e v e m e n tm a n a g e m e n ts y s t e ma n dp e r s o n n e l m a n a g e m e n ts y s t e m t h e s es y s t e m sa n dd a t a b a s e sh a v ea c c u m u l a t e dl a r g ea m o u n to fd a t a i nf a c t ，h i g h e re d u c a t i o na d m i n i s t r a t o r sc a no b t a i nt h es u p e r f i c i a li n f o r m a t i o no n l yb yt h e s i m p l es t a t i s t i c a la n a l y s i s ，s o r t i n ga n db a c k u p h o w e v e r , t h ei n f o r m a t i o nb e h i n dt h ed a t ac a n n o tb eu t i l i z e de f f e c t i v e l y d a t am i n i n g ( d m ) i sf o c u s e do nt h ed i s c o v e r yo fm o d e lh i d d e nf r o mt h eh i s t o r i c a ld a t a a n du s et h em o d e l st op r e d i c tt h ef u t u r e d mc a nm a k et h es c i e n t i f i cr e s e a r c h b u s i n e s s d e c i s i o na n dm a n a g e m e n tb a s e do nl a r g ea m o u n to fd a t ae x i s t e d ，s oa st os u p p o r tt h e d e c i s i o n - m a k i n g a s s o c i a t i o nm i n i n gi s t h eo n eo fm o s ta c t i v er e s e a r c hd i r e c t i o n s i t r e f l e c t st h ed i r e c td e p e n d e n to ra s s o c i a t e dk n o w l e d g eb e t w e e no n et h i n ga n do t h e rt h i n g s f i r s to fa l l ，t h i st h e s i sm a k e sag e n e r a ld i s c u s s i o na b o u td m ，i n c l u d i n gd mh i s t o r y , c o n c e p t sa n dr e l a t e dt e c h n o l o g i e s t h e n ，i tm a k e sd e e p r e s e a r c ha b o u tt h ei m p o r t a n t a s s o c i a t i o nr u l em i n i n ga l g o r i t h m si nd m ，a n a l y s e st h ec l a s s i c a la p r i o r ia l g o r i t h ma n d a p r i o r i t i da l g o r i t h m ，s u m n l su pt h ep r o b l e m so ft h ea l g o r i t h m t h e n ，o n ei m p r o v e d a l g o r i t h mh a sb e e np r o p o s e db a s e do na p r i o r i t i da l g o r i t h m au n i v e r s i t y2 0 0 4 - 2 0 0 8g r a d e s t u d e n ta c h i e v e m e n to ft h ec o u r s e c o m p u t e rp r o g r a m m i n gb a s ea n dv f a st h er e s e a r c h o b j e c t ，u s i n gt h es t a n d a r dd mp r o c e s sa n di m p r o v e da p r i o r i t i da l g o r i t h m t h i st h e s i so b t a i n t h ef a c t o r sa f f e c t i n gt h es t u d e n ta c h i e v e m e n t ，s oa st os u p p l yt h eb a s i sf o ri m p r o v i n g t e a c h i n gq u a l i t y w ec a nn o to n l ym i n et h es t u d e n ta c h i e v e m e n tb u ta l s os t u d e n ta g e ( m a t u r i t yo f c o g n i t i v et h i n k i n g ) ，g e n d e r ，h o b b i e s ，f a m i l yb a c k g r o u n d ，h e a l t hs t a t u s ，s t u d e n tr e g i s t r a t i o n ， e d u c a t i o n ，c o l l e g ee n t r a n c ee x a m i n a t i o nr e s u l t s ，c o u r s ec o n t e n t ，e x a mp a p e r , t e a c h e r ，a n d o t h e ri n f o r m a t i o n ，s oa st os u p p l yt h ed e c i s i o n m a k i n gb a s i sf o ra d m i n i s t r a t o r sa n dt e a c h e r s ， t e a c hs t u d e n t sa c c o r d i n gt ot h e i rc h a r a c t e r s ，i m p r o v et h el e v e lo fc o l l e g et e a c h i n ga n d m a n a g e m e n te f f e c t i v e n e s s k e y w o r d s ：d a t am i n i n g ；a c h i e v e m e n t ；a p r i o r i ；a p r i o r i t i d 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 汉西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密d ，使用本授权书。 ( 请在以上方框内打“1 j ”) 指导老师签名： 豸叮 日期： 砂h 厂- f z 坩蜂 奄嚣 吖 关 _ 名 堑 矿 作 肌 划 蝴 扔 日 位 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： 1 在a p r i o r i t i d 算法基础上做了三方面改进：根据频繁项集的性质，在连接步前， 先缩减频繁项目集的规模；根据求置信度的公式，减少需要考虑的规则数；基于本文 研究课题是影响学生成绩的因素，所以只考虑前件或后件为成绩的关联规则； 2 采用j a v a 语言，按照优化的算法思路编程实现，采用g u i 界面，方便交互和 数据挖掘结果的可解释性；定性地分析了改进算法的时间复杂性，得出的结论是新算 法比a p r i o r i t i d 算法在连接和剪枝步缩短了时间，且缩减了k 1 维频繁项集的规模，从 而提高了算法收敛速度。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰 写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确说明。 本人完全了解违反上述声明所引起的一切法律责任将由本人承担。 学位论文作者签名： 聪译 日期： p o rf f 西南交通大学硕士研究生学位论文第1 页 1 1 本论文的研究意义 第1 章绪论 数据挖掘技术是在“数据爆炸但知识贫乏的现象下应运而生的，现在数据挖掘 技术在商业应用中已经可以投入使用，因为对这种技术进行支持的三种基础技术已经 发展成熟，它们是海量数据搜集，多处理器计算机和数据挖掘算法。目前，数据挖掘 技术在商业、金融业、保险、市场营销等方面都得到了广泛的应用1 4 】，而在教育领域应 用相对较少。 近年来随着高校不断扩张，学校人数大幅度增加，给高校学生管理和教学工作带 来了严峻的考验，传统的教学管理手段已经逐渐不能适应社会的发展了。目前，高校 对学生信息和成绩等数据的处理一般还停留在数据统计分析、查询，备份阶段。远远 不能发现隐藏在数据背后的信息，更不能提供决策参考和依据。 教学工作是高校的核心工作。而成绩不仅可以评估教学质量，同时能够评价学生 的学习效果。通过对学生成绩运用数据挖掘技术，发掘学生成绩背后的隐含的有价值 的信息，为引导各校领导重视教学工作，注意改善教学条件，加强教学管理，深化教 学改革，努力提高教学质量提供了重要的依据。 1 2 数据挖掘技术的国内外研究现状 1 2 1 国外现状 数据挖掘技术发展日益成熟。数据库、人工智能、信息处理、知识工程等领域的 国际学术刊物也纷纷开辟了k d d ( k n o w l e d g ea n dd a t ae n g i n e e r i n g ) 专题或专刊 1 。 i e e e 的k d d 会刊领先在1 9 9 3 年出版了k d d 技术专刊，所发表的5 篇论文代表了当 时) d 研究的最新成果和动态。 在经过十几年的技术发展之后，国外在数据挖掘技术上取得了丰富的经验。从总 体上，国外在数据挖掘领域中的研究内容十分广泛，已经取得了明显的成果，如h a r t ， j a n df u ，y ( 1 9 9 5 ) 等人对于定量关联规则以及其他种类的关联规则的发现研究， m e h t a ，m ( 1 9 9 6 ) 等人针对大型数据库快速分类算法的研究，o w e n ，a b ( 1 9 9 9 ) 对分 类与回归的管状邻域研究， f r i e d m a n ， j h ( 1 9 9 7 ) 对最近邻分类方法的改进，以及对 聚类规则的研究、数据泛化、简约和特征提取研究等不但在研究方面使各个学科的 经验向该领域集中，而且出现了大量的软件产品，在社会的各个领域的应用也取得了 丰硕的成果，国际上比较有影响的数据挖掘系统有s a s 公司的e n t e r p r i s e m i n e r ，i b m 西南交通大学硕士研究生学位论文第2 页 公司的i n t e l l i g e n t m 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 e s t u d i o ，加拿大s i m o n f r a s e r 大学的d b m i n e r 等。此外，在s q ls e r v e r2 0 0 5 中设计商业智能应用程序【5 1 ，可以使用微软的数据挖掘标准解决如今的商业问题。 1 2 2 国内现状 数据挖掘技术已经被越来越多的国内企业管理者所认识，其中包括电信、金融、 零售、保险等行业的决策者。未来数据挖掘技术在国内将会得到更加广泛的研究和应 用【2 】o 数据挖掘仍然面临着许多问题和挑战：如数据挖掘的效率有待提高，尤其是超大 规模数据集中数据挖掘的效率；开发适应多数据类型、容噪的挖掘方法，以解决异构 的数据集的数据挖掘问题；动态数据和知识的数据挖掘；网络与分布式环境下的数据 挖掘等；另外，近年来多媒体数据库发展很快，面向多媒体数据库的挖掘技术和软件 今后将成为研究开发的要点。 在国内，数据挖掘的研究和应用受到了学术界、商业界和政府部门的越来越多的 重视，但是基本上还是以学术研究为主，实际应用还处于起步阶段。1 9 9 3 年国家自然 科学基金首次支持对该领域的研究项目。之后许多单位也开始了理论研究和应用实践， 例如，福建省建立了空间数据挖掘与信息共享教育部重点实验室，主要研究地球空间 数据从采集、处理、存储、和发布形成信息流的全过程的系统集成研究1 6 j 。 1 3 数据挖掘技术在教育领域的应用 在教育领域，数据挖掘是一种崭新的教育信息处理技术，目前的研究和应用不够 广泛，没有达到电信、零售等行业的规模【7 】。随着数据挖掘技术的成熟及应用领域的不 断扩展，不少高校研究人员已开始研究将数据挖掘技术应用于学生信息管理、高校的 教学管理、教学质量评估、合理安排课程、招生就业及考试系统中，对提高学校教学 管理水平起到了很好的指导作用。 数据挖掘应用在教育领域的主要作用是对教育数据库中的大量数据进行抽取、转 换、分析和其他模型化处理，从中提取辅助教育决策的关键性数据。数据挖掘更主要 是为教育决策提供真正有价值的信息，进而获得更好的教育效益。但很多学校面临的 一个共同问题是；学校数据量非常大，而管理者获得的有价值的信息却很少，因此需要 从大量的教育数据中经过深层分析，获得有利于教育决策、促进教育发展的价值信息【8 j 。 1 4 本论文的主要内容及结构安排 近年随着信息技术飞速发展，在各个领域包括商贸、政府的电子政务、大规模工 业生产过程中的智能监控和诊断及科学技术等，产生了海量数据。在这种情况下，依 西南交通大学硕士研究生学位论文第3 页 靠传统方法对这些数据进行统计分析，已经不能满足要求。这时数据挖掘技术的产生， 为解决这一问题提供了技术基础。数据挖掘技术正是从海量数据中发现有用的知识和 信息的一种技术。关联规则挖掘是数据挖掘的一个重要分支，主要研究数据项之间有 价值的相互关系。 本文从数据挖掘的国内外研究和应用现状、数据挖掘技术在教育领域的应用开始， 接着介绍了数据挖掘的技术综述，包括数据挖掘的发展历史、概念和经常用到的相关 技术。然后就论文核心内容利用关联规则数据挖掘技术分析学生成绩的理论基础 关联规则进行详细论述，不仅阐明了关联规则的研究现状、基本概念、原理、关联规 则数据挖掘的种类、不同关联规则算法的比较，而且详细介绍了论文使用的a p r i o r i t i d 改进算法的设计和实现，分析了a p r i o r i t i d 改进算法的时间复杂性。最后利用该算法对 学生成绩挖掘得到关联规则。这一部分依据数据挖掘流程，从数据采集、预处理到利 用算法进行关联规则挖掘、关联规则的结果分析，都进行了详细的介绍。 西南交通大学硕士研究生学位论文第4 页 第2 章数据挖掘技术综述 2 1 数据挖掘的发展历史 数据挖掘是一个逐渐演变的过程，电子数据处理的初期，人们就试图通过某些方 法来实现自动决策支持，当时机器学习成为人们关心的焦点。机器学习的过程就是将 一些已知的并已被成功解决的问题作为范例输入计算机，机器通过学习这些范例总结 并生成相应的规则，这些规则具有通用性，使用它们可以解决某一类的问题。随后， 随着神经网络技术的形成和发展，人们的注意力转向知识工程，知识工程不同于机器 学习那样给计算机输入范例，让它生成出规则，而是直接给计算机输入己被代码化的 规则，计算机是通过使用这些规则来解决某些问题。专家系统就是这种方法所得到的 成果，但它有投资大、效果不甚理想等不足。8 0 年代人们又在新的神经网络理论的指 导下，重新回到机器学习的方法上，并将其成果应用于处理大型商业数据库。8 0 年代 末，一个新的术语一数据库中的知识发现( k d d ) - - 出现，人们接受了这个术语，并用 k d d 来描述整个数据挖掘的过程，包括最开始的制定业务目标到最终的结果分析，而 数据挖掘( d m ) 贝j j 是描述使用挖掘算法进行数据挖掘的子过程。 这些技术是随着时间顺序先后出现的，但并不是后来的技术代替之前的技术，而 是不同的技术有不同的应用领域。 2 2 数据挖掘的概念 一 所谓数据挖掘，简单地概括就是从历史数据集中发现隐含模式，并且应用这些模 式进行预测。具体地说，数据挖掘的定义是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的、但又潜在有用的信息和知识 的过程。该定义概括了数据挖掘的数据源的五个特点和挖掘得到的信息的三个特点。 数据挖掘与传统数据分析( 如查询、报表、联机应用分析) 的本质区别是数据挖掘是 在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息是未知、有 效和可用的。未知是指该信息是预先未曾预料到的，即数据挖掘是要发现那些不能靠 直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎意料 就可能越有价值。有效性要求挖掘前要对数据源进行仔细检查，只有保证数据源的有 效性，才能保证挖掘出来的信息的有效性。可用性，即这些信息或知识对于所讨论的 业务或研究领域是有效的、是有实用价值和可实现的。 西南交通大学硕士研究生学位论文第5 页 2 3 数据挖掘的相关技术 2 3 1 决策树 决策树【9 1 对于分类和预测是强有力的常用工具。基于树的方法之所以有吸引力，很 大程度上是因为决策树代表着规则。规则可以很容易表达，以便我们能够理解，也能 在数据存取语言中表示，比如用s q l 在特定类别中检索记录。决策树对探测数据也很 有用，可以了解从大量的候选输入变量到一个目标变量的关系。决策树把数据探查和 建模结合在起，即使建立最终模型时使用一些其他技术，它也是建模过程最强有力 的第一个步骤。 2 3 2 人工神经网络 在许多数据挖掘和决策支持应用中，由于有公认的轨迹记录，人工神经网络【1 0 】 已经成为一种普遍采用的方法。神经网络是一种可以容易地应用于预测、分类和聚类 的强有力的多用途工具。从预测金融业的时间序列到医学诊断情形，从识别有价值的 客户到识别欺诈信用卡交易，从识别写在支票上的数字到预测发动机的故障率，等等， 神经网络被广泛应用到各行各业。 2 3 3 关联规则 关联规则挖掘【1 1 】是发现大量数据中项集之间有趣的关联或相关联系。关联规则形 式简洁、易于解释和理解，并可以有效地捕捉数据间的重要关系。尽管关联规则挖掘 起源于商业上对购物篮进行分析的问题，但是随着研究的不断深入，其基本模型在多 角度得到了扩充。关联规则挖掘技术的应用领域包括：商业与金融、电子商务、网站 设计、通信和互联网等。 2 3 4 链接分析 链接分析【1 2 】主要研究的问题有：哪些网站与其他哪些网站链接? 谁用电话呼叫 谁? 哪些医师为哪些病人开哪些药? 这些关系在数据中都是可见的，并且它们都包含 着大多数数据挖掘技术不能直接利用的丰富信息。在联系越来越多的世界中，理解相 互关系和联系是很关键的，链接分析就是定位于这一需求的数据挖掘技术。 链接分析是以图论的数学分支为基础的。它并不适用于所有类型的数据，也不能 解决所有类型的问题，但在可以应用的情况中，它常常会产生很富洞察力且可操作的 西南交通大学硕士研究生学位论文第6 页 结果。如在万维网上通过分析页面直接的链接识别权威信息源等。 2 3 5 遗传算法 像神经网络一样，遗传算法【1 3 1 也是以模仿生物过程为基础。在数百万年之间，进 化和自然选择已经造就了对环境高度适应的特殊物种。通过将一代最适应的生物个体 中的遗传物质传播给下一代，进化论能够优化下一代个体的适应度。遗传算法将相同 的观念应用到一些其结果能表示为最优的“个体”，目标是最大化个体的“适应度”的 问题。 西南交通大学硕士研究生学位论文第7 页 第3 章关联规则数据挖掘算法的分析 3 1 关联规则挖掘研究综述 关联规则挖掘是在数据挖掘领域中较早提出的一个研究方向，目前该领域的新算 法、新应用层出不穷，相关问题定义和背景也不尽相刚1 4 】。关联规则主要用来分析数 据库中不同属性间有价值的相互依存关系，目前的研究主要集中在基本关联规则挖掘、 复杂类型关联规则挖掘、针对关联规则评价的研究、并行挖掘算法和增量挖掘算法等 几个方耐d j 。 1 基本关联规则挖掘 基本关联规则挖掘算法是a p r i o r i 算法，它采用分层搜索，依赖频繁数据项集的产 生。有人提出了更为高效的d h p ( d i r e c th a s h i n ga n dp r u n e ) 算法，它基于散列技术和事 务压缩技术，缩减了2 候选项集的规模和扫描事务量。为了更有效地处理大规模数据 集，有人提出了p a r t i t i o n 算法，它主要基于“分而治之”的思路。 上面这三种算法都是采用分层搜索的基本框架，分层搜索的缺点是需要多次扫描数据 库，形成多个候选数据项集，算法的执行效率较低，因此不少学者提出了新的频繁数 据项产生方法。如，f p - g r o w t h ( f r e q u e n t p a t t e r ng r o w t ha l g o r i t h m ) 算法，它的最大优点 是只需扫描一次数据库，但要把数据库事务压缩到一棵频繁模式树中，又增加了对存 储空间的要求，所以如果能够折衷时间和空间开销，可以得到比较高效的算法。 2 复杂类型关联规则挖掘 复杂类型关联规则是基于基本关联规则的变体，如多概念层关联规则、定量关联 规则和序列模式等。 多概念层关联规则【1 6 】是概化关联规则和多层关联规则的统称。在底层难以找出强 关联规则的多稀疏数据空间，利用较高层次的抽象概念往往可以找出有意义的关联规 则，同时又可以满足不同用户可能对不同概念层次空间上知识的兴趣感。正是基于这 样的原因提出了多概念层关联规则。 一般的布尔型关联规则无法处理具有连续属性值的属性变量，有学者就提出了定 量属性离散化信息丢失检测方法。 序列模式的主要任务是考虑某模式在其他模式出现前后一段时间内关联出现的频 率。 3 针对关联规则评价的研究 什么是有意义的关联规则? 这本身就是一个很主观的问题。所以如何构造关联规 则的兴趣度指标也是关联规则挖掘研究的一个重要研究内容。利用支持度和置信度来 评价有意义关联规则的方式受到广泛质疑。因为存在两个缺陷：第一个，考虑到算法 西南交通大学硕士研究生学位论文第8 页 实施的效率，它一般不挖掘那些支持度低而置信度高的规则；其次基本的数据项集定 义无法发现负项集。 4 并行挖掘算法 目前的大部分关联规则挖掘算法是串行的，而利用多处理器对分布数据进行并行 挖掘1 17 1 ，也逐渐受到人们的重视。 5 增量挖掘算法 增量挖掘算法f 1 8 】包括事务增量和参数增量两种。当数据库中的事务记录不断刷新， 新的数据不断被写入而旧的数据可能会被删除时，这种数据环境是事务增量。参数增 量是指在人机不断交互过程中，往往需要不断调整支持度、置信度等参数来获取满意 的挖掘结果。有学者在d h p 算法基础上提出一种快速更新算法f u p ( f a s tu p d a t e a l g o r i t h m ) ，有效减少了事务增量环境下候选数据项的规模，性能明显优于d h p 算法， 但只适用于事务增加的条件。 3 2 关联规则的基本概念 1 数据项与数据集 设i = f 。，f ： o l lf 。 是n 1 个不同项目的一个集合，每个( k = l ，2 ，m ) 称为 数据项( i t e m ) ，数据项的集合i 称为数据项集( i t e m s e t ) ，简称为项集，其元素个数称为 数据项集的长度，长度为k 的数据项集称为k 维数据项集，简称为k 项集( k i t e m s e t ) 。 2 事务 是数据项集i 上的一个子集，即t i ，每个事务均有个唯一的标识符t i d 与之相 联，不同事务的全体构成了全体事务集d ( 即事务数据库) 。 3 数据项集的支持度 设x c _ i 为数据项集，b 为事务集d 中包含x 的事务的数量，a 为事务集d 中包 含的所有事务的数量，即数据库中的记录个数。则数据项集x 的支持度( s u p p o r t ) 定义： r s u p p o r t ( x ) = =(31)a 项集x 的支持度s u p p o r t ( x ) 描述了项集x 的重要性。 4 最小支持度与频繁项集 最小支持度( m i n i m u ms u p p o r t ) 表示发现关联规则要求数据项必须满足的最小支 持门限值，记为m i ns u p ，它表示数据项集在统计意义下的最低重要性【1 9 】。只有满足最 小支持度的数据项集才有可能在关联规则中出现，支持度大于或等于最小支持度的数 据项集称为强项集，或频繁项集( l a r g ei t e m s e t ) ，反之，称为弱项集( s m a l li t e m s e t ) 。 5 候选频繁项集 定义：设4 ，彳2 ，以是r 1 个事件，如果对于任意k ( 1 k 玎) ，任意1 i 1 ( 收入) = 3 0 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 2 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层 次的；而在多层的关联规则中，对数据的多层已进行了充分的考虑。例如：h p 台式机 = c a n o n 打印机，是一个细节数据上的单层关联规则；台式机= c a n o n 打印机，是一 个较高层次和细节层次之间的多层关联规则。 3 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品，而在多 维的关联规则中，要处理的数据将会涉及多个维。换句话说，单维关联规则是处理单 个属性中的一些关系， 多维关联规则是处理各个属性之间的某些关系。如啤酒_ 尿布，这条规则只涉及 到用户购买的物品；性别= “男”- 职业= “经理”，这条规则就涉及到两个字段的信息， 是两个维上的一条关联规则。 3 5 常见的关联规则算法 3 5 1a i s 算法 a i s 算法【2 3 1 在扫描数据库的过程中，该算法同时产生候选项集并对其进行计数。 当读取一条记录后，算法从记录中寻找是否有前一次搜索后生成的频繁项集，所有这 样的频繁项集和该记录中的其他数据项通过扩展操作形成新的候选项集。一个很大的 缺陷，就是产生出了过多的小候选。 a i s 算法的问题在于它产生过多的被验证为小的候选，故浪费了很多时间去验证。 a i s 同样在第二次扫描中为太多的小候选项集计数但这种计数从第三次开始就急剧减 少。 3 5 2s e t m 算法 s e t m 算法【2 4 】希望用s q l 语句来计算频繁项集。与a i s 相似，s e t m 算法同样在 从数据库中读事务时产生候选项集它产生并计数a i s 算法产生的候选，但用s q l 的标 准j o i l l 操作来产生候选，s e t m 算法将候选产生与计数分开。它以线性结构保存候选 的副本及产生事务的编号t i d 。 西南交通大学硕士研究生学位论文第12 页 s e t m 算法的问题在于g 宰集的大小。c 。牛集一般比对应的g 集大s 倍，其中s 是候选的平均支持度。除非事务集很小，g 乖集必然要写到磁盘上且要排序两次，这 就引起s e t m 算法效率很低当数据库中事务数增加时，g 大小未变且事务及频繁项集 的平均大小不变，而q 拳线性增大因此，对有较多事务的数据库，s e t m 算法与其他 算法的差距很大。 3 5 3 a p r i o r i 系列算法 a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则问题， 其核心方法是基于频集理论的递推方法，即a p r i o r i 算法【2 3 1 。以后许多研究人员对原有 的算法进行优化，但核心思想不变，形成了a p r i o r i 系列算澍2 5 1 。 1 a p r i o r i 算法 算法的第一次遍历仅仅计算每个项目的具体值的数量，以确定频繁1 项集l 。随 后的遍历，第k 次遍历，包括两个阶段。首先，使用第( k - 1 ) 次遍历中找到的频繁项集厶一 和根据产生候选项集g 。接着扫描数据库，计算c 。中候选的支持度，从而生成频 繁项集厶。如此下去，直到不能找到维度更高的频繁项集为止。 2 a p r i o r i t i d 算法 a p r i o r i t i d 算法【2 6 】是a p r i o r i 算法的改进算法，旨在减少用于未来扫描的事务集的 大小。这个算法最大的特点是在每步( 除第一步外) 计算候选的支持度时，不需浏览整个 事务集d 。为了达到这个目的，在每次计算g 支持度的过程中，给不包含g 中的任何 项集的事务打上删除标记，在以后的扫描计数中不加考虑，这样计算候选项集支持度所 涉及的记录( 记为c 。木) 数目将小于事务数据库中实际的记录数，并且随着k 值的增大， 这一差值也不断增大，因而有效地提高了候选项集的计数速度，提高了整个算法的效率。 集合c 。木的每个成员的形式为( t i d ， x 。) ) ，其中每个x 。都是一个潜在的频繁k 项集， 在标识符为t i d 的事务中。对于k = l ，c 1 宰对应于数据库d ，对于k l ，用相应的算法 产生g 水。 3 a p r i o r i h y b r i d 算法 a p r i o r i h y b r i d 算法【2 4 】是a p r i o r i 算法和a p r i o r i t i d 算法的融合，在初始遍历中使用 a p r i o r i 算法，当在遍历末尾处集合g 能放进内存时就转换到a p r i o r i t i d 算法。 我们用下列的启发式来估计下一次遍历中g 是否能放进内存。在当前遍历的末 尾，我们有了c 。中的候选计数。我们从这一点估计，如果产生了c 。，那么它的大小尺 寸是多少。若这次遍历中c 小到可以放进内存，而且当前遍历中的大型候选比前次遍 历要少，那么我们就转换成a p r i o r i t i d 。通过性能测试，在几乎所有的情况下，算法 a p r i o r i h y b r i d 比a p r i o r i 和a p r i o r i t i d 要完成的更好。当转换出现的遍历是最后一次遍 历时，a p r i o r i h y b r i d 比a p r i o r i 要差一点：因为a p r i o r i h y b r i d 要承担转换的成本而没有 西南交通大学硕士研究生学位论文第13 页 收益。 4 d h p 算法 a p r i o r i 算法仍然有两个缺陷没有很好地解决： 第一个是初期的候选项集过于庞大g 尤其如此。 第二个是如果能不断减少数据库中所需扫描的事务数量，并缩短事务的长度，可 有效缩短频繁项集的生成时间。 d h p ( d i r e c th a s h i n ga n dp r u n e ) 算、法 2 7 1 针对a p r i o r i 算法的缺陷进行改进，所以d h p 有两个特点： 首先利用h a s h 技术更有效地生成候选项集。 然后，利用频繁数据项集的性质有效缩减扫描数据库大小。即如果某事务支持一 个长度为k + l 的频繁数据项集，则该事务至少含有k + 1 个长度为k 的频繁数据项集。 d h p 算法具体过程分三步： 首先生成l 频繁数据项集和2 候选数据项集的散列表日，。 其次完成下列任务： 1 ) 在散列表日。的基础上生成候选数据项集c 。 2 ) 在扫描数据库珥中统计候选数据项集，生成频繁数据项集厶。 3 ) 缩减数据库规模形成新的扫描数据库d m 。 4 ) 生成k + l 候选数据项集的散列表日m 。 第三步在功能上和第二步相同，但在实现方法上，它直接利用a p r i o r i 候选数据项 集的生成方法生成候选数据项集，而不采用散列表技术。之所以这么做是因为在算法 的后期c 。的规模缩减的很快，散列表技术已经不能显著地缩小c 。的规模了，反而会造 成额外的计算负担。因此，在d h p 循环的初期利用第二步产生频繁数据项集，当散列 表中大于或等于最小支持度r a i ns u p 的桶的数目超过一定的数值后d h p 利用a p r i o r i 方法产生频繁数据项集。 5 f a r m 算法 a p f i o r i 算法产生的c ：具有两个特点：c ：中所包含的候选2 一项集的数目lc ：i 由i 厶l 所决定，r ic 2i - l 厶ix ( il 1 | - 1 ) 2 。f a r m ( f a s ta s s o c i a t i o nr u l em i i l i n g ) 算法例据此判定 c ：的生成不是必需的，建立一个包含i 厶i ( jl 。卜1 ) 2 个元素的一维数组a ，代替哈希 树统计c ，中各候选2 项集的支持次数。为此，算法保证每个候选2 一项集对应且只对 应于唯一的数组元素。 f a r m 与a p r i o r i 相比有两点不同：第一是在循环2 中的处理，第二是对数据库的 处理。在循环2 中，f a r m 用一个一维数组代替a p r i o r i 中的哈希树来进行候选2 项集 的出现次数统计。从循环2 开始，f a r m 在每个循环利用d h p 算法中的缩减数据库大 小的技术，为后续循环生成越来越小的数据库以减少数据库扫描的开销。 西南交通大学硕士研究生学位论文第14 页 6 p a r t i t i o n 算法 基于划分的( p a r t i t i o n ) 算法1 2 9 1 先把数据库从逻辑上分成几个互不相交的块，每次 单独考虑一个分块并对它调用任意一种频繁项集的挖掘算法来生成所有的频繁项集， 然后把产生的频繁项集合并，用来生成全局频繁项集。然后扫描数据库来验证每个候 选项集是否是真正的频繁项集。这样只要扫描两次数据库，就可以找出频繁项集。第 一次扫描数据库是对数据库进行分块，对每一部分找出该部分的频繁项集，这些频繁 项集称为局部频繁项集。在第二次扫描数据库的时候，计算每个候选项集的实际支持 度，以确定全局频繁项集。 p a r t i t i o n 算法的改进之处便是要减少a p r i o r i 算法搜索数据库的开销，进而大大提 高了整体性能。但也存在如下问题： 首先，第一次扫描数据库所产生的频繁项集只能是分块中的频繁项集，并不一定 表示在整个数据库中也是频繁项集，因此可能产生过多的频繁项集，导致第二次扫描 数据库确定时效果不好。 其次，为避免频繁项集在不同分块中重复出现，在系统做挖掘之前需要先将数据 库排序，而排序的时间不容忽视。 3 5 4f p g r o w t h 算法 频繁模式增长( f r e q u e mp a t t e r ng r o w t h ， f p g r o w t h ) t 3 0 】【3 l 】是一种挖掘全部频繁项 集而不产生候选项集的方法。通过短频繁模式逐步增长的方式来得到更长的频繁模式， 无需产生候选项集，而且只需扫描两次数据库。第一次扫描生成频繁1 项集；第二次 扫描构造f p t r e e 。 f p g r o w t h 算法的主要思想是基于分治策略，即在第一次扫描数据库以后，将产生 的频繁项数据压缩到一棵频繁模式树中，又称之为f p t r e e ( f p 树) ，用模式树保留项集 的关联信息，然后对模式树产生频繁项集。当原始数据量很大的时候，也可结合划分 的方法，使得一棵f p 树能放入主存中。 模式树是一种自底向上方式的探索树，算法首先查找以某特定项结尾的频繁项集， 如，数据库中包含三个数据项a 、b 、c 。那么首先查找以c 结尾的频繁项集，接下来是 b ，最后是a 。由于每个事务都映射到模式树的一条路径，因此通过仅考察包含特定结 点( 如c ) 的路径，就可以发现以c 结尾的频繁项集。 3 5 5 h c s 。m i n e 算法 h c s m i n e 算法【3 2 】基于哈希链结构挖掘频繁模式，并动态构造链地址。算法针对数 据库中的频繁投影逐条进行扫描，每扫描一条就产生相应的项集并记录其支持数，对 西南交通大学硕士研究生学位论文第15 页 于新产生的项集，利用哈希函数计算其链地址。 所有链地址相同的项集构成一条链表，链表结点中的计数域为该结点中项集累计 出现的次数，各条链表头表结点的计数域为该链表中所有结点的计数之和。这样，在 频繁模式挖掘过程中，只需考虑那些头表结点中计数域大于等于最小支持数的结点， 从而节省挖掘时间。 3 6 各种关联规则算法的比较 表3 1 各种关联规则算法比较分析 分类算法特点 a i s 候选项集是在读入一个事务时产生的 s e t m 需 a p r i o r i 要 a p r i o r i t i d 立 生 a p r i o r i a p r i o r i h y b r i d 借助于上一步产生的频繁项集来产生候 候 选 系列算法f a r m 选项集 项 集 d h p p a r t i t i o n 不 用一种压缩的数据结构( f p t r e e ) 来存 国巨 响 储关联规则挖