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

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

一种快速发现最大频繁项目集的序列算法

提出了一种快速发现最大频繁项目集的算法MFIA。该算法只需扫描一遍数据库，通过构造数据库事务的相应项目序列来发现最大频繁项目集。实验表明：MFIA算法性能稳定，可扩展性好，效率高。     

事件序列中频繁串行情节的增量式发现算法

本文研究事件序列中频繁情节的发现问题,提出了在事件序列中发现频繁串行情节的增量式算法．如果在事件序列中发现了频繁情节及其出现频率,我们就可以生成描述或预测该序列行为的情节规则．     

基于子序列全连接和最大团的时间序列模体发现算法

针对时间序列模体发现算法计算复杂，并且无法发现多实例模体的问题，提出基于子序列全连接和最大团的时间序列模体发现（TSSJMC）算法。首先，使用快速时间序列子序列全连接算法求得所有子序列之间的距离，生成距离矩阵；然后，设置相似性阈值，将距离矩阵转化为邻接矩阵，构造子序列相似图；最后采用最大团搜索算法从相似图中搜索最大团，最大团的顶点对应的时间序列为包含最多实例的模体。在公开的时间序列数据集上进行实验，选用已有的能够发现多实例模体的Brute Force和Random Projection算法作为对比对象，分别从准确性、效率、可扩展性和鲁棒性对TSSJMC算法进行分析并获得了客观的评判结果。实验结果表明，与Random Projection算法相比，TSSJMC算法在效率、可扩展性和鲁棒性法方面均有明显优势；与Brute Force算法相比，TSSJMC算法发现的模体实例数量虽略低，但其效率和可扩展性都优于Brute Force算法。因此，TSSJMC是质量和效率相平衡的算法。     

基于项目序列集操作的关联规则挖掘算法

最大频繁项目序列集的生成是影响关联规则挖掘的关键问题，传统的算法是通过对事务数据库的多次扫描实现的，最新的研究已经开始通过减少事务数据库的扫描次数进而减少挖掘过程的I／O代价来获得更高的效率，随着计算机性能的提高，探索合适的数据结构来支持基于一次事务数据库扫描的高效算法成为可能，该文首先给出项目序列集和它的基本操作的严格定义，然后在此基础上提出了一个称为ISS－DM的最大频繁项目序列集生成算法。ISS－DM算法是通过对事务数据库的一次扫描而逐步演化成最大频繁项目序列集的，最后作者对这一算法的时间和空间效率进行了理论分析和实验验证。     

一种挖掘带时间约束序列模式的改进算法

针对带时间约束的序列模式，提出了一种改进的挖掘算法TSPM，克服了传统的序列模式挖掘方法时空开销大，结果数量巨大且缺少针对性的缺陷．算法引入图结构表示频繁2序列，仅需扫描一次数据库，即可将与挖掘任务相关的信息映射到图中，图结构的表示使得挖掘过程可以充分利用项目之间的次序关系，提高了频繁序列的生成效率．另外算法利用序列的位置信息计算支持度，降低了处理时间约束的复杂性，避免了反复测试序列包含的过程．实验证明，该算法较传统的序列模式发现算法在时间和空间性能上具有优越性。     

通用时间约束的序列模式挖掘

提出了满足滑动窗口、最大间隙、最小间隙、最大跨度四种时间参数限制的序列挖掘算法．算法通过划分不同的等价类分解搜索空间，利用时间连接实现模式的逐步增长，挖掘过程只需扫描一次序列数据库．由于序列嵌入的四种参数具有通用性，本算法不仅能发现以前相关算法所能发现的模式，还能发现其他算法所不能发现的模式。     

基于图结构的候选序列生成算法

先生成候选序列再判断候选序列是否为频繁序列，最后获得频繁序列是序列数据挖掘中基于候选序列挖掘算法的一般结构，如Apriori类算法，GSP算法，SPADE算法等。因此，研究候选序列生成算法具有普遍意义。本文首先研究了序列数据集(序列数据库)与图结构间的关系，证明了一个序列是频繁序列的必要条件是该序列对应于一个完全子图。以此为基础提出了基于图结构的候选序列生成算法，文中给出了算法正确性证明。在T25110D10K和T25120D100K数据集上的挖掘实验表明在本文提出的候选序列生成算法上进行挖掘比用Apriori算法进行挖掘的效率更高。     

基于CTID序列模式的一种改进算法

提高序列模式挖掘算法效率的关键在于减少发现频繁序列的时间。文中基于CTID概念提出了一种改进的频繁序列模式挖掘算法——SPM，它充分利用频繁项集和中间挖掘结果，得到更多有效的序列模式，并简化了剪枝步骤，从而提高了算法效率。实验证明该算法可行。     

基于项目序列集亚操作和数据分割的最大频繁项目序列挖掘方法

发现频繁项目序列集是关联规则挖掘中的一个重要步骤.该文提出两个发现最大频繁 项目序列的算法Dfis和Dfisp.Dfis算法基于项目序列集操作理论,只有一次数据库扫描.Dfisp 是Dfis的改进算法,它引入数据分割技术以提高内存使用率因而增强对大型数据库的处理能力, 是一个两次数据库扫描算法.实验表明了它们的性能和优势.     

一种用户行为模式的挖掘算法

最大频繁事件序列挖掘是数据挖掘中重要的研究课题之一。该文提出了一种新的挖掘用户行为模式的算法。该算法采用位图索引表的数据格式,使用一种有效的基于前缀树的频繁事件序列扩展方法,结合有效的剪枝技术,明显地加速了最大频繁事件序列的生成。     

