含正负项目的基于位串频繁项集挖掘算法研究

对频繁模式树中的每个节点引入一个位串存储前缀路径,提出了包含正负项目的频繁模式树的构造方法,它不需要反复遍历节点就可获得包含正负项目的频繁项集．与直接使用ＦＰｇｒｏｗｔｈ算法相比,无需对原始数据库进行负项目的扩展,也不用再构造并销毁额外的数据结构,只需在原始的频繁模式树上修改,因而在时空开销上都具有一定的优势．实验表明,所提出的算法比现有的同类挖掘算法和直接ＦＰｇｒｏｗｔｈ算法具有更好的效率．     

基于FP-Tree快速挖掘频繁项集

发现频繁项集是关联规则挖掘中最基本、最重要的问题.目前已有两类频繁项集挖掘算法,然而由于其内在的复杂性,这一问题并未完全解决.提出了一种基于FP-Tree的频繁项集挖掘算法,该算法通过计算FP-Tree中非叶子节点的频繁子孙集和频繁前缀,组合生成频繁项集,无需递归构造每个频繁项的条件模式树,节约了时间和内存空间,算法性能在一定程度上得到了提高.     

基于FP—tree的最大频繁项集挖掘新算法

研究挖掘关联规则的一个重要工作就是找出所有的频繁项集。基于FP—tree的最大频繁项集挖掘算法要多次生成大量的FP—tree,并且需要对其多次遍历,消耗了大量的时间。针对以上缺点,提出一种基于FP—tree并利用数组和矩阵技术进行优化的最大频繁项集挖掘算法（Mining Maximal Frequent Itemset。简称MMFI）,它既减少创建FP—tree的数量,又节省遍历FP—tree的时间,实验证明本算法是有效的。     

基于FP-Tree有效挖掘最大频繁项集

最大频繁项集的挖掘过程中,在最小支持度较小的情况下,超集检测是算法的主要耗时操作.提出了最大频繁项集挖掘算法FPMFI(frequent pattern tree for maximal frequent item set)使用基于投影进行超集检测的机制,有效地缩减了超集检测的时间.另外,算法FPMFI通过删除FP子树(conditional frequent pattern tree)的冗余信息,有效地压缩了FP子树的规模,减少了遍历的开销.分析表明,算法FPMFI具有优越性.实验比较说明,在最小支持度较小时,算法FPMFI的性能优于同类算法1倍以上.     

一种基于正频繁项集的非矛盾正负关联规则挖掘算法

关联规则前件或后件中部分项集为负的负关联规则更有意义,要挖掘这样的负关联规则首先要获取负频繁项集。为快速获取负频繁项集,本文提出将正频繁项集中若干项改为负项,若满足最小支持度计数则为负频繁项集。在正负频繁项集中生成关联规则时,会产生矛盾的关联规则,对于矛盾规则,提出使用二次概率相关性判断方法来正确选择具有矛盾的关联规则。经过实验,验证该算法是有效和正确的。     

基于FP-Tree的共享前缀频繁项集挖掘算法

在数据挖掘中发现关联规则是一个基本问题,而发现频繁项集是关联规则挖掘中最基本、最重要的问题。提出了基于FP-Tree的共享前缀频繁项集挖掘算法－FP-SPMA算法。构造FP-Tree来压缩事务数据库,通过共享前缀和前瞻剪枝快速减小候选项集,无需递归构造条件模式树,算法性能有明显的提高。     

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

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

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

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

基于间隔链表改进的频繁项集挖掘算法

针对PrePost算法中需要建立复杂的前序和后序编码树(PPC-tree)和节点链表(N-list)的问题,提出一种基于间隔链表(I-list)改进的高效频繁项集挖掘算法。首先,该算法采用了比频繁模模式树(FP-tree)更加压缩的数据存储结构间隔编码的频繁模式树(IFP-tree),无需迭代地建立条件FP-tree;其次,该算法利用更简洁的I-list代替了PrePost中复杂的N-list,从而提高了建树和挖掘速度;最后,对于单分支路径的情况,该算法通过组合的方法,直接求得某些频繁项集,以提高算法的时间性能。实验结果表明:一方面,对于同一数据集在相同支持数下挖掘的结果相同,验证了改进算法的正确性;另一方面,无论在时间还是空间上改进算法的整体性能均比PrePost算法提高约10%;且对于稀疏型数据库或密集型数据库的挖掘都有较好的应用。     

一种基于组合方式改进的频繁项集挖掘算法

