WSpan: Weighted sequential pattern mining in large sequence databases

Sequential pattern mining algorithms have been developed which mine the set of frequent subsequences satisfying a minimum support constraint in a sequence database. However, previous sequential mining algorithms treat sequential patterns uniformly while sequential patterns have different importance. Another main problem in most of the sequence mining algorithms is that they still generate an exponentially large number of sequential patterns when a minimum support is lowered and they do not provide alternative ways to adjust the number of sequential patterns other than increasing the minimum support. In this paper, we propose a Weighted Sequential pattern mining algorithm called WSpan. Our main approach is to push the weight constraints into the sequential pattern growth approach while maintaining the downward closure property. A weight range is defined to maintain the downward closure property and items are given different weights within the weight range. In scanning a sequence database, a maximum weight in the sequence database is used to prune weighted infrequent sequential patterns and in the mining step, maximum weights of projected sequence databases are used. By doing so, the downward closure property can be maintained. WSpan generates fewer but important weighted sequential patterns in large databases, particularly dense databases with a low minimum support, by adjusting a weight range. Introduction