一种基于位运算的频繁闭项集挖掘算法

针对相关算法在挖掘频繁闭项集时所存在的问题, 提出了一种基于位运算的频繁闭项集挖掘算法。该算法首先将数据集转换成布尔矩阵, 只需扫描数据集一次; 通过位运算计算支持度, 利用矩阵和数组存储辅助信息, 减少时间和空间消耗; 深度优先搜索产生频繁闭项集时利用剪枝策略进一步减少挖掘时间; 利用同生项集性质进行闭合性检测, 无须检查超集或子集。理论分析和实验结果验证了该算法的有效性。     

不确定数据频繁闭项集挖掘算法

由于不确定数据的向下封闭属性,挖掘全部频繁项集的方法会得到一个指数级的结果。为获得一个较小的合适的结果集,研究了在不确定数据上挖掘频繁闭项集,并提出了一种新的频繁闭项集挖掘算法——NA-PFCIM。该算法将项集挖掘过程看作一个概率分布函数,考虑到基于正态分布模型的方法提取的频繁项集精确度较高,而且支持大型数据库,采用了正态分布模型提取频繁项集。同时,为了减少搜索空间以及避免冗余计算,利用基于深度优先搜索的策略来获得所有的概率频繁闭项集。该算法还设计了两个剪枝策略:超集修剪和子集修剪。最后,在常用的数据集(T10I4D100K、Accidents、Mushroom、Chess)上,将提出的NA-PFCIM算法和基于泊松分布的A-PFCIM算法进行比较。实验结果表明,NA-PFCIM算法能够减少所要扩展的项集,同时减少项集频繁概率的计算,其性能优于对比算法。     

基于父子等价剪枝策略的最大频繁项集挖掘

在传统剪枝策略中,具有相同事务集的父子结点搜索空间没有充分剪枝,效率较低.为此,提出父子等价的剪枝策略.采用深度优先搜索集合枚举树,对于父子结点中具有相同事务集的搜索空间进行剪枝,有效地缩小搜索空间,减少频繁项计算的次数,给出基于该剪枝策略的最大频繁项集挖掘算法.实验结果表明,该算法可缩短同一支持度下的最大频繁项集挖掘时间.     

一种基于ESEquivPS的封闭频繁项集挖掘算法

本文提出一种基于ESEquivPS(扩展支持度相等性剪枝策略)的封闭频繁项集挖掘算法ECFIMA。该算法采用深度优先和广度优先相结合的策略访问搜索空间,使用垂直位图向量格式存储表示项集和事务数据库,同时利用基本剪枝策略、相等性剪枝策略、扩展支持度相等性剪枝策略1和扩展支持度相等性剪枝策略2进行候选空间剪枝,并采用多种不同特性的测试数据集进行实验。实验结果表明,ECFIMA算法是一种高效的封闭频繁项集挖掘算法,在多种测试数据集上性能都优于CHARM算法,尤其是在拥有大量长的封闭频繁项集的测试数据集上,效率比CHARM算法提高约2~3倍。     

基于频繁项集挖掘最大频繁项集和频繁闭项集

提出了基于频繁项集的最大频繁项集（BFI-DMFI）和频繁闭项集挖掘算法（BFI-DCFI）。BFI-DMFI算法通过逐个检测频繁项集在其集合中是否存在超集确定该项集是不是最大频繁项集;BFI-DCFI算法则是通过挖掘所有支持度相等的频繁项集中的最大频繁项集组合生成频繁闭项集。该类算法的提出,为关联规则的精简提供了一种新的解决方法。     

基于图和双向搜索的频繁项集挖掘算法

基于图的关联规则挖掘算法会产生大量候选项集。针对该问题,提出一种结合双向搜索策略的改进算法。按照支持度对频繁 1-项集排序,对频繁k-项集的最长超集进行验证,利用Apriori算法进行剪枝。实验结果表明,在支持度阈值较小时,改进算法能有效减少候选项集的数量,提高挖掘效率。     

一种快速挖掘频繁项目集算法

发现频繁项目集是多种数据挖掘应用中的的,最新的研究主要围绕减少事务数据库的扫描次数进而减少挖掘过程的I/O代价来提高效率.本文提出一种快速挖掘频繁项目集的算法FDFI(fast discoveryfrequentitemsets).该算法利用深度优先搜索的特点,结合频繁项目集的性质,有效地缩小了搜索空间,并采用独特的支持度计数策略,只需一次数据库扫描,就可计算所有项目集的支持度,大大减少了数据扫描量.最后作者对这一算法的性能进行了理论分析和实验验证.     

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

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

基于N-list和DiffNodeset结构的频繁项集并行挖掘算法

频繁项集挖掘是数据挖掘中的一个基本问题,在许多数据挖掘应用中发挥着重要作用。针对并行频繁项集挖掘算法MrPrePost在大数据环境存在密集数据集下算法效率下降、计算节点负载量不均衡和冗余搜索等问题,提出了基于N-lists和DiffNodeset两种结构的并行频繁项集挖掘算法(Parallel Mining algorithm of Frequent Itemset based on N-list and DiffNodeset structure, PFIMND)。首先,根据N-list和DiffNodeset在存储不同数据集上的优势,设计了稀疏度估计函数(Sparsity Estimation, SE),根据数据集稀疏程度灵活选取其中之一压缩数据集,相比采用单一存储结构消耗的内存更少;其次,提出了计算量估计函数(Computation Estimation, CE)来估计频繁1项集F-list中每一项的负载量,并根据计算量进行均匀分组;最后采用集合枚举树作为搜索空间,为避免组合爆炸和冗余搜索问题,设计了超集剪枝策略和基于宽度优先搜索的剪枝策略,生成最终的挖掘结果。实验结果表明,相比...     

