Mining and Ranking Generators of Sequential Pattern

Publication Type

Conference Proceeding Article

Publication Date

4-2008

Abstract

Sequential pattern mining ¯rst proposed by Agrawal and Srikant has received intensive research due to its wide range applicability in many real-life domains. Various improvements have been proposed which include mining a closed set of sequential patterns. Sequential patterns supported by the same sequences in the database can be considered as belonging to an equivalence class. Each equivalence class contains patterns partially-ordered by sub-sequence relationship and having the same support. Within an equivalence class, the set of maximal and minimal patterns are referred to as closed patterns and generators respectively. Generators used together with closed patterns can provide additional information which closed patterns alone are not able to provide. Also, as generators are the minimal members, they are preferable over closed patterns for model selection and classi¯cation based on the Minimum Description Length (MDL) principle. Several algorithms have been proposed for mining closed sequential patterns, but none so far for mining sequential generators. This paper ¯lls this research gap by investigating properties of sequential generators and proposing an algorithm to e±ciently mine sequential generators. The algorithm works on a three-step process of search space compaction, non-generator pruning and a ¯nal ¯ltering step. We also introduce ranking of mined generators and propose mining of a unique generator per equivalence class. Performance study has been conducted on various synthetic and real benchmark datasets. They show that mining generators can be as fast as mining closed patterns even at low support thresholds.

Discipline

Software Engineering

Research Areas

Software Systems

Publication

Proceedings of the 8th SIAM International Conference on Data Mining (SDM)

City or Country

Atlanta, USA

Additional URL

http://www.siam.org/proceedings/datamining/2008/dm08_51_Lo.pdf

Link to Full Text

Share

COinS