（计算机软件与理论专业论文）数据库中的快速关联规则挖掘.pdf

摘要1 y 5 7 8 9 7 作为数据库研究领域中的热点 数据库中的知识发现 简称k d d 正在受到越 来越多的关注 它被定义为在数据中寻找正确的 有趣的 潜在有用的并最终町以 理解的模式 对关联规则的挖掘在许多数据挖掘任务中都有重要作用 有着广泛的 应崩范围 随着被挖掘的数据集在大小和复杂度上的飞速增长 研究高效可伸缩的 挖掘算法对保证系统的可伸缩性和交互性至关重要 关联规则挖掘算法使用格理论中的组合特性来将原始问题分解为许多更小的互 相独立的问题 最有名的和最有影响力的算法包括a p r i o r i 算法和f p g r o w t h 算法 这些算法在所有的最大频繁项目集都很短时性能很好 然而 如果存在长的最大频 繁项目集 算法性能将会急剧f 降 长的最大频繁项目集容易出现在项目之州相关 性很高的应用场合 s e g f r e e 是针对此问题提出的一个算法 s e g f r e e 将数据库分为许多个分段并在 每个分段中挖掘f l e e 项目集 f r e e 项目集是一种精简集 数据库分成的分段数越多 每个分段中的f l e e 项目集将会越少 s e g f r e e 算法能显著的减少项目集模式匹配的时 间 比以往的算法效率都高 r u l e f r e e 项目集是针 对有效的挖掘长模式所提出的另一种方法 r u l e f r e e 项目 集是一种精简集 我们能使用它再生出所有的频繁项目集和他们的准确支持度 r u l e f r e e 项目集远比整个频繁项目集集合小 再生的过程也不需要对数据库进行存 取 针对r u l e f r e e 项目集的挖掘提出了两种使用不同策略的算法r f s m i n e r 和 h o p e i i i 实验数据显示即使在很困难的情况下r u l e f r e e 项目集也能被高效开采 先对数据库做扫描以获得一些辅助信息能够有效的优化挖掘过程 提出a r s c 算法就是用来生成分段信息表以达到这一目的的 分段信息表耗用内存不大 容易 z t 成但加速的效果很好 它能与很多种算法协同工作 还可以使用在不局限于关联 规则挖掘的其他数据挖掘任务中 本立受国家科技攻关汁划资助 专题编写2 0 0 l b a l 0 2 a 0 4 0 2 0 3 l i i 搿露 挖掘带否定的关联规则是个非常困难的问题 其中主要的计算量来源于要找 出所有的频繁广义项日集 项目集中可能带负项目 及其支持度 针对这个问题提 出了一个方法 不是去挖掘完整的频繁 一义项目集集合 而是挖掘一个叫做s f r e e 项目集的精简集 使用这个精简集能不用读取数据库就能还原出所有的频繁广义项 目集及其支持度 针对挖掘s f r e e 项目集提出了算法m s f i 我们将它 ia p r i o r i 算 法做了比较 实验数据显示这种方法更有效 在现代计算机系统中入侵检测系统已经变成了一个很重要的组成部分 入侵检 测系统首先使用数据挖掘算法来对审计数据查找频繁模式 析取特征 然后使用分 类算法建立入侵检测模型 这其中最重要的步骤是判别字段间的关联和相关性以构 造特征 提出了一种新的想法足在入侵检测系统中标准关联规则的描述能力不够 应该使用带否定和带支持度约束的关联规则来取得更好的效果 关键词 数据挖掘 关联规则 频繁项目集 精简集 a b s t r a c 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 k d d h a sr e c e i v e di n c r e a s i n ga t t e n t i o na n dh a s b e e nr e c o g n i z e da sa p r o m i s i n gf i e l do fd a t a b a s er e s e a r c h i ti sd e f i n e da st h en o n t r i v i a l p r o c e s s o fi d e n t i f y i n g v a l i d n o v e l p o t e n t i a l l y u s e f u la n d u l t i m a t e l y u n d e r s t a n d a b l e p a t t e r n si nd a t a m i n i n ga s s o c i a t i o nr u l e sf r o ml a r g ed a t a b a s e sp l a y sa r te s s e n t i a lr o l ei n m a n y d a t am i n i n gt a s k sa n dh a sb r o a da p p l i c a t i o n s h i g h p e r f o r m a n c es c a l a b l ec o m p u t i n g i sc r u c i a lf o re n s u r i n gs y s t e ms c a l a b i l i t ya n di n t e r a c t i v i t ya sd a t a s e t sg r o wi n e x o r a b l yi n s i z ea n d c o m p l e x i t y t 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 mu s el a t t i c e t h e o r e t i cc o m b i n a t o r i a lp r o p e r t i e s t o d e c o m p o s et h eo r i g i n a lp r o b l e mi n t o s m a l l i n d e p e n d e n ts u b p r o b l e m s t h em o s t f a m o u sa n di n f l u e n t i a la l g o r i t h m sa r ea p r i o r im a df p g r o w t h w h e na l lm a x i m a l f r e q u e n t i t e m s e t sa r es h o r t t h e s e a l g o r i t h m sp e r f o r mr e a s o n a b l yw e l l h o w e v e r p e r f o r m a n c e d r a s t i c a l l yd e c r e a s e sw h e na n yo f t h em a x i m a li t e m s e t sb e c o m e sl o n g e r 1 1 1d a t am i n i n g a p p l i c a t i o n sw h e r e i t e m sa r ec o r r e l a t e d m a x i m a lf r e q u e n ti t e m s e t sc o u l db e l o n g a l g o r i t h ms e g f r e ei sp r o p o s e d t od e a lw i t ht h i s p r o b l e m s e g f r e e d i v i d et h e d a t a b a s ei n t o s e g m e n t sa n de x t r a c tf l e es e t si ne a c hs e g m e n t f r e es e t si sac o n d e n s e d r e p r e s e n t a t i o na n dt h e r ew i l lb el e s sf r e es e t si ne a c hs e g m e n ti fw ed i v i d et h ed a t a b a s e i n t om o r e s e g m e n t s s e g f r e es i g n i f i c a n t l yr e d u c e st h et i m ef o rp a t t e r nm a t c ha n di sm o r e e f f i c i e n tt h a nt h ep r e v i o u sa l g o r i t h m s r u l e f r e es e t si s p r o p o s e da s a n o t h e rw a yt om i n ed a t a b a s e sw i t h l o n gp a t t e r n s e f f i c i e n t l y r u l e f r e es e t si sac o n d e n s e dr e p r e s e n t a t i o na n dw ec a nr e g e n e r a t ea 儿f r e q u e n t p a t t e r n sa n d t h e i re x a c tf r e q u e n c i e sb y u s i n gr u l e f r e es e t s r u l e f r e es e t si sm u c hs m a l l e r t h a nt h ew h o l e f r e q u e n tp a t t e r n c o l l e c t i o na n dt h e p r o c e s s o fr e g e n e r a t i o nc a l l b e p e r f o r m e dw i t h o u ta n ya c c e s st o t h e o r i g i n a l d a t a t w o a l g o r i t h m s r f s m i n e ra n d h o p e i i i a r ep r o p o s e dt om i n er u l e f r e es e t sf r o md a t a b a s e sa n dt h e yu s ed i f f e r e n t v s t r a t e g y p r a c t i c a le x p e r i m e n t s s h o wt h a tt h i s r e p r e s e n t a t i o n c a nb ee x t r a c t e d v e r y e f f i c i e n t l ye v e n i nd i f f i c u l tc a s e s g e t t i n gs o m ea d d i t i o n a l i n f o r m a t i o nt h r o u g hs c a n n i n gd a t a b a s ec a no p t i m i z et h e m i n i n gp r o c e s sv e r ye f f i c i e n t l y t h e a r s ca l g o r i t l m ai sp r o p o s e dt o c r e a t e s e g m e n t i n f o r m a t i o nt a b l et od ot h i s s e g m e n ti n f o r m a t i o nt a b l ec o s t sl i t t l em e m o r y t os a v ea n di s e a s yt o c r e a t ef r o mt h ed a t a b a s eb u tp e r f o r m se x c e l l e n t l y i tc a na l s ob eu s e di ns o m e o t h e r m i n i n g t a s k sa n dw o r kw i t hm a n y a l g o r i t h m s t h ep r o b l e mo f m i n i n ga s s o c i a t i o nr u l e st h a tm a y i n v o l v en e g a t i o n si sd i f f i c u l ta n d r e m a i n sa no p e np r o b l e m i th a sb e e ns h o w nt h a tt h em a j o rc o m p u t a t i o n a lt a s ki s t o i d e n t i f y a l lo ft h ef r e q u e n ti t e m s e t st h a tm a yh a v en e g a t i o n sf r o mw h i c hr u l e sw i t h n e g a t i o n sc a nb ed e r i v e d a n e wi d e ai sp r o p o s e dt oe x t r a c tac o n d e n s e dr e p r e s e n t a t i o no f f r e q u e n tg e n e r a l i z e di t e m s e t sc a l l e ds f l e es e t s i n s t e a do fe x t r a c t i n gt h ew h o l ef r e q u e n t g e n e r a l i z e di t e m s e t sc o l l e c t i o n w es h o w t h a tt h i sc o n d e n s e d r e p r e s e n t a t i o nc a n b eu s e dt o r e g e n e r a t e a l l f r e q u e n tg e n e r a l i z e dp a t t e r n s a n dt h e i re x a c t f r e q u e n c i e s w i t h o u t a n y a c c e s s i n gt ot h eo r i g i n a ld a t a a na l g o r i t h m m s f i i sp r e s e n t e dt oe x t r a c tt h ef r e q u e n t s f r e es e t sw e c o m p a r e d i tw i t ha p r i o r ia l g o r i t h m a n dp r a c t i c a le x p e r i m e n t ss h o wt h a t t h i sr e p r e s e n t a t i o nc a nb ee x t r a c t e dv e r ye f f i c i e n t l y i nam o d e mc o m p u t e rs y s t e m i n t r u s i o nd e t e c t i o ns y s t e mh a sb e c o m ea ne s s e n t i a l c o m p o n e n t t h ei n t r u s i o nd e t e c t i o ns y s t e mf i r s ta p p l i e sd a t am i n i n gp r o g r a m st oa u d i t d a t at oc o m p u t ef r e q u e n tp a t t e r n s e x t r a c tf e a t u r e sa n dt h e nu s ec l a s s i f i c a t i o na l g o r i t h mt o c o m p u t ed e t e c t i o nm o d e l s t h em o s ti m p o r t a n ts t e p o ft h i s p r o c e s s i st od e t e r m i n e r e l a t i o n sb e t w e e nf i e l d si nt h ed a t a b a s er e c o r d st oc o n s t r u c tf e a t u r e s t h ei d e ai sp r o p o s e d t h a tt h es t a n d a r da s s o c i a t i o nr u l e sh a v en o te n o u g h e x p r e s s i v e n e s sa n di n t r u s i o nd e t e c t i o n s y s t e m sc a ne x t r a c tt h ea s s o c i a t i o nr u l e sw i t hn e g a t i o n sa n dv a r y i n gs u p p o r tt h r e s h o l d st o g e tb e t t e rp e r f o r m a n c e 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 m s e t c o n d e n s e dr e p r e s e n t a t i o n v 1绪论 1 1 背景 今天的人们已经拥有了大量的数据 迫切希望将这些数据转化为有用的知识和 信息 在这样的背景下产生了数据挖掘这个新兴学科并迅速成为信息科学中的热门 研究领域 受到广泛的关注 数据挖掘是新兴的边缘学科 研究者主要来自统计 机器学习 数据库三个领域 数据挖掘的结果 即挖掘所获得的知识 能使用在如 商业管理 市场分析 工程设计和科学探索等各个领域 数据挖掘是信息科学革命性发展的直接结果 从信息科学的发展历程来看 首 先成熟的是以文件系统为代表的数据采集技术 当数据的收集不再是问题以后 对 数据的处理 包括存贮 检索等等 就成为了系统的瓶颈 于是数据库技术应运而 生 数据库技术成功地解决了上述问题后 人们就希望能够对数据进行更好的分析 和理解 这样就产生了数据仓库和在线数据分析 o l a p 技术 这部分地解决了人 们的需求 比如o l a p 的工具支持多维分析 一定范围内的决策支持等等 但人们还需要对数据做出更深入的分析 如数据的分类 聚类 特征等等 以 难以想象的高速度所收集的大量数据被存贮在超大规模的数据库中 远远超出了人 们能理解它的能力 这被称为 数据丰富而信息贫乏 结果是数据库往往变成了 数 据的坟墓 很少被人访问 决策更多地不是依赖信息 而是依赖决策者的直觉 数 据挖掘就是要改善 数据丰富而信息贫乏 的情况 将 数据的坟墓 变成隐藏着 知识的 金矿 1 1 2 数据挖掘 一般来说 数据挖掘指的是从大量的数据中发现知识 大量的数据 意味着可 伸缩性对数据挖掘甚至比效率还重要 2 1 而知识不仅可以是频繁的模式 也可以是 异常5 3 1 有人认为数据挖掘和数据库中的知识发现 k d d 是同义词 但也有人认 为数据挖掘是k d d 的一个步骤 数据挖掘包括如下的过程川 4 1 数据清洗 从数据中去除噪音和不致的数据 2 数据整合 不同来源的数据被合并在一起 3 数据选择 选择和分析任务相关的数据 4 数据变换 将数据转换成挖掘所需要的形式 5 模式析取 这是数据挖掘的核心过程 用来从数据中找到模式 6 结果评价 通过定义好的兴趣度量标准来衡量所挖掘到的结果是否有趣 7 知识表示 用可视化或其它形式将挖掘到的知识展现给用户 数据挖掘是一个交互的过程 用户用数据挖掘语言来表达挖掘任务 用户 i u 能对挖掘到的知识提出意见 这些意见将被用来指导对数据库进行更进步的挖掘 怎样将用户已有的知识结合到数据挖掘过程中是很有趣的研究问题 数据挖掘可以在传统意义的关联数据库上实行 也很适合在数据仓库上实行 因为数据仓库一般已实现了数据挖掘的前两个步骤的功能 即数据清洗和数据整 合 现在的很多数据库管理系统也在考虑加大对数据挖掘的支持力度 将许多数据 挖掘所需要的功能整合到数据库管理系统中去 8 中还提出了一个天才的构想 能在o l t p 系统上几乎不增加额外丌销就能实现数据挖掘的功能 其它的可以挖掘 的数据源包括事务数据库 面向对象数据库 空间数据库 时态数据库 文本数据 库以及i n t e r n e t 上的万维网网页等等 9 j 著名 j 2 维网网页搜索引擎g o 0 9 1 e 就是 在搜索引擎中使用数据挖掘技术的成果 数据挖掘按挖掘的知识来分类 大致包括特征 c h a r a c t e r i z a t i o n 荚联 a s s o c i a t i o n 分类 c l a s s i f i c a t i o n 和聚类 c l u s t e r 等等 记1 特征是指找山每一 类数据的特点 关联是找出不同属性之间的相关性 分类是指对给出的几类数据找 出分类的规则 聚类是指将给出的数据按相似性分成几类 1 3 近年来新提出的一个 有趣的数据挖掘任务是在关系数据库中象使用w 曲搜索引擎一样按关键字搜索数据 儿1 另个有趣的挖掘任务是 在 1 6 中 作者不是研究在给定的环境下州 么模 式是频繁的 而是给定的模式在什么环境下是频繁的 在 1 7 一文中作者还讨论了使 用统一模型米对待所有的数据挖掘任务的问题 本文对数据库中的快速关联舰则挖掘算法进行研究 1 3 关联规则挖掘 关联规则挖掘的目的是寻找在大量的数据项中隐藏着的联系或者相关性 当收 集了越柬越多的数据时 他们变得对这些数掘中隐含着的联系很有兴趣 比如说 电子商务中商家对顾客网上所购买的东两之间的联系很有兴趣 1 发现这些有趣的 关联能帮助他们做出决策 比如市场分析 信用卡风险鉴别 网络故障诊断 天体 识别 基因的相似性分析等等 1 关联规则的一个典型例子是售货篮分析 售货篮分析指的是通过对顾客在同一 售货篮中所购买的商品之问的联系的分析来调查顾客的购买行为模式 它能辅助零 售商来制定市场营销策略 比方说 在布置卖场时 将顾客经常一同购买的商品 如 牛奶和面包 放置在一起 刺激顾客的消费欲望 增加销售额 我们将在2 1 节中给出关联规则挖掘的形式化定义 这最早是在e 2 0 中提出的 它还提出了关联规则的挖掘可以分为两个步骤 第一步是找出数据库中的所有频繁 项目集的集合及其支持度 第二步是通过第步所得到的频繁项目集的信息来牛成 所有的关联规则 其后的研究绝大多数也遵循这两个步骤 又因为第二个步骤计算 量相对非常小 因为它不需要到数据库中去读取信息 所以关联规则挖掘研究的重 点就放在了第一个步骤上 即查找数据库中的所有频繁项目集及其支持度 查找频繁项目集按策略来说可分为三大类 即经典的 基于精简集 c o n d e n s e d r e p r e s e n t a t i o n 的和基于最大频繁项目集 m a x i m a lf r e q u e n t i t e m s e t 的 经典的方法查找频繁项目集集合的全集 这其中 广度优先搜索策略口l 的典型 代表是a p r i o r i 算法 2 2 它也是最经典最有影响力的算法 深度优先搜索策略的典型 代表是f p g r o w t h 算法 2 3 这两类算法各有优缺点 2 4 j 其它比较著名的算法还包括 t r e e p r o j e c t i o n 2 p a s c a l 2 6 1 等 与经典的方法不同 基于精简集的方法并不查找频集项目集的全集 而是查找 它的一个称为精简集的子集田 町以利用这个子集再生出完整的频繁项目集的全集 1 及其支持度来 理想的精简集应该远小于整个频繁项日集集合 这样就可以极人地 提高挖掘的效率 己知的精简集包括c l o s e d 集例 f r e e 集俐 d i s j u n c t i o n f r e e 集 3 0 n d i l 1 等 开采精简集的主要算法包括a c l o s e 2 c h a r m m i n e x 2 9 1 等 基于最大频繁项目集的方法与前面两者都不同 它查找最大频繁项目集的集合 所谓最大频繁项目集 指的是它本身是频繁项目集 但它的任何一个超集都不是 根据 2 2 中提出的著名的a p r i o r i 属性 频繁项目集的任何子集都是频繁项目集 最 大频繁项目集集合的每一个元素的所有子集的集合的并集就是完整的频繁项目集集 合 但这还不能求出每一个频繁项目集的支持度 还需要对数据库额外做一趟扫描 以求出每一个频繁项目集的支持度 这一趟扫描通常很花时问 基于最大频繁项目 集的算法包括m a x m i n e r 3 3 p i n c e r s e a r c h 3 4 m a f i a 3 5 1 等 不管是查找完整的频繁项目集集合 还是精简集 还是最大频繁项目集集合 都存在算法的效率问题 有许多方法已被提出用来加速关联规则挖掘的算法 这包 括从减少数据库的扫描趟数入手的p a r t i o n 算法 3 6 d i c 算法 1 等 从加快支持度计 数入手的t i d 链 2 0 和垂直格式 3 8 等 从候选集剪枝入手的d h p 算法 3 9 o s s m 算 法 等以及其它一一些方法如抽样 f 4 2 m 增量式挖掘 并行 等 这些方法极大 地提高了关联规则算法挖掘的效率 4 6 中用真实数据而非人造数据对已有的算法性 能做了大量测试 4 7 q b 编制了一个称为 神谕 的有趣程序 它己知所有的频繁项 目集而只是查找它们的支持度 通过这样来定义关联规则挖掘的速度极限 它发现 现有算法的性能还很有改善的余地 与传统观点不同 有一派的观点认为 关联规则挖掘的数据库应该使用垂直的 数据格式 而不是传统的水平格式 这方血的工作包括 4 8 4 9 等 有些应用领域并不要求关联规则挖掘有非常精确的结果 但需要很快的系统的 响应速度 这时人们常常考虑在降低精确性的基础上极大的增加挖掘速度 这方面 的主要研究工作包括 2 9 5 0 1 等 随着应用领域要求的不同 关联规则有不少变种 5 1 可以大致将它们分为两类 一类是从扩展关联规则的形式出发 增强关联规则的描述能力 这包括 5 2 1 5 3 等 另一类是从提出新的兴趣度量标准出发 更好地表达用户的兴趣所在 这包括 5 4 1 1 5 5 1 1 5 6 5 7 等 5 8 w 更是分析了几十种已经提出的兴趣度量标准 这些变种增 强了关联规则的描述能力 拓广了关联规则的应用领域 刺关联规则的研究还包括分布式环境下的关联规则挖掘 5 9 1 和时态相关的关 联规则挖掘 6 基于粗糙集理论上的关联规则挖掘 62 1 在多个关系卜 挖掘关联规则 侧 更好的结果表达方式 如可视化 6 4 f 6 5 1 6 6 在关联规则挖掘中保护数据的隐密 以保护用户的隐私 6 7 i 1 给用户提供更多的交互机制 等等 关联规则还能对其它的数据挖掘任务提供支持 比如分类 7 0 j 7 国内在关联规则的挖掘上也取得了一些进展 毛国君等提出了i s s d m 算法以 进一步减少对数据库的访问 它只需一趟扫描就能完成对关联规则的挖掘m 夸雄 飞等提出了一种多段支持度算法 分段计算项目集的支持度 提早排除 f 频繁项目 集1 7 陆建江等讨论了借助 f 态模糊数模型来划分数量属性的论域 由此生成一系列 的语言值关联规则的问题 7 4 1 谢志鹏等分析了概念格与关联规则提取之间的关系m 1 寇育敬等研究了在有约束的环境下关联规则的增量式开采 提出了s e p a r a t e m 算 法 7 6 1 4 本文的贡献 本文主要在以下方面有所突破 1 针对f l e e 项目集的丁i 发 本文将分段的思想引入 提出了s e g f r e e 算法 s e g f r e e 算法通过分段加大了f r e e 项目集出现的概率 减少了项目集匹配的次数 较 经典算法更为高效 s e g f r e e 算法在3 3 讨沧 2 本文提出了一种新的精简集r u l e f r e e 集并证明了它是一个精简集 它还是 这类精简集中最小的一个 r u l e f l e e 集在3 4 1 介绍 3 针对r u l e f l e e 集的开采 本文提出了两种算法r f s m i n e r 和h o p e i i l r f s m i n e r 通过计算广义项目集的支持度来开采r u l e f r e e 集 h o p e i i i 通过计算项 目集支持度的卜下界来开采r u l e f r e e 集 这两种算法各有优点 3 4 2 介绍算法 r f s m i n e r 3 4 4 介绍算法h o p e i i i 4 分段信息表是加速关联规则挖掘的一种有效辅助手段 本文提出了一种牛 e 成分段信息表的算法a r s c 和经典算法相比 a r s c 花费时问更短 加速效果更好 4 43 讨论a r s c 算法 5 带否定的关联规则是关联规则的一个重要变种 挖掘难度要大丁对标准关 联规则的挖掘 本文将精简集的思想引入带否定的关联规则的挖掘 提出了一种精 简集s f r e e 集及其挖掘算法m s f i 更详细的介绍在52 3 6 网络入侵检测是关联规则挖掘的一个应用领域 本文讨论了关联规则在入 侵检测中的作用并在7 3 中提出了在入侵检测巾应该使用带否定和带支持度约束的 关联规则的观点 1 5 本文的组织 本文的组织如下 在第 章中 我们讨论关联规则挖掘的背景 意义 应用范围和国内外的研究 概况 第二章介绍经典的关联规则算法 主要是对a p r i o r i 和f p g r o w t h 这两种算法 做剖析 第三章讨论基于精简集的关联规则挖掘 这包括介绍传统的f r e e 集 提出 我们的s e g f r e e 算法以及提出r u l e f r e e 集及其挖掘算法 第四章讨论t 3 h 速关联舰 则挖掘的一些办法 主要从减少数据库的扫描趟数 加快支持度计数 候选集剪枝 三方面考虑 包括我们提m 的a r s c 算法 第五章介绍了标准关联规则的变种 主 要讨论带否定的关联规则和基于约束的关联规则 包括我们提出的m s f i 算法 第 六章介绍了我们使用的软件平台 包括软硬件环境 使用的测试数据集和集成的各 种算法 第七章讨论了关联规则的一个应用领域 入侵检测 最后一章总结全文 并给出了以后的研究方向 2 经典的关联规则挖掘算法 2 1 引言 在1 3 中我们已经对关联规则挖掘的任务进行了简单的介绍 下而我们来看关联 规则挖掘的形式化的问题定义 令i i l i 2 i 是一个符号的集合 其中的每一个符号 我们称之为一个项目 i t e m 令d 是一个事务的多重集 m u l t i s e t 每个事务t 都是项目集的一个子集 即t i d 是事务的多重集的意思是指d 中可能包含有完全相同的事务 即d 中町 能有两个事务所包含的项目完全相同 我们给d 中的每条事务都分配一个唯一的事 务标识符 我们称它为t i d 令x 为一个项目的集合 x g i 对 个事务t 如果 x c t 我们称之为事务t 包含项目集x 关联规则是形如x j y 的规则 其中x c i y c i 并且x o y 西 在事务集d 巾 如果包含x 的事务中c 同时包含y 我们说规则x j y 的可信度为c 如果d 中s 的事务包含x u y 我们说规则x j y 的支持度为s 支持度和可信度除了百分比的 形式外 也可以是绝对数值 如3 0 表示3 0 个事务 或相对数值 如0 4 表示4 0 这几种形式之问没有本质的区别 本文中将彳i 加区分地使用这三者 请读者根据上 下文自行加以判断 给定个事务集d 用户给出一个最小的可信度和最小的支持度 我们称为可 信度阈值和支持度闽值 关联规则挖掘的任务就是要生成所有的支持度和可信度分 别高于可信度闽值和支持度闽值的关联规则 这里的d 可以是实际生活中的 个文 件或一个关系表 我们在1 3 中已经提到 关联规则挖掘的任务可以分解为两个子问题 1 支持度高于支持度闽值的项目集我们称为频繁项目集 第一步就是要找出 所有的频繁项目集及其支持度 2 有了所有的频繁项目集及其支持度的信息后 我们就能生成所需要的关联 觇则 例如 项目集a b c d 和项同集a b 是频繁项目集 那么关联规则a b j c d 的 可信度就等于s u p p o r t a b c d s u p p o r t a b 这里我们用s u p p o r t x 表示项目集x 的 支持度 即d 中有百分之多少的事务包含x 如果a b j c d 的可信度高于可信度闽 值 那么这就是一条我们需要的关联规则 因为它的支持度显然也高于支持度闽值 这是因为项目集a b c d 是频繁项目集 1 2 容易看出 第二步的计算量很小 因为它不需在数据库中读取信息 所以 关 联规则挖掘的任务主要是第一个步骤 即找出所有的频繁项目集 找出所有的频繁项目集并不是一件轻而易举的事情 所有可能的频繁项目集的 个数与全部项目的个数成指数关系 令lif m 即一共有m 个不同的项目 那最多 可能有2 个频繁项目集 想像一下m 为1 0 0 0 或1 0 0 0 0 是很平常的事情 2 很容 易就成为一个天文数字 这2 个项目集都是i 的子集 它们构成了 个高度为m 的格 l a t t i c e 下面我们来看一个例予 事务数据库d 中有5 条事务 如表2 1 所示 表2 1 一个事务数据库d t i di t e m s 1acd 2b ce 3ab ce 4be 5abce 数据库d 中可能的频繁项目集构成了一个格 如图2 1 所示 这个格中一共有 3 2 个项目集 高度为5 依据支持度闽值的设定 这个格中只会有一部分项目集足 频繁项目集 例如 支持度闽值设定为2 4 0 时 这3 2 个项目集中只有15 个是 频繁的 在图21 中用加粗的黑框来表示 2 一个天真的办法就是测试项目集格中所有项目集的支持度 这样只需对事务数 据库d 做一趟扫描 但显然 这对于比较大的m 来说是行不通的 图2 1d 的项目集格 这样我们就需要按照一定的顺序分次分批地对项目集格 i t e m s e tl a t t i c e 这个巨 大的搜索空间进行访问 在1 3 中我们已经提到和基于最大频繁项目集 m a x i m a l f r e q u e n ti t e m s e t 以及基于精简集 c o n d e n s e dr e p r e s e n t a t i o n 的方法不同 经典的关 联规则挖掘算法需要找出所有的频繁项目集 即遍历搜索空间中的每一个频繁项开 集所代表的结点 有两种主要的搜索策略 它们是广度优先策略 b r e a d t h f i r s t 和 深度优先策略 d e p t h f i r s t 在本章的2 2 节我们将介绍a p r i o r i 算法 它使用的是 广度优先的搜索策略 a p r i o r i 算法提出之后几乎所有其它采用广度优先搜索策略的 算法都使用a p f i o f i 算法的框架 在本章的2 3 节我们将介绍f p g r o w t h 算法 它借 助于一个称为f p 树的数据结构实现了深度优先的搜索策略 这两种经典关联规则挖 掘算法分别是这两种搜索策略的典型代表 包含了这两种搜索策略的所有的最重要 的思想 需要指出的是 广度优先和深度优先这两种搜索策略各有所长 谁更好一 真是学术界激烈讨论的问题 至今没有定论 我们将在本章的小结中 2 4 节 对这 两种最经典最重要的算法 即a p r i o f i 算法和f p g r o w t h 算法 做一个简单的比较和 总结 2 2 a p r i o r i 算法 2 2 1 a p r i o r i 算法流程 a p r i o f i 是一个通过挖掘频繁项目集来挖掘布尔型关联规则的很有影响的算法 a p r i o r i 这个名字的来由是因为这个算法使用了频繁项目集的一些特性 即先验的知 识 p r i o r k n o w l e d g e 我们将在2 2 2 巾加以介绍 a p r i o r i 算法使用的是广度优先的 搜索策略 分层的 1 e v e l w i s e 迭代的 i t e r a t i v e 搜索项目集格空间 已得到的k 项目集的信息会被用来加速对 k 1 项f 集的搜索 k 项目集表示长度为k 的项 目集 a p r i o r i 算法首先查找长度为1 的频繁项目集 记成l l l l 又被用来查找长度为2 的频繁项目集即l 2 l 2 又被用来查找氏度为3 的频繁项目集l 3 如此进行下去 直 到找不出新的频繁项目集为止 对每个l k 的查找都需要对数据库进行一整趟扫描 也就是说 长度为 k 1 的候选项目集是使用长度为k 的频繁项目集生成的 所 谓候选项目集的意思就是它有可能是频繁的 到底它是不是真 f 的频繁项目集这就 需要到数据库中去对它进行计数 看它出现的次数是不是高于支持度阈值来决定了 a p r i o r i 算法主体程序的伪码如下 苗 先约定c k 表示长度为k 的候选项目集 l k 表示长度为k 的频繁项目集 l l 频繁的单个项目构成的项目集 f o r k l l k 西 k 十 d o b e g i n c k j 从l k 中生成候选项目集 f o r 数据库中的每一个事务t d o 对被t 所包含的c k 1 中的每一个候选项目集的计数器加一 l k t c k t 中计t 数器的值大于等于支持度闽值的项目集 e n d r e t u r n u l k 了解了a p r i o r i 算法的主体框架后 下面我们来看a p r i o r i 算法是如何从长度为k 的频繁项目集中生成长度为 k 1 的候i g s o i 目集的 2 2 2 候选集生成与利用a p r i o r i 属性剪技 a p r i o r i 算法使用了一个被称为a p f i o r i 属性的性质来减小搜索空间 提高挖掘算 法的效率 a p f i o f i 属性是基于这样的 个观察 即项目集 i u a 的支持度 这罩 的i 是一个项目集 a 是一个单个项目 不可能超过项目集i 的支持度 即s u p i u a s u p i 也就是说 如果项月集i 的支持度s u p i m i ns u p 这里的r a i ns u p 足支持度闽值 那么我们有s u p 1 w a 一 s u p i m i n s u p 成立 即如果项目集i 不是 频繁项目集 那么项目集i u a 肯定也不是频繁项目集 a p r i o r i 属性满足反单凋性 a n t i m o n o t o n e 即如果一个项目集不是频繁项目集 那么它的所有超集就都彳i 是频繁项目集 在a p r i o r i 算法中 我们在生成长度为 k 1 的候选项目集时已经知道了所有长度为k 的频繁项目集 这让我们能很好的利用 a p r i o r i 属性来为候选项目集剪枝 即减少生成的候选项目集从而缩小搜索宁间 具 体来说 生成长度为 k 1 的候选集需要两个步骤 第一步 让长度为k 的频繁 项目集集合l k 做自连接 第二步 对生成的结果进行剪枝 我们来看它的算法伪码 首先假定l k 中所有的项目集中的项目都已按照一定的顺序排好序 这很容易实 现 一般是按照字典顺序排序 第一步对l k 做自连接 i n s e r ti n t oc k 1 s e l e c tp i t e m l p i t e m 2 p i t e m k q i t e m k f r o ml k p l kq w h e r e p i t e m l 2 q i t e m la n d a n dp i t e m k 1 q i t e m k 1a n dp i t e m k z q i t e m k 第二步利用a p r i o r i 属性减技 f o r a l l ck 1 中的项目集c d o f o r a l l c 的长度为k 的子集s d o i f f s l k t h e nd e l v e cf r o mc k 1 这是因为根据a p r i o r i 属性 如果一个项目集是频繁项目集 那么它的所有子集 必然也是频繁项目集 我们已经知道了所有k 度为k 的频繁项目集 所以 个候选 项目集的所有长度为k 的子集必须都在l k 中 否则它就不可能是一个频繁项目集 因而可以从c h l 中把它删除掉 这就大大减少了c n l 的大小 从而减少了在下一趟 扫描中需到数据库中去进行计数的候选项目集的个数 从而提高了算法的效率 下 面是候选集f 卜成过程的一个例子 l 3 a b c a b d a c d a c e b c d 自连接l 3 即l 3 l 3 得到 从a b c 和a b d 得到a b c d 从a c d 和a c e 得到a c d e 再进行剪枝 a c d e 被删除掉了因为它的一个子集a d e 并4 i 在l 3 中 最后得到c 4 a b c d 这就是从长度为3 的频繁项目集集合l 3 中生成的艮度为4 的候选项目集集合 2 2 3 性能分析 下面举一个例子来说明a p r i o r i 算法的执行流程 如图2 2 所示 支持度阈值设 为2 t h e a p r i o r ia l g o r i t h m a ne x a m p l e 堕塑 壁l 业l 匿 q 匮避鲴 埕呈墨l