基于频繁模式树的约束最大频繁项集挖掘算法

多数最大频繁项集挖掘算法产生候选项目集的代价很高,而实际应用中用户只关心部分关联规则。针对该问题,提出一种基于频繁模式树的约束最大频繁项集快速挖掘算法。该算法能随时删除不满足约束条件的项集,无需生成候选项目集,由此提高挖掘效率。实验结果证明,该算法的效率优于同类算法。     

多谓词约束下基于模式增长的频繁项集挖掘算法

针对多维关联规则中挖掘事务数据库的所有频繁项集这一问题,提出了基于维约束进行求解的构想。采用模式增长的挖掘方法并根据渭词约束特征,设计了两种频繁项集挖掘算法,其中MCMF11算法在指定约束下构建模式树并进行频繁项集挖掘,而节点向量约束的算法MCMF12在预先挖掘出无约束频繁项集的情况下,依据给定约束对已有频繁集及模式树进行更新搜索,因此需要开销更多的主存,但在更新过程中有更高的效率。理论分析和实验结果都表明了MCMFI算法的完备性和有效性。     

基于约束的交互式频繁模式挖掘算法

频繁模式挖掘是数据挖掘领域中很重要的一部分.目前,出现了许多基于约束的频繁模式挖掘算法和交互式算法,但把两者结合起来的算法却很少.提出了一种基于约束的交互式频繁模式挖掘算法IMCFP(interactive mining of constraint-based frequent patterns).首先该算法按照约束的性质来建立频繁模式树,并且只需扫描一遍数据库;然后建立每个项的条件树,挖掘以该项为前缀的最大频繁模式,并用最大频繁模式树来存储;最后根据最大模式来找出所有的支持度明确的频繁模式.另外,该算法允许用户在挖掘过程中动态地改变约束.实验表明,该算法与iCFP算法相比是很有效的.     

基于约束的最大频繁项集挖掘算法

为了解决目前带约束的频繁项集挖掘算法在具有长模式的密集型数据库中挖掘的不足,提出了一种快速的基于约束的最大频繁项集挖掘算法。该算法在特定约束条件的基础上运用了深度优先策略和有效的剪枝方法快速挖掘最大频繁项集。实验结果表明了该算法是快速有效的。     

目标频繁模式挖掘算法研究

通用的频繁模式挖掘算法通常产生庞大的频繁模式集,其中很多是用户不感兴趣的非目标模式。要排除这些非目标模式,用户必须进行"二次挖掘"。TFP-growth虽然生成所有最大目标频繁模式,但要从中获得目标频繁模式,还需经过"二次挖掘"。若在挖掘的早期就对非目标频繁模式的产生加以限制,则有望提高算法的效率。本文在TFP-growth和SFP-growth的基础上,提出一种目标频繁模式挖掘算法STFP-growth,通过对TFP-树的排序、根据树根结点的不同情形采用不同的建子树方法和目标频繁模式筛选方法等来提高算法的效率。STFP-growth挖掘的结果是所有满足用户需求的目标频繁模式,不需"二次挖掘"。实验表明,STFP-growth的效率高于TFP-growth,也明显优于Apriori和Eclat。     

带有多个可转化约束的频繁项集挖掘算法

1.引言频繁项集的挖掘是数据挖掘课题中的一个很重要的方面,然而频繁项集的挖掘过程通常会产生数目庞大的频繁项集,并且其中的绝大多数并不是客户所期望得到的,因而使挖掘过程的效果和效率都大打折扣。     

一种约束最大频繁模式快速挖掘算法

为了避免用户通过"二次挖掘"才能得到有用的结果集,本文提出了一种新的约束最大频繁模式挖掘算法CSMFPMax.CSMFP-Max算法基于CFP树和对称矩阵,在挖掘过程中采用了多种剪枝策略并结合了自顶向下和自底向上的双向搜索策略,大大缩小了候选集规模,避免了不必要的条件CFP树的产生.理论分析和实验结果表明CSMFP-Max算法是一种高效的约束最大频繁模式挖掘算法,具有良好的时空效率.     

改进的基于频繁模式树的最大频繁项集挖掘算法——FP-MFIA

