（通信与信息系统专业论文）图书借阅数据关联规则的挖掘.pdf

图书借阅数据关联规则的挖掘 摘要 随着现代社会的不断发展，知识更新速度的加快以及各个学科之i b j 的关系同 益紧密社会对学生的知识面要求就越柬越高。作为学生、教师与外界接触的窗 口，高校图书馆显得尤为重要。它不仅方便教师、学生查阅文献，同时也是学生 在课拳之外汲取知识的另外一个重要的场所。现在几乎所有的高校都采用数掘库 技术对图书馆进行管理，其主要目的是为了方便图书馆对图书的采购、编曰及对 图书的流通进行快速、有效的管理。在图书的流通过程中产生了大量的数据， 而学生借阅信息是其中最重要的数掘之一。学生尤其是硕士研究生和博士研究生 的借阅书刊信息在一定程度上能够代表学科的发展方向和各学科之问的关联程 度。本课题的目标就是从读者的大量借阅信息中挖掘出各学科之帕j 的关联程度。 文章首先讨论了国内外数掘挖掘的发展、应用情况以及关联规则的相关理论 基础；然后根掘书馆借阅数据的特点进行数据预处理，包括数掘的导入和提取， 最终实现了事务数掘摩的建立：在此之后是基于a p r i o rj 算法及其改避算法 f p g r o w lh 的刚书借阅数扼关联胤则的实现，并针对结果分析此课题的意义及两 种算f 去f l o 优缺点。文章最后是总结与展望。 通过对图书借阅数掘关联规则的挖掘表明，程序语言类，网络浏览器类， 国际互联j 弼络类及图像识别及其装置类书籍同时被借闻的概率比较大，并且得出 了两种翁：洼诒嚷；行时蚓上的差异。实践证明，借阅数扼关联规则的挖掘在高校图 书馆数掘库应用中县有一定应用自u 景。 关键词：数据挖掘：关联规则：图书馆数据库；& o r i o r i 算法；f p - g r a w t h 算法 a s s o c l a t i 0 1 qr u l eo fb o rr o w e db o o k s a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fm o d e ms o c i e t y , u p d a t es p e e do fk n o w l e d g ea n d t h ec l o s e rr e l a t i o n sb e t w e e nd i f f e r e n ts u b j e c t s t h ed e m a n df o rk n o w l e d g et os t u d e n t s i sh i 【曲e ra n dh i 曲e ea saw i n d o wc o n n e c t i n gt h eo u t s i d ew i t hs t u d e n t sa n dt e a c h e r s ， l i b r a r yi nu n i v e r s i t yi sm o r ea n dm o r ei m p o r t a n t i ti sn o to n l yc o n v e n i e mt oc o n s u l t l i t e r a t u r e s ，b u ta l s oi sa n o t h e rp l a c et oa c q u i r ek n o w l e d g eo u t s i d eo f t h ec l a s s r o o mf o r s t u d e n t s n o wd a t a b a s et e c h n o l o g yi sa d o p t e dt om a n a g et h el i b r a r yi na l m o s te v e r y u n i v e r s i t y , w h i c h i sc o n v e n i e n tf o rb o o k sp u r c h a s e 。c a t a l o g u ea n de f f e c t i v e m a n a g e m e n to fb o o k sc i r c u l a t i o n i nt h ec i r c u l a t i o no fb o o k s ，al o to fd a t aa r e p r o d u c e d ，w h i l et h es t u d e n t s b o r r o w i n gi n f o r m a t i o ni so n eo ft h em o s ti m p o r t a n td a t a d e v e l o p m e n t a ld i r e c t i o na n da s s o c i a t i o ne x t e n to fs u b j e c t sa r er e p r e s e n t e db yt h e b o r r o w i n gi n f o r m a t i o no fs t u d e n t st os o m ee x t e n t ，e s p e c i a l l ym a s t e r sa n dd o c t o r s t h e a i mi nt h i sp a p e ri st om i n ea s s o c i a t i o nr u l e sa m o n gd i f f e r e n ts u b j e c t sf r o ml o t so f b o r r o w i n gi n f o r m a t i o n f i r s t l y a p p l i c a t i o np r o s p e c t so fd a t am i n i n ga th o m ea n da b r o a da r ed i s c u s s e d s u b s e q u e n t l y , c o r r e l a t i v et h e o r i e so fa s s o c i a t i o nr u l e sa r ep r e s e n t e d t h e nd a t ao f b o r r o w e db o o k sa r ep r e p r o c e s s e d ，w h i c hi n c l u d e sd a t a i m p o r t i n ga n dd a t ae x t r a c t i o n ， a n dt r a n s a c t i o nd a t a b a s ei se s t a b l i s h e d a f t e rt h a t a s s o c i a t i o nr u l e so fb o r r o w e d b o o k sb a s e do na p r i o r ia l g o r i t h ma n df p - g r o w t h a l g o r i t h ma r er e a l i z e d a c c o r d i n gt o t h er e s u l t s ，t h em e a n i n go ft h es u b j e c ta n dc o m p a r i s o no ft w od i f f e r e n ta l g o r i t h m sa r e a n a l y z e d f i n a l l y , c o n c l u s i o na n de x p e c t a t i o na r ed e s c r i b e d t h er e s u l t so f m i n i n ga s s o c i a t i o nr u l eo f b o r r o w e db o o k ss h o wt h a tb o o k sa b o u t p r o g r a ml a n g u a g e b o o k sa b o u tn e t w o r kb r o w s e r b o o k sa b o u ti n t e r n e ta n db o o k s a b o u ti m a g er e c o g n i t i o na r eb o r r o w e dw i t hh i g hp r o b a b i l i t ya tt h es a m et i m e t h e d i f f e r e n c e so fr u n t i m eb e t w e e na p r i o r ia l g o r i t h ma n df p g r o w t ha l g o r i t h ma r e e d u c e d i ti sp r o p o s e dt h i nm i n i n ga s s o c i a t i o nr u l e so fb o r r o w e db o o k sw i l lh a v e b r i g h tp r o s p e c t si nu n i v e r s i t yl i b r a r y k e y w o r d s d a t a m i n i n g ；a s s o c i a t i o nr u l e ；l i b r a r yd a t a b a s e ；a 研o r ia l g o r i t h m ；f p - g r o w t h a l g o r i t h m 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 掘我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含未获得! 洼；塑造直墓丝益墨挂型主塑 鲍：奎拦亘窒! 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的浣明并表示谢意。 学位论文作者签名：王朗阉签字同期：2 硒7 年6 月i r 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权傈留并向国家有 关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权学校可以将学 位论文的全部或部分内容编入有关数扼库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。f 保密的学位论文在解密后适用本授权书) 学位论文作者签名：王阴嗣 导师签字： 签字r 期：2 叩薛月f 日 签字同期： 年 月同 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 幽书 “恻数据关跌j m 则的挖掘 1 绪论 1 1 前言 随着现代社会的不断发展，知识更新的速度加快以及各个学科之日j 关系的同 益紧密，社会对学生的知识面要求也就越来越高。目酊学生在课肇上所学的知识 虽然每年都在更新，但还是跟不上社会的发展。高校图书馆作为学校学生、教师 跟外界接触的窗口，显得尤为重要。它不仅方便老师、学生查阅文献，同时也是 学生在课章之外汲取知识的另一个重要的场所。现在几乎所有的高校都采用数据 库技术对图书馆进行管理，其主要目的是为了方便图书馆对图书的采购、编目及 对图书的流通进行快速有效的管理。在图书馆的流通中，产生了大量的数掘，而 学生的借阅信息是其中最重要的数掘之一。学生尤其是硕士研究生和博士研究生 的借阅信息在一定程度上能够代表学科的发展方向和各个学科之问的关联程度。 因此基于读者借阅信息关联规则的数掘挖掘已经成为优化馆减的一个重要的环 节。 1 2 国内外研究现状 1 9 9 3 年a g r a w a r 等人首先提出了关联规则的问题，并于1 9 9 4 年提出了挖 掘关联规则的经典算法a p rj o r i 算法，后来有不少学者对关联规则问题进行了大 量的研究。比如对原有a p r i o r i 算法进行优化，如引入哈希方法、划分的思想、 随机采样等，以提高算法挖掘觇则的效率，但这些算法固有的缺陷，就是需要多 次重复扫描数掘库，而且可能产生大量的候选项集：j i a w e jh a n 等人提出的不 产生候选项集的f p g r o w t h 算法，虽然不需要生成频繁候选项目集且只需要扫 描数掘库两次，但如果大项集的数量很多，而且如果由原数掘库得到的f p t r e e 的分支很多且分支长度很长时，该算法将需要构造出数量巨大的条件f p t r e e 不仅费时而且要占用大量的空间，挖掘效率不高，而且递归算法本身效率也较低。 因为最大频繁项目集隐含了所有的频繁项目集，所以有很多学者提出了直接挖掘 壤，i 频繁项目鬟的算法，如g u n o p u l o s 等人二提出的随机算法使用了垂真位向 幽书f 吕闽数据关联胤则的挖掘 量的数掘结构来表示事务数据库，但它无法保证发现所有的最大频繁项目集： m a x m i n e r 算法。“使用水平数据库格式和宽度有限的搜索策略，可能需要多次扫 描数掘库，并且会产生许多无用的候选项目集，带来代价昂贵的i o 开销以及计 算开销；p i n c e r s e a r c h 算法”1 需要维护一个最大频繁模式的超集一最大候选集， 其代价通常也是很高；m a f i a 算法”1 是b u r d i c k 等人提出的最大频繁项目集挖掘 算法，但该算法仍需要多次重复扫描数据库：d m f 算法也需要多次重复扫描数 据库：d m f i a 算法“。只需扫描数掘路两次，但需要生成数量庞大的最大频繁候选 项目集。挖掘关联规则的挑战性在于数掘量巨大，算法的效率是关键，因此有必 要研究出占用内存小、i 0 操作少、执行速度快的高效算法。 1 3 研究目的、资料来源、分析工具 在理论上，由于高校学生逐年增长。图书馆数掘库呈指数增长，基于a p r io r i 算法的数掘挖掘在每次寻找频繁项集时，都需要扫描数掘库一次，因此随着数据 库的增大，寻找频繁项集的时间越长，系统的效率也会受到很大的影响”3 。因此， 需要采取其它的方法对a p r i o r i 算法加以改进，以便提高系统的效率。 本课题研究的主要目的及实际应用价值是针对于图书馆借阅数据库，从读者 的大量借阅信息中挖掘出各学科之间的关联关系及关联程度，从而在一定程度上 可以辅助图书馆的购书工作、教师的教学工作以及优化图书馆减布局等等。 本课题来源于数掘挖掘技术领域，是关于中国海洋大学图书馆数掘库借阅信 息关联规则算法的实现。所需的实验数掘是由中国海洋大学图书馆提供的连续五 年的借阅数据，数掘是以同志文件形式存在的。所阅文献主要是国内外的关于数 掘挖掘中关联规则方面的最新发表的论文。查阅的手段主要是通过学校图书馆的 各个工具获得一些国内的学术论文和一部分国外的学术论文，而一些比较先进但 又无法找到或者是找到但是有弄不到原文的学术论文则通过图书馆的查新中心 进行查找。 本课题研究使用了配有5 1 2 m 内存和8 0 g 硬盘的a m i ) 计算机，数掘的预处理、 关联规则的产生是在v i s u a lf o x p r o ，m i c r o s o f ta c c e s s 数掘库及m i c r o s o f t v i s u a lc 什6 0 环境下实现的。 幽j 5 f h 阀数拒共联悦则的挖据 1 4 撰写顺序及主要内容 本课题主要研究对于特定应用领域高校图书馆，对于特定问题的解决采 用知识发现技术，其中以关联规则发现为主。 本课题撰写顺序及研究内容简要介绍如下： ( 1 ) 简要介绍本课题国内外研究现状、研究目的、资料来源和分析工具； ( 2 ) 简要介绍数据挖掘的基本理论知识： ( 3 ) 详细介绍关联规则的数据挖掘，着重介绍a p r j o r i 算法及其改进的算法； ( 4 ) 以高校图书馆图书借阅为例，谇细讲述图书馆数据的预处理、数据的分 析、事务数掘库的建立、经典a p r i o r i 算法的实现以及改进算法 f p 一( ；r o w t h 的实现： ( j ) 总结全文的工作，并对数掘挖掘的发展前景进行展望。 幽书僻阅数据关联胤则的挖掘 2 数据挖掘概述 在信息爆炸的当今时代，信息过量几乎成为人人需要面对的问题。如何爿能 不被信息的汪洋大海所淹没，并从中及时发现有用的知识呢? 数掘挖掘和知识发 现是处理此类问题的有效手段f 8 】o 2 1 数据挖掘的兴起及定义 2 1 1 数据挖掘的兴起 随着社会信息化程度的提高，数据量呈指数增长。虽然我们未能给出一个准 确的数掘增长数字，但计算机硬件的发展从一个侧面反映了数据存储量的迅速增 长。1 9 8 1 年，当第一台p c 机问世时，比尔盖茨( b i l lg a t e s ) 预言：“对任 何人来说，6 4 0 k b 内存就足够了。”1 然而，为了满足数据库和多媒体信息存储 的需要，高档微机上的内存已经出乎意料地从2 0 多年6 i 的6 4 0 k b 攀升到2 g b 的水平，内存容量扩大了3 2 7 5 8 倍：硬盘容量也超过2 0 0 g b ，与2 0 多年前的 2 0 m b 比较，增大了1 0 2 3 9 0 倍。需要是发明之母，计算机存储容量的迅速提高 是为了满足数据量同益增长的社会需求。现在，条形码技术、数掘库、多媒体和 计算机网络的广泛使用使企业、政府和其他许多组织机构积累大量数据。如何从 大量数据中挖掘有价值的信息是当今信息时代的一个重要研究课题。数掘挖掘作 为自动或半自动提取有用知识的技术，为我们摆脱“数据爆炸、知识贫乏”“” 的困境找到了出路。 数掘挖掘又称为数掘库中的知识发现，出现于2 0 世纪8 0 年代后期。在 1 9 8 9 举行的第十一届国际联合人工智能会议( j j c a 8 9 ) 上，首次出现数掘库知 识发现( k n o w l e d g ed is c o v e r yi nd a t a b a s e ，即k d d j 的概念。1 9 9 3 年，a g r a w a 提出了交易数掘库中的关联规则挖掘，从此数掘挖掘在世界范围内广泛兴起。 2 1 2 数据挖掘的定义 对于数掘挖掘的定义，目前存在两种观点：一部分人认为数掘挖掘是指数据 4 l 圣l 书f h 剜敌铡关联w 则的挖掘 库中的知识发现；另一部分人则认为数据挖掘是数掘库知识发现过程中的一个处 理步骤。 根据f a y y a d 的定义：数掘挖掘( d a t am i n i n g ) 是指从数掘库中发现潜 在有用的、新颖的、可理解模式的高级处理。 从该定义可以看出，数掘挖掘是数据库知识发现过程中最核心的一个步 骤。数掘库中的知识发现包括以下四个主要步骤： ( 1 ) 原始数据的选择与清沈：根掘数据挖掘的目的，确定需要挖掘的数掘，并对 原始数据( r a wd a t a ) 中的噪声和遗失值进行处理。 ( 2 ) 数掘变换：为了满足数掘挖掘算法的需要，对数据的表示形式或数掘柿局进 行变换，如对连续型数值属性进行离散化，将数据的水平布局变换为垂直征 局等。 ( 3 ) 数掘挖掘：利用特定的算法从数掘中提取知识，知识的表示形式包括概念j ； 规则和模式。 ( 4 ) 模式评估：评价知识的重要性、置信度和有趣度等，对模式进行解释，评估 模式的合理性和可用佳。 幽2 - 1知识发现的过程 可见，数掘挖掘只是数掘库知识发现过程中的一个重要步骤。它是利用确定 的算法从准备好的数据中挖掘或提取有用知识的过程。数据挖掘是知识发现中最 核一b 的部分。然而盘通常情况。f ，人们对数掘挖掘与知识发现的概念不进行严格 踮阳一 蝴b l ! j 书f h 阿敌捌共联w 则的挖掘 区分。 2 2 数据挖掘的功能 总体来讲，根掘数据挖掘发现的模式类划可以将其分两种：描述性数掘挖 掘和预测性数掘挖掘。描述性数掘挖掘意在刻画数掘的特性和特征。预测性数据 挖掘任务在当自# 数据上进行推断，以进行预测。另外，数据挖掘能够发现各种位 于不同抽象层的模式。这些数据模式由不同的视角为用户提供领域的知识，为用 户聚焦有趣模式的搜索带来了方便。具体柬讲，数据挖掘功能大略可以归纳为6 种：概念描述、关联分析、分类和预测、聚类分析、异类分析和演化分析，下面 分别简述此6 种功能【。 ( 1 ) 概念描述( c o n c e p td e s c r i p t i o n ) 一个概念常常是对一个包含大量数据的数据集合总体情况的概述。对含有大 量数掘的数掘集合进行概述性的总结并获得简明、准确的描述，这种描述就称为 概念描述。获得概念描述的方法主要有以下两种： 利用更为广义的属性，对所分析数据进行概要总结，其中被分析的数据 就称为目标数据集。 对两类所分析的数据特点进行对比并对对比结果给出概要性总结，而其 中两类被分析的数据集分别被称为目标数掘集和对比数据集。 ( 2 ) 关联分析f a s s o c i a t i o n a n a l y s i s ) 关联分析就是从给定的数掘集中发现频繁出现的项集模式知识( 又称为关联 规则a s s o c i a t i o nr u l e s ) 。关联分析广泛应用于市场营销、事务分析等应用领域。 在大型数掘库中，存在很多关联规则，对用户来说其中有些是有用的，而有 些则是无用的，因此需要进行筛选。在实际进行关联规则数据挖掘时，一般用支 持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 两个阈值来淘汰那些无用的关联规则。 近年柬，关联数据挖掘研究方兴未艾，提出了许多高效的关联规则数掘挖掘算法。 ( 3 ) 分类和预测( c l a s s i f i c a t i o na n dp r e d i c a t i o n ) 6 幽1 5 俏蒯数据关联规则的挖掘 分类就是找出一组能够描述数掘集合典型特征的模型( 或函数) ，以便能够 分类识别未知数据的归属或类别，即将未知事例映射到某种离散的类别之一。分 类模型( 或函数) 可以通过分类挖掘算法从一组训练样本数据( 其类别归属己知) 中学习获得。分类挖掘所获得的分类模型可以采用多种形式加以描述输出。其中 主要的表示方法有：分类规则、决策树、数学公式和神经网络1 5 】。 分类通常用于预测未知数据实例的归属类别( 有限离散值) ，如一个银行客 户的信用等级是属于a 级、b 级还是c 级。但在一些情况下，需要预测某数 值属性的值( 连续数值) ，这样的分类就被称为预测。尽管预测既包括连续数值 的预测，也包括有限离散值的分类。但一般还是使用预测柬表示对连续数值的预 测，而使用分类来表示对有限离散值的预测。 ( 4 ) 聚类分析( c l u s t e r i n g a n a l y s i s ) 聚类分析与分类预测方法明显不同之处在于，后者所学习获取分类预测模型 所使用的数掘是己知类别归属，属于有教师监督学习方法，而聚类分析( 无论是 在学习还是在归类预测时) 所分析处理的数据均是无类别归属，类别归属标志在 聚类分析处理的数据集中是不存在的。究其原因很简单，它们原来就不存在，因 此聚类分析属于无教师监督学习【1 6 1 方法。 聚类分析中，首先需要根掘“各聚集内部数掘对象问的相似度最大化和各聚 集对象间相似度最小化”的基本聚类分析原则，以及度量数掘对象之间相似度的 计算公式，将聚类分析的数掘对象划分为若干组。因此一个组中数掘对象间的相 似度要比不同组数掘对象问的相似度要大。每个聚类分析所获得的组就可视为是 一个同类别归属的数据对象集合，更进一步从这些同类别数据集中，又可以通过 分类学习获得相应的分类预测模型。此外通过反复不断地对所获得的聚类组进行 聚类分析，还可以获得仞始数据集台的层次模型。 ( 5 ) 异类分析( o u t l i e r a n a l y s i s ) 一个数扼库中的数据一般不可能都符合分类预测或聚类分析所获得的模型。 那些不符合由大多数数据对象所构成的规律的数掘对象就被成为异类。以前许多 数掘挖掘方法都在证式进行数掘挖掘之i “就将这些异类作为噪声或意外而排除 幽书甜蒯数掘关联埘则的挖掘 在数掘挖掘的分析处理范围之外。但在一些应用场合，如各种商业欺准行为的自 动检测小概率发生的事件往往比经常发生的事件更有价值。对异类数掘的分析 处理通常就称为异类挖掘。 数据中异类可以利用数理统计方法分析获得，即利用己知数掘所获得的概率 统计分御模型，或利用相似度计算所获得的相似数掘对象分布，分析确认异类数 掘。而偏离检测旧就是从数据已有或期望值中找出某些关键测度显著的变化。 ( 6 ) 演化分析( e v o l u t i o n a n a l y s i s ) 数据演化分析就是对随时间变化的数据对象的变化规律和趋势进行建模描 述。这一建模手段包括：概念描述、对比概念描述、关联分析、分类分析、时间 相关数据分析等。 在数掘挖掘的上述6 种功能中，当前研究较多也较为成熟的是关联分析， 它是由r a k e s ha g r a w a l 等人在文献中首先引入的。关联分析是指从给定的数据 集中发现关联规则，这些规则反映了大量数据中项目集之间有趣的关联或相关联 系。 2 3 数据挖掘的应用领域与发展趋势 2 3 1 应用领域 当日u 数据挖掘应用主要集中在电信、零售、银行、保险、基因工程、网络r 志分析等方面，并逐步扩展到制造业、农业、电子政务、教育、软件工程、智能 交通和军事研究等领域”，以下通过一些具体的例子加以说明。 1 零售业中的客户购买行为分析：这种应用最早出现在美国，超市利用数据挖 掘从售货数掘记录中发现购买商品的关联特性。利用数据挖掘得到的知识柬调整 关联商品的摆放位置，既方便了顾客，又促进了销量。在线购物活动中，通过提 醒顾客是否购买关联商品同样也促进了销量。b e r r y 和l i n o f f l “对零售业数 据挖掘和客户关系管理进行了专门研究。 2 银行信用卡业务智能数掘分析：例如美国花旗银行( c i t i b a n k ) 利用数掘挖 幽* f h 闻故摧共联w 则的挖掘 掘获得的知识区分顾客信用等级有效地减少了恶性透支，每年避免了十几亿美 元损失。 3 电信业务中的通话记录分析：电信公司或呼叫中心通过挖掘大量通话记录， 能找出电话呼叫方是谁、被叫方是谁、通话时间有多长、电话线是否同时支持传 真和语音等细节信息。客户服务呼叫中心能利用这些信息以及客户资料挖掘有价 值的增值服务模型。这对于面向特定客户进行服务或设备销售而言是非常有用 的。c h e n 等人报道了在数据仓库框架下的可伸缩电信串联传输分析方面的工作。 4 基于时序数掘挖掘的预测：政府高层、企业决策者需要对不同级别的宏观经 济数掘分析，通过时序数掘库和基于时序的数掘挖掘预测未来的经济走势，进行 计算机辅助智能决策”。 5 电子信息的防伪检测：电子商务和电子政务系统通过训练的模式知识自动地 辨别信息真伪，防止电子帐单和印鉴等电子信息的伪造。c h a n 等人研究了基亩二 分布式数据挖掘的信用卡防卫检测。 6 计算机网络入侵监测系统：网络安全管理部门利用数据挖掘发现的知识检测 黑客程宇的入侵。在信息系统的安全管理中，采用基于规则集的访问控制技术结 台系统f 1 志文件，借助数掘挖掘技术能检测出未授权用户对受保护数掘的非法访 问。 7 面向提高服务质量的w e b 结构重组：通过挖掘w e br 志发现用户坊问行 为知识，重新组织w e b 结构，提高服务质量。 总之，数掘挖掘能应用于众多领域。概括起来，可以将数掘挖掘应用归纳为 客户关系管理、智能数据分析、智能决策、防伪检测、入侵检测等类型。 2 3 2 发展前景 人类已经步入信息时代，面对数据爆炸，如何快速有效地获得最有价值的信 息资源，成为企业在激烈竞争中取胜的关键。因此，与数据挖掘相关的技术和工 具将面临很好的发展i 口景。美国权威高科技市场调查机构加特纳公司( ( ；a r t n e r ) 的研究表明，“随着数掘捕获、传输和存储技术的快速发展，大型系统用户将更 望兰堂塑鍪塑兰壁里型竺堡塑一 多地需要采用新技术来挖掘市场以外的价值”。在财富5 0 0 强企业中，其中8 2 的企业购买了数掘挖掘产品b o ( 业务对象) ，实现了企业的商务智能( b u s i n e s s i n t e l 】i g e n o e b i ) 】。数掘挖掘将成为继互联网之后的下一个研究热点，特别 是高维、大型、分布式数掘挖掘将具有广阔的应用酊景和巨大的潜在经济价值。 其中，分类预测技术作为智能决策的重要手段将在未来的商务智能中发挥重要作 用。 邕书f h 恻敬拒丢联i 弛刚的挖掘 3 关联规则理论基础 关联规则( a s s o c i a t i o nr u l e s ) 的概念首先由r a g r a w a l 等于1 9 9 3 年提 出的，是反映一个事物与其他事物之间的相互依赖性或相互关联性。“。利用最有 影响的挖掘单维单层布尔型关联规则频繁项集的a p r i o r i 算法，生成频繁项集 从而产生关联规则。同时对关联规则挖掘算法的不断改进，使关联规则理论得到 了更广泛的应用。 3 1 关联规则的基本概念及参数 ( 1 ) 关联规则 设d 是事务集，i = ，l 。，i 。 是d 中全体项组成的集合，其中l 。( k = l ， 2 ，j i ) 称为项，包含k 个项的项集称为k 一项集。一个事务t ( t r a n s a c t i o n ) 是一个项集，它是i 的一个子集，每个事务都与一个唯一标识符t i d 相联系不 同的事务起组成了事务集d ，它构成了关联规则发现的事务数掘库( t r a n s a c t i 0 一n d a t a b a s e ) 。若x ，y 为项目集，且xny = 0 ，则蕴涵式x = y 称为关联规 则。 ( 2 ) 支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 关联规则表示为：x = y 的蕴涵式，这罩x c i ，y c i ，并且x n y = o 。d 中 的规则x = y 是出支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 来约束的。支持度 表示规则出现的频度，置信度表示规则的强度。具体描述是二 刚耻叫x - r 户跚l 斌f x u y 目】( ) ( u y ) ( 3 1 ) c 。n r i d e n c e ( xj y ) ：s u p p o r t ( x = u _ y ) 1 0 0 ：p ( y x ) f 3 2 ) s u p p o n ( 入l ( 3 ) 最小支持度与最小置信度 有媚户或领域专家设定的支持度和置信度的门槛值，当s u p p o n ( x = y ) 、 c o n f i d e n c ef x = y ) 分别大于等于各自的门槛值时，认为x = y 是有趣的，此两 幽书f h 蝴数据关联心则的挖掘 值称为最小支持度( m i n s u p ) 和最小置信度( m i n _ c o n f ) 。 ( 4 ) 项集( i t e m s e t ) 、k - 项集和频繁项集( f r e q u e n ti t e m s e t ) 若干项的集合，称为项集。项集中所包含的项的个数称为项集的长度，长度 为k 的项集称为k 项集。包含项集的事务数，称为项集的频率或支持计数。 当项集的支持计数大于或等于m i n - s u p 与d 中事务总数i d l f l 9 乘积时，称为频 繁项集( f r e q u e n ti t e m s e t ) ，当项集的支持计数可能大于等于m i n _ s u p i d i 时， 称为候选项集。 所有频繁k 项集的集合常记作l k ，所有候选k 。项集的集合记作c k ，显然 l kc c k 。 ( 5 ) 相关分析 大部分关联规则挖掘算法使用支持度置信度框架，虽然这一框架排除了相 当一部分无趣规则，但仍会产生一些无趣规则。 相关性【2 6 度量的定义： correlation=一p(x u y ) 旦墨盟 ( 3 3 ) j p ( x ) j d ( 】，) p ( y ) 若上式的值等于1 ，则x 和y 相互独立( 没有相关性) ：若值小于1 ，则x 和y 是负相关的：若值大于1 ，则x 和y 是正相关的( 一个的出现蕴涵另一个的出现) 。 3 2 关联规则的算法 a p r i o r i 算法是a g r a w a l 等人在提出算i ! $ a i s 和s e t m ”之后提出的一种改进 算法，它是最为典型的一种层次算法，其核心技术被其他各类布尔关联规则挖掘 算法所广泛采用。 3 2 1a p t i o r i 算法 关联规则是指大量数据中项集之问存在的有趣的关联或相关联系。a p r i o r i 算法是挖掘关联规则的一个重要方法一一个基于两阶段频繁集的方法懈3 ，将关 剧书惴脚数据共联埘则的挖掘 联规则挖掘算法分解为两个子问题 ( 1 ) 求出事务集d 中满足最小支持度m i n s u p 的所有频繁集 ( 2 ) 利用频繁集生成满足最小可信度m i n c o n f 的所有关联规则。 其中第一个问题是算法的关键，a p r i o r i 算法是基于频繁集理论的递推方法 柬解决这一问题，也就是一种称作逐层搜索的迭代方法。根扼上述两个关键步 骤，a p r i o r i 算法具体可以理解为：首先。找出1 一频繁项集的集台，该集台记 作l 。l 用于找出：一频繁项集的集台l = ，而l ? 用于找出k 如此下去，直到找 不到k 一频繁项集。找每一个l l 需要扫描一次数据库：其次，设置不同的最小支 持度和最小可信度，发现有用的关联规则。该算法利用频繁集的两个性质，即任 一频繁集的子集都是频繁集，若某一项集不是频繁集，则其超集也不是频繁集， 采用的“从小到大”逐步迭代的方法产生频繁集”，而且它是一种验证型的方法， 但是该方法运行时间很大。 现将算法a p r i o r i 详细描述如下： 算法：( a p r j o r i ) 利用层次循环发现频繁项集 输入：事务数掘库d ，最小支持闽值m i n s u p 输出：d 中的频繁项集l 处理流程： ( 1 ) l , = f i n d f r e q u e n t j j t e m s e t ( d ) ：发现卜项集 ( 2 ) f o r ( k = 2 ：l o ：k 十+ ) ( 3 ) c 【= a p r i o r i g e n ( l 。，m i n s u p ) ： 根掘频繁( k - 1 ) 一项集产生候选k 一项集 ( 4 ) f o re a c ht d 扫描数据库，以确定每个候选项集的支 持频度 ( 5 ) c 。= s u b s e t ( c 。t ) ：获得t 所包含的候选项集 ( 6 ) f o re a c hc c c c o u n t * + ： i 圣| 书僻恻敬据关联w 则的挖掘 ( 8 ) l f c c 。：c e o u n t m j i qs u p p r o c e d u r ea p r i o r i g e n ( l h ，r a i n s u p ) ( 3 ) i f ( 1 。 1 = 1 ： 1 ) a ( 1 。 k - 2 = 1 = k - 2 ) 人( 1 k - 1 1 ) = 2 3 = 6 7 与最小可信度6 5 相比，只由后两个规则满足条件，所以输出关联规则 1 6 幽书f 蒯数据关联脱刚的挖掘 1 a 3 2 和2 a 3 1 。 使用此方法，存在定的缺点4 。： 可能产生大量的频繁集：当长度为1 的频繁集有1 0 0 0 0 个时，长度为2 的候 选集个数将会超过1 0 0 0 万。此外如果要生成一个很长的规则时。要产生的中问 元素的数量也是巨大的。因此提出了可以有效地解决上述问题的方法一一 f p g r o w t h 方法。 3 2 2 f p g r o w t h 算法 在许多情况下，a p r i o r i 的频繁集产生检查方法大幅度压缩了频繁集的大 小，并导致很好的性能。但还存在一些固有的缺点： ( 1 ) 可能产生大量频繁集。 ( 2 ) 可能需要重复扫描数掘库，通过模式匹配检查一个很大的频繁集。 采用频繁模式增长( f r e q u e n t p a t t e r ng r o w t h ) ，即f p - g r o w t h ，可以有效 地解决上述问题。算法的主要思想是采取如下分治策略”“：将提供频繁集的数据 库压缩到一个频繁模式树( 或f p 一树) ，但仍保留项集关联信息；然后，将这种 压缩后的数掘库分成一组条件数掘库( 种特殊类型的投影数据库) ，每个关联 一个频繁数掘项，并分别挖捌每个数据库。 f p t r e e 是如下的一种树结构： ( 1 ) 它由三个部分组成：标记为空结点( n u l l ) 的根作为根的儿子的项目 前缀子树( it o mp r e f i xs u b t r e e s ) 集合频繁项头表( f r e q u e n ti t e mh e a d e r t a b l e ) ： ( 2 ) 项目前缀子树中的每一个节点由三个域组成。：项目名( i t e m 一1 3 a m e ) 支持计数( c o u n t ) 节点链( n o d e - i n k ) 。其中，项目名表示节点代表哪个项目， 支持计数表示包含到本节点为止的路径( 即频繁项目集) 的事务数，节点链指向该 结点在f p t r e e 中第一次出现时的位置代表相同项目的下一个节点( 无节点可 链时为空) ； 例书僻蒯数据关联规则的挖掘 ( 3 ) 频繁项头表的每个条目包含三个域：项目名( i t e m - n a m e ) 支持度计 数( c o u n t ，该项目总的支持度计数) 节点链的头指针( n o d e 一1 i n k ) ，指向该项 目在模式树中的第一次出现位置。 下面给出构造f p - t r e e 的算法的详细描述。 算法：构造f p t r e e 输入：事务数据库d ，最小支持数 输出：f p - t r e e 过程： ( 1 ) f o re a c ht r a n s a c t i o nti nd ( 2 ) ( 3 ) f o re a c h i t e mxi nt ( 4 ) 从c l 中找到与x 同名的候选项c ，使c 的支持度计数加l ：说明： c 】为候选卜频繁项集的集合。 ( 5 ) ( 6 ) 选取c 1 中支持度计数大于；的项，得到卜频繁项目集f ，按支持度计 数降序排列f 得到l ； ( 7 ) 创建树根r o o t ，标记为n u l l ；开始建树 ( 8 ) f o re a c ht r a n s a c t i o nti nd ( 9 ) ( 1 0 ) 选取t 中频繁项目，并按l 的顺j 芋排列，记为 p l p ，其中p 为第一个 元素，p 为余下元素的列表： ( 1 1 ) l n s e r t t r e e ( p 【p ，r o o t ) ： ( 1 2 ) | 芏| 书f 吕i 嘲数拒共联j 观则的挖掘 说明：过程的( 1 ) 一( 6 ) 句通过扫描次事务数掘库得到1 一频繁项集l ；从( 7 ) 开始创建f p t r e e 。( 8 ) 一( 1 2 ) 通过再次扫描事务数据库来构建f p t r e e 。 p r o c e d u r ei n s e r t t r e e ( pp ，r o o t ) ( 2 ) 如果r o o t 有儿子n ，使得n i t e m n a m e = p i t e m n a m e 那么n c o u r t + + ( 3 ) 否则 ( 4 ) 创建新节点n ( 7 ) 将n n o d e l i n k 链到头表中与它同名的项或树中与它同名的项 ( 8 ) 如果p 非空，那么 ( 9 ) ( 1 0 ) 把p 的第一个元素赋值给p ，并把它从p 中删除 ( 1 2 ) ( 1 3 ) 过程结束 分析：f p t r e e 构造算法刚好扫描两次事务数掘库：第一次扫描生成频繁卜项 目集；第二次扫描实现构造f p t r e e 。 输入：由算法l 生成的f p t r e e ：最小支持度阈值m i n s u p 输出：频繁模式的完全集 方法：调用f p g r o w t