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

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

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

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

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

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

不确定数据频繁项集挖掘方法综述

近几年来,不确定数据广泛出现在传感器网络、Web应用等领域中。不确定数据挖掘已经成为了新的研究热点,主要包括聚类、分类、频繁项集挖掘、孤立点检测等方面,其中频繁项集挖掘是重点研究的问题之一。综述了传统的频繁项集挖掘的两类基本算法,分析了在此基础上提出的适用于不确定数据以及不确定数据流的频繁项集挖掘的方法,并探讨了今后可能的研究方向。     

基于差分隐私的不确定数据频繁项集挖掘算法

基于不确定数据的频繁项集挖掘算法已经得到了广泛的研究。对于记录用户敏感信息的不确定数据,攻击者可以利用自己掌握的背景信息,通过分析基于不确定数据的频繁项集,从而获得用户的敏感信息。为了从不确定的数据集中挖掘出基于期望支持度的前K个最频繁的频繁项集,并且保证挖掘结果满足差分隐私,在本文中,FIMUDDP算法（Frequent Itemsets Mining for Uncertain Data based on Differential Privacy）被提出来。FIMUDDP利用差分隐私的指数机制和拉普拉斯机制确保从不确定数据中挖掘出的基于期望支持度的前K个最频繁的频繁项集和这些频繁项集的期望支持度满足差分隐私。通过对FIMUDDP进行理论分析和实验评估,验证了FIMUDDP的有效性。     

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

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

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

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

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

针对PFIM算法中频繁概率计算方法的局限性,且挖掘时需要多次扫描数据库和生成大量候选集的不足,提出EPFIM(efficient probabilistic frequent itemset mining)算法。新提出的频繁概率计算方法能适应数据流等项集的概率发生变化时的情况;通过不确定数据库存储在概率矩阵中,以及利用项集的有序性和逐步删除无用事物来提高挖掘效率。理论分析和实验结果证明了EPFIM算法的性能更优。     

基于有序树的不确定数据最大频繁项挖掘算法

针对UF-tree中项集存在的数据和路径冗余的问题,设计了有序的压缩不确定树SCUF-tree,在节点中存储元素的不同支持度,达到压缩存储空间和方便移植已有的确定数据最大频繁项集算法的目的。结合最大频繁项集挖掘算法MMFI的设计思想,提出了一种挖掘不确定最大频繁项集算法UMMFI算法,并采取逐层逐个的NBN策略挖掘不确定最大频繁项集。实验结果表明,UMMFI算法具有较好的时空效益和适应性。     

基于不确定数据的可能频繁闭序列模式挖掘

; 对于不确定数据的频繁序列模式挖掘,会导致可能频繁模式数量的指数级出现,其中有些无用的挖掘结果,引起频繁序列的冗余。针对上述不足, 提出了可能频繁闭序列模式(pfcsp)的定义, 以及一种基于不确定数据的可能频繁闭序列挖掘算法U-FCSM。此算法中,基于一种元组不确定数据模型,计算序列的可能频繁性,应用BIDE算法的闭序列思想判断可能频繁序列是否是可能频繁闭序列模式。为了减少搜索空间与避免冗余的计算,应用了几个剪枝与边界技术。U-FCSM算法的有效性与效率通过大量的实验得以表明。     

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

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

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

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

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

频繁闭项集挖掘是许多数据挖掘应用中的重要问题。为减少候选项集数量和降低支持度计算的开销,提出一种新的深度优先搜索频繁闭项集(DFFCI)的算法。将改进的压缩频繁模式树(CFP-Tree)表示的数据集信息投影到划分矩阵,使用二进制向量逻辑运算计算支持度,简化了计算过程,减少了时间开销;采用基于支持度预计算技术的全局2-项剪枝和局部扩展剪枝,有效削减了搜索空间。实验结果表明该算法的性能优于其他主流深度优先算法。     

基于有序FP-tree的最大长度频繁项集挖掘算法

频繁项集的挖掘受到大量候选频繁项集和较高计算花费的限制,只挖掘最大长度频繁项集已满足很多应用。提出一种基于有序FP-tree结构挖掘最大长度频繁项集的算法。即对有序FP-tree的头表进行改造,增加一个max-level域,记录该项在有序FP-tree中的最大高度。挖掘时仅对max-level 大于等于已有最大长度频繁项集长度的项进行遍历,不产生条件模式基,无需递归构造条件FP-tree,且计算出最大长度频繁项集的支持度。实验结果表明该算法挖掘效率高、速度快。     

关联规则中基于降维的最大频繁模式挖掘算法

基于FP-tree的最大频繁模式挖掘算法是目前较为高效的频繁模式挖掘算法,针对这些算法需要递归生成条件FP-tree、产生大量候选最大频繁项集等问题,在分析FPMax、DMFIA算法的基础上,提出基于降维的最大频繁模式挖掘算法(BDRFI)。该算法改传统的FP-tree为数字频繁模式树DFP-tree,提高了超集检验的效率;采用的预测剪枝策略减少了挖掘的次数;基于降低项集维度的挖掘方式,减少了候选项的数目,避免了递归地产生条件频繁模式树,提高了算法的效率。实验结果表明,BDRFI的效率是同类算法的2~8倍。     

基于改进的FP-tree的频繁模式挖掘算法

FP-growth算法是一种基于FP-tree数据结构的高效的频繁模式挖掘算法,它不产生候选集。构造频繁模式树FP-tree需扫描数据库两次,在第二遍扫描中还扫描了那些仅包含了非频繁项的事务,针对此问题,在深入分析了FP-tree特性的基础上, 改进了FP-tree构造过程,同时用一种基于Hash表的辅助存储结构,节省了项目查找时间,提高了挖掘效率。