（计算机软件与理论专业论文）基于矩阵的频繁项集挖掘算法研究.pdf

两叮矢乎 基于矩阵的频繁项集挖掘算法研究兰州大学硕士学位论文 摘要 关联规则是数据挖掘领域的一个重要分支，它反映的是大量数据中间内在的 关联联系，其目的是找出满足最小支持度和最小置信度要求的强关联规则。频繁 项集挖掘是关联规则挖掘的关键步骤，也是数据挖掘的热点和难点问题。可见， 频繁项集挖掘是一个具有重要理论意义和广阔应用前景的研究课题。 频繁项集挖掘算法研究。本文在对关联规则挖掘问题简述的基础上，深入地 探讨了典型的频繁项集挖掘算法a p r i o r i 和f p g r o w t h ，并关注了几种改进的频 繁项集挖掘算法，介绍了频繁项集挖掘问题的最新扩展。 基于矩阵改进频繁项集挖掘。本文提出了一种改进的基于矩阵的频繁项集挖 掘算法。该算法汲取了经典频繁项集挖掘算法的基本思想，引入了一种新的数据 结构：i m o f i 。该算法采用类似指针原理的间接寻址方式的索引技术，对位图模 式存储的候选项集矩阵进行了内部编码，使矩阵i m o f i 的元素不仅仅描述某个特 定的频繁项目在某事务中的出现，而且描述频繁项目下次出现时所在事务的序 号。结合辅助向量a v 的使用，算法避免了候选项集的重复存储，有效地压缩了 矩阵i m o f i 的存储代价。通过以上改进，该算法为快速搜索频繁项目集合提供了 非常有效的方法，从而提高了频繁项集挖掘的效率。 本文在n e t 环境下，用c 牾言实现了该算法，并令其与经典的频繁项集挖 掘算法进行了比较，发现该算法在短模式数据上具有良好的性能，并对该算法提 升挖掘性能的原因进行了归纳。 关键词：数据挖掘、关联规则、频繁项集挖掘 萄计r 虫害 基于矩阵的频繁项集挖掘算法研究兰州大学硕士学位论文 a b s t r a c t a s s o c i a t i o nr u l e si sa ni m p o r t a n tb r a n c ho fd a t am i n i n g i tr e f l e c t st h ei n n e r r e l a t i o n s h i po fa m a s so fd a t a i t sg o a li st of i n da l ls t r o n ga s s o c i a t i o nr u l e ss a t i s f y i n g m i n i m a ls u p p o r ta n dm i n i m a lc o n f i d e n c e f r e q u e n ti t e m s e t sm i n i n gi sn o to n l yt h e p r i m a r ys t e po fa s s o c i a t i o nr u l e sm i n i n g ，b u ta l s oa h o ta n dd i f f i c u l tp r o b l e mo fd a t a m i n i n g i ti so b v i o u st h a tf r e q u e n ti t e m s e t sm i n i n gi sa r e s e a r c hs u b j e c to fi m p o r t a n t t h e o r ym e a n i n ga n do f w i d eo u d o o kf o ra p p l i c a t i o n r e s e a r c ho nf 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 i nt h i sp a p e r ，b a s e do nt h eb r i e f s t u d yo fa s s o c i a t i o nr u l em i n i n g ，w et a k ea ni n - d e p t hs t u d yo nt y p i c a lf r e q u e n t i t e m s e t sm i n i n ga l g o r i t h m s ，s u c ha sa p r i o r ia n df p g r o w t h t h e nw ep a ya t t e n t i o nt o s o m ei m p r o v e df 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 ，i n t r o d u c el a t e s te x t e n d e dp r o b l e m o ff r e q u e n ti t e m s e t sm i n i n g i m p r o v i n gf 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 mb a s e do nm a t r i x t h i sp a p e rp u t s f o r w a r da l li m p r o v e da l g o r i t h mb a s e do nm a t r i xf o rm i n i n gf r e q u e n ti t e m s e t s t h e a l g o r i t h ma b s o r b st h el o # co fc l a s s i c a la l g o r i t h m s ，i m p o r t san e wd a t as t r u c t u r e ： i m o f i t h ea l g o r i t h mn s e si n d i r e c ta d d r e s s i n gi n d e xt e c h n i q u es i m i l a rt op o i n t e rt o m a k eb i t m a pm a t r i xf i l l e dw i t hf r e q u e n ti t e m sb ei n n e rc o d e d t h ee l e m e n t so f m a t r i x i m o f ia r em a d et od e s c r i b et w om e a n i n g ：o c c u r r e n c eo fs o m ef r e q u e n ti t e mi na c e r t m nt r a n s a c t i o na n dt h eo r d e ro ft r a n s a c t i o ni nw h i c hs o m ef r e q u e n ti t e mn e x t a p p e a r s w i t ha vb e i n gu s e d ，t h ea l g o r i t h mm a k e sc a n d i d a t es e t sv o i da p p e a r i n g r e p e a t e d l y ，c o m p r e s s e st h es t o r a g ec o s to fi m o f i b yt h e s ei m p r o v e m e n ta b o v e ，t h e a l g o r i t h mp r o v i d e sav e r ye f f e c t u a lm e t h o dt or a p i d l ys e a r c hf r e q u e n ti t e m s e t s ， c o n s e q u e n t l yg r e a t l ye n h a n c e se f f i c i e n c yf o rm i n i n gf r e q u e n ti t e m s e t s t h i sa l g o r i t h mb r o u g h to u ti nt h ep a p e ri sc o d e dv i ac # l a n g u a g ea n dr i m s o n n e tf r a m e w o r k a f t e rc o m p a r i n gt h ea l g o r i t h mw i t hc l a s s i c a la l g o r i t h m s ，w e f i n dp r e d o m i n a n tp e r f o r m a n c ei ns h o r tp a t t e r n ，s u m su pt h er e a s o n sf o ru p g r a d i n gt h e m i n i n gp e r f o r m a n c e 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 r e q u e n ti t e m s e t sm i n i n g 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发 表的成果、数据、观点等，均已明确注明出处。除文中已经注明 引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究成果做出重要贡献的个人和集体，均已在文中以 明确方式标明。 本声明的法律责任由本人承担。 论文作者签名： 玉这逡日期：芝z ! 么 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：王噬超导师签名： 睁一：出否 皙，叶矢乎 基于矩阵的频繁项集挖掘算法研究 兰州大学硕士学位论文 1 1 研究背景 第一章绪论 随着人类社会步入信息时代的速度加快，人们更加迫切地需要掌握大量的知 识。知识是种概念、规则、规律和模式【，它不像数据和信息那样具体，但是 它却是人们一直不懈追求的目标事实上，人们把数据看作形成知识的源泉一 般地讲，人们从海量的数据中抽取出信息，利用信息来形成和验证知识，同时又 不断地利用知识来获得新的信息。因此，随着信息技术的发展，特别是计算机存 储技术和网络技术的发展人们收集数据的速度加快了，获取数据的范围扩大了， 存储数据的容量提高了。从而产生了“数据过剩而信息贫乏”的尴尬现象，原因 正是人们缺乏获取有效信息和知识的手段于是，数据挖掘技术应运而生。 数据挖掘( d a t am i n i n g ) 是指从大量的数据中提取对决策有潜在价值的、 隐含的、先前未知的知识的高级处理过程。其中，具有辅助决策价值的知识是数 据挖掘的目标；隐含性、未知性是知识本身固有的特点；数据可能是有噪声的、 不完全的和异构存储的，是数据挖掘面临的现实困难。数据挖掘技术自从2 0 世 纪8 0 年代被提出来后，便以一种全新的概念改变着人类利用数据的方式，被称 为未来信息处理的骨干技术之一。就目前观点看，数据挖掘是一个多学科的交叉 研究领域，它融合了数据库技术、人工智能理论、机器学习理论、统计学、面向 对象方法、高性能计算、分布式计算以及数据可视化等最新技术的研究成果。 数据挖掘根据采用挖掘算法的不同可以分为3 种类型：关联规则分析、分类 分析、聚类分析。其中关联规则分析又称为关联规则挖掘( a s s o c i a t i o nr u l e s m 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 ) 。相对于第个子问题而言，第二个子问题相对 简单一些，可以利用已知项集的支持度信息，直接通过计算置信度枚举出所有强 关联规则，并且内存、i o 以及算法效率改进余地不大，因此挖掘关联规则问题 的整体性能主要由频繁项集挖掘问题决定。 1 9 9 3 年，a g r a w a l l 2 1 等通过研究顾客交易数据库中项集间的关系提出关联规 则分析问题。从那时起，频繁项集挖掘问题的研究就一直是关联规则分析研究领 域的难点和重心，大部分的研究工作都围绕频繁项集挖掘问题开展。同时，频繁 项集挖掘方法并不只局限于挖掘关联规则，还可以广泛应用于相关性分析、孤立 点分析、分类和聚类等多种数据挖掘任务和入侵检测、序列模式、w e b 挖掘等多 种数据挖掘应用和数据分析处理任务中p 】1 4 j 。 综上所述，频繁项集挖掘问题是一个具有重要理论意义和广阔应用前景的研 究课题，而且受到理论界和产业界的普遍重视。近几年来，频繁项集挖掘问题在 数据库方向的研究和应用领域已经成为一个公认的重要研究方向 1 2 主要工作及其新意 本文在研究关联规则挖掘理论的基础上，对频繁项集挖掘算法进行了认真的 分析探讨，介绍了一些改进的频繁项集挖掘算法以及频繁项集挖掘的扩展问题。 在此基础上，本文重点研究了矩阵在挖掘算法中的应用，并完成了一些有新意的 研究工作，具体包括如下几个方面： l 、本文引入了一种新的数据结构i m o f i 矩阵及其辅助结构a v 向量。矩阵 i m o f l 用来逐行存储每条事务中的候选项集，并令频繁项目按照支持度由大及小 的次序排列。矩阵i m o f i 的元素不仅仅描述某个特定的频繁项目在某事务中的出 现，而且通过内部的编码方案描述频繁项目下次出现时所在事务的序号，为快速 搜索频繁项目集合提供了非常有效的方法，从而提高了频繁项集挖掘的效率。结 合辅助向量a v 的使用，算法避免了候选项集的重复存储，有效地压缩了矩阵 i m o f l 的存储代价。 2 、本文提出一种改进的基于矩阵的频繁项集挖掘算法f i a v b o l 。算法主要 实现了快速挖掘频繁模式，具体步骤是：创建i m o f l 的矩阵结构，令其存储频繁 项目和候选项集：建立辅助向量a v ，令其记录不重复的候选项集数目：为i m o f l ：暂叶虫拿 基于矩阵的频繁项集挖掘算法研究兰州大学硕士学位论文 矩阵建立内部索引，实现快速遍历候选项集队列；最后，通过i s o f i 矩阵和辅助 向量a v 从候选模式中挖掘出所有频繁项集。 3 、本文在n e t 环境下，用c # 语言实现了该算法，并令其与经典的频繁项集 挖掘算法进行了比较，发现该算法在短模式数据上具有优越的性能，并对该算法 提升挖掘性能的原因进行了归纳。 1 3 本文的组织结构 第一章：绪论。首先介绍了本文研究工作的背景，接着重点介绍了主要研究 工作的内容以及成果和创意之处。 第二章：频繁项集挖掘算法研究。首先介绍了关联规则挖掘问题的概念，详 细描述了关联规则挖掘问题，并给出了相关术语的定义。在此基础上，重点研究 了经典的频繁项集挖掘算法，介绍一些优秀的改进算法，并对最大频繁项集挖掘 问题和封闭频繁项集挖掘问题进行了简单描述。 第三章：基于矩阵改进频繁项集挖掘算法。本章提出了一种新的改进的基于 矩阵的频繁项集挖掘算法- f i m a b o i ，详细阐述了算法的设计思路、数据结构、 算法描述以及具体实现，并通过具体的实例讲解算法的演算过程。最后，将该算 法与经典的频繁项集挖掘算法进行性能比较，得出结论，并分析原因 第四章：总结和展望。总结本论文进行的研究工作，并对下一步的工作进行 展望 ；萄，叶虫害 基于矩阵的频繁项集挖掘算法研究兰州大学硕士学位论文 第二章频繁项集挖掘算法研究 频繁项集挖掘问题产生于关联规则挖掘问题，是关联规则分析过程的重要组 成部分，它的执行效率决定了关联规则分析过程的主要效率。同时，频繁项集挖 掘并不局限于挖掘关联规则，还可以广泛应用于相关性分析、孤立点分析、分类 和聚类等多种数据挖掘任务以及序列模式、入侵监测、w e b 挖掘等多种数据挖掘 应用中。因此频繁项集挖掘问题的研究也受到其他数据库研究领域的广泛重视， 并逐渐在数据库研究领域形成了一个以频繁项集挖掘问题为重点的研究方向。 本章从关联规则挖掘问题下手，首先介绍了关联规则挖掘问题的概念和问题 的分解，从而引出频繁项集挖掘问题，并进行详细描述。然后，对h p r i o r i 算法 和f p - g r o w t h 算法进行了详细的分析。最后，介绍了几种高效频繁项集挖掘算法 以及频繁项集挖掘算法的扩展问题。 2 1 关联规则挖掘简述 2 1 1 关联规则的概念 关联规则挖掘又称为关联规贝j j 分析，其目标是发现大量数据中所有项目之间 有趣的联系或关系。关联规则挖掘寻找给定数据集合中项目之间的隐藏的关联关 系，描述数据之间联系的密切程度，是数据挖掘技术中的重要分支之一关联规 则挖掘的典型例子是购物篮分析，该过程主要通过分析顾客采购的不同商品间的 联系，发现顾客的购买行为模式，帮助零售商制定相应的营销策略，如商品货架 设计、库存安排以及根据购买模式对用户进行分类等。 实际上，关联规则用于描述在同一个事件中出现的不同项的相关性，更确切 的说，关联规则是通过量化的描述对象x 的出现对对象y 的出现有多大的影响。 关联规则挖掘问题的形式化描述具体如下： 定义2 1 ；项目集合i = i l ，i 2 ，i m ，其中i k ( k = l ，2 ，m ) 表示一个项目。 如果x _ c i ，集合x 被称为项集。当l x l - k ，则x 被称为k - 项集。 定义2 2 ；事务t 是一个二元组：t = ( t i d ，x ) ，其中，t i d 称为事务号，是 萄，叮虫亭 基于矩阵的频繁项集挖掘算法研究 兰州大学硕士学位论文 该事务唯一的标识，x i 是一个项集。 定义2 。3 ：事务数据库d 是i 上事务的集合；d = t l ，t 2 ，t n ) 其中t k ( k - 1 ，2 ，n ) 是一个事务。 定义2 4 ：项集x 的支持数是事务数据库d 中包含x 的所有事务数，记为： s u p p o r t ( x ) ，i l p s u p p o r t ( x ) = f t i d i ( t i d ，d d ，x _ c i ) l 。 定义2 5 ：项集x 的支持度是d 中包含x 的事务数占所有事务数的百分比， 即s u p p o r t ( x ) i d l 。 如果事务数据库确定，支持度和支持数的概念具有相同的度量意义，区别仅 仅在于数字的形式，前者是比例，后者是绝对数量。 定义2 6 ：一个关联规则是形如x _ “的蕴含式，这里x c i ，y c i ，并且 x n y - 彩其中涉及到支持度和置信度的使用，具体如下： ( 1 ) 规则x 剞在事务数据库d 中成立，具有支持度s ，则s 是d 中项集x u y 的支持度，为s u p p o r t ( xy ) ，即： s u p p o r t ( x = v ) = s u p p o r t ( x 忡e ( x u 耻照铲 ( 2 ) 规则x y 在事务数据库d 中具有置信度c ，其中c 是d 中同时包含x u y 的事务数占包含x 的所有事务数的百分比，它是条件概率p ( y i x ) ，记为 c o n f , z e n c e ( x j y ) ，即： confidence(xy)=p删玛=篙support( k ， 定义2 7 ：同时满足用户给定的最小支持度阈值和最小置信度阙值的关联规 则称为强关联规则。关联规则挖掘是在事务数据库中发现所有关联规则的过程。 定义2 8 ：给定事务数据库d 和最小支持度阈值九，果s u p p o r t ( x ) 芑九，则 项集x 被称为频繁项集，如果l x l - k ，则x 被称为频繁k _ 项集。 定义2 9 ：给定事务数据库d ，以及最小支持度阈值九，频繁项集挖掘是在事 务数据库d 中发现所有支持度满足最小支持度阈值九的所有频繁项集的过程。 ：菊_ r 矢乎 基于矩阵的频繁项集挖掘算法研究兰州大学硕士学位论文 2 1 2 问题的分解 由上述定义可知，关联规则挖掘问题可以分解为两个问题。 首先，发现满足最小支持阈值的频繁项集；然后从这些频繁项集中产生满足 最小置信度阈值的强关联规则。具体讲，挖掘关联规则主要包含以下二个步骤； 步骤o 发现所有支持度大于或者等于最小支持度阈值的项目集合，根据定 义，这些项集的被称作频繁项集； 步骤二：根据获得的频繁项集，产生相应的强关联规则，规则的形式为a = b 。 根据定义，这些规则必须大于或者等于最小置信度阕值。 在这两个步骤中，第二步相对简单一些。一旦在事务数据库中找出支持度满 足最小支持度阈值的所有项集，由它们可以直接产生所有强关联规则。具体过程 为；对于每个满足最小支持度阈值的项集x ，产生x 的所有非空子集；对于x 的 每个非空子集y ，给定最小置信度阈值6 ，如果：s u p p o r t ( x ) s u p p o r t ( y ) 6 ， 则输出规则y = ( 卜y ) 。由于这些规则由满足最小支持度阈值的项集产生，每个 规则都满足最小支持度，同时这些又满足最小置信度，因此这些规则都是强关联 规则。 综上所述，由于在关联规则挖掘过程的第一步中已经计算了所有频繁项集的 支持度，第二步过程是一个利用已知支持度直接枚举所有强关联规则的过程，其 实就是一个简单的统计和计算，因此挖掘关联规则过程的整体性能由第一步决 定。所以关联规则挖掘的核心是第一个过程，该过程称为频繁项集挖掘。 2 2 频繁项集挖掘的基本方法 频繁项集挖掘问题是关联规则挖掘的核心，其目的就是高效地找出事务数据 库中所有的频繁项集。本节重点介绍了两种经典的频繁项集挖掘算法：a p r i o r i 算法和f p g r o w t h 算法。 2 2 1a p ti o ri 算法 a p r i o r i l 5 博法最早来源于r a g r a w a l 等于1 9 9 3 年提出的a i s 阁算法，是公认 的解决频繁项集挖掘问题最早的、最有影响的算法。 ：暂，盱矢拿 基于矩阵的频繁项集挖掘算法研究兰州大学硕士学位论文 该算法的核心思想就是广度优先、逐层迭代。具体讲就是，频繁( k - 1 ) 项集 k l 用于搜索频繁k _ 项集h 。首先，找出所有的频繁1 项集，该集合记为l l 。 利用h 中各个集合做连接操作，从而找出频繁2 项集k ，继续利用k 寻找b ， 逐层迭代，直到找到所有的频繁项集。在执行算法思想的同时，利用频繁项集的 两个重要性剧q 进行有效的剪枝。 频繁项集的两个重要性质如下： 1 、频繁项集的所有非空子集都是频繁的。 根据频繁项集定义，如果项集x 不满足最小支持度阀值九，则x 不是频繁的， 即s u p p o r t ( x ) 九如果将项a 添加到x ，则结果项集( 即x u a ) 不可能比x 更频 繁出现。因此，x u a 也不是频繁的，即s u p p o r t ( x ua ) 的子女分支。如此以至，生成如图2 2 所示的f p - t r e e 。 在f p _ t r e e 上进行频繁项集挖掘的过程如下：由长度为1 的频繁项集( 初始 后缀模式) 开始，构造它的条件模式基( 一个“子数据库”，由f p l r e e 中与后 缀模式一起出现的前缀路径集组成) 。然后，构造它的( 条件) f p _ 伢e e ，并递归 地在该树上进行挖掘。模式增长通过后缀模式与由条件f p _ t r e e 产生的频繁项集 链接实现。 ；萄计矢亨 基于矩阵的频繁项集挖掘算法研究兰州大学硕士学位论文 从上面的分析可知，f p - g r o w t h 算法包含两个部分；一是生成f p - t r e e ；二 是在f p - t r c c 上进行频繁项集挖掘。其中生成f p - t r c c 的过程为； 1 、扫描事务数据库d 一次。生成所有频繁项的集合f 和这些频繁项的支持 度。对f 中的频繁项按支持度降序排序，结果为频繁项表l 2 、创建f p - t r e e 的根节点，以“n u l l 标记它。对于d 中每个事务t ，执行： 选择t 中的频繁项，并按l 中的次序排序。设排序后的频繁项表为 p i p ，其中p 是第一个元素，而p 是剩余元素的表。调用过程i n s c a _ t r c c ( p j p ，d 。该过程的 伪代码如图2 3 所示。 f f - g m w t h 算法中，在f p - t r c c 上进行频繁项集挖掘主要是通过调用 f p - g r o w t h ( f p - t r c c , n u l l ) 来实现。该过程的伪代码如图2 4 所示。 f p - c 蛐o w t h 算法将发现长频繁项集的问题转换成递归地发现一些短的项集， 然后连接后缀。它使用最不频繁的项作后缀，提供了好的选择性。该方法大大降 低了搜索开销。 f p c - t o w t h 算法采用f p - t r c c 存储结构，将事务数据库进行有效压缩，提高 了算法的空问效率。当数据库较小时，f f t r c c 可以基于内存实现，省去了多次 访问数据库带的i o 时问开销，大幅度提高了算法的时问效率。当数据库很大时， 构造基于内存的f p - t r c c 是不现实的。一种有效的改进是：首先将数据库划分成 蔺叶矢亭 基于矩阵的频繁项集挖掘算法研究兰州大学硕士学位论文 过程：i n s e r tt r e e ( p i p ，乃 输入：频繁r l a 为 p l r l ，f p t r e et 输出：f p - t r e * t 方法： l ：i f 树r 有子女n 使得n i t e m - n a m e = p i t c m - n a m c t h e n 2 ：n c o u n t = n c o u n t + 1 ： 3 ：e l s e 4 ： 创建一个新节点n ，n c o u n t ：= 1 ； 5 ： 将节点n 链接到它得父节点死 6 ： 通过节点链结构将其节点n 链接到具有相同i t e m - n a m e 的节点； 7 ： 8 ：i fp _ ot h e n 1 0 ：调用i n s c nt 皿n ) ； 图2 3f e - c 订o w t h 算法 过程：f p _ g r o w 出( t r e e ，a ) 使用f p - t m ，通过模式增长挖掘频繁项集。 输入：f p - t r t r e e ，节点a 输出：所有频繁项集f ( d ， ) 方法： l ：f f t r e e 含单个路径p t h e n 2 ： f o r 路径p 中节点的每个组合1 5f 3 ： 产生项集p u a ，其支持度等于o 中节点的最小支持度； 4 ： f ( d ， ) = f ( d ，a ) u 舻u a ) 5 ：e l s e f o r 在t r e e 的头部的a i 6 ： 产生一个项集p - 气u a ，s u p p o n ( 1 b ) - s u p p o r t ( a i ) ； 7 ： 构造b 的条件模式基； 8 ： 构造p 的条件f p - t r c et r e e j ； 9 ：i f t r e e ，- d 1 0 ： 用f p - g r o w t h ( t r e ，1 3 ) ； 1 1 ： 图2 4 频繁项集挖掘 1 2 蔺叶矢拿 基于矩阵的频繁项集挖掘算法研究 兰州大学硕士学位论文 投影数据库的集合，然后在每个投影数据库上构造f p t r e e 并挖掘它。该过程可 以递归使用，直到投影数据库的f p - t r e e 可以在内存中存储。 对f p g r o w t h 方法的性能研究表明：对于挖掘长的和短的频繁项集，它都是 有效的。f p g r o w t h 算法的不足之处是：构造条件f p - t r c c 的c p u 开销和存储开 销很大。 2 3 频繁项集挖掘算法介绍 近年来，先后出现了多种频繁项集挖掘算法。这些算法有基于a p r i o d 思想的 变种和改进l g l l l 4 1 l t s l l l ，也有对f p - t r e e 的变形和对f p - g r o w t h 的改进 1 1 7 1 1 蛆1 1 1 9 1 1 2 0 1 1 2 7 1 1 3 1 l 嘲，还有一些其它类型的算法1 2 1 l l l o l l l 3 1 1 2 5 x 2 6 1 2 s 1 1 2 9 f 3 0 1 。这些算法的 主要差别在于事务数据库在内存中的存储形式以及由此而产生的不同的挖掘策 略。本节介绍四种高效频繁项集挖掘算法，它们是：a p r i o r i t i d 、f p - g r o w t h 、 a f o p t 和m a h k 2 3 1a p r i o r i t i d 算法 a p r i o r i t i d 算法【1 1 】f 1 2 】是r a g r a a l 在a p r i o r i 算法基础上改进后提出的关联 规则挖掘算法。该改进算法的关键之处在于只在第一次计算卜项集的支持数时用 到了数据集d ，当k l 时使用数据集合c k 替代数据库d 。c i ( 中的元素形如： ，其中 x k 是用t i d 惟一标识的事务中包含的频繁b 项集的集合。当k = l 时， c l 【相当于数据库d ，不同的是将项目i 换作了由单个项目i 构成的项目集 i 当k l 时，c l 【由算法生成。c l 中元素的形式为 。 如果一个事务不包含任何k 维侯选项集，那么c k 中将不包含这个事务。这样， c k 中元素的个数将会少于数据库中的事务数。然而当k 值较小时，由于大部分事 务会包含几乎所有的k 维频繁项集，c k 中的数据量仍会很大。 2 3 2f p g r o wt h * 算法 f p g r o 科h 是1 1 t g g r a h n e 和j z h u l l 8 l 于2 0 0 3 年提出的，该算法基于f p - t r e e 结 构，是对f p g r o w t h 算法的变形和改进。在f p - g r o w l h 算法中，当由原始数据库构 萄叶矢孽 基于矩阵的须繁项集挖掘算法研究兰州大学硕士学位论文 建完第一棵f p t r e e 以后，大量的时间花费在f p - t r c c 的遍历以及新的条件f p t r e e 的构建上。大量的实验结果表明大约有8 0 的c p u 时间都耗费在了f p - t r e e 的遍历 上【1 8 l 。f p g r o w t h * 算法采用了一种新的数组技术改进t f p - t r e e 的操作性能，在 构建条件f p - t r e e 的同时构建个二维数组，使用该数组保存所有的二项集的支 持度计数。利用这项数组技术。使得每次递归时只需要扫描一遍f p t r e e ，这样 就提高了f p g d o w t h 算法的效率。另外，为了提高程序的效率f p g r o w t h * 算法还 使用了自己的内存分配技术，先申请一大块内存，然后程序执行中的内存申请都 来自于这一大块内存。 2 3 3a f o p t 算法 g u i m e i 【j u 等于2 0 0 3 年提出了a f o p t 算法【1 9 】，该算法在f p t r 的基础上 构造了一种简单紧凑的数据结构a f o p t - t r e e ( a s c e n d i n gf r e q u e n c yo r a t e d p r e f i xt r e e ) 。与f l - t r e 圮不同。在构建a f o p t - t r e e 结构时，频繁1 项集按支持 度递增的顺序排列。a f o p t 结构没有项头表，算法采用了自顶向下的扫描不仅 能够减少条件数据库的数目，而且能够降低对每一个条件数据库扫描的开销。在 a f o y r 算法中，使用数组存储稀疏型数据，使用a f o p t - t r e e 结构存储稠密型 数据，还使用了桶计数与动态排序技术。 2 3 4m a f i a 算法 m a f i a 算法( m a x i m a lf r e q u e n ti t e m s e ta l g o r i t h m ) 1 3 1 1 2 2 ，由d b u r d i c k 等人 于2 0 0 1 年提出，2 0 0 3 年又对算法进行了改进和补充。该算法不仅可以用来挖掘 最大频繁项集也可以用来挖掘全部频繁项集以及封闭频繁项集。m a f i a 算法利 用垂直位图的方法表示事务数据库，高效的压缩了数据库的存储空间，并能够快 捷的进行支持度计算。算法利用词典序子集合枚举树来描述搜索空间，该方法由 r y m 刚提出，被a g a r w a t 2 暑1 b a y a r d o l 2 1 】采用推广。同时，m a f i a 算法采用深 度优先的方法对搜索空间进行访问，祠用多种剪枝策略对搜索空阔进行潮减。另 外m a f i a 还采用动态排序、位图压缩、位图投影等技术提高算法的效率 ：暂i 叶矢乎 基于矩阵的频繁项集挖橱算法研究兰州大学硕士学位论文 2 4 频繁项集挖掘算法的扩展 随着频繁项集挖掘算法研究的不断深入，对频繁项集的关注也从经典频繁项 集挖掘，扩展到最大频繁项集挖掘和封闭频繁项集挖掘。最大频繁项集挖掘和封 闭频繁项集挖掘是经典频繁模式挖掘条件加强的结果。其算法也多从经典频繁模 式挖掘算法中发展而来 由此，频繁项集挖掘问题根据挖掘任务的不同目标可以划分为三类：所有频 繁项集挖掘、最大频繁项集挖掘和封闭频繁项集挖掘。全部频繁项集挖掘的目标 是找出事务数据库d 中所有的频繁项集合，因此全部频繁项集挖掘就是前面描 述分析的频繁项集挖掘。 本节对最大频繁项集挖掘问题和频繁项闭集挖掘问题进行简单的介绍。 2 4 1 最大频繁项集挖掘 定义2 1 0 ：事务数据库d 中，给定最小支持度阅值九，如果项集x 是频繁的， 并且对任意的项集y ，y3x ，均有s u p p o r t ( y ) ，即项集x 的所有超集都是 非频繁的，则x 被称为最大频繁项集( m a x i m a lf r e q u e n ti t e m s c t s ) 。d 中所有最 大频繁项集构成的集合记为m f i 。最大频繁项集挖掘任务的目的是找出d 中的 m f i 。 对于表2 1 中的事务数据库d ，项目集l = a ，b ，c ，d c ，e g ，设最小支持度 阈值为3 ，则频繁1 项集l l = a ，b c ，d ，e ，t 3 ，m f l = 协b ，c ，e 、 b ，母、 田 。 虽然最大频繁项集挖掘方法可以有效的提高频繁项集挖掘任务的性能，但存 在一个根本的缺陷：即挖掘出的所有最大频繁项集的同时，丢失了大部分频繁项 集的支持度信息。因为最大频繁项集挖掘方法只保留了最大频繁项集的支持度信 息，而没有保留由最大频繁项集的子集合构成的频繁项集合的支持度信息，甚至 在某些算法中，没有保留最大频繁项集的具体支持度信息，仅找出了所有的最大 频繁项集。这样必然导致关联规则产生时无法准确计算该规则的置信度当然， 从前面的分析中可知，频繁项集挖掘问题不仅局限于关联规则分析，它还广泛应 用到许多其他重要问题中，而这些应用中可能仅需要挖掘出最大频繁项集或所有 频繁项集，对频繁项集的具体支持度不做要求。 蒿叶矢乎 基于矩阵的频繁项集挖掘算法研究兰州大学硕士学位论文 2 4 2 封闭频繁项集挖掘 定义2 1 1 ：事务数据库d 中，项目集合i = i l ，i 2 ，i m ，d 中事务集合 t a ( t i d l ，t - ) ，( t i d 。，t 。) ，其中，( t i d t ，t t ) 表示一个事务对象，t i d 七是事务号，t - i 是一个项集。关系r t x i 是事务对象与项且集合间的二元关系。元组( t ，i ) e r 表 示事务对象t 具有属性i e i 。 定义2 1 2 ：公共模式映射f ：2 t 一2 1 ，f ( s ) = i e i l v t s g t , ( t i ) r ，称 f ( s ) 是事务集s c t 的公共模式。 定义2 1 3 ：投影映射g ：2 i 一2 t ，g = t t i v i e k c i , ( t ，i ) e r ，称g ( k ) 为项集k ci 的支持集。 定义2 1 4 ：2 i 上的闭包算子h = f 。g ，h = f ( g ( d ) 。项集x 是封闭的，当且仅 当h = x 。 定义2 1 5 ：事务数据库d 中，给定最小支持度阈值九，对于封闭的项集x ， 如果s u p p o r t ( x ) 乏九，则称项集x 为封闭频繁项集。事务数据库d 中所有封闭频 繁项集构成的集合记为c f i 。封闭频繁项集挖掘任务的目的是找出d 中的c f i 。 对于前面表2 1 中的事务数据库，有5 个事务，7 个项目，项目集i = a b ，c ， d c ，g ，设最小支持度阈值为3 ，则频繁1 - 项集合l = a ，b ，qd e ，f ， c f i = t a ：4 ， b ：4 ，协b ，c ，c ) ：3 ， b ，q ：3 ， d ：3 ，其中每个封闭频繁项集后边的 数字为该项集的支持度。 封闭频繁项集挖掘的概念由p a s q u i e r 等1 2 4 1 于1 9 9 9 年提出。由定义可知，任 一频繁项集合都是某个封闭频繁项集的子集，所以只要找到所有的封闭频繁项 集，就可以由它方便的找到所有的频繁项集。由于事务数据库d 中所有封闭频 繁项集的规模比频繁项集的规模要小几个数量级，因此可以将所有频繁项集的挖 掘问题转化为封闭频繁项集挖掘问题。另外，在挖掘过程中可以利用封闭频繁项 集的一些特性进行搜索空间的剪枝，因此封闭频繁项集挖掘的效率远高于挖掘所 有频繁项集。 与最大频繁项集挖掘方法相比，虽然事务数据库d 中封闭频繁项集的数目 ：暂，叶矢亭 基于矩阵的顿繁项集挖掘算法研究兰州大学硕士学位论文 会大于最大频繁项集的数目，但封闭频繁项集挖掘在找出事务数据库中所有的封 闭频繁项集的同时保持了项集所有的支持度信息，不会影响关联规则生成时规则 置信度的计算。因此，封闭频繁项集挖掘方法的研究受到数据挖掘研究和应用领 域的高度重视。 萄埘幺乎 基于矩阵的频繁项集挖掘算法研究兰州大学硕士学位论文 第三章基于矩阵改进频繁项集挖掘算法 本章通过对经典频繁项集挖掘算法的分析和对基于矩阵的改进算法研究，提 出了一种改进的基于矩阵的频繁项集挖掘算法，并且按照算法设计、算法描述、 程序实现和实验分析的思路完成了一系列的具体工作。其中，算法设计部分重点 讲解了算法的设计思路、数据结构和算法的伪码描述及其实例演示；算法的实现 部分简要列举了真实代码的核心部分；算法的实验和分析部分介绍了程序开发