Approximate mining of maximal frequent itemsets in data streams with different window models

A data stream is a massive, open-ended sequence of data elements continuously generated at a rapid rate. Mining data streams is more difficult than mining static databases because the huge, high-speed and continuous characteristics of streaming data. In this paper, we propose a new one-pass algorithm called DSM-MFI (stands for Data Stream Mining for Maximal Frequent Itemsets), which mines the set of all maximal frequent itemsets in landmark windows over data streams. A new summary data structure called summary frequent itemset forest (abbreviated as SFI-forest) is developed for incremental maintaining the essential information about maximal frequent itemsets embedded in the stream so far. Theoretical analysis and experimental studies show that the proposed algorithm is efficient and scalable for mining the set of all maximal frequent itemsets over the entire history of the data streams.     

基于B-list的最大频繁项集挖掘算法

针对现有的最大频繁项集挖掘算法挖掘时间过长、内存消耗较大的问题,提出了一种基于构造链表B-list的最大频繁项集挖掘算法BMFI,该算法利用B-list数据结构来挖掘频繁项集并采用全序搜索树作为搜索空间,然后采用父等价剪枝技术来缩小搜索空间,最后再结合基于MFI-tree的投影策略实现超集检测来提高算法的效率。实验结果表明,BMFI算法在时间效率与空间效率方面均优于FPMAX算法与MFIN算法。该算法在稠密数据集与稀疏数据集中进行最大频繁项集挖掘时均有良好的效果。     

基于FSG的最大频繁子图挖掘算法*

图挖掘已成为数据挖掘领域研究的热点,然而挖掘全部频繁子图很困难且得到的频繁子图过多,影响结果的理解和应用。可通过挖掘最大频繁子图来解决挖掘结果数量巨大的问题,最大频繁子图挖掘得到的结果数量很少且不丢失信息,节省了空间和以后的分析工作。基于算法FSG提出了最大频繁子图挖掘算法FSG-MaxGraph;结合节点的度、标记及邻接列表来计算规范编码,提出两个定理来减少子图同构判断的次数,并应用改进后的决策树来计算支持度。实验证明,新算法解决了挖掘结果太多理解困难的问题,且提高了挖掘效率。     

基于改进FP-tree的最大频繁项集挖掘算法

现有的最大频繁项集挖掘算法在挖掘过程中需要进行超集检测,基于FP-tree的算法需要递归的建立条件频繁模式树,挖掘效率不高.提出了一种基于改进FP-tree高效挖掘最大频繁项集的算法(MMFI).该算法修改了FP-tree结构并采用NBN策略,在挖掘过程中既不需要进行超集检测也不需要递归的建立条件频繁模式树.算法分析和实验结果表明,该算法是一种有效、快速的算法.     

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

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

一种挖掘最大频繁项集的深度优先算法

最大频繁项集挖掘是许多数据挖掘应用中的重要问题．提出一种新的深度优先搜索最大频繁项集的算法．该算法采用位图数据格式,结合了流行的各种有效剪枝技术,并使用局部最大频繁项集来进行高效的超集存在判断,明显地加速了最大频繁项集的生成,从而降低了CPU时间．     

频繁模式挖掘的约束算法

在频繁模式挖掘过程中能够动态改变约束的算法比较少.提出了一种基于约束的频繁模式挖掘算法MCFP.MCFP首先按照约束的性质来建立频繁模式树,并且只需扫描一遍数据库,然后建立每个项的条件树,挖掘以该项为前缀的最大频繁模式,并用最大模式树来存储,最后根据最大模式来找出所有支持度明确的频繁模式.MCFP算法允许用户在挖掘频繁模式过程中动态地改变约束.实验表明,该算法与iCFP算法相比是很有效的.     

Parallel mining of maximal sequential patterns using multiple samples

In this paper, we propose a new parallel algorithm, named PMSPX, which mines maximal frequent sequences by using multiple samples to exclude infrequent candidates effectively. A frequent sequence is maximal if none of its supersequences is frequent. Unlike the traditional single-sample methods developed for mining frequent itemsets, PMSPX uses multiple samples. Thus, it can avoid or alleviate some problems inherent in the single-sample methods. We theoretically analyzed how to increase the minimum support level to prevent misestimating infrequent candidates as frequent in the mining of samples. PMSPX is a parallel version of our sequential MSPX algorithm, and it is developed on a cluster of workstations. In PMSPX, each processing node uses MSPX to find a candidate set of local maximal frequent sequences first, independently from other processing nodes. Then, a top-down search is performed, starting with all the candidates, in a synchronous manner to identify real maximal frequent sequences. This asynchronous local mining followed by synchronous global mining approach minimizes the synchronization and communication among the processing nodes. Three database partitioning methods are proposed to distribute the database across the processing nodes, so that their workloads are balanced and the data skewness of the whole database is preserved in the data partition of each node. A comprehensive analysis was performed on PMSPX and existing parallel sequence mining algorithms, and extensive experiments were conducted on PMSPX. PMSPX demonstrates very good speedup and scaleup properties. It also requires less communication and synchronization than other parallel algorithms.     

基于最大频繁项目序列集挖掘ISS_DM算法的改进

阐述了挖掘最大频繁项目序列集ISS_DM算法,针对该算法不能有效地解决客户序列视图数据库的数据挖掘问题,结合序列模式提出了改进的ISS_DM算法,并进行了相应的验证.实践证明,改进后的算法同原算法相比,对相同的数据量进行挖掘,算法执行时间明显减少,效益较高.