基于FP-Tree的共享前缀频繁项集挖掘算法

在数据挖掘中发现关联规则是一个基本问题,而发现频繁项集是关联规则挖掘中最基本、最重要的问题。提出了基于FP-Tree的共享前缀频繁项集挖掘算法－FP-SPMA算法。构造FP-Tree来压缩事务数据库,通过共享前缀和前瞻剪枝快速减小候选项集,无需递归构造条件模式树,算法性能有明显的提高。     

基于前缀树的高效频繁项集挖掘算法

针对频繁项集挖掘时间与空间效率低的问题,提出一种基于前缀树的高效频繁项集挖掘算法,通过对事务集进行预处理,创建索引表并分配索引编号,保证前缀树中事务顺序的一致性,根据索引编号等信息创建紧凑的前缀树,采用自底向上的挖掘与投影的方式挖掘出频繁项集。实验结果表明,该算法挖掘效率高、占用空间少。     

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

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

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

针对FP-growth算法存在动态维护复杂、在挖掘过程中需要递归地创建大量的条件频繁模式树,导致时空效率不高等不足,本算法在压缩前缀树的基础上,通过调整树中节点信息和节点链,采用深度优先的策略挖掘频繁模式,无需任何附加的数据结构,极大地减少了系统资源的消耗,减少树的规模和遍历次数,挖掘效率大大提高。     

基于AC算法的比特流频繁序列挖掘

为解决比特流频繁序列挖掘效率不高以及易受用户数据影响而导致准确率低的问题,首先从理论上论证了短频繁序列挖掘存在的局限性,根据不同长度的频繁序列挖掘时存在的特点,将其分为长频繁序列与短频繁序列,提出比特流协议头部字段定位算法;基于AC多模式匹配算法分别针对长、短频繁序列挖掘的不同特点,提出了相应的挖掘方法,提高了挖掘结果的准确性。最后通过实验验证了所提算法的有效性。     

基于XML的完全频繁查询模式挖掘算法

使用树结构建模对XML查询进行研究,提出了一种基于树同构的查询包含检测方法。采用最右分枝扩展方法,系统地枚举查询模式树的同根子树。在枚举过程中,采用Diffset结构记录包含同根子树的事务集的查询事务标识,并给出挖掘算法DiffFRSTMiner。实验结果证实了该算法合理、高效,并可以减少一定的内存开销。     

基于路径的频繁子图挖掘算法研究

图挖掘是数据挖掘的一个重要研究方向,而图挖掘主要集中在图数据集内频繁子图的挖掘。频繁子图挖掘技术的关键是建立有效机制减少冗余候选子图,以便高效计算和处理所需的频繁子图。提出了一种基于路径的频繁子图挖掘算法,该算法首先找出所有频繁边从而挖掘出频繁单路径,然后通过组合、双射和操作扩展出较多的频繁路径,再通过连接操作产生所有频繁子图候选集。通过定理证明了该算法的正确性和完整性,从理论上分析了该算法时间复杂度低于现有的算法,最后进行了2个图数据集实验,在候选集产生的数量和时间性能2方面验证了算法的优越性。     

基于XML数据的频繁模式挖掘算法*

结合XML文档的特点,采用XML数据模型XOEM和压缩结构树的存储结构,提出了一种高效的XML数据的频繁模式挖掘算法──AFPMX算法,并从理论和实验两方面证明了该算法是可行和有效的。     

一种基于前缀节点的频繁子图挖掘算法

基于频繁子树挖掘算法中的前缀节点思想,将模式图分为图核—分支—连接向量三个部分,提出了CBE算法。对在分支上扩展得到的候选模式图,CBE算法能够在常数时间内完成规范化判定。通过实验证明CBE算法的子图挖掘效率有显著提高。     

基于频繁叶模式的XML最大频繁查询模式挖掘算法

在XML频繁查询模式挖掘稠密数据集、长数据集中,为克服项目集挖掘过程中挖掘的项目过多、不利于结果利用等问题,提出基于频繁叶模式的最大频繁查询模式挖掘算法MFRSTMiner。该算法通过构造频繁模式扩展森林,在扩展森林的叶节点中挖掘出最大频繁子树。试验结果表明该算法能够有效地挖掘动态事务集的最大频繁查询模式。     

XML数据流分页频繁子树挖掘研究

