一种基于Spark的不确定数据集频繁模式挖掘算法

如何在海量不确定数据集中提高频繁模式挖掘性能是目前研究的热点.传统算法大多是以期望、概率或者权重等单一指标为数据项集支持度，在大数据背景下，同时考虑概率和权重支持度的算法难以兼顾其执行效率.为此，本文提出一种基于Spark的不确定数据集频繁模式挖掘算法（UWEFP），首先，为了同时兼顾数据项的概率和权重，计算一项集的最大概率权重值并进行剪枝；然后，为了减少对数据集的多次扫描，结合Spark框架的优点，设计了一种具有FP-tree特征的新颖的UWEFP-tree结构进行模式树的构建及挖掘；最后在Spark环境下，以UCI数据集进行实验验证.实验结果表明本文的方法在保证挖掘结果的同时，提高了效率.     

从不确定图中挖掘频繁子图模式

研究不确定图数据的挖掘,主要解决不确定图数据的频繁子图模式挖掘问题.介绍了一种数据模型来表示图的不确定性,以及一种期望支持度来评价子图模式的重要性.利用期望支持度的Apriori性质,给出了一种基于深度优先搜索策略的挖掘算法.该算法使用高效的期望支持度计算方法和搜索空间裁剪技术,使得计算子图模式的期望支持度所需的子图同构测试的数量从指数级降低到线性级.实验结果表明,该算法比简单的深度优先搜索算法快3～5个数量级,有很高的效率和可扩展性.     

不确定数据流中频繁模式的并行挖掘算法

不确定数据集中频繁模式挖掘的研究热点之一是挖掘算法的时空效率的提高,特别在目前数据量越来越大的情况下,实际应用对挖掘算法效率的要求也更高。针对动态不确定数据流中的频繁模式挖掘模型,在算法AT-Mine的基础上,给出一个基于MapReduce的并行挖掘算法。该算法需要两次MapReduce就可以从一个滑动窗口中挖掘出所有的频繁模式。实验中,多数情况下通过一次MapReduce就可以挖掘到全部频繁项集,并且能按数据量大小均匀地把数据分配到各个节点上。实验验证了该算法的时间效率能提高1个数量级。     

一种不确定数据集上频繁模式挖掘的近似算法

为提高不确定数据集上频繁模式挖掘的效率, 针对已有算法在判断是否需要为头表中的某项创建子头表时的计算量比较大的问题, 给出一个近似挖掘策略AAT-Mine, 以损失小部分频繁项集为代价, 提高整个算法的挖掘效率。采用三个不同的典型数据集进行了算法的测试, 分别与目前最好的算法和典型算法进行性能对比。实验结果验证了近似算法AAT-Mine的时空效率都得到了提高。     

基于模式增长的不确定数据的频繁模式挖掘算法

为提高不确定数据频繁模式(FP)挖掘算法的时空效率,提出了基于最大概率的不确定频繁模式挖掘(UFPM-MP)算法。首先,利用事务项集中的最大概率值预估期望支持数;然后,使用该期望支持数与最小期望支持数阈值进行比较,以确定某一项集是否为候选频繁项集,并对候选项集建立子树以递归挖掘频繁模式。实验中,UFPM-MP算法与AT-Mine算法进行了对比,并在6个典型的数据集上进行实验验证。实验结果表明,UFPM-MP算法的时空效率得到了提高,稀疏数据集上提高约30%,稠密数据集上的效率提高更为明显(约3~4倍)。预估期望支持数的策略有效地减少了子树和头表项的数量,从而提高了算法的时空效率;且最小期望支持数越小,或需要挖掘的频繁模式越多的时候,算法的时间效率提高越多。     

一种高效的频繁模式挖掘算法

在分析研究具有代表性的关联知识挖掘算法的基础上,提出了挖掘频繁模式的一个新的数据库存储结构AFP-树,并在此结构上设计了一个频繁模式挖掘算法。理论研究已经阐明了AFP-树的有效性和相关算法的高效性。     

一种频繁子图挖掘算法

为减少频繁子图规范化检测的时间复杂度,对规范化邻接矩阵的相关性质进行分析。给出相关定理并证明其正确性,从而减少冗余候选子图的产生。在此基础上,提出一种频繁子图挖掘算法——FSM_CAM。实验结果证明,与现有频繁子图挖掘算法FSubGraphM相比,FSM_CAM算法的效率较高。     

基于概率衰减窗口模型的不确定数据流频繁模式挖掘

考虑到不确定数据流的不确定性,设计了一种新的概率频繁模式树PFP-tree和基于该树的概率频繁模式挖掘方法PFP-growth.PFP-growth使用事务性不确定数据流及概率衰减窗口模型,通过计算各概率数据项的期望支持度以发现概率频繁模式,其主要特点有：考虑到窗口内不同时间到达数据项的贡献度不同,采用概率衰减窗口模型计算期望支持度,以提高模式挖掘准确度;设置数据项索引表和事务索引表,以加快频繁模式树检索速度;通过剪枝删除不可能成为频繁模式的结点,以降低模式树的存储及检索开销;对每个结点都设立一个事务概率信息链表,以支持数据项在不同事务中具有不同概率的情形.实验结果表明,PFP-growth在保证挖掘模式准确度的前提下,在处理时间和内存空间等方面都具有较好的性能.     

有效的不确定数据概率频繁项集挖掘算法

