（计算机软件与理论专业论文）多最小支持度关联规则挖掘研究.pdf

摘要 摘要 与传统的统计、查询方法相比，数据挖掘是人工智能、模式识别、数据库、 机器学习以及管理信息系统等形成的交叉学科数据挖掘是一个新兴的边缘学 科，其应用领域非常广泛，并且具有良好的应用前景。 本文概述了关联规则挖掘，尤其对多最小支持度关联规则挖掘进行了深入研 究分析，主要包括以下内容： 关联规则研究分析。概述了关联规则挖掘的基本概念，分类讨论了关联规则 挖掘算法，并分析了其中几种典型算法；对多最小支持度关联规则挖掘的基本理 论、挖掘算法和研究现状进行了研究分析 针对多最小支持度关联规则挖掘，本文提出了一种多项目支持树o m s t r c 均 结构模型，它能够储存关于频繁模式的关键信息。同时提出了一种基于m i s o b 的多最小支持度关联规则挖掘算法，即c f p - g r o w t h 算法，用以挖掘所有的频繁 项集。 针对多最小支持度设置难的问题，本文提出了一种保持m i s - 嗡结构的稳 定算法，该算法不需要再次扫描数据库，只需要不断的运行挖掘算法来调整支持 度，以便对所有项目设置一个适当的支持度阈值。 基于合成数据对c f p o g r o w t h 算法的性能与a p r i o r i 算法、m s a p r o r i 算法、 f p g r o w t h 算法进行了比较实验，并对实验结果进行了分析。结果表明c f p - g r o w t h 算法挖掘效率高于原m s a p r i o r i 算法并对保持m i s - 慨结构的稳定算法进行实 验测试，结果表明比重新构建m i s 仃要节省大量的时间 关键词：数据挖掘；关联规则；多最小支持度；m i s o t r e 豫c f p o g r o w t h 算法 西北大学硕士研究生论文 a b s t r 芷t a b s t r a c t c o m p a r i n gw i t ht h et r a d i t i o n a ls t a t i s t i ca n dq u e r ym e t h o d s ，d a t am i n i n gi s a c s s - s u b j e c tw h i e l ai sf o r m e db ya r t i f i c i a li n t e l l i g e n c e ，p a t t e r nr e c o g n i t i o n , d a t a b a s e ， m a c h i n el e a r n i n ga n dm a n a g e m e n ti n f o r m a t i o ns y s t e m , e t e d a t am i n i n gi sa n e w l y - e s t a b l i s h e df r o n t i e rs u b j e c t i th a sb e e nu s e de x t e n s i v e l y , a n di t sa p p l i c a t i o n f u t u r ei sa l s ob r i g h l a s s o c i a t i o nr u l e sm i n i n gi ss u m m a r i z e di nt h i sp a p e r m u l t i p l em i n i m u m s u p p o r t sa s s o c i a t i o nr u l e ；m i n i n gi se s p e c i a l l yr e s e a r e l a e da n da n a l y z e d t h em a i n c o n t e n t sa l el i s t e da sf 0 1 i c l w s ； r e s e a r c ha n da n a l y s i so fa s s o c i a t i o nr u l e si sp r e s e n t e d f i r s t l y , t h eb a s i c c o n c e p t so fa s s o c i a t i o nr u l e sm i n i n gi ss u m m a r i z e d t h e na s s o c i a t i o nr u l e sm i n i n g a l g o r i t h m sa r cd i s e u s 溉lr 懿p c e f i v e l y ；, c ：e l t a j nt y p i c a la l g o r i t h r ma m o n g t h e m 黜a l s o a n a l y z e d s e c o n d l y , t h eb a s i ct h e o r i e s ，m i n i n ga l g o r i t h m sa n da e t u a n yr e s e a r c ho f m u l t i p l em j n i m u l ns u p p o r t sa s s o c i a t i o nr u l e sm i n i n ga 托r e s e a r e l a e da n da n a l y z e d f o rm u l t i p l em i l l i l l i l l ms u p p o r t sa s s o c i a t i o nr u l e sm i n i n gi nt h ed i s s e r t a t i o n 毽 p r o p o s e1 3 n e w 仃c cs t r u c t u r em u l t i p l ei t e ms u p p o r tt r e e ( m i s - t r e 昭) ，t os t o r et h e c r u c i a l i n f o r m a t i o na b o u tf r e q u e n tp a t t e r n s m e a n w h i l e , me f f i c i e n tm i s - i r e e - b a s e d a l g o r i t h mf o rm i n i n gm u l t i p l em i n i m u ms u p p o r t s a s s o e i a t i o ar u l e s , c a l l e d 髓幢 c f p g r o w t ha l g o r i t h m ，i sd e v e l o p e df o rm i n i n ga l lf i e q u e n ti t e m s e t s f o rt h ed i t f i e u l tq t t e s t i o t tt os e tm u l t i p l em i n i m u ms u p p o r t si nt h ed i s s e r t a t i o n , w ep r o p o s em e f f i c i e n ta l g o r i t h mw l a i e l a 咖m a i n t a i nt h em i s - l l - e eb l l u c t l l l e i tn e e d n o tt ol r c s c a nd a t a b a s ea n do n l yn e e dt or 1 mt h em i n i n ga l g o r i t h mr e p e a t e d l yt oa d j u s t i t e m ss u p p o r t su n t i la na p p r o p r i a t et h r e s h o l d sf o ra l li t e m sa tat i m e b a s e do nt h es y n t h e t i cd a t a , t h ep e r f o r m a n c eo fc f p g r o w t ha l g o r i t h mi s e x p e r i m e n t e d , w h i e l ai sc o r o l l a t e dw i t ha p r i o r ia l g o r i t h m , m s a p r i o r ia l g o r i t h ma n d f p - g r o w t ha l g o r i t h m t h er e s u l t so ft h ee x p e r i m e n t sa r ea n a y z e d w h i c hs h o w st h a t c f p g r o w t ha l g o r i t h mi s m o r ce f f i c i e n tt h a nt h et y p i c a lm s a p r i o r ia l g o r i t h m 西北大学硕士研究生论文 i i a b s t r a c t f u r t h e r m o r et h em a i n t a i n i n ga l g o r i t h r ao f t h em i s - t r e e 灿c n l i se x p e r i m e n t e d t h e r e s u l ts h o w st h a tm i s - t r e em a i n t e n a n c em e t h o dj sa b l et os a v em o r et i m et h a n r e c o n s t n g - f i n gt h em i s - t r e 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 s ；m u l t i p l e1 v i n i r f l r ms u p p o r t ；m i s - t r e e ； c f p - g r o w t ha l g o r i t h m 西北大学硕士研究生论文 1 1 i 第一章绪论 1 1 引言 第一章绪论 通信、计算机和网络技术正改变着整个人类和社会，最明显的是在这些技术 的帮助下人们产生和收集数据的能力迅速提高了。然而，网络化时代同时也出现 了一大堆新的问题，诸如信息过量、难以消化；信息真假难以辨识；信息安全难 以保证；信息形式不一致，难以统一处理等等如何理解已有的历史数据并用以 预测未来的行为，如何从这些海量数据中发现信息，变被动的数据为主动的知识， 如何快速、准确地获得有价值的信息，指导政府和企业决策，获取更大的经济效 益和更好的社会效益，都迫使人们去寻找新的、更为有效的数据分析手段对各种 “数据矿藏进行有效的挖掘以发挥其应用潜能 数据挖掘和知识发现( d a t am i n i n ga n dk n o w l e d g ed i s c o v e r yi nd a t a b a s e s ) 正 是在这样的需求背景下应运而生了它的出现为自动和智能地把海量数据转化为 有用的信息和知识提供了手段数据挖掘和知识发现作为一门新兴的边缘学科， 汇集了来自机器学习、模式识别、数据库、统计学、人工智能以及管理信息系统 等各学科的研究成果。多学科的相互交融和相互促进，使得这一学科得以蓬勃发 展，而且己初具规榭1 , 2 1 数据挖掘方法的提出，让人们有能力最终认识数据的真正价值，即蕴藏在数 据中的信息和知识数据挖掘和知识发现是近年来一个十分活跃的研究领域到 目前为止，由美国人工智能协会主办的k d d 国际研讨会已召开了多次，规模由 原来的专题讨论会发展到国际学术大会以k d d 国际会议为例，平均会议代表 年增长率为4 0 另外，仅以1 9 9 9 年为例，就有近2 0 个国际会议列有k d d m 的专题如c f 9 9 c i m c a 9 9 ，d a w a k 9 9 ，d i s c o v e r ys c i e n c e l 9 9 9 , e u r o - p a r 9 9 ， i d a - 9 9 ，i s s m i s 9 9 j s m ，k d d 9 9 ，p k d d 9 9 ，r s f d g r c ，d s 9 9 ，d b 9 9 , i j c a i - 9 9 ，s i g m o d 9 9 ，p a d d 9 9 ，c l m c a 9 9 ，p a k d d 9 9 等【3 】近几年，从事数据挖 掘研发的人员遍布世界8 0 多个国家，数据挖掘的研究重点也己从算法研究向具 体应用过渡，从实验室原型走向商品化阶段。国内这两年也有相当多的数据挖掘 和知识发现从实验室原型走向商品化阶段，同时也有相当多的数据挖掘和知识发 西北大学硕士研究生论文 第一章绪论 现方面的研究成果，许多学术会议上都设有专题进行学术交流。但数据挖掘技术 的研究还很不成熟，其应用还有较大的局限性，正是这些局限性，促使数据挖摇 研究进一步发展 1 2 关联规则研究现状 关联规则挖掘是数据挖掘领域中一个非常重要的研究课题，它的核心是基于 频繁项集理论的推理方法，并在附加邮递、目录设计、追加销售、仓储规划以及 机遇购买模式对客户进行划分等方面得到广泛应用，然而在这些应用中的数据库 都是极其庞大的，如何有效的提取关联规则是其技术难点之一 在关联规则挖掘过程中。为了挖掘有意义的关联规则。一般由用户给定两个 阈值：最小支持度和最小置信度，最小支持度定义了规则在统计意义上所需覆盖 事件样本数量的下限；最小置信度则表征了规则用于推理的强度关联规则的算 法一般也分为两步：首先产生满足最小支持度的频繁项集：然后在频繁项集的基 础上产生满足最小置信度的所有规则。由此可见，最小支持度和最小置信度对挖 掘关联规则的过程有着重要的影响，而最小置信度又是通过最小支持度得到，所 以最小支持度就成了影响关联规则挖掘的一个关键因素 目前，在许多关联规则挖掘算法中，其常用的经典算法是a l o f i o r i 算法，但 它在找出频繁项集的过程中需要多次扫描数据库，为了能够提高a p f i o r i 的有效 性，现在国内外已经提出了许多a 两o r i 算法的变形【镐6 7 鼬】旨在提高原算法的效 率。它们都是以a p r i o f i 算法为基础，产生关联规则时需要生成大量的候选项集， 为了避免产生候选项集，j w h a u 等人提出另一经典算法是基于f p - b - e e 树生成频 繁项集的f p - 孕o w t h 算法，虽然f p - g r o w t h 算法克服了先前关联规贝h 挖掘算法的 不足，节省了大量的空间和时间开销，但由于它没有考虑挖掘关联规则的高效增 量更新问题，严重限制了该算法的实际应用，目前研究者已经提出了一些基于 f p t r e e 的增量更新的算法 t o , t m 2 。但这些方法均没有考虑支持度和数据库同时发 生变化时如何增量更新关联规则。还有将模糊的思想融入数据挖掘、形成的模糊 关联规则的挖掘，在模糊关联规则的挖掘中提出了有效支持度的概念( 是当前关 联规则研究的新方向) 等等 1 3 1 4 1 然而以上算法大多都只为了减少数据库的访问 西北大学硕士研究生论文2 第一章绪论 次数，和减少数据的存储空间来提高算法的运行效率，并不能提高算法挖掘结果 的有效性，因为它们都是在整个挖掘过程中仅由用户预先设定一个最小支持度， 即为单支持度模型。而多数情况下，项目的分布频率并不相同或相近，并且项目 的分布频率变化较大，所有数据只采用单个最小支持度是不够的，它没有抓住数 据在数据库中的分布频率不同这一特征。如在超市中，一些耐用、价格高的商品 被购买的次数比较少，而发现包含这些稀有项目的规则很重要 国内外某些学者提出了一个多支持度的模型解决了单支持度模型中可能出 现的稀有项问题，基于多支持度的模型提出了很多新的数据采集算法它们是为 数据库中每个项目预先设定一个项目最小支持度，规则r 中的最小支持度定义 为规则中所有项目最小支持度的最小值，这样就解决了单个最小支持度的不足， 但是数据库中每个项目的最小支持度也都必须由用户预先来设定，而且到底设定 多大的最小支持度最为合适没有一个标准。没有相关的专业知识，用户很难设置 合适的最小支持度阈值来得到他们想要的理想结果。如果最小支持度阈值设置太 大，会导致结果太少甚至没有结果如果阈值太小，对用户来说结果又会很多， 这也意味着在计算方面会花费很多的时间，并且要花更多的精力去筛选答案 所以，在多最小支持度关联挖掘算法的基础上，本文提出了一种多项目支持 树呷s 缸) 结构模型和一种基于m i s 击的多最小支持度关联规则挖掘算法， 即o f p - g r o w t h 算法，用以挖掘所有的频繁项集。 1 3 本文的主要工作 本课题的研究得到陕西省自然科学基金和陕西省教育厅重点科研计划项目 基金的支持数据挖掘是一个非常广泛的研究领域，包含方方面面的不同内容 本文主要进行了多最小支持度关联规则挖掘算法的研究，主要做了如下工作： ( 1 ) 在国内外大量相关文献资料的基础上，对关联规则数据挖掘的基本概念、 研究现状等问题进行了分析、归纳总结对关联规则挖掘的常用算法进行了分类 探讨，并分析了其中几种典型算法，比较了它们各自的优缺点及适用范围。 t ；( 2 ) 对多最小支持度关联规则挖掘的基本概念、挖掘算法及研究现状进行了 归纳、分析和研究并对多最小支持度关联规则挖掘算法进行了改进，提出了一 西北大学硕士研究生论文 第一章绪论 种多项目支持树( m i s - t r e e ) 结构模型，并提出了一种基于m i s - t r e e 的多最小支持 度关联规则挖掘算法，即c f p - g r o w t h 算法，用以挖掘所有的频繁项集。 ( 3 ) 针对用户很难同时对所有项目设置一个适当的支持度阈值，并且为了节 省耗时，动态调整项目的最小支持度，提出了一种不需要再次扫描数据库保持 m i s t r e e 结构的稳定算法 ( 4 ) 基于合成数据对c f p - g r o w t h 算法的性能与a p r i o r i 算法、m s a p r o r i 算法、 f p g r o w t h 算法进行了比较实验，并对实验结果进行了分析。同时对保持m i s - t r e e 结构的稳定算法进行实验测试、分析。 西北大学硕士研究生论文 第二章关联规则挖掘 第二章关联规则挖掘 关联规则挖掘是数据挖掘研究的一个重要分支，关联规则是数据挖掘的众多 知识类型中最为典型的一种关联规则挖掘可以发现存在于数据库中的项目 o t e m s ) 或属性( a t t r i b u t e s ) 问的有趣关系，这些关系是预先未知的和被隐藏的，也 就是说不能通过数据库的逻辑操作( 如：表的联接) 或统计的方法得出。这说明它 们不是基于数据自身的固有属性( 例如函数依赖关系) ，而是基于数据项目的同时 出现特征，所发现的关联规则可以辅助人们进行市场运作，决策支持及商业管理， 网站设计等。关联规则是由r a g r a w a l 等人首先提出的1 1 副6 】，它的一个典型例子就 是：9 0 的客户在购买面包的同时也会购买牛奶”，其直观意义为顾客在购买某些 商品的时候有多大的倾向会购买另外一些商品 2 1 基本概念 设，= 辑。毛，) 是由m 个不同的项目组成的集合。记d 为事务( t r a n s a c t i o n ) t 的集合，这里事务t 是项的集合，并且r i 对应每一个事务有唯一的标识， 如事务号，记作t i d 。设x 是一个i 中项的集合，如果x g t ，那么称事务t 包 含x 。 一个关联规则是形如z j 】，的蕴涵式，这里x c ，y c i ，并且x n y = o 。 规则x 号y 在事务数据库d 中的支持度( 踟p p o n ) 是事务集中包含x 和y 的事务 数与所有事务数之比，记为s u p p o n ( xj 】，) 即 s u p p o r t ( x y = v ：x u k r , r e d ) i d i 规则j 辛y 在事务集中的置信度( c o 西d 凹嘲是指包含x 和y 的事务数与包 含x 的事务数之比，记为c o n f i d e n c e ( jjy ) ，即 c o ：n 丘d c z jj ，户l 留：x u y e l 丁d ) i i 口：x r ，r 三) ) i 给定一个事务集d ，关联规则挖掘问题就是产生支持度和置信度分别大于用 户给定的最小支持度( m i n s u p ) 和最小置信度( m i n c o n o 的关联规则。这种既满足最 小支持度又满足最小置信度的关联规则，称之为强关联规则。 从关联规则的概念可知，关联规则挖掘的过程分成两个步骤。第一步，发现 西北大学硕士研究生论文 5 第二章关联规则挖掘 所有的频繁项目集，即支持度大于给定最小支持度阈值的项集；第二步，根据所 获得的频繁项集产生关联规则，根据定义，这些规则必须满足最小置信度阈值 这里的第二步相对比较简单，一旦从数据库中产生了频繁集，则可以从中直 接产生强关联规则。 ( d 对于每一个频繁项集l ，产生所有的l 的非空子集； 0 i ) 对于1 的每一个非空子集s ， 若s u p p o r t _ c o u n t ( 1 ) s u p p o r t _ c o u n t ( s ) m i n c o n f ，则输出关联规则 “s j ( t - s ) ” 关联规则挖掘的基本模型如图2 1 所示： 图2 1 关联规则挖掘步骤 图中d 为数据集，算法1 为频繁项目集的搜索算法，算法2 为关联规则的 产生算法，r 为挖出的关联规则集合。用户通过指定m i n s u p p o r t 和m i n c o n f i d e n c e 分别与算法l 和算法2 交互，并通过与r 的交互对挖掘结果进行解释和评估 2 2 关联规则分类 通常关联规则挖掘可视不同的情况分类如下 ( 1 ) 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型布 尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系； 而数值型关联规则可以和多维或多层关联规则结合起来，对数值型字段进行处 理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规 则中也可以包含种类变量例如： 性别一女”j 职业一镪书”，是布尔型关联规则： 性别一女”j a v g ( 收) k ) = 2 3 0 0 ，涉及的收入是数值类型，所以是一个数值型 西北大学硕士研究生论文6 第二章关联规则挖掘 关联规则。 ( 2 ) 基于规则中数据的抽象层次，可分为单层关联规则和多层关联规则在 单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次 的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 台式机s o n y 打印机，是一个细节数据上的单层关联规则； 台式机= ，s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可分为单维的和多维的。在 单维的关联规则中，只涉及到数据的一个维，如用户购买的物品；而在多维的关 联规则中，要处理的数据将会涉及多个维。所以，单维关联规则是处理单个属性 中的一些关系；多维关联规则是处理各个属性之间的某些关系 例如：啤酒j 尿布，这条规则只涉及到用户购买的物品，是单维关联规则； 性别= “女”职业= 。秘书”，这条规则就涉及到两个字段的信息，所以 是一条多维关联规则。 ( 4 ) 基于规则中涉及到的数据的确定性，关联规则可以分为确定的和模糊的 由于客观世界的多样性和复杂性，许多事物难以用精确和确定的概念表示，所以 就出现了模糊关联规则l 埘模糊关联规则中的数据项用模糊概念的语义项表示， 表达自然，更能反映商业语义 例如：职业= “秘书”j 性别= “女”，这条规则只涉及到确定的数据项，是 一条确定性关联规则注：此处的确定性并非指规则的置信度。 职业= “模特”习个子= “高”，由于这条规则涉及到“高”这个模糊语义 项，因此是模糊关联规则 根据关联规则的分类，进一步分析某个具体的挖掘方法适用于哪一类规则的 挖掘，某类规则又可以用哪些不同的挖掘方法进行处理。 2 3 关联规则挖掘算法 2 3 1 算法分类 自从a g r a w a l 等人于1 9 9 3 年首先提出挖掘顾客事务数据库中项集间的关联 规则问题之后，该问题越来越受到重视，诸多的研究人员对关联规则的挖掘问题 西北大学硕士研究生论文 7 第二章关联规则挖掘 进行了大量的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、 并行的思想等，以提高算法挖掘规财的效率；提出各种变体，如泛化的关联规则、 周期关联规则等，对关联规则的应用进行推广通过对比分析，可将已有算法分 类如下。 ( 1 ) 搜索算法 搜索算法是在读入数据集中的每条事务时，对该事务中包含的所有项目集进 行处理，因此搜索算法需要计算数据集d 中所有项目集的支持数。a i s 算法、 s e t m 算法，以及以建格算法为主体的关联规则挖掘算法都是这种搜索算法 t 1 5 】【1 8 ，1 9 捌 搜索算法只需对数据集一次扫描就可以找出所有的频繁项目集，对每一条包 含1 1 个项目的事务就将产生2 。一1 个项目集，数据集d 中包含的项目数很大时， 所需计算和存储的候选项目集的数量往往非常庞大因此，该类算法只适合于项 目集数量相对较小的数据集中的关联规则挖掘。 ( 2 ) 宽度优先算法 包括r a g r a w a l 等人提出的a p r i o r i , a p f i o r i t i d 和a p r i o f i h y b r i d 算法【1 习【2 l 翻， j s p a r k 等人的d h p 算法f 2 3 纠等。 a p n 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 算法的基础上对数据集进行 修剪，以减少扫描数据库的时间，但对数据集的修剪需要额外的计算和操作 d h p 算法采用哈希技术对数据集和候选项目集进行修剪，特别是对候选2 - 项目 集的修剪特别有效a p r i o r i h y b r i d 算法是a p r i o r i 算法和a p r i o r i t i d 算法的融合， 该算法开始采用a p r i o r i 算法，然后在每次扫描完数据集之后计算修剪后的数据 集的大小；若修剪后的数据集可在内存中进行处理，则切换至a p r i o r i t i d 算法直 到找出所有的频繁项目集 ( 3 ) 深度优先算法 深度优先算法中的高效算法是h a r t 等人提出的f p g r o w t h 算法嘲。f f - g r o w t h 算法无需生成候选项目集，显著地缩小了搜索空间，有效地避免了“知识的组合 爆炸”，挖掘效率明显提高。 ( 4 ) 数据集划分算法 西北大学硕士研究生论文 s 第二章关联规m 咐2 掘 包括a s a v a s e r e 等人的p a r t i t i o n 算法【2 6 1 ，s b r i n 等人的d i c 算法【2 7 1 等。这些 算法将整个数据集划分成可以存放在内存中进行处理的数据块，以节省访问外存 的f o 开销。p a r t i t i o n 算法只需要对整个数据集进行两次扫描，d i c 算法在数据 块划分恰当时可以通过两次扫描数据集找出所有的频繁项目集。数据集划分算法 的候选项目集的数量一般比a p r i o r i 算法的候选项目集的数量大，数据集划分算 法是各种并行关联规则挖掘算法和分布式关联规则挖掘算法的基础 ( 5 ) 抽样算法 包括j s p a r k 等人提出的可调精度的挖掘算法f 2 研，h t o i v o n e n 的s a m p l i n g 算法【2 9 1 等。抽样算法通过对数据集d 抽样产生抽样数据集d 一，找出抽样数据集 d ，中的频繁项目集作为候选项目集，然后扫描数据集d 确定其中的频繁项目集 如何计算负边界以找回部分遗漏的频繁项目集是抽样算法的关键。抽样算法适合 于要求挖掘效率较高，而挖掘准确性不太高的环境下的关联规则挖掘 ( 6 ) 增量式更新算法 包括d w c h e u n g 等人提出的f u p 和f u p 2 算法 3 0 , 3 1 j , r f e l d m a n 的b o r d e r 算法 3 2 1 ，冯玉才等人的i u a 和p i u a 算法嗍等增量式更新算法主要解决两类 关联规则的增量式更新问题：第一，在给定的最小支持度和最小置信度阈值下， 当一个新的事务数据集西添加到旧的事务数据库d b 中时，如何生成肋u 彩中 的关联规则；第二，给定事务数据库d b ，在最小支持度和最小置信度阈值发生 变化时，如何生成数据库d b 中的关联规则 ( 7 ) 并行算法 并行算法分为基于无共享体系和基于共享体系的并行算法。基于无共享体系 的并行算法包括r a g r a w a l 等人提出的c d ( c o u n td i s t r i b u t i o n ) 。c a d ( c a n d i d a t e d i s t r i b u t i o n ) ，d d ( d a t ad i s t r i b u t i o n ) 箅法p 叼j s p a r k 等人的p d m 算法 1 3 5 1 , d w c h e u n g 等人的d m a 和f d m 算法脚1 ，铁治欣等人提出的p m a r 算法t 3 7 1 等基于共享体系的并行算法包括m j z a k i 等人提出的c c p d 算法【3 8 】以及胡侃 等人提出的a p m 算法【3 9 1 等。 西北大学硕士研究生论x 9 第二章关联规则挖掘 2 3 2 典型算法 ( 1 ) a p r i o r i 算法 a p r i o r i 算法是挖掘产生布尔关联规则所需频繁项集的基本算法，也是最著 名的关联规则挖掘算法之一a p r i o r i 算法就是根据有关频繁项集特性的先验知 识c r i o rk n o w l e d g e ) 而命名的。该算法利用了一个层次顺序搜索的循环方法来完 成频繁项集的挖掘工作这一循环方法就是利用l 【项集来产生1 ) 项集具体 做法就是：首先找出频繁1 项集，记为厶，然后利用厶来挖掘厶，即频繁2 项集； 不断如此循环下去直到无法发现更多的频繁l 【- 项集为止每挖掘一层厶就需要 扫描整个数据库一遍。 为提高按层次搜索并产生相应频繁项集的处理效率。帮助有效缩小频繁项集 的搜索空闯，a p r i o r i 算法利用了一个重要性质，即一个频繁项集中任一子集也 应该是频繁项集 a p r i o r i 算法可以产生相对较小的候选项目集，扫描数据库的次数由最大频 繁项目集的项目数决定。因此，该算法适合于最大频繁项目集相对较小的数据集 中的关联规则挖掘问题 ( 2 ) a p r i o r i t i d 算法 。 从上面介绍可以看到a p r i o r i 算法的缺点是：在每一次产生候选项目集时都要 扫描一遍数据库d ，而用于关联规则挖掘的数据库的规模通常是非常大的，所以 这样就无形之中增加了额外的开销，影响了算法的效率a p r i o r i t i d 算法在a p r i o r i 算法的基础上对数据集进行修剪，因而在扫描数据库的效率上要优于a p e o r i ， 而且减少了哟操作时间 a p r i o r i t i d 算法的第一步是简单统计所有含一个元素的项集出现的频率，来 决定频繁的一维项目集，同时产生集合g 在第k 步，分两个阶段，首先用一 函数a p 矗o i i g c a ，通过第o c 1 ) 步中生成的频繁项目集工h ，来生成候选项目集g ， 同时产生集合_ l ，然后搜索乙计算候选项目集巳的支持度。 a p r i o r i t i d 算法的优点是仅在第一次扫描时用事务数据库d 计算候选频繁项 目集的支持度，其它各次扫描用其上一次扫描生成的候选事务数据库d ，来计算 候选频繁项目集的支持度。在最后的几次扫描中，d 的大小要远远小于d ，减少 西北大学硕士研究生论文 1 0 第二章关联规则挖掘 了操作时间，从而提高了算法的效率。 ( 3 ) f p g r o w t h 算法 基于a p r i o r i 的频集方法，即使进行了优化，但是a p r i o r i 方法中一些固有的 缺陷还是无法克服，可能产生大量的候选集。当长度为1 的频集有1 0 0 0 0 个的时 候，长度为2 的候选集个数将会超过l o 的7 次方还有就是如果要生成一个很 长的规则的时候，要产生的中间元素量也是巨大的。 针对a p r i o r i 算法框架的缺陷，h a r tjw 等人提出了f p = t r e e 结构和相应的 f p g r o w t h 算法。f p - g r o w t h 方法采用的是分而治之的策略，即在经过了第一次的 扫描之后，把数据库中的频繁集压缩进一棵频繁模式树( r p - t r e e ) ，同时依然保留其 中的关联信息随后再将f p - t r c e 分化成一些条件库，每个库和一个长度为l 的 频集相关然后再对这些条件库分别进行挖掘。当原始数据量很大时，也可以结 合划分的方法，使得一个f p - t r e e 可以放入主存中实验表明，f p g r o w t h 对不同 长度的规则都有很好的适应性，同时在效率上较之a p r i o r i 算法有巨大的提高。 a p r i o r i 算法与f p - g r o w t h 算法的共同之处于对项目数为1 的频繁集的获得的 方式相同，都是通过对事务数据库进行一次扫描，找到物品支持计数不小于最小 支持计数的物品项，但同时也存在很大的区别： 首先，f p - g r o w t h 算法中需要对项目数为1 的频繁集进行降序排序，而a p r i o r i 算法对此不做处理 其次，f p g r o w t h 算法对于频繁集的搜索过程形成一棵f p = 仕e e ，在f p - t r e e 中包含了物品之间的相关信息，而a p r i o r i 算法则是一个反复循环的过程， 需要对事务数据库进行反复扫描，不断利用上一次的结果产生频繁集。 最后，f p - g r o w t h 算法的关联规则模式的挖掘是通过对f p - i x c e 进行遍历产生 的，而a p r i o r i 算法是通过频繁集最终产生关联规则模式的。 总之，f p - g r o w t h 算法不同于a p r i o r i 算法，不需要产生大量的候选集，而是 一个将较长的频繁模式的发现问题转化为寻找较短的模式而后再连接其前缀的 过程，从而有效的降低了搜索过程中的成本当然，对于f p g r o w t h 算法来说， 对机器内存有一定的要求，所以，在某些应用中，通常情况下要先对数据库进行 分割，然后对每一个分割后的数据库应用f p g r o w t h 算法。 西北大学硕士研究生论文 第二章关联规则挖掘 2 3 3 其它挖掘算法 前面介绍的算法主要针对最简单的单层单维的布尔型关联规则挖掘的，然而 对于许多实际应用来说，由于数据的多样性和复杂性，需要在不同细节层次和不 同维度间进行挖掘，因而出现了多种针对这种对象背景的挖掘算法。 ( 1 ) 多层关联规则 对于很多的应用来说，由于数据分布的分散性，所以很难在数据细节的层次 上发现一些强关联规则。当引入概念层次后，就可以在较高的层次上进行挖掘。 虽然较高层次上得出的规则可能是更普通的信息，但是对于一个用户来说是普通 的信息，对于另一个用户却未必如此所以数据挖掘应该提供这样一种在多个层 次上进行挖掘的功能 根据规则中涉及到的层次，多层关联规则可以分为同层关联规则和层间关联 规则。 多层关联规则的挖掘基本上沿用“支持度一置信度”的框架。不过，在支持 度设置的闯题上有一些要考虑的东西 同层关联规则采用两种支持度策略l 柏】，其一是统一的最小支持度阈值。即对 不同层次频繁项集的挖掘均使用相同的最小支持阈值采用这种策略可以简化搜 索过程，而且基于一个祖先结点是其子结点的超集，可以用优化技术来避免搜索 其祖先结点包含不满足最小支持度阈值的项集。但采用统一的最小支持度阈值也 存在一些问题，由于低层次项不可能比相应高层次项出现的次数更多。所以，如 果最小支持阈值设置过高，就可能忽略掉一些低层次中有意义的关联关系；如果 阈值设置过低，则可能产生过多的高层次无意义的关联关系。其二是递减的最小 支持度阈值即每个层次都有不同的最小支持度，较低层次的最小支持度相对较 小利用递减支持度阈值挖掘多层关联知识，可以选择若干搜索策略，包括：层 与层独立；利用单项进行跨层次过滤；利用1 c 项集进行跨层次过滤。这三种策略 各有各的优缺点，在实际运用时应该根据不同的具体情况选择不同的策略 若要挖掘跨概念层次的关联规则，应该整个使用较低层次的最小支持度阈 值，以使得低层次中的项能够被分析挖掘出来 ( 2 ) 多维关联规则 西北大学硕士研究生论文 第二章关联规则挖掘 以上研究的基本上都是同一个字段的值之间的关系，比如用户购买的物品。 用多维数据库的语言表示就是叫单维或者维内的关联规则，这些规则一般都是在 事务数据库中挖掘的。但是对于多维数据库而言，还有一类多维的关联规则。 例如： 年龄( x ，”2 0 3 0 ”) 职业g “学生_ 购买( x ，“笔记本电脑，) 在这里就涉及到三个维上的数据：年龄、职业、购买 根据是否允许同一个维重复出现，可以又细分为维间的关联规则( 不允许维 重复出现) 和混合维关联规则( 允许维在规则的左右同时出现) 。 年龄，“2 0 3 0 ”) 购买o “笔记本电脑，) = = 购买( x ，“打印机) 这个规则就是混合维关联规则。 在挖掘维问关联规则和混合维关联规则的时候，还要考虑不同的字段种类： 种类型和数值型 对于种类型的字段，原先的算法都可以处理。而对于数值型的字段，需要先 进行一定的处理，一般为连续属性离散化处理基本上有以下几种方法： ( 1 ) 数值字段被分成一些预定义的层次结构这些区间都是由用户预先定义 的得出的规则也叫做静态数量关联规则 ( 2 ) 数值字段根据数据的分布分成了一些布尔字段每个布尔字段都表示一 个数值字段的区间，落在其中则为1 ，反之为0 这种分法是动态的。得出 的规则叫布尔数量关联规则 ( 3 ) 数值字段被分成一些能体现它含义的区间它考虑了数据之间的距离的 因素得出的规则叫基于距离的关联规则 ( 4 ) 直接用数值字段中的原始数据进行分析使用一些统计的方法对数值字 段的值进行分析，并且结合多层关联规则的概念，在多个层次之间进行比较 从而得出一些有用的规则。得出的规贝u n t l 多层数量关联规则 上述方法有个共同的缺点就是边界划分太硬，这样有可能会导致一些有用规 则丢失为了解决这个问题，人们提出通过定义在属性论域上的模糊集来软化边 界1 4 1 , 4 2 , 4 3 1 ，这是因为模糊集可以在集合元素和非集合元素之间提供非常平滑的过 渡。另外，还有些学者提出基于云模型进行区间划分的概念，运用云模型也可以 较有效地解决硬划分带来的问题嗣有些研究扩展了常规关联规则的模型，提 西北大学磺士研究生论文 第二章关联规则挖掘 出了负关联规则挖掘问题 4 6 , 4 7 1 。 关联规则作为当前数据挖掘中最活跃的研究课题之一，已经进行了相当大量 的研究，并取得了可喜的成果。但针对稀有项之间关联模式的挖掘问题，当前的 研究工作相对不多，相关的应用更为罕见。 2 4 本章小结 本章描述了关联规则的基本概念及其分类，讨论并分析了关联规则挖掘算法 的分类、典型算法和其它频繁挖掘算法 西北大学硕士研究生论文 1 4 第三章多最小支持度关联规则挖掘 第三章多最小支持度关联规则挖掘 3 1 关联规则中的多最小支持度 在关联规则挖掘中，为了挖掘有意义的关联规则，一般需要给定某些条件， 只有满足给定条件的模式才被认为是有趣的，并被输出给用户当前一般是给定 两个阈值：最小支持度( m i n s u p ) 和最小置信度( m i n c o n o 。最小支持度定义了规则 在统计意义上所需覆盖事件样本数量的下限；最小置信度则表征了规则用于推理 的强度。用户在挖掘关联规则之前，需要首先设定好最小支持度和最小置信度， 只有那些同时满足这两个条件( 支持度 m i n s u p 且置信度 m i n c o n o 的模式才被 输出给用户，通过评价后作为决策的依据。并且，在实际挖掘过程中，对于不满 足最小支持度的项集，通常并不进行置信度条件的判断。由此可见，最小支持度 和最小置信度对挖掘过程有着重要影响，而又由于置信度通过支持度得到的，所 以最小支持度就成为了影响关联规则挖掘的一个关键因素。 最小支持度的作用是缩减挖掘数据库的搜索空间和约束规则产生的数量。常 规的关联规则挖掘算法对整个数据库的各种属性的数据项均采用唯一的支持度， 这是建立在以下两大客观前提假设之上的： ( 1 ) 数据集中各项具有近似的性质和作用，即重