共查询到17条相似文献,搜索用时 396 毫秒
1.
数据挖掘领域的一个活跃分支就是序列模式的发现,即在序列数据库中找出所有的频繁子序列。介绍序列模式挖掘的基本概念,然后对序列模式中的经典算法PrefixSpan算法和基于PrefixSpan框架的闭合序列模式CloSpan算法进行了描述,并对它们的执行过程及其特点进行了分析与比较,总结了各自的优缺点,指出PrefixSpan算法适用于短序列方面挖掘,而CloSpan算法在长序列或者阈值较低时胜过PrefixSpan算法且CloSpan算法挖掘大型的数据库有更好的性能,得出的结果对序列模式挖掘的设计有重要的参考价值。 相似文献
2.
PrefixSpan算法与CloSpan算法的分析与研究 总被引:1,自引:0,他引:1
数据挖掘领域的一个活跃分支就是序列模式的发现,即在序列数据库中找出所有的频繁子序列.介绍序列模式挖掘的基本概念,然后对序列模式中的经典算法PrefixSpan算法和基于PrefixSpan框架的闭合序列模式CloSpan算法进行了描述,并对它们的执行过程及其特点进行了分析与比较,总结了各自的优缺点,指出PrefixSpan算法适用于短序列方面挖掘,而CloSpan算法在长序列或者阈值较低时胜过PrefixSpan算法且CloSpan算法挖掘大型的数据库有更好的性能,得出的结果对序列模式挖掘的设计有重要的参考价值. 相似文献
3.
序列模式挖掘是从序列数据库中挖掘相对时间或其他模式出现频率高的模式。针对PrefixSpan算法构造投影数据库时开销巨大、扫描效率不高的问题,通过以序列扩展代替项集进行扩展、放弃挖掘序列数小于阈值min_support的投影数据库以及直接递归局部频繁项等方式进行改进,并将改进方法应用于Web用户行为模式挖掘中,对日志记录中的规律进行分析和研究。实验分析表明,相比PrefixSpan算法,该改进算法在算法效率方面有一定的提高。 相似文献
4.
5.
6.
在序列数据库更新时,现有的增量式序列模式挖掘算法只提到序列的插入操作和序列的扩展操作两种情况,没有针对序列删除操作。提出了一种基于序列树的增量式序列模式更新算法(ISPST)。当数据库更新时,ISPST算法只需要对与删除序列有关的序列构造投影数据库,实现对序列树的更新操作,通过深度优先遍历序列树得到更新后数据库中的所有序列模式。实验结果表明,当支持度发生变化时,ISPST算法在时间性能上优于PrefixSpan算法和IncSpan算法。 相似文献
7.
序列模式挖掘是数据挖掘的重要分支,关于序列模式挖掘的算法非常多,SPAM算法就是序列模式挖掘算法的一种,Perfixspan算法(基于投影的算法)也是序列模式挖掘算法的一种。SPAM算法和Perfixspan算法各有优缺点。研究这两种算法的基础上给出了一种结合这二种算法优点进行改进的算法。 相似文献
8.
无重复投影数据库扫描的序列模式挖掘算法 总被引:5,自引:0,他引:5
序列模式挖掘在Web点击流分析、自然灾害预测、DNA和蛋白质序列模式发现等领域有着广泛应用.基于频繁模式增长的PrefixSpan是目前性能最好的序列模式挖掘算法之一.然而在密数据集和长序列模式挖掘过程中会出现大量的重复投影数据库,使得这类算法性能下降.算法SPMDS通过对投影数据库的伪投影做单项杂凑函数,如MD5等,检查是否存在重复的投影数据库,避免大量重复数据库的扫描,并采用一些必要条件简化投影数据库的搜索,进而提高算法的性能.实验和分析都表明SPMDS性能优于PrefixSpan. 相似文献
9.
现有的增量式挖掘算法在支持度发生变化时,需要对序列数据库进行重复挖掘,为减少由此产生的时空消耗,提出一种高效的增量式序列模式挖掘算法。算法采用频繁序列树作为序列存储结构,当序列数据库和最小支持度发生变化时,通过执行更新操作,实现频繁序列树的更新,利用深度优先遍历频繁序列树找到序列数据库中所有的序列模式。实验结果表明,与IncSpan算法和PrefixSpan算法相比,该算法的挖掘效率较高。 相似文献
10.
11.
Mining sequential patterns by pattern-growth: the PrefixSpan approach 总被引:12,自引:0,他引:12
Jian Pei Jiawei Han Mortazavi-Asl B. Jianyong Wang Pinto H. Qiming Chen Dayal U. Mei-Chun Hsu 《Knowledge and Data Engineering, IEEE Transactions on》2004,16(11):1424-1440
Sequential pattern mining is an important data mining problem with broad applications. However, it is also a difficult problem since the mining may have to generate or examine a combinatorially explosive number of intermediate subsequences. Most of the previously developed sequential pattern mining methods, such as GSP, explore a candidate generation-and-test approach [R. Agrawal et al. (1994)] to reduce the number of candidates to be examined. However, this approach may not be efficient in mining large sequence databases having numerous patterns and/or long patterns. In this paper, we propose a projection-based, sequential pattern-growth approach for efficient mining of sequential patterns. In this approach, a sequence database is recursively projected into a set of smaller projected databases, and sequential patterns are grown in each projected database by exploring only locally frequent fragments. Based on an initial study of the pattern growth-based sequential pattern mining, FreeSpan [J. Han et al. (2000)], we propose a more efficient method, called PSP, which offers ordered growth and reduced projected databases. To further improve the performance, a pseudoprojection technique is developed in PrefixSpan. A comprehensive performance study shows that PrefixSpan, in most cases, outperforms the a priori-based algorithm GSP, FreeSpan, and SPADE [M. Zaki, (2001)] (a sequential pattern mining algorithm that adopts vertical data format), and PrefixSpan integrated with pseudoprojection is the fastest among all the tested algorithms. Furthermore, this mining methodology can be extended to mining sequential patterns with user-specified constraints. The high promise of the pattern-growth approach may lead to its further extension toward efficient mining of other kinds of frequent patterns, such as frequent substructures. 相似文献
12.
From sequential pattern mining to structured pattern mining: A pattern-growth approach 总被引:10,自引:0,他引:10 下载免费PDF全文
Jia-WeiHan JianPei Xi-FengYan 《计算机科学技术学报》2004,19(3):0-0
Sequential pattern mining is an important data mining problem with broad applications. However,it is also a challenging problem since the mining may have to generate or examine a combinatorially explosivenumber of intermediate subsequences. Recent studies have developed two major classes of sequential patternmining methods: (1) a candidate generation-and-test approach, represented by (i) GSP, a horizontal format-basedsequential pattern mining method, and (ii) SPADE, a vertical format-based method; and (2) a pattern-growthmethod, represented by PrefixSpan and its further extensions, such as gSpan for mining structured patterns. In this study, we perform a systematic introduction and presentation of the pattern-growth methodologyand study its principles and extensions. We first introduce two interesting pattern-growth algorithms, FreeSpanand PrefixSpan, for efficient sequential pattern mining. Then we introduce gSpan for mining structured patternsusing the same methodology. Their relative performance in l 相似文献
13.
Karam Gouda Mosab Hassaan Mohammed J. Zaki 《Journal of Computer and System Sciences》2010,76(1):88-102
Sequence mining is one of the fundamental data mining tasks. In this paper we present a novel approach for mining frequent sequences, called Prism. It utilizes a vertical approach for enumeration and support counting, based on the novel notion of primal block encoding, which in turn is based on prime factorization theory. Via an extensive evaluation on both synthetic and real datasets, we show that Prism outperforms popular sequence mining methods like SPADE [M.J. Zaki, SPADE: An efficient algorithm for mining frequent sequences, Mach. Learn. J. 42 (1/2) (Jan/Feb 2001) 31–60], PrefixSpan [J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, M.-C. Hsu, PrefixSpan: Mining sequential patterns efficiently by prefixprojected pattern growth, in: Int'l Conf. Data Engineering, April 2001] and SPAM [J. Ayres, J.E. Gehrke, T. Yiu, J. Flannick, Sequential pattern mining using bitmaps, in: SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining, July 2002], by an order of magnitude or more. 相似文献
14.
WebLog访问序列模式挖掘 总被引:4,自引:0,他引:4
WebLog挖掘的基本思想是将数据挖掘技术应用于Web服务器的日志文件。通过WebLog的序列模式挖掘可以改善Web的信息服务。该文介绍了传统的WebLog中访问序列模式挖掘的方法,并在此基础上提出了一种对WAP-tree的改进构造方法。 相似文献
15.
当今互联网所提供的功能和服务越来越多,Web内容也越来越丰富,移动应用越来越流行。然而,复杂的Web服务应用对用户提出了更高的要求,给用户浏览带来了很多问题,很多时候用户会感到无所适从。文中提出基于用户浏览序列模式的用户行为提取与分析方法。该方法可以分为浏览模式分析和用户聚类两部分。在浏览模式分析时,首先根据用户行为数据得到浏览序列,然后运用序列模式挖掘PrefixSpan算法获取用户习惯的浏览模式,最后把分析获取的用户浏览模式应用到Web浏览中,为不同的用户需求提供个性化的服务。在用户聚类时,运用层次聚类方法按照浏览模式的相似性对用户进行聚类,以分析用户的不同属性(如年龄、职业、学历等)对用户浏览模式的影响。实验结果表明,文中采用的PrefixSpan算法和层次聚类方法在用户浏览模式分析和研究方面具有很好的可行性和有效性。 相似文献
16.
传统的数据挖掘方法会生成大量的模式和规则,且难以理解,而实际上用户感兴趣的只是其中的一小部分.针对该问题,在挖掘序列模式的PrefixSpan算法基础上提出一种带数据项约束的序列模式挖掘方法,通过数据项约束,减少了搜索空间.实验结果表明,该方法可以有效地挖掘出满足数据项约束的序列模式. 相似文献
17.
In this paper, we deal with mining sequential patterns in multiple time sequences. Building on a state-of-the-art sequential
pattern mining algorithm PrefixSpan for mining transaction databases, we propose MILE (MIning in muLtiple sEquences), an efficient algorithm to facilitate the mining process. MILE recursively utilizes the knowledge of existing patterns
to avoid redundant data scanning, and therefore can effectively speed up the new patterns’ discovery process. Another unique
feature of MILE is that it can incorporate prior knowledge of the data distribution in time sequences into the mining process
to further improve the performance. Extensive empirical results show that MILE is significantly faster than PrefixSpan. As
MILE consumes more memory than PrefixSpan, we also present a solution to trade time efficiency in memory constrained environments.
相似文献
Xingquan ZhuEmail: |