FP-growth算法用于关联规则挖掘分成两个阶段：构建频繁模式树和进行频繁模式挖掘;对这两个阶段分别进行改进,若项头表中存在同频度的频繁项,在构建FP-tree的过程动态调整其位置,构建压缩的最优化FP-tree,提出了IMFP-tree算法。在进行频繁模式挖掘阶段,提出CFP-mine算法,CFP-mine算法采用一种新方法构建条件模式基,且采用组合方式挖掘频繁项集,有别于传统FP-growth算法的挖掘过程,理论上证明和实验验证本算法的正确性和高效性。     

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

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

基于标记域FP-Tree快速挖掘最大频繁项集

现有最大频繁项集挖掘算法,大多需要维护大量侯选项集并进行超集检测.当已有最大频繁项集数目较大时,超集检测将成为算法的瓶颈.提出了一种基于FP-Tree的快速挖掘最大频繁项集算法BF_DMFI(based on FP-Tree for discovering maximum frequent itemsets algorithm).该算法为FP-Tree中每个节点增加一个标记域,利用该域对节点进行有效的标记,从而减少了最大侯选频繁项集的数量,节约了超集检测时间,在一定程度上提高了算法的效率.     

基于FP树的全局最大频繁项集挖掘算法

挖掘最大频繁项集是多种数据挖掘应用了更新最大频繁候选项集集合,需要反复地扫描整个数据库,而且大部分算法是单机算法,全局最大频繁项集挖掘算法并不多见.为此提出MGMF算法,该算法利用FP-树结构,类似FP-树挖掘方法,一遍就可以挖掘出所有的最大频繁项集,并且超集检测非常简单、快捷.另外MGMF算法采用了分布式PDDM算法播报消息的思想,具有很好的拓展性和并行性.实验证明MGMF算法是有效可行的.     

基于FP-Tree的最大频繁项目集挖掘及更新算法

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题,之前的很多研究都是采用Apriori类的候选项目集生成-检验方法.然而,候选项目集产生的代价是很高的,尤其是在存在大量强模式和/或长模式的时候.提出了一种快速的基于频繁模式树(FP-tree)的最大频繁项目集挖掘DMFIA(discover maximum frequent itemsets algorithm)及其更新算法UMFIA(update maximum frequent itemsets algorithm).算法UMFIA将充分利用以前的挖掘结果来减少在更新的数据库中发现新的最大频繁项目集的费用.     

基于FP-Tree的反向频繁项集挖掘

在拓展现有反向频繁挖掘问题定义,探索反向频繁项集的3个具体应用后,提出了一种基于FP-tree的反向频繁项集挖掘方法.该方法首先采用分治思想,将目标约束划分为若干子约束,每步求解一个子线性约束问题,经过若干步迭代后找到一个满足整个给定约束的目标FP-tree;然后根据目标FP-tree生成一个仅含频繁项的临时事务数据库TempD;最后通过向TempD中撒入非频繁项得到目标数据集.理论分析和实验表明该方法是正确的、高效的,且与现有方法仅能输出1个目标数据集相比,该方法能够输出较多的目标数据集.     

多约束下的频繁项集挖掘

为了要从大量的频繁项集中筛选出有用的规则,引入基于约束的频繁项集的挖掘,有学者已经研究了基于单调型、简洁型约束和Tough型约束的频繁项集挖掘技术,但基于多约束下频繁项集挖掘问题还没有得到解决。论文就是基于这个问题,通过对构造的包含有多约束的算式的研究,确定了在什么情况下多约束能满足单调或反单调的条件。这不但使多约束能够融入到Apriori算法中去,而且提高了多约束条件下候选频繁项集检验的速度和效率。     

基于矩阵的频繁项集挖掘算法

如何高效地挖掘频繁项集是关联规则挖掘的主要问题。该文根据集合论和矩阵理论,提出一种基于矩阵的频繁项集挖掘算法。该算法只需扫描数据库一次,就能把所有事务转化为矩阵的行,把所有项和项集转化为矩阵的列,在对矩阵操作时能一次性产生所有频繁项集,且当支持度阈值改变时无需重新扫描数据库。实验结果表明,该算法的挖掘效率高于Apriori算法。     

一种基于单事务项集组合的频繁项集挖掘算法

Apriori是挖掘频繁项集的基本算法,目前该算法及其优化变种都没有解决候选项及重复扫描事务数据库的问题.文章通过对Apriori及其优化算法的深入探究,提出了一种基于单事务组合项集的挖掘算法,该算法在一个事务内部对"数据项"进行组合,在事务数据库中对所有相同"项集"进行计数.不经过迭代过程,不产生候选项集,所有频繁项集的挖掘过程只需对事务数据库一次扫描,提高了频繁项集挖掘效率.