随着XML数据流的广泛应用,从挖掘XML数据流中发现知识具有重要的理论与应用价值.相比其他频繁模式挖掘,大型XML文档与数据流的频繁子树挖掘面临困难：XML数据流不可能整体在内存解析;对XML数据流分段挖掘必须考虑XML数据的半结构化特征等.针对上述问题,提出数据流分页频繁子树挖掘模型Tmlist.Tmlist对XML数据流进行分页,管理跨页节点及频繁候选子树的跨页增长,逐页挖掘频繁子树;频繁候选子树的增长根据根节点层次由浅至深地在最右路径加入频繁候选节点,避免以低层次为根子树的重复性递归增长;对频繁候选子树采用子树拓扑序列和最右路径共同标识,子树的增长不需要对子树前缀进行匹配,省去前缀节点存储与匹配开销;以页面最小支持度对频繁候选子树按页筛选,子树按页面衰减度衰减支持度、剪枝.Tmlist在可控误差范围内降低频繁子树挖掘的空间消耗,提高内存利用率和挖掘效率.     

Efficient Mining of Frequent Closed XML Query Pattern

Previous research works have presented convincing arguments that a frequent pattern mining algorithm should not mine all frequent but only the closed ones because the latter leads to not only more compact yet complete result set but also better efficiency. Upon discovery of frequent closed XML query patterns, indexing and caching can be effectively adopted for query performance enhancement. Most of the previous algorithms for finding frequent patterns basically introduced a straightforward generate-and-test strategy. In this paper, we present SOLARIA＊, an efficient algorithm for mining frequent closed XML query patterns without candidate maintenance and costly tree-containment checking. Efficient algorithm of sequence mining is involved in discovering frequent tree-structured patterns, which aims at replacing expensive containment testing with cheap parent-child checking in sequences. SOLARIA＊ deeply prunes unrelated search space for frequent pattern enumeration by parent-child relationship constraint. By a thorough experimental study on various real-life data, we demonstrate the efficiency and scalability of SOLARIA＊ over the previous known alternative. SOLARIA＊ is also linearly scalable in terms of XML queries＇ size.     

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

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

改进的频繁模式挖掘算法

为解决传统频繁模式挖掘算法效率不高的问题,提出了一种改进的基于FP-tree （Frequent pattern tree）的Apriori频繁模式挖掘算法.首先,在Apriori算法的连接步加入连接预处理过程;其次,对CP-tree （Compact Pattern tree）进行扩展,构造了一个新的树结构ECP-tree （Extension of Compact Pattern tree）,新的树结构只需对数据库进行一次扫描就能构造出一棵紧凑的前缀树,且支持交互式挖掘与增量挖掘;然后,将改进点与APFT算法结合,用于挖掘频繁模式;最后,使用UCI数据库中两个数据集进行实验.实验结果表明：改进算法具有较高的挖掘效率,频繁模式挖掘速度显著提升.     

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

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

一种高效频繁子图挖掘算法

由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题--频繁子图挖掘.诸如化学、生物学、计算机网络和WWW等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间复杂性是O(n³·2ⁿ),其中,n是图集中的频繁边数.提出算法的时间复杂性是O〔2ⁿ·n^2.5／logn〕,性能提高了O(√n·logn)倍.实验结果也证实了这一理论分析.     

一种基于拓扑信息的物流频繁路径挖掘算法

为了高效地从海量物流数据中获取频繁路径,根据物流网络及物流的特征设计了一种物流数据模型以及一种充分考虑了物流网络拓扑信息的频繁路径序列挖掘算法PMWTI(Path Mining With Topology Information).在PMWTI中设计了一种用于候选路径序列深度剪枝的代价容忍度剪枝方法,该方法在利用Apriori性质剪枝的基础上进一步去除了部分不可能是频繁路径序列的候选路径序列,这在一定程度上缩减了候选路径序列规模,从而减少了对数据集的扫描.实验表明,相比没有采用该剪枝方法的同等算法,PMWTI具有更高的频繁路径挖掘效率.     

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

如何高效地挖掘频繁项集是关联规则挖掘的主要问题。该文根据集合论和矩阵理论,提出一种基于矩阵的频繁项集挖掘算法。该算法只需扫描数据库一次,就能把所有事务转化为矩阵的行,把所有项和项集转化为矩阵的列,在对矩阵操作时能一次性产生所有频繁项集,且当支持度阈值改变时无需重新扫描数据库。实验结果表明,该算法的挖掘效率高于Apriori算法。     

挖掘频繁闭序列的一种改进算法

由于频繁闭序列在数量上要远小于频繁序列且与频繁序列有着相同的表达能力在近几年倍受关注．频繁闭序列挖掘过程中最耗时同时也是最关键的步骤是序列间的包容关系检查，作者分析了频繁闭序列自身的特点以及已有的频繁闭序列挖掘算法，提出了一个挖掘频繁闭序列的算法FCSeq，该算法通过引入快速包含检查策略大大减少了不必要的包容关系判断，对提高算法的性能有着显著的作用，实验表明该算法有效．