USpan: An Efficient Algorithm for Mining High Utility

Sequential pattern mining plays an important role in many applications, such as bioinformatics and consumer behavior analysis. However, the classic frequency-based framework often leads to many patterns being identified, most of which are not informative enough for business decision-making. In frequent pattern mining, a recent effort has been to incorpo-rate utility into the pattern selection framework, so that high utility (frequent or infrequent) patterns are mined which ad-dress typical business concerns such as dollar value associ-ated with each pattern. In this paper, we incorporate utility into sequential pattern mining, and a generic framework for high utility sequence mining is defined. An efficient algo-rithm, USpan, is presented to mine for high utility sequential patterns. In USpan, we introduce the lexicographic quan-titative sequence tree to extract the complete set of high utility sequences and design concatenation mechanisms for calculating the utility of a node and its children with two ef-fective pruning strategies. Substantial experiments on both synthetic and real datasets show that USpan efficiently iden-tifies high utility sequences from large scale data with very low minimum utility