无序嵌入式频繁予树挖掘算法

频繁模式挖掘的研究对象包括事务、序列、树和图。该文提出用模式增长方法在无序树构成的森林中挖掘嵌入频繁子树。利用规范化方法实现用唯一的形式表现无序树，根据待增长模式的拓扑结构确定其增长点并构造相应的投影库，将挖掘频繁子树模式问题转化为在各个投影库中寻找频繁节点的问题。     

高效挖掘无序频繁子树

频繁模式挖掘是数据挖掘领域的中一个重要问题，其研究范围包括事务，序列，树和图．频繁子树挖掘广泛应用于生物信息学，web挖掘，化合物结构分析和挖掘等领域．本文提出用模式增长方法在由无序树构成的森林中挖掘直接频繁子树．算法利用规范化方法将元序树化为为唯一的表示形式，利用最右路径扩展方法构造完整的模式增长空间，然后根据待增长模式的拓扑结构确定其增长点并构造相应投影库，从而将挖掘频繁子树模式问题转化为在各投影库中寻找频繁节点问题．通过与HybridTreeMiner算法的实验比较，表明其具有更高的效率。     

用模式增长方法挖掘嵌入式频繁子树

提出用模式增长方法在带标记有序树构成的森林中挖掘嵌入式频繁子树.算法利用最右路径扩展方法构造完整的模式增长空间,然后根据待增长模式的拓扑结构确定其增长点并构造相应投影库,从而将挖掘频繁子树问题转化为在各投影库中寻找频繁节点问题.这大大降低算法的复杂性.实验表明其具有较高的时空效率.     

基于模式增长的嵌入式频繁子树挖掘算法研究

针对传统挖掘算法会输出大规模频繁子树且其中包含较多冗余信息,使事物表达不够清晰完整,降低后续操作效率的问题,提出基于模式增长的嵌入式频繁子树挖掘算法.定义标签树,并分析挖掘任务,根据模式增长的基本性质,扫描森林数据库,建立与频繁子树模式对应的投影库,确定模式增长过程,设立增长框架.提出融合压缩思想,采用深度优化方式遍历所有子树的节点,构建融合压缩树,实现数据清理.基于数据清理结果组建拓扑序列,制定树与森林的拓扑编码,输入数据库与最小支持度数值,结合覆盖定理对频繁子树队列进行裁剪,完成挖掘.仿真结果表明,上述方法挖掘的数据信息更加丰富完整,挖掘效率更高.     

FVTreeMiner：无序频繁子树挖掘算法

在挖掘无序树频繁模式的过程中,大多数的算法都是先产生候选者,再进行模式匹配判断它是否为频繁子树.产生候选者本身就需要消耗很大的空间来保存,并且要在复杂的树结构里做匹配也是件难事,它会影响整个挖掘过程的效率.为了尽量避免产生不必要的候选者,提高发现频繁模式的效率,基于对相关算法的研究,引进树投影资料库的概念,并在RootedTreeMiner算法的基础上,采用其模式延伸方法和广度优先标准型式概念,提出子树频繁度、频繁可延伸点串的概念,从而更有效系统地枚举所有的频繁模式树,并给出无序频繁子树挖掘算法FVTreeMiner.经系列实验结果证实了该算法合理、高效,并可以减少一定的内存开销和运行时间开销.     

一种高效的最大频繁Embedded子树挖掘算法

提出了一种高效的最大频繁Embedded子树挖掘算法——CMPETreeMiner。该算法采用先序遍历序列存储树,并将节点的范围属性加入该序列,采用伪投影技术对频繁子序列进行投影,并对投影序列中的每个节点编码。在挖掘带编码的频繁子序列过程中,对频繁子序列进行高效剪枝,得到最大频繁Embedded子树,无需生成所有频繁Embedded子树。实验结果表明,CMPETreeMiner算法是高效可行的。     

基于投影分支的快速频繁子树挖掘算法

频繁子树挖掘在生物信息、Web挖掘等很多领域都具有较高的应用价值．在频繁子树挖掘中引入投影分支的概念,并提出基于投影分支的快速频繁子树挖掘算法——FTPB．FTPB算法充分利用树结构本身的特点,在计算投影分支的同时解决树同构的判断问题,扫描数据库后能够根据当前的频繁模式树直接生成新的频繁模式树,可减少数据库的扫描次数和候选模式的搜索空间,从而降低算法复杂度．理论分析和实验结果表明,该算法较其他同类算法相比具有较高的效率,是有效可行的．     

基于投影编码的频繁子树挖掘算法

频繁子树挖掘被广泛地应用于Web挖掘、生物信息学、XML数据挖掘等领域.提出一种新的算法--PETreeMiner.算法利用序列中无候选产生的技术--前缀投影技术来挖掘频繁子树.在树的先序遍历序列中加入结点的范围属性,在投影过程中进行编码,使得挖掘到的频繁子序列直接对应成一棵频繁子树.实验结果表明算法优于其他算法.     

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

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

基于覆盖模式的频繁子树挖掘方法

无序树常用于半结构化数据建模,对其进行频繁子树挖掘有利于发现隐藏的知识。传统的频繁子树挖掘方法常常输出大规模且带有冗余信息的频繁子树,这样的输出结果会降低后续操作的效率。针对传统方法的不足,提出了一种用于挖掘覆盖模式（MCRP）算法。首先,采用宽度孩子数编码对树进行编码;然后,通过基于最大前缀编码序列的边扩展方式生成所有的候选子树;最后,在频繁子树集和δ'-覆盖概念的基础上输出覆盖模式集。与传统的挖掘频繁闭树模式和极大频繁树模式的算法相比,该算法能够在保留所有频繁子树信息的情况下输出更少的频繁子树,并且将处理效率提高15%到25%。实验结果表明,所提算法能有效减小输出频繁子树的规模,减少冗余信息,在实际操作中具有较高的可行性。     

