MAXSeq: 一个新的最大频繁序列挖掘算法

最大频繁序列发现是数据挖掘中的一个重要分支．本文提出一种发现最大频繁序列集的算法MAXSeq，该算法通过对潜在的最大频繁序列进行选择性的扩展，直接判断其是否为最大序列，无须对候选最大序列进行维护，从而显著减小了存储开销．同时，优化策略的恰当运用对降低CPU时间起着至关重要的作用．     

流数据中一种高效剪枝的频繁序列挖掘算法

序列模式挖掘就是在时序数据库中挖掘相对时间或其他模式出现频率高的模式.序列模式发现是最重要的数据挖掘任务之一,并有着广阔的应用前景.针对静态数据库,序列模式挖掘已经被深入的研究.近年来,出现了一种新的数据形式:数据流.针对基于数据流的序列模式挖掘的研究还不是十分深入.提出一个有效的基于数据流的挖掘频繁序列模式的算法SSPM,利用到2个数据结构(F-list和Tatree)来处理基于数据流的序列模式挖掘的复杂性问题.SSPM的优点是可以最大限度地降低负正例的产生,实验表明SSPM具有较高的准确率.     

挖掘最大频繁模式的新方法

由于其内在的计算复杂性,挖掘密集型数据集的频繁模式完全集非常困难,解决方案之一是挖掘最大频繁模式集．该文在频繁模式完全集挖掘算法Opportune Project基础上,提出了挖掘最大频繁模式的新算法MOP．它采用宽度与深度优先相结合的混合搜索策略,能恰当地选择不同的支持集表示和投影方法,将闭合性剪裁和一般性剪裁相结合,并适时前窥,实现搜索与剪裁效率最优化．实验表明,MOP效率是MaxMiner的2～8倍,比MAFIA高2个数量级以上．     

高效挖掘无序频繁子树

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

基于混合投影的频繁模式挖掘算法

频繁模式挖掘是最基本的数据挖掘问题,由于内在复杂性,提高挖掘算法性能一直是个难题．耶是通过数据库混合投影来挖掘频繁模式完全集的全新算法．HP混合投影思想是：任意数据集都不能简单地归入某个单一特性类别,挖掘过程应根据局部数据子集的特性变化动态地调整频繁模式树构造策略、事务子集表示形式、投影方法．HP提出基于树表示的虚拟投影与基于数组表示的非过滤投影,较好地解决了提高时间效率与节省内存空间的矛盾．实验表明,HP时间效率比Apriori,FP—Growth和H-Mine高出1～3个数量级,并且空间可伸缩性也大大优于这些算法．     

一种基于频繁序列树的增量式序列模式挖掘算法

针对目前现有的增量式序列模式挖掘算法没有充分利用先前的挖掘结果,当数据库更新时,需要对数据库进行重复挖掘的问题。本文提出一种基于频繁序列树的增量式序列模式挖掘算法(ISFST),ISFST采用频繁序列树作为序列存储结构,当数据库发生变化时,ISFST算法分两种情况对频繁序列树进行更新操作,通过遍历频繁序列树得到满足最小支持度的所有序列模式。实验结果表明,ISFST算法在时间性能上优于PrefixSpan算法和IncSpan算法。     

GenMax: An Efficient Algorithm for Mining Maximal Frequent Itemsets

We present GenMax, a backtrack search based algorithm for mining maximal frequent itemsets. GenMax uses a number of optimizations to prune the search space. It uses a novel technique called progressive focusing to perform maximality checking, and diffset propagation to perform fast frequency computation. Systematic experimental comparison with previous work indicates that different methods have varying strengths and weaknesses based on dataset characteristics. We found GenMax to be a highly efficient method to mine the exact set of maximal patterns.     

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

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

Efficient Algorithms for Mining and Incremental Update of Maximal Frequent Sequences

We study two problems: (1) mining frequent sequences from a transactional database, and (2) incremental update of frequent sequences when the underlying database changes over time. We review existing sequence mining algorithms including GSP, PrefixSpan, SPADE, and ISM. We point out the large memory requirement of Pref ixSpan, SPADE, and ISM, and evaluate the performance of GSP. We discuss the high I/O cost of GSP, particularly when the database contains long frequent sequences. To reduce the I/O requirement, we propose an algorithm MFS, which could be considered as a generalization of GSP. The general strategy of MFS is to first find an approximate solution to the set of frequent sequences and then perform successive refinement until the exact set of frequent sequences is obtained. We show that this successive refinement approach results in a significant improvement in I/O cost. We discuss how MFS can be applied to the incremental update problem. In particular, the result of a previous mining exercise can be used (by MFS) as a good initial approximate solution for the mining of an updated database. This results in an I/O efficient algorithm. To improve processing efficiency, we devise pruning techniques that, when coupled with GSP or MFS, result in algorithms that are both CPU and I/O efficient.This research is supported by Hong Kong Research Grants Council grant HKU 7040/02E.     

一种高效的最大频繁项集挖掘算法DFMFI-Miner

分析最大频繁项集和完全频繁项集的关系,提出了一个挖掘最大频繁项集的高效算法DFMFI—Miner（The Miner Basedon Depth—First Searching for Mining Maximal Frequent Itemsets）,采用深度优先方法搜索项集空间,采用垂直位图及一定的压缩方法对表示事务数据库并进行约简,并采用多种有效剪枝策略和优化策略,提高了算法的效率。在多个数据集上进行了实验,实验结果表明该算法特别适于挖掘具有长频繁项集的数据集。