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

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

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

发现最大频繁项目集是多种数据挖掘应用中的重要问题 .在应用中用户需要调整最小支持度 ,以发现更有用的最大频繁项目集 .为此提出了一种最大频繁项目集更新算法 (UMFPA) ,该算法通过对频繁模式树(FP Tree)中的频繁项目头表 (HTable)增加两个域 ,从而将减少在数据库不变而最小支持度变化的情况下的更新挖掘最大频繁项目集的费用 .实验结果表明 。

一种改进的基于FP-Tree的高效挖掘最大频繁项目集算法

为了解决最大频繁项目集算法DMFIA(discover maximum frequent itemsets algorithm)在挖掘候选项目集维数较大而最大频繁项目集维数较小的情况下产生大量候选项目集的问题,提出一种改进的基于FP-Tree(frequent pattern tree)的最大频繁项目集挖掘的FP-EMFIA算法;该算法在挖掘过程中根据项目头表,采用自上而下和自下而上的双向搜索策略,并通过条件模式基中的频繁项目和较小维数的非频繁项目集对候选项目集进行降维和剪枝,以减少候选项目集的数量,加速对候选集计数的操作。在经典数据集mushroom、chess和connect上的实验结果表明,FP-EMFIA算法在支持度较小时的时间效率优于DMFIA、IDMFIA(improved algorithm of DMFIA)和BDRFI(algorithm for mining frequent itemsets based on decreasing dimensionality reduction of frequent itemsets)算法的,说明FP-EMFIA算法在候选项目集维数较大时有相对优势。

关联规则中FP-tree的最大频繁模式非检验挖掘算法

基于FP-tree的最大频繁模式挖掘算法是目前较为高效的频繁模式挖掘算法,针对这些算法需要递归生成条件FP-tree、做超集检验等问题,在分析DMFIA-1算法的基础上,提出了最大频繁模式的非检验挖掘算法NCMFP。该算法改进了FP-tree的结构,使挖掘过程中不需要生成条件频繁模式树也不需要超集检验。算法采用的预测剪枝策略减少了挖掘的次数,采用的求取公共交集的方式保证了挖掘结果的完整性。实验结果表明在支持度相对较小情况下,NCMFP的效率是同类算法的2～5倍。

基于FP-tree的快速挖掘全局最大频繁项集算法

挖掘最大频繁项集的算法多基于局部数据库,为此提出了一种基于频繁模式树的快速挖掘全局最大频繁项集算法。该算法首先挖掘出所有全局频繁项目组成集合,然后各个节点根据该集合构建局部频繁模式树,最后将该集合作为全局最大频繁候选项集,采用自顶向下策略挖掘出所有的全局最大频繁项集。与类Apriori算法相比,该算法采用的频繁模式树结构能大幅度降低数据库扫描次数和运行时间;自顶向下的策略能大幅度减少候选项集数和通信量。实验结果表明,该算法是快速和高效的。

基于改进FP-Tree的最大频繁项集高效挖掘算法

基于FP-Tree的FP-Max算法在挖掘最大频繁集时需多次递归建立条件模式树耗费大量存储空间,这大大降低了算法的挖掘效率。提出了一种基于改进FP-Tree的最大频繁集快速挖掘算法—FP-EMax算法。该算法无需建立条件模式库大大减少了存储空间开销,采用预剪枝策略减少条件模式树的构造次数及子集检测次数,从而算法的挖掘效率大大提高。最后通过实验证明FP-EMax算法在支持度较小的情况下较之于FP-Max及同类算法具有更好的性能。

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

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

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

挖掘最大频繁项目集是关联规则挖掘中的关键问题,基于Apriori产生候选项目集需要付出很高的代价,尤其是在存在大量强模式或长模式的时候.提出一种基于频繁模式树(FP-Tree)的最大频繁项目集挖掘算MFIP-Miner(maximum frequent itemsets pattern miner),其挖掘过程无需产生候选项集,从而提高挖掘效率。

最大频繁模式的快速挖掘与更新算法

挖掘和更新最大频繁模式是多种数据挖掘应用中的关键问题。之前的许多研究都是采用Apriori类的候选生成-检验方法或基于FP-Tree的方法,而产生大量候选和动态创建大量FP-Tree的代价太高,特别是在支持度阈值较小或存在长模式时。因此,文章提出了一种最大频繁模式的快速挖掘算法DMFP及更新算法IUMFP。DMFP算法利用前缀树压缩存放数据,并通过调整前缀树中节点信息和节点链直接在前缀树上采用深度优先的策略进行挖掘,而不需要创建条件模式树,从而大大提高了挖掘效率。算法IUMFP充分利用以前的挖掘结果减少发现更新数据中新的最大频繁模式的代价。

一种最大频繁模式的快速挖掘算法

挖掘最大频繁模式是多种数据挖掘应用中的关键问题。提出一种挖掘最大频繁模式的快速算法,该算法利用前缀树压缩存放数据,并通过调整前缀树中节点信息和节点链直接在前缀树上采用深度优先的策略进行挖掘,而不需要创建条件模式树,从而大大提高了挖掘效率。

