PrefixSpan algorithm: derived from FreeSpan. The shrink speed is faster than FreeSpan.

University of Michigan - Ann Arbor

Sequential pattern mining is an important research field in data mining. It refers to finding frequent event sequences with a certain order from huge transaction records. At present, sequence pattern mining has been widely used in DNA sequence licensing, customer shopping behavior analysis, website access law analysis and network behavior law analysis.

For example, the transaction data of a large supermarket chain has a series of user transaction databases. Each record includes the user's ID, the time when the transaction occurred and the items involved in the transaction. If we can mine the patterns involving the association relationship between transactions, that is, the relationship between users' several purchase behaviors, we can take more targeted marketing measures.

Sequential Pattern Mining

FreeSpan is a sequential-pattern-mining algorithm based on frequent-pattern projection, using a divide-and-conquer strategy. Instead of generating and testing candidate sequences, it recursively uses the current set of frequent items to project the sequence database into a set of smaller projected databases, then mines sub-sequence fragments within each projection. This confines each subsequent test to a smaller projected database that matches the pattern being examined, dividing both the data and the set of patterns under consideration. Advantage: it reduces the overhead of generating candidate sequences. Disadvantage: it may generate many projected databases, which can become computationally expensive.

FreeSpan algorithm

Apriori algorithm: the original algorithm of association analysis, which is used to find frequent itemsets from candidate sets. Two steps: self connection and pruning. Disadvantages: no sequence.

AprioriAll algorithm: the execution process of AprioriAll algorithm is the same as that of Apriori algorithm. The difference lies in the generation of candidate set. It is necessary to distinguish the front and back of the last two elements.

AprioriSome algorithm: it can be regarded as an improvement of apriorall algorithm.

Apriori algorithm

GPS algorithm: it is used to find frequent itemsets with sequential order from the candidate item set. Two steps: self-connection and pruning. Disadvantages: Every time the support is calculated, all data sets need to be scanned; for the case of a very long sequence pattern, the algorithm is difficult to handle because the scale of the corresponding short sequence pattern is too large.

GPS algorithm

SPADE algorithm: Improved GPS algorithm to avoid the problem of scanning the data set D multiple times. It is roughly the same as the GSP algorithm, with an additional ID_LIST record, so that each ID_LIST is obtained according to the previous ID_LIST (thus obtaining support). The scale of ID_LIST is reduced as the pruning continues. Therefore, the problem of multiple scans of data set D by the GSP algorithm is solved.

Learn Before

Related