一种基于条件矩阵的最大频繁项集挖掘算法

在数据挖掘问题的研究中,为减少候选最大频繁项集数量和降低超集存在判断的开销,为了优化算法,提出了一种基于条件矩阵挖掘最大频繁项集的算法(conditional matrix for maximal frequent itemsets,CMMFI).将压缩频繁模式树表示的频繁项集信息投影到条件矩阵,采用最大顺序尾项排序和扩展2项集剪枝,有效削减了搜索空间,提高了算法的空间效率.使用标号数组优化超集检测的过程,减少了频繁项集比较的次数,减少了花费时间.最后,选用了两个模式长度不同的数据集,将算法与FPMax算法进行性能比较,实验结果验证了算法的有效性和优越性.     

一种基于ZBDD结构的Top—k挖掘算法

研究微阵列数据中挖掘Top—k频繁闭合项集问题,并设计挖掘算法ZDtoP。算法采用ZBDD结构压缩存储数据集,使用自顶向下深度优先搜索策略挖掘项集长度不小于给定值min_l的Top—k频繁闭合项集,并对搜索空间进行有效修剪。通过实例证明该算法是正确有效的。     

一种基于ZBDD结构的Top-k挖掘算法

研究微阵列数据中挖掘Top-k频繁闭合项集问题,并设计挖掘算法ZDtop。算法采用ZBDD结构压缩存储数据集,使用自顶向下深度优先搜索策略挖掘项集长度不小于给定值min_l的Top-k频繁闭合项集,并对搜索空间进行有效修剪。通过实例证明该算法是正确有效的。     

一种挖掘最大频繁项集的深度优先算法

最大频繁项集挖掘是许多数据挖掘应用中的重要问题．提出一种新的深度优先搜索最大频繁项集的算法．该算法采用位图数据格式,结合了流行的各种有效剪枝技术,并使用局部最大频繁项集来进行高效的超集存在判断,明显地加速了最大频繁项集的生成,从而降低了CPU时间．     

MAFIA: a maximal frequent itemset algorithm

We present a new algorithm for mining maximal frequent itemsets from a transactional database. The search strategy of the algorithm integrates a depth-first traversal of the itemset lattice with effective pruning mechanisms that significantly improve mining performance. Our implementation for support counting combines a vertical bitmap representation of the data with an efficient bitmap compression scheme. In a thorough experimental analysis, we isolate the effects of individual components of MAFIA including search space pruning techniques and adaptive compression. We also compare our performance with previous work by running tests on very different types of data sets. Our experiments show that MAFIA performs best when mining long itemsets and outperforms other algorithms on dense data by a factor of three to 30.     

基于FP-Tree的频繁闭合项目集挖掘算法的研究

目前频繁闭合项目集挖掘算法有很多,例如CLOSET[1]。CLOSET以FP-Growth为基础,采用FP-Tree来表示模式支持集,通过深度优先搜索来挖掘频繁闭合模式。其困难是,递归构造“条件FP-Tree”的CPU开销和存储开销很大。为解决上面的问题,论文提出一种基于FP-Tree和COFI-Tree的频繁闭合项目集挖掘算法,在该算法中引用了COFI-Tree结构,COFI-Tree无需递归地构造“条件FP-Tree”,并且某一时刻只有一个频繁项的COFI-Tree在内存,所以大大减少了内存消耗。通过实验证明:当挖掘大型数据库时,在执行时间方面,该算法比其它算法更有效。     

最大频繁项目集挖掘技术研究与展望

提高最大频繁项目集挖掘算法的效率是关联规则挖掘研究一个重点领域.本文主要对影响最大频繁项目集挖掘效率的数据分布、搜索策略、支持度计算及剪枝策略等技术进行了研究,并对已提出的最大频繁项目集挖掘算法进行了分析.     

一种高效的最大频繁项集挖掘算法DFMFI-Miner

分析最大频繁项集和完全频繁项集的关系,提出了一个挖掘最大频繁项集的高效算法DFMFI—Miner（The Miner Basedon Depth—First Searching for Mining Maximal Frequent Itemsets）,采用深度优先方法搜索项集空间,采用垂直位图及一定的压缩方法对表示事务数据库并进行约简,并采用多种有效剪枝策略和优化策略,提高了算法的效率。在多个数据集上进行了实验,实验结果表明该算法特别适于挖掘具有长频繁项集的数据集。     

Non-derivable itemset mining

All frequent itemset mining algorithms rely heavily on the monotonicity principle for pruning. This principle allows for excluding candidate itemsets from the expensive counting phase. In this paper, we present sound and complete deduction rules to derive bounds on the support of an itemset. Based on these deduction rules, we construct a condensed representation of all frequent itemsets, by removing those itemsets for which the support can be derived, resulting in the so called Non-Derivable Itemsets (NDI) representation. We also present connections between our proposal and recent other proposals for condensed representations of frequent itemsets. Experiments on real-life datasets show the effectiveness of the NDI representation, making the search for frequent non-derivable itemsets a useful and tractable alternative to mining all frequent itemsets.