针对最大频繁项目集挖掘算法(DMFIA)当候选项目集维数高而最大频繁项目集维数较低的情况下要产生大量的候选项目集的缺点,提出了一种改进的基于频繁模式树(FP-tree)结构的最大频繁项目集挖掘算法--FP-MFIA。该算法根据FP-tree的项目头表,采用自底向上的搜索策略逐层挖掘最大频繁项目集,从而加速每次对候选集计数的操作。在挖掘时根据每层的条件模式基产生维数较低的非频繁项目集,尽早对候选项目集进行剪枝和降维,可大量减少候选项目集的数量。同时在挖掘时充分利用最大频繁项集的性质,减少搜索空间。通过算法在不同支持度下挖掘时间的对比可知,算法FP-MFIA在最小支持度较低的情况下时间效率是DMFIA以及基于降维的最大频繁模式挖掘算法(BDRFI)的2倍以上,说明FP-MFIA在候选集维数较高的时候优势明显。     

不产生候选的快速投影频繁模式树挖掘算法

1.概述近年来,对事务数据库、时序数据库和各种其它类型数据库中的频繁模式挖掘的研究越来越普及。许多先前的研究都是采用Apriori或类似的候选产生—检查迭代算法,使用候选项集来找频繁项集。这些算法都基于一种重要的反单调的Apriori性质:任何非频繁的(k—1)-项集都不可能是频繁k-项集的子集。因此,如果一个候选k-项集的(k—1)-子集不在频繁(k—1)-项集中,则该候选也不可能是频繁的,从而可     

频繁项集挖掘算法研究

论述了频繁项集数据挖掘算法,并采用自底向上和自顶向下遍历搜索分类方法,对已有的频繁项集挖掘算法进行了分析和比较。     

一种基于FP-Growth的频繁项目集并行挖掘算法

FP-Growth算法是基于FP树挖掘频繁项目集的经典算法,为提高FP-Growth算法挖掘大规模数据频繁项目集的效率,提出了一种基于FP-Growth的频繁项目集并行挖掘算法FPPM。该算法基于Map/Reduce并行模型,在每个计算节点上首先构造局部频繁模式树,并对之进行挖掘得到局部频繁项目集,然后合并局部频繁项目集以得到全局频繁项集,由于此时得到的结果并不完备,所以对合并后未达到最小支持度阈值的项目集,重新计算其支持数。介绍了FPPM算法的设计思想,测试了其性能。实验结果表明FPPM算法具有较好的可扩展性。     

一种多关系频繁模式挖掘算法*

传统数据挖掘算法在处理多表时,需要物理连接,存在效率不高的问题。为了解决这一问题,提出了一种多关系频繁模式挖掘算法。该算法利用元组ID传播的思想,使多表间无须物理连接,就可以直接挖掘频繁模式。实验表明,此算法具有较高的效率。     

项约束频繁项集挖掘的新方法

项约束频繁项集挖掘是项约束关联规则挖掘的关键步骤。对项约束频繁项集挖掘的内涵进行讨论,认为一个项集X本身满足项约束条件B是不够的,数据库中支持X的全部事务均满足B才能称“项集X满足条件B”。据此,将Direct算法改进为Direct*,在Direct*中负项被作为一个独立的项来看待。项约束是简洁性约束,但目前已有的算法没有充分利用其简洁性,提出利用项约束简洁性的MSEB算法。实验表明：对稠密数据库,MSEB的效率较高,并且Direct*和MSEB两个算法均是正确的。     

Sliding window based weighted maximal frequent pattern mining over data streams

As data have been accumulated more quickly in recent years, corresponding databases have also become huger, and thus, general frequent pattern mining methods have been faced with limitations that do not appropriately respond to the massive data. To overcome this problem, data mining researchers have studied methods which can conduct more efficient and immediate mining tasks by scanning databases only once. Thereafter, the sliding window model, which can perform mining operations focusing on recently accumulated parts over data streams, was proposed, and a variety of mining approaches related to this have been suggested. However, it is hard to mine all of the frequent patterns in the data stream environment since generated patterns are remarkably increased as data streams are continuously extended. Thus, methods for efficiently compressing generated patterns are needed in order to solve that problem. In addition, since not only support conditions but also weight constraints expressing items’ importance are one of the important factors in the pattern mining, we need to consider them in mining process. Motivated by these issues, we propose a novel algorithm, weighted maximal frequent pattern mining over data streams based on sliding window model (WMFP-SW) to obtain weighted maximal frequent patterns reflecting recent information over data streams. Performance experiments report that MWFP-SW outperforms previous algorithms in terms of runtime, memory usage, and scalability.     

