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

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

快速挖掘可变支持度约束的闭合与最大频繁Induced子树

国内外学者提出了许多频繁子树挖掘算法.这些算法使用的均是固定最小支持度.一般说来,具有较高支持度的短子树通常是有趣的;而对于长子树,即使支持度相对低一些也可能有趣.这就要求挖掘过程中最小支持度的值随着树中节点数的增加而减小.提出了快速挖掘可变支持度约束的闭合与最大频繁Induced子树的算法--SCCMTreeMiner. 该算法采用最右扩展技术枚举候选子树,以及两种新的剪枝方法提高挖掘效率,挖掘过程中最小支持度的设定随着树中节点数的增加而减小.实验结果表明,SCCMTreeMiner生成的子树数量和执行时间与CMTreeMiner算法相比都有大幅度减少.     

一种基于升序FP-tree的频繁模式挖掘算法

本文提出了一种基于升序FP-tree的频繁模式挖掘算法,该算法按照支持度升序构造升序FP-tree,并通过在其中搜索扩展频繁集及归并子树来挖据频繁模式。实验表明,与FP-growth算法相比,算法的挖掘速度提高了将近2倍,此外新算法还具有比较好的伸缩性。     

PFTM：一种基于投影的频繁子树挖掘算法

频繁子树在Web挖掘、XML文档分析、生物信息处理等领域有着重要的应用。提出了一种新的基于投影的频繁子树挖掘算法(PFTM)，通过对数据库和候选节点集进行投影，并采用递推式候选节点集更新技术来有效地压缩搜索空间。以高效地从森林中挖掘出频繁子树。PFTM不需要产生候选子树。性能对比实验表明，PFTM是有效和可扩展的，而在算法效率上，PFTM要比FREQT平均高出40％左右。     

基于子树约束的最大频繁子树挖掘算法

目前大多数频繁子树算法都是挖掘频繁子树完全集,这些算法数据搜索空间的内存开销和输出的结果集都非常庞大.为了减小结果集,提出基于子树约束的最大频繁子树算法--CSMTreeMiner,采用垂直和层次扩展的方法来枚举频繁子树,并使用覆盖关系来对不可能生成最大频繁子树的模式进行删除.实验结果验证CSMTreeMiner算法的有效性和稳定性.     

极大频繁子树挖掘及其应用

极大频繁子树挖掘在Web挖掘、HTML/XML文档分析、生物医学信息处理等领域有着重要的应用,可用于解决这些领域的自同构问题.本文提出了一种极大频繁子树挖掘算法(MFTM).MFTM基于最右路径扩展技术,在搜索过程中,采用覆盖定理进行裁剪,压缩搜索空间,从而极大地加快了算法的收敛速度.性能实验表明,极大频繁挖掘等算法是有效和可伸缩的.     

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

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

关联规则挖掘中对Apriori算法的一种改进研究

通过对关联规则挖掘算法的详细分析,提出了一种基于无向项集图的动态频繁项集挖掘算法.当事务数据库和最小支持度发生变化时,该算法只需重新遍历一次无向项集图即可得到新的频繁项集.该算法不仅简单、只需扫描一次数据库,而且还具有搜索速度快、节省内存空间等优点.     

基于分区的频繁子树挖掘算法研究

针对基于模式增长原理的嵌入式子树挖掘算法——TreeGrowth(TG)算法挖掘子树过大与内存消耗大缺点,在分区挖掘思想的基础上,提出了一种新算法——PTG(partition tree growth)算法。PTG算法将数据库划分成多个分区,先用TG算法进行挖掘,得到每个分区的局部频繁子树。根据全局支持数进行筛选,得到全局频繁子树,有效地减少了挖掘的子树,有效地降低了内存的开销。仿真实验结果表明,PTG算法能够解决在大数据集上挖掘时出现内存空间不足的问题,验证了其有效性与健壮性。     

基于加权动态网络的频繁模式挖掘研究

