PrefixSpan算法在多维序列模式挖掘中的应用

多维序列模式挖掘是在序列模式挖掘的基础上发展起来的，文章阐述了有关概念，介绍了两种序列模式挖掘算法：GSP算法和PrefixSpan算法，在对两类算法进行比较分析的基础上形成了挖掘多维序列模式的UniSeq算法、Dim-Seq算法和Seq-Dim算法。针对不同维度的模式，各种算法特点不同。     

PrefixSpan算法与CloSpan算法的分析与研究

数据挖掘领域的一个活跃分支就是序列模式的发现,即在序列数据库中找出所有的频繁子序列。介绍序列模式挖掘的基本概念,然后对序列模式中的经典算法PrefixSpan算法和基于PrefixSpan框架的闭合序列模式CloSpan算法进行了描述,并对它们的执行过程及其特点进行了分析与比较,总结了各自的优缺点,指出PrefixSpan算法适用于短序列方面挖掘,而CloSpan算法在长序列或者阈值较低时胜过PrefixSpan算法且CloSpan算法挖掘大型的数据库有更好的性能,得出的结果对序列模式挖掘的设计有重要的参考价值。     

一种改进的PrefixSpan算法及其在Web用户行为模式挖掘中的应用

序列模式挖掘是从序列数据库中挖掘相对时间或其他模式出现频率高的模式。针对PrefixSpan算法构造投影数据库时开销巨大、扫描效率不高的问题,通过以序列扩展代替项集进行扩展、放弃挖掘序列数小于阈值min＿support的投影数据库以及直接递归局部频繁项等方式进行改进,并将改进方法应用于Web用户行为模式挖掘中,对日志记录中的规律进行分析和研究。实验分析表明,相比PrefixSpan算法,该改进算法在算法效率方面有一定的提高。     

用户Web日志序列模式挖掘研究

单个用户访问网站能够留下大量的访问信息，合理地挖掘这些信息便能够得到用户个人的访问模式。文中将序列模式挖掘运用到单一用户Web日志上．最终可以得到单一用户的访问序列模式。在序列模式挖掘过程中，将传统的序列模式挖掘概念进行了扩充，对应到单一用户的序列模式上；运用Session来划分时间段，增强了时间的概念；运用概念格的理论，很好地实现了增量序列模式挖掘。并使用一个新的算法，解决MFP(最大前向路径)在Web日志中获取存在的一些问题。     

多时间粒度序列模式挖掘

序列模式挖掘是数据挖掘的一个重要问题.传统的序列模式仅能揭示频繁出现的项目以及出现的顺序,但不能揭示在前续项目出现的情况下,后续项目出现的时间.在本文中,引入一种新的多时间粒度序列模式,模式中相邻项目之间的转换时间采用从原数据集中导出的、多时间粒度下的最小有界时间区间和平均时间标注.建立了多时间粒度序列模式挖掘模型,提出了一种新的多时间序列模式挖掘算法MG-PrefixSpan.实验表明,算法是有效的.     

一种高效的并行挖掘频繁序列的算法

序列模式发现在数据挖掘领域中的地位越来越重要，本文首先介绍了频繁序列挖掘模式的基本概念，然后基于投影树算法，给出了其数据并行模式和任务并行模式，接着进行了算法的复杂性分析，我们的实验证明这些算法都能获得较好的加速比，而且任务并行模式具有更好的可扩展性。     

序列模式挖掘算法研究

数据挖掘领域一个活跃的研究分支就是序列模式的发现，即在序列数据库中找出所有的频繁子序列。目前的序列模式挖掘方法主要分为两类，一类是候选集生成测试方法：另一类是模式扩展方法。先介绍序列模式挖掘中的基本概念，然后描述几个重要算法，最后给出性能分析。     

序列模式挖掘在铝电解中的研究应用

序列模式挖掘是数据挖掘中的研究热点之一，它是基于关联规则的频繁项集的挖掘，其实质是在关联模型中加入时间属性。本文利用序列模式挖掘的典型算法prefix算法对铝电解中重要的工艺参数数据进行挖掘分析，给出铝电解槽的重要的工艺参数的序列化，对于提高铝电解的生产效率，节能降耗，延长率电解槽的寿命具有重要的意义。     

对比保序模式挖掘算法

