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

Sequential pattern mining is to find all frequent sub sequences as sequential patterns in a sequence database. A sequence database is a large collection of records, where each record is an ordered list of events. Each event can have one or many items. For examples, the customer purchase database is a popular database in which each event is a set of items (itemset) and some other databases such as DNA sequences and Web log data are typically examples of the databases in which all events are single items.

The problem of mining sequential patterns was first introduced by Agrawal and Srikant in [2]. They also presented three algorithms to solve this problem. All these algorithms are variations of the Apriori algorithm [1] proposed by the same authors and used in association rule mining. Many other approaches have been developed since then [2, 3, 11, 12, 15, 16, 19]. The general idea of all methods is outlined as follows: starting with more general (shorter) sequences and extending them towards more specific (longer) ones. However, existing methods uses specified data structures to “represent” the database and have different strategies to traverse and enumerate the search space.

GSP [19] which is also a typical Apriori-like method adopts a multiple pass, candidate generation, and test approach in sequential pattern mining. But it incorporates time constraints, sliding time windows, and taxonomies in sequence patterns. PSP [15] which is another Apriori-based algorithm also builds around GSP, but it uses a different intermediary data structure which is proved more efficient than that used in GSP.

Based on the “divide and conquer” philosophy, FreeSpan [12] is the first algorithm which projects the data sequences into smaller databases for reducing the I/O costs. This strategy has been continually used in PrefixSpan [16]. Starting from the frequent items of the database, PrefixSpan generates projected databases with each frequent item. Thus, the projected databases contain only suffixes of the data-sequences from the original database, grouped by prefixes. The pattern is extended by adding one item in frequent itemsets which are obtained from projected databases. The process is recursively repeated until no frequent item is found in the projected database.

All the above methods utilize the same approach in sequence mining: the horizontal data sequence layout. And the corresponding algorithms make multiples of passes over the data for finding the supports of candidate sequences. Some methods have approached the vertical data layout to overcome this limitation; they are SPADE [22], SPAM [3] and PRISM [10]. Instead of browsing the entire sequence database for each pattern, these algorithms store the information indicating which data sequences contain that pattern so that its support is determined quickly. Moreover, the information of a new pattern is also constructed from old patterns’ information.

The SPADE algorithm [22] uses a vertical id-list representation of the database where it stores a list of all input sequence (sequence id) and event identifier (event id) pairs containing the pattern for each level of the search space for each pattern. On the other hand, SPADE uses a lattice-theoretic approach to decompose the search space and uses simple join operations to generate candidate sequences. SPADE discovers all frequent sequences in only three database scans. The SPADE algorithm outperforms GSP by a factor of two at lower support values [22].

SPAM [3] is another method that maintains the information of a pattern. It uses a vertical bitmap representation of the database for both candidate representation and support counting. SPAM outperforms SPADE by about a factor of 2.5 on small datasets and better than an order of magnitude for reasonably large datasets.

PRISM [10] was proposed in 2010. It is one of the most efficient methods for frequent sequence mining [10]. Similar to SPAM, PRISM also utilizes a vertical approach for enumeration and support counting but it is different from the previous algorithms. This algorithm uses the prime block encoding approach to represent candidate sequences and uses join operations over the prime blocks to determine the support of each candidate. Especially, all sequential patterns which are found by this algorithm are organized and stored in a tree structure which is the basis for our proposed algorithm—MSR_PreTree.

Besides, there are several sequential pattern mining techniques that are simply applied to web log mining such as WAP-Mine [17] with WAP-tree; and PLWAP [7] with its PLWAP-tree, FS-Miner [6], etc.

In this section, we discuss existing contributions in sequential rule mining research. Sequential rules [14, 18, 21, 22] are “if-then rules” with two measures which quantify the support and the confidence of the rule for a given sequence database. For example, if a customer buys a car, then he will also buy a car insurance.

