频繁项集挖掘的研究进展及主流方法

关联分析作为数据挖掘的主要研究模块之一,主要用于发现隐藏在大型数据集中的强关联特征。而多数关联规则挖掘任务可分为频繁模式(频繁项集、频繁序列、频繁子图)的产生和规则的产生。前者发现数据集中满足最小支持度阈值的项集、序列与子图;后者从上一步发现的频繁模式中提取高置信度的规则。频繁项集挖掘是许多数据挖掘任务中的关键问题,也是关联规则挖掘算法的核心。十几年来,学者们致力于提高频繁项集的生成效率,从不同的角度进行改进以提高算法效率,大量的高效可伸缩性算法被提出。文中对频繁项集挖掘进行深入分析,对完全频繁项集、闭频繁项集、极大频繁项集的典型算法进行介绍和评述,最后对频繁项集挖掘算法的研究方向进行简要分析。     

基于Spark框架的FP-Growth大数据频繁项集挖掘算法

针对大数据中的频繁项集挖掘问题,提出一种基于Spark框架的FP-Growth频繁项集并行挖掘算法。首先,根据垂直布局思想将数据按照事务标识符垂直排列,以此解决扫描整个数据集的缺陷。然后,通过FP-Growth算法构建频繁模式树,并生成频繁1-项集。接着,通过扫描垂直数据集来计算项集的支持度,从而识别出非频繁项,并将其从数据集中删除以降低数据尺寸。最后,通过迭代过程来生成频繁 -项集。在标准数据集上的实验结果表明,该算法能够有效挖掘出频繁项集,在执行时间方面具有很大的优越性。     

挖掘最大频繁项集的改进蚁群算法

最大频繁项集挖掘用于发现频繁地出现在数据集中的最大子集,目前已经有许多有效的算法。应用蚁群算法挖掘最大频繁项集是一种新的方法,但是该算法往往迭代次数多,提取率低。结合频繁项集关联图和最大最小蚂蚁系统,提出一种新的蚁群算法。算法构造蚁群路径图,蚁群在动态的信息素和启发式因子指导下构造局部最大频繁项集,通过新的局部更新和全局更新机制发现全局最大频繁项集。对比实验表明,算法挖掘速度快,提取率高。     

挖掘数据流中的频繁模式

发现数据流中的频繁项是数据流挖掘中最基本的问题之一．数据流的无限性和流动性使得传统的频繁模式挖掘算法难以适用．针对数据流的特点,在借鉴FP-growth算法的基础上．提出了一种数据流频繁模式挖掘的新方法：FP—DS算法．算法采用数据分段的思想,逐段挖掘频繁项集,用户可以连续在线获得当前的频繁项集,可以有效地挖掘所有的频繁项集,算法尤其适合长频繁项集的挖掘．通过引入误差ε,裁减了大量的非频繁项集,减少了数据的存储量,也能保证整个数据集中项目集支持度误差不超过ε.分析和实验表明算法有较好的性能．     

多段支持度数据挖掘算法研究

在基于相联规则的数据挖掘算法中,Apriori等算法最为著名。它分为两个主要步骤：（1）通过多趟扫描数据库求解出频繁项集;（2）利用频繁项集生成规则。随后的许多算法都沿用Apriori中“频繁项集的子集必为频繁项集”的思想,在频繁项集Lk-1上进行JOIN运算构成潜在k项集Ck。由于数据库和Ck的规模较大,需要相当大的计算量才能生成频繁项集。AprioriTid算法给每个事务增加了一个唯一标识Tid,其特点是只扫描一趟数据库,其余趟扫描（如第k趟扫描）均在相应的数据集Ck^-上进行。由于数据规模改变不大,各算法的效率差别并不明显。该文提出分段计算支持度的思想,是把一个项集的支持度分段计算,每一个段记录该项集在相应规模事务中出现的频度,从而构成一个支持度向量。由于有了项集的多段支持度,可以推测出该项集能否包含在更大规模的频率项集中,采用这种算法既提高了在扫描数据库中的信息获取度,又能及时剔除超集不是频繁项集的项集,进一步缩减了潜在项集的规模,在数据集扫描过程中,按文中定理1的思想调整数据集,达到提高频繁项集生成效率的目的。     

Chopper：有效的树挖掘算法