一种基于前缀树的频繁模式挖掘算法

挖掘频繁模式是许多数据挖掘任务的关键步骤。基于FP-Tree的挖掘算法由于无须生成候进项集效率明显高于Apriori类算法,但FP-Tree结构存在动态维护复杂、而且在挖掘过程中需要递归地创建大量的条件FP-Tree,时空效率不高。因此,本文提出一种基于前缀树的新算法。该算法通过引入一种新结构—前缀树(Prefix Tree)用来压缩存放数据所相关信息,并通过调整前缀树中节点信息和节点键直接在Prefix Tree上采用深度优先的策略挖掘频繁模式,而不需要任何附加的数据结构,从而大大提高了挖掘效率。

基于频繁模式树的约束最大频繁项集挖掘算法

多数最大频繁项集挖掘算法产生候选项目集的代价很高,而实际应用中用户只关心部分关联规则。针对该问题,提出一种基于频繁模式树的约束最大频繁项集快速挖掘算法。该算法能随时删除不满足约束条件的项集,无需生成候选项目集,由此提高挖掘效率。实验结果证明,该算法的效率优于同类算法。

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

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

差分隐私下的一种频繁序列模式挖掘方法

频繁序列模式挖掘是数据挖掘领域的1个基本问题,然而模式本身及其支持度计数都有可能泄露用户隐私信息.差分隐私(differential privacy,DP)作为一种新出现的隐私保护技术,定义了一个相当严格的攻击模型,通过添加噪音使数据失真达到隐私保护的目的.由于序列数据内在序列性和高维度的特点,给差分隐私应用于频繁序列模式挖掘带来了挑战.对此提出了一种基于交互式差分隐私保护框架的频繁序列模式挖掘算法Diff-FSPM(differential-privacy frequent sequential pattern mining).该算法利用指数机制获取最优序列长度,并采用一种维规约策略获得原始序列数据集的规约表示,有效降低序列维度的影响;应用前缀树压缩频繁序列模式,利用拉普拉斯机制产生的噪音扰动频繁模式的真实支持度计数,同时采用闭频繁序列模式和Markov假设,有效分配隐私预算,并利用一致性约束后置处理,增强输出模式的可用性.理论角度证明算法满足ε-差分隐私,实验结果验证算法具有较好的可用性.

一种基于前缀广义表的关联规则增量式更新算法

关联规则挖掘是数据挖掘研究的一个重要方面 ,关联规则的高效维护算法研究是当前研究的热点 .传统更新算法与Apriori算法框架一致 ,要多遍扫描数据库并产生大量的候选项目集 .为此 ,该文对FP tree进行了改进 ,引入了前缀广义表———PG List,并提出了基于PG List的关联规则挖掘 (MARBPGL)与增量式更新算法(IUABPGL) .算法MARBPGL仅须扫描数据库两遍 ,算法IUABPGL在最坏的情况下仅须扫描原数据库一遍 ,扫描新增数据库两遍 ,且两个算法均无须生成候选项目集 ,避免了产生“知识的组合爆炸” ,提高了挖掘和维护的效率 .理论分析和实验结果表明该文提出的算法是有效可行的 .

一种基于有向树挖掘Web日志中最大频繁访问模式的方法

提出了一种基于Apriori思想的挖掘最大频繁访问模式的s-Tree算法。该算法使用有向树表示用户会话,能挖掘出最大前向引用事务和用户的浏览偏爱路径;使用一种基于内容页面优先的支持度计算方法,能挖掘出传统算法不能发现的特定的用户访问模式;使用频繁模式树连接分层的频繁弧克服了图结构数据挖掘算法中直接连接两个频繁模式树要判断连接条件的缺点,同时采用预剪枝策略,降低了算法的开销。实验表明,s-Tree算法具有可扩展性,运行效率比直接采用图结构数据挖掘算法要高。

基于频繁模式树的约束最大频繁项目集挖掘算法研究

目前绝大多数频繁项目集(或最大频繁项目集)挖掘算法并没有考虑相关领域知识,其结果会产生许多无关的模式.因此,发现约束频繁(或约束最大频繁)项目集是多种数据挖掘应用中的关键问题,然而,这方面的研究工作却很少.为此该文提出了一种快速的基于频繁模式树(FP-tree:一种扩展前缀树结构)的约束最大频繁项目集挖掘及其更新算法.实验结果表明该算法是快速有效的.

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

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

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

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

分布环境中的并行频繁模式挖掘算法

频繁模式的并行挖掘算法是数据挖掘中重要的研究课题。目前已经提出的并行算法大多是基于Apriori或基于FP-tree。由于两者的固有局限性,而且在计算过程中需要多次同步,因而具有较低的性能。文章提出了一种基于分布数据库的并行挖掘算法。该算法尽可能地让每个处理器独立地挖掘,每个处理器基于前缀树采用深度优先搜索的策略挖掘局部频繁模式集,并通过相关性质尽量减少候选全局频繁模式的规模,减少网络的通信量和同步次数以提高挖掘效率。