不同时刻的动态网络往往具有不同权重,针对加权动态网络的频繁模式挖掘,提出一种挖掘算法WGDM,它适用于加权动态社会网络、生物网络等方面的频繁模式挖掘。WGDM算法利用支持度的反单调性裁剪搜索空间,从而减少冗余候选子图,提高算法效率。通过实验测试了WGDM算法的性能,并根据中国实际股票市场网络,利用WGDM算法挖掘股票市场网络中有趣的频繁模式。     

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

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

EvoMiner: frequent subtree mining in phylogenetic databases

The problem of mining collections of trees to identify common patterns, called frequent subtrees (FSTs), arises often when trying to interpret the results of phylogenetic analysis. FST mining generalizes the well-known maximum agreement subtree problem. Here we present EvoMiner, a new algorithm for mining frequent subtrees in collections of phylogenetic trees. EvoMiner is an Apriori-like levelwise method, which uses a novel phylogeny-specific constant-time candidate generation scheme, an efficient fingerprinting-based technique for downward closure, and a lowest-common-ancestor-based support counting step that requires neither costly subtree operations nor database traversal. Our algorithm achieves speedups of up to 100 times or more over Phylominer, the current state-of-the-art algorithm for mining phylogenetic trees. EvoMiner can also work in depth-first enumeration mode to use less memory at the expense of speed. We demonstrate the utility of FST mining as a way to extract meaningful phylogenetic information from collections of trees when compared to maximum agreement subtrees and majority-rule trees—two commonly used approaches in phylogenetic analysis for extracting consensus information from a collection of trees over a common leaf set.     

一种动态的频繁项集挖掘算法

提出了一种基于无向项集图的动态频繁项集挖掘算法。当事务数据库和最小支持度发生变化时,该算法只需重新遍历一次无向项集图,即可得到新的频繁项集。与传统的频繁项集挖掘算法相比,在执行效率上有显著提高。     

一种新的频繁子树挖掘算法研究与实现

为提高频繁子树挖掘算法效率,结合原有频繁子树挖掘算法FSubtreeM的相关技术提出了新的全局树引导结构及其相关引理,并证明了其正确性.最后提出了新的频繁子树挖掘算法FSM_CGTG,并通过实验证明了该算法在现实数据集上的有效性且比现有频繁子树挖掘算法FSubtreeM性能优越.     

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

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

关联规则挖掘Apriori算法的研究与改进

本文采用一种基于布尔矩阵的频繁集挖掘算法。该算法直接通过支持矩阵行向量的按位与运算来找出频繁集,而不需要Apriori算法的连接和剪枝,通过不断压缩支持矩阵,不仅节约了存储空间,还提高了算法的效率。     

基于矩阵的关联规则挖掘算法

针对一些经典的关联规则算法进行分析,提出一种基于矩阵的高效关联规则挖掘算法。该算法把交易数据库转化为0-1矩阵形式,只需进行一次数据库搜索,使用逻辑运算方法发现频繁项集并计算它的支持计数,加快了频繁k项目集的验证速度,能大量减少所需的I/O次数,减小了存储空间。实验表明,新算法执行效率明显优于Apriori算法。     

一种基于人工免疫的新的频繁项挖掘算法

以往算法的研究主要围绕着减少候选项目集进而减少事务数据库的扫描次数的角度,先求出候选项集,再计算候选项集的支持度求得频繁项集。本文改变过去求频繁项集的角度,从新的角度来看频繁项目集的定义,同时结合人工免疫的特点,设计一个基于人工免疫的新频繁项集挖掘算法。本文详细介绍了算法设计等。新算法的复杂度与支持度,数据库总容量有关。验证实验的结果与其他算法相比较证明了该算法的可行性、有效性和完备性。     

一种改进的闭图挖掘算法

频繁子图挖掘是各种图挖掘的基础和瓶颈,为了提高频繁子图挖掘算法的效率,在频繁闭图方法的基础上提出了一种新算法BPCG.首先使用了一种新结构表存储频繁子图集,从而不需扫描图集就可直接扩展最频繁邻接边及计算支持度阈值;然后算法又利用兄弟剪枝策略和删除局部频繁边,缩小搜索空间并减少不必要的操作.通过实验证明,算法优于其他子图挖掘算法.