针对已有概率频繁项集挖掘算法采用模式增长的方式构建树时产生大量树节点,导致内存空间占用较大以及发现概率频繁项集效率低等问题,提出了改进的不确定数据频繁模式增长(PUFP-Growth)算法。该算法通过逐条读取不确定事务数据库中数据,构造类似频繁模式树(FP-Tree)的紧凑树结构,同时更新项头表中保存所有尾节点相同项集的期望值的动态数组。当所有事务数据插入到改进的不确定数据频繁模式树(PUFP-Tree)中以后,通过遍历数组得到所有的概率频繁项集。最后通过实验结果和理论分析表明:PUFP-Growth算法可以有效地发现概率频繁项集;与不确定数据频繁模式增长(UF-Growth)算法和压缩的不确定频繁模式挖掘(CUFP-Mine)算法相比,提出的PUFP-Growth算法能够提高不确定数据概率频繁项集挖掘的效率,并且减少了内存空间的使用。     

挖掘不确定频繁子图的改进算法的研究

鉴于图结构能简单方便地描绘复杂的数据以及实际应用中图数据的获得具有不确定性,不确定频繁子图挖掘算法得到广泛的研究。目前一个典型的图挖掘算法是MUSE,但MUSE算法存在期望支持度计算消耗大、时间效率不够高等问题。针对此问题提出了一种基于划分思想混合搜索策略的不确定子图挖掘算法EDFS,它用改进过的GSpan算法进行不确定的子图数据预处理,用裁剪子图模式的搜索空间裁剪不确定子图数据,用基于划分思想的混合策略进行频繁子图的挖掘。子图同构与边存在概率的实验结果证明了EDFS算法能更高效地挖掘出不确定数据频繁子图。     

从图数据库中挖掘频繁跳跃模式

很多频繁子图挖掘算法已被提出.然而,这些算法产生的频繁子图数量太多而不能被用户有效地利用.为此,提出了一个新的研究问题:挖掘图数据库中的频繁跳跃模式.挖掘频繁跳跃模式既可以大幅度地减少输出模式的数量,又能使有意义的图模式保留在挖掘结果中.此外,跳跃模式还具有抗噪声干扰能力强等优点.然而,由于跳跃模式不具有反单调性质,挖掘它们非常具有挑战性.通过研究跳跃模式自身的特性,提出了两种新的裁剪技术:基于内扩展的裁剪和基于外扩展的裁剪.在此基础上又给出了一种高效的挖掘算法GraphJP(an algorithm for mining jump patterns from graph databases).另外,还严格证明了裁剪技术和算法GraphJP的正确性.实验结果表明,所提出的裁剪技术能够有效地裁剪图模式搜索空间,算法GraphJP是高效、可扩展的.     

GenMax: An Efficient Algorithm for Mining Maximal Frequent Itemsets

We present GenMax, a backtrack search based algorithm for mining maximal frequent itemsets. GenMax uses a number of optimizations to prune the search space. It uses a novel technique called progressive focusing to perform maximality checking, and diffset propagation to perform fast frequency computation. Systematic experimental comparison with previous work indicates that different methods have varying strengths and weaknesses based on dataset characteristics. We found GenMax to be a highly efficient method to mine the exact set of maximal patterns.     

基于不确定性数据的频繁闭项集挖掘算法

对于不确定性数据,传统判断项集是否频繁的方法并不能准确表达项集的频繁性,同样对于大型数据,频繁项集显得庞大和冗余。针对上述不足,在水平挖掘算法Apriori的基础上,提出一种基于不确定性数据的频繁闭项集挖掘算法UFCIM。利用置信度概率表达项集频繁的准确性,置信度越高,项集为频繁的准确性也越高,且由于频繁闭项集是频繁项集的一种无损压缩表示,因此利用压缩形式的频繁闭项集替代庞大的频繁项集。实验结果表明,该算法能够快速地挖掘出不确定性数据中的频繁闭项集,在减少项集冗余的同时保证项集的准确性和完整性。     

一种高效频繁子图挖掘算法

由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题--频繁子图挖掘.诸如化学、生物学、计算机网络和WWW等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间复杂性是O(n³·2ⁿ),其中,n是图集中的频繁边数.提出算法的时间复杂性是O〔2ⁿ·n^2.5／logn〕,性能提高了O(√n·logn)倍.实验结果也证实了这一理论分析.     

MAXSeq: 一个新的最大频繁序列挖掘算法

最大频繁序列发现是数据挖掘中的一个重要分支．本文提出一种发现最大频繁序列集的算法MAXSeq，该算法通过对潜在的最大频繁序列进行选择性的扩展，直接判断其是否为最大序列，无须对候选最大序列进行维护，从而显著减小了存储开销．同时，优化策略的恰当运用对降低CPU时间起着至关重要的作用．     

一种开采频繁项目集集合的快速算法

在大的数据集合中,开采其中的频繁项目集集合是数据挖掘中极具挑战的重要任务。已经有很多高效的算法被总结了出来。本文提出了一种思想,即开采频繁项目集集合的一 个子集,我们称之为频繁无析取规则集集合,而并非开采完全的频繁项目集集合。我们证明能借助它不读取数据库而还原出频繁项目集集合的全集和它们的支持度。本文还提 提出了一个开采无析取规则集集合的算法HOPE-Ⅱ,实验结果显示了其高效性。我们将它与另一种称为频繁封闭集的精简集进行对比,几乎所有的实验结果都显示使用无析取规则集集合比使用封闭集集合来开采频繁项目集集合更有效。     

一种基于多数组的频繁模式挖掘算法

提出了一种新颖的频繁模式挖掘算法,该算法与现有的挖掘算法相比具有明显的优点,首先,该算法不需要产生候选项集,其次该算法具有更少的数据库扫描次数,该算法在中小型数据库上挖掘关联规则只需要扫描交易数据库一次,对于大型交易数据库的关联规则挖掘最多也只需要扫描交易数据库两次。因而,该算法与现有的频繁模式挖掘算法相比具有更高的效率。