An efficient method for mining non-redundant sequential rules using attributed prefix-trees

摘要

Mining sequential generator patterns and mining closed sequential patterns are important to sequence mining. They address difficulties in the mining of sequential patterns by reducing the number of sequential rules, and the results are often used to generate non-redundant sequential rules. This paper proposes an efficient method for mining non-redundant sequential rules from an attributed prefix-tree. The proposed method has two phases. In the first phase, it builds a prefix-tree that stores all the sequential patterns from a given sequence database. Then in the second phase, it mines non-redundant sequential rules from this prefix-tree. In the prefix-tree building process, each node on the prefix-tree has a field that indicates whether this node is a minimal sequential generator pattern, and another field that indicates whether this node is a closed sequential pattern. By traversing the prefix-tree, non-redundant sequential rules can be easily mined from a minimal sequential generator pattern X to a closed sequential pattern Y such that X is a prefix of Y. In addition, a good pruning mechanism is proposed to reduce the search space and the execution time in the mining process. Experimental results show that the proposed method is more efficient than existing methods in mining non-redundant sequential rules.