基于项集优化重组的频繁项集发现算法

基于项集优化重组的频繁项集发现算法作者：王明，宋顺林，WANGMing，SONGShun-lin作者单位：王明,WANGMing(江苏大学,计算机科学与通信工程学院,江苏,镇江,212013;镇江市高等专科学校,电子信息系,江苏,镇江,212003)，宋顺林,SONGShun-lin(江苏大学,计算机科学与通信工程学院,江苏,镇江,212013)刊名：计算机应用英文刊名：JOURNALOFCOMPUTERAPPLICATIONS年，卷(期)：2010，30(9)被引用次数：0次参考文献(8条)1.TANPANG-NING.STEINBACHM.KUMARV.范明.范宏建数据挖掘导论20062.朱玉全.宋余庆.陈耿关联规则挖掘中增量式更新算法的研究2005(15)3.宋宝莉.覃征分布式全局频繁项目集的快速挖掘方法2006(8)4.孙英慧.孙英娟关联规则挖掘Apriori算法研究2009(4)5.宋威.高磊.李晋宏一种基于闭项集的无冗余关联规则挖掘方法2009(6)6.徐章艳.刘美玲.张师超.卢景丽.区玉明Apriori算法的三种优化方法2004(36)7.黄端琼.陈崇成.黄洪宇.樊明辉基于映射位集合的遥感图像关联规则挖掘2005(7)8.曾万聃.周绪波.戴勃.常桂然.李春平关联规则挖掘的矩阵算法2006(2)相似文献(10条)1.期刊论文李少年.孟志青.田媛一个基于频繁项集的时态数据挖掘算法-湘潭大学自然科学学报2003,25(3)研究了基于频繁项集的一个时态数据挖掘算法.首先,引进了基于频繁项集关联规则的概念,性质.然后,给出了基于时态约束关联规则的相关概念的定义和性质分析.最后,给出了在时态数据库中挖掘具有时态约束的最大频繁项集,并在此频繁项集生成时态关联规则的算法.由此导出了一种具有一定意义的时态关联规则挖掘方法,这种方法可以用于商品销售,股票价格等问题的知识发现,最后讨论了该算法在股票数据分析上的一个应用.2.学位论文李清峰数据挖掘中关联规则的频繁项集研究2007关联规则是数据挖掘的重要内容，是指挖掘发现大量数据中项目集之间有用的关联或相关联系。挖掘频繁项目集是关联规则等多种数据挖掘应用中的关键问题。然而，在挖掘中候选项目集产生的数量是很大的，尤其是存在大量强模式和(或)长模式的时候。本文在该课题的研究中提出三种高效挖掘最大频繁项集的算法：改进的Apriori算法、MMFI和MSMCA算法，减少计算量的开销。最终研究成果是MSMCA算法，该算法充分利用唯一已知的参数：最小支持数，进行最小逻辑组合运算挖掘最大频繁项集，大大减少了候选频繁项集，较大地提高了挖掘频繁项集的工作效率；理论分析和实验结果表明提出的算法是有效可行的。且该算法采用了统计计数，各频繁项集(最大频繁项集的所有子集)的支持数也能一并求出。同时，借助频繁树的思想向该问题的最优解决方案进行探索。3.会议论文包勇.卢加元.吴慧中基于频繁项集的降维在数据挖掘中的应用结合数据挖掘中的关联规则发现和粗集理论,提出一种基于频繁项集的数据降维方法.对数据集进行有效的降维处理,可提高后继数据处理的效率和质量.算法具有受数据集规模影响小,可扩充性好的优点.理论分析表明所提出的算法是有效可行的.4.学位论文梁碧珍目标频繁项集挖掘算法与应用研究2007随着信息技术尤其是网络技术的快速发展，人们收集、存储和传输数据的能力不断提高，导致数据出现了爆炸性增长。与此形成鲜明对比的是，对人们决策有价值的知识却非常匮乏。知识发现与数据挖掘正是在这一背景下诞生的一门新学科。关联规则是数据挖掘当前研究的主要模式之一，它用于确定数据集中不同域或属性之间的联系，找出有价值的多个域之间的依赖关系。频繁项集挖掘是生成关联规则的关键步骤，其效率问题是关联规则挖掘中的一大难点和热点。频繁项集挖掘可分为完全频繁项集挖掘、频繁闭项集挖掘和最大频繁项集挖掘三类。论文对关联规则的相关定义、频繁项集和最大频繁项集的挖掘方法进行了深入分析和研究。目标频繁项集挖掘是适应用户需要的一种频繁项集挖掘方法。TFP-树能有效过滤与目标模式无关的项和事物，将数据库中完整的、非冗余的信息压缩到一棵树上，使得搜索范围大大缩小；而基于SFP-树的频繁项集挖掘算法是一种较高效的算法，文章的第_部分和第三部分深入讨论了TFP-树和SFP-树结构，以及基于这两种树结构的频繁项集和最大频繁项集的挖掘算法，结合两者的优势，提出一种排序紧缩非冗余树FP-树，简称STFP-树，并提出基于STFP-树目标频繁项集算法STFP-grOWth和最大目标频繁项集挖掘算法STFP-Max，实验结果表明，算法是较高效的。随着Internet的发展和普及，网络安全问题同益突出，入侵检测是弥补防火墙的不足而提出的安全策略，文章的第四部分对关联规则挖掘算法在入侵检测中的应用进行探索性研究，将提出的目标频繁项集挖掘算法STFP-grOWth进行扩展，应用于入侵检测系统，通过KDDcup99实验数据对模型进行评估。5.期刊论文董朝贤频繁项集的数据挖掘算法及其实现-三门峡职业技术学院学报2007,6(2)Apriori算法是一种有效的关联规则挖掘算法,Apriori算法使用一种称作逐层搜索的迭代方法得到频繁项集,但是它产生大量的候选项集,还需要多次扫描数据库,每次对数据库的重复扫描非常冗长,大量的时间消耗在内存与数据库中的数据交换上.因此笔者引入了一种不产生候选项集的频繁项集挖掘算法--FP-growth算法,并对FP-growth算法的相关性质、实现作以介绍.6.学位论文姜晗关联规则的精简方法研究2007数据挖掘是指从大量数据中提取或“挖掘”知识。关联规则是数据挖掘当前研究的主要模式之一，用于确定数据集中不同域或属性之间的联系，找出有价值的多个域之间的依赖关系。发现频繁项集是关联规则挖掘中最基本、最重要的问题，自从Agrawal的开创性工作以来，有关研究从未停止过。当支持度阈值较低或数据集中存在长模式时，频繁项集挖掘可能产生大量频繁模式集，这将给人们的理解和从中发现有趣的模式造成一定的困难。为压缩庞大的频繁模式集，压缩的频繁项集挖掘是最近研究的一个热点问题，其中包括最大频繁项集挖掘和频繁闭项集挖掘。@2现有最大频繁项集挖掘算法，大多需要维护大量侯选项集并进行超集检测。当已有最大频繁项集数目较大时，超集检测将成为算法的瓶颈。本文首先提出了一种基于标记域FP-Tree的快速挖掘最大频繁项集算法BF-DMFI，该算法为FP-Tree中每个节点增加一个标记域，利用该域对节点进行有效的标记，从而减少了最大侯选频繁项集的数量，节约了超集检测时间，在一定程度上提高了算法的性能。按照搜索空间树的遍历策略，最大频繁项集挖掘算法分为宽度优先算法和深度优先算法。宽度优先算法大多需要维护大量候选项集并多次重复扫描数据库或搜索FP-Tree；而深度优先算法则需要递归构造频繁项的条件模式树并进行相应挖掘，这将加大算法的执行时间和所占用的内存空间。提出了一种基于FP-Tree的非递归深度优先挖掘算法DF-DMFI。该算法通过构造每个频繁节点的频繁子孙集和频繁前缀，连接生成最大频繁项集，利用MFI-Tree进行超集检测，并对FP-Tree进行有效的剪枝，从而保证了算法的执行效率。现有最大频繁项集和频繁闭项集挖掘算法，大多从事务数据库中直接挖掘，具有较高的时间和空间复杂度。提出了基于频繁项集的最大频繁项集(BFI-DMFI)和频繁闭项集挖掘算法(BFI-DCFI)。在BFI-DMFI算法中，通过逐个检测频繁项集在其集合中是否存在超集来判断该项集是不是最大频繁项集；在BFI-DCFI算法中，通过挖掘所有支持度相等的频繁项集中的最大频繁项集，组合生成频繁闭项集。利用此方法挖掘最大频繁项集和频繁闭项集在一定程度上降低了算法的时间和空间复杂度。在上述研究的基础上，本文最后设计并实现了一个关联规则挖掘工具原型。该原型可以挖掘出基于频繁项集、频繁闭项集和最大频繁项集的关联规则，并可根据用户自定义的规则进行约束挖掘，以进一步精简关联规则结果集。7.期刊论文频繁项集挖掘算法研究-情报杂志2005,24(11)在数据库中挖掘频繁项集是数据挖掘领域的最基本、最重要的问题.自从Agrawal的开创性工作以来,有关研究从未停止过.然而由于其内在的计算复杂性,这一问题并未完全解决.通过描述频繁项集挖掘的特点,并根据解空问的分类对已有各种频繁项集、闭频繁项集、最大闭频项集和不生成频繁项集的挖掘算法进行了分析和比较.8.期刊论文郑杰.张勇军动态排序的最大频繁项集挖掘算法的应用-科技信息2010(21)频繁项集的挖掘是数据挖掘中的一个基础和核心问题,具有广泛的应用领域.由于它是数据挖掘过程中最耗时的部分,挖掘算法的好坏直接影响数据挖掘尤其是关联挖掘的效率和应用范围.9.期刊论文李雄飞.苑森淼.董立岩.全勃.LIXiong-Fei.YUANSen-Miao.DONGLi-Yan.QUANBo多段支持度数据挖掘算法研究-计算机学报2001,24(6)在基于相联规则的数据挖掘算法中，Apriori等算法最为著名.它分为两个主要步骤：(1)通过多趟扫描数据库求解出频繁项集；(2)利用频繁项集生成规则.随后的许多算法都沿用Apriori中“频繁项集的子集必为频繁项集”的思想，在频繁项集Lk-1上进行JOIN运算构成潜在k项集Ck.由于数据库和Ck的规模较大，需要相当大的计算量才能生成频繁项集.AprioriTid算法给每个事务增加了一个唯一标识Tid，其特点是只扫描一趟数据库，其余趟扫描（如第k趟扫描）均在相应的数据集Ck上进行.由于数据规模改变不大，各算法的效率差别并不明显.该文提出分段计算支持度的思想，是把一个项集的支持度分段计算，每一个段记录该项集在相应规模事务中出现的频度，从而构成一个支持度向量.由于有了项集的多段支持度，可以推测出该项集能否包含在更大规模的频繁项集中，采用这种算法既提高了在扫描数据库过程中的信息获取率，又能及时剔除超集不是频繁项集的项集，进一步缩减了潜在项集的规模.在数据集扫描过程中，按文中定理1的思想调整数据集，达到提高频繁项集生成效率的目的.10.学位论文王春凯挖掘正相关的频繁项集2007数据挖掘的任务是发现大型数据集中隐藏的、预先未知的知识。关联规则的挖掘是数据挖掘研究的重要问题之一。该问题自1993年被R．Agrawal等人提出以来，一直受到广泛关注和重视。通常，关联规则的挖掘分两步：(1)挖掘所有的频繁项集；(2)由频繁项集产生强关联规则。其中第一步的时间复杂度远高于第二步。从频繁项集产生关联规则的方法是简单的，但是可能导致无意义的关联规则的产生。一些研究者注意到这一问题，提出在产生关联规则时利用提升度判断规则前、后件之间的正相关性，进一步过滤掉一些无意义的规则。但是，这种做法仍然存在两个问题：(1)不能减少挖掘频繁项集的时间开销。(2)不能保证规则前件(后件)中的项是正相关的，当规则的前件或后件内部存在负相关的项时，仍然可能产生无意义的关联规则。针对以上问题，本文基于数学期望，引进正相关的频繁项集的概念，并给出一种挖掘正相关的频繁项集的算法。本文的算法可以直接在FP-树中挖掘正相关的频繁项集，将正相关性的判断推进到了挖掘频繁项集的过程中。这样，不仅可以大幅度地减少产生频繁项集的数量，显著地提高挖掘频繁项集的效率，而且在由频繁项集产生关联规则时，可以有效地避免产生无意义的关联规则。此外，在挖掘频繁项集时，本文的算法还通过提取公共项，进一步降低了递归地构造条件FP-树的时间开销。在UCI机器学习基准数据集上实验表明，本文算法可以大幅度地减少产生频繁项集的数量，显著地提高挖掘频繁项集的效率，具有很好的性能，对于大型、稠密数据集尤其如此。本文链接：