基于XML的完全频繁查询模式挖掘算法

使用树结构建模对XML查询进行研究,提出了一种基于树同构的查询包含检测方法。采用最右分枝扩展方法,系统地枚举查询模式树的同根子树。在枚举过程中,采用Diffset结构记录包含同根子树的事务集的查询事务标识,并给出挖掘算法DiffFRSTMiner。实验结果证实了该算法合理、高效,并可以减少一定的内存开销。     

Incremental sequence-based frequent query pattern mining from XML queries

Existing algorithms of mining frequent XML query patterns (XQPs) employ a candidate generate-and-test strategy. They involve expensive candidate enumeration and costly tree-containment checking. Further, most of existing methods compute the frequencies of candidate query patterns from scratch periodically by checking the entire transaction database, which consists of XQPs transferred from user query logs. However, it is not straightforward to maintain such discovered frequent patterns in real XML databases as there may be frequent updates that may not only invalidate some existing frequent query patterns but also generate some new frequent query patterns. Therefore, a drawback of existing methods is that they are rather inefficient for the evolution of transaction databases. To address above-mentioned problems, this paper proposes an efficient algorithm ESPRIT to mine frequent XQPs without costly tree-containment checking. ESPRIT transforms XML queries into sequences using a one-to-one mapping technique and mines the frequent sequences to generate frequent XQPs. We propose two efficient incremental algorithms, ESPRIT-i and ESPRIT-i ⁺, to incrementally mine frequent XQPs. We devise several novel optimization techniques of query rewriting, cache lookup, and cache replacement to improve the answerability and the hit rate of caching. We have implemented our algorithms and conducted a set of experimental studies on various datasets. The experimental results demonstrate that our algorithms achieve high efficiency and scalability and outperform state-of-the-art methods significantly.     

基于事务映射区间求交的高效频繁模式挖掘算法

关联规则挖掘是数据挖掘重要研究课题,大数据处理对关联规则挖掘算法效率提出了更高要求,而关联规则挖掘的最耗时的步骤是频繁模式挖掘。针对当前频繁模式挖掘算法效率不高的问题,结合Apriori算法和FP-growth算法,提出一种基于事务映射区间求交的频繁模式挖掘算法IITM（interval interaction and transaction mapping）,只需扫描数据集两次来生成FP树,然后扫描FP树将每个项的ID映射到区间中,通过区间求交来进行模式增长。该算法解决了Apriori算法需要多次扫描数据集,FP-growth算法需要迭代地生成条件FP树来进行模式增长而带来的效率下降的问题。在真实数据集上的实验显示,在不同的支持度下IITM算法都要要优于Apriori、FP-growth以及PIETM算法。     

基于最大频繁项目序列集挖掘DMFIA算法的改进

为了有效地解决客户序列视图数据库的数据挖掘问题,借鉴了关联规则挖掘最大频繁项目集DMFIA算法的相关思想.详细阐述了该算法,针对原算法不能有效地解决客户序列视图数据库的数据挖掘这一问题,在原算法的基础上结合序列模式提出了改进的DMFIA算法,并在原算法的基础上有了较大的改进.为了验证算法的正确性,运用Ora-cle9i数据库的PL/SQL进行了相应的验证.实验结果证实了改进算法的有效性和实用性,并具有较好的创新性和理论价值.     

基于FP-tree的最大频繁项目集挖掘算法

最大频繁项目集挖掘是数据挖掘领域最重要的基本问题之一,在分析已有算法的基础上提出了FP-MMFI算法,它是对FP-growth算法在最大频繁项目集挖掘上的扩展.提出了频繁路径的概念,用它可以有效地对FP-tree进行压缩和缩小搜索空间,同时使用投影的方法对超集检测进行了优化,减少了项目匹配的次数.最后实验结果表明,该算法在性能上优于已有的同类算法.     

基于遗传算法的频繁项挖掘算法

从数学规划的角度重新表述了单维布尔型频繁项挖掘问题,利用新定义的加法和数乘及范数运算将其归结为一个非线性0－1规划问题,并利用遗传算法进行求解。在分析频繁项挖掘问题困难原因的基础上,提出了利用原数据库记录确定初始种群的方法,并在IBM公布的ticeval2000数据库上进行了数值实验。实际计算结果表明,该方法一般在几代内即可找到一批长频繁模式。