The study in [18] has proposed a method for generating a complete set of sequential rules from frequent sequences and removing redundant rules in the post-mining phase. Based on the description in [18], Lo et al. [14] generalized the Full algorithm for mining a full set of sequential rules and it is completely the same algorithm as the RuleGen algorithm proposed by Zaki [22].

Full algorithm: First, the algorithm finds all frequent sequences (FS) whose support is no less than minSup by using an existing method. For each frequent sequence, the algorithm generates all sequential rules from that frequent sequence. We now describe the process of rule generation in more detail.

For each frequent sequence \(f\) of size \(k\), it is possible to generate \((k-1)\) rules. Each rule is expressed as pre \(\rightarrow \) post, in which pre is a prefix of sequence \(f\) and pre \(++\) post = f. For example, from a sequence \(\langle \)(AB)(B)(C)\(\rangle \), we can generate two candidate sequential rules: \(\langle \)(AB)\(\rangle \rightarrow \langle \)(B)(C)\(\rangle \) and \(\langle \)(AB)(B)\(\rangle \rightarrow \langle \)(C)\(\rangle \). For each frequent sequence \(f\), Full generates and examines every prefixes of \(f\) in turn. For each prefix pre, it tries to form a rule pre \(\rightarrow \) post where post is the postfix of \(f\) with respect to prefix pre. After that, it passes over FS to find that the prefix’s support and calculates the confidence of that rule. If the confidence is not less than the minimum confidence threshold, we have a significant sequential rule. This process is repeated until all frequent sequences are considered. Let \(n\) be the number of sequences in FS, and \(k\) be the size of the largest sequence in FS; the complexity of this algorithm is \(O(n*k*n)\) (without including the time of prefix generation). The major cost of Full is the database scan. It has to scan the database many times for counting the support of every prefixe of a frequent sequence.

In order to improve the runtime, we proposed two algorithms: MSR_ImpFull and MSR_PreTree [21].

MSR_ ImpFull algorithm: It is an improved version of Full. As mentioned above, to generate rules from a frequent sequence, Full has to split it to get the prefix and has to browse FS to get the prefix’s support. To overcome this, MSR_ImpFull sorts FS in ascending order of their size before generating rules. After sorting, we have the fact that the sequences which contain sequence \(X\) as a prefix must be after \(X\) because their size is larger. Therefore, for a frequent sequence \(f\) in FS, MSR_ImpFull does not have to split it; it browses the sequences following \(f\) to find which sequences contain \(f\) as a prefix. After that, it generates rules from the found sequences and \(f\). The generated rule is f \(\rightarrow \) post, where post is the postfix of the found sequence with prefix \(f\). The confidence is calculated directly from the found sequence’s support and \(f\)’s support. MSR_ImpFull reduces k FS scans for each sequence of size \(k\) when compared with Full. So, if we consider only the number of FS scans without the time of prefix checking, then the complexity of MSR_ImpFull is \(O(n*n).\)

MSR_PreTree algorithm: Although MSR_ImpFull algorithm has less number of FS scans than Full, for each sequence \(f\), it scans all sequences following \(f\) to identify which sequence contains \(f\) as a prefix. In order to overcome this, MSR_PreTree uses a prefix-tree structure presented in Sect. 4. Every node in the prefix-tree is always the prefix of its child nodes (only sequence-extended nodes). Consequently, it is possible to generate rules directly without scanning all frequent sequences for prefix checking.

Besides, Fournier-Viger et al. [8‐10] have recently discussed a more general form of sequential rules such that items in the prefix and in the postfix of each rule are unordered. However, our study simply focuses on mining usual sequential rules.

In our approach (MSR_PreTree, IMSR_PreTree), the set of rules is generated from frequent sequences, which is organized and stored in a prefix-tree structure as illustrated in Fig. 1. In this section, we briefly outline the prefix-tree.

