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

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

基于FP-tree挖掘密集型数据最大频繁模式算法

Fp-growth算法是当前挖掘频繁项目集算法中速度最快,应用最广,并且不需要候选集的一种挖掘关联规则的算法．但是,Fp-growth算法也存在着算法结构复杂和空间利用率低等缺点．在FP-tree结构的基础上提出了密集型数据最大频繁模式挖掘算法FP-DMax．算法FP-DMax只需要2次扫描数据库,在挖掘过程中不产生候选项集,大大提高了算法的时空效率．实验表明,算法FP-DMax在挖掘密集型数据最大频繁模式方面是高效的．

基于Fp树的加权频繁模式挖掘算法

提出一种不产生候选项目集的加权频繁模式挖掘算法。对每个项目集权重进行归一化操作,避免加权支持率大于1,证明该算法满足加权向下封闭性。在此基础上,构建基于加权Fp树的剪枝策略。实例分析和实验结果表明,该算法能减少加权频繁项目集生成过程中的计算量,提高加权频繁项目集的生成效率。

基于合并FP树的频繁模式挖掘算法

FP-growth算法是一个挖掘频繁模式的有效算法,但它在挖掘过程中需要产生大量的条件FP树,因此其时空效率不够理想。提出了DFP-mine算法,通过在改进的FP树上合并子树来挖掘频繁模式,并在挖掘过程中结合了自顶向下和自底向上的双向搜索策略。理论分析和实验表明本文提出的算法具有较好的时空效率。

基于FP-参考树/表的频繁模式挖掘算法

通分析FP-growth算法中包含的冗余操作,引入数据结构FP参考树/表,改变FP-growth算法中条件模式基的存储和生成方式,提出了新的FPRSG算法,高效地解决了频繁模式挖掘问题。理论分析与实验结果表明,FPRSG算法优于FP-growth算法。

基于有限个条件FP_树中挖掘频繁模式

在数据挖掘中发现关联规则是一个基本问题,而关联规则发现中最昂贵的步骤便是寻找频繁模式。FP_growth(FrequentPatern growth)方法在产生长短频繁项集时不产生候选项集,从而大大提高了挖掘的效率,但是FP_growth在挖掘频繁模式时候产生大量的条件FP树从而占用大量空间,对FP_growth进行研究并提出一种改进算法,该算法不仅利用FP_growth算法所有优点而且避免了FP_growth的缺陷。主要通过建立有限棵条件FP树(数目为事务数据库的属性个数)来挖据长短频繁模式,大大节省了FP_growth算法所需要空间,实验证明该文算法是有效的。

基于IS~±树模型的频繁模式挖掘

IS-树是一种新型的全文存储索引模型.提出一种基于扩展I-S树模型的频繁模式挖掘算法.和FPgrowth方法一样,算法直接构造频繁项集,不进行Apriori算法所采用的代价很高的候选集产生与测试操作.然而它比FP-树模型具有更多的优点:只需扫描一遍事务库;挖掘任务只局部关联于一棵根树;动态更新性好,仅做增量变化.实验表明,其具有与FP-growth算法相当甚至更高的效率.更重要的是,IS+树模型同时是一种事务库的良好索引形式,具有高效支持事务查询的能力.

一种基于FP阵列技术的频繁模式挖掘算法

在FP-growth算法中,为了产生条件FP树,必须扫描FP树两次。提出一种新颖的FP阵列技术,将FP-tree数据结构与FP阵列有效地结合起来,直接从FP阵列得到频繁项的计数,从而省略了第一次扫描,节省了时间。尤其对于稀疏数据库,该算法在执行时间上比原FP-growth算法具有更优的性能。

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

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

一种高效的闭频繁模式挖掘算法

为了构造条件FP树,必须两次遍历FP树。提出一种FP阵列技术,直接从FP阵列得到频繁项的计数,从而省略了第一次遍历。为了检查闭频繁项集,采用FP树的一种变形结构,并将它与FP阵列结合起来,提出了一种高效的闭频繁模式挖掘算法。实验表明,该算法具有很好的性能。

基于约束FP树的天体光谱数据相关性分析系统研究

从海量天体光谱数据中挖掘光谱数据特征和物理化学性质之间内在的、隐含的相关性,是人类探索天文规律的一种有效方法。利用基于约束FP树的关联规则挖掘方法作为天体光谱数据相关性分析手段,采用VC++和Oracle9i作为开发工具,设计与实现了天体光谱数据相关性分析系统,给出了其系统的软件体系结构和模块功能,并对光谱数据预处理、背景知识表示、CFP树构造、频繁模式提取及关联规则生成等关键技术以及关键模块的实现技术,进行了详细描述。系统运行结果表明,利用关联规则来描述、分析天体光谱数据特征和物理化学性质之间存在的相关性,是可行的和有价值的,从而为寻找天体规律提供了一种有效手段。