在数据集中挖掘频繁模式是数据挖掘研究的关键环节之一。在过去，很多的努力都集中在独立数据的挖掘上。然而，现实世界中许多实体之间总会保持着千丝万缕的关系。如何获得这些关系的频繁模式，已逐渐成为近年来研究的一个目标，我们将它称之为频繁结构的挖掘。在数据挖掘中，一个重要的方法是关联规则挖掘。它被用来发现频繁出现在数据库事务中的项集；另一个重要的方法是序列挖掘，它的任务是去寻找一个项集的序列。这些挖掘任务都被称为频繁模式的挖掘。     

标签集约束近似频繁模式的并行挖掘

近似频繁模式衍生于频繁模式,综合了频繁项集与频繁子图的特点。针对该模式的研究集中在无标签图上,其应用场景主要为社交网络、语义网络、智能电网等。近似频繁模式挖掘过程同时涉及频繁项集挖掘和频繁子图挖掘,因此已有的处理频繁模式挖掘算法无法较好地解决近似频繁模式挖掘问题。基于近似频繁模式结构,将其拓展到带标签图中,引入标签集约束,并设计标签集约束近似频繁模式挖掘算法LCPP（Label-Constraint Proximity Pattern）,该算法并行部署在MapReduce计算模型中,弥补了开源pFP算法处理大规模数据时效率不高的缺点。实验结果验证了该算法的有效性和可扩展性,表明了LCPP算法是pFP算法的极佳补充。     

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

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

一种基于Spark的频繁项集快速挖掘算法

如何在海量数据集中提高频繁项集的挖掘效率是目前研究的热点.随着数据量的不断增长,使用传统算法产生频繁项集的计算代价依然很高.为此,提出一种基于Spark的频繁项集快速挖掘算法（fast mining algorithm of frequent itemset based on spark,Fmafibs）,利用位运算速度快的特点,设计了一种新颖的模式增长策略.该算法首先采用位串表达项集,利用位运算来快速生成候选项集;其次,针对超长位串计算效率低的问题,考虑将事务垂直分组处理,将同一事务不同组之间的频繁项集通过连接获得候选项集,最后进行聚合筛选得到最终频繁项集.算法在Spark环境下,以频繁项集挖掘领域基准数据集进行实验验证.实验结果表明所提方法在保证挖掘结果准确的同时,有效地提高了挖掘效率.     

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

频繁模式挖掘算法FP-growth算法需递归地生成大量的条件FP-树,且耗费大量存储空间和时间。为此,采用矩阵技术统计约束子树中的频繁项集和频繁项集的支持度,以进行数据挖掘。实验结果表明,该频繁模式挖掘算法是有效的,具有较高的时间效率及空间 效率。     

Apriori算法的优化方法

关联规则是数据挖掘的主要技术之一,是指从一个大型的数据集中发现有趣的关联或相关关系,即从数据集中识别出频繁项集,然后再利用这些频繁集创建描述关联规则的过程.频繁项集挖掘是关联规则挖掘的主要步骤,在频繁项集挖掘中,需要大量进行两个操作:判断两个k-项集是否是前k-1项相同且最后一项不同,即连接步;判断一个项集是否为另一个项集的子集,即剪枝步,通过减少连接操作和剪枝操作的循环次数,以此来提高Apriori算法的效率.     

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

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

数据流上近似非可导项集的挖掘算法

频繁项集是通过对大规模数据进行挖掘获取的代表数据模式的知识结构.非可导频繁项集作为频繁项集的有效压缩方式,能够高效深入地挖掘海量数据、稠密数据与数据流当中的规律.针对项集在计算界限值时代价昂贵的缺点,提出了近似可导项集的概念,并基于纵向数据格式实现了挖掘算法MANDI,能够提高支持度计算和项集间操作的速度.另外,为了满足数据流实时、快速的特点,讨论并证明了近似可导项集的增量性质,提出了可动态更新的算法UANDI.通过实验验证了两种算法的可行性和有效性.     

基于双阈值Apriori算法和非频繁项集的关联规则挖掘方法

针对从本文数据集中的正负关联规则挖掘问题,提出一种基于双阈值Apriori算法和非频繁项集的挖掘方法。首先,对通过逆文档频率(IDF)对语料库中的项(项集)进行加权,筛选出前N%的项集。然后,通过提出的双支持度阈值Apriori算法来提取频繁项集和非频繁项集,以此降低非频繁项集的数量。最后,通过置信度和升降度阈值的判断,分别从频繁项集和非频繁项集中挖掘正负关联规则。其中,创新性的利用了非频繁项集来挖掘正负关联规则。在一个医学文本数据集上的实验结果表明,提出的方法能够有效挖掘出正负关联规则,且能够大大降低项集和规则数量。     

