（计算机应用技术专业论文）关联规则挖掘在图书馆管理系统中的研究与应用.pdf

摘要 摘要 数据挖掘( d a t am i n i n g ) 就是从海量的数据中挖掘出可能有潜在价值的信息 的技术。这些信息是可能有潜在价值的，支持决策，可以为企业带来利益，或者 为科学研究寻找突破口。关联规则挖掘是数据挖掘技术中的非常重要的功能。关 联是某种事物发生时其他事物会发生的这样一种联系。图书馆每天产生大量的图 书流通数据，这些数据除了用于记录读者的信息外，一般只用来做一些常规的业 务数据统计，这些数据潜在的使用价值还远远没能得到充分的挖掘和利用。我们 可以通过将关联规则挖掘方法应用到图书数据的分析中，挖掘和发现读者借阅行 为中隐含的规律，以指导图书馆的馆藏图书分布决策，以及提供读者服务工作， 提出读者的个性化服务模型。 本文主要是对数据挖掘技术中的关联规则挖掘研究。通过总结前人对于关联 规则的各项研究，特别是对经典a p r i o r i 算法以及其变形算法的深入细致的分析比 较，改进了一种新的关联规则挖掘算法，该算法是：基于维谓词约束、维数目约 束以及频繁链表结构的多维关联规则挖掘算法；同时并对关联挖掘综合评价问题 的相关性进行分析探讨、在前人基于概率差值的兴趣度阀值的基础上，进行了理 论上的验证，在产生关联规则这一步骤方面，扩宽了负项目挖掘的思路，并综合 频繁项集的产生过程，最终写出了改进后的算法。接着在微型计算机上编程实现 了本文改进算法，建立了实验模型，通过大量实验数据模拟，验证了该改进算法 在时间和空间上的性能提高、以及产生的关联规则项目更加科学合理和客观。本 文最后还将改进的算法应用于广东工业大学图书馆管理系统，建立了用于挖掘系 统的图书馆数据仓库，设计和实现了图书馆挖掘系统，并对2 0 0 9 年2 月至4 月的 馆藏读者借阅数据进行了关联规则挖掘，通过对数据的认真细致分析比较，挖掘 到了隐藏在借阅数据之间的读者借书规律，并结合学校实际情况，因地制宣，提 出了相应的馆藏布局和读者个性化服务等方面的建议，从而有效地提高了图书馆 管理工作决策的水平。 论文最后还对所做的工作进行了总结，指出了关联规则挖掘技术需要进一步 研究的方向，最后展望了数据挖掘技术的发展前景。 关键词：数据挖掘；关联规则；a p r i o r i 算法；频繁项集 广东工业大学硕士学位论文 a b s tr a c t d a t am i n i n gi st h et e c h n o l o g yt h a te x c a v a t e df r o mm a s so fd a t aw h i c hm a yh a v e t h ep o t e n t i a lv a l u eo fi n f o r m a t i o n t h ei n f o r m a t i o nt h a tm a yb es o m ep o t e n t i a lv a l u ei n s u p p o r to fd e c i s i o n - m a k i n g ，c a nb r i n gb e n e f i t sf o rt h ee n t e r p r i s e ，o rf o r s c i e n t i f i c r e s e a r c ht of i n dab r e a k t h r o u g h m i n i n ga s s o c i a t i o nr u l e si nd a t am i n i n gi sav e r y i m p o r t a n tf u n c t i o n a s s o c i a t i o nr u l e sa r ea s s o c i a t e da tt h et i m es o m e t h i n ge l s ew i l l h a p p e ni ns u c hac o n t a c t l i b r a r i e sh a v ea d a t af l o wo f l a r g en u m b e r so f b o o k sp e rd a y , w h i c hu s e dt or e c o r di n f o r m a t i o nf o rr e a d e r si na d d i t i o n ，g e n e r a l l yu s e da sam o r e c o n v e n t i o n a lb u s i n e s sd a t as t a t i s t i c s ，t h ep o t e n t i a lv a l u eo ft h e s ed a t ai sf a rn o tb e e n f u l l ye x c a v a t e da n du t i l i z a t i o n t h r o u g ha s s o c i a t i o nr u l em i n i n gm e t h o da p p l i e d t ot h e a n a l y s i so f t h ed a t ai nt h eb o o k ，w ec a nf i n dr e a d e r sb o r r o we x c a v a t i o na n dd i s c o v e r y o ft h el a wo fi m p l i e db e h a v i o rt o g u i d et h ed i s t r i b u t i o no fl i b r a r yb o o k s i n d e c i s i o n - m a k i n g ，a sw e l la ss e r v i c e sp r o v i d e dt h er e a d e r sp e r s o n a l i z e ds e r v i c em o d e l t h i sp a p e ri sf o c u so na s s o c i a t i o nr u l em i n i n go fd a t am i n i n g t h r o u g ht h e s u m m a r yo fp r e v i o u sa s s o c i a t i o nr u l e sf o rt h ev a r i o u ss t u d i e s ，e s p e c i a l l yf o rt h ec l a s s i c a p r i o r ia l g o r i t h ma n di t sd e f o r m a t i o na l g o r i t h mi n - d e p t ha n a l y s i sa n dd e t a i l e d c o m p a r i s o n , t h ei m p r o v e m e n to fan e wa 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 , w h i c hi s ： b a s e do np r e d i c a t e d i m e n s i o n a lc o n s t r a 硫s ，v i c t o r i al i s tt h en u m b e ro fs t r u c t u r a l c o n s t r a i n t s ，a sw e l la sf r e q u e n tm u l t i - d i m e n s i o n a la 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 ； a tt h es a m et i m e ，ac o m p r e h e n s i v ee v a l u a t i o no fm i n i n ga n dr e l a t e di s s u e st oe x p l o r e t h er e l e v a n c eo ft h ea n a l y s i si nt h ep r e v i o u si n t e r e s tm a r g i nb a s e do nt h ed e g r e eo f p r o b a b i l i t yt h r e s h o l do nt h eb a s i so fat h e o r yv e r i f i c a t i o n , i nt h ea s s o c i a t e dr e g u l a t o r y i st h i ss t e p ，t h ew i d e n i n gp r o j e c tm i n i n gn e g a t i v et h i n k i n g ，a n di n t e g r a t e df r e q u e n t i t e m s e t so ft h es e l e c t i o np r o c e s s ，a n du l t i m a t e l yw r o t et h ei m p r o v e da l g o r i t h m t h e ni n t h e m i c r o - c o m p u t e rp r o g r a m m i n gt oi m p r o v et h ea l g o r i t h mi nt h i sp a p e r , t h e e s t a b l i s h m e n to fa ne x p e r i m e n t a lm o d e l , al a r g en u m b e ro fe x p e r i m e n t a ld a t at h r o u g h s i m u l a t i o n , t h ev a l i d i t yo ft h ei m p r o v e da l g o r i t h mi nt i m ea n ds p a c et oi m p r o v e p e r f o r m a n c e ，a sw e l la sa s s o c i a t i o nr u l e sg e n e r a t e db yt h ep r o j e c tm o r es c i e n t i f i ca n d a b s t r a c t r e a s o n a b l ea n do b j e c t i v e f i n a l l y , t h ea l g o r i t h mw i l lb e u s e dt o i m p r o v et h e g u a n g d o n gu n i v e r s i t yo ft e c h n o l o g yl i b r a r ym a n a g e m e n ts y s t e m , t h ee s t a b l i s h m e n t o fal i b r a r ys y s t e mf o rm i n i n gd a t aw a r e h o u s e d e s i g na n di m p l e m e n t a t i o no f am i n i n g s y s t e ml i b r a r i e s ，a n dt h r o u g ht h ea s s o c i a t i o nr u l em i n i n go ff o u rm o n t h so fr e a d e r sd a t a c o l l e c t i o nf r o mf e b r u a r y2 0 0 9t oa p r i l2 0 0 9 ，t h r o u g hc a r e f u la n a l y s i so fd a t a c o m p a r i s o n , t h ee x c a v a t i o nt ot h eh i d d e nd a t ar e a d e r st ob o r r o wl a wl i b r a r y , c o m b i n e d w i t ht h ea c t u a ls i t u a t i o ni ns c h o o l s ，i nl i n ew i t hl o c a lc o n d i t i o n s ，t h ec o r r e s p o n d i n g l a y o u to ft h ec o l l e c t i o n sa n dr e a d e r sp e r s o n a l i z e ds e r v i c e ss u g g e s t e dt h a ti no r d e rt o e f f e c t i v e l yi m p r o v et h em a n a g e m e n to f t h el i b r a r yd e c i s i o n - m a k i n gl e v e l f i n a l l yt h ew o r ki sa l s os u m m a r i z e d ，a n dt h ep a p e rp o i n t so u tt h a tt h ea s s o c i a t i o n m l em i n i n gt e c h n o l o g yd i r e c t i o nf o rf u r t h e rr e s e a r c h , a n dl o o k st ot h ed a t am i n i n g t e c h n o l o g yd e v e l o p m e n tp r o s p e c t s 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 s ；a p r i o r ia l g o r i t h m ；f r e q u e n ti t e m s e t s i i i 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及所取得的研究成果。尽我所知，除了文中特别加 以标注和致谢的地方外，论文中不包含其他人已经发表或者撰写过的研究成果， 不包含本人或其他用途使用过的成果。与我一同工作过的同志对本研究所做的任 何贡献均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的。论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 论文作者签字：乡- m - - 2 u 山 指导教师签字 2 第一章绪论 第一章绪论 1 1 引言 随着数据库技术的成熟和数据应用的普及，各个领域所积累的数据量正在以 指数级速度增长。人们正面临着“数据丰富而知识贫乏 的问题，所以迫切需要 一种新的技术从海量数据中自动、高效地提取所需要的有用知识。正是在这种“数 据的丰富带来了对强有力的数据分析工具的需求 的背景下，数据库中知识发 现技术营运而生，并得到迅速发展，成为数据库研究、开发和应用最活跃的分支 之一。它可以从大型数据库中的海量原始数据中提取人们感兴趣的、隐含的、尚 未被发现的有用的信息和知识。数据挖掘是一个融合数据库、机器学习、数理统 计、可视化和信息科学技术为一体的新兴的交叉学科领域。它的发展不仅可以为 商务管理、科学研究、查询优化、过程控制等领域提供决策支持，而且为相关的 计算机学科注入新的活力，从而推进计算机科学向纵深方向发展。毫无疑问，对 数据挖掘的深入研究在计算机理论和应用两个方面都具有十分重大的意义。在数 据挖掘所能发现出的众多知识种类中，例如，关联规贝j j ( a s s o c i a t i o nr u l e ) 的挖掘、 分类( c l a s s i f i c a t i o n ) 、聚类( c l u s t e r i n g ) 、趋势( t r e n d ) 分析、偏差( d e v i a t i o n ) 分析、 模式( p a t t e r n ) 分析等，关联规则的挖掘是目前数据挖掘领域中研究最为广泛最为深 入的课题之一。数据挖掘综合了各个学科技术，有很多的功能，当前的主要功能 有：分类、聚类、关联规则和序列模式的发现、预测、偏差的检测。事实上，数 据挖掘的各项功能不是独立存在的，在数据挖掘中互相联系，发挥作用。 关联规则是用于发现大量数据中项集之间有意义的关系模式。例如：每天购 买啤酒的人也有可能购买香烟，比重有多大，可以通过关联的支持度和可信度来 描述。通常挖掘关联规则的问题可以分为两个阶段：第一阶段，根据使用者所制 定的最小支持度从数据库中找出出现频率大于或等于最小支持度的所有频繁项目 集；第二阶段，则是以第一阶段所产生的频繁项目集来产生关联规则。目前，大 多数图书馆根据业务和办公的需要，建立了各自的业务处理系统和图书馆办公自 动化系统，这些业务信息系统为提高图书馆的工作效率，减少重复性的工作起到 了积极的作用，推动了图书馆事业的发展。虽然关系型数据库成功地解决了图书 广东工业大学硕士学位论文 馆的大量事务处理，但它仅仅只能对数据库中保存的大量日常业务数据进行简单 的统计报表、检索查询等浅层面的处理。积累的大量进书数据、读者借还书的历 史记录等等，其数据量在不断地迅速膨胀。这些图书管理数据，犹如茫茫的信息 海洋，能否从中了解：这些表面毫无关联的数据之间是否存在或多或少的关系呢? 怎样才能找到这些关系并利用到图书馆管理中呢? 如何识别读者读书习惯，改进 服务质量，取得更好的读者忠诚度和满意程度呢? 这就是数据分析与数据挖掘要 做的工作。 1 2 研究意义 数据的存储量在呈指数级地增加，从大量数据中挖掘有价值的知识在当今信 息时代具有重要意义。关联规则挖掘是数据挖掘领域中的重要课题之一。它既能 用于概念描述又能用于分类预测与决策，在数据挖掘中发挥重要作用。目前关联 规则挖掘技术在学术界与产业界受到广泛关注并被深入研究探索。有专家预测， 数据挖掘技术在图书馆中的应用是现代图书馆发展的一个关键技术，运用数据挖 掘技术不仅可以对读者的借阅数据进行分析，从而适时调整馆藏方向，使图书馆 的信息资源体系更加合理化；同时还可以发现读者的借阅模式和借阅偏好，帮助 图书馆为读者提供个性化的信息服务乜1 。本研究将深入挖掘图书馆巨量数据中隐 含的有价值信息，这对于提高图书馆管理工作和决策水平有着非常重大的意义。 1 3 研究现状和应用 国际上第一次关于数据挖掘与知识发现的研讨会于1 9 8 9 年在美国的底特律 召开，之后，数据挖掘技术得到了长足的发展。由于数据挖掘一开始就是面向应 用的，是为决策服务的，一些公司运用数据挖掘的成功案例，显示了数据挖掘的 强大生命力： 全球最大的零售商沃尔玛( w a l m a r t ) 通过对顾客购物清单的数据挖掘发现了 “尿布j 啤酒”的关联规则，后来沃尔玛就把尿布和啤酒摆放在一起，从而双双 促进了尿布和啤酒的销量。 由i b m 公司a l m a d e n 研究中心的r a g r a w a l 等人研究开发的多任务数据挖掘 系统q u e s t 是面向大型数据库系统，功能包括关联规则、分类规则、序列模式和 相似序列等。 2 第一章绪论 美国a u t o t r a d e r c o m 是世界上最大的汽车销售站点，每天都会有大量的用户 对网站上的信息点击，寻求信息，该网站运用了s a s 软件进行数据挖掘，每天对 数据进行分析，找出用户的访问模式，对产品的喜欢程度进行判断，并设特定服 务，取得了成功。 南京大学的徐洁磐、陈栋等人开发了一个原型系统：k n i g h t ，这是一个通用 的d m 工具，可用于处理不同领域的知识发现任务，主要有聚类分析、特征知识 发现、分类规则发现、关联规则发现、函数依赖发现及基于查询的知识发现等。 中科院软件所史忠植研究员领导的课题组在d m 技术的研究上也有大量成 果，发表若干论文。李得毅院士、孟海军等人也发表了多篇前沿论文。 上海宝钢年产量超过l 千万吨，营业额达数百亿，在长期的运营中积累了包 括原料、生产、质量、销售、运输、订单、供应商、客户在内的数百g b 数据。 宝钢应用s a s 公司的产品在i b ms p 2 上建立了一个企业级的d w ，也取得了许多 丰硕的成果。 1 4 数据挖掘面临的主要问题 数据挖掘面临的主要问题有挖掘方法、用户交互、性能和存储的各种数据类 型问题啼3 。 1 挖掘方法与用户交互问题。这类问题涉及所挖掘的知识类型、在多粒度上 挖掘知识的能力、领域知识的使用、特定的挖掘和知识显示。 ( 1 ) 在数据库中挖掘不同类型的知识：由于不同的用户可能对不同类型的知 识感兴趣，数据挖掘系统应当覆盖范围很广的数据分析和知识发现任务，包括数 据特征化、区分、关联、分类、聚类、趋势和偏差分析以及类似性分析。这些任 务可能以不同的方式使用相同的数据库，并需要开发大量数据挖掘技术。 ( 2 ) 多个抽象层的交互知识挖掘：由于很难准确地知道能够在数据库中发现 什么，数据挖掘过程应当是交互的。 ( 3 ) 结合背景知识：可以使用背景知识或关于所研究领域的信息来指导发现 过程并使得发现的模式以简洁的形式在不同的抽象层表示。 ( 4 ) 数据挖掘结果的表示和显示：发现的知识应当用高级语言、可视化表示 或其他表示形式表示，使得知识易于理解，能够直接被人们使用。这要求系统采 用有表达能力的知识表示技术，如树、表、规则、图、图表、交叉表、矩阵或曲 3 广东工业大学硕士学位论文 线等。 ( 5 ) 处理噪声和不完全数据：存放在数据库中的数据可能反映噪声、异常情 况或不完全的数据对象。这些对象可能搞乱分析过程，导致数据与所构造的知识 模型过分适应。其结果是，所发现的模式的精确性可能很差。 ( 6 ) 模式评估兴趣度问题：数据挖掘系统可能发现数以千计的模式。对 于给定的用户，许多模式不是有趣的，它们表示公共知识或缺乏新颖性。关于开 发模式兴趣度的评估技术，特别是关于给定用户类，基于用户的信赖或期望，评 估模式价值的主观度量仍然存在一些挑战。 2 性能问题。包括数据挖掘算法的有效性、可收缩性和并行处理。 ( 1 ) 数据挖掘算法的有效性和可伸缩性：数据挖掘一个重要的特点是去产生 假设，但它并不去验证假设。为了有效地从数据库的大量数据中提取信息，数据 挖掘算法必须是有效的和可伸缩的。即对于大型数据库，数据挖掘算法的运行时 间必须是可预计的和可接受的。 ( 2 ) 并行、分布式和增量挖掘算法：数据库的大容量、数据广泛和一些数据 挖掘算法的计算复杂性促使开发和研究了并行、分布式和增量挖掘算法。这些算 法将数据划分成多个部分，这些算法可以并行处理，然后将各个处理结果合并。 数据挖掘过程的高花费导致了对增量数据挖掘算法的需要，增量算法与数据库更 新结合在一起，而不必随着数据库的更新重新挖掘全部数据，算法渐增地进行知 识更新，修正和加强先前业已发现的知识h 1 。 3 关于数据库类型的多样性问题。 ( 1 ) 关系的和复杂的数据类型的处理：由于关系数据库和数据仓库已经广泛 使用，故对它们开发有效的数据挖掘系统是重要的。然而，其他数据库可能包含 复杂的数据对象、超文本和多媒体数据、空间数据、时间数据或事务数据。由于 数据类型的多样性和数据挖掘的目标不同，指望一个系统挖掘所有类型的数据是 不现实的。为挖掘特定类型的数据，应当构造特定的数据挖掘系统。同样，对于 不同类型的数据，应当有不同的数据挖掘系统。 ( 2 ) 由异种数据库和全球信息系统挖掘信息：局域网和广域网( 如i n t e r n e t ) 连接了许多数据源，形成了庞大的、分布式的和异种的数据库。从具有不同数据 语义的结构化的、半结构化的和非结构化的不同数据源发现知识，对数据挖掘提 出了巨大挑战。数据挖掘可以帮助发现多个异种数据库中的数据规律，这些规律 4 第一章绪论 多半难以被简单的查询系统发现。 1 5 本文的研究内容 1 认真研究数据挖掘中的现有关联规则算法的优缺点。对数据挖掘和关联规 则挖掘技术进行系统分析，重点研究a p r i o r i 算法的性能瓶颈问题，详细讨论提高 a p r i o r i 算法效率的各种优化技术，客观分析它们的优缺点。 2 针对a p r i o r i 算法的不足之处，结合前人研究成果，改进了一种更为有效 的算法，并编写出了改进算法的伪代码，在微型计算机上实验模拟，验证了改进 算法在时间空间上的有效，以及产生的关联规则更加科学合理。 3 认真研究图书馆管理系统中数据的特点，通过应用本文改进的关联规则挖 掘算法从大量的借阅数据中挖掘出隐含的有价值的读者借书规律，为图书馆管理 提供决策支持服务。 1 6 本文的创新点 基于维谓词约束、维数目约束、约简事务以及频繁链表结构的多维关联规则 挖掘算法的改进。 本文在研究a p r i o r i 经典算法及其前人各种改进算法的基础上，着重分析了频 繁项集挖掘的过程，在a p r i o r i 算法的思想指导下，结合图书馆应用实际，改进了 基于维谓词约束、维数目约束、约简事务以及频繁链表结构的多维关联规则挖掘 算法，并对关联挖掘评价问题的兴趣度度量进行分析探讨，从理论上证明了负项 目关联规则挖掘的正确性，最终编写出了改进后的算法伪代码，通过实验模拟数 据证明了改进算法在性能上的优越性，最终将研究成果应用于广东工业大学图书 馆挖掘系统，为图书馆管理提供决策支持，取得了良好的效果。 1 7 论文内容安排 第一章：绪论。概要地介绍了数据挖掘技术和图书馆应用技术。阐述了课题 的来源、研究现状和应用、研究内容，存在的问题以及本文的创新点。 第二章：先是介绍分析了数据挖掘技术的研究现状。在阅读大量文献的基础 上，本文介绍了数据挖掘技术的起源、任务与功能、一般挖掘过程、挖掘技术和 方法以及当前挖掘算法面临的困难与挑战等。接着介绍了关联规则挖掘的基本概 5 广东工业大学硕士学位论文 念、分类和一般步骤：关联规则挖掘通常分为频繁项集生成和强关联规则生成两 个步骤，其中频繁项集生成是关联规则挖掘中最耗时最重要的一步。 第三章：重点介绍了经典的关联规则挖掘算法a p r i o r i 算法。a p r i o r i 算法需 要频繁扫描庞大的事务数据库，产生大量i 0 ，而且需要巨量的存储候选项集的空 间，该算法效率差强人意，迫待改进。同时分析了多种前人的基于a p r i o r i 算法的 改进算法。它们虽然比起经典算法来有了很大的提高，但还是各有一些局限性。 最后介绍了算法思路不同于a p r i o r i 算法的f p g r o w t h 算法。 第四章：通过总结前人的多维关联规则算法，结合a p r i o r i 算法性质和图书馆 数据特点。改进了基于维谓词约束、维数目约束、约简事务以及频繁链表结构的 多维关联规则挖掘算法，并对关联挖掘综合评价问题的相关性进行分析探讨。最 后编写出改进算法的伪代码，还通过实验模拟数据验证了改进算法在关联规则挖 掘技术上的性能提高。 第五章：将第四章提出的改进算法应用于广东工业大学图书馆系统，建立了 图书馆数据仓库，通过分析借阅数据，挖掘出其中潜在的有益关联规则，并为以 后图书馆管理提出切合实际的可付诸实践的决策支持建议。 结论与展望：首先总结了论文所做的工作，然后指明了关联规则挖掘的进一 步研究方向，最后展望了数据挖掘技术在现代化图书馆管理系统中的发展前景。 6 第二章数据挖掘及关联规则的介绍 第二章数据挖掘及关联规则的介绍 2 1 数据挖掘 2 1 1 数据挖掘定义 数据采掘嘲( d a t am i n i n g ) ，又称为数据挖掘、数据开采等。一般认为数据采 掘是数据库中知识发现( 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 ) 的一个环节， 是采用具体的数据采掘算法从数据中自动高效地提取有用模式的过程，而k d d 是包含数据采掘、数据准备等环节的循环往复过程。许多专家都给出了有关k d d 的定义，在k d d 研究领域一致认可的描述性定义是f a y y a d 等人给出的： 定义2 1 ：k d d 是从数据集中识别出有效的、新颖的、潜在有用的、以及最 终可理解的模式的非平凡过程。在上述定义中： 1 数据集是一组事实( 如关系数据库中的记录的集合f ) ； 2 模式是一个用l 来表示的表达式e ，它可用来描述数据集f 的某个子集 f e ，e 作为一个模式要求它比对数据子集f e 的枚举要简洁( 描述信息量要少) ； 3 过程是指k d d 是一个多阶段的过程，包括数据准备、数据采掘、知识评 价，以及上述过程的反复求精；该过程是非平凡的，是指整个过程是自动的、智 能的( 如计算所有数据的总和与平均值都不能算作是一个k d d 过程) ； 4 有效性是指发现的模式应用于新的数据时要具有一定的可信度； 5 新颖性是要求发现的模式应该是新的、用户未知的或未曾预料到的； 6 潜在有用性是指发现的知识将来具有实际效用，如用户根据发现的知识来 进行商业决策可以产生一定的经济效益； 7 最终可理解性是要求所发现的模式容易被用户理解。 2 1 2 数据挖掘的一般过程 数据挖掘，它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律 等知识的复杂过程。知识发现的过程可以分为三个主要阶段：数据准备，数据挖 掘和结果表达和理解。如图2 1 所示： 7 广东工业大学硕士学位论文 数据源 图2 - 1 知识发现过程 f i g u r e2 - 1k n o w l e d g ed i s c o v e r yp r o c e s s 1 数据准备。 ( 1 ) 数据集成一一将多文件或多数据库运行环境中的数据进行合并处 理，解决语义模糊性，处理数据中的遗漏和清洗脏数据等。 ( 2 )数据选择为知识发现的目标搜索和选择有关的数据，这包括不 同模式数据的转换和数据的统一和汇总。数据选择的目的是辨别出需要分析 的数据集合，缩小处理范围，提高数据挖掘的质量。 ( 3 )数据预处理对数据进行清理和充实等预处理工作。 ( 4 )数据转换对数据编码，数据库中字段的不同取值转换成数码 形式将有利于搜索。 2 数据挖掘。 8 第二章数据挖掘及关联规则的介绍 此阶段进行实际的挖掘操作，利用机器学习、统计分析等方法，从数据库中 发现有用的模式或知识。 3 结果表达与解释。 根据最终用户的决策目的对提取的信息进行分析，把最有价值的信息区分出 来，并且通过决策支持工具提交给决策者。这一步骤的任务不仅是把结果表达出 来，还要对信息进行过滤处理。如果不能令决策者满意，需要重复以上数据挖掘 的过程。 2 1 3 数据挖掘的分类 数据挖掘涉及的学科领域很多，有多种分类法。 根据挖掘任务分，可以分为分类或预测模型发现、聚类规则发现、分类规则 发现、关联规则发现、序列模式发现、异常和趋势发现、时间综合和概括等； 根据挖掘对象分，可以分为事务数据库、关系数据库、面向对象数据库、空 间数据库、时态数据库、文本数据库、多媒体数据库、以及环球网w e b 信息库等。 其中从关系数据库中挖掘知识是使用最为广泛的一种，也是最为成熟的一类数据 挖掘技术嘲； 根据挖掘方法分，可以分为：机器学习方法、统计方法、神经网络方法、遗 传算法、概念树方法、最近邻算法、粗糙集方法、可视化技术等。 2 1 4 数据挖掘面临的挑战 尽管数据挖掘有如此多的优点，但数据挖掘也面临着许多的问题，这也为数 据挖掘未来的发展提供了更大的空间口3 。 1 数据挖掘的基本问题就在于数据的数量和维数，数据结构也因此显的非常 复杂，如何进行探索，选择分析变量，也就成为首先要解决的问题。 2 面对如此大的数据，现有的统计方法等都遇到了问题，我们直接的想法就 是对数据进行抽样，那么怎么抽样，抽取多大的样本，又怎样评价抽样的效果， 这些都是值得研究的难题。 3 既然数据是海量的，那么数据中就会隐含一定的变化趋势，在数据挖掘中 也要对这个趋势做应有的考虑和评价。 4 各种不同的模型如何应用，其效果如何评价。不同的人对同样的数据进行 9 广东工业大学硕士学位论文 挖掘，可能产生不同的结果，甚至差异很大，这就涉及到可靠性的问题。 5 当前互联网的发展迅速，如何进行互联网的的数据挖掘，还有文本等非标 准数据的挖掘，都引起了人们的极大兴趣。 6 数据挖掘涉及到数据也就碰到了数据的私有性和安全性。 7 数据挖掘的结果是不确定的，要和专业知识相结合才能对其做出判断。 2 2 关联规则 2 2 1 关联规则定义 1 项集：项的集合称为项集( i t e m s e t ) 。设i = 1 1 ，1 2 ，i n 是一个项集，其中 i i ( i = l ，2 ，3 ，n ) 可以是购物篮中的物品，也可以是保险公司的顾客。k 项集包含k 个项的项集被成为k 项集，k 表示项集中项的数目。 2 事务：事务是项的集合，设有事务t ，则t i 。对应每个事务有唯一的标 识，如事务号记为i d 。设x 是i 中项的集合，如果x t ，则称事务t 包含x 。 3 事务集：事务的集合称为事务集。设某事务集为d ，则d = t 1 ，t 2 ，t n ， d = t i l t i d ，i = l ，2 ，n ) 。 4 关联规则：关联规则是如下形式的逻辑蕴涵：a b ，其中a 、b 是项集， a i ，b i ，anb = o 。一般用两个参数描述关联规则的属性。 ( 1 ) 可信度( 置信度) c o n f i d e n c e ：可信度即是“值得信赖性。 设a ，b 是项集，对于事务集d ，a d ，b d ，anb = o ，a jb 的可信 度定义为：可信度( 惦b ) = 包含a 和b 的元组数包含a 的元组数。 可信度表达的就是在出现项集a 的事务集d 中，项集b 也同时出现的概率。如 例子：购买牛奶的顾客中有8 0 也同时购买了面包，即是关联规则：“牛奶j 面 包 的可信度为8 0 。 ( 2 ) 支持度( s u p p o r t ) 。 支持度( a j b ) = 包含a 和b 的元组数元组总数。支持度描述了a 和b 这 两个项集在所有事务中同时出现的概率。例如在一个商场中，某天共有1 0 0 0 笔业 务，其中有1 0 0 笔业务同时买了牛奶和面包，则“牛奶j 面包关联规则的支持 度为1 0 。 满足最小支持度的项集的集合称为频繁项集。同时满足最小支持度和最小置 1 0 第二章数据挖掘及关联规则的介绍 信度阀值的规则称为强关联规则。给定一个事务集d ，挖掘关联规则问题就是产 生强关联规则。 2 2 2 关联规则分类 按照不同划分标准，关联规则可以进行分类如下： 1 基于规则中处理的变量类别，关联规则可以分为布尔型和数值型阳1 。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的 关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字 段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值 型关联规则中也可以包含种类变量。 例如：“性别= 男 “职业= 工程师”，是布尔型关联规则；“性别= 男”j “a v g ( 收入) = 4 3 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 2 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同 层次的；而在多层的关联规则中，对数据的多层性已经作了充分的考虑。 例如：i b m 台式机s o n y 打印机，是一个细节数据上的单层关联规则；台式 机：s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 3 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而 在多维的关联规则中，要处理的数据将会涉及多个维。换句话说，单维关联规则 是处理单个属性中的一些关系；多维关联规则是处理多个属性之间的某些关系。 例如：啤酒j 尿布，这条规则只涉及到用户的购买的物品。“性别= 女 “职 业= 秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。 4 基于关联规则带约束条件与否，可分为不带约束的关联规则和约束性关联 规则嘲。 我们通常所研究的关联规则，都是不带约束的关联规则。而在实际中，用户 往往并不是对所有的关联规则都感兴趣，而只想知道关于某方面的关联规则，如 那些至少包含用户指定的项目集中某项的规则等。这时就需要定义约束条件，进 行约束性关联规则的挖掘。 广东工业大学硕士学位论文 2 2 3 关联规则挖掘的步骤 关联规则挖掘的基本模型如图2 - 2 所示n 们： 图2 2 ：关联规则挖掘的基本模型 f i g u r e2 - 2t h eb a s i c m o d e lo fa s s o c i a t i o nr u l e sm i n i n g 其中d 为数据集，a l g o r i t h m - 1 为频繁项集的搜索算法，a l g o r i t h m - 2 为关联 规则的产生算法，r 为挖掘出的关联规则集合。用户通过指定最小支持度阀值 ( m i n s u p ) 和最小置信度阀值( m i n c o n o 分别与算法a l g o r k h m - 1 和a l g o r i t h m - 2 交 互，并通过与r 的交互对挖掘结果进行解释和评价。 终上所述，故关联规则挖掘可以分解为下列两个子问题n ： 1 找出所有频繁项集：这些项集出现的频率满足最小支持度m i n s u p ，即这些 项集在数据库d 中的频繁性不小于最小支持度计数； 2 由频繁项集产生强关联规则：这些规则必须满足最小置信度m i n c o n f 当然，除了这两个度量标准以外也可以使用附加的度量，例如兴趣度( i n t e r e s t ) 度量n 2 3 等。在这两个子问题中，第二个子问题最容易，找出所有频繁项集以后， 产生规则。目前有很多产生频繁项目集的算法，这些算法产生频繁k 项集时，扫 描数据库的每个事务用以统计这些候选k 项集的支持度，并按照事务数确定的最 小支持度在第k 次迭代时找出所有频繁k 项集。然而，由于数据库的规模通常是 非常大的，所以在每次迭代时产生候选项目集以统计其支持度是非常耗时的。所 以，寻求频繁项目集的有效产生算法是提高关联规则挖掘算法的关键。事实上， 在挖掘关联规则的整个执行过程中第一个子问题是核心问题，而第二个子问题相 对较为简单。 1 2 第二章数据挖掘及关联规则的介绍 2 3 本章小结 本章详细介绍了数据挖掘及关联规则的相关基本知识，通过查阅相关文档， 了解和学习了数据挖掘技术，对数据挖掘的一般过程、分类和需要研究的方向有 了明确的认识。同时对数据挖掘的重要研究领域即关联规则挖掘的研究有了深刻 的把握，抓住了关联规则挖掘算法提高的关键问题，为进一步分析关联规则算法 的优缺点奠定了基础，为写好论文积累了基本的知识，扩宽了思路，明确了研究 方向。 1 3 广东工业大学硕士学位论文 3 1 概述 第三章关联规则挖掘算法及分析 通过第二章关于数据挖掘及关联规则的介绍，我们知道在数据挖掘所发现的 知识模式中，关联规则模式是非常重要的一种，也是最活跃的一个分支。关联规 则表示数据库中一组对象之间某种关联关系的规则。发现关联规则的算法属于无 监督学习的算法。关联规则可以表示为“购买了商品a 和b 的顾客中有8 5 的人 又买了商品c 和d 。从这些规则可找出顾客购买行为模式，可以应用于商品货架 设计、生产安排、针对性的市场营销等等。关联规则对统计和决策工作有重大意 义。关联规则的概念最早由a g a r w a l ，m i i e l n s k i ，s w a m i 提出，自a g r a w a l 等人 于1 9 9 3 年提出频繁模式挖掘问题以来，己经提出了许多行之有效的技术来进行频 繁模式挖掘，根据是否产生候选集可以把算法分为两大类：产生候选集候选模式 的方法和不产生候选集候选模式的方法。前一种方法以算法a p r i o r i 算法为代 表，而后一种以算法f p - g r o w t h ( f r e q u e n tp a t t e r ng r o w t h ) 为代表。下面对关联 规则挖掘的主要代表算法进行详细地阐述、并客观真实地分析它们各自的优缺点 和主要的应用范围。 3 2a p i o r i 经典算法 a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则问 题，设计了基于频繁集理论的a p r i o r i 算法。这是一个基于两阶段频繁集思想的方 法，将关联规则挖掘算法的设计分解为两个子问题： 1 找到所有支持度大于等于最小支持度的项集( i t e m s e t ) ，这些项集称为频 繁集( 疳e q u e mi t e m s e t ) ； 2 使用第一步找到的频繁集产生期望的规则。 为了生成所有频繁集，使用了递推的方法，生成所有频繁项集的a p r i o r i 算法 流程如下所示： i n p u t ：事务数据库d ；最小支持度m i n s u p ； o u t p u t ：d 中的频繁项集l 。 1 4 第三章关联规则挖掘算法及分析 l 1 = f i n d _ f r e q u e n t _ i t e m s e t ( d