针对现有的对比序列模式挖掘方法主要针对字符序列数据集且难以应用于时间序列数据集的问题，提出一种对比保序模式挖掘（COPM）算法。首先，在候选模式生成阶段，采用模式融合策略减少候选模式数；其次在模式支持度计算阶段，利用子模式的匹配结果计算超模式的支持度；最后，设计了动态最小支持度阈值的剪枝策略，以进一步有效地剪枝候选模式。实验结果表明，在6个真实的时间序列数据集上，在内存消耗方面，COPM算法至少比COPM-o(COPM-original)算法降低52.1%，比COPM-e(COPM-enumeration)算法低36.8%，比COPM-p(COPM-prune)算法降低63.6%；同时在运行时间方面，COPM算法至少比COPM-o算法降低30.3%，比COPM-e算法降低8.8%，比COPM-p算法降低41.2%。因此，在算法性能方面，COPM算法优于COPM-o、COPM-e和COPM-p算法。实验结果验证了COPM算法可以有效挖掘对比保序模式，发现不同类别的时间序列数据集间的差异。     

基于矩阵算法的序列模式挖掘研究

序列模式挖掘中几种算法的缺点:都要进行多次扫描数据库,CPU要进行多次I/O操作.这成为序列挖掘中的一大瓶颈,使得算法在实际应用中的效率不高.文中提出一种矩阵算法,即在一次扫描数据库时,根据扫描数据建立由0和1组成的事务矩阵.接下来的大序列、序列模式等都是通过矩阵的列向量对应元素的相乘运算和简单的加法运算而得到.从而使算法得到进一步优化,提高了CPU的使用率,解决了序列挖掘中的瓶颈问题.本算法通过大量的数据实验,证明了算法确实有效地优化了算法的时间复杂度.     

基于影响度的统计显著序列模式挖掘算法

针对传统序列模式挖掘算法中支持度不能如实体现序列模式兴趣度以及未对报告的序列模式进行质量评估的问题,提出一个基于影响度的统计显著序列模式挖掘算法ISSPM。首先,递归地挖掘出所有满足兴趣度约束的序列模式;然后,使用项集置换方法构建这些序列模式的置换检验零分布;最后,通过该零分布计算出被评估的序列模式的统计度量值,并从上述序列模式中找到所有统计显著序列模式。真实序列记录集合上的实验结果表明,ISSPM算法相较于PSPM、SPDL和PSDSP算法挖掘到的序列模式数量更少但兴趣度更强;仿真序列记录集合上的实验结果表明,ISSPM算法报告的结果中假阳性序列模式数量平均占比为3.39%,且该算法的嵌入模式的发现率均不低于66.7%,明显优于上述3个对比算法。可见,ISSPM算法报告的统计显著序列模式能够体现序列记录集合中更有价值的信息,同时根据这些信息做出的进一步分析和决策也更加可靠。     

数据流中基于滑动窗口的序列模式挖掘算法

序列模式发现是最重要的数据挖掘任务之一,并有着广阔的应用前景。针对静态数据库,序列模式挖掘已经被深入地研究,但针对基于数据流的序列模式挖掘的研究还不是十分深入。数据流有着无限性的特性,因此往往不能保存数据流中全部的数据,同时很多时候只对最近的时间段的序列模式感兴趣,提出一个有效的结合滑动窗口技术的挖掘序列模式的算法FPM-SW,算法利用到3个数据结构（PatternTable,CountTable和Ta-tree）来处理基于数据流的序列模式挖掘的复杂性问题。算法通过CountTable结构来保存以往的潜在频繁序列,考虑到在某些情况下CountTable占用内存过多,算法还结合了一种压缩CountTable技术来减少内存占用。FPM-SW的优点是可以最大限度地降低负正例的产生,实验表明FPM-SW具有较高的准确率。     

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

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

基于PrefixSpan的序列模式挖掘改进算法

针对序列模式挖掘算法PrefixSpan在挖掘过程中需要构造大量投影数据库的不足,提出IPMSP算法,在递归挖掘过程中,通过检查序列数据库关于前缀的前缀,避免对同一频繁前缀模式构造重复投影数据库,同时舍弃对非频繁项的存储并在投影序列数小于最小支持度时停止扫描投影数据库,从而提高PrefixSpan算法的时空性能。实验结果证明,IPMSP算法在时间和空间性能上优于PrefixSpan算法。     

Sequential Pattern Mining in Multi-Databases via Multiple Alignment