The prefix-tree is built recursively as follows: starting from the root of tree at level 0, the root is a virtual node labeled with a null sequence \(\phi \) and the support is 0. At level \(k\), a node is labeled with a \(k\)-sequence and its support count. Recursively, we have nodes at the next level \((k+1)\) by extending the \(k\)-sequence with a frequent item. If the support of the new extended sequence satisfies minSup, then we store that sequence and continue the extension recursively. There are two ways to extend a \(k\)-sequence: sequence extension and itemset extension [10]. In sequence extension, we add an item to the sequence as a new itemset. Consequently, the size of a sequence-extended sequence always increases.

For example, Fig. 1 shows the prefix-tree of frequent sequences. \(\langle \)(A)(A)\(\rangle \) and \(\langle \)(A)(B)\(\rangle \) are sequence-extended sequences of \(\langle \)(A)\(\rangle \), and \(\langle \)(AB)\(\rangle \) is an itemset-extended sequence of \(\langle \)(A)\(\rangle \). Sequence \(\langle \)(A)\(\rangle \) is a prefix of all sequences in T1 and it is an incomplete prefix of sequences in T2.

In MSR_PreTree, for each node \(r\) in the prefix-tree, the algorithm browses all the child nodes of \(r\) and considers each candidate rule generated by each child node with respect to prefix r.sequence, if the candidate rule’s confidence satisfies minConf then that rule is outputted. Thus, the algorithm must still browse the child nodes which produce non-significant rules with respect to prefix r.sequence. For example, if node \(r\) has 1,000 child nodes, then it has to browse all those nodes, calculates the confidence of all those nodes, and checks the confidence with minConf even if there are certainly nodes which produce non-significant rules among those nodes. Considering the recursive characteristic in the implementation, this cost is too high. So, it is necessary to avoid browsing the child nodes which do not produce significant rules. Consequently, the key problem is that how to know which child nodes certainly produce non-significant rules.

To overcome this problem, we improve MSR_PreTree to early prune the sub trees which produce non-significant rules. We have the following theorem [5]:

The improved algorithm of MSR_PreTree is shown in Fig. 2. Using PRISM [10] we have a full set of frequent sequences stored in the prefix-tree structure which gathers all sequences with a common prefix into a sub-tree. Thus, we generate rules within each common prefix sub-tree. Starting from the first level, each sub-tree rooted at a node \(r\) labeled with \(1-\)sequence can be processed independently to generate sequential rules using procedure GENERATE_RULES_FROM_ROOT(r). This procedure is performed using the following steps:

Step 1 Generating rules with the prefix that is a sequence at the root. Let pre be the sequence at root noder (line 3). From Remarks 1 and  2, we find that sequence pre is the prefix of all the sequences in sequence-extended sub-trees of the root \(r\). Hence, we generate only rules from the sequences in these sub-trees in turn. The following are the descriptions of rule generation from each sub-tree with prefix pre (lines 3–9).

For each l.sequence at node \(l\) in the tree rooted at nseq (that is the sub-tree as mentioned above) including the root and sequence-extended children and itemset-extended children, we consider the following rule: pre\(\rightarrow \)post where post is a postfix of l.sequence with respect to the prefix pre (r.sequence). We apply the above theorem when we have already determined the confidence of the rule generated from node \(l\). If the confidence satisfies minConf, we output that rule and repeat recursively on extended children of \(l\). Otherwise, we completely prune all the sub-trees of \(l.\) It means that we do not need to generate rules from all child nodes and descendents of the node \(l\) with prefix pre. After that, we continue considering the other nodes by backtracking up the tree nseq if it still has child nodes.

In this process (lines 5–9), we traverse the sub-tree in a depth-first manner so that the pruning technique can be applied. Figure 3 shows some pruning cases when generating rules with the prefix R.sequence. The sub-trees rooted at the nodes (highlighted) which generate rules having the confidence less than minConf are pruned. These sub-trees are marked by surrounding line.