基于FP树的挖掘关联规则的增量式更新的研究

关联规则的高效维护算法研究是当前数据库研究的热点之一。本文研究了事务数据库中关联规则的增量式更新问题,提出了基于频繁模式树的关联规则增量式更新算法的设计思路,以处理最小支持度或事务数据库发生变化后关联规则的更新问题。

一种基于映射方法的改进频繁模式增长算法

文章介绍了知识发现中关联规则挖掘算法的基本思想及其性能,分析了FP-tree算法在关联规则挖掘中存在耗费巨大空间存贮的问题,提出了一种运用投影技术改进的频繁模式增长算法,该算法改善FP-tree构造,实验结果表明,运用投影技术改进的频繁模式增长算法可以提高关联规则挖掘效果。

快速更新全局频繁项目集

数据挖掘中的频繁项目集更新算法研究是重要的研究课题之一.目前已有的频繁项目集更新算法主要针对单机环境,有关分布式环境下的全局频繁项目集的更新算法的研究尚不多见.为此,提出了快速更新全局频繁项目集算法(fast updating algorithm for globally frequent itemsets,简称FUAGFI).该算法主要考虑数据库记录增加时全局频繁项目集的更新情况.FUAGFI利用已建立的各局部频繁模式树(frequent pattern tree,简称FP-tree)及已挖掘的全局频繁项目集,可有效地降低网络通信量,提高全局频繁项目集的更新效率.实验结果表明,所提出的更新算法是行之有效的.

FP-Growth算法的改进

基于FP树的FP-Growth算法在挖掘频繁模式过程中需要两次扫描事务集来建立FP树,这不仅降低了算法的效率,而且给数据库服务器带来负担。在原有经典FP-Growth算法的基础上,提出一种基于二维表的方法对原算法进行改进,改进算法通过使用二维向量记录频繁度仅需遍历一次事务集,从而省略FP-Growth算法在生成新条件FP树时对条件模式基的第一次遍历,大大缩短了建立FP树的时间。实验结果表明,该算法的改进优于经典算法。

一种基于聚合链的改进FP-Growth算法

提出了一种基于聚合链挖掘频繁模式的改进FP-growth算法.该算法引入聚合链的单链表结构,改进了FP树结构.改进后的FP树是单向的,每个结点只保留指向父结点的指针,节省了树空间;相同项的不同节点的路径信息压缩进聚合链中,避免了生成节点链和条件模式库.用Agrawa方法生成实验数据进行分析,实验结果验证了该算法在时间上的优势.

基于MapReduce的频繁项集并行挖掘算法

现有FP-growth频繁集挖掘算法在处理大数据时存在时空效率不高的问题,且内存的使用随着数据的增加已经无法满足把待挖掘数据压缩存储在单个内存中,为此,提出一种基于MapReduce模型的频繁项集并行挖掘算法。该算法采用一种基于key/value键值对直接扫描value寻找条件模式基的方式,同时通过在原有FP-tree树节点中新增一个带频繁项前缀的域空间来构建一颗新的条件模式树NFP-tree,使得对一项频繁项的条件模式基进行一次建树一次遍历就可以得到相应的频繁项集。对所提出的算法在Hadoop平台进行了验证与分析,实验结果表明该算法效率较传统FP-growth算法平均提高16.6%。

基于频繁模式树的涉恐情报关联分析

【目的/意义】利用数据挖掘技术在海量数据中快速、准确、有效的发现涉恐线索并及时处置是反恐工作的重要手段之一。【方法/过程】本文研究如何利用频繁模式树对涉恐基础数据进行挖掘,提取涉恐特征的频繁项集。首先通过对数据库中的涉恐人员信息进行涉恐特征计数排序并建立频繁模式树,然后在树结构中递归遍历发现满足最小支持度阈值的频繁项集。【结果/结论】文中的方法可以快速发现大量基础数据中的涉恐关联属性,有利于在系统中自动搜索重点涉恐人员,为反恐预警系统提供决策参考。通过与其他产生关联规则的方法结合使用,还可以发现暴恐活动中不同因素的因果关系。

一种改进的FP_growth算法

FP_growth算法是一种不产生候选项集的关联分析算法,克服了Apriori算法需要产生候选项集的缺点,提高了效率。但是在挖掘FP树时,没有按长度对条件模式基排序,再按条件模式基中各项的长度判断各项之间的子集关系从而快速挖掘频繁项集。实验表明改进后的算法比原算法在效率上有了显著提高。