（计算机应用技术专业论文）数据挖掘中关联规则的研究与应用(1).pdf

分类号： u d c ： 密级 编号 数据挖掘中关联规则的研究与应用 r e s e a r c ha n da p p l i c a t i o n0 na s s o c i a t i o nr u l e s b a s e db a t am i n l n g 学位授予单位及代码：量查墨王态堂 i ! q l 竖2 学科专业名称及代码：让星扭虐旦蕉丕l q ! ! ! q 塑 研究方向：盐簋扭置篚撞剑 指导教师：奎煎熬塑 论文起止时问：呈业7 1 1 - - 2 0 q 旦2 申请学位级别： 亟圭 研究生：塞毯生 摘要 信息技术的迅猛发展使得各个领域的数据量激增，数据挖掘足一种新的认识数 据、理解数据的智能手段，关联规则足数据挖掘中最重要的一种。 本文在研究关联规则挖掘技术的基础上，丌展了基于关联规数据的分析和挖掘研 究。首先，针对其中的缺点和不足，提出了一种匹配度方法用以取代置信度，用匹配 度方法生成的规则不仅具有较高的相关性，而且减少了冗余规则的生成。再次，在分 析经典a p r i o r i 算法的基础上，提出了一种有效的基于矩阵的a p r i o r i 的改进算法。 该算法应用了矩阵的思想，只需对数掘库扫描一次，即可得到频繁项集，大大提高了 算法的效率。 最后，结合学生成绩数扔；的特点将数据挖掘技术和关联规则算法运用到学工管理 系统中：提出学生培养模型和优秀课程问关系模型的概念并对其进行了求解，以学生 的信息为数掘源，运用改进的a p r i o r i 算法实现了上述目标。 关键词：关联规则频繁项集a p ri o r i 算法 a b s t r a c t t h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g yl e a d sa ni n c r e d i b l er o c k e ti na l l k i n d so fd a t a d a t am i n i n gp r o v i d e sp e o p l ean e wi n t e l l i g e n ta p p r o a c ht ou n d e r s t a n dd a t a a s s o c i a t i o nr u l ei sa ni m p o r t a n tp a t t e r ni nd a t am i n i n g b a s e do nt h er e s e a r c ho ft h ea l g o r i t h mo nm i n i n ga s s o c i a t i o nr u l e ，t h ed i s s c r e t a t i o n m a k e sr e s e a r c ho nt h ea n a l y s i so fs t u d e n t s m a r k d a t a f i r s t l y , i nv i e wo ft h es h o r t c o m i n g s a n dl a c k ，s u p p o r tt h ea t c h i n g d e g r e em e t h o dt or e p l a c et h ea t c h i n g d e g r e eo fc o n f i d e n c e ， t h er u l e sg e n e r a t e db yt h em a t c h i n g d e g r e em e t h o dn o to n l yh a v eh i g hr e l e v a n c eo nb e f o r e a n da f t e r , b u ta l s or e d u c et h eg e n e r a t i o no fr e d u n d a n tr u l e s s e c o n d l y , o nt h eb a s i so ft h e r e s e a r c ho fa p r i o r ia l g o r i t h m ，p r e s e n t sa ni m p r o v e dm a t r i x b a s e da p r i o r ia l g o r i t h mt o i m p r o v et h ep e r f o r m a n c eo fa s s o c i a t i o nr u l ea l g o r i t h m t h i sa l g o r i t h mu s e st h et h o u g h t so f m a t r i x , j u s tn e e d ss c a nt h ed a t a b a s eo n l yo n et i m et og e tt h ef r e q u e n ti t e m s e t ，i ti n c r e a s et h e e f f i c i e n c yo fa l g o r i t h m f i n a l l y , c o m b i n e dt h ec h a r a c t e r i s t i c so fs t u d e n t s d a t a ，t h et e c h n o l o g yo fd a t am i n i n g a n da p r i o r ia l g o r i t h m sa r ea p p l i e di ns t u d e n tm a n a g e m e n ts y s t e m t h ec o n c e p to fs t u d e n t f o s t e r e d m o d e la n dm o d e lo fr e l a t i o n s h i pb e t w e e ne x c e l l e n tc o u r s e sa r ep r o p o s e da n d s t u d i e d w i t ht h ei n f o r m a t i o nd a t as o u r c e so fs t u d e n t s ，m a k et h eu s eo fi m p r o v e da p r i o r i a l g o r i t h mt oa c h i e v et h ea b o v eg o a l s k e yw o r d s ：a s s o c i a t i o nr u l ef r e q u e n ti t e m s e t sa p r i o r ia l g o r i t h m 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，数据挖掘中关联规则的研究与应 用是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中已经 注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品 成果。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。 作者签名：鏖茏焦 年一月一日 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版 权使用规定 ，同意长春理工大学保留并向中国科学信息研究所、中国优秀博硕 士学位论文全文数据库和c n k i 系列数据库及其它国家有关部门或机构送交学 位论文的复印件和电子版，允许论文被查阅和借阅。本人授权长春理工大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印 或扫描等复制手段保存和汇编学位论文。 作者签名：壅盘堑 年一月一日 指导导师签名：砻曩 年一月一日 第一章绪论弟一早硒下匕 1 1 数据挖掘技术研究背景及研究意义 随着数据库技术的成熟和数据应用的普及，人类积累的数据量证在以指数速度迅 速增长。进入九十年代，伴随着因特网( i n t e r n e t ) 的出现和发展，将整个世界联成一 个小小的地球村，人们可以跨越时空地在网上交换数据信息和协同工作。这样，展现 在人们面前的已不是局限于本部门，本单位和本行业的庞大数据库，而是浩瀚无垠的 信息海洋，数据洪水正向人们滚滚涌来。激增的数据背后隐藏着许多重要的信息，人 们希望能够对其进行更高层次的分析，以便更好地利用这些数据。目自 的数据库系统 可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和舰 则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段， 导致了“信息爆炸但知识贫乏”的现级。于是，个新的挑战被提了出来：在这被称 之为信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何彳能不被信息的 汪洋大海所淹没，从中及时发现有用的知识，提高信息利用率呢? 要想使数据真萨成 为一个公司的资源，只有充分利用它为公司自身的业务决策和战略发展服务彳行，否 则大量的数据可能成为包袱，甚至成为垃圾。因此，面对“人们被数掘淹没，人们却 饥饿于知识”的挑战，从数据库中发现知识( 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 ) 及 其核心技术一数据挖掘( d a t am in in g ) 便应运而生，并得以蓬勃发展，越柬越显示出 其强人的生命力。 数据挖掘( d m ) 就是从大量的、不完令的、有噪声的、模糊的、随机的实际应用数 据中，提耳义隐含在其中的、人们事先不知道的、但又是潜在有朋的信息和知识的过程 。数铡挖掘技术的应用领域十分广阔，它可以从关系数据库、数据仓库、文本和多 媒体数据库、事务数据库和互联网等各种数据源上设法获取渚如分类模型、聚类模型、 同归模型、关联模型和时间序列模型等多种知谚 模型。可以晓，有数掘积累的地方， 就有数侧挖掘技术的用武之地。日i i ，j ，数拆：挖掘技术在货篮数就分析、会融风险预测、 产品质量分析、电信、分子生物学、琏因工程研究，i n t e r n e t 站点访j 、u j 模式发现以及 信息搜索等领域得到了广泛的应用。数据挖掘技术被认为足数捌库和人工智能领域中 研究、丌发和j 衄用最活跃的分支之，汇聚了f ：州领域的研究嚣，尤其是数据库技术、 人j 。j ：智能技术、数理统计、可视化技术、并行计算等力嘶的学行和工稃技术人员，投 身剑数抛挖捌这一新兴的研究领域，形成了新的技术热，i 。 1 2 数据挖掘研究现状及存在的问题 1 2 1 数据挖掘的发展历史及国内外研究现状 数据挖掘是一个逐渐演变的过程，电子数据处理的初期，人们就试图通过某些方 法束实现自动决策支持，当时机器学习成为人们关心的焦点。机器学习的过程就是将 一些己知的并己被成功解决的问题作为范例输入计算机，机器通过学习这些范例总结 并，主成相应的规则，这些规则具有通用性，使用它们可以解决某一类的问题的。随后， 随着神经网络技术的形成和发展，人们的注意力转向知识工程，知识工程不同于机器 学习那样给计算机输入范例，让它生成出规则，而是直接给计算机输入已被代码化的 规则，计算机是通过使用这些规则柬解决某些问题。专家系统就是这种方法所得到的 成果，但它有投资大、效果不甚理想等不足。6 0 年代人们又在新的神经【) 6 9 络理论的指 导下，重新回到机器学习的方法上，并将其成果应用于处理大型商业数拆：库。8 0 年代 末，一个新的术语一数据库中的知识发现( k d d ) 出现，人们接受了这个术语，并用k d d 来描述整个数据发掘的过程，包括最丌始的制定业务目标到最终的结果分析，而数据 挖掘( d m ) 则用来描述使用挖掘算法进行数据挖掘的子过程。 从数据库中发现知识( k d d ) 一词首次出现在1 9 8 9 年举行的第十一届国际联合人工 智能学术会议上。到目前为止，由美国人工智能协会主办的k d d 国际研讨会已经召，l ： 了多次，规模由原束的专题讨论会发展剑国际学术大会，研究霞点也逐渐从发现方法 转向系统应用，注重多种发现策略和技术的集成，以及多种学科之问的相互渗透。 i e e e ( i n s t i t u t eo fe l e c t r i c a la n de l e c t r o n i ce n g i n e e r s ) ，a c m ( a s s o c i a t i o no f c o m p u t i n gm a c h i n e r y ) 等其它学会电纷纷把数据挖掘与知识发现( d a t am i n i n ga n d k n o w l e d g ed i s c o v e r y ，d m k d ) 列为会议议题或出版专刊，成为! _ 6 ，j - 困际上的一个研究 热点。目前对关系数据库和事务数据库进行数抛挖掘和知识发现的研究已经取得了一 定的进展，最有影响的发现算法有：加拿大s i m o nf r a s e r 大学j h a n 教授的概念树 提升算法、i b m 的r a g r a w a l 的关联算法、澳人利亚的j r q u i n l a n 教授的分类算法、 密两根州立大学e r i c kg o o d m a n 的遗传算法等。i b m ，g t e ，s a s ，m i c r o s o f t ，s i l j c o n g r a p h i c s ，i n t e g r a ls o l u t i o n s ，t h i n k in gm a c h i n e s ，d a t a m in d ，u r b a ns c i e n c e ， a b t e c h ，u n i c al e c h n o l o g i e s 等公司，相继j 发啦一些实用的k d d 商、啦系统和原型系 统，如市场分析用b e h a v i o r s c a n ，e x p l o r e r ，m i ) t ( m a n a g e m e n td is c o v e r yt 0 0 1 ) ，会 融投资领域的s t o c ks e l e c t o r ，a i ( a u t o m a t e di n v e s t o r ) ，欺准预警片j 的f a l e o n ， f a s ，c l o n e d e t e c t o r 等。 因外牛 1 比，困内对d m k i ) 的研究稍晚，没仃形成整体力鞋。目f j ，j ，h 内从拜数 掘挖捌研究的人员主要集中舀：人学，也订部分 ：研究所或公i d 。j 行涉及的研究领域7 艮 多，般集l f lj ：算法的研究、数掘挖赫f 的实际一川以及仃父数圳挖捌州沦力l f i f 的研究。 i 西进行的人多数研究项 l 魁政府资助进行的，纽l 州咏f 然科。乎琏金、黼：n 1 划、 “九五”计划等，但至今还没有关于国内数据挖掘产品的报道。国内企业运用数掘挖 掘技术束协助业务活动的应用还处于起步阶段。成功应用的案例还比较少，这对数据 挖掘技术和工具的研究人员以及丌发商来 兑，我国是一个有巨大潜力的市场。 1 2 2 数据挖掘技术在教育领域中应用的研究现状及意义 数据挖掘技术在商业、会融业以及企业的生产、市场营销等方面部得到了广泛的 应用，而在教育领域应用相对较少，高校中对教师信息、学生信息、成绩等数据的处 理还一般停留在简单的数据的备份和查询阶段。这些教学管理系统，多半是以台帐管 理为主的0 t l p 系统，缺乏综合分析，辅助决策的能力；并且对其历史积累的海量信 息中隐含知识的利用无能为力。 近年来随着高校的不断扩招，学生人数大幅度增加，给高校学生管理、教学工作 带来了严峻考验，传统的教学管理手段己逐渐不能适应社会的发展。随着数据挖掘技 术的成熟及应用领域的不断扩展，不少高校研究人员已开始研究将数据挖掘技术应用 于高校的教学、管理中，例如，将数据挖掘技术应用于课章教学评价中，通过找出课 堂效果与教师职称、年龄等因素之f h j 的内在联系，以有效地指导教学工作：通过对毕 业生数据库进行数据挖掘研究，得到了有益于高等学校教学管理决策及毕业生就业指 导的挖掘结果：在制定人事激励制度时，为了针对不同类别的教师建立有针对性的制 度，叮以应用分类和关联规则方法挖掘隐含的规则，从而为高校管理决策提供科学依 据等等。总之，将数据挖掘技术戍用于学校的教学、管理中，对提高学校教学管理水 平起到了很好的指导作用，而且采用先进技术对考试过程和教学环节中产生的数据进 行多层次、多角度的分析，利用分析结果辅助教学决策是保证教学质量、提高学生素 质的必然要求。 1 2 3 数据挖掘技术存在问题 1 、数掘类型不同 绝大多数数据库是关系型的，因此在关系数据库【：有效地执行数据采掘是至关重 要的。但是在不同应用领域中存在各种数掘艉l 数掘库，而h 经常包含复杂的数据类型， 例如结构数据、复杂对象、事务数据、历史数据等。i ”f 数掘类型的多样性和小l r d 的 数据采掘目标，一个数据采掘系统不可能处理各种数铽。凼此针对特定的数据类型， 需要建屯特定的数抛采捌系统。 2 、数掂的动态性及数扔 缺陷 现。实数铡库通常足庞大、动念、不充令、4 i 准确、7 c 余和稀疏的，这给知谚 发现 系统提出了以：多难题。数引胯f f l 数抛的小断变化造j 戊定丽发现的知谚5 很快过时，数掘 的小准确f l - f 史知i j ! 挖巅i i 过氍i j , ，蔚要哑强的领域知谚 卡l lr 卫彩的抽样数据，f i i j 时导敛发现结 粜n 勺个i i 确；小充全数据他括缺少t n 个人址采的槭什：仇或缺少火系的字段：重复f 蜕 3 的信息称为冗余信息，为避免将用广毫无意义的函数发现作为知议发现的结果，系统 必须了解数掘库的固有依赖。另外数捌的稀疏性和不断增加的数据量增加了知识发现 的难度。 3 、挖掘算法和产生规则的有效性问题 海量数据库通常有上百个属性和袁及数百万个元组，g b 量级数据库已不鲜见，t b 量级数据库已经出现，高维大型数据库不仅增大了搜索空l 日j ，也增加了发现错误模式 的可能性。 因此必须利用领域知识降低维数，除去无关数据，从而提高算法效率。从一个大 型数据库中抽取知识的算法必须高效、可测量，即数据采掘算法的运行时间必须可预 测且可接受，同时应保证所得知识的合理性。 4 、交互性用户界面 数据采掘的结果应准确地描述数据采撅的要求，并易于表达。从不同的角度考察 发现的知识，并以不同形式表示，用商层次语言和图形界面表示数扼；采掘要求和结果。 目前许多知识发现系统和工具缺乏与用户的交互，难以有效利用领域知识，对此可以 利用贝叶斯方法和演绎数据库本身的演绎能力发现知识。 5 、数据源不同的问题 局域网、广域网以及i n t e r n e t 网将多个数据源联成一个大型分布、异构的数据 库，从包含不同语义的格式化和非格式化数据中挖掘知识是对数掘挖掘的一个挑战。 数掘采掘可揭示大型异构数据库中存在的普通查询不能发现的知i ： 。数据库的巨大规 模、广泛分布及数据采掘方法的计算复杂性，要求建立并行分和的数据采掘。 6 、私有性和安全性问题 数据采掘能从不同角度、不同抽象层卜看待数据，将影响到数据采掘的私有性和 安金性。通过研究数据采掘导致的数掘推法侵入，造成信息泄露。 1 3 论文的研究内容及结构 论文的t 要研究内容是：基于支持度一置信度的框架柬生成天联规则和a p r i o r i 算法的诸多不足，本文从两个方面n j 提高关联规则挖掘的价值性，并f j l 在此犟础l ：提 出了基r 一种新的框架( 支持度一匹配度的框架) 来下利用一种改进的关联舰! j ! i j 挖掘 算法( a p r i o ri m e ) 生成天联规则。i f 细内容如一f ： ( 1 ) 分析在支持度一置信度框架的衔鼍标准f 生成关联规则小足，并将支持度一匹配 度的框架和支持度一置信度丰f f 架做对比分析，试验证明吞：新框架下生成姚则比 框架蜓好。 ( 2 ) 分析火联规则中，卜成频集的绐媳锋法( a p t i o f i 算法) 的f ；足，提出f ll 的改进 的锌法( a p r i o r i m e ) ，它 ：要aa p r i o r j 算法旌础i ：从更少i 0 次数和使内仃 j i ：1 ；i i 适- f t 入于改进。通过戈m w j 放引米验西e 改进算法的- ：矗效，肚和t 叮i j t t ；。 ( 3 ) 将数据挖掘技术和关联规则算法运用到学工管理系统中，从而为教学部门提供 决策支持信息，促使更好地丌腱教学工作，提高教学质量。最后以学生相关信 息为数据源，基于数据挖掘技术运用在新的框架下自己改进的算法实现了上述 目标。 本文各章的主要内容如下： 第一章绪论。主要介绍了本论文的研究背景和研究意义，综述了数据挖掘的理 论渊源、发展现状，以及国内外数据挖掘的发展情况。 第二章数据挖掘技术。主要介绍数据挖掘的基本知识，包括数据挖掘的过程、 数据挖掘的任务、数据挖掘的分类以及数据挖掘的常用技术和方法。 第三章数据挖掘中关联规则的衡量标准。主要介绍了关联规则的支持度一匹配度 的框架，并提出了一种新的支持度一冒信度框架。 第四章基于a p r i o r i 算法的改进。主要对关联规则挖掘中的典型算法a p r i o r i 算法的介绍以及一些基于此算法的改进算法，并且从减少扫描数据库的次数角度提出 一种改进的算法a p r i o r i m e 。 第血章关联规则在学工管理中的应用。将数据挖掘技术和关联规则算法运用到 学工管理系统中，从而为教学部门提供决策支持信息，促使更好地丌展教学工作，提 高教学质量。 第六章结束语。主要总结了在论义研究阶段的工作，论文的创新点。 最后是致谢和参考文献。 1 4 本章小结 本章主要介绍了数据挖掘技术研究背景以及它的研究意义，从多方面分析了目前 数据挖掘技术的在国外内的发展现状和存在的主要缺陷，并以数据挖掘技术在教育行 业的应用说明了数据挖掘技术的重要性，最后介绍了论文的主要研究内容和论文结 构。 2 1 数据挖掘与知识发现 第二章数据挖掘技术 利用数据库管理系统( d b m s ) 可以对数据库中的数据进行有效的存取，但随着数 据库管理系统的广泛应用，部门业务不断拓展，数据库中存储的数据量急剧增大，并 且趋f 分散，传统的d b m s 尽管提供了比较完善的存取和查询功能，但不能满足人们 对大量数据进行知识抽取、发现数据l 日j 隐藏的依赖关系，从而为决策提供科学支持的 需要。数据挖掘和知识发现币是在这种情况下产生发展的一种新型数据分析技术。知 识发现又称k d 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 ) ，是从大量数据提取可信的、新 颖的、有效的并能被人们理解的模式处理过程哺。 数据挖掘是k d d 最关键的步骤，也是技术难点所在，通常情况下可不加区别地使 用二者。数据挖掘旨在能从大型数据库f t l 提取隐藏的预测性信息，它能发掘数据问潜 在的模式，找出企业经营者可能忽视的信息，以易于理解的形式反映给用户，并为企 业作出日订瞻的、基于知识的决策参考意见。目前困际上在该领域的研究相当活跃，无 论在理论上，还是实用技术上都取得了喜人的成果，同时也丌发出了各种专用或通用 的数据挖掘软件。 数据挖掘所能发现的知识有如下几种：广义型知谚：，反映同类事物共同性质的知 识：特征型知识，反映事物各方面的特钮f 知识：差异璎知识，反映不同事物之i h j 属性 差别的知识：关联型知识，反映事物之l 日j 依赖或关联的知识；预测璎知识，根据历史 的和当日，j 的数据推测未来数据：偏离型知识，揭示事物偏离常规的异常现象。例如， 从一家超市的数据库中，可以发现的一条典型关联规则可能是“买面包和黄油的顾客 十有八九也买牛奶”，也可能足“买食品的顾客几乎都用信用卡”，这种规则对于商家 ) f ：发和实施客户化的销售计划策略是非常自。用的。 在世界走向信息化的今天，充分利j 】食业的信息资源，挖掘食业和所对应市场的 运作舰律性，以不断提高企业的经济设益足先进介业的必由之路。可预汁：不久将来 先进的大企业将会设置“统一数捌分析簟家”的i ：作岗位。 2 2 挖掘的任务和方法 2 2 1 数据挖掘的任务 根据挖掘 l 标昂l 埘缘，数圳挖铡f e 务一叮分为以卜儿类：数掳总结、分类、聚炎、 火暇舰! j ! i j 发现等。 1 、数据总结 数据总结又称数据约简，目的是对数据进行浓缩，给出它的紧凑描述。最简单的 数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值，或 者用直方图、饼状图等图形方式表示。数据挖掘主要关心从数据泛化的角度来讨论数 据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过程。为 了不遗漏任何可能有用的数据信息，数据库中所包的数据或信息总是最原始、最基本 的信息，但人们有时希望能从较高层次的视图上处理或浏览数据，因此需要对数据进 行不同层次上的泛化以适应挖掘目的要求。数据泛化目前主要有两种技术：多维数据 分析方法和面向属性的归纳方法。 多维数据分析方法是一种数据仓库技术，也称作联机分析处理( o l a p ) 。数据仓库 是面向决策支持的、集成的、稳定的、不同时i 日j 的历史数据集合。在数掂分析中经常 要用到诸如求和、总计、平均、最大、最小等汇集操作，这类操作的计算量特别大。 因此一种很自然的想法是，把汇集操作结果预先计算并存储起来，以便于决策支持系 统使用。存储汇集操作结果的地方称作多维数据库。多维数据分卡厅技术已经在决策支 持系统中获得了成功的应用，如著名的s a s 数掘分析软件包使用了多维数据分析技术。 多维数据分析方法进行数据总结，针对的是数据仓库，数据仓库存储静态的历史 数据。为了处理联机数据，研究人员提出了一种面向属性的归纳方法。它的思路是， 直接对月j 户感兴趣的数据视图( 用一般的s q l 查询语者即可获得) 进行泛化，而不是像 多维数据分析方法那样预先将泛化数折j 存储在数据仓库中，方法的提出者对这种数据 泛化技术称之为面向属性的归纳方法。原始关系经过泛化操作后得到的是一个泛化关 系，它从较高的层次上总结了在较低层次上的原始关系。有了泛化关系后，就可以对 它进行符种深入的操作而生成满足用户需要的知识。 2 、分类 分类的目的是找到一个分类函数或分类模型，该模型能把数据库中的数据项映射 到给定类别中的某一个。分类目的是从历史数据纪录中自动推导出对给定数据的推广 描述，从而能对未来数据进行预测。要构造分类器需要有一个训练样本数据集作为输 入。训练集由一组数据库记录或冗组构成，每个元组足一个由有关字段( 又称属性或 特征) 值组成的特征向量。分类器的构造力法有统汁方法、机器学习方法、神经网络 方法等等。 统计方法包括贝叶斯法和基于事例的学习，对应的知识表示为判别函数和原型事 例。机器学习方法包括决策树法和舰则归纳法。神经网络方法t 要是b p 算法( 自订向反 馈神经网络) ，b p 算法本质：足一羊叶l - i f ：线性判别函数。 3 、聚类 聚类足把组个体叛照十似。盹pi 成符干类删，即“物以类聚”。它的 i 的足使得 属j ：问类别的个体之f h j 的趴离堪t 叮能的小，m 小类删 ：的个体m 的距离j s 町能的 大。聚类方法也卜要包括统计力法、机器学爿j 法、神经例络方法。 在统计方法中，聚类称聚类分析，它是多元数据分析的三大方法之一( 其它两种 是回归分析和判别分析) 。它主要研究基于几何距离的聚类，如欧式距离、明考斯基 距离等。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、 有序样品聚类、有重叠聚类和模糊聚类等。这种聚类方法是种基于全局比较的聚类， 它需要考察所有的个体才能决定类的划分，因此它要求所有的数据必须预先给定，而 不能动态增加新的数据对象。 在机器学习中聚类称作无监督归纳，因为和分类学习相比，分类学习的例子或数 据对象有类别标记，而要聚类的例子则没有标记，需要由聚类学习算法柬自动确定。 很多人工智能文献中，聚类也称概念聚类，因为这里的距离不再是统计方法中的几何 距离，而是根据概念的描述来确定的。当聚类对象可以动态增加时，概念聚类则称是 概念形成。在神经网络中，有一类无监督学习方法：自组织神经网络方法。 4 、关联规则发现 挖赫| ；关联规则主要足针对事务型数抛库，特别是售货数据，由于条形码技术的发 展，零售部门可以利用前端收款机收集存储大量的售货数据，如果对这些历史事务数 据进行分析，则可对顾客的购买行为提供极有价值的信息。例如，可以帮助如何摆放 货架上的商品，把顾客经常同时买的商品放在一起，帮助规划市场，减少库存，对市 场变化提供预测。由此可见，从事务数据中发现关联规则，对于改进零售j 等商业活 动的决策非常重要。在事务数据库中存在非常多的关联规则。本文介绍的改进h p r i o r i 算法是关联规则挖掘的重要方法。其主要原理是在事务数据库数据矩阵化的基础上产 牛频繁集，然后由基于支持度、匹配度的评价系统产生合理的关联j j i ! 则。 2 2 2 数据挖掘的方法 楸捌数捌挖掘任务及信息的数抛格式，通常采用的方法有f i 砸) l 种： l 、基于频繁集的a p r i o r i 及其改进方法 有关a p r i o r i 挖掘理论将在第四章详细介绍。 2 、籽l 糙集( r o u g hs e t ) 方法 料糙理论是近几年来才兴起的用于研究不精确、不确定性矢i l 谚! 的学习、表达、归 纳的力法。它通过引入不可分辨关系、等价类、卜近似、下近似等概念考察知以表达 中小f d 属性的重要性，来确定哪些属性是冗余的，哪蝗槿性足必小t l r 少的。删除冗余 属 ，# 进f 而简化知谚 表达空问，最终能从数据i f i 挖赫i ：h ：舰毗0 。它的理论核心足堆于知识 源j 二肘对象的分类这一思想的，通过分类找 n 属性刚的天联规! j ! i j 。 3 、遗传算法( g e n e t i ca l g o r i t h m s ) 遗传鲜法是基一j ：达尔文的进化论l i 琏【天it 针i 、突变f l lf f 然选择等概念。这北算法 作川j ：对某一特定1 u j 题的一组叮能的解法。它 | j 试图通过纰合或“繁磺”现仃的最好 的斛法柬产生史好的解法。利j f j “适嚣7 l 存”f | ：j 【念他较办的晰江破抛弃，从 酊! 敛 8 解法的集合，即繁殖的结果得到改善。通常，解法的随机突变用来防止算法受阻于好 的但非最优的解法。 4 、神经网络( n e u r a ln e t w o r k s ) 人工神经网络是模拟人类的形象直觉思维、是在生物神经网络研究的基础上，根 据尘物神经元和神经网络的特点，通过简化、归纳、提炼总结出来的一类并行处理网 络。利用其非线性映射的思想和并行处理的方法，用神经网络本身结构可以表达输入 与输出的关联知识。它完成输入空间与输出空l b j 的映射关系，是通过网络结构不断学 习、调整，最后以网络的特点结构来表达的，没有显示函数表达。 5 、聚类法( c l u s t e r i n g ) 聚类算法是通过对变量的比较，把具有相似特征的数据归于一类。刚此，通过聚 类以后，数据集就转化为类集，在类集中同一类中数据具有相似的变量值，不同类之 间数据的变量值不具有相似性。区分不同的类是属于数据挖掘过程的一部分，这些类 不足事先定义好的，而是通过聚类算法采用全自动方式获得。 聚类法大至上可分为两种类型： ( 1 ) 分层聚类( h i e r a r c h i c a l ) 。 分层聚类是基于数学的标准，对数拆：进行细分或聚合。这种类型适用于数值数据。 ( 2 ) 概念聚类( c o n c e p t u a l ) 。 概念聚类是基于数据的非数值属性，对数据进行细分或聚合。这种类j 适用于非 数值数据。 6 、分类法( c l a s s i f i c a t i o n ) 分类法是最普通的数据挖掘方法之。它试图按照事先定义的标准义寸数引进行归 类。 分类法大至t r 可分为如下几种类型： ( 1 ) 决策树归纳法( d e c i s i o nt r e el n d u c t i o n ) 。 决策树归纳法根据数据的值把数捌分层组织成树型结构。在决策树中每一个分支 代表一个子类，树的每一层代表一个概念。国际上最有影响和最早的决策树疗法是由 q u i u l a n 研制的i d ：j 方法，后人又发展了各种决策树力法，如工b l e 方法使谚 别率提 高了lo ( j 6 。 ( 2 ) 规则归纳法( r u l ei n d u c ti o n ) 。 规则归纳法是【i 】一系列的if - t h e nj 9 【! ! i ! l j 柬对数据：进行归类。 ( 3 ) 神经网络法( n e u r a ln e t w o r k s ) 。 神经网络法婴足通过训练神经网络使其谚 别4 i 川的类，再利川神乡争网络对数据 进行9l 类。 7 、覆盖l f 例引 斥反例力 上 利j 1j 覆芏j i l l 所有i l i 例排斥所彳f 反例的心想求：乒找枷| j ! l j 。比较媳掣的彳i l i a i s kl 的 ( j ll 办法、洪家浆改进的a ( j 15 方i 法衣ia i s 力法。 8 、统计分析方法 在数据库字段项之| 日j 存在两种关系：函数关系( 能用函数公式表示的确定性关系) 和相关关系( 不能用函数公式表示，但仍足相关确定性关系) ，对它们的分析可采用回 归分析、相关分析、主成分分析等方法。 9 、模糊论方法 利用模糊集合理论，对实际问题进行模糊判断、模糊决策、模糊模式识别、模糊 簇聚分析。系统的复杂性越高，精确能力就越低，模糊性就越强。 2 3 数据挖掘的对象和类型 2 3 1 数据挖掘的对象 根据信息存储格式，用二卜挖掘的对缘有事务数据库、关系数据库、面向对缘数据 库、数据仓库、文本数据源、多媒体数据库、遗产数据库以及环球网w e b 。 目的，用于数据挖掘的数据源主要是事务数据库、关系数据库、数据仓库和环球 网w e b 。 2 3 2 数据挖掘的类型 l 、基于规则中处理的变量的类别f i i 司，关联规则可以分为钿尔犁和数值犁。佰 尔型关联舰则处理的数据都足离散的、种类化的，它显示了这些变量之i h j 的关系。而 数值型关联规则可以和多维关联或多层关联规则结合起来。对数值型字段进行处理的 过程中需将其进行动态的分割，或者直接又t 原始的数据进行处理。当然数值犁天联规 则中也可以包含种布尔型变量。例如：( 性别= “女”) 号( 职业= “秘书”) ，足靠尔氆 关联规则；( 性别= “女”) j ( a v g ( 收入) ：2 3 0 ) ，由于收入是数值型数据，所以足一个 数值型关联规则。 2 、基于规则中数据的抽象层次，可以分为单层关联舰则和多层关联规则。在单 层天联规则【 】，觇则不涉及不f r 可抽缘层的项或属性；而在多层关联规则中，舰毗i j 涉及 f i 同抽缘层的项或属性。例如：i b m 台式机j s o n y 打印机，是一个细节数据一【：的单丘； 关联规则：台式机j s o n y 打印机，足一个较高层次和细节层次之问的多层关联规则。 3 、基f 舰则中涉及剑的数据的维数，关联规则可以分为单维的和多维的。在单 维的关联觇则中，我们， l 涉及到数荔的个维，如用，、购买的物品，而在多维的关联 规则中，要处王q ! 的数折：将会涉及多个维。换成另一句话，单维关联规则足处王翟啦个属 性中的关系；多维关联舰则足处j q ! 再个f j 川磁性之l 日j 的天系。例如：下l n i 的关联舰则 是哪维天联规则，它， i 涉及了一个维“购买”。 购艾汁算机荨购丈财务软件 卜i f f f 的关联规则足多维火驳胤则，它涉及了一个维“年龄”、“年收入”和“蚴岁：”0 1 0 年龄 2 5 ，3 5 人年收入 4 力，5 力 垮购买计算机 2 4 数据挖掘的相关技术以及挖掘工具 2 4 1 数据挖掘的相关技术介绍 这些技术尽管独立于数据挖掘技术，将这些技术和数据挖掘技术结合能提高整个 数据挖掘过程的效率和使用价值。 l 、在线分析处理( o nl i n ea n a l y t i c a lp r o c e s s i n g ，o l a p ) 在线分析处理技术是一种与数锯挖掘技术相似的技术，不同之处在线分析处理技 术是一非自动过程，但它能迅速响应用户的请求。在线分析处理工具允许用户观察、 操作及分析所谓的多维数据库。 2 、数据仓库( d a t aw a r e h o u s e s ) 数据仓库是面向主题的、稳定的、不同时i h j 的数据集合，用以支持经营管理中的 决策。 通常由一些小型数据库构成，它的主体是由关系数据库构成，但某些层次的数据 也可能由其它类型的数据( 如多维数据) 组成，它兼备数据集成和数据分析的功能。它 的作用相当于一档案室，尽管它的内容允许增加，但一般不允许更新。 3 、可视化数据技术( d a t av i s u a li s a t i o n ) 可视化数据技术足一全交互式技术。它利用宅日j 和非空间的属性( 如：大小、颜 色等) 把大量的数据以图表的形式在屏幕上挈现给用户，从而使用户在脱察数据时能 在一较高的层次上找出数据问可能的关系。 2 4 2 数据挖掘的工具 目自订，国外有许多研究机构、公司和学术组织从事数据采掘工具的研制和j i ：发。 这些工具主要采用基于人工智能的技术，色括决策树、规则归纳、神经厄网络、可视 化、模糊建模、簇聚等，另外也采用了传统的统计方法。这些数据采掘：l ：具差别很大， 不仅体现在关键技术e ，还体现在运 j 二平台、数槲存取、价格等方面。 数据采掘工具可根抛应用领域分为三类： 1 、单任务类 仅支持k d d 的数铡采巅d 步骤，并f 1 需要大t t - 硅的预处理和善后处理工作。t 要采用 决策树、神经网络、事例学习和规则9i 纳的办法，发现任务大多属于分类。 2 、通用多任务类 可执行多个领域的矢h 谚：发现任务，集成了分类、可视化、聚集、概括等多种策略， 盘【lc 1 e m e n t in e 、i b in t e lli g e n tm i f l e e 、s ( ；【ir l e s e t 、d b in o r 。 3 、专用领域类 现有的许多数据采掘系统是专为特定 的丌发的，用于专用领域的知识发现，对 采掘的数据库有语义要求，发现的知识和方法也较单一。 2 5 数据挖掘的步骤 数据挖掘工程的特点之一是在真诈丌始数据挖掘之前需要做大量预处理工作。这 些工作包括：定义问题、获取相关数掘和为挖掘准备数据。挖掘过程如图2 1 1 1 i i ! ! ! 一一 - ： 数据挖掘 - i 结果评价 图2 i 数据挖拥 过氍图 下面对数据挖掘工程的一般方法和步骤进 j ：多 体闽述： l 、定义问题 这一步的主要目的足确定数据挖拥f 是否适合解决客，! 所提出的问题。其次还要做 ) l s o i 相关工作： 第一、需要从客户那里获取哪些数据。第二：、足行有足够的数据支持数扼挖掘。 2 、获取数掘 这一阶段主要足祚：企业数就- ：库专家的帮助i - s l ! 解命= 业数技i ：库的结构、内容等。 3 、整理和仞探数据 整耻数据阶段 i 篮怂把i 岳要挖j ) j l i 的数扒骼f ! 成通合j 挖掘的枷i 准格i = 。刈j j | 5 止与五 失和错误的数扔：做适叫1 处f e 。 初探数据阶段主要是使用数据操作技术产生图表和统计结果，对数据进行初步处 理以获得数据的大致“轮廓”，从而使得分析员能发现那些有价值和值得进一步分析 的数据区域。 4 、选择和准备数据 在初步理解数据后，下一步就是针对数据挖掘目标选择合适的挖掘工具和挖掘技 术。通常选择数据的子集或样本进行预挖掘，以便较快地确定合适的挖掘工具和挖掘 技术。数据样本的选择可以使用各种统计技术。 5 、挖掘数据( m i n i n gt h ed a t a ) 这一阶段是整个过程的核心阶段，主要是用选择好的挖掘工具和挖掘技术对数据 进行处理，从而发现规则、模式和趋势等。 6 、解释结果 这一阶段主要是把数据挖掘所得到的知识反馈给用户进行评价。这时可以利用各 种可视化技术使结果更容易理解。 7 、运用知识 这一阶段主要是利用数据挖掘获得的知识束解决最初客户所提： j 的问题。通过挖 掘所获得的知识的价值在很大程度上取决于它们是否能有效地解决初始问题。 2 6 本章小结 本章辛要介绍了数据挖掘的过程、分类、仟务、对象和技术方法，为后面章节中 的数抛挖拥 的实际应用奠定了略实的理论基础。 在第_ f i 章中将要介绍关于数掘挖掘技术在学生管理系统中的应j f j ，在研究中，本 文选择关联规则技术进行探讨。 第三章改进的关联规则的衡量标准 在交易数据库中挖掘关联规则是数据挖掘领域中的一个非常重要的课题。关联规 则是发现数据库中不同项之问的联系，这些规则可用于发现顾客购买行为模式，如购 买了某些商品对购买其他商品的影响。这样的规则可应用于商晶货架设计、货存安排 以及根据购买模式对用户进行分类等。 本章分析了关联规则的衡量标准，针对其中的缺点和不足，提出了一种匹配度方 法用以取代置信度，并将匹配度方法生成的规则与支持度置信度框架生成的规则进 行了比较结果表明：用匹配度方法生成的规则不仅前件和后件具有较高的相关性，而 且减少了冗余规则的生成。 3 1 研究背景 关联规则是数据挖掘诸多功能中的一种，也是目前最为重要和应用最广泛的数据 挖掘方法之一。关联规则的概念由a g r a w a l 、i m i e l i n s k i