（计算机应用技术专业论文）关联规则挖掘算法研究.pdf

摘要 数据挖掘是当今人工智能和数据库研究方面最富活力的领域。数据挖掘是指 从大量的数据中发现潜在的、有用的知识的过程。关联规则数据挖掘是数据挖掘 的一个主要研究内容，而如何快速发现频繁项集是关联规则数据挖掘算法的核心 问题。 本文讨论了数据挖掘的一般理论，包括数据挖掘的概念、任务、模式以及数 据挖掘的应用和发展趋势。深入研究了关联规则挖掘算法，分析了关联规则挖掘 中经典的a p r i o r i 算法，并总结了a p r i o r i 算法中存在的问题。针对该算法的效率问题， 从两个角度进行改进：( 1 ) 降低候选项目集中候选项的数量；( 2 ) 减少扫描数据库的 次数。因此，给出了一种更高效的关联规则挖掘算法。算法的主要思想是在扫描 数据库的同时把支持每个项目的事务都标记出来，采用一种新的方法生成所有的 频繁集。该算法只需对源数据库进行一次扫描就可以找出所有的频繁集，并通过 裁剪候选集的方法达到减少候选项数目集的目的。这样做不但降低了算法的i o 负 荷，而且减少了时间开销，具有很高的效率。最后，将基于关联规则的数据挖掘 新方法应用到教学评价中，对挖掘结果进行了分析，并提出了指导意见。 本文的工作虽然取得了一定的成果，但尚有大量问题有待于进一步研究，比 如，关联规则挖掘应用系统的设计；关联规则有趣度的研究以及如何将挖掘结果 友好地呈现给用户。 关键词：数据挖掘关联规则频繁集支持度可信度 a b s t r a c t d a t am i n i n gi so n eo ft h em o s ta c t i v er e s e a r c hf i e l d s ，e s p e c i a l l yi nt h ef i e l d so f a r t i f i c i a li n t e l l i g e n c ea n dd a t a b a s e d a t am i n i n gi sak i n do fp r o c e s st h a tr e v e a l s p o t e n t i a lu s e f u lk n o w l e d g ef r o mm a s s i v ed a t a t h ea s s o c i a t i o nr u l em i n i n gi sam a i n r e s e a r c ha s p e c to fd a t am i n i n g a n dt h ed i s c o v e r yo ft h ef r e q u e n ti t e ms e t si sa k e y p r o b l e m o ft h ea s s o c i a t i o nr u l em i n i n g a l g o r i t h m f i r s t l y ，t h ed a t am i n i n gi sd i s c u s s e dg e n e r a l l yi nt h i sp a p e r ，i n c l u d i n gi t sc o n c e p t s ， p a t t e r n s ，a p p l i c a t i o n sa n dd e v e l o p m e n tt r e n d s e c o n d l y , a p r i o r ia l g o r i t h mi sr e s e a r c h e d a n da n a l y s e dd e e p l y ，w h i c hi sc l a s s i co ft h ea 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 s a n d t h e ns u m m a r i z e st h ep r o b l e m se x i s t i n gi na p r i o r ia l g o r i t h m f o ri m p r o v i n gt h e e x i s t i n g p o o re f f i c i e n c yo fa p r i o r ia l g o r i t h m ，t h i sp a p e re x p o u n d ss o m es c h e m e si nt w oa s p e c t s o n es h e m ei sr e d u c i n gt h ec a n d i d a t ei t e ms e t s ，a n dt h eo t h e ri s d e c r e a s i n gt h et i m e s s p e n d i n gi ns c a n n i n gd a t a b a s e t h e n ，am o r ee f f i c i e n ta l g o r i t h mf o ra s s o c i a t i o nr u l e m i n i n gi sp r e s e n t e d t h em a i ni d e ao ft h ea l g o r i t n mi st om a r ka l lt h et r a n s a c t i o n s s u p p o r t i n ge a c hi t e mi ns c a n n i n gd a t a b e s e t h en e wa l g o r i t h ma d o p t sau n i q u ew a yt o g e n e r a t et h ef r e q u e n ti t e ms e t s i tc a bm i n ea l lt h ef r e q u e n ti t e ms e t sb ys c a n n i n gt h e s o u r c ed a t a b a s eo n l yo n c ea n dr e d u c i n gt h ec a n d i d a t ei t e ms e t sd e p e n d i n go nt h e p r u n i n g i tn o to n l yd e c r e a s e st h eb e a ro fi 0 ，b u ta l s or e d u c e st h ee x e c u t i o nt i m e ，a n d t h e ng o th i g he f f i c i e n c y f i n a l l y ，t h en e wm e t h o db a s e do na s s o c i a t i o nr u l e si s a p p l i e d i n t ot h et e a c h i n ge v a l u a t i o n ，t h em i n i n gr e s u l ti sa n a l y z e d ，a n di n s t r u c t i v eo p i n i o ni s p r o p o s e d a l t h o u g ht h ec e r t a i nr e s u l t sh a sb e e no b t a i n e di nt h i sp a p e r , t h e r ea r es t i l lm a n y q u e s t i o n s t ob es t u d i e d h a r d l y ，s u c ha s ，d e s i g n i n g t h ea s s o c i a t i o nr u l e m i n i n g a p p l i c a t i o ns y s t e m ，s t u d y i n gt h ei n t e r e s t i n ga s s o c i a t i o nr u l e sa n dp r e s e n t i n gt h em i n i n g r e s u l t sm o r e f r i e n d l yt ot h eu s e r k e y w o r d s ：d a t am i n i n g a s s o c i a t i o nr u l e f r e q u e n ti t e ms e t s u p p o r t c o n f i d e n c e 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特j j , l d n 以标 注和致谢中所罗列的内容以外，论文中不包含其它人已经发表或撰写过的研究成 果：也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：盔盔玺墅同期2 硝! 垒! ! 三 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：蕴盔星垫 导师签 第一章绪论 第一章绪论 数据挖掘( d a t am i n i n g ) 是一门汇集统计学、机器学习、数据库、模式识别、 知识获取、专家系统、数据可视化和高性能计算等多种学科的新兴交叉学科，这 个领域融合了多个不同学科领域的技术和成果，使其方法表现出多种多样的形式。 为自动和智能地把海量的数据转化为有用的信息知识提供了有力的手段，给数据 和知识之间的鸿沟架设了方便之桥。 1 1 数据挖掘的研究背景 如今是一个网络化的时代，通信、计算机和网络技术正改变着整个人类和社 会。半个世纪以来，人们利用信息技术和搜集数据的能力在不断提高，当前有无 数数据库被用于商业管理、政府办公、科学研究和工程开发等，这一势头仍将持 续发展下去。特别是近年来，i n t e m e t 的迅猛发展，网络经济等概念的出现，以其 巨大的社会效益成为信息科学最引人注目的科研课题。于是，一个新的挑战被提 了出来：在这被称之为信息爆炸的时代，信息过量几乎成为人人需要面对的问题。 如何才能不被信息的汪洋大海所淹没，从中及时发现有用的知识，提高信息利用 率呢? 要想使数据真正成为一个公司的资源，只有充分利用它为公司自身的业务决 策和战略发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾【l l 。因此， 面对“信息爆炸、但知识匾乏 的挑战，数据挖掘技术应运而生，并得以蓬勃发 展，越来越显示出其强大的生命力。 自2 0 世纪6 0 年代以来，数据库和信息技术已经系统地从原始的文件处理演化 到复杂的、功能强大的数据库系统。但是，数据库技术作为一种基本的信息存储 和管理方式，仍然以联机事务处理o l t p ( o n l i n et r a n s a c t i o np r o c e s s i n g ) 为核心技术 应用，缺少对决策、分析、预测等高级功能的支持机制，已经不能满足人们日益 增长的对数据中隐含知识的渴求。而数据挖掘方法的提出，让人们最终有能力认 识到数据的真正价值，即蕴含在数据中的信息和知识，能够挖掘出蕴含在数据库 中不为人知又非常有用的知识和信息，以辅助决策。 数据挖掘发现的知识可以被用于信息管理、查询优化、决策支持等，还可以 用于数据自身的维护。因此，数据挖掘把人们对数据的应用从低层次的简单查询， 提升到从数据中挖掘知识，提供决策支持。在这种需求的牵引下，不同领域的研 究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等 方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成了新的 技术热点。 关联规则挖掘算法研究 经过几十年的研究和实践，数据挖掘技术吸收了许多学科的研究成果，形成 了独具特色的研究分支。勿容置疑，数据挖掘研究和应用具有很大的挑战性，一 方面，数据挖掘概念己经被广泛接受，而且相关的研究成果和产品得到了学者的 认可，吸引了越来越多的研究者；另一方面，目前的数据挖掘研究还存在许多有 待研究和探索的问题。 1 2 数据挖掘中的关联规则 目前，数据挖掘的主要研究领域可分为分类、聚类、关联规则等方面。关联 规则挖掘是数据挖掘研究的一个重要分支，它是数据挖掘的众多知识类型中最为 典型的一种，有着极其重要的应用价值。关联规则挖掘可以发现存在于数据库中 的项目( i t e m s ) 或属性( a t t r i b u t e s ) 间的有趣关系，这些关系是预先未知的和被隐藏 的，也就是说不能通过数据库的逻辑操作( 如：表的联接) 或统计的方法得出。这说 明它们不是基于数据自身的固有属性( 例如函数依赖关系) ，而是基于数据项目的同 时出现特征。即关联规则表示数据库中一组对象之间某种关联关系的规则。例如， 关联规则可以表示为“购买了项目a 和b 的顾客中有9 5 的人又买了c 和d ”。从这 些规则可找出顾客购买行为模式，可以应用于商品货架设计、生产安排、针对性 的市场营销等。采用关联模型比较典型的例子是“啤酒和尿布”的故事【2 】。在美国， 一些年轻的父亲下班后经常到超市去买婴儿尿布，超市经过对顾客的购物信息进 行挖掘，发现在购买婴儿尿布的年轻父亲中，有3 0 4 0 的人同时要买一些啤酒。 超市随后调整了货架的摆放，把尿布和啤酒放在一起。结果是：销售额明显增加 了。 关联规则问题k l ：t a g r a w a l 等人于1 9 9 3 年首次提出，后来诸多的研究人员对关联 规则的挖掘问题进行了大量的研列3 1 。他们的工作包括：对原有的算法进行优化， 如引入随机采样、并行的思想、增加衡量标准、改变存储结构等，以提高算法的 效率；对关联规则的应用进行推广，从最初的商业指导到生活中的其他领域，如 教育、科研、医学等。 1 3 关联规则挖掘的研究现状 关联规则数据挖掘是挖掘发现大量数据中项集之间有趣的关联或相关联系， 它在数据挖掘中是个重要的课题。由于关联规则挖掘可以发现用传统的人工智能 和统计方法无法发现的项与项或属性与属性间的关系规律，因此具有重要的研究 价值。同时它也满足了人们从大规模数据存储中获取知识的迫切需求。许多国外 大学的研究机构和学者对该领域的发展做出了重要贡献，如加拿大s i m o nf r a s e r u n i v e r s i t y 大学的j i a w e ih a n 等著名专家，它们的许多工作都足在该领域中具有奠基 第一章绪论 性的【4 】。近年来，国内的关联规则挖掘研究也正逐渐掀起高潮，出现了一批相关的 科研项目，在算法和应用方面取得了一些具有扩展性或突破性的研究成果【5 】。 从近年来的文献中可以看出，除了不断地提出一些新的挖掘技术外，大量的 有关数据挖掘的文章集中于讨论如何提高数据挖掘系统，尤其是提高关联规则挖 掘的性能，包括算法的有效性、可伸缩性和并行处理。 关联规则的发现可分为两步，第一步是迭代识别所有的频繁项目集，要求频 繁项目集的支持率不低于用户设定的最低值，第二步是从频繁项目集中构造可信 度不低于用户设定的最低值的规则，识别或发现所有频繁项目集是关联规则发现 算法的核心，也是计算量最大的部分。 最为著名的关联规则发现方法a p r i o r i 算法由a g r a w a l 和s r i k a n t 提出，但a p r i o r i 算法有明显的性能瓶颈，随着数据库容量的增大，在挖掘频繁项目集时需要产生 大量候选项集，重复访问数据库、外存，将导致性能低下。正因为如此，包括a g r a w a l 在内的许多学者提出- a p r i o r i 算法的若干改进方法，以提高算法的效率，如散列 技术、事务压缩、划分技术、抽样算法等，它们各有其优缺点。因此，探索新的 理论和算法来减少数据库的扫描次数和候选集空间占用，已经成为近年来关联规 则挖掘研究的热点之一。这也正是本文的研究所在。 1 4 本文工作 本文的主要研究内容是关联规则挖掘算法。通过对国内外取得的一些成果进 行研究和分析，并在借鉴前人成果的基础上，针对目前关联规则挖掘算法研究和 运用中遇到的一些问题提出改进的方法。论文的主要工作包括： 1 研究了关联规则挖掘经典算法 研究与分析了关联规则数据挖掘。在描述关联规则的概念和性质的基础上， 概括关联规则的分类和步骤，重点研究关联规则挖掘经典算法一a 研o r i 算法，充 分分析了算法的优缺点及已有的改进措施。 a p r i o r i 算法的核心方法是基于频集理论的递推方法。研究表明，a p r i o r i 算法简 单易懂，但是存在明显的性能瓶颈：在挖掘频繁模式时需要产生大量候选项集， 多次扫描数据库，时空复杂度过高。 2 提出了关联规则挖掘经典算法的改进方案 针对频繁项目发现算法的性能瓶颈问题，本文提出了两种改进方案，以提高 算法效率。具体改进方案如下： ( 1 ) 在扫描数据库的同时把支持每个项目的事务都标记出来，采用一种新的方 法生成所有的频繁集，以减少数据库扫描次数，降低算法的i 0 负荷。 ( 2 ) 采用裁剪的方法降低产生候选项目集中候选项的数量，减少时间开销，以 4 关联规则挖掘算法研究 提高算法的效率。 3 改进了关联规则挖掘算法 通过对关联规则深入细致的研究，基于两种改进方案，本文给出了一种更高 效的关联规则挖掘的改进算法。该算法在扫描数据库的同时记录每个项目的支持 事务，通过候选k 项集中每个项目的的支持事务集来确定候选k 项集的支持事务 集，避免了重复扫描数据库，并通过裁剪的方法达到减少候选项数目集目的，大 大地节约系统的开销。 4 验证了改进算法的效率 为了比较改进算法与a p r i o r i 算法的效率，采用同样的实验条件，用真实数据 库中的数据来评估算法的性能。实验证明，改进的关联规则挖掘算法具有较高的 嗷率。 5 将改进算法应用于教学质量评价中，取得了较好的效果 讨论了改进算法的应用实例。首先分析教学评价的重要性及现状，针对现行 教学质量评价体系的不足之处，将数据挖掘技术引入到高校教学质量评价中。通 过把改进算法运用到实际的教学质量评价表中，挖掘出课堂效果与教师的状态特 征之间的关联关系，从而得到有价值的信息。最后对结果进行分析和评估，并绐： 出了提高教学质量的指导建议。 1 5 论文的组织 本论文共分为六章，具体组织如下： 第一章绪论。主要描述论文研究的背景和意义、论文的研究现状、论文的主 要工作以及结构安排。 第二章数据挖掘。研究了数据挖掘的理论，包括数据挖掘的概念、任务、模 式，讨论了数据挖掘的应用和发展趋势。 第三章关联规则数据挖掘。详细研究了数据挖掘中的关联规则挖掘，从关联 规则挖掘的典型例子引出关联规则挖掘的问题描述，然后给出关联规则的概念和 性质，列出关联规则挖掘的基本步骤，分析关联规则挖掘的经典算法a p r i o r i 算法 以及一些改进技术。 第四章一种改进的关联规则挖掘算法。首先提出了基于a p r i o r i 算法的两种改 进方案，并综合改进方案给出i m a 算法，然后通过举例详细说明了i m a 算法的执行 情况，最后对i m a 算法的性能与a 研o r i 算法的性能进行了比较实验。 第五章改进算法在课掌教学评价中的应用。讨论改进的关联规则算法在高校 教学评价系统中的应用。从教学评价数据中进行数据挖掘，对挖掘结果进行分析， 找到课堂教学效果与教师状念的关系，从而为教学部门提供了决策支持信息。 第六章结束语。总结了全文的工作，指出了下一步的研究内容和方向。 第二章数据挖掘 第二章数据挖掘 数据挖掘是指从大量的数据中发现潜在的、有用的知识的过程。本章将研究 数据挖掘的理论体系，包括数据挖掘的概念、任务和基本模式；讨论数据挖掘的 应用和发展趋势；为后续章节建立理论基础。 2 1 1 数据挖掘的定义 2 1 数据挖掘的相关概念 所谓数据挖掘，就是从大量的、不完全的、有噪声的、模糊的、随机的实际 应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和 知识的过程【6 】。简单地说，数据挖掘就是从大量的数据中提取或者“挖掘”知识。 在许多场合下，数据挖掘又被称为数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ，简称k d d ) 7 】。但是，更科学的说法是将数据挖掘视为数据库知识发现 的一个基本步骤。在这种情况下，数据库的知识发现过程由以下几个步骤组成： 1 数据清理：消除噪声或者不一致数据。 2 数据集成：多种数据源可以组合在一起。它和数据清理一起被视为预处理 步骤，结果数据存放在数据仓库中。 3 数据选择：从数据库中检索与分析任务相关的数据。 4 数据变换：将数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作。 5 数据挖掘：使用智能方法提取数据模式。 6 模式评估：根据某种兴趣度度量，识别出有趣的模式。 7 知识表示：使用可视化技术，向用户提供挖掘的知识。 2 1 2 数据挖掘系统结构 尽管将数据挖掘视为数据库知识发现过程的一个基本步骤更为科学，但是在 产业界、媒体和数据库研究界，将数据挖掘直接当作数据库中的知识发现更为流 行。因此数据挖掘有了一个更加广泛的概念：数据挖掘是从存放在数据库、数据 仓库或其他信息库中的大量数据中挖掘有趣知识的过程。基于这种观点，一个典 型的数据挖掘系统可以由以下几个主要成分组成( 如图2 1 所示) ： 6 关联规则挖掘算法研究 图形用户界面 上t 模式评估 上t 数据挖掘引擎 上t f 数据库或数据仓库服务器 丁t 数据库数据仓库 图2 1 典型的数据挖掘系统结构 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、电子 表格或其他类型的信息库。可以在数据上进行数据清理和集成。 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服 务器负责提取相关数据。 数据挖掘引擎：数据挖掘系统基本的部分，由一组功能模块组成，用于特征 化、关联、分类、聚类分析以及演变和偏差分析。 模式评估：通常，此模块使用兴趣度阈值过滤发现的模式，并与数据挖掘模 块交互，把搜索聚焦在有趣的模式上。 图形用户界面：实现用户和数据挖掘系统之间的通信，允许用户与系统交互， 指定数据挖掘任务、提供信息，根据数据挖掘的中间结果进行探索式数据挖掘【8 】。 此外，此模块还允许用户浏览数据库和数据仓库，评估挖掘的模式，以不同的形 式对模式可视化。 2 1 3 数据挖掘的数据来源 从原则上讲，数据挖掘应该能够在任何类型的数据源上进行，包括关系数据 库、数据仓库、事务数据库、高级数据库系统等。 1 关系数据库 关系数据库是表的组合，每个表都赋予一个唯一的名字。每个表包含一组属 性( 列或字段) ，通常存放大量元组( 记录或行) 。表中的每个元组代表一个被唯一的 关键字标识的对象，并被一组属性值描述。 第二章数据挖掘 关系数据库通常采用数据查询的方式进行访问，数据查询使用关系查询语言， 如著名的s q l 语言，或者借助于图形用户界面书写。当数据挖掘应用于关系数据库 时，可以进一步搜索数据模式。例如，数据挖掘系统可以分析顾客数据，根据顾 客的收入、年龄和以前的信用信息来预测新顾客的信用风险。 在数据挖掘应用的数据源中，关系数据库是最流行和最丰富的，因此也是数 据挖掘研究的主要数据形式。 2 数据仓库 数据仓库是从多个数据源收集的信息存储，存放在一个一致的模式下，并通 常驻留在某个站点。数据仓库通过数据清理、数据变换、数据集成、数据装入和 定期数据刷新来构造。数据仓库是一种全新的数据存储模式。它是一种语义上一 致的数据存储，存放企业战略决策所需的信息【9 】。 数据仓库最常见的应用有三种： 信息处理：支持查询和基本的统计分析，并使用交叉表、表、图表或图进 行报告。 分析处理：支持基本的联机分析处理( o l a p ) 操作。一般地，它在汇总的历 史数据上操作。 。 数据挖掘：支持知识发现，包括找出隐藏的模式和关联，构造分析模型， 进行分类和预测，并用可视化工具提供挖掘结果。 在数据仓库的三种应用中，信息处理可以反映直接存放在数据库中的信息， 但并不反映复杂的模式或隐藏在数据库中的规律【m 】。联机分析处理可以由用户选 定的数据仓库子集，导出汇总的信息，由此帮助简化数据分析。而数据挖掘则更 进一层，它的目标是尽可能自动地发现隐藏在大量数据中的模式和有趣的知识。 3 事务数据库 事务数据库通常由一个文件组成，其中每个记录代表一个事务。通常，一个 事务包含一个唯一的事务标识号( t r a n s a c t i o ni d ，简称t d ) 和一个组成事务的项的 列表。事务可以存放在表中，每个记录代表一个事务。 4 高级数据库系统 高级数据库系统是面向特殊应用的数据库系统，包括以下一些： 面向对象的数据库：采用基于面向对象的程序设计范例，每个实体被看作 一个对象，一个对象的数据和代码封装在一个单元中。 空间数据库：包含涉及空间的信息。这种数据库包含地理数据库，v l s i ( v e r y l a r g es c a l ei n t e g r a t i o n ，超大规模集成电路) 芯片设计数据库、医疗和卫星图像数据 库【1 1 1 。 文本数据库：包含文字描述的数据库。通常这种描述不是简单的关键词， 而是长句子或短文，如产品介绍、汇总报告等。文本数据库可能是非结构化的， 8 关联规则挖掘算法研究 也可能是半结构化的。 多媒体数据库：存放图像、音频和视频数据。它们用于基于图像内容的检 索、声音传递、视频点播等方面。 异种数据库：由一组互连的、自治的成员数据库组成。这些成员间相互通 信，以便交换信息和回答查询。一个成员数据库中的对象可能与其它成员数据库 中的对象很不相同，使得很难将它们的语义吸收进一个整体【1 2 】。 2 2 1 数据挖掘的任务 2 2 数据挖掘的任务和基本模式 数据挖掘的任务是从数据中发现模式。模式是用语言l 来表示的一个表达式e ， 它可以用来描述数据集f 中数据的特性，e 所描述的数据是集合f 的一个子集f e 。e 作为一个模式，它比所有描述数据子集f e 中元素的方法都简单。例如，“如果成 绩在8 1 9 0 之间，则成绩优良 可称为一个模式，而“如果成绩为8 1 ，8 2 ，8 3 ，8 4 ， 8 5 ，8 6 ，8 7 ，8 8 ，8 9 或9 0 ，则成绩优良就不能称之为一个模式。 数据挖掘的核心技术是人工智能、机器学习、数理统计等，但它并非多种技 术的简单组合，而是一个不可分割的整体，还需要其他技术韵支持，才能挖掘出 令用户满意的结果。 2 2 2 数据挖掘的模式 由于每一种数据挖掘技术都有其自身的特点和实现的步骤，对数据的形式有 具体的要求，因此成功的应用数据挖掘技术以达到目标，这个过程本身就是一件 很复杂的事情，下面主要从挖掘任务和可获得的数据这两个角度来讨论对具体挖 掘模式的选择。 根据挖掘任务，数据挖掘可分为概念描述、聚集发现、关联规则发现、分类 发现、回归发现和序列模式发现等。在选择使用某种数据挖掘技术之前，首先要 将待解决的商业问题转化成正确的数据挖掘任务，然后根据挖掘任务来选择具体 使用某一种或几种挖掘模式。下面具体地分析每种挖掘任务应使用哪些挖掘模 式。 1 概念描述 对一含有大量数据的数据集合进行概述性的总结并获得简明、准确的描述， 这种描述就称为概念描述。概念描述是描述型数据挖掘的最基本形式。它以简洁 汇总的形式描述给定的数据集，提供数据的有趣特性【l3 1 。通常，用户指定的数据 通过数据库查询来收集。例如，为研究上一年销售增加1 0 的软件产品的特征，可 第二章数据挖掘 9 以通过执行一个s q l 查询收集关于这些产品的数据。数据特征的输出可以用多种形 式提供，包括饼图、条图、曲线、多维数据立方体和包括交叉表在内的多维表。 2 聚类发现 聚类是根据一定的规则，把一组个体按照相似性归成若干类别，即“物以类 聚 。它的目的是使属于同一类别的个体之间的距离尽可能地小，而不同类别的 个体间的距离尽可能地大。与分类不同，在开始聚类之前你不知道要把数据分成 几组，也不知道怎么分( 依照哪几个变量) ，因此在聚类之后要有一个对业务很熟悉 的人来解释这样分类的意义。很多情况聚类需要经过几次反复之后才能最终得到 一个理想的结果【l4 1 。聚类分析在电子商务上的典型应用是帮助市场分析人员从客 户资料库中发现不同的客户群，并且用购买模式来刻画不同客户群的特征。此外 聚类分析可以作为其它算法的预处理步骤，这些算法再在生成的类上进行处理。 3 关联规则发现 关联分析是寻找在同一个事件中出现的不同项的相关性，比如在一次购买活 动中所买不同商品的相关性。以购物篮这个典型例子分析关联规则，“在购买面 包和黄油的顾客中，有9 0 的人同时也买了牛奶，即( 面包+ 黄油) 牛奶。用于 关联规则发现的对象主要是事务型数据库，分析的是售货数据，也称货篮数据。 关联分析目前是数据挖掘中应用最广泛的一种，它具有一定的研究价值。 4 分类发现 分类的目的是建立一个分类函数或分类模型( 也称作分类器) ，该模型能把 数据库的数据项映射到给定类别中的某一个。分类要解决的问题是为一个事件或 对象归类。设有一个数据库和一组具有不同特征的类别，该数据库中的每一个记 录都赋予一个类别的标记，这样的数据库称为示例数据库或训练集。分类分析就 是通过分析示例数据库中的数据，为每个类别做出准确的描述，建立分析模型或 挖掘出分类规则，然后用这个分类规则对其它数据库中的记录进行分类。例：信 用卡申请者，分类为低、中、高风险。 5 回归发现 回归是通过具有已知值的变量来预测其他变量的值。它与分类类似，差别在 于前者的预测值是连续的，而后者是离散的。在最简单的情况下，回归采用的是 如线性回归这样的标准统计技术，但在大多数现实世界中的问题是不能用简单的 线性回归来预测的。如商品的销售量、股票价格、产品合格率、利润的大小等， 很难找到简单有效的方法来预测，因为要描述这些事件的变化所需的变量以上百 计，且这些变量本身往往都是非线性的。为此人们又发明了许多新的手段来试图 解决这个问题，如逻辑回归、神经网络等。 6 序列模式发现 序列模式分析和关联分析类似，其目的也是为了挖掘数据之间的联系，但序 关联规则挖掘算法研究 列模式分析的侧重点在于分析数据间的前后序列关系。它能发现数据库中形如“在 某一段时间内，顾客购买商品a ，接着购买商品b ，然后购买商品c ”，即序列 a j b j c 出现的频率较高之类的知识。序列模式分析描述的问题是：在给定的交 易序列数据库中，每个序列是按照交易时间排列的一组交易集，挖掘序列函数作 用在这个交易序列数据库上，返回该数据库中出现的高频序列【巧】。在进行序列模 式分析时，同样也需要用户输入最小置信度和最小支持度。 总之在选择一种数据挖掘技术的时候，应根据商业问题的特点来决定采用哪 种数据挖掘形式比较合适。应选择符合数据模型的算法，确定合适的模型和参数， 只有选择好正确的数据挖掘工具，才能真正发挥数据挖掘的作用，使企业在激烈 的市场竞争中做出正确的决策，保持有力的竞争优势。 2 3 数据挖掘的应用 ，t 数据挖掘技术的应用领域非常广泛，在政府管理决策、商业运营决策、科学 研究和工业企业决策支持等各个领域都能应用数据挖掘技术。其中比较成功的应 用领域包括： 1 商业管理 通过对顾客交易的数据进行分析可以有效地对顾客群体进行划分，预测不同 群体的购买行为和需求大小，进行有针对性的营销设计。运用模式识别和聚类分 析的方法，通过提取客户资料，对客户和它们对几种不同商品的兴趣进行聚类分 析，可以发现潜在客户的具体特征，从而对这些潜在客户进行相应的促销宣传。 2 网站管理 网站是电子商务的基础平台，大型网站每日都有数以万计的访问量，如何合 理安排网站组织结构，是一个非常困难的任务。通过应用数据挖掘可以从用户的 访问信息中发现有价值的知识，从而指导网站设计者更新网站结构与内容，更好 地与客户进行交流，发现潜在客户，改进客户关系管理，提高网络营销效率，而 且可以进一步实施针对个性化用户或用户群的访问界面，从而开展有针对性的电 子商务以满足访问者的需求 1 6 - 1 7 1 。 3 信息安全 在电子商务中，电子交易是其中的一个重要组成部分，而信用卡又在电子交 易中扮演了重要的角色。通过运用数据挖掘中的离群数据挖掘方法或聚类方法总 结正常交易行为和诈骗行为之间的关系，获取诈骗行为的一些特性。利用这些知 识去分析和判断现有交易中具有诈骗的倾向，如发现某项业务符合这些特征时， 可以向决策人员提出警告【1 8 1 。 4 金融证券 第二章数据挖掘 数据挖掘已广泛地应用于银行和金融市场。金融市场中的数据挖掘主要应用 于改进预测市场波动的能力、建立预测模型以识别出历史上曾引起市场波动的因 素所具有的模式、进行投资分析增加收入、以及减少商业欺诈所造成的损失 1 9 - 2 0 】。 典型的应用有：贷款偿还预测和客户信用政策分析；股票预测；客户保持； 实时营销。 5 科学研究 利用数据挖掘技术可以处理极大量的数据，例如在生物d n a 分析、新药的药 理分析和治疗机理和天文学研究等领域都可以找到数据挖掘技术的应用空间【2 1 1 。 2 4 数据挖掘的发展趋势 1 应用的探索：随着电子商务和电子市场逐渐成为零售业的主流因素，数据 挖掘也在不断扩展其在商业领域的应用面。通用数据挖掘系统在处理特定应用问 题时有其局限性，因此目前的一种趋势是开发针对特定应用的数据挖掘系统。 2 可伸缩的数据挖掘方法：数据挖掘必须尽可能交互式地、有效地处理大量 数据。由于数据量在不断地激增，因此针对单独和集成的数据挖掘功能的可伸缩 算法显得十分重要【2 2 1 。一个重要的方向是基于约束的挖掘，它提供了额外的控制 方法，允许用户说明和使用约束，引导数据挖掘系统对感兴趣模式的搜索。 3 数据挖掘与数据库系统、数据仓库系统的集成：数据库系统、数据仓库系 统己经成为信息处理系统的主流，而数据挖掘系统的理想体系结构是与数据库和 数据仓库的紧藕合。事务管理、查询处理、联机分析处理和联机分析挖掘应集成 在一个统一框架中。这将保证数据的可获得性，数据挖掘的可移植性、可伸缩性， 以及形成对多维数据分析和探查的集成信息处理环境。 4 数据挖掘语言的标准化：标准的数据挖掘语言或其他方面的标准化工作将 有助于数据挖掘的系统化开发，加强多个数据挖掘系统之间的互操作，促进数据 挖掘系统在企业和社会中的使用。 5 可视化数据挖掘：可视化数据挖掘是从大量数据中发现知识的有效途径， 系统研究和开发可视化数据挖掘技术将有助于推进数据挖掘作为数据分析的基本 工具。 6 复杂数据类型挖掘的新方法：复杂数据类型挖掘是数据挖掘中一项重要的 前沿研究课题。现在，虽然在多媒体挖掘、时序挖掘以及文本挖掘方面取得一些 进展，但与实际应用的需要仍存在很大的距离。对此需要进一步地研究，尤其是 把针对上述数据类型的现存数据分析技术与数据挖掘方法集成起来的研究。 7 w e b 挖掘：由于w e b 上存在大量信息，并且w e b 在当今社会扮演越来越重要 的角色，有关w e b 内容挖掘、w e b r 志挖掘，将成为数据挖掘中 关联规则挖掘算法研究 一个最为重要和繁荣的子领域。 8 数据挖掘中的隐私保护与信息安全：随着数据挖掘工具、计算机网络的日 益普及，数据挖掘要面对的一个重要问题是隐私保护和信息安全。需要进一步开 发有关方法，以便在适当的信息访问和数据挖掘过程中确保隐私保护与信息安全。 2 5 本章小结 本章首先研究了数据挖掘的概念，包括数据挖掘的定义、过程及数据挖掘的 系统结构；接着描述了数据挖掘的任务和模式，讨论了数据挖掘的应用；最后展 望了数据挖掘的未来发展趋势。 第二章关联规则数据挖掘 第三章关联规则数据挖掘 关联规则数据挖掘就是从大量的数据中挖掘出有价值的描述数据项之间相互 联系的有关知识，它的目标是发现数据集中所有的频繁模式。本章将研究与分析 关联规则数据挖掘。在描述关联规则的概念和性质的基础上，概括关联规则的分 类和步骤，重点研究关联规则挖掘经典算法一a p r i o r i 算法，分析算法的优缺点， 总结改进技术方案，为a p r i o r i 改进算法的提出和构造建立理论上的必要性前提。 3 1 关联规则描述 3 1 1 基本概念 关联规则挖掘可以描述如下：假设i - - i l ，i 2 ，i m ) 是m 个不同项目的集合， 给定一个交易数据库d ( 即一个交易集合) ，d 中的每个元素( 交易) t 是i 中一些 项目组成的集合，并且t 曼i 。每个交易可以用唯一的标识符t i d 来标识。关联规则 是形如x y 的蕴含式，其中x c i ，y c i ，并且x ny = 。x 表示此关联规则的前 件或前提( a n t e c e d e n t ) ，y 为此关联规则的后件或结论( c o n s e q u e n t ) ，关联规则 的挖掘就是要发现满足用户给定的最低支持度和最低置信度的所有条件蕴含式， 即强关联规则。这些规则的支持度和置信度都大于等于最低支持度和最低置信度。 每个关联规则有两个度量标准：置信度和支持度。置信度是对关联规则的准 确度的度量，或者说表示规则的强度，支持度是对关联规则的重要性的度量，表 示规则的频度。支持度说明了这条规则在所有事务中有多大的代表性，显然，支 持度越大，关联规则越重要。有些关联规则置信度虽然很高，但支持度却很低， 说明该关联规则实用的机会很小。反之，如果支持度很高，置信度很低，则说明 该规则不可靠。如果不考虑关联规则的支持度和置信度，那么在数据库中存在非 常多的关联规则。事实上，人们一般只对那些满足一定的支持度和置信度的关联 规则感兴趣。因此，为了发现有意义的关联舰则，需要由专家或用户给定两个基 本阈值：最低支持度和最低置信度。 有关定义如下所述： 定义3 1 项目( i t e m ) ：交易数据库中的一个属性字段，每个字段有一定的取 值范围。对一超级市场来讲，项目一般是指一次交易中的一个物品。 定义3 2 交易( t r a n s a c t i o n ) ：某个客户在一次交易中，发生的所有项目的集 合。 定义3 3 项目集( i t e ms e t ) ：包含若干个项目的集合，简称项集。 1 4 关联规则挖掘算法研究 定义3 4k 项集：对于项集x ，如果x 中包含有k 个项目，则x 称为k 项集。例 如：项集x = a ，b ) 就是一个2 一项集。 定义3 5 支持度( s u p p o r t ) ：称交易数据库d 中包含项目集x 的交易的个数与 d 中总的交易个数之比为x 在d 中的支持度，它是概率p ( x ) 。把x 的支持度记作 s u p p ( x ) ，而关联规则x j y 的支持度则记作s u p p ( x = ：, y ) ，具体描述是： s u p p ( x = ：, y ) = p ( xu 定义3 6 置信度( c o n f i d e n c e ) ：对形如x j y 的关联规则，其中x 和y 都是项 目集，定义规则的置信度为交易集合d 中既包含x 也包含y 的交易个数与d 中包含x 的交易个数之比，或者说是项目集x j y 的支持度与x 的支持度之比，1 1 1 s u p p ( x k j y ) s u p p ( x ) 。置信度即是指在出现了项目集x 的交易中，项目集y 也同时出现的概 率有多大。把规则x j y 的置信度记作c o n f ( x j ， 具体描述是： c o n f ( x j y ) = p ( yix ) 定义3 7 最低支持度( m i n i m u ms u p p o r t ) ：由用户定义的衡量支持度的一个 阈值，表示项目集在统计意义上的最低重要性，记作而m i n s u p 。 定义3 8 最低置信度( m i n i m u mc o n f i d e n c e ) ：由用户定义的衡量置信度的一 个阈值，表示规则的最低可靠性，记作m i n c o n f , 对于满足最低支持度和最低置信度要求的关联规则称为强关联规则，否则为 弱关联规则。 定义3 9 支持数：d 中包含项目集x 的事务( 交易) t 的个数，称为x 在d 中的 支持数( s u p p o r tc o u n t ) 或频率，简记为c o u n t 。设d 中包含的事务数表示为ld l ，根据 以上支持度和支持数的定义，可以得出关联规则某项目集x 的支持数与支持度的关 系是c o u n t = s u p p o r t l d i ，另外与最低支持度相对应，把支持数定义为最低支持数 ( m i n i m u ms u p p o r tc o u n t ) ，简记为m i n c o u n t ，它和最低支持度的关系是 m i n c o u n t - - m i n s u p i d f 。 定义3 1 0 频繁项目集：若项集x 的支持度不小于最低支持度，则称x 为频繁项 目集，即x 满足最低支持度要求。若某一项目m 满足最低支持度要求，则称m 为频 繁项目，所有频繁项目的集合称为频繁1 项集，记为l 1 ；满足最低支持度要求的k 一 项集称为频繁k 项集，所有频繁k 项集的集合记为l k 。 3 1 2 频繁集的性质 性质l ：子集支持 设a