（计算机应用技术专业论文）改进的垂直数据表示的高效频繁项集挖掘算法研究.pdf

论文题目：改进的垂直数据表示的高效频繁项集挖掘算法研究 专业；计算机应用技术 硕士生：梅锦锋 指导教师：衣杨副教授 摘要 关联规则挖掘是近年来发展十分迅速而且非常活跃的研究领域。它主要应用于发 现数据中不同项目或属性之间的有趣联系。随着被收集和存储数据的高速增长，许多 业界人士对于从他们的数据库中挖掘关联规则的兴趣愈加浓厚。频繁项集挖掘是关联 规则挖掘的基础和核心问题。相关挖掘算法的性能直接影响数据挖掘尤其是关联挖掘 的效率和应用范围。为了进一步适应和满足用户不断变化的需求，本文进行了一系列 关于提高频繁项集挖掘算法的性能和完善相关功能的研究工作。 本文首先认真地分析和归纳了当前频繁项集挖掘算法的研究成果，并测试和总 结出相关算法的实现方法和性能特点。为提出性能和功能更优的频繁项集挖掘算法作 好理论准备。然后在提高执行挖掘的效率和消除矛盾或无效规则相关信息这两个方面 对当前的高效挖掘算法进行一系列的改进。1 ) 本文提出的h y b r i d s e t 算法结合了采用 垂直数据表示的e c l a t 和d i f f s e t 算法分别善于处理稀疏和稠密数据集的优点。实验证 明，h y b i r d s e t 算法在分析稀密程度不同的数据集时的性能与e c l a t 等经典算法的最优 性能基本一致甚至更优。2 ) 充分利用频繁项集的相关信息是减少计算候选集的支持 度的时间开销的重要途径。实验证明，本文根据这一特点提出的h y b i r d s e t + 算法能在 很多情况下进一步提高执行频繁项集挖掘任务的效率；3 ) 由于上述算法的结果中存 在与矛盾或无效规则相关的频繁项集，本文根据频繁项集和相关度之间的联系对 h y b i r d s e t + 算法做出相应改进。实验证明，改进后的d h y b i r d s e t 算法能在真实数据的 分析中减少部分冗余频繁项集的生成。 关键词：关联规则挖掘，频繁项集挖掘，h y b i r d s e t 算法，垂直数据表示 t i t l e ：i m p r o v e de f f i c i e n ta l g o r i t h m sf o rm i n i n gf r e q u e n ti t e m s e t sb a s e do nv e r t i c a ld a t a l a y o u t m a j o r ：c o m p u t e ra p p l i c a t i o na n dt e c h n o l o g y n a m e ：j i n f e n gm e i s u p e r v i s o r ：a s s o c i a t ep r o f e s s o ry a n gy i a b s t r a c t t h ea s s o c i a t i o nr u l em i n i n gi sav e r ya c t i v er e s e a r c hf i e l dw h i c hh a sm a d ear a p i d d e v e l o p m e n ti nr e c e n ty e a r s a n di ti sa p p l i e dt 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 n s b e t w e e nt h ed i f f e r e n ti t e m so ra t t r i b u t e s w i t ht h eh i g h - s p e e di n c r e m e n to f t h ec o l l e c t e da n d s t o r e dd a 饥t h ep e o p l ea t em o r ei n t e r e s t e di no b t a i n i n gt h ea s s o c i a t i o nr u l e sf r o mt h e i r d a t a b a s e f r e q u e n ti t e m s e t sm i n i n gp l a y sac r u c i a lr o l ei na s s o c i a t i o nr u l em i n i n g t om e e t t h ev a r i o u sd e m a n d so ft h eu s e r s ，as e r i e so fr e s e a r c ho ni m p r o v i n gt h ep e r f o r m a n c ea n d f u n c t i o n so f t h ea l g o r i t h m so f t h ef r e q u e n ti t e m s e t sm i n i n gh a db e e nc a r r i e do u t i nt h i sp a p e r , a no v e r v i e wo ft h ef r e q u e n ti t e m s e t sm i n i n gi sg i v e n b o t hs t r e n g t h sa n d w e a k n e s s e so fs o m ep o p u l a rr e l e v a n ta l g o r i t h m sa l ei l l u s t r a t e da n ds u m m a r i z e d t h e n , a s e r i e so fi m p r o v e m e n to ne n h a n c i n gt h ee f f i c i e n c ya n de l i m i n a t i n gt h er e d u n d a n tf r e q u e n t i t e m s e t sa r ep r o p o s e d 1 1t h i sp a p e rp r e s e n t st h en o v e la l g o r i t h mc a l l e dh y b r i d s e tw h i c h c o m b i n e st h em e r i t so ft h ee c l a ta n dd i f f s e ta l g o r i t h m sw h i c hw e r eg o o da td e a lw i t ht h e s p a r s ea n dd e n s ed a t a s e t sr e s p e c t i v e l y e x p e r i m e n t a lr e s u l t ss h o wt h a tb o t hs p a r s ea n d d e n s ed a t a s e t sh y b i r d s e ti ss u p e r i o rt ot h ep r e v i o u sa l g o r i t h m s 2 ) m a k i n gm o s tu s eo ft h e i n f o r m a t i o no f t h ef r e q u e n ti t e m s e t si st h ew a yt or e d u c i n gt h ec o s to f c o u n t i n gt h es u p p o r t s o ft h ec a n d i d a t e s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ei m p r o v e da l g o r i t h mc a l l e dh y b i r d s e t + i sp r o p o s e da c c o r d i n gt or e l e v a n tp r o p e r t i e si ss u p e r i o rt ot h eh y b i r d s e ti nm o s tc a s e s 3 1 u s u a l l y , s o m es t r o n ga s s o c i a t i o nr u l e sw h i c hc a nb ed e d u c e df r o mt h ef r e q u e n ti t e m s e t sa r e c o n f l i c t i n go rv o i d t h ei m p r o v e da l g o r i t h mc a l l e dd h y b i r d s e ti sp r o p o s e da c c o r d i n gt ot h e l i n k a g ea m o n gt h ef r e q u e n ti t e m s e t sa n dc o r r e l a t i o n e x p e r i m e n t a lr e s u l t ss h o wi tt a l l r e d u c es o m er e d u n d a n ti n f o r m a t i o ng e n e r a t e di nt h ep r o c e s so f a n a l y z i n gt h er e a ld a t a k e yw o r d s ：a s s o c i a t i o nr u l em i n i n g ，f r e q u e n tl t e m s e t sm i n i n g ，h y b i r d s e t ，v e r t i c a ld a t a l a y o u t 改进的垂直数据表示的高效频繁项集挖掘算法研究 第1 章前言 1 1 研究背景 第1 章前言 随着信息科学技术的高速发展以及数据库管理系统的广泛应用，各大领域积累的 数据日益倍增。与此同时，这些数据蕴含了大量用户所需的知识。尽管数据库系统具 有高效的录入、查询和统计数据等功能，但是它缺乏能发现数据背后隐藏的知识的手 段，从而造成在当今全球范围内出现“数据爆炸但知识匾乏”的窘境。为了解决这个 问题，众多数据挖掘专家进行大量的研究工作并取得了一系列的研究成果。 数据挖掘( d m ，d a t am i n i n g ) r t 是二十世纪九十年代兴起的一项决策支持的新 技术。它主要基于a i 、机器学习、统计学等技术，高度自动化地分析企业原有的数据， 做出归纳性的推理，从中挖掘出潜在的模式，预测客户的行为，帮助企业的决策者调 整市场策略，减少风险，做出正确的决策。总言之，数据挖掘是从大量数据中提取或 “挖掘”知识。 起源于购物篮分析的关联规则是数据挖掘最重要的研究内容之一。在购物篮分析 中，它通过发现顾客放入其购物篮中不同商品之间的联系，从而进一步了解顾客的购 买习惯，以致获取更大的经济效益。例如：沃尔玛利用相关技术获知将尿布与啤酒摆 在一起能够同时提高两者的销售额。到目前为止，关联规则挖掘技术已广泛应用到众 多行业。例如：零售、保险、银行、通信、政府、医疗，教育等等。 关联规则挖掘大致分为频繁项集挖掘和产生规则两个阶段。其中，频繁项集挖掘 是关联规则挖掘的核心内容，它的具体含义是指从事务记录中获取全部出现频率不小 于一个预定义的闽值的项集。频繁项集挖掘的性能直接影响关联挖掘的效率和应用范 围。随着用户对提高执行挖掘任务效率的需求日益迫切，众多数据挖掘专家进入了该 研究领域并取得了大量研究成果。 总的来说，关联规则挖掘和频繁模式挖掘的提出、改进和拓展都是为了适应和满 足用户不断变化的需求。 一方面，为满足用户提高执行挖掘任务效率的要求，相关的改进算法和新的高效 算法不断被提出。为避免多次扫描数据库的高代价开销，部分算法将数据库中的数据 的排列方式由通常的水平方式改为垂直方式。该数据表示方式命名为垂直数据表示。 改进的垂直数据表示的高效频繁项集挖掘算法研究第l 章前言 例如，e c l a t 2 和d i f f s e t c 3 都是采用垂直数据表示的高效的频繁项集挖掘算法。 另一方面，为适应用户需求的不断变化。多种频繁模式挖掘被相继提出，如：最 大频繁项集挖掘 4 j 、频繁闭项集挖掘 5 j 、基于约束的频繁项集挖掘 6 等等( 它们的 具体定义将在2 2 详细介绍) 。各种频繁模式挖掘的研究出发点具体如表卜1 所示。 表1 - 1 各种频繁模式挖掘的研究出发点 频繁模式挖掘类型研究出发点 频繁项集挖掘获取事务记录中出现频繁率较大的项集。 最大频繁项集挖掘减少频繁项集的挖掘过程中产生的大量冗余项集。 频繁闭项集挖掘 减少频繁项集的冗余记录同时保证频繁项集信息的完整性。 基于约束的频繁项集挖掘通常用户需要具有特定性质的频繁项集。 压缩频繁项集挖掘由于在挖掘过程中难以确定合适的最小支持度导致部分具 有较大价值的项集信息的丢失。 最k 频繁闭项集挖掘用户对频繁闭项集数量的需求往往不是巨大的。 1 2 研究目的和内容 本质上，以频繁项集挖掘为核心的关联规则挖掘的提出和应用是为了满足用户从 理海量数据中项之间的有趣关系这一需求。随着数据的海量激增，用户关于提高挖掘 任务的执行效率和完善相关功能的需求日趋迫切。因此，本文的主要研究目的是进一 步提高执行频繁项集挖掘任务的效率以及完善相关的功能，以致能进一步适应和满足 用户的需求。 为实现上述的研究目的，本文以下几个方面进行了相关的研究工作： 1 ) 分析了各种频繁模式挖掘的研究现状，并了解关联规则的特点、功能； 2 ) 研究了a p d o r i 、f p g r o w t h 、e c l a t 和d i f f s e t 这四个经典频繁项集挖掘算法的 设计、实现和性能； 3 ) 重点分析和研究了垂直数据表示的特性以及t i d s e t ( 或d i 凰e t ) 的规模对e c l a t ( 或d i 疗s e t ) 算法效率的影响，并结合t i d s e t 和d i f f s e t 这两种垂直数据表示方法的优 点提出采用h y b i r d s e t 垂直数据表示的h y b i r d s e t 算法。 4 ) 重点分析了频繁项集的固有性质和计算候选集支持度计数所需开销之间的关 系。并根据这些特点提出h y b i r d s e t 算法的改进算法h y b i r d s e t + 。 2 改进的垂直数据表示的高教频繁项集挖掘算法研究 第1 章前言 5 ) 重点分析了挖掘结果中存在的与矛盾或无效规则相关的频繁项集，并根据相 关度和频繁项集之间的关系提出相应的功能改进算法一d h y b i r d s e t 。 1 3 本文的主要贡献 实现频繁项集的高效挖掘和迸一步完善其功能是本论文主要任务。在现有的相关 研究成果的基础上，本文进行了与频繁项集挖掘相关的研究工作并取得了一些研究成 果。其中，本文最主要的贡献有以下三个方面： 1 ) 提出基于e c l a t 和d i f f s e t 的改迸算法一h y b i r d s e t 。它结合了e c l a t 算法和 d i f f s e t 算法的优点，采用h y b i r d s e t 垂直数据表示存储项集的相关信息，而且充分利用 交集和差集操作计算候选项集的支持度计数。实验证明，与e c l a t 和d i f f s e t 等算法相 比较，h y b i r d s e t 算法在分析不同的数据集和最小支持度取值不同的条件下都表示出良 好的性能。 2 ) 提出基于h y b i r d s e t 的性能改进算法一h y b i r d s e t + 。该算法根据频繁项集的 固有性质和计算候选集支持度计数所需开销之间的关系对h y b i r d s e t 算法进行相应的 改进。实验证明，h y b i r d s e t + 算法能进一步提高执行频繁项集挖掘任务的效率。 3 ) 提出基于h y b i r d s e t + 的功能改进算法一d h y b i r d s e t 。该算法根据频繁项集与 相关度之间的联系对h y b i r d s e t + 算法进行相应的修改，克服了频繁项集挖掘的结果中 存在与矛盾或无效规则相关的频繁项集这缺点。实验证明，在对真实数据的分析中 d h y b i r d s e t 算法能减少与矛盾或无效规则相关的频繁项集的生成。 1 4 本文的组织结构 本文的组织结构具体如下所述： 本章主要介绍了本文的研究背景、目的、内容以及主要贡献。 第2 章详细阐述了频繁项集挖掘的相关概念和定义，并重点介绍了各种频繁模式 挖掘的主要研究成果和详细评析了f p - g r o w t h 、e c l a t 和d i f f s e t 等经典频繁项集挖掘算 法。 第3 、4 与5 章是本文的重点研究内容和成果。 第3 章阐述了本文在e c l a t 和d i f f s e t 的基础上提出的改迸算法一h y b i r d s e t 算法。 实验证明，在多个数据集和多个最小支持度的条件下h y b r i d s e t 算法都能达到e c l a t 和 改进的垂直数据表示的高效频繁项集挖掘算法研究第1 章前言 d i 脓t 算法的最优值。 第4 章在第3 章的基础上提出h y b i r d s e t 算法的改进算法一h y b i r d s e t + 算法。该 算法根据频繁项集的相关信息和计算候选集的支持度所需开销之间的关系进一步提 高执行频繁项集挖掘任务的效率。 第5 章在第4 章的基础上提出h y b i r d s e t + 算法的改进算法d h y b i r d s e t 算法。 该算法能减少与矛盾或无效规则相关的频繁项集的生成，从而减少此类规则对用户的 误导。通过对真实数据的测试验证了d h y b i r d s e t 算法新增功能的实用性。 第6 章是全文研究工作的总结与展望。这章对全文内容作了概括性的总结，并指 出本文存在的不足和进一步的研究方向。 4 改进的垂直数据表示的高效频繁项集挖掘算法研究 第2 章频繁模式挖掘概述 第2 章频繁模式挖掘概述 2 1 关联规则挖掘 关联规则c l 7 最早由a g a r w a l 等提出，并应用于购物篮分析。关联规则挖掘寻找 给定数据集中项之间的有趣关系。随着被收集和存储数据的高速增长，许多业界人士 对于从他们的数据库中挖掘关联规则的兴趣愈加浓厚。 定义2 一l ：七一项集 一个商品或者一个属性称为一个项目。多个项目的集合称为项集。设，为数据库 d 中全体项目的集合，集合x = ，j 2 ，t ( x ，l x l = 七) 称为k 一项集。 定义2 - 2 ：事务 一个事务( 或称一条记录) ，是形如 t i d ，x 的二元组。其中，t i d 是它唯一的标 识符，j 为项目集。设a 是一个项集，事务r 包含a 当且仅当爿r 。 要挖掘的数据集或者数据库t i d 是条事务的集合，一条事务也称为一条记录， 为数据集或数据库t i d 的记录总数。 定义2 - 3 ：支持度计数和支持度 数据库t d b 中包含项集x 的事务的数目称为项集x 的支持度计数，记为 c o u n t ( 1 。 项集x 的支持度是项集x 在数据库记录中的出现频率。记为 s u p p o r t ( x ) = c o u n t ( x ) in 。 定义2 - 4 ：频繁项集 如果项集的支持度不小于用户给定的最小支持度阈值( m i ns u p ) ，则称其为频繁项 集( f r e q u e n t t e m s c t ) ，简单频集。该阈值可以由用户或领域专家设定。 其中，最小支持度阙值对应的支持度计数称为最小支持度计数( m i n _ c o u n t ) ， m i n _ e o u n t = m i n _ s u p m r 。 改进的垂直数据表示的高效频繁项集挖掘算法研究第2 章频繁模式挖掘概述 定义2 5 ：频繁项集挖掘 频繁项集挖掘是指从事务记录中获取全部出现频率不小于预定义的最小支持度 阈值的项集。 定义2 - 6 ：关联规则 关联规则是形如a b 的蕴涵式，其中a c i ，b c ，并且a n b = o 。a 称为 关联规则的前件或前提，b 称为关联规则的后件或结论。 定义2 - 7 ：置信度 关联规则ajb 的置信度是指数据库t i d 中包含a 的事务同时也包含b 的百分 比是f 。即： c o n f i d e n c e ( a 口) ：s u p p o r t ( a u b ) x1 0 0 ( 2 1 ) s u p p o r t ( 爿、 支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则在整个 数据集中的统计重要性，后者用于衡量关联规则的可信程度。 一般来说，只有支持度和置信度均较高的关联规则才可能是用户感兴趣、有用的 关联规则，即强关联规则 1 | 。 定义2 - 8 ：关联规则挖掘 关联规则挖掘是从大量数据中寻找项之问的有趣关系的过程。在挖掘关联规则 前，必须预设定最小支持度闽值( m i n _ s u p ) 和最小置信度阂值( m i n _ e o n f ) 。再在数据库 记录r 中获取全部支持度和置信度分别不小于m i n _ s u p 和m i n _ e o n f 的关联规则，即关 联规则a jb 满足以下两个条件： ( 1 ) s u p p o r t ( a j b l m i n _ s u p ； ( 2 ) c o f i d e n c e ( a = b 1 m i n _ c o n f 总的来说，关联规则的挖掘的主要过程 1 ，8 】如下所述： 步骤一：找出所有频繁项集。这些项集出现的次数必须不小于预定义的最小支持 计数。 步骤二：由频繁项集产生强关联规则。这些规则的支持度和置信度必须不小于最 小支持度阈值和最小置信度阈值。 6 改进的垂直数据表示的高教频繁项集挖掘算法研究 第2 章频繁模式挖掘概述 最后，得到的关联规则既满足最小支持度，又满足最小置信度。在这两个步骤中， 第二个步骤较为容易实现，而第一个步骤决定了整个求解过程的性能。现采用下面的 例子具体阐述实现关联规则挖掘的整个求解过程： 现从表2 - 1 中事务数据库记录r 中挖掘关联规则。其中，最小支持度和最小置信 度的阈值分别为0 4 和0 5 。 表2 - 1 事务数据库记录 事务项序号 记录 l 苹果，面包 2面包，牛奶 3饼干，牛奶 4咖啡，面包 5 面包，牛奶 由相关记录可知；项集 面包 ，f 牛奶 和f 面包，牛奶 的支持度分别为0 8 、0 6 和0 4 。则根据定义知： 项集 面包 、【牛奶 和 面包，牛奶 都是频繁项集，且有如下两个相关的强关联 规则； ( 1 ) 面包 f 牛奶 ： ( 2 ) f 牛奶 令( 面包 以上的两个强关联规则的含义分别为： 强关联规则( 1 ) ：如果某一事务中包含“面包”，则它同时包含“牛奶”的可能 性为0 5 ，并且所有事务中有0 4 包含了两者； 强关联规则( 2 ) ：如果某一事务中包含“牛奶”，则它同时包含“面包”的可能 性为0 6 7 ，并且所有事务中有0 4 包含了两者。 2 2 频繁模式挖掘 近十多年来，众多数据挖掘专家进入了频繁项集挖掘这一研究领域，而且已经拓 展到其他频繁模式的研究并取得大量的研究成果。频繁模式挖掘的具体含义是指从事 务记录中获取全部出现频率不小于一个预定义的阈值的模式。 1 ) 频繁模式挖掘的研究方向 现阶段，频繁模式挖掘主要包括了以下的研究方向： 7 改进的垂直数据表示的高效频繁项集挖掘算法研究 第2 章频繁模式挖掘概述 ( 1 ) 频繁项集挖掘 1 ，7 9 j 。1 9 9 3 年，a g r a w a l 首先提出频繁项集挖掘，并将其应 用于购物篮分析。具体的分析结果能较直接地反映顾客的购买习惯中的显著特点，为 进一步发现蕴藏的购买行为模式提供了重要依据。其中，a p f i o f i 算法 1 0 ，1 1 是最有影 响的挖掘布尔关联规则频繁项集的算法。它主要基于“频繁项集的所有非空子集都必 须是频繁项集”【1 2 】这一性质设计而成。随后，e c l a t 算法【z 、h m i n e 算法【1 3 1 、 f p g r o w t h 算法 1 4 等更高效的算法被相继提出。 ( 2 ) 最大频繁项集挖掘 4 1 5 1 。一般情况下，频繁项集挖掘得到的频繁项集数量 非常庞大。由于任一频繁项集的子集都是频繁的，所以结果当中相当大的一部分属于 冗余信息。为减少冗余频繁项集的数量，1 9 9 8 年，r j b a y a r d o 等提出了最大频繁项 集挖掘这一任务。最大频繁项集挖掘任务的执行结果中不存在任一频繁项集是另一频 繁项集的子集或超集的情况，从而有效地减少了冗余信息。 ( 3 ) 频繁闭项集挖掘 5 l6 j 。频繁闭项集挖掘是基于最大频繁项集挖掘在减少冗 余信息的同时却未能保证频繁项集信息的完整性这一缺点提出的。由于最大频繁项集 的结果中的任一频繁项集的信息只能确定它的子集是频繁项集，而没有包含这些子集 的支持度的具体值。为了弥补这一缺点，n p a s q u i e r 等在1 9 9 9 年提出了频繁闭项集挖 掘这一任务。与最大频繁项集相比较，频繁闭项集只包含了其所有具有相同支持度并 处于相同事务项的频繁子集的信息。因此，频繁闭项集挖掘在减少频繁项集的冗余记 录的同时保证频繁项集信息的完整性。其中，c h a r m t 7 1 j g lc l o s e t e t a 算法是较为 高效的频繁闭项集挖掘算法。 ( 4 ) 基于约束的频繁项集挖掘 6 ，1 9 。在绝大多数频繁项集( 或最大频繁项集) 挖 掘过程中，与所处理的数据相关的专业知识并未考虑在内，从而在结果中会产生许多 用户并不感兴趣的项集( 或模式) 。1 9 9 5 年，y f u 等提出约束频繁项集挖掘这一任务 以满足在不同情况下用户对频繁项集的具体需要。规则约束大致可以分为五类：反单 调的、单调的、简洁的、可转变的和不可转变的。随后，大量学者进行了相关的研究， 并取得相当多的成果 2 0 ，2 l 】。 ( 5 ) 压缩的频繁模式挖掘 2 羽和最k 闭频繁项集挖掘c z s 3 。2 0 0 0 年，j ，p e i 等提 出了压缩的频繁模式挖掘，最小支持度由一个定值改为一个范围，从而避免了部分有 8 改进的垂直数据表示的高效频繁项集挖掘算法研究第2 章频繁模式挖掘概述 较大价值的项集的的信息因没选取合适的最小支持度而在挖掘过程中丢失。 在多种频繁模式挖掘中，挖掘结果中的频繁项集( 或模式) 都必须满足最小支持 度的要求。然而，在实际上用户难以确定一个合适的最小支持度。因此，在2 0 0 5 年 j w a n g 等提出了一个新的挖掘任务：挖掘长度不小于某定值( m i n _ 1 ) - 的支持度最大 的k 个频繁闭项集，其中k 和r a i n1 分别是用户按照实际需求设定的目标频繁闭项集 的数量和最小长度。与此同时，他们还设计了一种基于f p t r e e 的高效的t f p 2 3 算法 用以求解。 2 ) 频繁模式挖掘示例 某种意义上，上述的多种频繁模式挖掘是一个纵向发展过程。为进一步说明这些 频繁模式挖掘的不同之处，现根据表2 - 2 中的事务记录阐述各种频繁模式挖掘。 ( 1 ) 频繁项集挖掘。在最小支持度计数为3 的条件下，可以从表2 2 的事务记录 中缛到 a b ：7 ， a c ：6 ， a b c d ：3 等数十个频繁项集。 表2 - 2 事务数据库部分记录 事务项序号记录 o l a d ，e ，g 0 2a b 0 3 a b 。c 。e ，h 0 4 a b ，c 。d 0 5 a ，b ，c ，d ，e i 0 6a ，b c 0 7 a ，b ，c ，d ，e i 0 8 a b ，c ，e ( 2 ) 最大频繁项集挖掘。在最小支持度计数同样为3 的条件下，项集 a b ：7 ， a c ：6 ，( 缸：6 与 a b c ：6 ) 都是频繁项集。因为项集( a b ：7 、 a c ：6 和 酏：6 都是频 繁项集 a b c ：6 的子集，所以最大频繁项集挖掘的结果中只保存了频繁项集 a b c ：6 的 信息。 ( 3 ) 频繁闭项集挖掘。相对于最大频繁项集挖掘，频繁闭项集挖掘的结果中会 存在一个频繁项集是另一个频繁项集的子集或超集的情况。在最小支持度计数同样为 3 的条件下，频繁闭项集挖掘的结果中存在频繁项集 a b c ：6 和 a b ：7 的信息，其中项 集 a b c ：6 ) 是项集 a b ：7 的超集。另外，可根据频繁项集 a b c ：6 推导出它的频繁子集 9 改进的垂直数据表示的高教频繁项集挖掘算法研究第2 章频繁模式挖掘概述 a c ：6 ) 和 b c ：6 的信息。 ( 4 ) 基于约束的频繁项集挖掘。相对与其他频繁模式挖掘，该模式挖掘增加了 用户确定的约束条件。 假设表2 - 2 中的每一个项集都有对应的价值，具体如表2 3 所示。设约束条件为： 项集的平均值不小于2 5 。易知，事务项数据库记录中有项集 幻 和 a b e ，则： 项集 b c 的平均值a v g ( b e ) = ( 1 0 + 3 0 ) 2 2 5 ，不满足约束条件；然而，该项集的 超项集 a b c 的平均值为a v g ( a b c ) = ( 4 0 + 1 0 + 3 0 ) 3 2 5 ，满足约束条件。 表2 - 3 各项集的价值列表 ( 5 ) 最k 闭频繁项集挖掘。区别于上述的频繁模式挖掘，它不需要设定最小支 持度。假设对表2 2 中的事务数据库记录进行挖掘，且挖掘任务是获取长度不少于2 出现频率最高的4 个闭频繁项集。则得到的挖掘结果为：f a b ：7 ，a b e ：6 ，a d ：4 a b c d ：3 ，a e ：3 。 2 3 当前频繁项集挖掘算法的分析 2 3 1a p r i o r i 算法 1 ) a p r i o r i 算法原理 a p f i o f i 算法是最有影响的挖掘布尔关联规则频繁项集的算法。它基于频繁项集的 所有非空子集必定是频繁项集这一性质设计而成。该性质的具体如下所述： 如果项集彳不满足最小支持度阈值m n s u p ，则a 不是频繁的，即 e ( a ) _ m i n s u p c w ) f = f u r z = 霉o r ，其中巧初始为空； i fz 0 ，调用函数e c l a t ( t , ) 。 3 ) e c l a t 算法示例 现采用如下例子进一步说明e c l a t 算法的算法步骤。被分析的数据如表2 - 6 所示， 且展小支持度计数为3 。具体过程如图2 - 4 所示( 画删除线的项集为非频繁项集) 。 表2 6 简单的示例数据库 事务项序号 记录 1a ，c ，d ，e ，f 2a ，b ，c ，d ，e 3b d 4b ，c ，f 5a ，c ，d ，e 。f 6k 图2 - 4e c l a t 算法挖掘示例 1 7 改进的垂直数据表示的高效频繁项集挖掘算法研究第2 章频繁模式挖掘概述 第一步：扫描数据库，获取全部卜项集的t i d s e t 以及对应的支持度计数，非频繁 卜项集的信息不再保留。例如卜项集( k 的t i d s e t 为t ( k ) = 6 ，即它的支持度计数为 i t ( k ) l = l 。易知，全部频繁卜项集的集合l 为：l = a ，b ，c ，d ，e ，f 。 第二步：对l 中的任一个频繁卜项集x ，它依次与其后面的项目连接得到新的 候选集。例如项集 a ) 和它后面的5 个项集分别连接得到新的候选集 a b ， a e ， a d ， a e ， a f 。新的候选集的t i d s e t 等价于它两个不同的子集的t i d s e t 的交集。例如： t i d s e t ( a b ) = t i d s e t ( a ) nt i d s e t ( b ) 将新的候选集组成一个集合c = a b ，a c ，a d ，l i e ，a t ) 。由于项集 a b 和 a f 的支 持度计数小于3 ，则项集 a b 和( a f 以及它们的超集都不可能是频繁的。因此，将在项 集 a b 和 a f 从集合c 中剔除。此时，c = a e ，a f , a n l 。 若c 非空，重复第二步，直到集合c 为空或只包含一个元素，此时不能再产生新 的候选集，求解过程结束。 4 ) e c l a t 算法性能分析 与a p r i o r i 算法相比，e c l a t 算法具有以下优点： ( 1 ) 无需复杂的h a s h 数据结构； ( 2 ) 在生成候选项集后，不需再进行剪枝； ( 3 ) 扫描数据库次数较少，挖掘效率较高。 与f p g r o w t h 算法相比，e c l a t 算法占用的内存比较小 3 1 l 。 2 3 4d i f f s e t 算法 1 ) d i f f s e t 算法原理 d i f f s e t 算法 赞约】是根据e c l a t 算法处理稠密( 即项集的支持度计数平均值较大) 数据集时性能不高这一特性提出的。它的设计原理与e c l a t 算法基本一致。区别于e c l a t 算法，d i f f s e t 算法采用d i f f s e t 垂直数据表示t a o i 隙n 集相关信息和进行差集操作确 定项集的支持度计数。 改进的垂直数据表示的高教频繁项集挖掘算法研究第2 章频繁模式挖掘概述 2 ) d i f f s e t 算法描述 d i f f s e t 算法的具体执行步骤如下所述： 输入：事务项数据库t d b ，最小支持度阈值r a i ns u p 。 输出：所有的频繁项集f 。 算法： s t e p j ：扫描数据库一次，得到频繁卜项集e ，f = f u 最： s t e p2 ：d i f f s e t ( f 1 ) ： f o ra l l 五e 月d o f o r a l lx i r tj id o 产生新的候选项集r = 五u d i f f s e t s ( r ) = d 移a s ( x j 、一d i f f s e t s ( x , ) ； c o u n t ( r ) = c o u n t ( x , ) 一id i f f s e t s ( r ) l ； i f ( c o u n t ( r ) m i n _ s u p g v ) f = f u r ，z ：= 互u r ，其中z 初始为空； i f z o ，调用函数d i f f s e t ( t , ) ： 3 ) d i f f s e t 算法示例 现采用如下例子进一步说明d i f f s e t 算法的算法步骤。假设给定如表2 6 所示的事 务记录，现采用d i f f s e t 算法找出其中全部频繁项集。其中最小支持度计数为3 。挖掘 任务的具体执行过程如图2 5 所示。 d i i f s e t 算法的设计原理与e c l a t 算法基本一致。最大的区别在于项集信息的存储 方式以及对应的计算支持度计数所采用的操作。d i f f s e t 算法采用差集操作，项集的支 持度计数的具体计算方法如下所述： 设c o u n t ( p ) 表示项集p 的支持度计数，i d i f f s e t ( p ) i 为项集p 对应的差集的元素 个数。则项集的支持度计数的计算公式如下： c o u n t ( p x ) = c o u n t ( p ) - id i f f s e t ( p x ) i ( 3 一1 ) 1 9 改进的垂直数据表示的高效频繁项集挖掘算法研究第2 章频繁模式挖掘概述 c o u n t ( p x y ) = c o u n t ( p x ) 一id i f f s e t ( p x y ) i ( 3 2 ) 对于图2 5 的d i f f s e t 算法示例，有： d i f f s e t ( a ) = 3 ，4 ，6 ，c o u n t ( a ) = 6 - 3 = 3 ； d i f f s e t ( a c ) = d i f f s e t ( c ) 一d i f f s e t ( a ) = 3 ，6 一 3 ，4 ，6 = a ) ； c o u n t ( a c ) = c o u n t ( a ) - i d i f f s e t ( a c ) l = 3 0 = - 3 ：则可确定项集 a c ，为频繁项集。 图2 - 5d i f f s e t 算法挖掘示例 4 ) d i f f s e t 算法性能分析 e c l a t 算法和d i f f s e t 算法在设计、实现等方面是非常相近的。与其他类型的算法 相比，具有相近的性能特点。与a p f i o d 算法相比，e c l a t 算法和d i f f s e t 算法具有以下 优点： ( 1 ) 无需复杂的h a s h 数据结构； ( 2 ) 在生成候选项集后，不需再进行剪枝； ( 3 ) 扫描数据库次数较少，挖掘效率较高。 与f p g r o w t h 算法相比，e c l a t 算法占用的内存比较小 3 l j 。 另一方面，e c l a t 算法和d i f f s e t 算法的最大区别在于：处理较为稠密的数据集时 e c l a t 算法的性能较差，d i f f s e t 算法的性能较好；处理稀疏的数据集时，则反之。 改进的垂直数据表示的高教频繁项集挖掘算法研究 第2 章频繁模式挖掘概述 2 4 频繁模式挖掘的发展趋势 随着数据挖掘技术领域的进一步扩大，挖掘的数据源从一般的关系数据库结构扩 大到多种结构化数据、半结构化和非结构化的数据。另一方面，由于序列、树和图等 数据结构可以广泛地反映了很多情形中的数据关系，因此，频繁序列模式挖掘 1 】、频 繁子树挖掘 1 和频繁子图挖掘 1 相继被提出。 1 ) 频繁序列模式挖掘 序列模式挖掘是指挖掘相对时间或其他模式出现频繁高的模式。由于很多商业交 易、电传记录、天气数据和生产过程都是时间序列数据，在针对目标市场、客户吸引、 气象预报等的数据分析中，序列模式挖掘是很有用途的。 g s p 算法 3 2 是一个频繁序列模式挖掘的类a p d o n 算法。其主要思想同样是利用 多次迭代来计算数据库中的频繁序列模式。每一次迭代有两个步骤：产生序列模式候 选集；计算和选择频繁序列模式。与频繁项集的挖掘相似，g s p 算法有与a o f i o f i 算 法类似的瓶颈问题。随后，f r c c s p a n r 3 3 、p r e f i x s p a n 3 4 根据f p - g r o w t h 算法实现的高 效频繁序列模式挖掘算法被相继提出。 与频繁项集挖掘的发展方向类似，压缩的频繁序列模式挖掘 3 5 等其他序列模式 被相继提出。 2 ) 频繁子树挖掘 频繁子树挖掘的定义 如下所述： 给定有序标号树的数据库t d b 以及子树r ，r 的支持度定义为s ( r ) 爿p ( t ) l n i ， 其中p ( t ) 是t d b 中包含r 的树的棵数，是t d b 中树的棵数。所以，r 是频繁子 树当且仅当j ( r ) r a i n _ s u p 。这里的r n i n _ s u p 是用户指定的最小支持度阈值。频繁子 树挖掘就是要从数据库t d b 中找出所有频繁子树。 近年来，研究人员在频繁子树挖掘方面已经取得了不少成果。w a n g 和l i u a t 雨j 用a p d o r i 算法的思想，在有序树中挖掘频繁路径集；而m i y a l l 眦 矧等人则尝试用有 2 1 改进的垂直数据表示的高效频繁项集挖掘算法研究第2 章频繁模式挖掘概述 向生成测试的方法来挖掘频繁子树。随后，f r e q t 等算法 3 9 被相继提出。 3 ) 频繁子图挖掘 频繁子图挖掘的定义 如 如下所述： 给定图的数据库g d = g l i = o ，f ，栉 ，给定一个最小支持度阈值m i n _ s u p ，如果 子图g 与g i 子图同构，贝l j o ( g ，q ) - - 1 ，否则d ( g ，g f ) = o ，6 ( g ，g ) = o ( g ，q ) 。如果 g e g d 万( g ，q ) m i n _ s u p ，则g 是一个频繁子图。频繁子图挖掘就是从数据库g d 中找出所 有频繁子图。 为实现频繁予图挖掘的求解，a k i r oi n o k u e h i 等人最早将a p r i o d 算法思想应用到 频繁子图挖掘【4 ，并吸引了许多学者进入该研究领域。为设计出