（管理科学与工程专业论文）关联规则挖掘算法研究.pdf

关联规则挖掘算法研究 摘要 关联规则挖掘是数据挖掘领域中的一个非常重要的研究内容，其主要目标 就是发现数据库中一组对象之间某种有趣关联或相关联系。近年来，关联规则 挖掘研究成为数据挖掘中的一个热点，并被广泛应用于市场营销、事务分析等 领域。 本文对经典关联规则挖掘算法进行了系统的研究和全面的总结，在此基础 上提出了新的关联规则挖掘及更新算法。 首先，本文介绍了数据挖掘、关联规则挖掘的基本知识和一些经典的关联 规则算法。 然后，针对f p g r o w t h 算法的不足，本文从数据结构与挖掘方法两个方面 进行改进，提出了基于i c f p 树的频繁模式挖掘算法q m f i i c f p 。该算法减少 了f p 树所占用的内存，节省了条件模式树生成所耗的时间。实验表明该算法 比f p g r o w t h 算法具有更好的性能。 最后，论文对在支持度和数据库增加同时发生变化的情况下，如何快速更新关 联规则的问题进行了详细的分析研究，提出了一种基于矩阵的关联规则更新算法 i u b m ，并对该算法进行了分析和讨论。与其他算法相比，该算法仅需扫描一遍新增 的数据库d b ，因此该算法具有较高的效率。 关键词：数据挖掘：关联规则；f p 树；矩阵；增量更新 t h er e s e a r c ho nt h e a l g o r i t h m so fm i n i n ga s s o c i a t i o nr u l e s a b s t r a c t a so n eo ft h ei m p o r t a n tc o n t e n t si nd a t am i n i n g ，a s s o c i a t i o nr u l em i n i n ga i m s t od i s c o v e rt h ei n t e r e s t i n gc o n n e c t i o no rt h ec o r r e l a t i o nm i d s tas e to fo b j e c t si na d a t a b a s e a s s o c i a t i o nr u l em i n i n gh a sb e c o m eah o tr e s e a r c ht o p i ci nr e c e n ty e a r s ， a n di th a sb e e nu s e dw i d e l yi ns e l e c t i v em a r k e t i n g ，d e c i s i o na n a l y s i sa n db u s i n e s s m a n a g e m e n t i nt h et h e s i s ，s o m ec l a s s i c a la l g o r i t h m sf o rm i n i n ga s s o c i a t i o nr u l e sh a v eb e e n s y s t e m a t i c a l l ys t u d i e da n dc o m p r e h e n s i v e l ys u m m a r i z e d o nt h eb a s i co fp r e v i o u s r e s e a r c h ，t h en o v e la l g o r i t h m s f o r m i n i n g a s s o c i a t i o nr u l e sa n di n c r e m e n t a l u p d a t i n go fa s s o c i a t i o nr u l e sa r ep r o p o s e d f i r s t l y , t h et h e s i s i n t r o d u c e ss o m eb a s i ck n o w l e d g eo fd a t a m i n i n ga n d a s s o c i a t i o nr u l e sa n ds o m ec l a s s i c a la l g o r i t h m sf o ra s s o c i a t i o nr u l e s s e c o n d l y ，t h et h e s i sa n a l y s e st h ed i s a d v a n t a g eo ff p g r o w t h t a k i n gm e a s u r e s f r o md a t as t r u c t u r ea n dm i n i n gm e a n s ，an o v e la l g o r i t h mf o rm i n i n gf r e q u e n t p a t t e r n sb a s e do ni m p r o v e dc o m p r e s s e df p - t r e e ，i e q m f i i c f p , i sp r o v e d t h i s a l g o r i t h m s a v e sl a r g em e m o r y s p a c eo c c u p i e db y f p - t r e ea n dt h ec o s to f c o n s t r u c t i n gm a n yc o n d i t i o n a lf p - t r e e s e x p e r i m e n t ss h o wt h a tt h et i m ea n ds p a c e f o rq m f i - i c f ph a v er e d u c e ds i g n i f i c a n t l yc o m p a r e dt of p g r o w t hm i n i n g f i n a l l y , an e wi n c r e m e n t a lu p d a t i n ga l g o r i t h mb a s e do nm a t r i xf o rm a i n t a i n i n g d i s c o v e r e da s s o c i a t i o nr u l e s ，i e i u b m ，u s e dw h e nt h et r a n s a c t i o nd a t a b a s e i n c r e a s e sa n dt h em i n i m u ms u p p o r tc h a n g e s ，i s p r e s e n t e di n t h et h e s i s s o m e a n a l y s i st ot h en e wa l g o r i t h mi sp r e s e n t e d c o m p a r e dw i t ht h eo t h e ra l g o r i t h m ，t h e a l g o r i t h mj u s ts c a n st h en e wd a t a b a s ed bo n c e ，t h e r e f o r ei t h a sah i g h e re f f i c i e n c y k e yw 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 ；f p - t r e e ；m a t r i x ；i n c r e m e n t a lu p d a t i n g 插图清单 图3 1f p 树 图3 2c f p 树一 图3 3 映射的频繁项集 图3 4 频繁项头表及i c f p 树的最左边分枝 图3 5 插入记录1 后的i c f p 树 图3 6 插入记录2 ，3 ，4 后的i c f p 树 图3 7 插入记录5 后的i c f p 树 图3 8 插入记录5 后的i c f p 树 图3 9 ( a ) 初始化子树s u b t r e e ( 4 ) 图39 ( b ) 子树s u b t r e e ( 4 ) 遍历完后 图3 1 0 ( a ) 初始化子树s u b t r e e ( 3 ) 图3 1 0 ( b ) 子树s u b t r e e ( 3 ) 遍历完后 图3 1 l 子树s u b t r e e ( 2 ) 遍历完后 图3 1 2 子树s u b t r e e ( 2 ，3 ) 遍历完后 图3 1 3c h e s s 数据集上两种算法的比较 图3 1 4 t 1 0 1 4 d 1 0 0 k 数据集上两种算法的比较 图4 1 矩阵图 图4 2 对应数组值 图43 修改后的矩阵图 图4 4 修改后的对应数组值 埒m幅掩侈侉矽m m”筋筋拍卯勰”驺 表格清单 表2 1f p 示例数据库1 2 表2 2 通过创建条件模式基挖掘f p - t r e e 。1 3 表3 1c f p 示例数据库1 4 表3 2 在c h e s s 数据集上的执行时间2 7 表3 1 3 在t l o l 4 d 1 0 0 k 数据集上的执行时间2 8 表4 1 原事务数据库3 0 表4 2 整数化的事务数据库 表4 3 符号定义说明3 3 表4 4 数据库d b 3 6 表4 5d b 的矩阵向量b v 3 6 表4 6 ( d b 对应的) 矩阵表a r m 3 6 表4 7 ( d b 对应的) 对应数组值a r v 。3 6 表4 8 新增数据库d b 3 6 表4 9 曲的矩阵向量b v 。3 6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得叠墨王些盔堂或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：謦朝， 签字日期：川年占月巧日 学位论文版权使用授权书 本学位论文作者完全了解盒8 b 王些太堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金世 工、业盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名：j 留勿 签字日期：弦7 年j ，月以日 电话 邮编 榭咖毋 名 年 签订 睹 撕 文 期 埝 日 位 字 学 签 致谢 值此论文完成之际，我谨向所有关心和帮助过我的老师，同学、朋友以及 家人致以最真诚的谢意! 首先，我要特别感谢我的导师倪志伟教授。倪老师治学严谨，学识渊博， 使我在理论学习上受益匪浅，且对我的生活和工作也是关怀备至。从论文选题 到最终成文，一直得到老师的指导和大力支持，才使得我能够顺利完成论文撰 写。在此，我谨向我的导师致以崇高的敬意和衷心的感谢! 我要感谢师兄吴吴、吴俊、伍章俊、赖大荣、张威和蔡博文在我实习和求 职的过程中所提供大量的帮助。特别感谢合肥信息技术服务有限公司的所有同 事，在将近一年的时间里所给予我的关怀与帮助。 感谢合肥工业大学管理学院智能管理研究所的同学们，正足在和你们的交 流和帮助下，我才得以不断提高，衷心地祝愿你们学业有成、前程似锦! 最后我要感谢我的家人，感谢他们二十多年来给予我在学习和生活方面 的支持和鼓励，使我能够安心学习，顺利完成学业! 1 1 论文研究背景和意义 第一章绪论 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的 数据越来越多。激增的数据背后隐藏着许多有价值的重要信息，人们希望对这 些数据进行更高层次的分析，以便更好地利用这些数据，达到为决策服务的目 的。没有强有力的分析工具，理解这些海量的、类型各异的数据己经远远超出 了人的能力数据挖掘方法的提出，让人们最终有能力认识到数据的真正价值， 即蕴藏在数据中的信息和知识。数据挖掘( d a t am i n i n g ) 指的是从大型数据库 或数据仓库中提取人们感兴趣的知识，这些知识是隐含的、事先未知的、潜在 的有用信息。 数据挖掘的任务是从数据中发现模式，分为6 种：分类模式、回归模式、时 间序列模式、聚类模式、关联模式、序列模式，其中关联模式的挖掘是目前数 据挖掘领域中最为广泛的研究课题之一。 数据项之间的关联规则称为关联模式。本文所要讨论的问题集中在数据挖 掘中的关联规则上。关联规则起初主要应用于对购物篮的分析，关联规则是发 现交易数据库中不同商品之间的联系，这些规则找出顾客购买行为模式，如购 买了某一商品对购买其他商品的影响。发现这样的规则可以应用于商品货架设 计、货存安排以及根据购买模式对用户进行分类虽然关联规则是伴随零售业 的飞速发展而产生的一种需求，但它的应用决不仅仅在零售业上，还体现在金 融、生物，证券和安全交易、电信、公安等，所以展开对关联规则的研究具有 重大意义。 1 2 国内外研究现状 1 9 9 3 年a g r a w a lr 等人首先提出了关联规则的问题【2 ，并于1 9 9 4 年提出了挖 掘关联规则的经典算法a p f i o r i 算法【3 1 ，这个算法奠定了关联规则挖掘算法的基 础，之后不少国内外学者、机构对关联规则挖掘进行了大量的研究。 为了提高算法挖掘规则的效率，不少学者进行了大量的研究，并对原有的 a p r i o r i 算法进行了优化，如引入了散列方法【4 】f 5 】、事务压缩6 】【7 】、划分的思想扪、 随机采样【9 】和动态集计数【l o 】等。但这些算法都不能避免a p r i o r i 系列算法固有的 缺陷，就是需要多次重复扫描数据库，而且可能产生大量的候选项集。 针对a p r i 耐算法的固有缺陷，j i a w e i h a n 等提出了不产生候选挖掘频繁项 集的方法f pg r o w t h 算法【l ”，实验表明，f p g r o w t h 算法对不同长度的规则都 有很好的适应性，同时在效率上较之a p r i o r i 算法有巨大的提高。但如果大项集 的数量很多，并且如果由原数据库得到的f p t r e e 的分支很多且分支长度很长 时，该算法将需要构造出数量巨大的条件f p t r e e ，不仅费时而且要占用大量的 空间，挖掘效率不高，而且递归算法本身效率也较低。为此研究者提出了许多 改进的算法：文献【l2 1 中的f p g r o w t h * 算法利用f p - a r r a y 技巧大大改善了挖掘性 能。文献【l3 】提出了h m i a 算法，该算法使用了一种超链接数据结构h s t r u c t ， 能在挖掘处理过程中动态修改数据链接求频繁项集的。文献1 1 4 j 使用了一种特殊 的树p t r e e ，仅需遍历一次数据库，就可计算出所有的关联规则。文献【i5 j 使用 了i 临时根节点的技巧，有效解决了挖掘过程中不断产生和释放条件模式树的缺 点。文献【l6 】中的c f p t r e e 是对f p t r e e 的进一步压缩存储，尤其是对密集型数 据库，极大减小了存储空间；文献【1 7 1 【18 】1 9 j 【2 0 j 对关联规则的并行挖掘进行了研究。 上述关联规则挖掘算法都基于两个前提：事务数据库中的元组数不变； 最小支持度和最小置信度不变。关联规则的增量式更新算法就是对以上两个 前提不成立时的关联更新问题。已有许多研究人员对如何高效地更新关联规则 进行了分析和研究，并提出了相应的算法。其中关联规则的更新主要涉及四个 方面：第一，在给定的最小值支持度下，当数据库内容增加时关联更新的问题 1 2 1 1 2 4 1 1 2 6 1 1 2 8 1 ；第二，数据库不变，最小支持度发生变化的关联更新问题 2 3 1 1 2 5 1 1 a 7 1 1 2 9 1 ；第三，在给定的最小值支持度和置信度下，当数据库内容删除时 关联更新的问题 2 2 3 3 2 】【3 3 l ；第四，在实际应用中，数据库内容和最小支持度经 常同时发生变化，文献 3 0 】【3 1 l 【3 4 】给予了关注，并提出了基于f p 树的解决方法。 挖掘关联规则的挑战性在于数据量巨大，算法的效率是关键，因此有必要 研究出占用内存小、i o 操作少、执行速度快的高效算法。 1 3 论文的工作与组织结构 1 3 1 论文的工作 本文对经典关联规则挖掘算法进行了系统的研究和全面的总结，在此基础 上提出了新的关联规则挖掘及更新算法。本文工作主要体现在以下几个方面： 第一。提出了一种基于i c f p - 树的频繁模式挖掘算法q m f i - i c f p 。论文详细 介绍了i c f p - 树的定义以及构造方法，然后对基于i c f p 一树的频繁模式挖掘问题 进行了详细地分析研究，提出了q m f i - i c f p 算法；最后用j a v a 对算法进行了实 现，给出了与f p g r o w t h 算法的性能比较结果。 第二，提出了一种基于矩阵的改进增量更新算法i u b m 。论文对在支持度和 数据库增加同时发生变化的情况下，如何快速更新频繁项集的问题迸行了详细 的分析研究，并提出了i u b m 算法，最后给出了一个详细的实例分析。 1 3 2 论文的组织结构 围绕着上述研究工作，本文的组织结构如下。 第二章，首先介绍了数据挖掘的定义、方法和应用领域；接着给出关联规 则的基本概念，并详细描述了关联规则挖掘的两种经典算法。 第三章，首先介绍了新的数据结构i c f p 一树的定义、构造，然后提出了基 于i c f p - 树结构的频繁模式挖掘算法q m f i i c f p ，最后对算法q m f i i c f p 和 f p g r o w t h 进行了比较试验，并在不同的数据集上对其进行了性能分析。 第四章，首先详细介绍了a b m 算法和u b m 算法的基本思想，然后对在支持 度和数据库增加同时发生变化的情况下，如何快速更新关联规则的问题进行了 详细的分析研究，提出了i u b m 算法，最后给出了一个详细的实例分析。 第五章，对全文进行了简要的总结，并对今后的工作进行了展望。 2 1 数据挖掘概述 第二章数据挖掘与关联规则 随着社会的发展，数据量急剧膨胀，数据的时效性和复杂性远远超过了当 前的信息处理能力。信息化和全球化是二十一世纪的最大特征，在网络技术的 推动下，近十几年来，人们生产和搜集数据的能力大幅度地提高，而数据获得 和生产能力大大超过数据处理的能力。现今，由于数据生产、传输能力与数据 分析能力的不平衡，人们被数据淹没，寻找隐藏在其中的有用信息无异于大海 捞针。人们希望能够提供高层次的数据分析功能，自动和智能地在待处理的数 据中寻找和发现有用的信息知识。数据挖掘( d a t am i n i n g ) 技术也因此应运而 生，并蓬勃发展，越来越显示出强大的生命力。 2 1 1 数据挖掘的定义 什么是数据挖掘? 数据挖掘就是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信 息和知识的过程。 数据挖掘是揭示存在于数据里的模式及数据间的关系的学科，它强调对大 量观测到的数据库的处理。它是涉及数据库管理，人工智能，机器学习，模式 识别，及数据可视化等学科的边缘学科。 数据挖掘是可以从大量数据中挖掘出隐含的、先前未知的、对决策有潜在 价值的知识和规则的高级处理过程。通过数据挖掘，有价值的知识、规则或高 层次的信息就能从数据库的相关数据集合中抽取出来，并从不同角度显示，从 而使大型数据库作为一个丰富、可靠的资源为知识的提取服务。 2 1 2 数据挖掘的方法 数据挖掘方法可以分为： ( 1 ) 统计方法：统计学方法可用于对数据的建模。统计方法可细分为：回 归分析、判别分析、聚类分析、探索性分析等。其中回归分析方法是用一组独 立变量和常量来估计一个因变量，主要有线性回归模型、非线性回归模型和非 线性多重回归模型。统计方法可用于分类、聚类和预测等应用。 ( 2 ) 机器学习方法：机器学习法的核心问题是从特殊的训练样本中归纳出 通用函数。机器学习方法可用于分类、聚类和预测等应用。 机器学习可细分为：归纳学习方法、基于范例学习、遗传算法等。 ( 3 ) 神经网络方法：它从结构上模仿生物的神经网络，是一种通过训练数 据集来学习的非线性预测模型。神经网络方法可以用于分类、聚类、特征挖掘 等多种应用。 神经网络方法可细分为：前向神经网络、自组织神经网络等。 ( 4 ) 数据库方法：主要是多维数据分析或联机分析方法，另外还有面向属 性的归纳方法。 ( 5 ) 粗糙集方法：粗糙集理论是一种研究模糊、不完整、不确定知识和数 据的表达、学习、归纳的理论方法，主要用于分类挖掘，数据约简等应用。 ( 6 ) 决策树方法：是一种用树形结构来表示决策集合的方法。其中决策集 合通过对数据集进行分类来产生规则。主要的决策树方法有i d 3 、c 4 5 、c 5 0 和 c a r t 。 ( 7 ) 贝叶斯网络：也称为因果网络、概率网络、影响图和认知图。它将不 确定事件以网络的形式相互连接起来，通过这种关系网络人们可以对某一与其 它事件有关的事件的结果进行预测。 ( 8 ) 最近邻技术：通过足个与选定记录最相近的历史纪录的组合来辨别新 的记录。最近邻技术主要应用于聚类分析、偏差分析等。 在当前的数据挖掘软件包中被用到的分析过程包括：决策树推断、规则推 断、最近邻方法、聚类方法、联合规则、特征提取、可视化。另外，有些还包 括：神经网络、图形模型、遗传算法、自组织图、神经模糊系统。 2 1 3 数据挖掘的应用 数据挖掘的目的是：提高市场决策能力；检测异常模式；在过去的经验基 础上预言未来趋势等。它不仅能用于控制成本，更重要的是能给企业带来效益。 很多企业都在利用数据挖掘技术帮助管理客户生命周期的各个阶段，包括 争取新的客户、在已有客户的身上赚更多的钱、和保持住好的客户。如果能够 确定好的客户的特点( 如性别、年龄、职业等) ，那么就能为客户提供针对性 的服务。比如，已经发现了购买某一商品的客户的特征，那么就可以向那些具 有这些特征但还没有购买此商品的客户推销这个商品：找到流失的客户的特征 就可以在那些具有相似特征的客户还未流失之前采取针对住的弥补措施，因为 保留一个客户要比争取一个客户便宜的多，也更容易。 数据挖掘技术可以应用在很多不同的领域。电信公司和信用卡公司是用数 据挖掘技术来检测欺诈行为的先行者。保险业也开始用数据挖掘技术来减少欺 诈。在医疗领域中，数据挖掘技术可以用来预测外科手术、医疗试验和药物治 疗的效果。制药公司通过挖掘化学物质和基因对疾病的影响的数据库来判断哪 些物质可能对治疗某种疾病产生效果。零售商更多的使用数据挖掘技术来解决 每种商品在不同地点的库存，了解消费者的消费模式，通过数据挖掘更灵活的 使用促销和优惠券手段。 当前，在电信领域中数据挖掘技术的贡献有：电信数据的多维分析；欺诈 模式分析与非正常模式的确定与辨别；关联规则及序列模式的分析。数据挖掘 在金融领域中的应用有：设计和建立数据仓库，并进行多维数据分析与数据挖 掘；贷款还贷预测以及客户的信用分析；目标市场客户的聚类与分类；金融犯 罪行为的发现。在商业中的应用：基于商业数据的数据仓库的建立；销售、信 息、客户、产品、时间和区域的多维分析；商业促销行为分析；客户忠诚度分 析；相关产品推荐。 由于数据挖掘技术的良好的应用前景，各大软件公司及大学研究机构对此 开展了研究。一批数据挖掘系统被开发出来，其中比较有代表性的有： ( 1 ) i b m 公司的i n t e l l i g e n tm i n e r ，它提供了较全面的数据挖掘算法，良 好的算法伸缩性，并可以和d b 2 集成在一起使用。 ( 2 ) s a s 公司的s a se n t e r p r i s em i h e r ，它包括回归、分类、统计分析， 其特点是有较强的统计分析功能。 ( 3 ) i s ld e c i s i o ns y s t e m s 公司的c 1 e m e n t i n e ，它的挖掘算法包括规则归 纳，神经网络、分类及可视化工具。 其它产品还有t a n d e m 的r e l a t i o n a ld a t am i n e r ，a n g o s ss o f t w a r e 的 k n o w l e d g es e e d e r 等等。除了这些综合软件包外，还有许多专门用途的产品。 另外，许多专业于数据挖掘的咨询公司也成立了。 2 2 关联规则基本概念 关联规则就是从大量的数量中挖掘出有价值描述数据项之间相互联系的有 关知识。随着收集和存储在数据库中的数据规模越来越大，人们对从这些数据 中挖掘相应的关联知识越来越有兴趣。例如：从大量的商业交易记录中发现有 价值的关联知识就可帮助进行商品目录的设计、交叉营销或帮助进行其它有关 的商业决策。 2 2 ，1 基本概念 设，= i 。，i ：，i 为数据项集合，口= t ，t ：，t - ) ，其中乃i 称为一个交 易或事物，称d 为i 上的交易集或者数据集，简称交易集或数据集。 基于以上基本假设，下面给出关联规则相关定义： 定义2 1 关联规则 关联规则就是具有a j b 形式的蕴含式，其中有a c i ，b i 且4 n 占= 谚。 衡量关联规则是否有意义有两个标准：支持度和置信度。 定义2 2 支持度 给定数据集d ，关联规则a j b ，令 s u p p ( 彳j 耻p ( ak 3 耻盟坐等竺剑 m 称s u p p ( a j b ) 为关联规则a j b 在数据集d 上的支持度。 定义2 3 置信度 给定数据集d ，关联规则a b ，令 c o n f ( a 等口，= 尸c 曰f 一，= ；占写 帮 称。矿( 4 j b ) 为关联规则a jb 在数据集d 上的置信度。 定义2 3 强关联规则、最小支持度、最小置信度 绘定数据集d 和关联规则a jb ，并给定m i n s u p ( o ，1 ) 和m i n c o n f ( 0 ，1 ) 。当s u p p ( a j b ) = m i n s u p ，且c o 矿( 4 j b ) _ m i n c o n f 时，称关联规 则a j b 为数据集d 上的强关联规则，简称强关联规则。其中，m i n s u p 称为 最小支持度，m i n c o n f 称为最小置信度。 满足最小支持度阈值和最小信任度阂值的关联规则就称为强关联规则。通 常为方便起见。都将最小支持度阂值简写为m i n _ s u p ，最小信任度阈值简写为 皿i n c o n f 。这两个阈值均在0 到i 之间。 定义2 4 项集、k 一项集、频繁k 一项集 一个数据项的集合称为项集，一个包含k 个数据项的项集称为k 一项集。如 集合 啤酒，尿布 就是一个2 一项集。 满足最小支持度的项集就称为频繁k 一项集。所有频繁项集的集合就记为 l k 。 2 2 2 挖掘步骤 挖掘关联规则主要包含以下两个步骤： 步骤一：发现所有的频繁项集，根据定义，这些项集的频度至少应等于最 小支持频度。 步骤二：根据所获得的频繁项集，产生相应的强关联规则。根据定义这些 规则必须满足最小信任度。 此外，还可利用兴趣度来帮助挖掘有价值的关联规则知识。 第一步工作最为关键，需要大量的i o 操作。第二步中可以在第一步的基 础上直接得到。因此目前对关联规则算法的研究上主要集中在如何高效的生成 频繁项集上。 2 2 3 关联规则的分类 随着关联规则的研究和发展，出现了很多全新的关联规则形式。关联规则 的研究根据所处理的数据集的性质和挖掘结果的不同而有不同的分类： ( 1 ) 根据关联规则所处理的具体值来进行分类划分 若一个规则仅描述数据项是否在出现这种情况间的联系，那么这种关联规 则就是一个布尔关联规则。例如，“牛奶= ) 面包”所描述的就是市场购物分 析所获得一条布尔关联规则。 若一个规则仅描述是定量数据项( 或属性) 之间的关系，那么它就是一个定 量关联规则。在这些规则中，数据项( 或属性) 的定量数值可以划分为区间范围。 规则a g e ( x ，”3 0 3 4 ”) ai n c o m e ( x ，”4 2 k - 4 8 k ”) = b u y s ( x ，”c o m p u t e r ”) ( a ) 就 是一个定量关联规则，这里的定量属性a g e 和i n c o m e 均己被离散化了。 ( 2 ) 根据规则中数据的维数来进行分类划分 若一个关联规则中的项( 或属性) 仅涉及一个维，那么它就是一个单维关 联规则。如规则b u y s ( x ，”牛奶”) = b u y s ( x ，”面包”) 只涉及一个维( 属性b u y s ) ， 因此它是一个单维关联规则。 若一个规则涉及二个或更多维，诸如：属性a g e ，i n c o m e 和b u y s ，那么它 就是一个多维关联规则。如规l i j ( a ) 因为它涉及三个维，所以也可以认为它也是 一个多维关联规则。 ( 3 ) 根据规则描述内容所涉及的抽象层次来进行分类划分 一些关联规则挖掘方法可以发现不同抽象层次的关联规则，例如，挖掘出 规则( b ) 和规则( c ) 。 a g e ( x ，”3 0 - - 3 4 ”) ； b u y s ( x ，”笔记本电脑”) ( b ) a g e ( x ，”3 0 3 4 ”) = b u y s ( x ，”电脑”) ( c ) 在规则( b ) 和规则( c ) 中( 属性b u y s ) 的数据项描述涉及不同抽象层次内容( “电 脑”是”笔记本电脑”的更高层次) ，由于规则( b ) 和规则( c ) 内容涉及多个不同抽象 层次概念，因此就构成了多层次关联规则；相反若一个关联规则的内容仅涉及 单一层次的概念，那么，这样的关联规则就称为单层次关联规则。 ( 4 ) 根据关联规则所涉及的关联特性来进行分类划分 关联挖掘可扩展到其他数据挖掘应用领域，如进行分类学习，或进行相关 分析( 即可以通过相关数据项出现或不出现来进行相关属性识别与分析) 。 2 3 经典关联规则算法 自从关联规则数据挖掘幢首先由a g r a w a l 等人提出以后，人们对关联规则 数据挖掘技术的研究就从来没有停止过，理论上在对它进行了很多卓有成效的 分析和研究的同时，实践上还提出了不少行之有效的算法，为关联规则挖掘从 理论到应用奠定了基础。下面，本文将对几种经典的关联规则数据挖掘算法进 行综述。 2 3 1a p r i o r i 算法及其改进 关联规则数据挖掘算法的关键是快速、高效地发现频繁项集。发现频繁项 集的经典算法是1 9 9 4 年由r a k e s ha g r a w a l 等人提出的h p r i o r i 算法。 2 3 1 1 a p r i o r i 算法 a p r i o r i 算法要对数据库进行多次遍历，第一次遍历得到卜频繁项集合 l ，第k 次遍历前，先利用l 。产生k 一候选项集合c 。，然后在遍历过程中确定 c 。中每一个元素的支持度，通过计算找出k 一频繁项集合h ，算法在候选项集合 为空时停止。 为提高产生相应频繁项集的处理效率，a p r i o r i 算法利用了一个重要的性 质来有效缩小频繁项集的搜索空间。下面介绍这一性质。 ( 1 ) a p r i o r i 性质 频繁项集的所有非空子集必定是频繁的，或者说非频繁项集的所有超集必 定是非频繁的。即若存在项集i 不是频繁的，满足p o ) r a i n s u p ，则把项i 添加到项集i 的结果项集i u i 必定也不是频繁的，即p ( i u i ) m i n _ s u p 。这说 明a 璎i o r i 性质满足反单调性。 ( 2 ) 连接和剪枝 产生频繁项集的过程主要分为连接和剪枝两步： 连接操作 为发现l k ，可以用l k i 中两个项集相连接以获得一个l k 的候选集合c k 。 设l l 和1 2 是l k - l 中的两个项集，记号l i d 】表示l i 的第j 项。如果1 1 和1 2 的前 k 2 个对应项相等，则1 1 和1 2 可连接。当满足条件( 1 l 【l 】= 1 2 1 ) a ( 1 l 【2 】= h 2 d a a ( 1 t 【k 2 】= 1 2 k - 2 】) a ( 1 i k 一1 】 r a i n _ s u p ) r e t u r n l 2u t 厶 p r o c e d u r ea p r i o r i g e n ( l k 1 ，m i n _ s u p ) f o re a c hl l l k - 1 f o re a c h l 2 l k 1 i f ( ( 1 l 【1 】= 1 2 【l 】) a a ( 1 l k 一2 】= 1 2 k 一2 】) a ( 1 l k - 1 1 2 k l 】) ) c z1 1 01 2 ；将两个项集连接到一起 i fh a s _ i n f r e q u e n ti t e m s e t ( c ，l k 1 ) d e l e t ec ；除去不可能产生频繁项集的候选 e l s e = c k u c ) r e t u r nc k p r o c e d u r eh a s i n f r e q u e n t _ i t e m s e t ( c ，l k i ) f o re a c h ( k - 1 ) s u b s e tso f c i fj 盛l k ，ir e t u r n t r u e ； e l s er e t u r nf a l s e 2 3 1 2a p r i o r i 算法的改进 a p r i o r i 算法能够比较有效地产生频繁项集，但它存在两个致命的弱点：一 是需要产生大量候选项集，而真正有价值的不多：二是需要多次扫描事务数据 库，效率低下。 对a p r i o r i 算法的改进主要在于控制候选集的规模，减少对事务数据库的 扫描次数等方面，主要技巧有以下几种： ( 1 ) t o i v o n e n 提出抽样法p 】。从事务数据库中随机抽取一些样本数据集，使 用这些样本发现局部频繁项集，然后用数据库中剩余的部分检验并修正局部频 繁项集，求出全局频繁项集。该方法的优点是提高算法的性能和可扩展性，难 点是如何对数据库进行合理取样而尽可能不丢失信息。 ( 2 ) s a v a s e r e 提出分化的p a r t i t i o n 方法睁l 。p a r t i t i o n 方法将事务数据库分为 n 片，分别求出各片的局部频繁模式，所有局部频繁模式的并集为全局频繁模 式的候选集，第二遍扫描计算可最终求出全局频率项集。该方法具有分布、并 行的思想。最多扫描数据库两次，同样可以减轻c p u 和i 0 负担，提高算法 性能和可扩展性。 ( 3 ) a g r a w a l 提出剪枝方法川。在产生每个c k 时，凡被认为对k 频繁项集 l k 的产生不做贡献的事务被剪掉，以后不再对该事务做任何处理，这样可以使 得随着k 的增大，扫描的数据库越来越小。 ( 4 ) p a r k 提出h a s h 表方法【5 1 。该方法利用h a s h 表将事务数据库投影到 h a s h 表上来减少产生的候选项集的数量。即在第k 遍扫描数据库时，同时统 计c k 和h a s h 表中的ck + l 项目。在求出l k 的同时利用h a s h 表中c k + l 的计 数进一步剪裁c n t 。该方法由于h a s h 表对内存的耗费，对于稠密、大数据库 的性能是一个值得考虑的问题。 ( 5 1 b r i n 提出动态项目集计数法i m 】。该方法在数据库扫描过程中开始支持 度和可信度统计，确定合适的支持度求出频繁项集。该方法可有效地减少数据 库扫描的次数( 一般不超过两次) ，提高算法的效率。 2 3 2f p - g r o w t h 算法及其优缺点 在许多情况下，a p h o r i 算法大幅度压缩了侯选项集的大小，以获取较好的 性能。但即使是进行了优化，a p r i o r i 系列算法仍然无法克服它的一些固有缺陷。 针对a p r i o r i 算法存在的问题，j i a w e ih a n 等人于2 0 0 0 年提出一种额的基于 f p t r e e 的频繁模式增长算法【1 1 1 ，简称为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 ) 算 法，能够在不产生侯选项集的情况下产生所有的频繁项集。 2 3 2 1f p - g r o w t h 算法 f p g r o w t h 算法采取了如下的分而治之策略：首先，将提供频繁项集的数据 库压缩成一棵频繁模式树( f p t r e e ) ，但仍保留项集关联信息。然后，将这种压 缩后的数据库分成一组条件数据库( 一种特殊类型的投影数据库) ，每个关联一 个频繁项，并分别挖掘每个数据库。算法的具体步骤如下： ( 1 ) 生成频繁模式树 频繁模式树的生成步骤如下： 扫描事务数据库d 一次，产生频繁1 项集，并得到它们的支持度计数。 频繁项按支持度计数的递减顺序排序，用l 表示。 创建f p t r e e 的根节点，以”n u l l ”标记它。对于d 中的每个事务，执行 以下操作：选择事务中的频繁项，并按l 中的次序排序。设排序后的频繁项表 为【p i p ，其中p 是第一个元素，而p 是剩余元素的表。调用i n s e r t _ t r e e ( p i p ，t ) ， 该过程的执行情况如下：如果t 有子女n 使得n i t e m n a m e = p i t e m - n a m e ，则n 的计数增加l ；否则创建一个新节点n 将其计数设置为l ，链接到它的父节点t ， 并且通过节点链结构将其链接到具有相同i t e m n a m e 的节点。如果p 非空，递 归地调用i n s e r tt r e e ( p , n ) 。 以表2 1 的f p 示例数据库为倒，通过频繁模式树生成算法得到频繁模式树 如图2 1 所示( 设最小支持度计数为2 ) 。 表2 1f p 示例数据库 t i d 项集排序的项集 o o l 1 1 ，1 2 ，1 51 2 ，1 1 ，1 5 0 0 2王2 。“1 2 。1 4 0 0 31 2 1 3 1 2 1 3 0 0 4 i l ，1 2 ，1 41 2 ，i i ，1 4 0 0 51 1 1 31 1 b 0 0 61 2 1 31 2 1 3 0 0 71 1 1 31 1 1 3 0 0 8 i l ，1 2 ，1 3 ，1 51 2 ，1 1 。1 3 ，1 5 0 0 9 i l ，1 2 ，1 3 1 2 。i l ，1 3 图2 1 存放压缩的频繁模式信息的f p 树 ( 2 ) 挖掘频繁项集 对f p t r e e 进行挖掘以生成全部频繁项集，挖掘过程由长度为l 的频繁模式 ( 初始后缀模式) 开始，通过构造它的条件模式基( 一个“子数据库”，由f p - t r e e 中与后缀模式一起出现的前缀路径集组成) 和条件f p - t r e e ，递归地在f p t r e e 上 进行挖掘。模式增长通过后缀模式与由条件f p t r e e 产生的频繁模式连接实现。 f p g r o w t h 方法将发现长频繁模式的问题转换成递归地发现一些短模式， 然后连接后缀。它使用最不频繁的项作后缀，提供了很好的选择性，该方法大 大降低了搜索开销。 算法搐述如下： p r o c e d u r ef p - g r o w t h ( f p - t r e e ，a ) i f t r e e 含单个路径pt h e n f o r 路径p 中节点的每个组合( 记做卢) 产生模式夕u 口，其支持度s u p p o r t = ( 3 中节点的最小支持度； e l s ef o re a c ha i 在t r e e 的头部 产生一个模式= 曲u 口，其支持度s u p p o r t = a i s u p p o r t 构造卢的条件模式基，然后构造的条件f p t r e et r e e p ； i ft