基于位置信息的序列模式挖掘算法*

PrefixSpan算法在产生频繁序列模式时会产生大量的投影数据库,其中很多投影数据库是相同的。提出了基于位置信息的序列模式挖掘算法——PVS,该方法通过记录每个已产生投影数据库的位置信息,避免了重复产生相同的投影数据库,从而提高了算法的运行效率。通过实验证明,该算法在处理相似度很高的序列数据时比PrefixSpan算法有效。     

一种基于序列末项位置信息的序列模式挖掘算法

针对PrefixSpan算法中反复扫描投影数据库寻找局部频繁项并重复构造挖掘大量重复投影数据库的不足,提出一种基于序列末项位置信息的序列模式挖掘算法SPM-LIPT。通过连接2-序列位置信息表(LIPT)找到序列模式的下一项,实现序列模式增长,避免对投影数据库反复扫描;同时通过检查相同末项序列首位置信息表(SLIFPT)进行前向剪枝;消除大量重复投影的构建。最后通过实验证明了算法的有效性。     

一种高效的增量式序列模式挖掘算法

现有的增量式挖掘算法在支持度发生变化时,需要对序列数据库进行重复挖掘,为减少由此产生的时空消耗,提出一种高效的增量式序列模式挖掘算法。算法采用频繁序列树作为序列存储结构,当序列数据库和最小支持度发生变化时,通过执行更新操作,实现频繁序列树的更新,利用深度优先遍历频繁序列树找到序列数据库中所有的序列模式。实验结果表明,与IncSpan算法和PrefixSpan算法相比,该算法的挖掘效率较高。     

一种基于位置信息的高效DNA序列挖掘算法

类Apriori算法在产生频繁模式时需要多次扫描数据库,并且产生大量的候选集;Free Span和Prefix Span等基于投影数据库的算法在产生频繁模式时会产生大量的投影数据库,占用很多内存空间,这些都造成了很大的冗余。针对以往序列挖掘算法存在的不足,提出一种高效的序列挖掘算法——基于位置信息的序列挖掘算法PBSMA(Position-Based Sequence Mining Algorithm)。PBSMA算法通过记录频繁子序列的位置信息来减少对数据库的扫描,利用位置信息逐渐扩大频繁模式的长度,并且借鉴关联矩阵的思想和Prefix Span算法中前缀的概念,深度优先去寻找更长的关键模式。实验结果证明,无论在时间还是空间上,PBSMA算法都比Prefix Span算法更高效。     

一种改进的增量挖掘算法

Pre-FUFP算法基于次频繁项的概念有效处理了频繁模式树的更新,但当有次频繁项变成频繁项时,需要判定原数据库中哪些事务包含该数据项。为此,通过引入次频繁项对应原事务标识符的索引确定需要处理原数据库的事务,减少这一过程所消耗的时间,并用基于压缩FP-tree和矩阵技术代替原始FP-growth挖掘出频繁模式。实验证明该算法在时间效率上较Pre-FUFP有大幅度提高。     

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

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

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

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

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

PretixSpan算法解决了类Apriori算法的不足,但产生的投影数据库花费了较多的存储空间及扫描时间.本文基于PretixSpan算法提出PSD算法,舍弃了对非频繁项的存储及对投影序列数小于最小支持数的投影数据库的扫描,减少了不必要的存储空间,提高了查询速度.实验证明,PSD算法比PretixSpan算法具有更好的时空性能.     

无重复投影数据库扫描的序列模式挖掘算法

序列模式挖掘在Web点击流分析、自然灾害预测、DNA和蛋白质序列模式发现等领域有着广泛应用.基于频繁模式增长的PrefixSpan是目前性能最好的序列模式挖掘算法之一.然而在密数据集和长序列模式挖掘过程中会出现大量的重复投影数据库,使得这类算法性能下降.算法SPMDS通过对投影数据库的伪投影做单项杂凑函数,如MD5等,检查是否存在重复的投影数据库,避免大量重复数据库的扫描,并采用一些必要条件简化投影数据库的搜索,进而提高算法的性能.实验和分析都表明SPMDS性能优于PrefixSpan.     

基于序列前缀技术的XML频繁路径挖掘算法

XML文档是半结构化数据,对其进行频繁路径挖掘可以分为两步：XML文档序列化和序列挖掘阶段. 现有的序列化方式将XML文档表示为Xpath路径集合,其中有大量的节点冗余;序列挖掘阶段采用的类Apriori算法需要多次扫描数据库并产生大量的候选集,采用的PrefixSpan算法会产生大量的投影数据库,占用较大的内存. 针对以往XML频繁路径挖掘算法存在的不足,本文提出一种高效的挖掘算法——基于序列前缀技术的XML频繁路径挖掘算法（PXFP,Prefix-based XML Frequent Path Mining Algorithm）. PXFP算法以广度优先方式遍历XML文档树并将每个节点表示为“节点：父节点”的形式,这种序列化的方式减少了节点冗余. 在序列挖掘阶段借鉴PrefixSpan 算法中前缀的概念,但不产生投影数据库,仅得到直接后缀（即前缀的子节点）,通过记录频繁子路径的位置信息逐渐扩大频繁模式的长度,位置信息的引入减少了对数据库的扫描. 实验结果表明,PXFP算法取得了比PrefixSpan算法更高的时间和空间效率.     

