Mining sequential patterns by pattern-growth: The PrefixSpan approach
Mining sequential patterns by pattern-growth: The PrefixSpan approach
复制标题
DOI：
10.1109/tkde.2004.77
复制
发表时间：
2004-11-01
影响因子：
8.9
通讯作者：
Hsu, MC
中科院分区：
文献类型：
--
作者：
Pei, J;Han, JW;Hsu, MC
顺序模式挖掘是一个重要的数据挖掘问题，有着广泛的应用。然而，这也是一个困难的问题，因为挖掘可能必须生成或检查组合爆炸性数量的中间子序列。大多数以前开发的顺序模式挖掘方法，如GSP，探索候选生成和测试方法[1]，以减少要检查的候选数量。然而，这种方法在挖掘具有大量模式和/或长模式的大型序列数据库时可能效率不高。在本文中，我们提出了一种基于投影的序列模式增长方法，用于有效地挖掘序列模式。在这种方法中，序列数据库被递归地投影到一组较小的投影数据库中，序列模式通过仅探索局部频繁片段在每个投影数据库中生长。基于对基于模式增长的顺序模式挖掘的初步研究，我们提出了一种更有效的方法，称为PSP，它提供有序增长和减少预测数据库。为了进一步提高性能，在PrefixSpan中开发了一种伪投影技术。综合性能研究表明，在大多数情况下，PrefixSpan优于基于优先级的算法GSP、FreeSpan和SPADE[29]（一种采用垂直数据格式的顺序模式挖掘算法），并且在所有测试算法中，PrefixSpan集成伪投影是最快的。此外，这种挖掘方法可以扩展到挖掘具有用户指定约束的顺序模式。模式增长方法的高前景可能导致其进一步扩展到有效挖掘其他类型的频繁模式，例如频繁子结构。
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 [1] 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 [8], 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 [29] ( 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.