IMSR_PreTree: an improved algorithm for mining sequential rules based on the prefix-tree

Sequential rules generated from sequential patterns express temporal relationships among patterns. Sequential rule mining is an important research problem because it has broad application such as the analyses of customer purchases, web log, DNA sequences, and so on. However, developing an efficient algorithm for mining sequential rules is a difficult problem due to the large size of the sequential pattern set. The larger the sequential pattern set, the longer the mining time. In this paper, we propose a new algorithm called IMSR_PreTree which is an improved algorithm of MSR_PreTree that mines sequential rules based on prefix-tree. IMSR_PreTree also generates rules from frequent sequences stored in a prefix-tree but it prunes the sub trees which give non-significant rules very early in the process of rule generation and avoids tree scanning as much as possible. Thus, IMSR_PreTree can significantly reduce the search space during the mining process. Our performance study shows that IMSR_PreTree outperforms MSR_PreTree, especially on large sequence databases.