GSPalgorithm is an algorithm used for sequence mining. The algorithms for solving sequence mining problems are mostly based on the apriori algorithm. One way to use the level-wise paradigm is to first discover all the frequent items in a level-wise fashion. It simply means counting the occurrences of all singleton elements in the database. Then, the transactions are filtered by removing the non-frequent items. At the end of this step, each transaction consists of only the frequent elements it originally contained. This modified database becomes an input to the GSP algorithm. This process requires one pass over the whole database. GSP algorithm makes multiple database passes. In the first pass, all single items are counted. From the frequent items, a set of candidate 2-sequences are formed, and another pass is made to identify their frequency. The frequent 2-sequences are used to generate the candidate 3-sequences, and this process is repeated until no more frequent sequences are found. There are two main steps in the algorithm.
Candidate Generation. Given the set of frequent -frequent sequences Fk-1, the candidates for the next pass are generated by joining F with itself. A pruning phase eliminates any sequence, at least one of whose subsequences is not frequent.
Support Counting. Normally, a hash tree-based search is employed for efficient support counting. Finally non-maximal frequent sequences are removed.
Algorithm
F1 = the set of frequent 1-sequence k=2, do while Fk-1 != Null; Generate candidate sets Ck ; For all input sequences s in the database D do Increment count of all a in Ck if s supports a End do Fk = k = k+1; End do Result = Set of all frequent sequences is the union of all Fk's
The above algorithm looks like the Apriori algorithm. One main difference is however the generation of candidate sets. Let usassume that: are two frequent 2-sequences. The items involved in these sequences are and respectively. The candidate generation in a usual Apriori style would give as a 3-itemset, but in the present context we get the following 3-sequences as a result of joining the above 2- sequences The candidate-generation phase takes this into account. The GSP algorithm discovers frequent sequences, allowing for time constraints such as maximum gap and minimum gap among the sequence elements. Moreover, it supports the notion of a sliding window, i.e., of a time interval within which items are observed as belonging to the same event, even if they originate from different events.