频繁项集挖掘算法的研究

频繁项集挖掘是数据挖掘领域的一个重要部分。随着大量数据不停地收集和存储,人们总希望从这些数据中找到内在的联系来为我们服务,频繁项集的挖掘算法有许多,如Apriori算法,fp-growth算法就是经典的频繁项集关联挖掘算法,文章重点分析了apriori的算法思想、算法描述及实际应用,同时也简要介绍了fp=growth算法思想。     

基于等价类的关联规则挖掘矩阵算法

关联规则挖掘算法中的Apriori算法利用查找频繁项集来发现数据集中的关联规则,算法思路简单容易实现;但在由k-1次频繁项集生成k次频繁项集时需反复查找数据库,效率较低,在寻找高次频繁项集时其低效性更加明显;矩阵算法是通过直接查找高次频繁项集,避免了反复查找数据库,但要存储大量的非频繁项集,且查找低次频繁项集速度较慢。文中提出的矩阵等价类算法,利用等价关系进一步降低矩阵算法的时间空间复杂度,然后通过项目相似度直接求取所有最大频繁项集。实验结果证明了算法的可行性、高效性。     

基于等价类的关联规则挖掘矩阵算法

关联规则挖掘算法中的Aprori算法利用查找频繁项集来发现数据集中的关联规则,算法思路简单容易实现;但在由k-1次频繁项集生成k次频繁项集时需反复查找数据库,效率较低,在寻找高次频繁项集时其低效性更加明显;矩阵算法是通过直接查找高次频繁项集,避免了反复查找数据库,但要存储大量的非频繁项集,且查找低次频繁项集速度较慢.文中提出的矩阵等价类算法,利用等价关系进一步降低矩阵算法的时间空间复杂度,然后通过项目相似度直接求取所有最大频繁项集.实验结果证明了算法的可行性、高效性.     

数据立方体与频繁项集的统一计算框架研究

数据立方体和频繁项集挖掘分别是数据仓库和数据挖掘领域的重要技术，已开展了大量的相关研究工作，取得了较好的进展.数据立方体和频繁项集挖掘依据各自的数据单元和项集构造了类似的代数格（Lattice）结构;数据立方体的等价类上界单元与频繁项集挖掘的闭项集也是相对应的.如果能够论证二者的统一性，则可以为彼此提供更广泛的研究思路，有利于两种技术的相互促进，如：在数据库中利用冰山立方体计算实现频繁项集挖掘来避免数据迁移、利用频繁项集挖掘算法优化数据立方体计算等.之前的工作没有将二者系统地结合起来研究，也没有建立二者之间较为完整的联系.本文在深入研究数据立方体的计算和频繁项集挖掘的过程后，将二者有效地结合在一起，提出了统一的计算框架，给出了二者众多计算性质和方法之间的映射关系，进行了相关概念泛化，具体地建立了冰山立方体、浓缩立方体和商立方体等主要数据立方体计算与相应频繁项集挖掘方法的对应关系.通过算法和实验进一步论证统一计算的有效性：（1）将频繁项集挖掘事务集导入关系数据库，用冰山立方体计算方式进行频繁项集挖掘，从而在数据库中用标准的或扩展的SQL可以实现对关系表进行频繁项集挖掘;（2）验证了浓缩立...     

数据流中基于最近数据的动态维护Generator表示法

数据流中频繁的数据更新使得重新挖掘整个数据集显得比较困难。该文提出了在数据流中,基于最近数据的动态维护Generator表示方法。通过界定边界项集,使得由数据更新可能引起的项集变化能在边界集中被检测到,而无须保存所有频繁集,使处理限定在仅与更新相关的项集范围之内,取得了较好效果。     

基于FIUT结构增量式频繁项集挖掘

增量式频繁项集挖掘是当前研究的热点,基于FP-Growth的Pre-FUFP算法有效处理了频繁模式的更新,但需递归遍历FP-tree,导致效率较低。提出Pre-FIUT算法,引入频繁超度量树结构,提高了获得频繁项集挖掘效率;基于FIUT的Pre-FIUT可通过查看频繁超度量树叶子结点的支持度确定频繁项集,并与次频繁项集概念相结合进行增量式频繁项集挖掘。实验表明,Pre-FIUT算法能快速扫描和更新数据,合理利用内存,精确获得频繁项集。