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

y 6 5 4 0 9 6 四川大学硕下 1下 学位论文 ( 2 0 0 4 ) 关联规则挖掘算法的研究和设计 计算机应用专业 研究生冯 雯指导教师吕光宏 教授 摘要 进入九十年代以 来，随着网络技术的发展以 及各种各样的 i n t e rn e t 应用的出 现， 全球i n t e rn e t 业务呈现一种爆炸式增长的趋势， 使得人 类积累的数据量正在以 指数速度迅速增长。因此，迫切需要一种能够智能化地、自 动地把数据转换成有 用信息和知识的技术与工具一一 数据挖掘 ( d a t a m i n i n g , d m) 便诞生了。 “ 啤 酒搭着尿布卖” 的经典故事引出 了数据挖掘中 关联规则 挖掘的 无穷 作用。 挖掘关联规则就是发现对象之间的相关性，成为人们可 以利用的知识。生成事务 数据库的 频繁集是关联规则挖掘的关键，其中 著名的 算法有a p r i o r i 和f p - g r o w t h ( f r e q u e n t p a tt e r n g r o w t h , 频繁模式 增长 ) 等 算法。 但是它们得到的 频繁集并不是 最优:同时对于事务数据库中的数据，如果具有很强的可划分性 ( 可划分性是指 在每个划分之间具有低相似度而在同一个划分内部具有高相似度的性质) ， 那么即 使此类算法只是经过对最后生成的频繁集处理使得没有冗余，但是它的效率也不 是最好，于是本文在对已有算法深入研究后提出一点自己的想法。首先对事务数 据库 进 行 分 类; 然 后在 每 个划 分 上 面 进 行频 繁 模 式 树 f p -t r e e ( f re q u e n t p a tt e r n t r e e ,频繁模式树)的构造和利用频繁模式增长算法f p - g r o w t h ( f r e q u e n t p a t t e rn g r o w t h ， 频繁 模式增长) 产生频繁集; 最后对结果进行一个修剪和合并， 得到最 优 结果。同时本文也给出了通过编程测试此算法和 f p - g r o w t h算法的性能，并作比 较。 第二章主要研究关联规则中 的基本概念， 同时分析由a g r a w a l 等人提出的 最 著名的a p r i o r i 频繁集产生 算法的 原理， 它是一种需 要计算频繁候选集的 算法。 计 算 项目 集 的 支 持 度是 发 现频 繁 项目 集 中 最 耗 时 的 工 作 ， 因 此， a p r io r i 算 法 具 有 一 定的局限性，而降低候选项目 集的数量是减小开销的最好手段。 本文第三章是重点，首先分析和研究了 f p - g r o w t h算法，它从根本上改进了 四川大学硕:i : 学位论文 ( 2 0 0 4 ) a p r i o r i 算法的缺点， 是一 种不产生 频繁 候选集的 关联规则挖掘 算法。 然后在 此基 础上，根据作者的理解和研究，总结出了 f p - g r o w t h算法还有些不足，提出基于 f p - g r o w t h 的新算法。 文中给出了 新算法的 理论依据，以 及整个 算法的思 路。 第四章， 编程实现利用本文提出的新算法来挖掘频繁集的整个过程，同 时实 现了著名的f p - g r o w t h算法，以便两种算 法挖掘同一 个测试数据库进行相应的测 试。 其中本文给出了实现过程中定义的数据结构和部分核心源代码， 并做了注释。 第五章，主要对本文提出的新算法和 f p - g r o w t h算法从存储空间和运行时间 以及结果的最优性三个方面进行比较，总结出本文提出的新算法的优点。 第六章，总结。提出新算法的不足之处和可以做的一些改进，结束全文。 目 前数 据挖掘技术在国 外应用非常广泛， 但是国内在这方面的 发展相对缓慢。 作者在对本文提出 和研究的各 种算法进行比 较和测试， 这些工作也只是对数据挖 掘进行一个简单而浅显的研究，希望在今后的工作中更加深化和具体的分析和研 究。 关键字: 关联规则、 频繁 集 ( 频繁模式) 、 频繁模式树、 频繁候选集 四川大学硕_ t : 学位论文 ( 2 0 0 4 1 s t u d y a n d d e s ig n o n t h e a lg o r i t h m s o f min i n g a s s o c i a t io n r u le s ma j o r : c o m p u t e r a p p l ic a t i o n p o s t g r a d u a t e : f e n g we n d i r c i t o r : p r o f l u g u a n g h o n g abstract w i t h t h e d e v e l o p m e n t o f a l l k i n d s o f n e t w o r k t e c h n o l o g i e s a n d a p p l i c a t i o n s o f i n t e r n e t s i n c e 1 9 9 0 s , t h e g r o w t h o f i n t e r n e t t r a f f i c h a s b e e n i n c r e ase d b y t h e s p e e d o f e x p o n e n t . i n c o n t r a s t t o t h e r a p i d g r o w t h o f i n f o r ma t i o n o n t h e w e b , a n e ff e c t i v e me a n s t o s t o r e t h e k n o w l e d g e , o r g a n i z e k n o w l e d g e d i s t r i b u t e d o n t h e i n t e rne t , a n d s h a r e k n o w l e d g e i s r e q u i r e d u r g e n t l y - - - - - - t o c o m e i n t o b e i n g t h e d a t a m i n i n g ( d m) . t h e c l a s s i c a l s t o r y , s e l l i n g b e e r s w i t h u r i n a ry c l o t h s , r e s u l t i n t h e p o w e r f u l f u n c t i o n o f mi n i n g as s o c ia t i o n r u l e s i n d a t a mi n i n g . mi n i n g a s s o c i a t i o n r u l e s wi l l l o o k f o r t h e c o r r e l a t i o n s o f t h e o b j e c t s a n d r e f i n e i t i n t o t h e u s e f u l k n o w l e d g e . t h e k e y t a s k i s f o r mi n i n g a s s o c i a t i o n r u l e s h o w t o c r e a t e t h e f r e q u e n t s e t s . b a s e d o n t h e f p - g r o w t h ( f r e q u e n t p a t t e rn g r o w t h ) a l g o r i t h m s , a n i m p r o v e d a l g o r i t h m i s g i v e n i n t h i s t h e s i s . f i r s t l y , t h e b u s i n e s s d a t a b a s e i s c l a s s i f i e d i n t o s o m e s u b g r o u p s a c c o r d i n g t o s o m e r u l e s . t h e n , t h e f r e q u e n t p a tt e rn t r e e i s c r e a t e d a n d t h e f re q u e n t p a t t e rn i s f o r me d i n t h e e a c h s u b g r o u p s . f i n a l l y , t h e i m p r o v e d r e s u l t s a r e o b t a i n e d . o n t h e o t h e r h a n d , t h e n e w a l g o r it h m i s c o m p a r e d w i t h f p - g r o w t h i n t h e p e r f o r m a n c e . i n c h a p t e r 2 , t h e b a s i c c o n c e p t s a n d t h e a p r i o r i a l g o r i t h m o n mi n i n g a s s o c i a t i o n r u l e s i s i n t r o d u c e d . t h e a p r i o r i a l g o r i t h m r e q u i r e s t o c o m p u t e t h e c a n d i d a t e s o f t h e f r e q u e n t p a t t e r n s o t h a t a l o t o f t i m e i s w a s t e d i n c o m p u t i n g t h e c a n d i d a t e o f t h e fr e q u e n t p a t t e rn. i n c h a p t e r 3 , t h e f p - g r o w t h a l g o r i t h m i s a n a l y z e d a n d o v e r t h e a p r i o r i a l g o r it h m i n t h e p e r f o r m a n c e . f o r t h e a l g o r i t h m, i t i s n o t r e q u i r e t o c o mp u t e t h e c a n d id a t e s o f t h e fr e q u e n t p a t t e rn. b ase d o n t h e f p - g r o w t h a l g o r i t h m , a n e w a l g o r i t h m i s p u t f o r w a r d a n d i s c o m p a r e d w i t h t h e f p - g r o w t h a l g o r i t h m . hi 四川人学硕 i万 学位论文 ( 2 0 0 4 ) i n s u c c e s s i o n c h a p t e r , t h e n e w a l g o r i t h m i s p r o v e d t h a t h a s s o me i m p r o v e m e n t o n t h e a b o v e - m e n t i o n e d a l g o r i t h m s b y r u n n i n g t h e t e s t p r o g r a m. a t p r e s e n t , t h e d a t a mi n i n g h as b e c o m e t h e h o t - t o p i c . t h e m o d i f i e d a l g o r i t h m i n t h i s t h e s i s i s a n o n l y b e g i n n i n g o n d a t a mi n i n g , m o r e w o r k s w i l l b e d o n e i n t h e f u t u r e . k e y w o r d s:a s s o c i a t i o n r u l e , f r e q u e n t p a tt e r n , f r e q u e n t p a t t e rn t r e e , t h e c a n d i d a t e s o f t h e f r e q u e n t p a t t e r n w 四川大学硕十学位论文 ( 2 0 0 4 ) 第一章绪论 1 . 1 数 据挖掘概述 随 着数据库技术的 成熟和 数据应用的普及， 人类积累的数据量正在以 指数速 度迅速增长。进入九十年代，伴随着因特网 ( i n t e r n e t )的出现与发展，以及随之 而来的企业内部网 ( i n t r a n e t )和企业外部网 ( e x t r a n e t )以及虚拟私有网 ( v p n v i r t u a l p r i v a t e n e t w o r k ) 的 产生和 应用， 将 整个世界联成一个小小的地球村， 人们 可以跨越时空地在网上交换数据信息和协同工作。这样，展现在人们面前的己不 是局限 于本部门、本单位和本行业的 庞大数 据库，而是浩瀚无垠的信息海洋，数 据洪水正向 人们滚滚涌来。当 数据量极度增长时，如果没有有效的方 法，用计算 机及信息技术来提取有 用信息和知识， 人们也会感到面对信息海洋像大海捞 针一 样束手无策。 据估计，一个大型企业数据库中的 数据，只有百分之七得到很 好应 用。 这样 ， 相对于“ 数据过剩” 和“ 信息爆炸” ， 人们又感到“ 信息贫乏 ” ( i n f o r m a t i o n p o o r ) 和“ 数据关在牢笼中” ( d a t a i n j a i l ) ， 正如奈斯伯特( j o h n n a i s b e t t ) 惊呼 “ w e a r e d r o w n i n g i n i n f o r m a t i o n , b u t s t a r v i n g f o r k n o w l e d g e ( 人 类正被数据淹没， 却饥 渴于知识) 。 面临浩渺无际的 数据，人 们呼唤 从数 据汪洋中 来一个去粗存精、 去伪存真的 技术和工具，也就是从数据库中发现知识( k d d, k n o w l e d g e d i s c o v e r y i n d a t a b a s e s ) 。这样， 数据挖掘( d m, d a t a m i n i n g ) 便应运而生了。 1 9 9 8 年，在美国纽约举行的第四届知识发现与数据挖掘国际学术会议上，不 仅进行了学术讨沦， 并且有 3 0 多家软件公司展示了他们的数据挖掘软件产品， 不 少软件已在北美、欧洲等国得到应用。实际上，数据库中的知识发现是一门交叉 性学科， 涉及到机器学习、 模式识别、统计学、智能数据库、知识获取、数据可 视化、 高性能计算、 专家系 统等多 个领域。内 容极为广泛， 理论和技术难度很大， 从而使 针对大型数据库的k d d ( k n o w l e d g e d i s c o v e r y i n d a t a b a s e s ， 知识发现 ) 技术 一 时 还 难以 满 足 应 用 需 要。 于 是， 1 9 9 5 年 美国 计 算 机 会 a c m , a m e r ic a c o m p u te r m e e t i n g ) 会议提出了 数据挖掘的概念， 它形象地把大型数据库看成是存放有价值 信 息的 矿藏， 通过有效的知识发现技术，从中挖掘或开采出 有用的 信息。 k d d最核心的部分是采用机器学习、 统计等方法进行知识学习的阶 段， 即数 i 四川大学硕j : 学位论文 ( 2 0 0 4 ) 据挖掘。 所谓 数据挖掘 ( d a t a min i n g ) ， 就是 从大量的、 不完全的、 有噪声的、 模 糊的、 随机的 实际 应用数据中，提取隐含在其中的、 人们事先不知道的、 但又是 潜在有用的信息和知识的过程。 何 为知识 ? 从 广义上理解， 数据、 信息也是知识的 表现形 式， 但是人们更把概 念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的源泉， 好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据库中的数 据;也可以是半结构化的，如文本、图形和图像数据;甚至是分布在网络上的异 构型数据。 发现的知 识可以被 用于信息管理、 查询 优化、 决策支持和过 程控制等， 还可以 用于数据自 身的维护。因此， 数据挖掘把人们对数据的应用从低层次的 简 单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了 不同 领域的 研究者， 尤其是 数据库技术、 人工智能技术、 数理统计、 可视化技术、 并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域， 形成新的技术热点。 知识发现 ( k d d )是从数据中识别有效的、 新的、 有潜在使用价值的、可 被 理解的模式的过程。数据挖掘是数据库中知识发现的一个步骤，但它是最关键的 一步。一般在研究领域被称作数据库中知识发现的，在工程领域则称之为数据挖 掘。 但是某些地方也可以不加区别地使用 k d d和数据挖掘。目前大多数的研究都 集中 在数据挖掘算法和 应用上。 1 . 1 . 1数据挖掘的任务和基本 模式 1 .数据挖掘的任务 数据挖掘的任务是从数据中发现模式。模式是一个用语言 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 0 0 4 ) 2 .不同的挖掘任务使用不同的挖掘模式 由于每一种数据挖掘技术都有其 自身的特点和实现的步骤，对数据的形式有 具体的要求，并且与具体的应用问题密切相关，因此成功的应用数据挖掘技术以 达到目 标过程本身就是一件很复杂的事情，下面主要从挖掘任务和可获得的数据 两个角度来讨论对具体数据挖掘模式的选择。 根据挖掘任务，数据挖掘可分为概念描述、聚集发现、关联规则发现、分类 发现、回 归发现和序列模式发现等。 在选择使用某种数据挖掘技术之前，首 先要 将待解决的商业问题转化成正确的数据挖掘任务，然后根据挖掘任务来选择具体 使用某一种或几种挖掘模式。下面具体的分析每一种挖掘任务应使用哪些挖掘模 式。 1 )概念描述 概念描述是描述型数据挖掘的最基本形式。它以简洁汇总的形式描述给定的 任务相关数据集，提供数据的有趣的一般特性。通常，用户指定类的数据通过数 据库查询收集。例如，为研究土一年销售增加 1 0 6 的软件产品的特征，可以通过 执行一个 s q l查询收集关于这些产品的数据。数据特征的输出可以用多种形式提 供，包括饼图、条图、曲线、多维数据立方体和包括交叉表在内的多维表。进行 概念描述挖掘时一般采用面向数据库的方法，另外还可以采用机器学习方法的基 于范例学习 技术。与机器学习 方法相比，面向数据 库的概念描述导致在大型数据 库和数据仓库中的有效性和可伸缩性。 2 ) 聚集发 现 聚集是把整个数据库分成不同 的群组。 它的目 的是 要群与群之间 差别很明显， 而同一个群之间的数据尽量相似。与分类不同，在开始聚集之前你不知道要把数 据分成几组， 也不知道怎么分 ( 依照哪几个变量) 。 因此在聚集之后要有一个对业 务很熟悉的人来解释这样分群的意义。很多情况下一次聚集你得到的分群对你的 业务来说可能并不好，这时你需要删除或增加变量以影响分群的方式，经过几次 反复 之后才能最终得到一个理想的结果。聚集在电 子商务上的典型应用是帮助市 场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同客户 群的特征。 此外聚类分析可以 作为其它算法 ( 如特征 和分类等)的预处理步 骤， 这些算法再在生成的簇上进行处理。 3 )关联规则发现 关联分析是寻找在同 一个事件中出 现的不同 项的相关性，比如 在一次 购买活 四川人学硕十学 位论文( 2 0 0 4 ) 动中所买不同 商品的相关性。 序列模式与此类似， 它寻找的是事件之间时间上的 相关性， 如对股票涨跌的分 析。 以市场货 篮这 个典型 例子分析关联规则。 “ 在购买 面包和黄油的顾客中，有 9 0 % 的人同时也买了牛奶”( 面包+黄油分牛奶) 。用于 规则发 现的 对象主要是事务型 数据库，分析的是售货数据， 也称货篮数据。关联 分析是目前是数据挖掘中应用最广泛的一种，它具有一定的研究价值。 4 )分类发现 分类要解决的问题是为一个事件或对象归类。设有一个数据库和一组具有不 同特征的类别 ( 标记) ，该数据库中的每一个记录都赋予一个类别的标记，这样的 数据库称为示例数据库或训练集。 分类分析就是通过分析示例数据库中的 数据， 为每个类别做出 准确的描述或建立分析模型或挖掘出 分类规则， 然后用这个分类 规则对其它数据库中的记录进行分类。 在电子商务中分类分析可以预测客户响应， 如哪些客户最倾向 于对直接邮件推销做出 回应， 又有哪些客户可能会换他的 手机 服务提供商，或进行商店定位，如按成功的商店、一般商店和失败商店排列得出 这 3类商店各自具有的属性。然后选择包含位置属性的地理数据库，分析每一预 期的商店位置属性，以确定预期的商店定位属于哪一类。只有那些符合成功一类 要求的商店位置才作为商店定位的候选。用于分类分析的典型方法有统计方法的 贝叶斯分类、机器学习的判定树归纳分类、神经网络的后向传播分类等。另外还 有一些其它分类方法，包括 k 一最临近分类、mb r 、遗传算法、粗糙集和模糊集 方法。目前，尚未发现有一种方法对所有数据都优于其它方法。 5 )回归发现 回归是通过具有已知值的变量来预测其他变量的值。它与分类类似，差别在 于前者的预测值是连续的，而后者是离散的。在最简单的 情况下，回归采用的是 像线性回归这样的标准统计技术。但在大多数现实世界中的问题是不能用简单的 线性回归所能预测的。如商品的销售量、股票价格、产品合格率、利润的大小等， 很难找到简单有效的方法来预测，因为 要描述这些事 件的变化所需的 变量以上百 计，且这些变量本身往往都是非线性的。为此人们又发明了许多新的手段来试图 解决这个问题，如逻辑回归、决策树、神经网络等。一般同一个模型既可用于回 归也可用于分 类， 如c a r t 决策树算法既 可以 用于建立分类树， 也可建立回 归树， 神经网络也是如此。 6 ) 序列模式发现 序列模式分析和关联分析类似， 其目 的 也是为了 挖掘数据之间的 联系， 但序 四川人学硕 1 : 学位论文 2 0 0 4 ) 列模式分析的侧重点在于分析数据间的前后序列关系。 它能发现数据库中形如“ 在 某一段时间内，顾客购买商品 a ，接着购买商品 b ，而后购买商品 c ，即序列 a - + b - 4 c出 现的频率较高” 之类的知识。 序列 模式分 析描述的问题是: 在 给定交 易序列数据库中，每个序列是按照交易时间排列的一组交易集，挖掘序列函数作 用在这个交易序列数据库上， 返回该数据库中出 现的高 频序列。 在进行序列模式 分析时，同样也需要有用户输入最小值信度 c和最小支持度 s 。另外关联规则挖 掘中采用的a p r i o r i 特性可以用于 序列模 式的挖掘， 另一类挖掘此类模式的 方法是 基于数据库投影的序列模式生长技术。 总 之在选择一种数据挖掘技术我们应根据商业问题的特点 来决定采用哪种数 据挖掘形式比较合适。应选择符合数据模型的算法，确定合适的 模型和参数。只 有选择好正确的数据挖掘工具，才能真正发挥数据挖掘的作用，使企业在激烈的 市场竞争中做出正确的决策，保持有力的竞争优势，以便达到我们的挖掘任务。 2数据挖掘的应用和研究方向 数据挖掘能够 自动发现以前未知的模式，自动预测未来趋势和行为。从数据 库中发现出来的知识可以用在信息管理、过程控制、科学研究、决策支持等许多 方面以 及金融、 市场营销、 信用保险、化工/ 医药等许多 领域。帮 助企事业单 位定 位市场、预测销售趋势、优化营销策略、监督交易活动、发现交易规则等等口 数据挖掘是一个年轻而非常活跃的研究领域，目前面临的问题，除了基础理 论和 技术方 面的外，更重要的是开发和应用。当前数据挖掘的 主要研究 方向 有: 1 )加强应用研究， 针对不同 数据挖掘任务的 专用数 据挖掘系统。 不同的应用 领域可能使用多种 类型数据和数据库， 知识发现系 统应当能够对不同类型的数据 和数据库进行有效的数据挖掘。 2 )高效率挖掘算法。 为能从大量数据中有效的抽取信息， 数据挖掘 算法必须 是高效的，即算法的运行时间必须是可预测的和可接受的，带有指数甚至中阶多 项式的算法是没有实际使用价值的。 3 )提高数据挖掘结 果的 有效性、 确定 性和可 表达性。 4 )数据挖掘结果的可视化。 5 )多 源数据挖掘。 网络将 许多数 据源连接在一 起， 形成巨 大的分布式异构数 据库，同时促进了并行和分布式数据挖掘算法的研究。 四川大学硕十学位论文 ( 2 0 0 4 ) 6 )数据挖掘的安全性和保密性。 1 . 2 数据挖掘中的关联规则挖掘 关联 规则挖掘是数据挖掘中 最活跃的 研究方 法之一。 最早是由a g r a w a l 等人 提出的，最初提出的动机是针对购物篮分析问 题， 其目的是为了 发现交易数据库 中不同商品之间的 联系规则。这些规则刻画了 顾客购买 行为模式， 可以 用来指导 商家科学地安排进货、库存以及货架设计等。之后诸多的研究人员对关联规则的 挖掘问题进行了大量的研究。他们的工作涉及到关联规则的挖掘理论的探索、原 有算法的改进和新算法的设计、并行关联规则挖掘 ( p a r a l l e l a s s o c i a t i o n r u l e m i n i n g )以 及数量关联规则挖掘 ( q u a n t i t i v e a s s o c i a t i o n r u l e m i n i n g ) 等问 题。 在 提高挖掘规则算法的效率、适应性、可用性以及应用推广等方面，许多学者进行 了不懈的努力。 1 .关 联规则挖掘的简单定义及应用 关联规则挖掘是指在交易数据、关系数据或其他信息载体中，查找存在于项 目 集合或对象集合之间的频繁模式、关联、相关性、或因果结构。它主要应用在 购物篮分析、交叉销售、产品目 录设计、 l o s s - l e a d e r a n a l y s i s ,聚集、分类等。 2 .关联规则的种类 我们将关联规则按不同 的情况进行分类 1 )基于规则中 处理变量的类型， 关联 规则可以分为布尔型和数值型。 布尔型 考虑的是项集的存在与否，而数值型则是量化的关联。 例如:性别=“ 女” 二 职业二“ 秘书”布尔型 性别= “ 女” = a v g( 收入) = 2 3 0 0数值型 2 )基于规则中数据的抽象层次:可以分为单层关联规则和多层关联规则。 单 层关联规则: 多层关联规则: 所有的变量都没有考虑到现实的数据具有多个层次。 充分考虑了数据的多层性。 3 ) 基于规则中涉及到的数据的维数。关联规则可分为单维的和多维的。 在单维的关联规则中，只涉及到数据的一个维，如用户购买的物品。 在多维的关联规则中，要处理的数据会设计到多个维。 换成另一句话，单维关联规则是处理单个属性中的一些关系;多维关联规k r 是处理各个属性之间的某些关系。例如:啤酒= 尿布，这条规则只涉及到用户的 购买的 物品，属于单维的关联规则; 性别= “ 女” = 职业二“ 秘书” ，这 条规则 就 v u 川大 学倾士 学位论文 ( 2 0 0 4 ) 涉及到两 个字 段的信息， 是两个维上的 一条关联规则， 属于多 维的关联规则。 我们了解了关联规则的分类之后，就可以在具体的分析过程 中考虑某些具体 方法适用于哪一类规则的挖掘，某类规则又可以用哪些方法处理。 1 . 3 本文主要贡献及内容安排 如前所述， 数据挖掘是一门具有 庞大知 识体系结 构的学科， 涵盖了 多种技术， 目 前己 经成为网络中不可缺少的技术。本文主要 通过挖掘关联规则 作为数据挖掘 的代表来研究其有关问题，内容主要集中在以下几个方面:分析关联规则挖掘 ( mi n i n g a s s o c i a t i o n r u l e s ) 中 产生 频繁集的常用算法、 算法的不足以 及对这些不足 进行改进的新算法。 本文首先介绍了数据挖掘的发展现状， 关联规则在数据挖掘中是一 个重要的 研究内容，于是接着论述关联规则挖掘的相关要点。 第二章详细研究关联规则中的 基本概念并深入分 析由 a g r a w a l 等人提出的著 名算法一 a p r i o r i 算法的原理:其后的数据挖掘算法大多数建立在 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 ir d 等。在这些算法 中，计算项目 集的 支持度是发现频繁项目 集中 最耗时的工作，占 据整个计算量的 大部分。因此，降低候选项目 集的 数量是减小开销的 最好手段。 第 三章 是 本 文 的 重 点， 首 先 分 析 和 研究 了f p - g r o w th (f re q u e n t p a tt e r n g r o w th , 频 繁 模式 增长 ) 算 法， 它 从 根 本 上 改 进了a p ri o r i 算 法 产生 庞 大 候 选 频 繁 集的 缺 点， 是 一 种 基于f p - t r e e ( f r e q u e n t p a tt e r n t re e , 频 繁 模 式 树 ) 的 不 产 生 频 繁 候 选 集 的 关 联规则挖掘算法。接着分析 f p - t r e e 的构 造过程和 f p - g r o w t h 算法的z 作过程， 总 结出f p - g r o w t h 算法具有节省时间和空间的优势。 在这些研究和分析的基础上， 总结出了f p - g r o w t h 算法还有些不足， 提出 通过分类将原始数据库进行归类， 得 到几个子数据库，使得同一 个数据库中事务 集的 项相似度较高，而不同数据库中 事务集的项的相似度很低， 几乎为零; 然后分别对每个子数据库构建f p - t r e e ， 然 后用 f p - g r o w th算法来挖掘得到频繁集， 并同时对每个子数据 库上的频繁集进行 优化;最后对这些子数据库上的频繁集进行合并求得原 数据库上频繁集，这 样保 证了能够 得到正确的最优结果，同时 也提高了 一定的性能。 第四章，编程实现通过本文提出的新算法挖掘频繁集的整个过程，同时 实现 了 著名的f p - g r o w t h 算法挖掘同一 个测试 数据库。其中 本文给出了 实现过程中定 四川大学硕i s 学位论文 ( 2 0 0 4 ) 义的数据结构和部分核心源代码， 并做了 相应的注释。 第五章，主要对木文提出的新算法和 f p - g r o w t h算法从存储空间、运行时间 和最后产生的频繁集等几个方面进行了比较，总结出本文提出的新算法的优点。 第六章，对更新挖掘关联规则算法进行一个总结，提出对它的不足之处可以 做的一些改进，结束全文。 目前数据挖掘技术在国外应用非常广泛， 但是国内在这方面的发展相对缓慢。 作者在对本文提出和研究的各种算法进行比较和测试，这些工作也只是对数据挖 掘进行一个简单而浅显的研究，希望在今后的工作中更加深化和具体的研究。 四川大学硕士学位论文 ( 2 0 0 4 ) 第二章 关联规则中算法的研究 几年前， 伴随着神奇的“ 啤酒搭着尿布卖”的故事，数据仓库走进了中国 人 的视野。 “ 啤酒搭着尿布卖”是一个经典的关于关联规则挖掘的故事，它告诉人 们可以利用手中没有规律的数据，找出物与人之间的规律。这个故事曾给人们带 来巨大的 震惊，同时这个挖掘出 来的 关联规则也给商业界带来了 惊人的利润。 挖掘关联规则就是发现大量数据中项集之间有趣的 关联或相关联系的 过程。 它在数据挖掘中是一个重要的 课题，最近 几年已 被业界公开研究，成为一个热点 并广泛用于多种应用中。最初关联规则的研究只是为了帮助发现交易数据库中不 同商品 ( 项)之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其 他商品的影响。分析结果可以应用于商品货架布局、货存安排以及根据购买模式 对 用户 进行分类。 目 前它已 经被广泛的 应用到各个领域中， 作为世界 上最大的“ 数 据库”一一网络，关联规则挖掘技术也融入其中。 a g r a w a l 等在 1 9 9 3 年首 先提出了 挖掘 顾客交易数据 库中项集间的 关联规则问 题，以 后诸多的 研究人员对关联规则的挖掘问题进行了 大量的 研究。 他们的 工作 包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法挖掘 规则的效率，对挖掘关联规则的应用进行推广。 关 联规则是形式如下的 一种规则， “ 在购买面包和黄油的 顾客中， 有9 0 %的 人 同时也买了牛奶” ( 面包+黄油一 牛奶， 置信度9 0 % ) 。 这种规则对顾客的 购买 行为 提供极有价值的信息，对改进零售业等商业活动的决策有重要意义。数据挖掘中 关联规则挖掘技术目前己经有不少成功的范例。其实在日常生活中我们也可以看 到许多相关的应用。 例如， 如果你在一家比 较著名的电 子商务网 站购买了一张周星驰的经典搞 笑 片 “ 大话西 游” ，该网站会提醒你， 【 购买该商品的用户还买了 这些商品】 :行 运一 条龙、9 7家有喜事、武状元苏乞儿、月光宝盒、秀兰邓波儿。 那么你也可以参 考是否要去购买这些影片。当然这只是一个非常简单的例子，但是足以说明关联 规则挖掘在我们现在整个生活领 域中应用是多么广大， 并且有着不可预测的 潜力。 夸 2 . 1 基本概念 项集 9 1 四川大学硕士学位论文 ( 2 0 0 4 ) 项的集合称为项集( i t e m s e t ) 。 设i = i , 1 2 ,- h 是一个项集， 其中i ; ( i = 1 , 2 ,3 , ， 二 ，n ) 可以是经典例子中的啤酒和尿布，也可以是保险公司的顾客。 k 一项 集 ( k = 1 , 2 , 3 . . . . . . ) 表示包含k个项的项集， k表示项集中 项的 数目。 2 事务1 9 ) 事务 是项的集合， 设有事务t ，则t c i 。 对应每个事务都有一个唯一的标识， 如事务号记为i d 。设 x是 i 中项的集合，如果 x c t ，则称事务 t包含 x a 3 .事 务 集 9) 事务的集合称为事务集，也称为事务数 据库。设某事务集为 d ， 则 d = ( t i , t 2 ,. , t n ) ， d = t i l t i (-= d , i = 1 , 2 ,， n ) . 4 .关 联规则9 设i = i il , i2 ， i耐 是 一 组 项 集 一 个商 场的 物 品 可 能 有 上 万 种 ) ， d 是 一 组 事务 集( 事务数 据库 ) 。 d中的 每个事务t 是一组项集， 显然满足t c i 。 关联 规则 是 如 下 形 式的 一 种 蕴 含 :x - - y ， 其 中x c i , y (- i ， 且x n y = 中 。 例如: 如果项集x ( x c t , x = x i , x 2 ,， x. ) 是事务集的 支持项 集， 那么它的关联规则就是 xi , x2 ,，x m - i - - x m 。对于规则右部含两个以 上项的规则 ( x i -x2 ,，xm ;或者 x1 , x2 - - x3 ,，x m +等等) 。 5 .支 持 度9 ( s u p p o r t ) 支持度描述了a和 b这两个项集在所有事务中同时出现的概率。 可以定义为: 支持 度 ( a fb ) = 包含a和b的元组数 / 元组总数。 数学公式表示为: p ( a u b ) 例如在一个商场中， 某天共有 1 0 0 0 笔业务， 其中有 1 0 0 笔业务同时买了牛奶 和面 包，则 (牛奶斗面包 )的 关联规则的 支持度为1 0 0 / 1 0 0 0 = 1 0 %. 6 .可 信度 191 ( c o n fi d e n c e ， 也称 置 信 度) 可 信 度即 是 “ 值 得 信 赖 性， 设a , b是两个项集， 对于事务 集d , a e d , b e d , an b = ( d , a f b 的可 信度定义为:可信度 ( a = b )= 包含 a 和 b 的元组数/ 包含 a 的元组数。 可信 度表达的就是在出 现项集a的 事务集d中， 项集b也同时出 现的 概率。 也就 是条 件概率，用数学公式可表示 为: p ( b a ) 例如购买牛奶的顾客中有 8 0 %也同时购买了面包， 即是关联规则: 牛奶 劝 面 包的 可信度为8 0 %. 支持度和置信度是描述关联规则的两 个重要 属性。如果不考虑关联规则的支 持度和可信度，那么在事务数据库中存在无穷多的关联规则。事实上，人们一般 只对满足一定 支持度和可信度的关联规则感兴趣。在 文献中， 一般称满足一 定要 四川大学硕士学 位论文( 2 0 0 4 ) 求的( 如较大的 支持 度和可信度) 的规则为强规 则。 因此， 为了 发现出 有意义的关联 规则，需要给定两个闭值:最小支持度和最小可信度。前者表示了一组物品集在 统计意义上的需满足的最低程度:后者反应了关联规则的最低可靠度。 给定一个事务 集 d ，挖掘关联 规则问 题就是产生 支持度和可信度分别大于 用 户给定的最小支持度和最小可信度的关联规则，也就是产生强规则的问题。 2 . 2 关联规则的数学模型 目前，在数据挖掘研究中，对关联规则挖掘的研究开展得比较积极和深入。 以下给出的数学模型用来描述关联规则的发现 问题。 设1 = 0 1 , 12 , . . . , 1 . 是一 组 物 品 集 ，其 中 每一 个事 务t 是一 组 物品， 显 然飞i 。 设 x为一组物品，当且仅当x c t时，称事务t包含 x。 一个关联规则是如下形式的 一种蕴涵:x -*y ，其中x c i , y c i 且x n y = a) 。 如果d中s % 的事务包含x u y , 则称规则x uy在事务集 d上的支持度s u p p o rt ( x u y ) = s 。 可信度为。 ， 如果 c = s u p p o rt ( xu y ) * 1 0 0 / s u p p o r t ( x ) ，则说 明d中 包含x的 事务中有。 %的 事务 同时也包含了 y。可信度说明了蕴涵的强度，而支持度说明了规则中所出现模式 的 频率。具 有高可信度和强支持度的 规则称为“ 强规则” ( s t r o n g r u l e s ) 。 关联规则 发现任务的 本质是要在数据库中发现强关 联规则。利用这些关联规则可以了 解客 户的行为，这对于改进零售业等商业活动的决策很有帮助。例如，可以帮助改进 商品的摆放 ( 把顾客经常同时买的商品摆放在一起 ) ，帮助如何规划市场 ( 互相搭 配进货)等。在数据挖掘研究领域，对于关联分析的研究开展的比较深入，人们 提出了多 种关联规则挖掘算法， 如a p r i o r i , f p - g r o w t h , a i s , d h p 等算法。 2 . 3 关联规则挖掘的过程 关联规则作为数据挖掘中最重要的工具之一，它具有广泛的应用前景。一般 可以分成两部分来实现: 1 . 挖掘频繁集:查找满 足给定支 持度的频繁集 频繁集:指满足最小支持度的项目集合。 k 一 频繁 集:指包含k 个项目的 频繁集。 性 质1 ) i ll : 频 繁 集的 子 集也 一 定 是 频 繁的 。 四川大学硕1 : 学位论文 ( 2 0 0 4 ) 例如， 如果厦 a b 是频繁集，则 a ) b 也一定是频繁集 2