（计算机软件与理论专业论文）lr：一种新的频繁项集挖掘算法.pdf

l r 一种新的频繁项集挖掘算法 专业：计算机软件与理论 硕士生：任亚洲 指导老师：高集荣副教授 摘要 关联规则问题是数据挖掘领域的一个研究热点。该问题的解决分为两步：频 繁项集挖掘和利用这些频繁项集产生强关联规则。由于第一步决定着整体性能， 因此研究频繁项集挖掘问题具有十分重要的意义。 在频繁项集挖掘算法中，对数据库的表示可以采取水平表示、垂直表示等 多种方法，采用垂直表示的算法性能通常优于采用水平表示的算法。 数据库垂直表示又可以分为两种：用交集表示的t i d s e t 方法和用差集表示的 d i f f s e t 方法。当数据库稠密时，d i f f s e t 方法优于t i d s e t 方法。当数据库很稀疏时， t i d s e t 方法在挖掘的开始阶段优于d i f f s e t 方法，但随着挖掘深度的增长，d i f f s e t 方法逐渐地优于t i d s e t 方法。于是z a k i 提出先用t i d s e t 方法再改用d i f f s e t 方法的 上下分界算法，但仍存在些不足。 本论文的主要工作有： 1 提出了一种新的算法l r 。该算法第一次在t i d s e t 和d i f f s e t 基础上明确提 出将频繁1 项集集合划分成稠密部分和稀疏部分，并给出了分界值的确定公式。 它改变了上下分界算法将所有的频繁1 项集采取统一对待的方法，在挖掘时对这 两部分采取不同的策略：对稠密项部分采用d i f f s e t 方法，对稀疏项部分采用z a k i 提出的方法，即先采用t i d s e t 方法，当挖掘到一定深度时，再改用d i f f s e t 方法， 从而达到很好的效果。 2 在回顾1 9 9 3 年来比较重要的频繁项集挖掘算法的基础上，第一次给出算 法的历史图，从而有助于从宏观的、动态的角度对频繁项集挖掘算法有一个更全 面、更清晰的认识。 关键词：数据挖掘，关联规则，频繁项集，l r l r ：an e w a l g o r i t h mf o rf r e q u e n ti t e m s e t sm i n i n g m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ： r e ny a z h o u s u p e r v i s o r ： g a oj i r o n gv i c ep r o f e s s o r a b s t r a c t a s s o c i a t i o nr o l em i n i n gi sa ni m p o r t a n tf i e l di nd a t am i n i n g ，w h i c hi n c l u d e st w o s t e p s ：f i n d a l l f r e q u e n t i t e m s e t sa n dg e n e r a t e s t r o n ga s s o c i a t i o nr u l e sf r o mt h e f r e q u e n ti t e m s e t s t h eo v e r a l lp e r f o r m a n c eo fm i n i n ga s s o c i a t i o nr u l e si sd e t e r m i n e d b yt h ef i r s ts t e p s ot h ed o m i n a t e dt i m eh a sb e e ns p e n to nf i n d i n gm u c hb e t t e r 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 a m o n g a l l 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 s ，t h er e p r e s e n t a t i o no fd a t a b a s e i n c l u d e sh o r i z o n t a lf o r m a ta n dv e r t i c a lf o r m a ta n ds oo n u s u a l l yv e r t i c a lf o r m a t o u t p e r f o r m sh o r i z o n t a lf o r m a t t h e r ea r et w oi m p o r t a n tk i n d so fv e r t i c a lf o r m a tf o rd a t a b a s e ：t i d s e ta n dd i f f s e t ， w h i c ha r ee x p r e s s e db yi n t e r s e c t i o na n dd i f f e r e n c es e c t i o nr e s p e c t i v e l y f o rd e n s e d a t a b a s ed i f f s e to u t p e r f o r m st i d s e t ，w h i l ef o rs p a r s ed a t a b a s et i d s e tp e r f o r m sb e t t e ra t b e g i n n i n g ，b u tg e t sw o r s e w i t ht h ei n c r e a s eo ft h em i n i n gd e p t h z a k i p r o p o s e dag o o d w a yt os t a r tw i t ht i d s e ta n dt h e ns w i t c ht od i f f s e tf o rs p a r s ed a t a b a s e ，b u tt h e r ea r es t i l l s o m e t h i n gt ob ei m p r o v e d t h em a i nw o r k so ft h i st h e s i sa r ea sf o l l o w s ： f i r s t ，w ep r e s e n tan e wa l g o r i t h m ，l r ，w h i c hd i v i d e sa l lf r e q u e n t1 - i t e m s e t si n t o t w op a r t s ，d e n s ea n ds p a r s e ，o nt h eb a s eo ft i d s e ta n gd i f f s e t ，a n du s e sd i f f e r e n tw a y s f o rt h e s et w op a r t s w eu s ed i f f s e tf o rd e n s ep a r t ，a n df o rs p a r s ed a t a b a s ew eu s e t i d e s ta tt h eb e g i n n i n ga n dt h e ns w i t c ht od i f f s e tl a t e ra sz a k ih a sb e e np r o p o s e d s e c o n d ，w eg i v et h eh i s t o r yg r a p ho ff 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 sf o rt h e f i r s tt i m e ，w h i c hg i v e su sac l e a ra n dc o m p r e h e n s i v ev i e wo fa l lt h ea l g o r i t h m s ，a f t e r t h eo v e r v i e wo fa l lt h ei m p o r t a n ta l g o r i t h m ss i n c e1 9 9 3 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 s ，l r 第1 章数据挖掘 近年来，数据挖掘引起了信息产业界的极大关注。主要原因是在过去3 0 年中，计算机硬件的进步导致了功能强大的计算机、数据收集设备和存储介质 的大量供应，数据收集急剧增长，存放在大量和大型数据库中。这些海量数据 只是单纯的存放在数据库中，由于缺乏号门的工具，其中蕴涵的大量的信息单 凭人脑的分析远远不够，也越来越不现实，从而造成“数据信息贫乏”。数据和 信息之间的鸿沟迫切地要求系统地开发数据挖掘工具，将埋在数据库中的宝贵 信息挖掘出来。 1 1数据挖掘的定义 1 9 8 9 年8 月，在第1 1 届国际人工智能联合会议的专题研讨会上，首次提出 了基于数据库的知识发现( k d d ：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 ) 方法，到1 9 9 5 年，在美国计算机年会上提出了数据挖掘的概念。即从数据库中提取隐含的、未 知的、具有潜在使用价值信息的过程。 简单的说，数据挖掘是从大量数据中提取或“挖掘”知识。许多人把数据挖掘 视为数据库中知识发现的同义词，而另一些人则认为数据挖掘是数据库中知识发 现的一个基本步骤。我们采用数据挖掘的广义观点：数据挖掘是从存放在数据库、 数据仓库、电子表格或其他信息库的大量数据中挖掘有趣的知识的过程。 典型的数据挖掘系统具有以下主要成分： 1 数据库、数据仓库或其他信息库。 2 数据库或数据仓库服务器。 3 知识库。 4 数据挖掘引擎。 5 模式评估模块。 6 图形用户界面及模式可视化。 中山大学硕士学位论文第1 章数据挖掘 1 2数据挖掘的功能与应用 1 数据挖掘功能就它们可以发现的模式类型介绍如下： 数据可以与类或概念相关联。 关联分析。关联分析是从数据库中发现频繁出现的项集模式知识。 分类和预测。分类是从数据库中找出描述并区分数据类或概念的模型， 以便能够使用模型预测类标记未知的对象类。然而，在实际某些应用中， 人们可能预测某些空缺值，而不是类标记。当被预测的值是数值数据时， 称为预测。 聚类分析。聚类分析数据对象，而不考虑已知的类标记。一般情况下， 训i 练数据中不提供类标记，聚类可以用于产生这种标记。 孤立点分析。孤立点分析就是从数据库中找出一些数据对象，它们与数 据的一般行为或模型不一致。 演变分析。数据演变分析描述行为随时问变化的对象的规律或趋势，并 对其建模。 2 数据挖掘的应用越来越广泛，几乎涉及各个领域，比如：生物医学和d n a 数据分析，金融数据分析，零售业，电信业，音频和视频，科学和统计等。一般 数据挖掘都与特定的领域相结合来产生有效的挖掘工具。 1 3数据挖掘的研究现状 从数据库中知识发现在1 9 8 9 年提出到现在的近2 0 年，数据挖掘发展迅速。 美国已经多次举办过k d d 国际会议，规模从学术研讨会发展为国际大会，研究 重点也从发现方法转到系统应用，注重多种发现策略和方法的集成，以及多种学 科之间的相互渗透。国外知名大学的研究机构和各大i t 公司的研究部门都投入 大量的精力对数据挖掘进行研究，获得了诸多的研究成果。美国斯坦福大学智能 数据库系统实验室开发出了大量的商用化数据挖掘系统，如d b m i n e r 挖掘系统。 i b m 的a l m a d e n 实验室所进行的q u e s t 项目同样也是数据挖掘研究领域中的佼 佼者，其代表性的产品是d b 2i n t e l l i g e n tm i n e r f o rd a t a 。世界上比较知名的数据库 公司，如o r a c l e 、s y b a s e 等都已经在不同程度上将数据挖掘的有关方法结合到其 第1 章数据挖掘 数据库产品中来，使得大型数据库的功能向智能化的方向迈进了重要的一步。 与国外相比，国内研究起步较晚，1 9 9 3 年国家自然科学基金首次支持国内 研究机构对该领域的研究。目前，国内从事数据挖掘研究的人员主要在大学，部分 在研究所或公司。研究领域集中在学习算法的研究、数据挖掘的实际应用以及有 关数据挖掘理论方面的研究。 1 4数据挖掘的发展趋势 当前，鉴于数据、数据挖掘任务和数据挖掘方法的多样性，给数据挖掘方法提 出了许多挑战性的课题，这些课题包括： 1 可伸缩的算法。 2 交互式发现。 3 与数据库系统、数据仓库系统干l l w e b 数据库系统的集成。 4 数据挖掘语言的标准化。 5 可视化数据挖掘。 6 复杂数据类型挖掘。 7 w e b 挖掘、隐私保护和信息安全等。 第2 章关联规则挖掘 关联规则问题是数据挖掘领域十分活跃的热点，也是数据挖掘中最重要的一 个分支，已经引起了数据库、人工智能、统计学、信息检索、可视化等诸多研究 领域的专家和研究机构的广泛重视，并取得了很多重要成果。 关联规则挖掘实际上是寻找给定数据集中项之间的有趣联系。从大量商务事 务记录中发现有趣的关联关系，可以有助于许多商务决策的制定。关联规则挖掘 的一个典型例子是购物篮分析。该过程通过发现顾客购买的商品之间的关系，分 析顾客的购买习惯，从而做出相应的销售策略。 关联规则是在1 9 9 3 年由i b m 公司的a g r a w a l 提出，以后很多人对它进行大量 研究，大致涉及三个方面：是经典频繁项集挖掘的高性能算法研究，包括对算 法的改进，以及探索新的挖掘方法；二是拓展频繁项集的概念，提出相应的挖掘 算法：三是拓展关联规则概念及应用范围，包括规则的价值评估、新的关联规则 类型等。 2 1关联规则挖掘的基本概念 2 1 1 项目集的概念 定义1 关联规则挖掘的数据集记做d ( 一般是事务数据库) ，d = “，t 2 ，t n ， 其中t k = i t ，i 2 f m l ( = 1 n ) 叫做事务或记录，i p ( p = l m ) n 做项目( i t e m ) 。每 一个事务都有一个唯一的标识符，称为t i d 。 定义2 设仁 f 。，f 2 i q 7 黾d 中全体项目的集合。，的任何子集x 称为d 中的 项目集( i t e m s e t ) 。若凶斯，即项目集中包含项目的个数或项目集的长度为k ，则 称项目集x 为k 项目集( k - i t e m s e t ) 。 定义3 设氏和x 分别为d 中的事务和项目集，如果事务t k 包含盖中的所 有项目，即c f k ，称事务r k 包含项目集x ，或称“支持石。数掘集d 中包含项 目集x 的事务数称为项目集x 的计数或支持数，记做s 。项目集x 的支持度记 做s u p p o r t ( x ) ，它是x 在数据库中的概率p ，计算公式为： 中山大学硕卜学位论文 s 啪o n 。篱x 1 0 0 第2 章关联规则挖掘 公式2 - 1 其中l d i 是事务集d 的事务总数。 定义4 若s u p p o r t ( x ) 不小于用户指定的最小支持度m i n s u p ，则称项目集x 为频繁项集，否则为非频繁项集。频繁t 项集的集合通常记做h 。 定义5 设l 为频繁项集集合，我们定义最大频繁项集集合肘为： m = ，工i 不存在l 且，c ，) 即最大频繁项集是一个频繁项集p ，使得p 的任何真超集都不是频繁的。 定义6 项集工是频繁闭项集如果不存在项集刀同时满足如下两个条件： ( 1 ) xc x ( 2 ) s u p p o r t c 的= s u p p o n ( r ) ，这样的频繁项集x 叫做频繁闭项集。 2 1 2 关联规则挖掘的概念 定义7 彳、y 为项目集，且j n y 为空，蕴含式x y 称为关联规则，x 、y 分 别被称为关联规则x y 的前提和结论。项目集x uy 的支持度称为关联规则的 支持度，用于衡量规则在数据库中的统计重要性，记做s u p p o n ( x = 爿) ： s u p p o r t 口j 功= s u p p o r t ( x uy ) = p ( x uy ) 公式2 2 关联规则x y 的置信度是d 中包含硼拘事务同时也包含y 的百分比，即条件概率 p ( y 脚，用于衡量规则的可信程度，记做c o n f i d e n c e 卅) ： c o n f i d e n c e 晖jy ) = p ( 焖= s u p p o r t ( x u y ) 1 0 0 公式2 3 s u p p o r t ( x ) 通常由用户指定最小支持度m i n s u p 和最小置信度m i n c o n f ，只有符合最小支 持度和最小置信度的规则才是用户感兴趣的关联规则，这种规则称为强规则。 2 2关联规则挖掘问题分解 关联规则挖掘问题的解决分为两步： 找出所有的频繁项集。这些项集必须满足最小支持度。 由频繁项集产生强关联规则。规则必须满足最小支持度和最小置信度。 中山大学硕士学位论文第2 章关鞋规则挖掘 这两步中，第一步最关键，是关联规则挖掘问题的核心，它的性能决定若关 联规则挖掘的整体性能。因此大部分的关联规则研究将重点放在此步上，产生了 很多的频繁项集挖掘算法。 2 3关联规则挖掘的研究进展 1 多层关联规则挖掘。a g r a w a l 等提出的c u m u l a t e 和h a n 等提出的m l - t m l n 最为著名。 2 多维关联规则挖掘。基本上可以分为使用量化属性的静态离散化关联规则、 量化关联规则和基于距离的关联规则。s r i k a n t 等提出偏完全性概念，指出等深度 区间分割信息损失最小。l e n t 等提出用聚类法进一步聚合挖掘出的多维关联规 则。m i l l e r 等提出基于距离的关联规则，主要思想是根据距离来分割数量型区问。 3 基于约束的关联规则挖掘。数据挖掘可能发现数以千计的规则，其中许多 用户并不感兴趣。因此在数据挖掘过程中可以在用户的各种约束下进行。这些约 束包括：知识类型约束，数据约束，维层约束，兴趣度约束、规则约束。 4 相关分析。大部分关联规则挖掘算法使用支持度一置信度框架，但仍会产 生对用户来说不感兴趣的规则。b r i n 、a h m e d 等均采用非支持率可信度框架表 达规则的意义，提出了根据项目间统计相关性来挖掘相关性规则的算法 5 并行挖掘。这是提高海量数据挖掘效率的途径之一。 6 其他。关于多支持率规则挖掘、增量型挖掘、周期性片断挖掘、周期性关 联规则挖掘、事务数据库中的因果结构挖掘等问题亦有一些研究成果发表。 第3 章频繁项集挖掘研究现状 频繁项集挖掘算法按照挖掘方式分类，可以分为宽度优先搜索算法、深度优 先搜索算法、宽度和深度相结合的搜索算法。下面分别介绍这三类算法。 3 1宽度优先搜索算法 3 1 1 a p r i o r i 算法 该算法【1 】是由a g r a w a l 在1 9 9 4 年提出的一种最有影响的挖掘布尔关联规则 算法。它使用一种称作逐层搜速的迭代方法产生频繁项集，利用“频繁项集的所 有非空子集都必须也是频繁的”这条性质对候选项集删减。 逐层搜索迭代方法中用上k _ l 生成“的步骤如下：第一步是连接步：自己与 自己连接产生候选七一项集的集合，记做c k 。设l l 和2 是l k 1 中的项集。记号6 们 表示f i 的第j 项。假定事务中的项按字典次序排列。执行连接lk _ 1d i l k - 1 ，其中上k _ l 中的元素是可连接的，如果他们前 一2 ) 个项是相同的。连接f 1 和z 2 的结果项集是 h 1 z 2 1 1 七_ 1 f 2 阵- 1 。第二步是剪枝步：对每个c k 中的项，确定其k - 1 项子集 在l k - l 中，否则删去c k 中的该项。 算法的主要时间花在删减c k 以及确定“上。为了减少时间消耗，引入数据 结构h a s h t r e e 。它含有两种节点，叶子节点和内部节点。内部节点指向其它的节 点，叶子节点存放项目集。设根结点深度为1 。寻找个长度为k 的项集时，从 根结点开始，直到叶子节点。在深度为i 的内部节点，对该项集第f 个项使用h a s h 函数，从而决定转向某个深度为( “1 ) 的节点。 算法的主要空间花在存放k - l 的h a s h t r e e 和c k 的h a s h t r e e 上。 a p r i o r i 的特点是： 扫描数据库的次数等于最大频繁模式的长度。 需要生成频繁模式的候选集。当支持率阂值较小而出现大量“长”关联 规则时，a p r i o r i 代价很高，容易出现组合爆炸。 中山大学硕士学位论文第3 章频繁项集挖摭刊f 究现状 3 1 2 a p r i o r i 的改进算法 对a p r i o r i 的改进主要在控制候选集的规模或减少数据库扫描次数等几个方 面。 1 a p r i o r i t i d 算法 该算法对数据库删减。每次确定出频繁i 项集l ，后，将数据库每条事务用 它所包含自缸i 中的项集表示，从而生成新的数据库西，用于求厶+ 1 ，初始西= d 。 但是该算法在挖掘前期会造成数据库膨胀。 2 a p r j o r h y b f 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 算法。避免a p n o d t i d 算法前期造成的数据库膨胀。 3 d h p 算法阳】 该算法根据c k 确定c k + z ，并用规模适当的h a s h 存放靠+ ，。在第卉遍扫描数据库 时，同时统计c k 矛l l h a s h 表中的c k + 】项目。在求出厶的同时，h a s h 表中c k + 1 1 的计数 可用于进一步剪裁c k + 1 口 4 p a r t i t i o n 算法【4 】 当数据库很大时，存放厶】的h a s h t r e e 和c k 的h a s h 。t r e e 的内存可能不够用， 就需要额外的操作。为此将数据库分成几块，对每块数据库d ；独立进行数 据挖掘。最后将每个数据库的i ( = 1 ，2 n ) 频繁项集合并，再次读入所有数据 确定最终的频繁项集。但是这个算法将数据库分块之后，造成全局频繁项可能不 是局部频繁项，而局部频繁项可能不是全局频繁项，但是最终合并的频繁项集肯 定包含全局频繁项集，不会造成遗漏。 5 s a m p l i n g 算法【5 】 数据库很大时，该算法采取从数据库随机抽样，对抽样之后的数据库进行频 繁项集挖掘。但是该算法可能造成频繁项遗漏。为此采取两种措施： 降低m i n s u p p o r t ，但是为此造成的损失是删减过大的频繁项候选集而消 耗太多的时间。 采取一种机制确定是否所有的频繁项集都包含在其中，若没有遗漏，只 需扫描一次d 确定频繁项集计数，否则，可以做第二次扫描，以找出在 第一次扫描时遗漏的频繁项集。当效率最为重要时，这种方法特别合适。 中山大学砷! 十学位论文第3 章频繁项集挖掘研究现状 6 d i c 算法1 6 ，7 】 该算法是a p r i o r i 算法的更新的一个变种它软化了计算和产生候选的界限。 只要候选满足最小的阅值。即使还没有全部计算这个候选项集在每个事务中是否 出现，d i c 中就开始由它产生下一步的候选限因为如此，它采用了一个前缀树 与h a s h 树不同的是，前级树中每个节点，包括叶节点和内部节点，都代表某个候 选频繁项集各个频繁子项集 3 1 3 a p r i o r i 算法最新进展 最新的a p r i o r i 算法吸收了到目前为止频繁项集挖掘算法中产生的几乎各种 好的方法，比如利用t r i e 树表示数据库及存储频繁项集以及t r i e 树的优化等，引 入h a s h 方法，对确定1 和2 频繁项集和删减候选项集进一步优化等。最典型的 这类a p r i o r i 算法是：c h r i s t i a nb o t g e t t 的a p r i o r i 算法f 8 】，f e r e n cb o d o n 的a p r i o r i 算法吼 3 2深度优先搜索算法 宽度优先搜索算法的主要缺点是： 要存放候选项集和部分频繁项集，消耗内存较大。 要先删减候选项集再读入数据库确定频繁项集，消耗时间较大。 为此，提出了深度优先搜索算法。按照对数据库的表示，该类算法可以分为 两类： 对数据库采用水平或垂直表示。 对数据库采用t r i e 表示。 3 2 1数据库水平或垂直表示算法 下图给出了数据库水平和垂直表示方法，每种方法又分为两种：链表表示和 位图表示。 中山火学硕，l j 学位论文 第3 章频繁项集挖掘州究现状 数据库水平链表表示 数据库水平位图表示 数据库垂直链表表示 数据库垂直位图表示 图3 - 1 数据库的四种表示 这四种表示各有优缺点：位图表示可以一次操作一组数据，简单快捷，而链 表表示则要逐一比较。当数据库很稀疏时，由于存储过多的“o ”元素而导致位 图表示占用空间远比采用链表表示要大。垂直表示可以引入t i d s e t 或d i f f s e t 方法， 不必产生候选项集，直接生成频繁项集，但是存放结果要占用很多空间。水平表 示则可以结合指针技术不必产生物理数据库，但是指针操作过于复杂和费时。 1 e c l a t 算法【1 0 】 该算法的主要特点如下： 采用深度优先搜索。 利用数据库的垂直表示，每个项对应其t i d s e t ，在求频繁项集时只需将 两个t i d s e t 相交，这样可以在判断是否为频繁项集的同时，又去掉不必 要的项。 将搜索空间分成格，或更小的子格，就不必同时存储所有频繁项集的 t i d s e t ，从而避免内存溢出的可能。 一d 一 同川h _ ! 坐堕兰型生竺型塑竺竖一 笙! 兰塑茎望堑丝塑! ! 窒翌些 举例：设数据库为 1 0 0 2 0 0 3 0 0 4 0 0 图3 2 数据库 图3 _ 3 给出该算法的挖掘图示，最终生成的频繁项集是： d ， c ) ， a ) ， e ) ， g ， dc ) ， da ) ，i de ) ， dg ) ； dca ) ， dce ； da e ) ； ca t ， ce ；l ae i ；l eg ) 。 ，一、 图3 - 3e c l a t 算法挖掘频繁项集 、 为前缀 略 珊碉固珂 中山大学硕士学位论文第3 章频繁项集挖掘研究现状 2 d i f f s e t 算法【1 1 】 分析e c l a t 算法，发现当数据库稠密时，求交集会导致大量的冗余而浪费了 很多空间，因此引入了d i f f s e t 方法，将求交集改为求差集。 设两个项目集爿= 日，b = p y 。其中，p 为a 与b 的共享前缀。则若用t i d s e t 方法求项集脚7 的t i d s e t ，表示为t ( e x d = t ( e x ) nf ( p 功，这罩，胍n 7 的t i d s e t 分别为t ( e x ) 、t ( p y ) 。而p x y 的计数j , j i t ( p x d i 。如果用d i f f s e t 方法，则先求d ( p x e ) 。 即d ( p x y ) = t ( p x ) - - t ( p y ) 。而跗y 的计数为尸的计数减去i d ( p x y ) l 。若开始鲋、 p y 都是用d i f f s e t 表示的，不知道其t i d s e t ，则求用时，利用公式d ( p x y ) - i ( p y ) 一d ( e ) o 。因为，d ( p x y ) = t ( p x ) 一t ( p y ) = t ( p x ) 一t ( p y ) + f ( p ) 一f ( p ) = ( f ( p ) o ( p 功) 一p ( p ) - t ( p x ) ) = d ( p 功- d ( p x ) 。册y 的计数仍为麒的计数减去l d ( p x l 9 1 。 在【1 1 中给出了这两种方法在数据挖掘不同阶段，而得到的d i f f s e t 和t i d s e t 平 均长度的比较。结果显示，当数据库越稀疏时，t i d s e t 开始平均长度降低越明显， 随着深度的增加，平均长度几乎保持不变，当数据库稠密时，平均长度从一开始 就几乎不变。而d i f f s e t 对任何数据库，在任何阶段，其变化都比较明显，其整体 性能优于t i d s e t 方法。但是也有例外，即当数据库很稀疏时，在开始不如t i d s e t 方法。为此，作者提出当数据库稠密时直接采用d i f f s e t 方法，当数据库稀疏时先 采用t i d s e t 方法，挖掘到一定阶段后再改用d i f f s e t 方法。 3 v i p e r 算法【1 2 1 分析e c l a t 算法，若数据库稠密时，则用数据库垂直t i d s e t 表示占用较大的 空间，为此v i p e r 算法引入了数据库的垂直位图表示，但是当数据库较稀疏时又 会因为大量的“o ”而浪费空间，该算法又引入s k i n n i n g 方法用于压缩垂直位图。 压缩方法：将连续的o 和1 分组，分别设每组权值为和暇，即当连续 的0 或1 达到或m 时，即这一组为满组。压缩表示中，若为满组则用1 表 示，而剩余的连续的0 或1 则用二进制表示个数。o 和1 之间的转换没有明显分 隔，只是通过在每个最后一个满组表示1 和剩余的计数域之间插入o 来隐式地分 隔1 和0 。为此，即使当恰好没有剩余时，仍用1 0 92 暇位填满计数域。 举例： ( 1 ) “( o o o ) 8 ( 1 ) 。( o o o o ) o ( o o o o ) 5 ( o ) 5 ( 1 ) 6 ( o o o o ) “( o o o o ) 1 ( o ) ( 1 ) k ( 0 0 0 0 ) 。( o ) m 压缩后代码表示为： o ) 4 0 0 ( x1 ) 8 ( 1 ) c o ( 1 ) o ( 1 ) 2 0 ( 0 1 ) f ( 1 ) g o ( 1 ) “( 1 ) 1 0 ( 0 1 ) 1 0 ) k o ( o 。o ( 0 1 ) m l ， 中山大学碗卜学位沦文第3 章频繁史集挖掘 i j 究现状 上标是为了对比原始位图在压缩后表示成什么，而未标记的0 则是填充符。 该算法问时引入了几项改进方法： 候选项同时产生方法( f o r c ) 。陔方法一次性产生某前缀的下一深度的 所有候选项，而不是只产生其中一个，从而避免了重复的删减查找。 候选项多深度统计方法( f a n g s ) 。该方法读入长度为i 的频繁项集， 但可以确定长度为i + 1 到2 i 的频繁项集，从而避免了多次读入。 优化将s n a k e 写入磁盘的方法。 求2 一频繁项集时，将数据库的垂直位图表示改为水平表示，引入矩阵方 法求解。 4 d e p t h p r o j e c t i o n 算法1 1 3 1 该算法是挖掘最大频繁项集的算法，但是它也可以用于频繁项集的挖掘，特 点为： 对数据库删减。以图3 3 为例，在确定出频繁1 项集后，这时数据库事 务删减非频繁项，只剩下频繁项的集合。开始挖掘以b 为前缀的频繁项 集，确定出可能的候选项集 bc ) ， bd ) ， bh ) ，遍历这个数据库，确定 出 bc ) ， bd ) 为频繁项集，输出。对数据库事务进一步删减为与b 的 扩充集e ( b ) = cd ) 的交集的项集集合，删去对本次挖掘没用的事务以 及事务中没有用的项。依次挖掘以 b ，c ， bd ) 为前缀的频繁项集。 结束后挖掘以 c ) ， d ， h i 为前缀的候选项集，重复上面的过程。 在统计候选项集时，在对数据库用水平位图表示基础上，直接采用聚集 桶计数方法即b u c k e t i n g 方法，十分快捷。 d e p t h p r o j e c t i o n 的不足之处是： 每次要生成新的投影数据库，若挖掘深度为k 的项集时，内存需放以前 ( k - 1 ) 个投影数据库，还有频繁项集子树。 桶计数技术在频繁1 项集较少时效果好，反之，对数据库采用水平位图 表示需要占用大量的无用空间。 5 h m i n e 算法1 1 4 】 该算法引入h s t r u c t 结构，仍然采用深度优先挖掘方法，但不必生成物理数 据库投影，而足在内存数据库基础上通过改变指针，生成新的h e a d e rt a b l e 表示 中山大学硕：卜学位论文第3 章频繁项集挖掘研究现状 出“新的”投影数据库。 主要过程：读入数据库至内存，删去非频繁项，对每个事务的每项附一个指 针域，用来指示以该项为首的下一条事务。建立h e a d e rt a b l e ，存放每个项的计数 值及以该项为首的事务链头指针，将数据库中具有相同首项的事务用链指针串起 来。通过遍历h e a d e rt a b l e 某项的链所串链的事务集合，确定以该项为前缀的频 繁项集，同时改变指针指示，建立新的子h e a d e rt a b e l ，生成逻辑数据库投影，用 于进一步挖掘。 3 2 2数据库t r i e 及其变形表示算法 此系列算法与以前的算法有很大的不同，即在表示数据库时用t r i e 树或其改 进形式，而不是水平或垂直表示；在挖掘时不用产生候选项集，而是采用频繁模 式增长方法确定频繁项集。 1 f p g r o w t h 算法【1 5 1 j i a w e ih a n 在2 0 0 0 年提出了称作频繁模式增长或简称f p 一增长的方法。算 法基本思想：首先将数据库压缩到一棵频繁模式树即f p 。t r e e ，但仍需保留项集 关联信息；然后将这种压缩后的数据库分成一组条件数据库，每个关联一个频繁 项，并分别挖掘每个数据库。 举例：数据库略【1 6 】 第一步：求出n 。扫描数据库求出频繁1 项集的集合，并得到它们的支持 度计数。设最小支持度计数为2 。频繁项的集合按支持度计数的递减顺序排序。 结果集或表记作三。正= 旧：7 ，1 1 ：6 ，1 3 ：6 ，1 4 ：2 ，1 5 ：2 。 第二步：构造f p t r e e 。树的根结点设为“n u l l ”。第二次扫描数据库，每个事 务中的项按上中的次序( 即递减支持度计数) 排序，并对每个事务创建一个分枝。 先读入t 1 0 0 ，排序 1 2 ，1 1 ，1 5 1 ，创建第一个分支， ，1 2 为n u l l 根节点的孩子，1 为尼节点的孩子，巧为，2 节点的孩子，并且每个节点 计数加1 ( 初始为0 ) 。读入第二个事务2 0 0 ，排序为 尼，h ) ，由于与第一个分 支共享前缀节点佗，所以只需为j 2 节点创建一个孩子( 1 4 ：1 ) ，同时节点，2 计数 加1 成为( 髓：2 ) 。依次按此步骤读完数据库。最终结果如图3 - 4 ： 中山大学坝十学位论文第3 章频繁项集挖掘研究现状 项i d支譬严计数 图3 - 4 存放压缩的频繁模式信息的f p t r e e 第三步：挖掘f p - t r e e 。先从上最后一项巧，由f p 一树生成它的条件模式基： ( i 2 ， 1 1 ：1 ) ，( 1 2 ，1 1 ，b ：1 ) ) ，构造巧的条件f p 一树，过程同第一、第二步，结果是 单支树，最后直接产生频繁模式：q 2 1 5 ：2 ) ，( 1 1 5 ：2 ) ，1 11 5 ：2 ) 。接下来考虑，4 ， 分析同巧。b 的条件模式基是 ( ，21 1 ：2 ) ，( 2 ：2 ) ，( ，1 ：2 ) ) 。构造它的条件f p 一树， 过程同第一、第二步，该树有两个分支如下图3 5 ： 图3 - 5 具有条件节点1 3 的条件f p t r e e 接f 来对乃的f p - 树进行挖掘，过程同第三步。结果产生的模式集为： ( 1 2 1 3 ：4 ) ，( 1 1 3 ：2 ) ，( 1 2 1 1 乃：2 ) ) 。最后对l 中的第一个点尼挖掘。 中山大学硕一i 学位论文 第3 章频繁项集挖掘研究现状 f p g r o w t h 算法如下【1 6 i 算法：f p g r o w t h 。使用f p t r e e ，通过模式段增长，挖掘频繁模式。 输入：事物数据库d ：最小支持度闽值m i n s u p 。 输出：频繁模式的完全集。 方法： ( 1 ) 按以下步骤构造f p t r e e ： ( a ) 扫描事物数据库d 一次。收集频繁项的集合f 和它们的支持度。对f 支 持度降序排序，结果为频繁项集表。 ( b ) 创建f p t r e e 的根结点。对于d 中每个事务t r a n s ，执行： 选择t r a n s 的频繁项，并按工中的次序排序。设排序后的频繁项表 为陋l p 】，其中p 是第一个元素，而p 是剩余元素的表。调用 i n s e r tt r e e ( 【p l e ，7 ) 。该过程执行情况如下：如果丁有子女使得 n i t e m n a m e = p i t e m n a m e ，则n 的计数增加1 ：否则创建一个新节点 ，将其计数设置为1 ，连接到它的父节点l 并且通过节点链结构 将其链接到具有相同i t e m n a m e 的节点。如果p 非空，递归地调用 i n s e tt r e e ( p , na ( 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 o w t h ( t r e e ，a ) 1 ) i f t r e e 含单个路径p t h e n 2 ) f o r 路径p 中的节点的每个组合( 记做p ) 3 ) 产生模式f l u a ，其支持度s u p p o r t = 中节点的最小支持度； 4 ) e l s ef o re a c ha i 在t r e e 的头部 5 ) 产生一个模式户= a i u a ，其支持度s u p p o r t = a i s u p p o r t ； 6 ) 构造卢的条件模式基，然后构造户的条件f p t r e et r e e b ； 7 ) i f t r e e b 不是空集t h e n 8 ) 调用f p _ g r o w t h ( t r e e b ，户) ； 当数据库很大时，内存可能容不下f p t r e e ，因此作者提出了数据库投影技术。 中山大学硕上学位沦文第3 章频繁项集挖掘研究现状 在投影之前，先确定频繁1 项集表l ，然后依次读入数据库事务，去掉非频繁项， 按降序排列该事务中的频繁项，接下来可以选择两种( 分布式或划分) 投影技术。 最终产生每个项的投影数据库，进而建立该项的f p t r e e 并挖掘该树。 分布式投影技术。每条事务投影到每个频繁项上。比如：事务卅声，c , d ) ， 在d 的投影数据库上增加一条：似bc ，在c 的投影数据库上增加叫 b ，在b 的投影数据库上增加一条叫 。 划分投影技术。只将每条事务投影到该事务最后一个项上。比如：事务 。声，c d ，只在d 的投影数据库上增加一条记录：翻bc ) 。当建立b 的f p 树时，对b 投影数据库中的每条项目进一步投影。比如：b 一投影 数据库中项目似b c ) ，设项目计数为”。将它进一步投影到c 一投影数据 库中，增加一条埘曰 。若已经有该项目，则在该项目的计数上加n ：否 则新建一条，计数值为n 。 该算法的缺点是： 当数据库很稀疏时，可以共享前缀的事务很少，几乎每条事务都要创建 一个分支，所需内存就会很大。 递归地产生条件模式树和条件模式基，既耗费时间又耗费空间。 2 o p 算法【1 l 1 8 】 o p 算法将f p g r o w t h 和h m i n e 算法结合在一起，当数据库稠密时采用 f p g r o w t h 算法，当数据库稀疏时采用h m i n e 算法，同时对二者做了较大改进。 对f p - g r o w t h 算法的改进：由于f p g r o w t h 算法递归地构造条件f p ，t r e e ，要 占用大量内存。因此，o p 算法采用改变指针而不是生成物理投影来达到同样的 效果。为此该算法采用两种策略：自底向上虚拟投影技术，即子女的频繁模式树 表示由遍历以父亲为根的子树得到；自顶向下的投影技术，即虚拟子女的投影数 据库由父亲频繁模式树中以穿线节点为树叶的子树林推导而来。 下面举一个自底向上的例子1 1 8 i ：以挖掘以c 为前缀的频繁项集为例，通过 遍历c 为根的子树得到投影数据库。 中山二k ：学碗：r 学位论文第3 章频繁项集挖掘研究现状 、 、 图3 - 6c 树的投影数据库 当挖掘到c 的孩子f 时，进一步投影得到下图： 、 图3 ，7f 树的投影数据库 该算法对h m i n e 改进：不用链表表示数据库，而是用数组表示，这样更节 省空间。由父亲到其子女投影可以采取虚拟投影也可以物理投影。 举例【1 8 】：结点( 3 )