Canonical forms for labelled trees and their applications in frequent subtree mining

Tree structures are used extensively in domains such as computational biology, pattern recognition, XML databases, computer networks, and so on. In this paper, we first present two canonical forms for labelled rooted unordered trees–the breadth-first canonical form (BFCF) and the depth-first canonical form (DFCF). Then the canonical forms are applied to the frequent subtree mining problem. Based on the BFCF, we develop a vertical mining algorithm, RootedTreeMiner, to discover all frequently occurring subtrees in a database of labelled rooted unordered trees. The RootedTreeMiner algorithm uses an enumeration tree to enumerate all (frequent) labelled rooted unordered subtrees. Next, we extend the definition of the DFCF to labelled free trees and present an Apriori-like algorithm, FreeTreeMiner, to discover all frequently occurring subtrees in a database of labelled free trees. Finally, we study the performance and the scalability of our algorithms through extensive experiments based on both synthetic data and datasets from real applications.     

ESPM--频繁子树挖掘算法

随着互联网的发展,频繁模式的挖掘由频繁项集扩展到结构化数据：树和图．在这些结构上的挖掘工作被应用于更为复杂的领域,比如生物信息学、网络日志和XML文档．提出了一个新颖的算法：ESPM,以挖掘有序标号树中的频繁子树．不同于以往的工作,把树同构的判断工作放到了算法的晚期,从而减少了整个挖掘过程的时间开销．人工数据集和真实数据集上的实验都证明ESPM相较于其他算法的优越性．还提出了一些可能的改进．     

最小频繁闭树的增量式更新算法

针对树挖掘算法产生大量频繁子树和树数据库随时间变化的问题,提出最小频繁闭树增量式更新算法以及增量式更新策略,能充分利用已有挖掘知识,无须重新运行树挖掘算法,并且只需进行一次数据库扫描操作。给出一种候选子树剪枝方法,能减少树同构判别次数,有效提高算法的运行效率。通过大量实验结果表明,该算法有效可行且效率较高。     

快速挖掘全局频繁项目集

分布式环境中，全局频繁项目集的挖掘是数据挖掘中最重要的研究课题之一．传统的全局频繁项目集挖掘算法采用Apriori算法框架，须多遍扫描数据库并产生大量的候选项目集，且通过传送局部频繁项目集求全局频繁项目集的网络通信代价高．为此，提出了一种分布数据库的全局频繁项目集快速挖掘算法——FMAGF.FMAGF算法采用传送条件频繁模式树或条件模式基来挖掘全局频繁项目集，可有效地减小网络通信量，提高全局频繁项目集挖掘效率．理论分析和实验结果表明提出的算法是有效可行的．     

利用编码的频繁导出式子树挖掘算法

针对频繁导出式子树的特点,给出一种基于编码的频繁导出式子树挖掘算法。该算法通过宽度优先编码来表示原始数据库,使单个投影的规模最小;通过对每个投影编码降低了整个投影库的规模,从而有效地提高了频繁导出式子树的挖掘效率。实验结果验证了该算法具有较高的挖掘效率。     

网格下基于BFCM数据挖掘算法的实现

为了拓展算法的应用领域,降低算法的复杂性,提出了网格平台下宽度优先遍历的规范化方法(BFCM)进行数据挖掘,依据规范化方法将无序树转化,利用最右路径扩展方法构造模式增长空间,根据待增长模式的拓扑结构确定增长点,最后构造相应投影库并找出频繁节点。实验证明该算法支持随机存取任意树和任意节点,具有较高的时空效率。     

基于离散区间的频繁嵌入式子树挖掘算法

针对频繁嵌入式子树挖掘,利用离散区间来构造投影库,给出一种基于离散区间的频繁嵌入式子树挖掘算法。该算法通过离散区间消除冗余投影,有效地压缩投影库的规模,提高了子树节点计数效率,减低了算法的时空复杂性。实验结果表明该算法具有较高的挖掘效率。     

一种新的频繁子树增量式更新方法

讨论频繁子树增量式更新问题,提出一种新的频繁子树增量式更新算法。提出有效树集概念和增量式更新策略,在更新挖掘时,无须重新运行子树挖掘程序,能充分利用已有的挖掘结果,算法只需要进行一次数据库遍历操作。提出候选子树剪枝策略,在更新挖掘过程中,能大幅减少子树同构次数,有效地提高了算法的运行效率。通过大量实验分析表明,算法有效可行且具有较高的运行效率。     

基于FP-Tree有效挖掘最大频繁项集

最大频繁项集的挖掘过程中,在最小支持度较小的情况下,超集检测是算法的主要耗时操作.提出了最大频繁项集挖掘算法FPMFI(frequent pattern tree for maximal frequent item set)使用基于投影进行超集检测的机制,有效地缩减了超集检测的时间.另外,算法FPMFI通过删除FP子树(conditional frequent pattern tree)的冗余信息,有效地压缩了FP子树的规模,减少了遍历的开销.分析表明,算法FPMFI具有优越性.实验比较说明,在最小支持度较小时,算法FPMFI的性能优于同类算法1倍以上.