基于排序FP-树的频繁模式高效挖掘算法

FP-growth算法是目前较高效的频繁模式挖掘算法之一。在FP-growth算法中,FP-树及条件FP-树的构造和遍历占了算法绝大部分的时间,如果能减少这方面的时间,则有望进一步改善算法的效率。本文给出了一个频繁模式挖掘算法SFP-growth。算法通过将FP-树有序化及采用高效排序算法等措施来提高FP-树构造的效率,从而使算法达到较高的效率。实验结果表明,SFP-growth是一个高效的频繁模式挖掘算法,其性能优于Apriori、Eclat和FP-growtn算法。

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

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

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

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

基于合并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算法具有更优的性能。

Web数据中频繁模式树的挖掘

为了高效地从半结构化WEB数据中挖掘频繁模式树,提出了把半结构化数据表示为标记、有序树,并基于最右路径扩展技术在有序树中发现所有频繁模式树的算法.其基本思想是,首先从只有一个节点的模式树开始,而新增节点只能通过添加到最右路径上来生成新的模式树,另外,还通过维护最右叶子出现次数列表来实现支持度的逐步计算.理论分析和试验结果表明该算法是可行的,并且具有计算性能线性于最大频繁模式总和的优点.

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

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

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

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

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

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

快速更新全局频繁项目集

数据挖掘中的频繁项目集更新算法研究是重要的研究课题之一.目前已有的频繁项目集更新算法主要针对单机环境,有关分布式环境下的全局频繁项目集的更新算法的研究尚不多见.为此,提出了快速更新全局频繁项目集算法(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方法生成实验数据进行分析,实验结果验证了该算法在时间上的优势.

基于最右扩展枚举的半结构化数据最大模式挖掘方法研究

本文以标记有序树作为半结构化数据的数据模型 ,研究了半结构化数据的树状最大频繁模式挖掘问题 .已有挖掘算法通常挖掘所有频繁模式 ,其中很多模式为其它模式的子模式 ,针对该问题 ,设计实现了一种最大模式挖掘算法 .该算法采用最右扩展枚举方法无重复枚举所有候选模式 ,利用频繁模式扩展森林实现高效剪枝扩展和挖掘频繁叶模式 ,通过计算频繁叶模式间的包含关系挖掘树状最大频繁模式 .

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

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

一种改进的FP_growth算法

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