（电路与系统专业论文）快速频繁项集挖掘算法研究.pdf

r e s e a r c ho nf a s tm i n i n gf r e q u e n ti t e m s e t sa l g o r i t h m b y y a ox i a o l i n g b e ( x i n y a n gn o r m a lu n i v e r s i t y ) 2 0 0 4 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fs c i e n c e l n c i r c u i ta n ds y s t e m i n t h e g r a d u a t es c h o o l o f h u n a nu n i v e r s i t y s u p e r v i s o r a s s o c i a t e p r o f e s s o rm a oj i a n x u d e c e m b e r ， 2 0 10 【一 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：拢菌验 日期：2 01 1 年3 月c 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 作者签名： 导师签名： 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“) 批晓诊 彩遂抄 日期：z o l l 年3 月 日 日期： 2 0 1 1 年弓月7 日 硕士学位论文 摘要 f p g r o w t h 算法是当前挖掘频繁项目集算法中应用最广，并且不需要候选集 的一种挖掘关联规则的算法。但是，f p g r o w t h 算法在挖掘大型数据库时存在占 用内存大和运行速度慢的缺点。为了克服这些不足，本文基于f p g r o w t h 算法提 出了两种新的适合于挖掘大型数据库的关联规则算法：e f p g r o w t h 算法和 l f p g r w o t h 算法。 e f p g r o w t h 算法利用项集等价类将关联规则挖掘的项集分成互不相交的子 空间的性质，将一个大型数据库分解成多个投影数据库，依次在每一个投影数据 库上进行约束频繁项集挖掘。算法尤其适合支持度较小时的大型数据库的挖掘。 分析和实验表明e f p g r o w t h 算法在挖掘大型数据库时时间和空间的性能上均优 于f p g r o w t h 算法。而且，随着数据库规模的增大，e f p g r o w t h 算法具有更明显 的优势。 l f p g r w o t h 算法将原来的搜索空间( 格) 划分成若干个更小的子空间( 子格) ， 通过子格间的迭代分解，将对网格p ( i ) 的频繁项集挖掘转化为对多个子网格的并 集进行约束频繁项集的挖掘。实验结果和理论分析表明，l f p g r o w t h 算法在挖掘 大型数据库时时间和空间的性能上均优于f p g r o w t h 算法。而且，随着数据库规 模的增大或支持度阈值的减少，l f p g r o w t h 算法具有更明显的优势。 本文还介绍了e f p g r o w t h 算法和l f p g r w o t h 算法挖掘频繁项集的一个应用 实例。 关键词：数据挖掘；f p 树；频繁项集；等价类；格 i i 快速完全频繁项集挖掘算法研究 a b s t r a c t f p g r o w t ha l g o r i t h mi so n eo ft h ec u r r e n t l ym o s tp o p u l a ra l g o r i t h m sf o rm i n i n g a s s o c i a t i o nr u l e sw i t h o u tc a n d i d a t eg e n e r a t i o n h o w e v e r , i th a sd i s a d v a n t a g e ss u c ha s l o w e rs p a c eu t i l i z a t i o nr a t ea n ds l o w e re x e c u t i o nt i m ew h e nm i n i n gt h el a r g ed a t a s e t s t oo v e r c o m et h e s ed r a w b a c k s ，b a s e do nt h ef p g r o w t ha l g o r i t h m ，t h i sp a p e rp r o p o s e d t w on e wa 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 sf r o ml a r g ed a t a s e t s - - e f p g r o w t h a l g o r i t h ma n dl f p - g r o w t ha l g o r i t h m a c c o r d i n gt oc h a r a c t e r i s t i co fl a r g ed a t a b a s e s ，i n s p i r e db yt h e f a c t t h a tt h e f p - g r o w t hp r o v i d e sa ne f f e c t i v ea l g o r i t h m ，an e we f p g r o w t hf o rm i n i n gf r e q u e n t p a t t e r n si nl a r g ed a t a b a s e si sp r o p o s e d b a s e do nt h ec h a r a c t e r i s t i co fe q u i v a l e n t c l a s s e s ，w h i c hs e p a r a t ei t e ms e t so fa s s o c i a t i o nr u l e si n t om a n ys u b s e t s ，p r o p o s e d a l g o r i t h md i v i d e sal a r g ed a t a b a s ei n t om a n yp r o je c t i o ns u b s e t sa n dc a r r i e so u t c o n s t r a i n e df r e q u e n t e x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mh a sa c c e l e r a t e dt h em i n i n g s p e e da n dt h ep e r f o r m a n c eo fs p a c es c a l a b i l i t yi ss u p e r i o rt ot h ef p g r o w t ha l g o r i t h m m o r e o v e r , t h ea l g o r i t h mh a sav e r yg o o dt i m ea n ds p a c es c a l a b i l i t yw i t ht h ei n c r e a s i n g s i z eo fd a t a b a s e t h en e wl f p g r o w t ha l g o r i t h md i v i d e sal a r g el a t t i c ei n t om a n ys u b - l a t t i c e s ，a n d c a r r i e so u tc o n s t r a i n e d f r e q u e n t t h r o u g hi t e r a t i v i n gd e c o m p o s i t i o no fs u b l a t t i c e s ， f r e q u e n ti t e m s e tm i n i n gi nl a t t i c ei st r a n s f o r m e di n t of r e q u e n ti t e m s e tm i n i n gi nu n i o n s e to fm u l t i p l es u b l a t t i c e s e x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mh a sa c c e l e r a t e dt h e m i n i n gs p e e da n dt h ep e r f o r m a n c eo fs p a c es c a l a b i l i t yi ss u p e r i o rt ot h ef p - g r o w t h a l g o r i t h m m o r e o v e r , t h ea l g o r i t h mh a sav e r yg o o dt i m ea n ds p a c es c a l a b i l i t yw i t ht h e i n c r e a s i n gs i z eo f d a t a b a s e k e yw o r d s ：d a t am i n i n g ；f p - t r e e ；f r e q u e n tp a t t e r n ；e q u i v a l e n tc l a s s e s ；l a t t i c e i i i 硕士学位论文 口 罩 i = 1 封 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t i i i 插图索引v i 附表索引v i i 第1 章绪论1 1 1 研究背景1 1 2 频繁项集挖掘的分类5 1 3 本文的主要工作5 1 4 论文结构5 第2 章频繁项集挖掘算法相关研究6 2 1 引言6 2 2 完全频繁项集挖掘6 2 2 1 经典算法6 2 2 2 其他算法1 3 2 - 3 数据流频繁项集挖掘1 6 2 4 最大频繁项集挖掘：1 7 2 5 频繁闭项集挖掘1 9 2 6 j 、结一2 0 第3 章基于等价类的快速频繁项集挖掘算法一2 1 3 1 引言2 1 3 2 基本概念和问题的描述2 1 3 3e f p g r o w t h 算法2 3 3 3 1 算法基本思想2 3 3 3 2 算法步骤2 4 3 3 3 约束频繁项集挖掘算法2 5 3 4 实验结果2 8 3 5 小结3 0 第4 章基于格的快速频繁项集挖掘算法3 2 4 1 引言3 2 i v j 快速完伞频繁项集挖掘算法研究 4 2 基本概念和问题的描述3 2 4 3l f p g r o w t h 算法3 3 4 3 1 基本思想3 3 4 3 2 实现方法一3 5 4 4 实验结果和分析3 8 4 4 1 实验结果3 8 4 4 2 实验分析4 0 4 5 爿、结4 1 第5 章频繁项集挖掘的应用4 2 5 1 引言4 2 5 2 频繁项集挖掘的应用4 2 5 2 1 实验数据库的介绍4 3 5 2 2 数据预处理一4 4 5 2 3 关联规则挖掘4 5 5 3 小结4 6 结论与展望4 7 参考文献4 9 致 射5 3 附录a 攻读学位论文期间所发表的学术论文目录5 4 附录b 攻读学位期间参加的科研项目5 5 v 硕士学位论文 插图索引 图1 1数据挖掘的一般过程2 图1 。2 论文结构图5 图2 1候选项集和频繁项集的产生9 图2 2 频繁1 项集l 的生成1 1 图2 3f p 树的生成1 2 图2 4f m i n e r 算法示意图15 图2 5m o m e n t 算法示意图。1 7 图2 6p i n c e r s e a r c h 算法示意图l8 图3 1沿等价类进行的投影分解的过程2 3 图3 2事务数据库d 的投影分解图2 7 图3 3投影数据库d d 7 的f p 树2 7 图3 4 投影数据库d c7 的f p 树2 8 图3 5 f p g r o w t h 和e f p g r o w t h 算法在w e b d o c s 上( 5 0 0 m ) 的运行时间2 8 图4 1 网格p ( i ) 戈l j 分3 3 图4 2 扩展集p ( e ) “3 4 图4 1 3 样例数据库的数据链表组3 6 图4 4 将p ( a ) 中事务迭加到其他子格3 7 图4 5将p ( e ) 中事务迭加到其他子格3 7 图4 6 三种算法在w e b d o c s 上( 5 0 0 m ) 的运行时间3 9 图4 7 三种算法在b i ot r a i n 上的运行时间3 9 图4 8 三种算法在w e b d o c s ( 支持度1 5 ) 上的运行时间4 0 v 1 快速完全频繁项集挖掘算法研究 附表索引 表2 1事务数据库d 8 表2 2 通过创建条件( 子) 模式基挖掘f p 树1 3 表3 1事务数据库d 2 6 表4 1事务数据库d 3 2 表5 1实验数据库的属性及值域4 3 表5 2 实验数据库的部分记录4 4 表5 3 f p g r o w t h 算法和新算法挖掘出来的频繁项集总数和运算时间4 5 i 硕士学位论文 第1 章绪论 在过去的数十年中，随着数据库技术和信息技术的发展，人们在商业、科学 研究和行政事务等领域内产生和收集数据的能力得到迅速提高。被收集并存储在 众多数据库中的数据正在飞速增长、变得越来越庞大，使得人类在不借助于功能 强大的工具情况下就不能正确、顺利地分析、处理和理解这些海量数据。结果， 收集并保存在各类大型数据库中的数据就逐渐变成了“数据坟墓 ，很难再有被 访问和利用的机会。同时，在许多决策过程中，由于缺乏从数据中提取有用知识 和信息的技术与工具，决策者往往是基于直觉而不是基于数据库中信息丰富的数 据来做出决定【l 】，因而降低了做出正确决策的可能性。然而，保存在数据库中的 庞大数据中却蕴含着大量不为人知、但又非常有用的知识和信息，这些知识和信 息能够为我们的商业决策、科学研究和行政事务管理等提供有效的决策依据和基 础。因此，面对海量数据，我们迫切需要开发一种能够从信息丰富的数据中提取 有价值的知识和信息以辅助决策的技术。正是这种需求导致了数据挖掘( d a t a m i n i n g ) 技术的产生、飞速发展和在各领域中的广泛应用。 1 1 研究背景 信息时代人们获取信息的途径、方法越来越多，既包括传统的电视、报纸、 书刊等纸质渠道或媒体，也包括互联网、电子邮件等电子媒介，还包括基于互联 网、企业网的各类应用系统。另外，信息的规模也空前的庞大。据第2 6 次中国 互联网络发展状况统计报告统计，截至2 0 1 0 年6 月，中国网民规模达到4 2 亿， 突破了4 亿关口，较2 0 0 9 年底增力1 3 6 0 0 万人；互联网普及率攀升至3 1 8 ，较2 0 0 9 年底提高2 9 个百分点。宽带网民规模为3 6 3 8 1 万，使用电脑上网的群体中宽带普 及率已经达到9 8 1 。而据知名网站( h t t p ：w w w i n t e r n e t w o r l d s t a t s c o m s t a t s h t m ) 的最新统计，全球网民达到1 9 6 亿，占全球人口的2 8 3 。 大量信息在给人们工作、学习、生活带来方便的同时也带来了严重的问题。 要在这种大规模多渠道的海量信息中找到所需的有价值信息，确实比较困难，即 所谓的“数据丰富，知识匮乏 。数据挖掘技术正致力于解决该问题。它不仅是 一个重要的研究领域，而且在现实世界中具有重大的潜在应用价值。目前，通过 采用数据挖掘技术来减少日常商业运作的成本，数据挖掘产品的商业用户每年节 省的资金可达数亿美元。数据挖掘是通过仔细分析大量数据来揭示有意义的新的 关系、趋势和模式的过程。它出现于2 0 世纪8 0 年代后期，是数据库研究中一个很 有应用价值的新领域，是一门交叉性学科，融合了人工智能、数据库技术、模式 快速完全频繁项集挖掘算法研究 识别、机器学习、统计学等多领域的理论和技术【l 】。数据挖掘的基本任务有分类、 时间序列分析、预测、聚类、汇总、关联规则等。目前数据挖掘技术己在金融部 门、客户关系管理方面、零售业、市场营销、化学制药等行业得到很好的应用， 并取得明显的效益。 英语中挖掘( m i n i n g ) 一词是指从矿山中将矿物挖出并加以冶炼、最终提取 金属的过程。如果将这一概念运用到信息世界，那么，数据挖掘就是从数据库这 个矿山中挖掘出数据这种矿物，然后对挖掘得到的数据加以分析和处理、最终提 取有价值的知识的过程。 数据挖掘的完整定义是【l 】：从大量的、不完全的、有噪声的、模糊的、随机 的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的 信息和知识的过程。它又常常被称为数据库中的知识发现( k d d ：k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) 。 如图1 1 所示，数据挖掘过程一般包含以下几个基本步骤【1 】： 清 ： ： ： ： ；：卫舅 图1 1 数据挖掘的一般过程 硕士学位论文 1 ) 数据清理：消除噪音或不一致数据； 2 ) 数据集成：多种数据源的数据组合在一起； 3 ) 数据选择：从数据中检索与分析任务相关的数据； 4 ) 数据变换：数据变换或统一成合适挖掘的形式，如通过汇总或聚集操作； 5 ) 数据挖掘：使用智能方法提取数据模式； 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式； 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 数据挖掘按照基本功能和可以发掘的模式类型，分类为：概念与特征化描述、 分类与预测、聚类分析、孤立点分析、关联规则分析、演变分析等。数据总结、 分类发现、聚类、关联规则发现是数据挖掘的四种最重要也是最主要的任务，以 下分别介绍【1 】： 数据总结目的是对数据进行浓缩，给出它的紧凑描述。传统的也是最简单的 数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值， 或者用直方图、饼状图等图形方式表示。k d d 主要关心从数据泛化的角度来讨论 数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过 程。由于数据库上的数据或对象所包含的信息总是最原始、基本的信息( 这是为 了不遗漏任何可能有用的数据信息) 。人们有时希望能从较高层次的视图上处理 或浏览数据，因此需要对数据进行不同层次上的泛化以适应各种查询要求。数据 泛化目前主要有两种技术：多维数据分析方法和面向属性的归纳方法。 分类在k d d 中是一项非常重要的任务，目前在商业上应用最多。分类的目的 是学会一个分类函数或分类模型( 也常常称作分类器) ，该模型能把数据库中的 数据项映射到给定类别中的某一个。分类和回归都可用于预测。预测的目的是从 历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行预测。 和回归方法不同的是，分类的输出是离散的类别值，而回归的输出则是连续数值。 要构造分类器，需要有一个训练样本数据集作为输入。训练集由一组数据库记录 或元组构成，每个元组是一个由有关字段( 又称属性或特征) 值组成的特征向量， 此外，训练样本还有一个类别标记。 与分类分析法不同的是，聚类法的样本集是一组未标定的纪录，即样本还没 有进行任何分类。聚类的目的是根据一定的规则，把这些样本按照相似性归成若 干类别，即“物以类聚 ，使得属于同一类别的样本之间的距离尽可能的小，而 不同类别上的样本间的距离尽可能的大。在对样本合理划分后，对不同的类别进 行描述。 聚类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。 在统计方法中，聚类称聚类分析，它是多元数据分析的三大方法之一( 其它 两种是回归分析和判别分析) 。它主要研究基于几何距离的聚类，如欧式距离、 快速完全频繁项集挖掘算法研究 明考斯基距离等。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、 动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。这种聚类方法是一种基 于全局比较的聚类，它需要考察所有的个体才能决定类的划分；因此它要求所有 的数据必须预先给定，而不能动态增加新的数据对象。聚类分析方法不具有线性 的计算复杂度，难以适用于数据库非常大的情况。 频繁项集挖掘( f r e q u e n tp a t t e r n sm i n i n g ) 是最为重要的关联规则分析手段。 频繁项集挖掘通过分析数据集中数据项之间的关联关系，发现频繁在一起出现的 项集，描述大数据集中蕴藏的关联规则l 2 j 。例如，“4 0 的购买了，( ( p r i d ea n d p r e j u d i c e ) ) 的人同时也购买( ( s e n s ea n ds e n s i b i l i t y ) ) 就是一个典型的关联规则。 关联规则挖掘广泛应用于目录分类设计( c a t a l o gd e s i g n ) 、购物架管理、顾客购买 行为分析、d n a 分析、网络入侵预警诊断等，是数据挖掘应用最为广泛的方法之一。 设卢( i 1 , i 2 ，i n ) 是项( i t e m ) 的集合。记任务相关的数据库为数据交易( t r a n s a c t i o n ) 的集合，这里每个交易醍项的集合，并且t _ c _ 。对应每一个交易有唯一的标识， 记作t i d 。设a 是一个项集，交易t 包含a 当且仅当a 至z 。关联规则是形女i ：i a 号b 的蕴含式，其中a c l ，b c l ，并且a nb = o 。规则a 兮b 在事务集d 中成立，具有 支持度s ，其中s 是d 中交易包含a u b ( 且p a 和b - - 者) 的百分比，它是概率p ( a u b ) 。 规则a 号b 在交易集d 中具有可信度c ，如果d 中包含a 的交易同时也包含b 的百分 比是c 。这是条件概率p ( bia ) ，即是 s u p p o r t ( a 号b ) = p ( a ub ) ( 1 1 ) c o n f i d e n c e ( a 兮b 1 = p ( b i a ) ( 1 2 ) 项的集合称为项集( i t e m s e t ) 。包含k 个项的项集称为k 项集。项集的出现频率 是包含项集的交易数，简称为项集的频率、支持计数或计数。如果项集满足最小 支持度m i ns u p p ，即项集的出现频率大于或等于m i ns u p p 与d 中交易总数的乘积， 则称它为频繁项集。给定一个交易集d ，挖掘关联规则问题就是产生支持度和可 信度分别大于用户给定的最小支持度( r a i ns u p p ) 和最小可信度( m n 关联规则挖掘过程包括两个基本步骤：首先在数据集合中找出频繁出现的模 式，其次是在频繁项集的基础上产生强关联规则。其中第二个步骤相对简单，可 以在已知的频繁项集支持度的基础上，直接通过置信度计算枚举出所有的强关联 规则。所以关联规则挖掘的整体性能由第一步决定，是关联规则挖掘的核心，往 往也将第一步挖掘称为频繁项集挖掘。 另外频繁项集挖掘的应用不局限于挖掘关联规则，还广泛应用于相关性分析、 孤立点分析、分类与聚类等挖掘任务。频繁项集挖掘的应用领域涉及零售业、互 联网( w e b 挖掘、入侵检测) 、d n a 序列分析、专家系统，以及科学与医疗研究。 因此，频繁项集挖掘问题是一个具有重要理论意义和广阔应用前景的研究课 题，受到理论界与产业界的广泛重视。如今，在数据库应用与研究领域，已经形 硕士学位论文 成了一个以完全频繁项集挖掘、数据流频繁项集、最大频繁项集、频繁闭项集挖 掘等问题为重点的重要研究方向。 1 2 频繁项集挖掘的分类 频繁项集挖掘包括完全频繁项集挖掘、数据流频繁项集挖掘、最大频繁项集 挖掘，频繁闭项集挖掘等，是数据挖掘中的一类重要挖掘问题，本文将在第2 章详 细讲述这几个问题的研究情况。 1 3 本文的主要工作 由上所述，数据挖掘有很多任务和研究方向，而本文的主要工作是研究如何 提高关联规则挖掘算法的性能，使其能快速、有效地发现数据中的隐藏的关联知 识。本文的工作主要分为五部分： 1 ) 在给出数据挖掘和关联规则的基本概念基础上，详细介绍关联规则挖掘 的基本理论及其算法； 2 ) 在对已有关联规则挖掘算法的分析基础上，提出两种基于f p g r o w t h 算法 的关联规则挖掘新算法； 3 ) 通过实验对比验证新算法的有效性； 4 ) 给出新算法的一个挖掘关联规则应用实例； 5 ) 总结本文的研究成果、指出将来的研究方向。 1 4 论文结构 本文的结构如图1 2 所示： 第1 章绪论 上 第2 i f t ： 频繁项集挖掘算法的相关研究 上 第3 章 基于等价类的快速频繁项集挖掘算法研究 上 第4 章 基于格的快速频繁项集挖掘算法研究 上 第5 章 频繁项集挖掘的应用 上 总结与展望 图1 2 论文结构图 快速完全频繁项集挖掘算法研究 2 1 引言 第2 章频繁项集挖掘算法相关研究 频繁项集挖掘包括完全频繁项集挖掘、数据流频繁项集挖掘、最大频繁项集 挖掘，频繁闭项集挖掘等，是数据挖掘中的一类重要挖掘问题，广泛应用于关联 规则挖掘、相关性分析、入侵检测、序列挖掘、分类分析、聚类分析、w e b 挖掘、 x m l 挖掘等诸多数据挖掘任务。频繁项集挖掘首先由a g r a w a l 等提出，通过分析 客户交易数据库中的项集之间的关系提出了关联规则分析问题，进一步的研究表 明解决关联规则分析问题的核心是挖掘出可以产生关联规则的频繁项集( 频繁项 集、频繁序列、频繁子树等等) ，因此，频繁项集挖掘问题一直受到人工智能领域 理论研究的广泛关注，近百种相关的挖掘算法先后被提出。 2 2 完全频繁项集挖掘 2 2 1 经典算法 2 2 1 1a p f i o f i 算法 a g r a w a l 等在1 9 9 3 年设计的一种最有影响的挖掘布尔关联规则频繁项集的算 法【2 】。该算法分成两个步骤，步骤l 是使用侯选项集找频繁项集，步骤2 是由频 繁项集产生关联规则。 步骤1 使用侯选项集找频繁项集 a p r i o r i 使用一种称作逐层搜索的迭代方法，k 项集用于探索( k + 1 ) 项集。首 先，找出频繁1 项集的集合。该集合记作上l 。三l 用于找频繁2 项集的集合2 ， 而三2 用于找频繁3 项集的集合工3 ，如此下去，直到不能找到频繁k 项集。找每 个上k 需要一次数据库扫描。 a p r i o r i 算法的具体描述如下所示2 】： 算法：a p r i o r i 使用根据候选生成的逐层迭代找出频繁项集。 输入：数据库d 和最小支持度阈值m i n s u p 。 输出：数据库d 中的频繁项集三 方法： 1 ) l 1 = f i n d _ f r e q u e n t _ l i t e m s e t s ( d ) 2 ) f o r ( k = 2 ；三k 1 m ；k + + ) 3 )c k 2 a p f i o d g e n ( l k 1 ，r a i n _ s u p ) ； 4 ) f o re a c ht r a n s a c t i o nt d s c a nd f o rc o u n t s 5 )c t = s u b s e t ( c k ，t ) ；g e tt h es u b s e t so f tt h a ta r ec a n d i d a t e s 6 ) f o re a c hc a n d i d a t ec c t 7 )c c o u n t + + ； 8 ) 9 ) 厶= c gi c 。c o u n t t r a i n _ s u p 1 0 ) 1 1 ) r e t u r n 工= u k l k p r o c e d u r ea p r i o r i g e n ( l k t ：f r e q u e n t ( k 1 ) 一i t e m s e t s ；m i n _ s u p ：m i n i m u m s u p p o r tt h r e s h o l d ) 1 ) f o re a c hi t e m s e ti i k 1 2 ) f o re a c hi t e m s e t1 2 l k 1 3 )i f ( 1 l 1 = 1 2 1 ) a ( 1 l 2 = 1 2 1 2 ) a 八( 1 l k 2 = 1 2 k - 2 】) 八 ( 1 l 【k 一1 】= 1 2 k - 1 】) t h e n 4 ) c 2 l l q 2 ；j o i ns t e p ：g e n e r a t ec a n d i d a t e 5 ) i fh a s _ i n f r e q u e n t _ s u b s e t ( c , l k 1 ) t h e n 6 ) d e l e t ec ；p r u n es t e p ：r e m o v eu n f r u i t f u lc a d i d a t e 7 ) e l s ea d dct oc k 8 ) 9 ) 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 _ s u b s e t ( c ：c a n d i d a t ek - i t e m s e t s ；l k 1 ： f r e q u e n t ( k 1 ) - i t e m s e o u s ep r i o rk n o w l e d g e 1 ) f o re a c h ( k 1 ) 一s u b s e tso f c 2 ) i f s 辞厶1t h e n 3 ) r e t u mt r u e ； 4 ) r e t u r nf a l s e ； 其 a p r i o r i g e n 做两个动作：连接和剪枝。在连接部分，通过l k i 与k 1 连接 产生可能的候选。在剪枝部分，使用a p r i o r i 性质删除具有非频繁子集的候选。 步骤2 由频繁项集产生关联规则 一旦由数据库中的事务找出频繁项集，由它们产生强关联规则是直接了当的 ( 强关联规则满足最小支持度和最小置信度) 。对于置信度，可以用公式2 1 ，其中 条件概率用项集支持度计数表示。 s u p p o r t c o u n t ( au b ) c o n f i d e n c e ( a = b ) = p ( b i a ) = s u p p o r t c o u n t ( a ) ( 2 1 ) 快速完全频繁项集挖掘算法研究 其中，s u p p o r tc o u n t ( a ub ) 是包含项集a ub 的事务数，s u p p o r t _ e o u n t ( a ) 是 含项集a 的事务数，根据公式2 1 ，关联规则可以产生如下： 对于每个频繁项集l ，产生1 的所有非空子集。 s u p p o r t _ c o u n t ( 1 ) m i nc o n y 对于l 的每个非空子集s ，如果s u p p o r t _ c o u n t 【印，则输出规 则”s 专( 1 s ) ”。其中，m i nc o n f 最小置信度阈值。 为了更好地描述该算法，本文通过一个实例来说明a p r i o r i 算法的频繁项集挖 掘过程。该实例基于表2 1 所示的事务数据库。该数据库中共有1 0 个事务。设最小 支持度为3 ，h i ( m i n _ s u p = 3 0 ) 。 表2 1 事务数据库d t i di t e m s e t a ) 使用侯选项集找频繁项集 1 ) 在算法的第一次迭代，每个项都是候选1 项集的集合c i 的成员。算法简 单地扫描所有的事务，对每个项的出现次数计数。 2 ) 因最小事务支持计数为3 ，可以确定频繁1 项集的集合工l 。它由具有最 小支持度的侯选1 项集组成。 3 ) 为发现频繁2 项集的集合上2 ，算法使用厶q 厶，形成候选2 项集的集 合c 2 。 4 ) 下步，扫描d 中的事务，计算g 中每个侯选项集的支持度计数。 5 ) 确定频繁2 项集的集合2 ，它由具有最小支持度的c 2 中的候选2 项集 组成。 6 ) 算法使用厶伊q 三2 ，形成候选3 项集的集合g 。 c ： c b c d c d h 扎 “ d 曲 舻“ 扎 “ “曲t=吣e“m i e n n n n 亿吼n 仉n m 不低于最小支持度的项，从而构成频繁3 项集的集合上3 。 8 ) 算法使用l 3 l 3 ，形成候选4 项集的集合c 4 。尽管连接结果被删去， 这样c 4 = ，因此算法结束。 算法过程如图2 1 所示。 t i d项i d 的列表 a3 b 7 c8 d6 e 4 f1 g 2 比较候选支持度计数 与最小支持度计数 圉 崮c 扫簇翌赣个 二 删e = j 刺be 圜 扫描d ，对每个 t i d项i d 的列表 ab2 ac2 ad o ae2 bc5 bd4 be3 ed5 ce3 de 1 g t i d项i d 的列表 a3 b 7 c8 d6 e 4 比较候选支持度计数 与最小支持度计数 t i d项i d 的列表 bcd3 bce2 t i d项i d 的列表 bc5 bd4 be3 cd5 ce3 比较候选支持度计数 图2 1 候选项集和频繁项集的产生 b ) 由频繁项集产生关联规则 设最小置信度为6 0 ，由公式2 3 可得到如下关联规则。 e 号b ，c o n f i d e n c e = 3 4 = 7 5 e 穹c ，c o n f i d e n c e = 3 4 = 7 5 9 t i d项i d 的列表 bcd3 rr，l 快速完全频繁项集挖掘算法研究 d 净b ，c o n f i d e n c e = 4 6 = 6 6 7 d 专c ，c o n f i d e n c e = 5 6 = 8 3 3 c 穹d ，c o n f i d e n c e = 5 8 = 6 2 5 b j c ，c o n f i d e n c e = 5 7 = 71 4 c 号b ，c o n f i d e n c e = 5 8 = 6 2 5 bad 号c ，c o n f i d e n c e = 3 4 = 7 5 dac 号b ，c o n f i d e n c e = 3 5 = 6 0 b 八c 穹d ，c o n f i d e n c e = 3 5 = 6 0 2 2 1 2f p - g r o w t h 算法 由上面分析可以看到，关联规则的挖掘一般分为一个两步过程：1 ) 找出满足 最小支持度的所有频繁项集2 ) 由频繁项集产生同时满足最小支持度和最小置信 度要求的强相关联规则。关联规则挖掘算法的研究主要集中在如何快速有效地找 出满足最小支持度的所有频繁项集。a p r i o r i 算法需要多次重复地扫描数据库，并 产生大量的候选项目集来找出所有的频繁项集，因此，算法在时间和空间上的开 销太大。为了克服这些不足，h a n 等人提出一种新的基于所谓f p 树的频繁项集 增长算法，简称为f p g r o w t h ( f r e q u e n tp a t e r ng r o w t h ) 3 1 。 步骤1 算法描述 f p - g r o w t h 算法采用新的分而治之( d i v i d e a n d c o n q u e r ) 策略：将提供频繁项目 集的事务数据库压缩到一颗频繁项集树( f r e q u e n tp a t e r nt r e e ，简称为f p - 树) ，但仍 保留项目集关联信息；然后，将这种压缩后的数据库分成一组条件数据库( 一种特 殊类型的投影数据库) ，每个关联一个频繁项目，并分别挖掘每个条件数据库。 f p g r o w t h 算法描述如下所示【3 】： 算法：f p g r o w t h 使用f p 一