To efficiently find global patterns from a multi-database, information in each local database must first be mined and summarized at the local level. Then only the summarized information is forwarded to the global mining process. However, conventional sequential pattern mining methods based on support cannot summarize the local information and is ineffective for global pattern mining from multiple data sources. In this paper, we present an alternative local mining approach for finding sequential patterns in the local databases of a multi-database. We propose the theme of approximate sequential pattern mining roughly defined as identifying patterns approximately shared by many sequences. Approximate sequential patterns can effectively summerize and represent the local databases by identifying the underlying trends in the data. We present a novel algorithm, ApproxMAP, to mine approximate sequential patterns, called consensus patterns, from large sequence databases in two steps. First, sequences are clustered by similarity. Then, consensus patterns are mined directly from each cluster through multiple alignment. We conduct an extensive and systematic performance study over synthetic and real data. The results demonstrate that ApproxMAP is effective and scalable in mining large sequences databases with long patterns. Hence, ApproxMAP can efficiently summarize a local database and reduce the cost for global mining. Furthremore, we present an elegant and uniform model to identify both high vote sequential patterns and exceptional sequential patterns from the collection of these consensus patterns from each local databases.     

基于深度优先序列模式挖掘的预取模型

序列模式挖掘能够发现隐含在Web日志中的用户的访问规律,可以被用来在Web预取模型中预测即将访问的Web对象。目前大多数序列模式挖掘是基于Apriori的宽度优先算法。提出了基于位图深度优先挖掘算法,采用基于字典树数据结构的深度优先策略,同时采用位图保存和计算各序列的支持度,能够较迅速地挖掘出频繁序列。将该序列模式挖掘算法应用于Web预取模型中,在预取缓存一体化的条件下实验表明具有较好的性能。     

基于多核并行的海量数据序列模式挖掘*

为了在多核处理器上充分利用多核资源以提升挖掘性能,提出了一种动态与静态任务分配机制相结合的基于多核的并行序列模式挖掘算法。该算法采用数据并行与任务并行相结合的策略,在各处理器核生成局部序列模式后,再与其他处理器核协同,以最终获得所有的全局序列模式。算法通过并行局部归约技术消除了局部序列的重复生成与计算,并可结合静态与动态任务分配机制解决处理器的负载不均衡问题。理论分析和实验都证实了该算法可有效利用多核计算平台及多核体系结构优势,具有较高的运行效率和加速比。     

基于Bitmap的序列模式挖掘的改进算法

结合BBSP,提出了一种称做最终位置归纳序列模式挖掘(LPI-SPM)的新算法,该算法可以有效地从大型数据库中获取所有的频繁序列模式。该策略与以前工作的不同点在于:当判断一个序列是否是模式时,通过扫描数据库创建S-矩阵来实现(PrefixSpan)或者通过对候选项进行交运算(SPADE)或并运算(BBSP)统计其数量来实现。相反,在基于下列事实的基础上LPI-SPN会很容易实施这一过程,即若一个项的最终位置小于当前前缀位置,在相同的顾客序列中,该项就不会出现在当前前缀的后面。LPI-SPM在序列挖掘过程中可以大大缩减搜索空间,而且挖掘序列模式的效力可观。实验结果表明,在各种数据集合中LPI-SPM胜过BBSP三倍。     

Efficient strategies for tough aggregate constraint-based sequential pattern mining

Frequent sequential pattern mining with constraints is the task of discovering patterns by incorporating the user defined constraints into the mining process, thus not only improving mining efficiency but also making the discovered patterns to better meet user requirements. Though many studies have been done, few have been carried out on the “tough aggregate constraints” due to the diffIculty of pushing the constraints into the mining process. In this paper we provide efficient strategies to deal with tough aggregate constraints. Through a theoretical analysis of the tough aggregate constraints based on the concept of total contribution of sequences, we first show that two typical kinds of constraints can be transformed into the same form and thus can be processed in a uniform way. We then propose a novel algorithm called PTAC (sequential frequent Patterns mining with Tough Aggregate Constraints) to reduce the cost of using tough aggregate constraints through incorporating two effective strategies. One avoids checking data items one by one by utilizing the features of promisingness exhibited by some other items and validity of the corresponding prefix. The other avoids constructing an unnecessary projected database through effectively pruning those unpromising new patterns that may, otherwise, serve as new prefixes. With these strategies, our algorithm obtains good performance in speed and space, as demonstrated by experimental studies conducted on the synthetic datasets generated by the IBM sequence generator, in addition to a real dataset.