序列模式数据挖掘算法的并行化研究

序列模式在许多领域都有着重要的应用,大量的数据和模式需要高效的、可扩展的并行算法.针对目前序列模式挖掘算法存在的普遍问题,在对串行序列模式数据挖掘算法研究的基础上,本文提出了一种并行的序列模式数据挖掘算法.通过理论分析与实验验证可知:该并行数据挖掘算法,在海量数据的情形下,能很好地提高数据挖掘的效率.     

序列模式挖掘研究与发展

序列模式挖掘是数据挖掘的一个重要研究课题,它在很多领域中都有着广泛的应用.首先讨论了序列模式挖掘的相关背景,然后对序列模式挖掘进行分类,并在此基础上对每一类序列模式挖掘算法的特点进行了介绍和比较;最后,对序列模式挖掘未来的研究重点进行展望,以便研究者对序列模式挖掘做进一步的研究.     

A Pattern Decomposition Algorithm for Data Mining of Frequent Patterns

Efficient algorithms to mine frequent patterns are crucial to many tasks in data mining. Since the Apriori algorithm was proposed in 1994, there have been several methods proposed to improve its performance. However, most still adopt its candidate set generation-and-test approach. In addition, many methods do not generate all frequent patterns, making them inadequate to derive association rules. We propose a pattern decomposition (PD) algorithm that can significantly reduce the size of the dataset on each pass, making it more efficient to mine all frequent patterns in a large dataset. The proposed algorithm avoids the costly process of candidate set generation and saves time by reducing the size of the dataset. Our empirical evaluation shows that the algorithm outperforms Apriori by one order of magnitude and is faster than FP-tree algorithm. Received 14 May 2001 / Revised 5 September 2001 / Accepted in revised form 26 October 2001 Correspondence and offprint requests to: Qinghua Zou, Department of Computer Science, California University–Los Angeles, CA 90095, USA. Email: zou@cs.ucla.eduau     

一个改进的关联规则的频繁项目集数据挖掘算法

在关联规则中的Apriori算法,具有天生的缺陷,运行效果很不理想。为了克服Apriori算法的缺点,本文提出了一个改进的算法：在产生频繁项目集组合时,只需扫描数据库一次,这样就可以有效率地降低I／O的存取时间,更快速地找出符合使用者需求的关联规则。仿真实验表明,该算法是有效的。     

序列模式挖掘的并行算法研究

序列模式在许多领域都有着重要的应用,大量的数据和模式需要高效的、可扩展的并行算法.针对目前序列模式挖掘算法存在的普遍问题,提出了一个适合无共享并行环境下的算法PMSP,有效地解决了存储受限以及时效性问题,并将它与当前相对较优的并行算法HPSPM做了比较,实验表明PMSP是有效的.     

基于频繁链表的频繁集的挖掘算法

自从1989年提出KDD以来,关联规则的挖掘一直是人工智能及数据库领域关注的焦点,尤其是项目决策者渴求的制胜法宝。挖掘关联规则的前提是频繁集的挖掘,目前典型的频繁集挖掘算法以Appriori算法为代表。在Appriori算法的基础上提出了一些可行的方法,所有这些算法不外乎达到两个目的:①在穷举的基础上,设法删除对关联规则不太有效的频繁集,减少候选频繁集的数量,达到提高挖掘算法性能的目的。②直接挖掘最大频繁集,以最大频繁集为基础挖掘感兴趣     

基于FP-tree的最大频繁模式挖掘算法

在FP-tree结构的基础上提出了最大频繁模式挖掘算法FP-Max。算法FP-Max只需要两次数据库扫描,挖掘过程不会产生候选项集。实验表明．算法FP-Max在挖掘密集型数据集方面是高效的。     

基于前缀树的关联规则挖掘算法分析与设计

通过研究项集之间的关系,发现大项集之间存在着一种特定的关系,即k-项集一定是由一个（k-1）-项集加上一个单独的项构成的。基于这种项集关系,本文提出基于前缀树的TIUA算法,算法摆脱了传统算法多次迭代的不足,并利用挖掘出的结果,只需扫描一次数据库,就能满足各种要求,通过以空间换时间,达到提高挖掘效率的目的。     

概念漂移数据流挖掘算法综述

数据流是一种新型的数据模型,具有动态、无限、高维、有序、高速和变化等特性。在真实的数据流环境中,一些数据分布是随着时间改变的,即具有概念漂移特征,称为可变数据流或概念漂移数据流。因此处理数据流模型的方法需要处理时空约束和自适应调整概念变化。对概念漂移问题和概念漂移数据流分类、聚类和模式挖掘等内容进行综述。首先介绍概念漂移的类型和常用概念改变检测方法。为了解决概念漂移问题,数据流挖掘中常使用滑动窗口模型对新近事务进行处理。数据流分类常用的模型包括单分类模型和集成分类模型,常用的方法包括决策树、分类关联规则等。数据流聚类方式通常包括基于k- means的和非基于k- means的。模式挖掘可以为分类、聚类和关联规则等提供有用信息。概念漂移数据流中的模式包括频繁模式、序列模式、episode、模式树、模式图和高效用模式等。最后详细介绍其中的频繁模式挖掘算法和高效用模式挖掘算法。