（模式识别与智能系统专业论文）基于事务数据表的关联规则挖掘技术研究.pdf

中文摘要 关联规则挖掘是数据挖掘的 一个非常重要的研究分支 难点在于其挖掘对象 是海量数据 a p r i o r i 算法需要对数据库进行多次扫描 在真正的海量数据库挖 掘中难以实用 f p g r o w t h 算法相对于a p r i o r i 算法在效率上提高了一个数量 级 但内存消耗大 在海量级数据库实现上也存在困难 当前国内外研究关联规 则的文献很多 大多数集中在对上述两个算法的改进上 本文研究如何由已知的事务数据库求出其相应的频繁项集和如何对由最大 频繁项集生成的关联规则进行有效性检验 本文针对频繁项集挖掘分类提出了基 于t d 处理事务数据表的频繁项集挖掘算法 分别用于产生完伞频繁项集 频繁 闭项集和最大频繁项集 算法在整个挖掘过程中 只需要扫描一次事务数据库 在由最大频繁项集生成关联规则的时候 可能会产生大量的冗余规则 这使得用 户分析和利用这些规则变得十分困难 本文对已有的多种关联规则删剪技术进行 了研究 发现了它们存在的问题 提出把约束性作为一种新的删剪技术 将基于 t d 处理事务数据表的频繁项集挖掘算法应用于m u s h r o o m 数据库的频繁项集挖掘 中 并通过算法分析说明本文提出的基于t d 处理事务数据表的频繁项集挖掘算 法在算法执行时间和空间的消耗上要优于f p g r o w t h 算法 关键词 关联规则完全频繁项集频繁闭项集最大频繁项集约束性 删剪技术t d 处理 a b s t i 认c t a s s o c i a t i o nr u l e sm i n i n gi sa ni m p o r t a n tf o r mo fd a t am i n i n g t h ed i f f i c u l t yo f m i n i n ga s s o c i a t i o nr u l e si s t h a tt h em i n i n go b j e c ti sv e r yl a r g ed a t a b a s e b e c a u s e a p f i o f ia l g o r i t h mn e e d st os c a nr e p e a t l ya n dt e d i o u s l yt h ed a t a b a s e i ti sn oa c t u a l v a l u et ot h er e a ld a t a b a s e f p g r o w t ha l g o r i t h mi sa b o u ta no r d e ro fm a g n i t u d ef a s t e r t h a nt h ea p n o f i b u tt h ea l g o r i t h mt a k e sm o r em e m o r y s ot h e r ei sd i f f i c u l t yt or e a l i z e t h ea l g o r i t h mi nr e a la p p l i c a t i o n si n v o l v i n gv e r yl a r g ed a t a b a s e a tp r e s e n tt h e r ea r ea l a r g en u m b e ro fb i b l i o g r a p h i e so nt h er e s e a r c ho fa s s o c i a t i o nr u l e si n l a n da n da b r o a d m o s to ft h e ma r ef o c u so nt h ei m p r o v e da l g o r i t h m sb a s e do nt h et w oa l g o r i t h m s t h em a i nc o n t e n to ft h i sd i s s e r t a t i o ni sa b o u th o wt og e n e r a t ef r e q u e n ti t e m s e t s f r o mk n o w nt r a n s a c t i o nd a t a b a s ea n dh o wt oc h e c ku pv a l i d i t yo fa s s o c i a t i o nr u l e s g e n e r a t e db ym a x i m a lf r e q u e n ti t e m s e t s a c c o r d i n gt oc l a s s i f i c a t i o no ff r e q u e n t i t e m s e t sm i n i n g t h i sd i s s e r t a t i o np r o p o s e st h r e ea l g o r i t h m sb a s e do nt dp r o c e s s i n g t r a n s a c t i o nd a t at a b l e t h ea l g o r i t h m sa r eu s e dt om i n ec o m p l e t ef r e q u e n ti t e m s e t s f r e q u e n tc l o s e di t e m s e t sa n dm a x i m a lf r e q u e n ti t e m s e t sr e s p e c t i v e l y i nt h ep r o c e s so f m i n i n g t h ea l g o r i t h m ss c a nt r a n s a c t i o nd a t a b a s eo n l yo n c e w h i l ea s s o c i a t i o nr u l e s g e n e r a t e df r o mm a x i m a lf r e q u e n ti t e m s e t s t h e r ea r eal a r g en u m b e ro fr e d u n d a n t r u l e s i ti sd i f f i c u l t yf o ru s e r st oa n a l y s ea n du t i l i z e i nt h i sd i s s e r t a t i o n s o m ee x i s t i n g p r u n i n gt e c h n o l o g i e sa r ea n a l y s e d t h r o u g hr e s e a r c h i n g t h e r ea r es o m ep r o b l e m s i n o r d e rt os o l v et h ep r o b l e m s t h i sd i s s e r t a t i o np r o p o s e san e wp r u n i n gt e c h n o l o g y n a m e dr e s t r i c t i o n t h ef r e q u e n ti t e m s e t sm i n i n ga l g o r i t h m sb a s e do nt dp r o c e s s i n g t r a n s a c t i o nt a b l ea r eu s e dt om i n ef r e q u e n ti t e m s e t si nr e a lm u s h r o o md a t a b a s e t h e f r e q u e n ti t e m s e t sm i n i n ga l g o r i t h m sb a s e do nt dp r o c e s s i n gt r a n s a c t i o nt a b l ea r e b e a e rt h a nf p g r o w t ha l g o r i t h mo nc o n s u m i n go ft i m ea n ds p a c e w h i c hi sp r o v e db y a l g o r i t h ma n a l y s i s k e yw o r d s a s s o c i a t i o nr u l e s c o m p l e t ef r e q u e n ti t e m s e t s f r e q u e n tc l o s e di t e m s e t s m a x i m a lf r e q u e n ti t e m s e t s r e s t r i c t i o n p r t m i n gt e c h n o l o g y t d p r o c e s s m g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果 除了文中特别加以标注和致谢之处外 论文中不包含其他人已经发表 或撰写过的研究成果 也不包含为获得苤壅盘堂或其他教育机构的学位或证 书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意 学位论文作者签名 王娟 签字日期 砌了年 月 日 学位论文版权使用授权书 本学位论文作者完全了解墨洼盘堂有关保留 使用学位论文的规定 特授权丕盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索 并采用影印 缩印或扫描等复制手段保存 汇编以供查阅和借阅 同意学校 向国家有关部门或机构送交论文的复印件和磁盘 保密的学位论文在解密后适用本授权说明 学位论文作者签名 签字日期 矿 7 年6 月r 日 导师签名 1 阿丕 签字日期 w 哆年否月弓日 力够 第一章绪论 1 1 选题背景及研究意义 第一章绪论弟一早珀1 匕 随着网络技术的飞速发展 网络在教育中的应用越来越广泛 网络教学日益 成为一种非常重要的教学方式 它以互联网作为传输信息的载体 为学生的学习 创建了广阔自由的环境 提供了丰富的资源 拓延了教学时空的维度 是网络和 多媒体技术相结合的一种新型教育技术 目前的网络教学系统大多数只是对所有学生线性地组织教学内容 按固定的 教学目标和策略进行教学 学生只能被动地接受完伞相同的学习内容 而没能考 虑不同学生因知识水平 认知能力等因素不同而对课程内容的不同需求 系统不 能根据学生的特点因材施教 存在着很大的不足口1 本文的选题背景是实验室承担的教育部 十一五 规划重点课题 面向自考 生的智能化网络学习资源建设研究 的一个子课题 为了弥补网络教学系统1 i 能对每个学生进行个性化学习服务的不足 本文将数据挖掘中的关联规则挖掘技 术引入到系统中 用于挖掘学生个性化特征信息中的潜在关联规则 学生的个性 化特征信息按信息的生存周期可分为静态特征信息和动态特征信息 其中静态信 息包括 学习者基本信息 如 姓名 性别 年龄 密码 i d 等 学习者的学 习偏好 动态信息包括 学习历史 如学生做过的练习和测试题及其答案 学习 者知识结构 如记录课程编号 知识点 错误数 最近一次测试情况 掌握程度 等 学生的个性化特征信息是实施个性化教学策略的基础 利用挖掘出的有效关 联规则对不同的学生制定不同的教学策略 真正地实现因材施教 因此 关联规 则技术的采用为网上学习系统的智能化 个性化提供了重要的技术手段 关联规则技术在网络教学系统中的应用可以提高教学系统的个性化服务水 平 为系统的决策分析提供了智能的辅助手段 使教学系统能根据学生知识结构 学习风格等个性特征进行个性化教学 从而提高学习者学习的积极性和主动性 提高学习效率 1 2 主要研究问题及国内外发展现状 本文的研究重点是关联规则挖掘技术 众所周知 关联规则挖掘可以分为两 个步骤 1 找出所有频繁项目集 2 由频繁项目集产生相应的强关联规则 本文的研究内容也是紧紧相扣于这两个步骤的 第一章绪论 关联规则最初由美国i b ma l i n a d e nr e s e a r c hc e n t e r 的a g r a w a lr 等人于1 9 9 3 年提出口 其最初提出的动机是针对购物篮分析问题 目的是为了发现事务数据 库中不同商品之间的联系规则 这些规则刻画了顾客购买行为模式 可以用来指 导商家科学地安排进货及货架设计等 最早被提出的关联规则挖掘算法是 a p r i o r i 算法 由于频繁项集生成过程的复杂性 特别随着数据集规模的增加 理论上需要考虑的项集数目和实际生成的频繁项集的数日巨大 所以提高频繁项 集的生成效率和可扩展性一直数据挖掘领域研究的热点之一 研究人员提出了很 多算法 从不同的角度对已有算法进行改进以提高算法的性能 如f p g r o w t h 法 基于矩阵的频繁项集挖掘算法h 力等 对频繁项集的关注也从经典频繁项集挖掘 扩展到最大频繁项集挖掘和频繁 闭项集挖掘 最大频繁项集和频繁闭项集是经典频繁项集中条件加强的结果 其 算法也多从经典频繁项集挖掘算法中发展而来 目前已经提出的可用于发现最大 繁项目集的算法有基于向量矩阵的频繁项集挖掘算法f i s m i n e r h 快速挖掘最 大频繁项集算法h 钉等 在f i s m i n e r 算法中 将所有频繁1 项集按支持度升序进 行排序并存储其对应的二进制位向量 将这些二进制位向量映射到向量矩阵进行 分析找出所有的频繁项集 既实现了数据库的一次扫描又避免了大量候选项集的 产生 但是 存储组合项的二进制位向量要占用一部分空间 如何在空间上提高 算法的效率成为值得研究的问题 快速挖掘最大频繁项集算法是一种基于布尔矩 阵的最大频繁项集挖掘算法 通过将f p t r e e 映射成布尔矩阵和权值表 运用布 尔逻辑运算进行矩阵投影操作得到最大频繁项集 算法在挖掘过程中不用生成最 大频繁候选项集 但f p t r e e 创建和维护所需的时间和空间仍是值得考虑的问题 一些近期提出的频繁闭项集挖掘算法有d c i c l o s e d i n d e x 算法阳川 基于图 论的频繁闭项集挖掘算法 等 d c i c l o s e d i n d e x 算法用 索引数组 来组织 数据 基于图论的频繁闭项集挖掘算法利用有向项集图来存储事务数据库中有关 频繁项集的信息 两个算法都提出了合理的数据结构来提高算法的效率 在了解了众多的频繁项集挖掘算法之后 接下来就要利用挖掘到的频繁项集 来产生相应的关联规则 传统的a p r i o r i 算法中规则生成方法简单 但计算复杂 规则之间存在着大量的冗余 特别当项集包含的项目较多时 生成的冗余规则成 指数增长 而且不能保证规则的有效性 这使得用户分析和利用这些规则变得十 分困难 为了帮助用户分析 可以采用各种技术来有效地减少大量冗余的规则 为了弥补置信度本身存在的缺陷 目前已有的关联规则删剪技术有相关性 提升 率 作用度 兴趣度等 1 3 本文主要工作 2 第一章绪论 本文的主要工作内容是 1 基于频繁项集的分类 提出了基于t d 处理事 务数据表的频繁项集挖掘算法 利用算法分别挖掘出事务数据库中的完全频繁项 集 频繁闭项集和最大频繁项集 2 对现有的冗余规则删剪技术进行研究 发 现提升率存在问题 提升率和相关性结论不一致等现象 基于这些问题的启发 提出了新的冗余规则删剪方法一约束性 3 经过大量实验后 发现了一些规 律 进行总结得出一些结论 4 将基于t d 处理事务数据表的频繁项集挖掘算 法应用于m u s h r o o m 数据库的频繁项集挖掘中 并通过算法分析说明本文提出的 基于t d 处理事务数据表的频繁项集挖掘算法在算法执行时间和空间的消耗上要 优于f p g r o w t h 算法 5 关联规则挖掘技术的应用 本文各章的内容安排 第一章 绪论部分主要介绍本文的选题背景和研究意义 及本文中相关技术 的国内外发展现状 第二章 具体介绍了关联规则挖掘的基本概念 关联规则的种类 经典 a p r i o r i 关联规则挖掘算法 基于a p r i o r i 的改进算法 f p g r o w t h 关联规则挖掘 算法 简要介绍了多层和多维关联规则挖掘及关联规则价值衡量的方法以及对三 种挖掘算法的研究 第三章 本文的核心部分 详细介绍了本文提出的基于t d 处理事务数据表 的频繁项集挖掘算法 并结合实例讲述如何利用算法来挖掘完全频繁项集 频繁 闭项集和最大频繁项集 第四章 针对现有的冗余关联规则的删剪技术进行研究 发现提升率存在问 题 在某些场合下 不能很好地发挥功能 以及提升率和相关性结论不一致等问 题 基于这些问题的启发 提出了约束性作为新的冗余关联规则的删剪技术 本 章的研究还处于初级阶段 有待于更一步地深入研究 第五章 将基于t d 处理事务数据表的频繁项集挖掘算法应用于m u s h r o o m 数 据库的频繁项集挖掘中 并通过算法分析说明本文提出的基于t d 处理事务数据 表的频繁项集挖掘算法在算法执行时间和空间的消耗上要优于f p g r o w t h 算法 所挖掘出的关联规则具有应用价值 第六章 总结与展望 总结了本文的工作成果 并提出下一步的研究方向 第二章关联规则挖掘算法研究 第二章关联规则挖掘算法研究 关联规则挖掘就是从大量的数据中挖掘出有价值 描述数据项之间相互联系 的有关知识 随着收集和存储在数据库中的数据规模越来越大 人们对从这些数 据中挖掘相应的关联知识越来越有兴趣 例如 从大量的商业交易记录中发现有 价值的关联知识就可帮助进行商品目录的设计 交叉营销或帮助进行其他有关的 商业决策 挖掘关联知识的一个典型应用实例就是超级市场利用前端收款机收集并存 储了大量的售货数据 这些数据是一条条的购买事务记录 每条记录存储了事务 处理时间 顾客购买的物品 物品的数量及金额等 这些数据中常常隐含形式如 下的关联规则 在购买铁锤的顾客当中 有7 0 的人同时购买了铁钉 这些关联 规则很有价值 商场管理人员可以根据这些关联规则更好地规划商场 如把铁锤 和铁钉这样的商品摆放在一起 能够促进销售 有些数据不像售货数据那样很容 易就能看出一个事务是许多物品的集台 但稍微转换一下思考角度 仍然可以像 售货数据一样处理 比如人寿保险 一份保单就是一个事务 保险公司在接受保 险前 往往需要记录投保人详尽的信息 有时还要到医院做身体检查 保单上记 录有投保人的年龄 性别 健康状况 工作单位 工作地址 工资水平等 这些 投保人的个人信息就可以看作事务中的物品 通过分析这些数据 可以得到类似 这样的关联规则 年龄在4 0 岁以上 工作在a 区的投保人当中 有4 5 的人曾 经向保险公司索赔过 在这条规则中 年龄在4 0 岁以上 是物品甲 工作在 a 区 是物品乙 向保险公司索赔过 则是物品丙 可以看出来 a 区可能污染 比较严重 环境比较差 导致工作在该区的人健康状况不好 索赔率也相对比较 高 2 1 基本概念 设i 之 乙 是由m 个不同项目组成的集合 d 是交易数据库 交易数 据库又称为事务数据库 其中每一个交易或事务t 是i 中一组项目的集合 即 t c i 每一个交易或事务t 都与一个惟一的标识符t i d 相联 对于项目集x i 如果x c t 则交易或事务t 支持x 如果x 中有k 个项目 则又称x 为k 一项目 集 或x 的长度为k 关联规则是指形式如下的一种数据隐含关系 x y 其中x c i y c i 且 x ny a 4 第二章关联规则挖掘算法研究 定义2 1 1 项目集x 的支持数 度 事务数据库d 中支持项目集x 的事务数 称为项目集x 的支持数 记为c o u n t x 设事务数据库d 中总的事务数为ldi 则项目集x 的支持度为 c o u n t x ldi 记为s u p x 定义2 1 2 关联规则x y 的支持数 度 事务数据库d 中支持项目集x uy 的事务数称为关联规则x y 的支持数 记为c o u n t x y 关联规则x y 的 支持度为 c o u n t x y ld 记为s u p x y 定义2 1 3 关联规则x y 的置信度 关联规则x y 的置信度定义为 c o u n t x y c o u n t x 记为c o n f x 寸y 为了挖掘出有意义的关联规则 一般需要给定两个阈值 最小支持度 m i n s u p 和最小置信度 m i n c o n f 前者表示了一组数据集在统计意义 卜所需满足的最低 要求 后者反映了用户对关联规则的最低置信度 关联规则挖掘的任务是 在给定的交易或事务数据库d 中 发现d 中所有的 强关联规则 所谓强关联规则是指这些规则的支持度 置信度分别1 i 低于用户给 定的最小支持度和最小置信度 2 2 关联规则的种类 将关联规则按不同的情况进行分类 1 基于规则中处理的变量的类别 关联规则可以分为布尔型和数值型 布尔型关联规则处理的值都是离散的 种类化的 它显示了这些变量之间的 关系 而数值型关联规则可以和多维关联或多层关联规则结合起来 对数值型字 段进行处理 将其进行动态的分割 或者直接对原始的数据进行处理 当然数值 型关联规则中也可以包含种类变量 例如 性别 女 一职业 秘书 是布尔型关联规则 性别 女 一a v g 收 入 2 3 0 0 涉及的收入是数值类型 所以是一个数值型关联规则 一 表示 规则中的蕴含关系 2 基于规则中数据的抽象层次 可以分为单层关联规则和多层关联规则 在单层的关联规则中 所有的变量都没有考虑到现实的数据是具有多个不同 的层次的 而在多层的关联规则中 对数据的多层性已经进行了充分的考虑 例如 i b m 台式机 s o n y 打印机 是一个细节数据上的单层关联规则 台 式机一s o n y 打印机 是一个较高层次和细节层次之间的多层关联规则 3 基于规则中涉及到的数据的维数 关联规则可以分为单维的和多维的 在单维的关联规则中 我们只涉及到数据的一个维 如用户购买的物品 而 在多维的关联规则中 要处理的数据将会涉及多个维 换成另一句话 单维关联 规则是处理单个属性中的一些关系 多维关联规则是处理各个属性之间的某些关 第二章关联规则挖掘算法研究 系 例如 啤酒一尿布 这条规则只涉及到用户购买的物品 性别 女 一职 业 秘书 这条规则就涉及到两个字段的信息 是两个维上的一条关联规则 给出了关联规则的分类之后 在下面的分析过程中 我们就可以考虑某个具 体方法适用于哪一类规则的挖掘 某类规则又可以用哪些不同的方法进行处理 2 3 经典a p t io ri 关联规则挖掘算法 在关联规则的挖掘算法中 以a g r a w a l 等人提出的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 i r d 算法 最为著名 它是一种最有影响和最为常用的 关联规则挖掘算法 其基本思想是将关联规则的挖掘分为如下两步 第一步 从事务数据库d 中找出所有支持度不小于用户指定的最小支持度阂 值的频繁项目集 在数据挖掘中 支持度不小于用户给定的最小支持度阈值的项 目集简称频繁项目集 第二步 使用频繁项目集产生所期望的关联规则 产生关联规则的基本原则 是其置信度不小于用户指定的最小置信度阈值 由于第二步较为容易和直观 因此挖掘出所有频繁项目集是该算法的核心 占据整个计算量的大部分 为了挖掘出事务数据库d 中所有的频繁项目集 a g r a w a l 等人建立了项目集 格理论 这个理论的核心原理是 频繁项目集的所有非空子集也是频繁项目集 非频繁项目集的任何超集亦是非频繁项目集 此原理一直被作为经典的数据挖掘 理论而被应用 2 3 1 产生频繁项集 a p r i o r i 算法是挖掘产生布尔关联规则所需频繁项集的基本算法 它也是一 个很有影响的关联规则挖掘算法 该算法利用了一个层次顺序搜索的循环方法来 完成频繁项集的挖掘工作 这一循环方法就是利用k 一项集来产生 k 1 一项集 具体做法就是 首先找出频繁卜项集 记为厶 然后利用厶来挖掘厶 即频繁 2 一项集 不断如此循环下去直到无法发现更多的频繁k 一项集位置 每挖掘一层厶 就需要扫描整个数据库一遍 a p r i o r i 利用层次循环发现频繁项集 输入 交易数据库d 最小支持阈值m i n s u p 输出 厶 d 中的频繁项集 处理流程 6 第二章关联规则挖掘算法研究 1 厶 f i n d f r e q u e n t l i t e m s e t d 发现卜项集 2 f o r k 2 l k l g k 3 c a p r i o r i g e n l k l m i n s u p 根据频繁 1 r 1 一项集产生候选k 一 项集 4 f o r e a c ht d 扫描数据库 以确定每个候选项集的支持频度 5 c r s u b s e t g t 获得t 所包含的候选项集 6 f o r e a c hc ec fc c o u n t 7 8 厶 c cjc c o u n t m i n s u p 9 r e t u r nl u 厶 p r o c e d u r ea p ri o r i g e n 厶 l m i n s u p 1 f o re a c h l k l 2 f o re a c h1 2 l k l 3 i f l l 1 2 l a l 一2 2 一2 a f l 一l m i n c o n f 则产生一个关联规则 s u p s s 一s 其中m i n c o n f 为最小置信度阈值 由于规则由频繁项目集产生 每个规则都自动满足最小支持度 2 4a p rio ri 的改进算法 作为经典的频繁项目集生成算法 a p r i o r i 算法在数据挖掘研究中具有里程 碑的作用 但随着研究的不断深入 发现a p r i o r i 算法存在如下两个缺陷 1 算法必须耗费大量的时间处理规模巨大的候选项目集 如频繁卜项目 集有1 0 0 0 0 个 候选频繁2 一项目集的个数将会超过i o m 如此大的候选项目集对 时问和主存空问都是一种挑战 2 必须多次重复扫描事务数据库 对候选项目集进行模式匹配 假如事 务数据库d 中有一个长度为2 0 的频繁项目集 那么至少需要扫描事务数据库2 0 次才能确定其频繁性 需要很大的i o 负载 正因为有如上两个缺陷 包括a g r a w a l 在内的许多学者提出了a p r i o r i 算法 的改进方法 这些算法仍然遵循上面的理论 但由于引入了相关技术 如数据分 割 抽样等 在一定程度上改善了a p r i o r i 算法的适应性和效率 2 4 1 基于散列 h a s h 的方法 p a r k 等人于1 9 9 5 年提出了一种基于散列 h a s h 技术产生频繁项目集的算 法 在他们的研究中发现 频繁2 一项目集生成的运算量较大 因此 p a r k 等人 引入散列技术来改进产生频繁2 一项目集的方法 这种方法把待扫描的项目集放 到不同的h a s h 桶中 每个项目集最多只可能放在一个特定的桶中 这样可以对 每个桶中的项目集进行测试 减少了候选项目集生成的代价 下面以候选频繁2 一项目集为例来讨论基于散列技术的频繁项目集的产生方 第二章关联规则挖掘算法研究 法 当扫描事务数据库d 中的每个事务时 我们可以产生每个事务的所有2 一项 目集 并将它们散列到相应的桶中 在哈希表中 对应的桶计数低于最小支持数 的2 一项集不是频繁2 一项集 即2 一项集支持数小于最小支持数 当然 这种方法 亦可扩展到任何的频繁k 一项目集的生成上 2 4 2 基于数据分割 p a r t tj o n 的方法 该方法只需扫描事务数据库两遍 在第一遍中 将大容量事务数据库d 从逻 辑上分成几个互不相交且能一次性装入内存的数据块 每块应用挖掘算法 如 a p r i o r i 算法 生成局部频繁项目集 由于d 中的频繁项目集作为局部频繁项目 集至少出现一次 即局部频繁项目集的并集包含d 中所有频繁项目集 这样 所 有局部频繁项目集可以作为d 中的候选频繁项目集 在第二遍扫描事务数据库d 时 计算每个候选频繁项目集的支持数 以确定d 中的频繁项目集 2 4 3 基于采样 s a m pl in g 的方法 1 9 9 6 年 t o i v o n e n 提出了一种基于采样 s a m p l i n g 技术产生频繁项目集的 算法 该算法的基本思想是 选取给定事务数据库d 中能反映整个数据分布的样 本s 然后在s 而不是在d 中搜索频繁项目集 采样是统计学经常使用的技术 虽然它可能得不到非常精确的结果 但是如果处理得当 可以在满足一定精度的 前提下提高挖掘效率或者在有限的资源下处理更多的数据 从本质上讲 使用一个抽样样本而不使用整个数据集的原凶是效率问题 许 多情况下使用整个庞大的数据库在时间方面是行不通的 仅对样本进行运算可以 使计算变得简单和更加可行 2 4 4 减少交易的个数 减少用于未来扫描的事务集的大小 一个基本的原理就是若一个事务不包含 长度为k 的大项集 则必然不包含长度为k l 的大项集 从而我们就可以将这些 事务移去 这样在下一遍的扫描中就可以减少要进行扫描的事务集的个数 2 5 基于f p t r e e 的关联规则挖掘算法f p g r o w t h h a nj i a w e i 等人于2 0 0 0 年提出了一种基于f p t r e e 的关联规则挖掘算法 f p g r o w t h 该算法仅需扫描数据库两次 不产生候选项目集 采用了 分而治 之 的策略 首先将提供频繁项目集的数据库压缩到一棵频繁模式树 f p t r e e 中 然后 将这种压缩后的数据库分成一组条件数据库 一种特殊类型的投影数 9 第二章关联规则挖掘算法研究 据库 并分别挖掘每个条件数据库 算法f p g r o w t h 将发现所有频繁项目集分解为以下两步 第一步 构造频繁 模式树f p t r e e 在f p t r e e 树中 每个节点由4 个域组成 节点名称n o d e n a m e 节点计数n o d e c o u n t 节点链指针n o d e i i n k 和父亲点指针n o d e p a r e n t 其中 n o d e n a m e 记录节点所表示的项目名 n o d e c o u n t 记录能到达该节点的交易数 n o d e i i n k 为指向f p t r e e 中具有相同的n o d e n a m e 值的下一节点 即通过 n o d e l i n k 将f p t r e e 中具有相同n o d e n a m e 值的节点链接起来 n o d e p a r e n t 为指向父节点的指针 另外 为了方便树遍历 创建一个频繁项目头表 它由两 个域组成 项目名称i t e m n a m e 以及节点链头n o d e h e a d 其中n o d e h e a d 为指 向f p t r e e 中具有相同n o d e n a m e 值的首节点的指针 第二步 调用f p g r o w t h 挖掘所有频繁项目集 1 频繁模式树f p t r e e 的构造 频繁模式树f p t r e e 的构造如下 1 扫描事务数据库d 一次 产生频繁卜项目集f 及其支持数 按其支持数 降序排列f 生成频繁项目列表l 2 创建频繁模式树的根节点r o o t 并标为 n u l 对于d 中的每个事务 作如下处理 按 中的次序排列事务中的频繁项目 设排列后的结果为 pp 其中p 是事务排列后的第一个项目 p 是剩余项目的列表 3 调用函数i n s e r t t r e e pp r o o t 函数i n s e r t t r e e pp r 的执行情况如下 如果r 有孩子n 使得n n o d e n a m e p 则n n o d e c o u n t n n o d e c o u n t l 否则创建一个新的节点n 该节点的设置为 n n o d e n a m e p n n o d e c o u n t l n n o d e p a r e n t r 并通过节点链指针n o d e ii n k 将其链接到具有相同n o d e n a m e 的节点 4 如果p 非空 将p 写成 pp 的形式 其中p 是p 的第一个项目 p 是剩 余项目的列表 设r n 转第 3 步 如果p 为空 结束 2 挖掘频繁项目集 基于f p t r e e 的频繁项目集挖掘算法是通过调用f p g r o w t h f p t r e e n u l l 来实现的 该过程的实现如下 p r o c e d u r ef p g r 0 w t h t r e e o f 1 i ft r e e 含单个路径pt h e n 2 f o r 路径p 中的每个组合 记为 d o 3 产生项目集o f u 卢 其支持数为 中节点的最小支持数 即为n o d e c o u n t 域的值 1 0 第二章关联规则挖掘算法研究 4 e l s e 5 f o re a c ht r e e 的头部伍d o 6 产生一个项目侈 口u c t i 其支持数位口 的支持数 7 构造 的条件模式 然后构造 的条件频繁模式树t r e e 月 8 i ft r e e 非空t h e n 9 调用f p g r o w t h t r e e 日 基于f p t r e e 的关联规则挖掘算法f p g r o w t h 是将发现频繁模式的问题转换 成递归地发现一些短模式 然后链接后缀 它使用最不频繁的项目作后缀 提供 了较好的选择性 显著降低了搜索开销 2 6 多层关联规则挖掘 对于事务或关系数据库来说 一些项或属性所隐含的概念是有层次的 例如 我们说商品 羽绒服 对于分析或决策者来说 有可能更关心的是高层次概念 冬季服装 服装 等 对于不同的用户 可能某些特定层次的关联规则更有 意义 同时 由于数据的分布和效率方面的考虑 数据可能在多层次粒度上存储 从某种程度来讲 挖掘多层次关联规则就可能得出更深入 更有说服力的知识 根据规则中所涉及的层次 多层次关联规则可以分为同层关联规则和层间关 联规则 1 同层关联规则 如果一个关联规则所对应的项目是属于同一粒度层次 那么它是同层关联规 则 例如图2 1 给出了一个关于商品的多层次概念树 针对这样的概念层次划分 牛奶 面包 和 羽绒服一酸奶 都是同层关联规则 图2 1 多层次概念树 第二章关联规则挖掘算法研究 2 层间关联规则 如果在不同的粒度层次上考虑问题 那么可能得到的是层问关联规则 例如 夏季服装一酸奶 目前多层次关联规则挖掘的度量方法基本上仍沿用 支持度一置信度 的框 架 不过 对支持度的设置还需要考虑不同层次的度量策略 一般情况下有两种 基本的度量策略 1 同一层次的最小支持度对于所有的层次 使用同一个最小支持度 2 不同层次使用不同的最小支持度每个层次都有自己的最小支持度 较 低层次的最小支持度相对较小 而最高层次的最小支持度相对较大 这种方法增 加了挖掘的灵活性 但也留下了需要解决的许多相关问题 对于多层次关联规则挖掘的策略问题 可以根据应用特点 采用灵活的方法 来完成 1 自上而下方法 先找到高层次的规则 如 冬季服装一牛奶 再找它的下一层规则 如 羽 绒服j 鲜奶 如此逐层自上而下挖掘 不同层次的支持度可以一样 也可以根 据上一层次的支持度动态生成下一层次的支持度 2 自下而上方法 先找低层次的规则 再找它的上一层次规则 不同层次的支持度也可以动态 生成 3 在一个固定层次上挖掘 用户可以根据情况 在一个固定层次挖掘 如果需要查看其他层次的数据 可以通过上钻和下钻等操作来获得相应的数据 2 7 多维关联规则挖掘 涉及两个或多个维的关联规则称为多维关联规则 多维关联规则有维内的关 联规则和混合维关联规则等常见的形式 1 维内的关联规则 例如 年龄 x 2 0 u3 0 a 职业 x 学生 4 购买 x 笔记本电脑 这里将涉及到三个维 年龄 职业 购买 相比而言 前面所介绍的诸如 啤酒 一尿布 只涉及 购买 单一维 因此它被称为单维关联规则 2 混合维关联规则 这类规则允许同一个维重复出现 例如 年龄 x 2 0 u3 0 a 购买 x 笔记本电脑 一购买 x 打印机 由于同一维 购买 在规则中重复出现 因此为关联规则的挖掘带来了一定的难度 但是这类规则更具有普遍性 具有更 1 2 第二章关联规则挖掘算法研究 好的应用价值 因此得到普遍关注 另外 在挖掘多维关联规则时 还要考虑数值型字段的离散化处理等问题 2 8 关联规则价值衡量的方法 当我们用数据挖掘的算法得出了一些结果之后 数据挖掘系统如何知道哪些 规则对于用户来说是有用的 有价值的 这里有两个层面 用户主观的层面和系 统客观的层面 2 8 1 系统客观层面 很多的算法都使用 支持度一置信度 的框架 这样的结构有时会产生一些 错误的结果 看如下的一个例子 假设一个提供早餐的零售商调查了4 0 0 0 名学生在早晨进行什么运动 得到 的结果是2 2 0 0 名学生打篮球 2 7 5 0 名学生晨跑 1 8 0 0 名学生打篮球 晨跑 那 么如果设m i n s u p 为4 0 m i n c o n f 为6 0 我们可以得到如下的关联规则 打篮球一晨跑 这条规则其实是错误的 因为晨跑的学生的比例是6 8 甚至大于6 0 然 而打篮球和晨跑可能是否定关联的 即 打篮球斗 不 晨跑 虽然这条规则的支持度和置信度都比那条蕴涵正向关联的规则 1 低 但是 它更精确 然而 如果我们把支持度和置信度设得足够低 那么将得到两条矛盾 的规则 但另一方面 如果把那些参数设得足够高 我们只能得到不精确的规则 总之 没有一对支持度和置信度的组合可以产生完全正确的关联 于是人们引入了兴趣度 用来修剪无趣的规则 即避免生成 错觉 的关联 规则 一般一条规则的兴趣度是在基于统计独立性假设下真正的强度与期望的强 度之比 然而在许多应用中已发现 只要人们仍把支持度作为最初的项集产生的 主要决定因素 那么要么把支持度设得足够低以使得不丢失任何有意义的规则 或者冒丢失一些重要规则的风险 对前一种情形计算效率是个问题 而后一种情 形则有可能丢失从用户观点来看是有意义的规则的问题 r s r i k a n t 给出了感兴趣的规则的定义 r i n t e r e s t i n g 其后并对此作了 改进 j s p a r k 把事件依赖性的统计定义扩展到兴趣度的定义上来 a s a v a s e r e 定义了否定关联规则的兴趣度 2 8 2 用户主观层面 第二章关联规则挖掘算法研究 上面的讨论只是基于系统方面的考虑 但是一个规则的有用与否最终取决于 用户的感觉 只有用户可以决定规则的有效性 可行性 所以我们应该将用户的 需求和系统更加紧密地结合起来 可以采用一种基于约束 c o n s t r a i n t b a s e d 的挖掘 具体约束的内容可以包 括以下儿方面 1 数据约束 用户可以指定对哪些数据进行挖掘 而不一定是全部的数 据 2 指定挖掘的维和层次 用户可以指定对数据哪些维以及这些维上的哪 些层次进行挖掘 3 规则约束 可以指定哪些类型的规则是我们所需要的 引入一个模板 t e m p l a t e 的概念 用户使用它来确定哪些规则是令人感兴趣的而哪些则不然 如果一条规则匹配一个包括的模板 i n c l u s i v et e m p l a t e 则是令人感兴趣的 然而如果一条规则匹配一个限制的模板 r e s t r i c tt e m p l a t e 则被认为是缺乏 兴趣的 其中有些条件可以和算法紧密地结合 从而既提高效率 又使挖掘的目的更 加明确 2 9 三种频繁项集挖掘算法研究 在完全频繁项集挖掘算法发展基础上 又分别提出了用于挖掘频繁闭项集和 最大频繁项集的算法 下面 将分别介绍完全频繁项集 频繁闭项集和最大频繁 项集的算法发展现状 2 9 1 完全频繁项集挖掘算法 传统的 完全 频繁项集挖掘算法主要有a p r i o r i 类 蜘算法 f p t r e e 算法 乜叫等 其中a p r i o r i 类算法是基于产生候选项集的 其缺点是 1 需要保存生 成的候选项集 中间结果 即候选 k 1 一项集的产生需要频繁k 一项集做基础 在支持度较低的时候 如果出现了比较 长 的频繁项集时 a p r i o r i 算法代价 很高 2 需要不断产生大量候选项集 有些项集是冗余的 即这些项集在事务 数据库中并未出现 3 需要多次扫描数据库 f p t r e e 算法的优点是不需要产 生候选项集 在挖掘过程中先构造f p t r e e 然后对f p t r e e 进行挖掘产生频繁 项集 在内存能满足要求的情况下只需2 次扫描数据库 但是如果内存无法满足 要求时 这类算法就变得相对较为复杂 需要扫描数据库的次数会多于2 次 其 i o 开销会随之增加心 目前 在挖掘频繁项集的研究中 很多组织和研究人员 1 4 第二章关联规则挖掘算法研究 围绕a p r i o r i 与f p t r e e 这2 个算法从不同角度对其进行深入研究瞳引 此外 其他一些研究人员从数据的存储方式 数据的表示方法 搜索方式等 方面来研究 提出了 些挖掘算法 1 0 p p o r t u n e p r o j e c 算法 3 算法是国内学者刘君强等人提出的 根据局部 数据集的特性动态地决定对数据库采用基于树的虚拟投影或者基于数组的非过 滤投影 从而较好地解决了提高效率与节省空间的矛盾 该算法主要采用深度优 先的搜索方法 但在必要的时候 也会用广度优先的方法先建立树的最上面几层 该算法与a p r i o r i f p t r e e 等算法相比 具有更好的性能 2 基于d i f f s e t 挖掘方法 3 d i f f s e t 是z a k i 等人提出的一种对数据的纵 向表示法 d i f f s e t 只保存候选频繁项集与产生的频繁项集在事务集上的差集 这样可以节省大量的存储空间 3 g r a h n e 等人提出的算法陋 利用数组来存储条件模式库的频度数据 在 建立条件f p t r e e 的同时计算以各个项目为后缀的条件模式库的频度数组值 因 此 在建立每棵条件f p t